1. 顺序表
1.1 顺序表的概念及其结构
** 基本概念:**
顺序表是用一段**物理地址连续的存储单元**依次存储数据元素的线性结构，一般情况下采 用数组存储,在数组中完成增删查改。如图1,它有如下特点:
存储空间连续,既允许元素的顺序访问,又可以随机访问。
要访问指定元素,可以使用索引(下标)来访问,时间复杂度为O(1);
要在其中增加或者删除一个元素,都要涉及后面所有元素的向前或向后移动，时间复杂度为O(n);
可以方便的存储表中的任一结点，存储速度快;
长度固定，分配内存之前必须知道数组的长度;
无需为表示结点间的逻辑关系而增加额外的存储空间，存储利用率提高；
存储结构:
顺序表一般可以分为:
1.静态顺序表:使用定长数组存储;
2.动态顺序表:使用动态开辟的数组存储;
静态分配和动态分配有什么不同呢？其实也就是数组的不同。在静态分配时，我们在编写的时候，就已经确定了数组的大小。而动态分配时，没有确定它的大小，是根据动态分配语句在运行时才将它的大小进行分配。这样有一点的好处就是，在静态分配时，当我想要存放顺序表的数据元素过超过 100的时候则会产生错误溢出，而动态分配时，如果一旦超过了分配的空间大小，可以再重新分配一块内存空间，把旧的空间和所增加的数据元素转移到新申请的空间上，这样就不会产生溢出的问题了。这是动态分配的一个优点。
代码如下:
//顺序表的静态存储
#define N 8
typedef int SLDataType;
typedef struct SeqList
{
SLDataType array[N];//定长数组
size_t size;//有效数组的个数
}SeqList;
//顺序表的动态存储
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* array;//指向动态开辟的数组
size_t size;//有效数据的个数
size_t capacity;//空间容量的大小
}SeqList;
/*注解:我们发现这里用的是指针,指针是存放一个存储单元地址的.顺序表根据第一个数据元素的地址和数据元素的大小,就可以算出任意数据元素的位置.即只定义第一个元素的指针即可，描述整个顺序表。但它仅仅是个地址，没有确切的空间，因此我们使用是要开辟空间;
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType));
详细代码下面讲解;*/
静态顺序表的定长数组导致N定大,空间开少了不够用,开多了浪费,所以现实中都是使用动态顺序表,使用倍增-复制的办法来支持动态扩容，将顺序表变成“可变长度”的。下面我将实现动态顺序表;
1.2 顺序表的插入(头插,尾插,插入指定位置）
1)**头插法:**每一次在顺序表的最前方插入,其他数据后移
void SeqListPushFront(SL* ps, SLDataType x)
{
//如果没有空间，或者空间不足，我们可以增容
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//对数组进行二倍增容,使用三目运算符是为了防止0这种情况
SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
//判断是否增容成功
if(tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
//从最后一个元素开始向前遍历到第一个元素，分别将它们向后移动一个位置
for (int i = ps->size - 1; i >= 0; i--)
{
ps->a[i + 1] = ps->a[i];
}
ps->a[0] = x;//将要插入的数据插入到头部
ps->size++;//表长加1
}
2)尾插法:顺序表的末尾增加数据,其他元素不用改变
void SeqListPushBack(SL* ps, SLDataType x)
{
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
printf("realloc fail");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->size] = x;
ps->size++;
}
3)指定位置插入:从最后一个元素开始向前遍历到第指定位置，分别将它们向后移动一个位置
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
//因为顺序表连续存储,所以首先要判断插入位置是否合法;
assert(pos >= 0 && pos <= ps->size);
//增容
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
//从最后一个元素开始向前遍历到第指定位置，分别将它们向后移动一个位置
for (int i = ps->size - 1; i >= pos; i--)
{
ps->a[i + 1] = ps->a[i];
}
//将x插入到指定位置
ps->a[pos] = x;
//表长加1
ps->size++;
}
1.3 顺序表的删除(头删,尾删,删除指定位置)
1)头删:从删除位置遍历到最后一个元素的位置,将他们依次向前移一个位置;
void SeqListPopFront(SL* ps)
{
//判断顺序表当前长度是否为0
assert(ps->size > 0);
//从删除位置开始遍历到最后一个元素位置，将他们分别前移一个位置。
for (int i = 1; i < ps->size; i++)
{
ps->a[i - 1] = ps->a[i];
}
//表长减一
ps->size--;
}
2)尾删:将表长减去1即可;
void SeqListPopBack(SL* ps)
{
assert(ps->size > 0);
ps->size--;
}
3)删除指定位置:首先判断指定位置是否合法然后从指定位置的下一个元素依次向前移动一步.
void SeqListErase(SL* ps, int pos)
{
assert(pos >= 0 && pos < ps->size);
for (int i = pos + 1; i < ps->size; i++)
{
ps->a[i - 1] = ps->a[i];
}
ps->size--;
}
1.4 顺序表的查找
**查找:**顺序表的一端开始，依次将每个元素的关键字同给定值 K 进行比较，直到相等或比较完毕还未找到.
int SeqListFind(SL* ps, SLDataType x)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}
1.5 顺序表的接口实现(供大家考察是否掌握）
大家可以参考其提供的接口进行练习考查是否已经掌握.
// 顺序表的动态存储
typedef struct SeqList
{
SLDataType* array; // 指向动态开辟的数组
size_t size ; // 有效数据个数
size_t capicity ; // 容量空间的大小
}SeqList;
// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl, size_t capacity);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(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);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
2. 链表
2.1 链表的概念及其结构
**基本概念**:
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。这里以单链表为例，说明其特征,如图1
- 存储空间不连续，数据元素之间使用指针相连,每个数据元素只能访问周围的一个元素;
- 长度不固定,可以任意增删;
- 要访问指定元素,要从头开始遍历元素,直到找到那个元素位置,时间复杂度为**O(N)**；
- 在指定的数据元素插入或删除，不需要移动其他元素,时间复杂度为O(1);
** 链表结构: **
链表的结构非常多样,以下情况组合起来一共有8中链表结构:
- 单向、双向 2. 带头、不带头 3. 循环、非循环
（注释:
单向:只包含指向下一个结点的指针，只能单向遍历;
双向:包含指向下一个结点的指针也包含指向前一个结点的指针,因此可以双向遍历;
**带头:1.****头结点是为了操作的统一和方便而设立的，放在链表第一个元素之前，其数据域大多无意义，但也可以用来保存链表长度。2.****有了头结点，对链表头部的插入和删除操作就统一了。3.**头结点不是链表的必要元素。
循环:将尾节点与首节点链接起来，形成了一个环状结构，在某些情况下会非常有用)
虽然有这么多链表的结构,但我们在实际运用中最常见到的还是两种结构:
这里由于篇幅原因,只讲解第一个无头单向非循环链表.
2.2 单链表的插入(头插,尾插,指定位置插入）
1）**尾插(无头结点):**1.创建新结点2.判断链表是否为空3.为空则让头指针指向新结点4.否则找到最后一个指针,指向新结点;
SLTNode* BuyListNode(SLTDateType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SListPushBack(SLTNode** pphead, SLTDateType 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;
}
}
2)**头插(无头结点):1.**创建新结点 2.新结点指向原链表 3.头指针指向新结点;(注:2,3顺序不能颠倒,否则新结点将找不到原链表的地址)
SLTNode* BuyListNode(SLTDateType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SListPushFront(SLTNode** pphead, SLTDateType x)
{
SLTNode* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
3)在pos位置之前插入结点:1.创建新结点;2.判断第一个是否是其指定的位置3.如果是再来个头插,否则,找到pos的前一个位置posPrev;4将其新结点插入到pos位置之前，posPrev之后;
SLTNode* BuyListNode(SLTDateType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
// 在pos位置之前去插入一个节点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pphead);
assert(pos);
SLTNode* newnode = BuyListNode(x);//创建新结点
//判断第一个是否等于pos
if (*pphead == pos)
{
newnode->next = *pphead;
*pphead = newnode;
}
else {
//找到pos的前一个位置
SLTNode* posprev = *pphead;
while (posprev->next != pos)
{
posprev = posprev->next;
}
posprev->next = newnode;
newnode->next = pos;
}
}
4)在pos位置之后插入结点:1.创建新结点; 2.新结点的next指向pos的next；3.pos的next指向newnode;(注:2,3不能交换位置,否则将丢失pos之后的地址）
SLTNode* BuyListNode(SLTDateType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SListInsertAfter(SLTNode* pos, SLTDateType x)
{
assert(pos);
SLTNode* newnode = BuyListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
2.3 单链表的删除(头删,尾删,指定位置删除)
1)**尾删:**1.判断链表是否为空,为空则则停止删除;2.若只有一个结点,释放其结点,让其链表为空;3.若有两个或两个以上的结点,找到最后一个和其前驱;4.其前驱next为空,释放最后一个结点;
void SListPopBack(SLTNode** pphead)
{
assert(*pphead != NULL);
//1.一个的情况
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//2.两个或者两个以上
else {
SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
2)头删: 1.判断链表是否为空;2.头指针指向第一个结点的next;3.释放第一个结点;
void SListPopFront(SLTNode** pphead)
{
assert(*pphead != NULL);//判断连表是否为空·
SLTNode* cur = (*pphead)->next;
free(*pphead);
*pphead = NULL;
*pphead = cur;
}
3)指定位置删除:1.判断链表是否为空;2.如果pos等于第一个结点,则采用头删;3.找出pos的前一个prev 4.将prev的next指向pos的next;5.释放pos;
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
SListPopFront(pphead);//头删,详见上面代码
}
else {
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
2.4 单链表的查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
SLTNode* cur = phead;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
else {
cur = cur->next;
}
}
return NULL;
}
2.5 单链表的接口实现(供大家考察是否掌握)
// 1、无头+单向+非循环链表增删查改实现
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
3. 顺序表与链表的优缺点
3.1 存取方式
顺序表:可以顺序存取,也可以随机存取;
单链表:只能从表头顺序进行存取元素;
3.2 逻辑结构与物理结构
顺序表:逻辑上相邻的元素,对应的物理存储位置也相邻；
单链表:逻辑上相邻的元素，物理存储位置不一定相邻，其逻辑关系是通过指针链接来表示的;
3.3 时间性能
顺序表支持随机访问,时间复杂度为O(1);
顺序表插入和删除需要依次移动元素，时间复杂度为O(N);
单链表要访问指定元素,需要从头遍历,时间复杂度为O(N);
单链表的插入和删除不需要移动元素,时间复杂度为O(1)；
3.4 空间性能
顺序表:需要预先分配存储空间，分配过多就会造成存储空间的浪费，而分配过少则会发生上溢。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大的连续存储空间，则会导致分配失败。
单链表:按需分配，且元素个数不受限制
以上是顺序表与链表的相关知识点，有不足的地方或者对代码有更好的见解，欢迎评论区留言共同商讨，共同进步！！
版权归原作者 skeet follower 所有， 如有侵权，请联系我们删除。