目录
2.顺序表
2.1概念及结构
顺序表是用一段
物理地址连续
的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组 上完成数据的增删查改。
??1. 静态顺序表：使用定长数组存储元素。
#define N 100
struct SeqList
{
int a[N];
int size;//记录存储了多少个数据
};
2. 动态顺序表：使用动态开辟的数组存储。
#define N 100
typedef int SLDataType;
struct SeqList
{
SLDataType* a;
int size; //存储的数据个数
int capacity;//存储空间的大小
}; 3.动态顺序表项目创建
| 程序名 | 功能 |
| SeqList.h | 创建顺序表，完成一些函数的声明 |
| SeqList.c | 实现顺序表各个函数的定义 |
| test.c | 测试顺序表所需函数是否正确 |
3.1顺序表的初始化
void SeqListInit(SeqList* psl);//初始化
void SeqListInit(SeqList& psl);//&为C++中的引用
?属于两个栈帧里面的两个变量，形参是实参的拷贝，形参的改变不影响实参。改正如下
?3.2顺序表的打印
void SeqListPrint(SeqList* psl)
{
assert(psl);
for (int i = 0; i < psl->size; ++i)
{
printf("%d ", psl->a[i]);
}
printf("\n");
}3.3顺序表尾插
?
?注意增容：
1.首先检查是否容量已经为满（ps->size==ps->capacity)
2.如果为满并且ps->capacity!=0，就增加容量，且以二倍的形式增加；若为满并且ps->capacity=0，说明还是空容量，就增加4个空间
void SeqListPushBack(SeqList*psl,SLDataType x);
{
//如果满了要扩容
if(psl->size==psl->capacity)
{
size_t newCapacity = psl->capacity == 0?4:psl->capacity*2;
SLDataType* tmp = realloc(psl->a,sizeof(SLDataType)*newCapacity);
if(tmp==NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
psl->a = tmp;
psl->capacity =newCapacity;
}
}
psl->a[psl->size] = x;//尾部插入
psl->size++;//实际容量加1
} 1.realloc的第一个参数为空的时候相当于malloc?
2.判断realloc扩容的方式
?
void TestSeqList2()
{
char* p = (int*)malloc(sizeof(int) * 10);
printf("%p\n", p);
int* p1 = (int*)realloc(p, sizeof(int) * 15);
printf("%p\n", p1);
}?
新申请的地址和原来的地址相同：原地扩容。下列代码为异地扩容
?
?
添加一个5可以触发扩容
3.4尾删除法
void SeqListPopBack(SeqList* psl);
{
//psl->a[psl->size - 1] = 0;
psl->size--;
}
?
删完前面的数后插入10和20，打印时未显示。
?改正如下
void SeqListPopBack(SeqList* psl);
{
assert(psl);
//psl->a[psl->size - 1] = 0;
if(psl->size > 0)
{
psl->size--;
}
}3.5头插法
1.同初始化，进行传址
2，检查顺序表内是否还有容量
3.挪动数据，给第一个位置空出来，在空出来的位置上插入新数据
void SeqListPushFront(SeqList* psl, SLDataType x)
{
assert(psl);
SeqListCheckCapacity(psl);//检查是否还有空间
for(int i = psl->size;i>0;i--)
{
psl->a[i] = psl->a[i-1];
}
psl->a[0] = x;
psl->size++;
}?或者为
void SeqListPushFront(SeqList* psl, SLDataType x)
{
assert(psl);
SeqListCheckCapacity(psl);//检查是否还有空间
int end = psl->size - 1;
while (end >= 0)
{
psl->a[end + 1] = psl->a[end];
--end;
}
psl->a[0] = x;
psl->size++;
}3.6头删法
?直接挨个把数据向前挪进行覆盖，然后ps->size-1
?
采用for循环
void SeqListPopFront(SeqList* psl)
{
assert(psl->size>0);
for(int i=0;i<psl->size-1;i++)
{
psl->a[i] = psl->a[i+1];
}
psl->size--;
} void SeqListPopFront(SeqList* psl)
{
assert(psl);
//挪动数据覆盖删除
if (psl->size > 0)
{
int begin = 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
++begin;
}
--psl->size;
}
}3.7顺序表的查找操作
给一个元素，查找是否在顺序表内，如果在返回下标，否则返回-1
int SeqListFind(SeqList* psl, SLDataType x)
{
assert(psl->size>0);
assert(psl);
for(int i = 0;i<ps->size;i++)
{
if(psl->a[i] == x)
return i;
}
return -1;
}3.8顺序表的插入操作
函数包含：指定插入下标,和想插入的元素
实现方法: 输入的下标位置及其后,所有数据都往后面挪，然后插入数据,
ps->size+1
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
assert(psl);
assert(psl->size>=pos);//被插入的位置必须小于等于size
SeqListCheckCapacity(psl);
for(int i = psl->size;i>pos;i++)
{
psl->a[i] = psl->a[i-1];
}
psl ->a[pos] = x;
psl ->size++;
}void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
//暴力检查
assert(psl);
//温和的检查
/*if (pos>psl->size)
{
printf("pos 越界：%d\n", pos);
return；
}*/
//暴力检查
assert(pos <= psl->size);
SeqListCheckCapacity(psl);
int end = psl->size - 1;
while (end >pos)
{
psl->a[end + 1] = psl->a[end];
--end;
}
psl->a[pos] = x;
psl->size++;
}?***将size_pos改成int 或者while条件中（end>=pos)改成（end>pos)防止发生整型提升
?
?
3.9顺序表的删除操作
void SeqListErase(SeqList* psl, size_t pos)
{
assert(psl->size>0);//必须有元素可以删除
for(int i = pos;i<psl->size-1;i++)
{
psl->a[i] = psl->a[i+1];
}
psl->size--;
}void SeqListErase(SeqList* psl, size_t pos)
{
assert(psl->size > 0);//必须有元素可以删除
assert(pos < psl->size);
size_t begin = pos + 1；
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
++begin;
}
psl->size++;
}3.10顺序表的元素数量查看操作
size_t SeqListSize(SeqList* psl)
{
assert(psl);
return psl->size;
}3.11顺序表某个元素的修改操作
void SeqListAt(SeqList* psl, size_t pos, SLDataType x)
{
assert(psl);
assert(pos<psl->size);
psl->a[pos] = elem;
}3.12顺序表的销毁操作
void SeqListDestroy(SeqList* psl)
{
assert(psl)
if(psl->a!=NULL)
{
free(psl->a);
psl->a = NULL;
}
psl->size = psl->capacity = 0;
}?3.13顺序表的增容操作
void SeqListCheckCapacity(psl)
{
//如果满了要扩容
if(psl->size==psl->capacity)
{
size_t newCapacity = (psl->capacity)== 0?4:(psl->capacity)*2;
SLDataType* tmp = realloc(psl->a,sizeof(SLDataType)*newCapacity);
if(tmp==NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
psl->a = tmp;
psl->capacity =newCapacity;
}
}
}
4.补充
越界不一定可以检查出来，不一定报错，越界是抽查
尾插尾删时间复杂度O(1)
头插头删时间复杂度O(N)
大致设置一个菜单包含各个功能
void menu()
{
printf("********************************\n");
printf("1.尾插数据 2.头插数据\n");
printf("5.打印数据 6.查找数据\n");
printf("-1退出\n");
}
int main()
{
int optiong = -1;
SeqList s;
SeqListInt(&s);
do
{
menu();
scanf("%d", &option);
if (option==1)
{
printf("输入要尾插的数据：>");
//int val = 0;
SLDataType val = 0;
scanf("%d", &val);
SeqListPushBack(&s, val);
}
else if(option == 5)
{
SeqListPrint(&s);
}
} while (optiong != -1);
SeqListDestroy(&s);
return 0;
}2.用Erase和Insert等效
SeqListPushBack(SeqList* psl, SLDataType x);
SeqListInsert(psl, psl->size, x);
SeqListPopBack(SeqList* psl);
SeqListErase(psl, psl->size-1);
SeqListPushFront(SeqList* psl, SLDataType x);
SeqListInsert(psl, 0, x);
SeqListPopFront(SeqList* psl);
SeqListErase(psl, 0);