系列文章目錄
第一章 時(shí)間復(fù)雜度和空間復(fù)雜度
第二章 順序表，列表
第三章 棧和隊(duì)列
第四章 二叉樹(shù)
第五章 排序
作者：??樂(lè)言??
簡(jiǎn)介：??大一學(xué)生，目前在致力于c/c++/python，高數(shù)的學(xué)習(xí)，有問(wèn)題盡管問(wèn)我，關(guān)注后私聊！
持續(xù)更新專欄：《c進(jìn)階》，《數(shù)據(jù)結(jié)構(gòu)修煉》??（優(yōu)質(zhì)好文持續(xù)更新中）??
文章目錄
目錄
系列文章目錄
文章目錄
前言
線性表
各個(gè)接口的實(shí)現(xiàn)
1.初始化順序表
2.銷毀順序表
3.檢查順序表容量是否滿了
4.順序表尾插
5.順序表尾刪
6.順序表頭插
7.順序表頭刪
8.在順序表中查找定值
9.在順序表指定位置插入數(shù)據(jù)
鏈表
無(wú)頭單向循環(huán)鏈表的實(shí)現(xiàn)
單鏈表定義：
?動(dòng)態(tài)申請(qǐng)一個(gè)節(jié)點(diǎn)
銷毀（釋放）所有節(jié)點(diǎn)
打印單鏈表
單鏈表頭插
單鏈表尾刪
單鏈表頭部刪除
單鏈表在pos位置之后插入
單鏈表中刪除位置為pos的節(jié)點(diǎn)
單鏈表刪除指定pos位置之后的節(jié)點(diǎn)
求單鏈表的長(zhǎng)度：
判斷但倆表是否為空
總結(jié)
前言
在順序表和鏈表的學(xué)習(xí)過(guò)程中，相信大家會(huì)有一些困惑，因?yàn)檫@里用到了大量結(jié)構(gòu)體和數(shù)組的知識(shí)，樂(lè)言在這里將會(huì)對(duì)順序表和單鏈表進(jìn)行深刻的講解，有代碼問(wèn)題，可以后臺(tái)私信作者?。。。。。。?！如果文章有錯(cuò)誤，歡迎指正?。。。。?！
??線性表
#define N 10000
typedef int sldataline;
struct Seqline
{
sldataline a[N];
int size;
};
我們?cè)谶@里可以發(fā)現(xiàn)，靜態(tài)的順序表開(kāi)辟的內(nèi)存是固定的，給多了浪費(fèi)空間，給少了又不夠，還得重新調(diào)整代碼，所以靜態(tài)的順序表十分不好用，在實(shí)際的生活場(chǎng)景中用的也不多。
所以我們通常使用動(dòng)態(tài)的順序表：
typedef int SLDataType;
typedef struct Seqlist
{
SLDataTpye *a;
size_t size;
size_t capacity
}SeqList;
我們要加上容量空間，同時(shí)size為存儲(chǔ)的有效數(shù)據(jù)的個(gè)數(shù)?
如果空間不夠就可以擴(kuò)容
??各個(gè)接口的實(shí)現(xiàn)
1.初始化順序表
要防止傳進(jìn)來(lái)的指針為空，所以一定要提前加上斷言
void SeqListInit(SeqList*psl)
{
assert(psl!=NULL);
psl->size=0;
psl->capacity=0;
}2.銷毀順序表
依然要記得加上斷言，防止傳進(jìn)來(lái)的指針是空指針
void SeqListDestory(SeqList*psl)
{
assert(psl!=NULL);
free(psl->a);
psl->size=0;
psl->capacity=0;
}首先釋放開(kāi)辟的空間，然后將指針置為空，將數(shù)據(jù)和空間容量大小都重置為0
3.檢查順序表容量是否滿了
如果我們一個(gè)個(gè)加入數(shù)據(jù)，這樣重復(fù)操作對(duì)我們來(lái)說(shuō)太過(guò)麻煩，所以我們可以一次性擴(kuò)容兩倍，這樣能應(yīng)付大多數(shù)情況，兩倍是一個(gè)折中的方式
void CheckCapacity(SeqList*psl)
{
assert(psl!=NULL);
if(psl->size == psl->capacity)
{
size_t newcapacity;
if(psl->capacity == 0)
newcapacity = psl->capacity = 4;
else
newcapacity = 2 * psl->capacity;
}
SLDataTpye*p=(SLDataType*)realloc(psl->a,newcapacity*sizeof(SLDataType));//擴(kuò)容
if(p == NULL)
{
perror("realloc");
exit(-1);
}
psl->p;
psl->capacity = newcapacity;
}4.順序表尾插
void SeqListPushBack(Seqlist*psl,SLDataType x)
{
assert(psl !=NULL);
CheckCapacity(psl);
psl->a[psl->size] =x;
psl->size++;
}5.順序表尾刪
void SeqListPopBack(SeqList*psl)
{
assert(psl->NULL);
assert(psl->size >0);
psl->size --;
}因?yàn)槲覀儫o(wú)法得知SLDataType是什么類型，他隨時(shí)都可以改，因此我們不能單純直接將隨意賦值為0（psl->a[psl->size-1]=0)
6.順序表頭插
因?yàn)轫樞虮硎沁B續(xù)存儲(chǔ)的，所以我們?cè)陧樞虮眍^部插入的時(shí)候，我們要依次挪動(dòng)數(shù)據(jù)
void SeqListPushFront(SeqList*psl,SLDType x)
{
assert(psl);
CheckCapacity(psl);
int i = 0;
for(i=psl->size-1;i>=0;i--)
{
psl->a[i+1] = psl->a[i];
}
psl->a[0] = x;
psl->size++;
}7.順序表頭刪
因?yàn)轫樞虮硎沁B續(xù)存儲(chǔ)的，所以要依次挪動(dòng)數(shù)據(jù)
void SeqListPopFront(SeqList* psl)
{
assert(psl);
assert(psl->size >0);
int i =0;
for(i=1;i<psl->size;i++)
{
psl->a[i-1]=psl->a[i];
}
psl->size--;
}依次覆蓋即可，然后再把有效數(shù)據(jù)-1；
8.在順序表中查找定值
int SeqListFind(const SeqList*psl,SLDataType x)
{
assert(psl);
int i = 0;
for(i=0;i<psl->size;i++)
{
if(psl->[i]==x)
{
return i;
}
}
return -1;
}9.在順序表指定位置插入數(shù)據(jù)
void SeqListInsert(SeqList*psl,size_t pos,SLDataType x)
{
assert（psl）；
assert（pos>=0 && pos <=psl->size);
CheckCapacity(psl);
size_t i =0;
for(i=psl->size;i>pos;i--)
{
psl->a[i]=psl->a[i-1];
}
psl->a[pos]=x;
psl->size++;
}??鏈表
順序表我們?cè)谑褂脮r(shí)，雖然下標(biāo)可以隨時(shí)訪問(wèn)，但是會(huì)出現(xiàn)一系列問(wèn)題會(huì)引起我們的思考
1. 中間/頭部的插入刪除，時(shí)間復(fù)雜度為O(N)2. 增容需要申請(qǐng)新空間，拷貝數(shù)據(jù)，釋放舊空間。會(huì)有不小的消耗。3. 增容一般是呈2倍的增長(zhǎng)，勢(shì)必會(huì)有一定的空間浪費(fèi)。例如當(dāng)前容量為100，滿了以后增容? ? ? ?到 200，我們?cè)倮^續(xù)插入了5個(gè)數(shù)據(jù)，后面沒(méi)有數(shù)據(jù)插入了，那么就浪費(fèi)了95個(gè)數(shù)據(jù)空? ? ? ? ? ?間。思考：如何解決以上問(wèn)題呢？下面給出了鏈表的結(jié)構(gòu)來(lái)看看
??無(wú)頭單向循環(huán)鏈表的實(shí)現(xiàn)
第一步我們依然是先新建一個(gè)工程：
- SList.h（單鏈表的類型定義，函數(shù)接口聲明，引用頭文件）
- SList.c（單鏈表各個(gè)接口函數(shù)的實(shí)現(xiàn)）
- test.c（主函數(shù)，測(cè)試函數(shù)的各個(gè)接口功能）?
單鏈表定義：
單鏈表類似如圖結(jié)構(gòu)
一部分儲(chǔ)存結(jié)構(gòu)體的數(shù)據(jù)，另一部分儲(chǔ)存下一塊結(jié)構(gòu)體空間的地址
代碼如下：
typedef int SLDatatype;//定義單鏈表數(shù)據(jù)類型
typedef struct SListNode//定義單鏈表節(jié)點(diǎn)
{
SLDataType data;//數(shù)據(jù)空間
struct SListNode*next；//指針空間
}SListNode;?動(dòng)態(tài)申請(qǐng)一個(gè)節(jié)點(diǎn)
代碼如下：
SListNode* BuySListNode(SLTDataType x)
{
SListNode* node=(SListNode*)malloc(sizeof(SListNode));
if(node == NULL)
{
perror("malloc");
return;
}
}銷毀（釋放）所有節(jié)點(diǎn)
我們?cè)谶@里有一個(gè)遍歷鏈表的操作
{
SListNode* node = (SListNode*)malloc(sizeof(SListNode));
if (node == NULL)
{
perror("malloc");
return;
}
node->data = x;
node->next = NULL;
}
void SListDestory(SListNode** pphead)
{
assert(pphead);
SListNode* cur = *pphead;
while (cur != NULL)
{
SListNode* next = cur->next;
free(cur);
}
*pphead = NULL;
}最后不能忘了置空指針
打印單鏈表
void SListPrint(SListNode* phead)
{
SListNode* ptr = phead;
while (ptr != NULL)
{
printf("%d->", ptr->data);
ptr = ptr->next;
}
printf("NULL\n");
}單鏈表尾插
下面是一個(gè)明顯的錯(cuò)誤
?代碼看似邏輯清晰，其實(shí)問(wèn)題暴露無(wú)遺。此處的指針傳參，相當(dāng)于把plist指針變量的值拷貝給phead給phead賦值newhead，phead的值改變是不會(huì)影響plist
這種寫法會(huì)導(dǎo)致一個(gè)問(wèn)題：? ? ? ? ?
- 當(dāng)鏈表為空時(shí)，我們需要改變plist的指向，讓他指向第一個(gè)節(jié)點(diǎn)，然而初始值plist和phead都指向NULL，調(diào)用函數(shù)后，phead指向了新的節(jié)點(diǎn)，但是plist還是指向NULL
- 問(wèn)題出現(xiàn)，我們又該如何解決？
plist指向的是第一個(gè)節(jié)點(diǎn)的指針，想要在函數(shù)中改變plist的值（指向），必須把plist指針進(jìn)行指針傳參，因?yàn)閜list原本就是一級(jí)指針，我們要想改變他，我們只能取他的地址進(jìn)行傳參
在函數(shù)中，我們想要改變int的值，就要傳遞int*,當(dāng)我們想要傳遞int*的時(shí)候，我們就要傳遞int**......
正確寫法是通過(guò)二級(jí)指針傳參，改變plist的指向
單鏈表為空的時(shí)候，plist直接指向新節(jié)點(diǎn)
單鏈表不為空，會(huì)找到尾部節(jié)點(diǎn)，然后將尾部節(jié)點(diǎn)的next指向新節(jié)點(diǎn)?。?！
//單鏈表尾插
void SListPushBack(SListNode** pphead, SLTDataType x)
{
assert(pphead);
SListNode* newnode = BuyListNode(x);
if (*pphead == NULL)
*pphead = newnode;
else if (**pphead != NULL)
{
SListNode* tail = *phead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}單鏈表頭插
頭插具體實(shí)現(xiàn)算法如圖：
新數(shù)據(jù)的next指向plist指向的節(jié)點(diǎn)
?代碼實(shí)現(xiàn)：
void SListPushFront(SListNode* pphead, SLTDataType x)
{
assert(pphead);
SListNode* newnode = BuySListNode(x);
newnode->next = *pphead;
pphead = *newnode;
}單鏈表尾刪
思想：
1：找到鏈表尾節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)。
2：雙指針，分別找到鏈表尾節(jié)點(diǎn)和它上一個(gè)節(jié)點(diǎn)
如圖所示：
?
- ?當(dāng)單鏈表只有一個(gè)節(jié)點(diǎn)時(shí)，刪除節(jié)點(diǎn)，plist指向NULL
- 而當(dāng)單鏈表有多個(gè)節(jié)點(diǎn)時(shí)，先找到單鏈表尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，刪除，然后將該節(jié)點(diǎn)的next指向NULL
- 可能會(huì)改變plist的指向，所以我們要用二級(jí)指針接受
代碼如下：
void SListPopBack(SListNode** pphead)
{
assert(pphead);
assert(*pphead);
SListNode* tail = *pphead;
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}如果pphead為空，那么直接釋放＋置空
如果pphead不為空，那么直接判斷下一個(gè)節(jié)點(diǎn)是否為空為空則置空，不為空則繼續(xù)判斷
思路2代碼實(shí)現(xiàn)：
void SListPopBack(SListNode** phead)
{
assert(pphead);
assert(*pphead);
SListNode* tail = *pphead;
SListNode* prev = *pphead;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
單鏈表頭部刪除
void SListPopFront(SListNode** pphead)
{
assert(pphead);
assert(**pphead);
SListNode* cur = *pphead;
*pphead = cur->next;
free(cur);
cur = NULL;
}將*pphead移向第二個(gè)節(jié)點(diǎn)即可。
在單鏈表中查找指定點(diǎn)的節(jié)點(diǎn)
SListNode* SListFind(SListNode** pphead, SLDataType x)
{
SListNode* cur = *pphead;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
單鏈表在pos位置之后插入
?我們只需在pos位置的next指向一個(gè)新開(kāi)辟的地址，新地址的next指向原來(lái)的下一個(gè)地址
代碼實(shí)現(xiàn)：
void SListInsertAfter(SListNode* pos, SLDataType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}單鏈表中刪除位置為pos的節(jié)點(diǎn)
考慮到pos位置可能為第一個(gè)節(jié)點(diǎn)，所以我們有必要選擇進(jìn)行語(yǔ)句
代碼如下：
void SListDel(SListNode** pphead,SListNode* pos)
{
assert(pphead);
assert(*pphead);
assert(pos);
if (pos == *pphead)
{
SListPopFront(pphead);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
prev = prev->next;
}
prev->next = pos->prev;
free(pos);
pos = NULL;
}單鏈表刪除指定pos位置之后的節(jié)點(diǎn)
圖示：
代碼實(shí)現(xiàn)：?
此處我們要定義一個(gè)新的指針，來(lái)存放pos的下一個(gè)節(jié)點(diǎn)的地址
void SListDelAfter(SListNode* pos)
{
assert(pos);
assert(pos->next);
SListNode* posnext = pos->next;
pos->next = pos->next->next;
free(posnext);
}求單鏈表的長(zhǎng)度：
遍歷尋找是否為空即可文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-432322.html
int SListSize(SListNode* phead)
{
int size = 0;
SListNode* cur = phead;
while (cur != NULL)
{
size++;
cur = cur->next;
}
return size;
}判斷但倆表是否為空
bool SListEmpty(SListNode* phead)
{
return phead == NULL;
}??總結(jié)
本文具體寫了順序表和單鏈表增刪查改的一系列操作，希望各位同志們也要?jiǎng)邮植僮饕幌?，這樣才能融會(huì)貫通，熟稔于心文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-432322.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)修煉第二篇：順序表和鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[ 數(shù)據(jù)結(jié)構(gòu) -- 手撕排序算法第二篇 ] 冒泡排序](https://imgs.yssmx.com/Uploads/2024/02/501879-1.png)
