文章目录
1.线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。
线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
2.顺序表
2.1概念及结构
顺序表是用一段 物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表可以分为两种结构：
1.静态顺序表：使用定长数组存储数据。
2. 动态顺序表：使用动态开辟的数组存储。
2.2接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
顺序表初始化：
void SeqListInit(SL* ps)
{
ps->a = NULL;
ps->size = ps->capacity = 0;
}
顺序表的打印
void SeqListPrint(SL* ps)
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
顺序表的销毁
void SeqListDestory(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
顺序表尾插
因为在初始化的时候并没有分配空间给顺序表，所以在尾插的时候，要考虑空间不够的问题，空间不够就需要扩容 。
所以我们封装一个检查是否需要增加顺序表容量的CheckCapacity函数。
void SeqListPushBack(SL* ps, SLDateType x)
{
CheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
顺序表容量检查
void CheckCapacity(SL* ps)
{
//空间不够需要增容
if (ps->capacity == ps->size)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * newcapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}
顺序表头插
顺序表头插和顺序表尾插一样都需要在插入数据前检查顺序表的容量是否合法。头插和尾插不一样的是：要在顺序表的头插入数据，需要把下标为1后面的数据都往后挪一位，这就导致顺序表头插的时间复杂度为O(N)。
void SeqListPushFront(SL* ps, SLDateType x)
{
CheckCapacity(ps);
//往后挪数据
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}
顺序表尾删
顺序表尾删比较简单，只需要把ps->size减一，顺序表就访问不到最后的那个数据了，不过需要注意的是：ps->size的值必须要大于等于零，不然就会造成内存的非法访问。
所以可以在尾删的开头加上一句断言，如果ps->size的值小于零，程序就会直接报错。
void SeqListPopBack(SL* ps)
{
assert(ps->size > 0);
ps->size--;
}
顺序表头删
顺序表头删和顺序表头插一样，需要挪动数据。
顺序表头删的时间复杂度是O(N)。
void SeqListPopFront(SL* ps)
{
assert(ps->size > 0);
//往前挪数据
int begin = 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
begin++;
}
ps->size--;
}
顺序表查找
int SeqListFind(SL* ps, SLDateType x)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}
顺序表插入
顺序表在查找之前，需要做两件事：
1、检查顺序表的容量。
2、把pos到ps->size之间的数据向后移一位，再把X填入pos位置。
由于需要移动数据，顺序表插入的时间复杂度为O(N)。
void SeqListInsert(SL* ps, int pos, SLDateType x)
{
assert(pos >= 0 && pos <= ps->size);
CheckCapacity(ps);
int end = ps->size - 1;
while (end >= pos)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size++;
}
顺序表删除
顺序表的删除时，就是将pos位置的后一位到ps->size向前覆盖一位。
由于需要移动数据，顺序表插入的时间复杂度为O(N)。
2.3顺序表的问题
问题：
- 中间/头部的插入删除，时间复杂度为O(N)。
- 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
3.链表
3.1链表的概念和结构
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
l所以说，链表是一种逻辑上连续，物理上不一定连续 的结构。
抽象中的链表：
现实中的链表：
注意：
- 链式结构在逻辑上是连续的，但是在物理上不一定连续。
- 链式结构的结点一般是在堆区上申请的内存空间。
- 在堆区上申请的空间，是按照一定的策略分配的，两次申请的空间可能是连续的，也可能是不连续的。
3.2链表的类型
链表的结构很多样，通过排列组合一共有8种。
1.单向和双向
2.带头和不带头
3.循环和非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
1.无头非循环单链表
特点：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
2.带头双向循环链表
特点：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单。
3.3链表的实现
3.3.1无头非循环单链表的接口实现
单链表打印
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
单链表创建新结点
SLTNode* BuyListNode(SLTDataType x)
{
SLTNode* tmp = (SLTNode*)malloc(sizeof(SLTNode));
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
tmp->data = x;
tmp->next = NULL;
return tmp;
}
单链表头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
单链表头删
单链表头删需要next来保存第一个的下一个结点，然后free第一个结点，让next成为单链表新的第一个结点。
void SListPopFront(SLTNode** pphead)
{
assert(pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
单链表尾插
单链表尾插是要注意该链表是否为空：
1.单链表为空：将新结点作为单链表的第一个结点。
2.单链表不为空：先找到单链表的尾，然后将新结点链接到尾上。
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuyListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
单链表尾删
单链表尾删要注意链表是否只有一个结点：
1.只有一个结点：直接将单链表的第一个结点free。
2.两个及以上结点：用tail保存单链表的尾，并用prev保存单链表的尾的前一个结点，将tail结点free，然后将prev指向NULL。
void SListPopBack(SLTNode** pphead)
{
assert(pphead);
//只有一个结点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//两个及以上个结点
else
{
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
单链表查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
assert(phead);
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}
单链表pos之后插入数据
将newnode的next指向pos的下一个，再将pos的next指向newnode。
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuyListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
单链表pos之后删除数据
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* next = pos->next;
pos->next = next->next;
free(pos->next);
}
单链表销毁
void SListDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
}
3.3.2带头双向循环链表的接口实现
创建返回链表的头结点
ListNode* ListCreate()
{
ListNode* pHead = (ListNode*)malloc(sizeof(ListNode));
if (pHead == NULL)
{
printf("malloc fail\n");
exit(-1);
}
pHead->next = pHead;
pHead->prev = pHead;
return pHead;
}
双向链表打印
void ListPrint(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->next;
while (cur != pHead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = BuyListNode(x);
ListNode* tail = pHead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = pHead;
pHead->prev = newnode;
}
双向链表尾删
void ListPopBack(ListNode* pHead)
{
assert(pHead);
assert(pHead->next != pHead);
ListNode* tail = pHead->prev;
ListNode* tailPrev = tail->prev;
free(tail);
tailPrev->next = pHead;
pHead->prev = tailPrev;
}
双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = BuyListNode(x);
ListNode* next = pHead->next;
newnode->next = next;
next->prev = newnode;
pHead->next = newnode;
newnode->prev = pHead;
}
双向链表头删
void ListPopFront(ListNode* pHead)
{
assert(pHead);
assert(pHead->next != pHead);
ListNode* next = pHead->next;
ListNode* nextNext = next->next;
free(next);
pHead->next = nextNext;
nextNext->prev = pHead;
}
双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* cur = pHead->next;
while (cur != pHead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* newnode = BuyListNode(x);
ListNode* posPrev = pos->prev;
posPrev->next = newnode;
newnode->prev = posPrev;
newnode->next = pos;
pos->prev = newnode;
}
双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* posPrev = pos->prev;
ListNode* posNext = pos->next;
free(pos);
posPrev->next = posNext;
posNext->prev = posPrev;
}
4.顺序表和链表的区别
| 不同点 | 顺序表 | 链表 |
|---|---|---|
| 存储空间上 | 物理上连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持O(1) | 不支持随机存储O(N) |
| 任意位置插入删除 | 需要移动元素O(N) | 只需要修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入删除频繁 |
| 缓存利用率 | 高 | 低 |