静态顺序表只适用于确定需要存多少数据的场景。
静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。
所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以，下面我们实现动态顺序表。
函数声明：
#ifndef _SEQLIST_H_
#define _SEQLIST_H_
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<windows.h>
typedef int SLDataType;//顺序表的动态存储
typedef struct SeqList
{
SLDataType*array;//指向动态开辟的数组
size_t size;//有效数据个数
size_t capacity;//容量空间的大小
}SeqList;
//基本的增删改查接口
void SeqListInit(SeqList*psl, size_t capacity);
void SeqListDestory(SeqList*psl);
void CheckCapacity(SeqList*psl);
void SeqListPushBack(SeqList*psl,SLDataType x);
void SeqListPopBack(SeqList*psl);
void SeqListPushFront(SeqList*psl, SLDataType x);
void SeqListPopFront(SeqList*psl);
int SeqListFind(SeqList*psl, SLDataType x);
void SeqListInsert(SeqList*psl,size_t pos, SLDataType x);
void SeqListErase(SeqList*psl, size_t pos);
void SeqListRemoveFirst(SeqList*psl, SLDataType x);
void SeqListModify(SeqList*psl, size_t pos, SLDataType x);
void SeqListPrint(SeqList*psl);
//扩展面试题的实现
void SeqListBubbleSort(SeqList*psl);
int SeqListBinaryFind(SeqList*psl, SLDataType x);
//本题要求：时间复杂度O（N）空间复杂度O（1）
void SeqListRemoveAll(SeqList*psl, SLDataType x);
#endif /*_SEQLIST_H_*/
函数实现：
#include"SeqList.h"
//基本的顺序表查删改接口
void SeqListInit(SeqList*psl, size_t capacity)
{
psl->array = (SLDataType*)(calloc(capacity, sizeof(SLDataType)));
psl->size = 0;
psl->capacity = capacity;
}
void SeqListDestory(SeqList*psl)//销毁
{
if (psl->array)
{
free(psl->array);
psl->size = 0;
psl->capacity = NULL;
}
}
void CheckCapacity(SeqList*psl)//查满
{
if (psl->size == psl->capacity)
{
psl->capacity *= 2;
psl->array = (SLDataType*)(realloc(psl->array, psl->capacity*sizeof(SLDataType)));
}
}
void SeqListPushBack(SeqList*psl, SLDataType x)//尾插
{
CheckCapacity(psl);
psl->array[psl->size] = x;
psl->size++;
}
void SeqListPopBack(SeqList*psl)//尾删
{
psl->size--;
}
void SeqListPushFront(SeqList*psl, SLDataType x)//头插
{
CheckCapacity(psl);
int i;
for (i = psl->size - 1; i >= 0; i--)
{
psl->array[i + 1] = psl->array[i];
}
psl->array[0] = x;
psl->size++;
}
void SeqListPopFront(SeqList*psl)//头删
{
int i;
for (i = 1; i < psl->size; i++)
{
psl->array[i - 1] = psl->array[i];
}
psl->size--;
}
int SeqListFind(SeqList*psl, SLDataType x)
{
int i;
for (i = 0; i < psl->size; i++)
{
if (psl->array[i] == x)
{
return i;
}
}
return -1;
}
void SeqListInsert(SeqList*psl, size_t pos, SLDataType x)//pos位后插x
{
if (pos < 0 || pos >= psl->size)
{
return -1;
}
CheckCapacity(psl);
int i;
for (i = psl->size-1; i >=pos; i--)
{
psl->array[i + 1] = psl->array[i];
}
psl->array[pos] = x;
psl->size++;
}
void SeqListErase(SeqList*psl, size_t pos)//删除pos值的位置
{
if (pos < 0 || pos >= psl->size)
{
return -1;
}
int i;
for (i = pos; i<psl->size-1; i++)
{
psl->array[i] = psl->array[i+1];
}
psl->size--;
}
void SeqListRemoveFirst(SeqList*psl, SLDataType x)//删除指定值（第一个x）
{
if (SeqListFind(psl, x) != x)
SeqListErase(psl, SeqListFind(psl, x));
}
#if 1
//删除所有的指定值
void SeqListRemoveAll(SeqList*psl, SLDataType x)//方法1：空间O（1）时间O（n）
{
int gap = 0;
int i;
for (i = 0; i < psl->size- gap; i++)
{
if (psl->array[i + gap] == x)
{
gap++;
if (i + gap >= psl->capacity)
{
break;
}
}
psl->array[i] = psl->array[i+gap];
}
psl->size -= gap;
}
#else
void SeqListRemoveAll(SeqList*psl, SLDataType x)//方法2：空间O（n）时间O（n）
{
SLDataType*tmp = (SLDataType*)(calloc(psl->capacity, sizeof(SLDataType)));
int i, j;
for (i = 0, j = 0; i < psl->size; i++)
{
if (psl->array[i] != x)
{
tmp[j] = psl->array[i];
j++;
}
}
free(psl->array);
psl->array = tmp;
psl->size = j;
}
#endif
void SeqListModify(SeqList*psl, size_t pos, SLDataType x)
{
if (pos >= 0 && pos < psl->size)
psl->array[pos] = x;
}
void SeqListPrint(SeqList*psl)
{
int i;
for (i = 0; i < psl->size; i++)
{
printf("%d", psl->array[i]);
}
printf("\n");
}
//扩展面试题的实现
void SeqListBubbleSort(SeqList*psl)
{
int i, j;
SLDataType tmp;
for (i = 1; i < psl->size; i++)
{
j = i;
while (j > 0 && psl->array[j] < psl->array[j - 1])
{
tmp = psl->array[j];
psl->array[j] = psl->array[j - 1];
psl->array[j - 1] = tmp;
j--;
}
}
}
int SeqListBinaryFind(SeqList*psl, SLDataType x)
{
int left = 0;
int right = psl->size - 1;
int mid;
while (left <= right)
{
mid = (left + right) / 2;
if (psl->array[mid] < x)
{
left = mid + 1;
}
else if (psl->array[mid] > x)
{
right = mid - 1;
}
else
return mid;
}
return -1;
}
测试函数：
#include "SeqList.h"
int main()
{
SeqList test;
//创建顺序表
SeqListInit(&test, 20);
//尾插
SeqListPushBack(&test, 1);
SeqListPushBack(&test, 2);
SeqListPushBack(&test, 3);
SeqListPushBack(&test, 4);
SeqListPushBack(&test, 5);
SeqListPushBack(&test, 6);
SeqListPushBack(&test, 7);
SeqListPushBack(&test, 8);
SeqListPushBack(&test, 9);
SeqListPushBack(&test, 10);
SeqListPrint(&test);
printf("\n");
//尾删
SeqListPopBack(&test);
SeqListPopBack(&test);
SeqListPrint(&test);
printf("\n");
//头删
SeqListPopFront(&test);
SeqListPopFront(&test);
SeqListPopFront(&test);
SeqListPrint(&test);
printf("\n");
//头插
SeqListPushFront(&test, 6);
SeqListPushFront(&test, 7);
SeqListPushFront(&test, 8);
SeqListPushFront(&test, 9);
SeqListPushFront(&test, 10);
SeqListPushFront(&test, 11);
SeqListPrint(&test);
printf("\n");
SeqListPopFront(&test);
SeqListPopFront(&test);
SeqListPopFront(&test);
SeqListPrint(&test);
printf("\n");
//顺序表查找
int ret1 = SeqListFind(&test, 6);
if (ret1 == -1)
{
printf("not find.....\n");
}
else
{
printf("find it....and the pos is:%d\n", ret1);
}
printf("\n");
//插入
SeqListInsert(&test, 6, 99);
SeqListPrint(&test);
printf("\n");
//擦除
SeqListErase(&test, 6);
SeqListPrint(&test);
printf("\n");
SeqListPushFront(&test, 66);
SeqListPushFront(&test, 66);
SeqListPushFront(&test, 66);
SeqListPushFront(&test, 66);
SeqListPushFront(&test, 66);
SeqListPrint(&test);
printf("\n");
//删除第一个值为66的元素
SeqListRemoveFirst(&test, 66);
SeqListPrint(&test);
printf("\n");
//删除所有值为66的元素
SeqListRemoveAll(&test, 66);
SeqListPrint(&test);
printf("\n");
//将第pos位的值修改为x
SeqListModify(&test, 2, 100);
SeqListPrint(&test);
printf("\n");
//冒泡排序
SeqListBubbleSort(&test);
SeqListPrint(&test);
printf("\n");
//二分查找
int ret2 = SeqListFind(&test, 100);
if (-1 == ret2)
{
printf("not find....\n");
}
else
{
printf("find it......and the pos is:%d\n", ret2);
}
printf("\n");
SeqListDestory(&test);
system("pause");
return 0;
}
