线性表
线性表 (linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串 …..
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。
1.顺序表
1.1 概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为:
1. 静态顺序表:使用定长数组存储元素。（缺点：开少了不够用，开多了浪费）
2.动态顺序表:使用动态开辟的数组存储。
1.2 顺序表的实现（C语言）
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小,所以下面我们实现动态顺序表。
以通讯录为例：
通讯录中每个联系人的信息：
typedef struct person
{
char name[NAME_MAX];
char sex[SEX_MAX];
int age;
char tele[TELE_MAX];
char addr[ADDR_MAX];
}person;包含：姓名、性别、年龄、电话、地址。NAME_MAX、SEX_MAX、TELE_MAX、ADDR_MAX 是提前用 #define 预定义好的常量。
通讯录的结构：
typedef struct contact
{
person* ps;
int sz;
int capacity;
}contact;person* ps：指向动态内存开辟 person 结构体的指针
int sz：通讯录当前有多少个人。
int capacity：通讯录的容量。
1.3 顺序表的问题及思考
问题:
1. 中间/头部的插入删除,时间复杂度为O(N)
2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。
思考:如何解决以上问题呢?下面给出了链表的结构来看看。
2、链表
2.1 链表的概念及结构
概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
物理结构：（数据实际上在内存中的内存位置，指针的值的变化）
逻辑结构：（为了便于理解，将指针形象化为箭头，指针值的变化反映为指针的移动）
2.2 链表的分类
实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:
1. 单向或者双向
2.戴头或者不戴头
3.循环或者非循环
虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构:
1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。
2.3 单向链表的实现（C语言）
一、定义链表的结点：
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;typedef int SLTDataType; 作用：如果想要链表存储的数据类型是 float ，只需要修改这条语句的 int 就行了。
不能写成：
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
SLTNode* next;
}SLTNode;typedef 在定义完结构体后才起作用。
在继续展示下面的函数前，有必要弄清什么时候该使用 assert 断言指针为 NULL，什么时候不该使用。
该用的时候：实参指针为空是错误的时候。也就是说，实参指针永远不应该为空，为空是错误情况，这个时候就应该使用 assert 断言。
不该使用的情况：实参指针可以为空的时候。也就是说，实参指针为空代表一定的意义的时候，这个时候不应该使用 assert 断言。
二、链表的打印：
void SLTPrint (SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
易错点
1、phead 是指向链表第一个结点的指针，可以为 NULL（表示链表没有数据），所以该函数不需要断言 phead 指针为空。但是对于顺序表，顺序表没有数据的标志是 size = 0，而不是 ps = NULL，所以打印顺序表的数据需要断言 ps
2、cur = cur->next；不能写成 cur++；除非 cur 是指向一个结构体数组，链表的结点是非连续的。
3、while(cur != NULL) 不能写成 while(cur->next != NULL) ，会导致最后一个数据没有打印。（while(cur != NULL) 也可以写成 while(cur)）
三、链表的尾插
void SLPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;
newnode->next = NULL;
if(*pphead == NULL)
{
*pphead = newnode;
}
else
{
// 找尾
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}易错点
1、不能断言 phead，phead == NULL 表示链表无数据，是合法的。
2、找尾部分不能写成：（这样链表链接不上）
// 找尾
SLTNode* tail = *pphead;
while (tail != NULL)
{
tail = tail->next;
}
tail = newnode;
3、if(*pphead == NULL）的判断十分有必要，不能省略。
4、要改变 phead 的内容，函数的参数应该是二级指针。如果不想使用二级指针，可以将函数的返回值的类型设计为 SLTNode* ，返回新的头指针。
5、由于 pphead 是指向 phead 的，pphead 应该永远不为 NULL，但为了避免疏忽大意带来的调试麻烦，有 pphead 为实参的函数都应该断言 pphead。
接下来要多次用到创建结点的操作，将以上创建结点的代码封装成一个函数：
SLTNode* BuyNode(SLTNode** pphead，int x)
{
assert(pphead);
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}五、链表的头插：
void SLTPushFront(SLTNode ** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
以上代码也能应对链表为空的情况
逻辑结构：
对比尾插会发现链表头插的效率更高。
六、链表的尾删
void SLTPopBack (SLTNode** pphead)
{
assert(pphead);
//链表为空
//温柔的检查
//if(*PPhead == NULL)
//{
// return;
//}
//暴力的检查
assert(*pphead != NULL);
if(*PPhead->next == NULL)
{
free(*PPhead);
*pphead = NULL;
return;
}
// 找尾
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
注意点：
1、在找尾的过程中，tail 在指向下一个结点之前，把 tail 赋值给 prev ，便于在找到最后的结点时将最后的结点的上一个结点的 next 指针置为空。
2、结点的存储空间在堆区，删除结点后要释放空间。
3、要考虑到只有一个结点和链表为空的情况，用 if 语句判断一下。
另一种更巧妙的办法：
void SLTPopBack (SLTNode** pphead)
{
assert(pphead);
//链表为空
//温柔的检查
//if(*PPhead == NULL)
//{
// return;
//}
//暴力的检查
assert(*pphead != NULL);
if(*PPhead->next == NULL)
{
free(*PPhead);
*pphead = NULL;
return;
}
// 找尾
SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
prev->next = NULL;
}七、链表的头删
void SLTPopFront(SLTNode ** pphead)
{
assert(pphead);
// 暴力检查
assert(*pphead);
// 温柔的检查
//if (*pphead == NULL)
//return;
SLTNode* first = *pphead;
*pphead = first->next;
free(first);
first = NULL;
}
对比尾删会发现链表头删的效率更高。
八、链表的查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
注意：空链表也能查找，只是返回空指针。
九、在 pos 位置的前面插入
void SLTInsert(SLTNode ** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
if (pos == * pphead)//在第一个位置插入，不就是前插吗
{
SLTPushFront(pphead, x);
}
else
{
// 找到pos的前一个位置
SLTNode* prev = * pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySLTNode(x);
prev->next = newnode;
newnode->next = pos;
}
}逻辑结构：
注意：
1、pos 位置是否在链表上是函数使用者考虑的事，上面的函数不保证 pos 位置是否在链表上，但应该保证 pos 至少不是 NULL。
2、在 pos 位置的后面插入的复杂性比在前面插入的复杂性小，因此在 pos 位置的前面插入的问题可以转化为在 pos 后面插入然后交换 pos 和插入的数据的位置。
十、在 pos 位置的后面插入
avoid SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
以上代码不能写成：
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
pos->next = newnode;
newnode->next = pos->next;
}这会导致 nownode 的 next 成员指向的是它自己。
逻辑结构：
十一、在 pos 位置删除
void SLTErase(SLTNode ** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
//assert(*pphead);
if (*pphead == pos)
{
SLTPopFront(pphead);//就是前删
}
else
{
// 找到pos的前一个位置
SLTNode* prev = * pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
注意：在调用完该函数后，一般由该函数的调用者来 free(pos)。
十二、在 pos 后面删除
void SLTEraseAfter (SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* del = pos->next;//保存pos位置下一个结点的地址
pos->next = pos->next->next;
free(del);
del = NULL;
}
以上代码不能写成：
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
pos->next = pos->next->next;
}
这会导致 pos 后面的结点的地址找不到。
十三、链表的销毁
void SLTDestroy (SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
SLTNode* tmp = cur->next;
free(cur);
cur = tmp;
}
}
2.4 双向循环链表的实现（C语言）
双向循环链表的初始形态应该是怎样呢？也就是说，如果一个双向循环链表没有数据，它该是怎样呢？对于顺序表来说，没有数据的标志是 size == 0，对于单向非循环链表来说，没有数据的标志是 phead == NULL，那对于双向循环链表来说，应该是怎样呢？
会是以下的样子吗？
如果真是这样，就没有体现循环的特点了，所以应该是这样：
一、 双向循环链表的尾插
void LTPushBack (LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
1、相比于单向链表的尾插，双向循环链表的尾插不需要判断链表是否为空，不需要找尾，不需要使用二级指针（函数中改变的都是结构体的成员）十分方便。
2、要断言 phead，因为 phead 永远不能为空，phead 为空是错误情况。