http://9195095.blog.51cto.com/9185095/1712715 顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。分为静态顺序表和动态顺序表。 .h文件
#pragma once
#include<string.h>
#include<assert.h>
#include<malloc.h>
typedef int DataType;
typedef struct SeqList //定义一个结构体
{
DataType* arry;
size_t size;
size_t capacity;
}SeqList;
void InitSeqList(SeqList*Seq); //初始化结构体
void PrintSeqList(SeqList*Seq); //输出函数
void PushBack(SeqList*Seq,DataType x); //后面插入数据
void PopBack(SeqList*Seq); //后面删除数据
void PushFrant(SeqList*Seq,DataType x); //前面插入数据
void PopFrant(SeqList*Seq); //前面删除数据
int Find(SeqList*Seq, DataType x); //查找数据
void Erase(SeqList*Seq, size_t pos); //清除第几个数据
void Remove(SeqList*Seq,DataType x); //删除第一个数据x
void Removeall(SeqList*Seq,DataType x); //删除所有的x
void firstRemoveall(SeqList*Seq, DataType x); //删除所有x的第二种方法
void Modify(SeqList*Seq, size_t pos, DataType x); //把第pos个数据修改成x
void Insert(SeqList*Seq, size_t pos, DataType x); //把第pos个数据插入x
void check(SeqList*Seq); //判断指针是否有效,并动态开辟内存
void check(SeqList*Seq)
{
assert (Seq);
if (Seq->size >= Seq->capacity)
{
DataType* tmp;
Seq->capacity *= 2;
tmp = (DataType*) malloc ( sizeof (DataType)*(Seq->capacity));
memcpy (tmp, Seq->arry, sizeof (DataType)*(Seq->size));
free (Seq->arry);
Seq->arry=tmp;
}
}
void InitSeqList(SeqList*Seq)
{
assert (Seq);
Seq->capacity = 2;
Seq->arry = (DataType*) malloc ( sizeof (DataType)*Seq->capacity);
Seq->size = 0;
}
void PrintSeqList(SeqList*Seq)
{
int i = 0;
for (i = 0; i < ( int )Seq->size; i++)
{
printf ( "%d" , Seq->arry[i]);
}
}
void PushBack(SeqList*Seq, DataType x)
{
check(Seq);
Seq->arry[Seq->size++] = x;
}
void PopBack(SeqList*Seq)
{
assert (Seq);
--Seq->size;
}
void PushFrant(SeqList*Seq, DataType x)
{
check(Seq);
int i = Seq->size-1;
for (; i >= 0; i--)
{
Seq->arry[i + 1] = Seq->arry[i];
}
Seq->arry[0] = x;
++Seq->size;
}
void PopFrant(SeqList*Seq)
{
assert (Seq);
int i =0;
for (; i<=( int )Seq->size;i++)
{
Seq->arry[i] = Seq->arry[i+1];
}
--Seq->size;
}
void Remove(SeqList*Seq, DataType x)
{
assert (Seq);
int i = 0;
for (; i<( int )Seq->size; i++)
{
if (Seq->arry[i] == x)
{
Seq->arry[i] = Seq->arry[i+1];
}
}
--Seq->size;
}
void Removeall(SeqList*Seq, DataType x)
{
assert (Seq);
int firstIndex = 0, secondIndex = 0;
int count = 0;
while (secondIndex<=( int )Seq->size)
{
if (Seq->arry[secondIndex] == x)
{
count++;
}
else
{
Seq->arry[firstIndex] = Seq->arry[secondIndex];
firstIndex++;
}
secondIndex++;
}
Seq->size-=count;
}
void firstRemoveall(SeqList*Seq, DataType x)
{
assert (Seq);
int i = 0;
for (; i <( int )Seq->size; i++)
{
if (Seq->arry[i] == x)
{
int begin = i;
for (; begin < ( int )Seq->size - 1; begin++)
{
Seq->arry[begin] = Seq->arry[begin + 1];
}
--Seq->size;
i--;
}
}
}
int Find(SeqList*Seq, DataType x)
{
assert (Seq);
int i = 0;
for (; i < ( int )Seq->size; i++)
{
if (Seq->arry[i] == x)
{
return Seq->arry[i];
}
else
{
return -1;
}
}
return 0;
}
void Erase(SeqList*Seq, size_t pos)
{
assert (Seq);
int i = pos-1;
for (; i<( int )Seq->size-1; i++)
{
Seq->arry[i] = Seq->arry[i+1];
}
--Seq->size;
}
void Modify(SeqList*Seq, size_t pos, DataType x)
{
check(Seq);
int i = 0;
for (; i <( int ) Seq->size - 1; i++)
{
if (i== pos-1)
{
Seq->arry[i] = pos;
}
}
}
void Insert(SeqList*Seq, size_t pos, DataType x)
{
check(Seq);
int i = Seq->size - 1;
for (; i >= ( int )pos; i--)
{
Seq->arry[i + 1] = Seq->arry[i];
}
Seq->arry[pos] = x;
Seq->size++;
}
|