线性表是一种在实际中广泛使用的数据结
构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。
但是在物理结构上(内存中)并不一定是连续的，线性表在物
理上存储时，通常以数组和链式结构的形式存储。
2.顺序表
2.1概念及结构
顺序表是用一段
物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。
在数组
上完成数据的增删查改。
使用顺序表的原因在于，数组有一些缺点。
比如c99之前的不支持变长数组。
顺序表是一种储存数据的方式。
在语法上允许不连续存放，但顺序表的储存方式要求数据连续存放。
往往会创建两个项目来实现数据结构，一个源文件，一个头文件。
使用数据结构时，函数调用即可。
数据结构对细节方面的要求很宽泛，实现方式有很多。
顺序表对储存方式有要求：储存的数据从0(相当于下标，表示位置)开始，依次存储
首先创建SeqList.h和SeqList.c文件
在.h文件中进行结构的定义
#define N 100
struct SeqList——sequence顺序
{
int a[N];
int size;
//记录储存了多少数据
};
这里定义的是一个静态的顺序表，不太实用。
因为开小了，不够用；开大了，浪费。
动态顺序表的定义：
struct SeqList
{
int* a;
//使用动态内存开辟来开辟空间
int size;
//记录储存了多少数据，即有效数据个数
int capacity;
//表示存储空间的大小，capacity——容量
};
这样也只能存储int类型的数据，为了存储其他类型的数据，在开头使用typedef重命名：typedef int SLDateType，顺序表中int* a;改为SLDateType* a;
其中SL是SeqList的简写DateType是起的名字，为了防止与后面链表的名字冲突，最好加上前缀。
这样储存其他类型数据时，修改被typedef的类型就行了。
数据结构就是你定义出某种结构出来，可以是顺序表，可以是链表来对数据进行管理。
实现数据结构就是实现对数据增，删，查，改的函数
第一步是初始化函数声明：
void SeqListInit(struct SeqList* psl);
//可以typedef结构体为SeqList//
void SeqListInit(SeqList* psl);
然后涉及动态开辟，使用完后还要销毁，进行销毁函数的声明。
void SeqListDestroy(SeqList* psl);
进行初始化函数定义
void SeqListInit(SeqList* psl)
{
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}
还有一种初始化定义方式：
//初始化的方式自由度很高
void SeqListInit(SeqList* psl, int capacity)
//capacity大小为4
{
psl->a = (int*)malloc(capacity);
psl->size = 0;
psl->capacity = 4;
}
写一定量的代码后一定要进行测试，不要写完后进行测试，错误会多到不想改。
越界检查方式通常是在数组后面加一些标志符来检查，越界的太多会检查不出来
对尾删进行改进：
void SeqListPopBack(SeqList* psl)
//尾删
{
if(psl -> size > 0)
{
psl - > size--;
//直接减少有效数据个数
}
}
完成测试，对程序做一点改进：
如果这样：SeqListPrint(NULL);在程序量特别大时，很容易找不到错误在哪
所以最好对每个传指针函数前加上一个断言
下面介绍首插：
首插时，同样面临一个问题，空间不够会越界，所以一样要检查是否扩容
所以要把上面的扩容部分的代码拷贝过来吗？
最好不要，因为有这样会造成代码的冗余，如果要修改的话，就要修改不止一处。
所以选择用函数实现空间的扩容
声明(SeqList.h)：void SeqListCheckCapacity(SeqList* psl);
//声明可以不写的，因为在首插尾插函数上面，但考虑到有时需要在SeqList.h查看大致的结构，最好还是加上
实现(SeqList.c)：
void SeqListCheckCapacity(SeqList* psl)
{
if (psl->size == psl->capacity)
//如果相同代表有效数据存满了，需要扩容
{
size_t Newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
SLDateType* tmp = (int*)realloc(psl->a, sizeof(SLDateType) * Newcapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
//终止程序，-1是返回码，0代表正常返回，其他都是异常结束
}
else
{
psl->a = tmp;
psl->capacity = Newcapacity;
}
}
}
然后在需要检查的部分写上：SeqListCheckCapacity(psl);
在test.c中要测试的会不断增多，同样用函数来解决main中代码过多的问题
一个小技巧：写代码命名最好和情况符合
void SeqListPushFront(SeqList* psl, SLDateType x)
//首插
{
assert(psl);
SeqListCheckCapacity(psl);
//检查容量
int end = size;
//从末尾开始移值
while(end)
{
psl->a[end] = psl->a[end-1];
}
psl->a[end] = x;
psl->size++;
}
接着测试：
测试结束后解决首删。
void SeqListPopFront(SeqList* psl)
//首删
{
assert(psl);
int begin = 0;
for(begin = 0; begin < psl->size - 1 ; begin++)
{
psl->a[begin] = psl->a[begin+1];
}
if(psl -> size > 0)
{
psl->size--;
}
}
下一个，在任意位置插入删除数据
void SeqListInsert(SeqList* psl, size_t pos, SLDateType x)
{
assert(psl);
assert(pos >= 0 && pos <= psl->size);
SeqListCheckCapacity(psl);
size_t end = psl->size;
while (end > pos)
{
psl->a[end] = psl->a[end - 1];
end--;
}
psl->a[pos] = x;
psl->size++;
}
这是第一次写出来的，有什么问题吗？
大问题没有，细节问题有不少，首先pos是size_t类型，不需要说明pos>=0，其次psl->size是int类型，与pos类型不匹配，虽然也能得到结果。
大部分人第一次写不会考虑pos的范围问题，如果不加断言，pos随便传一个值，就会造成数组越界，断言是相当粗暴的检查方式，大多用于绝对不能出现的情况，可以考虑使用if来较温和的判断，不过每个人有每个人检查的方式，所以具体看个人。
堆区的报错，往往是在free的时候，所以内存忘记释放，还可能导致不报错，在free时报错时都是数组越界。
当取尾值部分这样写时size_t end = psl->size - 1;
while
(end >=
pos
)时，这两行代码会有问题，end是无符号，size是0时，end为-1转为无符号类型是42亿多(在传第一个值时size是0，end =-1还是会变成42亿多)，改end为int类型，在和pos比较时，还是会转换为无符号类型，而且pos是下标，在大多数函数中下标都是以size_t类型传的，非要pos改为用int类型传，在if判断范围时还要加上pos小于0的情况。
还可以将while中的pos强转为int类型，最好的还是目前的代码，end>pos不用考虑-1的情况。
void SeqListInsert(SeqList* psl, size_t pos, SLDateType x)
{
assert(psl);
if(pos > psl->size)
{
printf("pos越界\n");
return;
}
SeqListCheckCapacity(psl);
size_t end = psl->size;
while (end > pos)
{
psl->a[end] = psl->a[end - 1];
end--;
}
psl->a[pos] = x;
psl->size++;
}
任意位置删除：
void SeqListErase(SeqList* psl, size_t pos)
{
assert(psl);
assert(pos < (size_t)psl->size);
//不能等于，等于的位置没有数据
size_t begin = pos + 1;
while (begin < (size_t)psl->size)
{
psl->a[begin - 1] = psl->a[begin];
begin++;
}
psl->size--;
}
完毕
本章节只是对顺序表的学习，用顺序表时c++有现成的。
test.c中
#include"SeqList.h"
void SeqListTest1()
{
SeqList s;
//虽然可以直接初始化，但规范是通过增删查该的函数进行数据的修改
SeqListInit(&s);
SeqListPushBack(&s , 1);
SeqListPushBack(&s , 2);
SeqListPushBack(&s , 3);
SeqListPushBack(&s , 4);
SeqListPushBack(&s , 5);
//最好测试到5，进行一次扩容情况的测试
SeqListPrint(&s);
SeqListPopBack(&s);
SeqListPopBack(&s);
SeqListPrint(&s);
SeqListPopBack(&s);
SeqListPopBack(&s);
SeqListPopBack(&s);
SeqListPopBack(&s);
SeqListPopBack(&s);
SeqListPopBack(&s);
SeqListPushBack(&s , 10);
SeqListPushBack(&s , 20);
SeqListPrint(&s);
}
void SeqListTest2()
{
SeqList s;
SeqListInst(&s);
SeqListPushBack(&s, 10);
SeqListPushBack(&s, 20);
SeqListPushBack(&s, 30);
SeqListPushBack(&s, 40);
SeqListPushFront(&s,11);
SeqListPrint(&s);
}
int main()
{
SeqListTest2();
return 0;
}
SeqList.h中
#include 欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）