静态顺序表和动态顺序表-创新互联
实现一个静态顺序表，首先，要定义一个保存数据的数组，保存在结构体中，用size来存储数组中的元素个数，
typedef struct SeqList
{
DataType array[MAX_SIZE];
size_t size;
}SeqList;首先来实现一下静态顺序表的初始化函数，可以借用系统的memset函数来实现，开辟一块空间全部初始化为0，没有存入数据所以size也为0
void InitSeqList(SeqList *pSeq)
{
assert(pSeq);
memset(pSeq->array, 0, sizeof(DataType)*MAX_SIZE);
pSeq->size = 0;
}然后简单的实现一下尾插的函数，把顺序表和需要插入的数据传给函数
void PushBack(SeqList *pSeq, DataType x)
{
assert(pSeq);//断言顺序表
if (pSeq->size >= MAX_SIZE)//判断顺序表是否已满，满的话就输出这个顺序表已满并返回程序
{
printf("The SeqList is Full.\n");
return;
}
pSeq->array[pSeq->size++] = x;//把需要尾插的数据插入顺序表末尾的下一个元素
}
尾删函数，只需要把顺序表传给函数，
void PopBack(SeqList *pSeq)
{
assert(pSeq);//断言，养成良好的代码习惯，方便出错时的检查工作
if (pSeq->size array[pSeq->size] = 0;//将顺序表的最后一个元素置为0，
--pSeq->size;//size减一
}
实现简单的头插函数
void PushFront(SeqList *pSeq, DataType x)
{
int begin = pSeq->size;//保存顺序表的元素个数
assert(pSeq);
if (pSeq->size >= MAX_SIZE)
{
printf("The SeqList is Full.\n");
return;
}
for (; begin >= 0; --begin)//从顺序表末尾开始移动元素，把第一个元素的位置空出来
{
pSeq->array[begin] = pSeq->array[begin - 1];
}
pSeq->array[0] = x;//将第一个位置插入需要插入的元素
pSeq->size++;//size加一
}
简单的头删函数，原理与头插相似，从第一个位置开始移动元素，覆盖第一个位置，将size减一
void PopFront(SeqList* pSeq)
{
int begin = 0;
assert(pSeq);
if (pSeq->size <= 0)
{
printf("The SeqList is NULL");
return;
}
for (; begin size; begin++)
{
pSeq->array[begin] = pSeq->array[begin + 1];
}
pSeq->size--;
}
//实现一个查找函数，如果找到了，就返回它的下标，如果没找到，就返回-1
int Find(SeqList* pSeq, size_t pos, DataType x)
{
int i = 0;
assert(pSeq);
for (; i < pSeq->size; ++i)
{
if (pSeq->array[i] == x)
{
return i;
}
}
return -1;
}
//插入函数，从顺序表末尾开始向后挪动元素，直到pos位置，将pos位置空出来插入元素
void Insert(SeqList* pSeq, int pos, DataType x)
{
int begin = pSeq->size-1;
assert(pSeq);
assert(pos size);
if (pos >= MAX_SIZE)
{
printf("The SeqList is Full");
return;
}
for (; begin >= pos; begin--)
{
pSeq->array[begin+1] = pSeq->array[begin];
}
pSeq->array[pos] = x;
pSeq->size++;
}
//删除函数
void Erase(SeqList* pSeq, size_t pos)
{
assert(pSeq);
if (pSeq->size<0)
{
printf("The SeqList is empty\n");
return;
}
assert(pos < pSeq->size);
int i = pos;//定义一个i用开保存当前位置
for (; i < pSeq->size; i++)//从当前位置开始向后，依次用之后的元素覆盖前面的元素，达到删除它的作用
{
pSeq->array[i] = pSeq->array[i + 1];
}
--(pSeq->size);
}
//删除指定元素
int Remove(SeqList* pSeq, DataType x)
{
int pos;
assert(pSeq);
if (pSeq->size size <= 0)
{
printf("The SeqList is empty\n");
return;
}
pos = Find(pSeq, 0, x);
while (pos != -1)
{
Erase(pSeq, pos);
pos = Find(pSeq, pos,x);//把顺序表，当前位置和要删除的元素传给Find函数，循环查找删除，直到把该元素全部删除
}
}
//但上面那种方法不够高效，没删除一次就需要把之后的元素全部向前挪动一次，频繁的挪动导致该函数比较低效，用count计数，计算每个元素前出现几次需要删除的元素，就将该元素向前挪动几个位置
void RemoveAll(SeqList* pSeq, DataType x)
{
int count = 0;
int begin = 0;
assert(pSeq);
for (; begin < pSeq->size; ++begin)
{
if (pSeq->array[begin] == x)
{
++count;
}
else
{
pSeq->array[begin-count] = pSeq->array[begin];
}
}
pSeq->size -= count;
}
//冒泡排序函数，参考数组的冒泡排序
void Bubblesort(SeqList* pSeq)//冒泡排序
{
assert(pSeq);
int i = 0;
int j = 0;
for (; i < pSeq->size;i++)
{
for (j = 0; j < pSeq->size - i; j++)
{
if (pSeq->array[j] < pSeq->array[j - 1])
{
DataType temp;
temp = pSeq->array[j - 1];
pSeq->array[j-1] = pSeq->array[j] ;
pSeq->array[j] = temp;
}
}
}
}
//选择排序函数
void Selectsort(SeqList* pSeq)
{
assert(pSeq);
int i = 0;
int j = 0;
int min = 0;
for (j = 0; j < pSeq->size - 1; ++j)
{
min = j;
for (i = j + 1; i < pSeq->size; ++i)
{
if (pSeq->array[i] < pSeq->array[min])
{
min = i;
}
}
Swap(&pSeq->array[min], &pSeq->array[j]);
}
}
//但上面那个函数比较低效，我在下面实现了一个选择排序函数，每次循环可以找出大值和最小值，有效的减少循环次数，提该函数效率
void Selectsort_OP(SeqList* pSeq)
{
int i = 0;
int min = 0;
int max = 0;
int left = 0;
int right = pSeq->size - 1;
assert(pSeq);
while (left < right)
{
min= left;
max = right;
for (i = left; i array[i] < pSeq->array[min])
{
Swap(&pSeq->array[i], &pSeq->array[left]);
}
if (pSeq->array[i] > pSeq->array[max])
{
Swap(&pSeq->array[i], &pSeq->array[right]);
}
}
left++;
right--;
}
}
//在下面，我简单的实现了一下二分查找，一定要注意循环条件
int Binarysearch(SeqList* pSeq, DataType x)
{
assert(pSeq);
int left = 0;
int right = pSeq->size - 1;
while (left <= right)
{
int mid = left - (left - right) / 2;//避免了溢出的问题
if (x < pSeq->array[mid])
{
right = mid;
}
else if (x > pSeq->array[mid])
{
left = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
//下面，是动态顺序表的各个函数的简单实现
typedef struct SeqList
{
DataType* array; //数据块指针
size_t size; //当前有效数据个数
size_t capicity; //容量
}SeqList;
//这个是检查容量，不够时动态开辟空间的函数，借助了系统的relloc函数
void CheckCapicity(SeqList* pSeq)
{
if (pSeq->size >= pSeq->capicity)
{
pSeq->capicity = 2 * pSeq->capicity;
pSeq->array = (DataType *)realloc(pSeq->array, pSeq->capicity*sizeof(DataType));
}
}
其他函数的实现大致都是类似的，只是动态开辟空间，在涉及到元素插入删除时需要检查容量另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
网站栏目：静态顺序表和动态顺序表-创新互联
本文路径：http://scyanting.com/article/hdhsh.html
