思維導(dǎo)圖：
?
順序表與鏈表都是兩種線性表，但是兩者之間又有著許多的不同。順序表是一種連續(xù)的空間，實(shí)際上就是數(shù)組。鏈表是不連續(xù)的空間，鏈表的空間是一塊一塊的開(kāi)辟出來(lái)的。
兩者的優(yōu)點(diǎn)與缺點(diǎn)：
順序表：
優(yōu)點(diǎn)：1.順序表的空間是連續(xù)的，所以能夠支持下標(biāo)的隨機(jī)訪問(wèn)。
缺點(diǎn)：2.順序表的空間是連續(xù)的容易造成空間的浪費(fèi)。
鏈表：
優(yōu)點(diǎn)：1.空間不連續(xù)，要用時(shí)才申請(qǐng)所以不會(huì)造成空間的浪費(fèi)。
缺點(diǎn)：2.空間不連續(xù)不能支持下標(biāo)的隨機(jī)訪問(wèn)。
一，順序表的操作
1.順序表的結(jié)構(gòu)
順序表的本質(zhì)是數(shù)組，所以要定義一個(gè)有數(shù)組的結(jié)構(gòu)體。并且，這個(gè)順序表是動(dòng)態(tài)的。所以我們又需要一個(gè)表示順序表內(nèi)元素個(gè)數(shù)的變量size和一個(gè)表示順序表容量的變量capacity。結(jié)構(gòu)體定義如下：
?代碼：
typedef int dataType;
typedef struct List
{
dataType* a;//數(shù)組
int size;//個(gè)數(shù)
int capacity;//容量
}List;2.順序表的初始化
?順序表的初始化是一個(gè)必要的操作，數(shù)組指針先初始化為NULL，size初始化為0，capacity初始化為0.代碼如下：
void ListInit(List* list)
{
assert(list);//防止傳入NULL
list->a = NULL;
list->size = 0;
list->capacity = 0;
}?3.順序表的前插操作
順序表的插入操作都要先判斷順序表內(nèi)的空間是否夠用，所以在插入數(shù)據(jù)到順序表之前得先對(duì)順序表的容量是否已滿進(jìn)行判斷。先寫(xiě)一個(gè)判斷容量的函數(shù)，代碼如下：
代碼：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-526295.html
void checkCapacity(List* list)
{
assert(list);
if (list->size == list->capacity)
{
int newcapacity = list->capacity==0 ? 4: 2 * list->capacity;
dataType* tmp = (dataType*)realloc(list->a, sizeof(dataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail!");
return;
}
list->a = tmp;
list->capacity = newcapacity;
}
}?然后便是對(duì)順序表的頭插操作，頭插操作插入的位置都是數(shù)組下標(biāo)為0的位置。為了實(shí)現(xiàn)這一操作，我們就必須在數(shù)組不為空的條件下對(duì)數(shù)據(jù)進(jìn)行后移然后將下標(biāo)為0的位置騰出來(lái)。代碼如下：
代碼：
void LishPushFront(List* list, dataType x)
{
assert(list);
checkCapacity(list);//判斷容量是否已滿
if (list->size == 0)//當(dāng)數(shù)組為空時(shí)直接插入
{
list->a[0] = x;
}
else//數(shù)組不為空時(shí)要將原有數(shù)據(jù)后移將下標(biāo)為0的位置騰出
{
int end = list->size - 1;
for (int i = end;i >= 0;i--)
{
list->a[i + 1] = list->a[i];
}
list->a[0] = x;
}
list->size++;//插入后數(shù)組元素個(gè)數(shù)增加
}4，順序表的尾插操作
順序表的尾插操作也是一個(gè)插入操作，所以尾插操作的第一步便是對(duì)數(shù)組的容量進(jìn)行檢查。然后才是數(shù)據(jù)的尾插操作。尾插不需要數(shù)據(jù)的移動(dòng)，只需要在size的位置上插入數(shù)據(jù)即可。
代碼如下：
代碼：
void ListPushBack(List* list, dataType x)
{
assert(list);
checkCapacity(list);
list->a[list->size] = x;
list->size++;
}5.順序表的頭刪
順序表的頭刪操作是一個(gè)移動(dòng)數(shù)據(jù)覆蓋然后將size減1的過(guò)程。說(shuō)是刪除數(shù)據(jù)其實(shí)就是覆蓋掉數(shù)組下標(biāo)為0的位置的數(shù)據(jù)。注意要對(duì)數(shù)組是否為空進(jìn)行判斷，當(dāng)數(shù)組為空時(shí)不能夠?qū)@個(gè)順序表進(jìn)行刪除??！代碼如下：
代碼：
void ListPopFront(List* list)
{
assert(list);
assert(list->size > 0);//對(duì)順序表是否為空進(jìn)行判斷
for (int i = 1;i < list->size;i++)
{
list->a[i - 1] = list->a[i];
}
list->size--;
}?6.順序表的尾刪
順序表的尾刪操作比起順序表的頭刪操作就顯得更加簡(jiǎn)單。順序表的尾刪操作不需要覆蓋只需要讓數(shù)組的最后一個(gè)數(shù)據(jù)訪問(wèn)不到便可，也就是將size減1。注意要對(duì)數(shù)組是否為空進(jìn)行判斷，當(dāng)數(shù)組為空時(shí)不能夠?qū)@個(gè)順序表進(jìn)行刪除操作！！代碼如下：
代碼：
void ListPopBack(List* list)
{
assert(list);
assert(list->size > 0);
list->size--;
}?7.順序表的中間插入
順序表的中間插入操作實(shí)現(xiàn)的功能就是將要插入的數(shù)據(jù)插入到要插入的下標(biāo)pos位置處。中間插入的操作能夠被頭插1和尾插復(fù)用進(jìn)而實(shí)現(xiàn)頭插與尾插。中間插入操作代碼如下：
代碼：
void ListInsert(List* list, int pos, dataType x)
{
assert(list);
assert(0 <= pos && pos <= list->size);//對(duì)pos的值進(jìn)行判斷以免造成越界
checkCapacity(list);
for (int i = list->size;i >= pos;i--)
{
list->a[i] = list->a[i - 1];
}
list->a[pos] = x;
list->size++;
}?8.順序表的中間刪除操作
順序表的中間刪除操作就是將下標(biāo)為pos的位置上的數(shù)據(jù)刪除的操作。也能被其他兩個(gè)刪除操作進(jìn)行復(fù)用從而實(shí)現(xiàn)頭刪和尾刪。和前兩個(gè)操作一樣中間刪除的操作的刪除就是覆蓋下標(biāo)pos位置上的1數(shù)據(jù)或者讓pos數(shù)據(jù)上的數(shù)據(jù)不可訪問(wèn)。中間刪除操作代碼如下:
代碼：
void ListErase(List* list, int pos)
{
assert(list);
assert(list->size>0);
assert(0 <= pos && pos < list->size);
for (int i = pos;i < list->size-1;i++)
{
list->a[i] = list->a[i + 1];
}
list->size--;
}9.順序表內(nèi)數(shù)據(jù)的尋找
在順序表內(nèi)尋找某個(gè)數(shù)據(jù)其實(shí)并不難，不過(guò)就是遍歷順序表內(nèi)的數(shù)組然后看看有沒(méi)有匹配的數(shù)據(jù)。如果有便返回?cái)?shù)據(jù)的下標(biāo)，沒(méi)有便返回不存在的下標(biāo)-1。代碼如下：
?代碼：
int ListFind(List* list, dataType x)
{
assert(list);
for (int i = 0;i < list->size;i++)
{
if (list->a[i] == x)
return i;
}
return -1;
}10，順序表數(shù)據(jù)的修改
?順序表內(nèi)數(shù)據(jù)的修改這一操作是和上一個(gè)查找操作配合著使用的。只有要查找的元素存在才能替換。否則便不能。代碼如下：
代碼：
void ListModify(List* list,int i,dataType x)
{
assert(list);
if (i == -1)//i這個(gè)值是通過(guò)ListFind函數(shù)找到的下標(biāo)
{
printf("要修改的值不存在！\n");
return;
}
else
{
list->a[i] = x;
}
}11.順序表的銷毀
太簡(jiǎn)單了，直接上代碼：
代碼：
void ListDestory(List* list)
{
assert(list);
free(list->a);
list->a = NULL;
list->size = list->capacity = 0;
}二，鏈表的創(chuàng)建與操作
1.鏈表的創(chuàng)建
鏈表是一種不連續(xù)的空間，但是又要將一個(gè)一個(gè)的節(jié)點(diǎn)聯(lián)系起來(lái)并且鏈表里還要放置一些數(shù)據(jù)。所以鏈表的結(jié)構(gòu)里就要有兩個(gè)變量，一個(gè)是存下一個(gè)鏈表節(jié)點(diǎn)的指針，一個(gè)是存當(dāng)前節(jié)點(diǎn)內(nèi)數(shù)據(jù)的變量。鏈表節(jié)點(diǎn)的結(jié)構(gòu)代碼如下：
代碼：
typedef int dataType;
typedef struct listNode
{
dataType val;//存放當(dāng)前節(jié)點(diǎn)內(nèi)的數(shù)據(jù)
struct listNode* next;//存放下一個(gè)節(jié)點(diǎn)的地址
}listNode;
?2.鏈表的頭插操作
鏈表的頭插操作在執(zhí)行時(shí)要分兩種情況。第一種情況是鏈表為NULL時(shí)，你需要讓鏈表的頭節(jié)點(diǎn)頭節(jié)點(diǎn)指向newnode。當(dāng)鏈表不為NULL時(shí)，newnode指向的next就是原來(lái)的頭節(jié)點(diǎn)，然后讓頭節(jié)點(diǎn)指向新的頭節(jié)點(diǎn)。代碼如下：
代碼：
void SlistPushFront(SListNode** pphead, dataType x)
{
assert(pphead);
assert(pphead);//防止傳入空指針
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("malloc fail\n");
return;
}
newnode->val = x;
newnode->next = NULL;
//當(dāng)鏈表為NULL
if (*pphead == NULL)
{
*pphead = newnode;
}
//當(dāng)鏈表不為NULL時(shí)
else
{
newnode->next = *pphead;
*pphead = newnode;
}
}?3.鏈表的尾插操作
鏈表的尾插操作其實(shí)與頭插操作差不多。最主要的是當(dāng)鏈表不是NULL時(shí)需要去找到尾節(jié)點(diǎn)，然后讓尾節(jié)點(diǎn)的next指向newnode。代碼如下：
代碼：
void SlistPushBack(SListNode** pphead, dataType x)
{
assert(pphead);//防止傳入空指針
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("malloc fail\n");
return;
}
newnode->val = x;
newnode->next = NULL;
//當(dāng)鏈表為NULL
if (*pphead == NULL)
{
*pphead = newnode;
}
//找尾插入值
else
{
SListNode* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}以上兩個(gè)代碼能復(fù)用的地方：生成節(jié)點(diǎn)的地方
代碼：
SListNode* BuyNode(dataType x)
{
SListNode* node = (SListNode*)malloc(sizeof(SListNode));
if (node == NULL)
{
perror("malloc fail\n");
return;
}
node->val = x;
node->next = NULL;
return node;
}改進(jìn)后的代碼：
頭插：
void SlistPushFront(SListNode** pphead, dataType x)
{
assert(pphead);
assert(pphead);//防止傳入空指針
SListNode* newnode = BuyNode(x);
if (newnode == NULL)
{
perror("malloc fail\n");
return;
}
newnode->val = x;
newnode->next = NULL;
//當(dāng)鏈表為NULL
if (*pphead == NULL)
{
*pphead = newnode;
}
//當(dāng)鏈表不為NULL時(shí)
else
{
newnode->next = *pphead;
*pphead = newnode;
}
}尾插：
void SlistPushBack(SListNode** pphead, dataType x)
{
assert(pphead);//防止傳入空指針
SListNode* newnode = BuyNode(x);
if (newnode == NULL)
{
perror("malloc fail\n");
return;
}
newnode->val = x;
newnode->next = NULL;
//當(dāng)鏈表為NULL
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SListNode* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}四，鏈表的頭刪操作
鏈表的頭刪操作也是一個(gè)簡(jiǎn)單的操作，這個(gè)操作就是將頭節(jié)點(diǎn)給銷毀掉然后再讓頭指針指向第二個(gè)節(jié)點(diǎn)。這也要分兩種情況來(lái)刪除，第一種情況是鏈表為NULL不能刪，第二種情況便是當(dāng)鏈表內(nèi)只有一個(gè)頭節(jié)點(diǎn)時(shí)直接刪除這個(gè)節(jié)點(diǎn)然后置空便可以了。第三種情況是當(dāng)鏈表內(nèi)有多個(gè)節(jié)點(diǎn)時(shí)需要將第二個(gè)節(jié)點(diǎn)的地址保存下來(lái)然后再將頭節(jié)點(diǎn)刪掉并置空。代碼如下：
代碼：
void SListPopFront(SListNode** pphead)
{
assert(pphead);
//當(dāng)鏈表為空時(shí)不能夠繼續(xù)刪除
assert(*pphead);
//只有一個(gè)節(jié)點(diǎn)時(shí)
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//有兩個(gè)節(jié)點(diǎn)時(shí)
else
{
SListNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
}五，鏈表的尾刪
鏈表的尾刪操作就是一個(gè)將鏈表的尾節(jié)點(diǎn)刪除的操作。這個(gè)操作也得分三種情況：
1.鏈表為NULL不刪? ?2.鏈表內(nèi)只有一個(gè)節(jié)點(diǎn)，直接刪除第一個(gè)節(jié)點(diǎn)? 3.鏈表內(nèi)有多個(gè)節(jié)點(diǎn)，找到最后一個(gè)節(jié)點(diǎn)刪除置空。代碼如下：
?代碼：
void SListPopBack(SListNode** pphead)
{
assert(pphead);
assert(*pphead);
//只有一個(gè)節(jié)點(diǎn)
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SListNode* tail = *pphead;
SListNode* prev = NULL;//記錄尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
while (tail->next)//找尾節(jié)點(diǎn)
{
prev = tail;
tail = tail->next;
}
free(tail);//去尾
tail = NULL;//將尾節(jié)點(diǎn)置空
prev->next = NULL;//尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的next指向NULL,消除野指針問(wèn)題
}
}六，鏈表的中間插入
鏈表的中間插入操作講的是在鏈表的某個(gè)數(shù)據(jù)的位置處插入一個(gè)操作者想要插入的值。這個(gè)操作的關(guān)鍵點(diǎn)就在于找到要插入位置的前一個(gè)位置然后將這個(gè)位置的nex指向給改掉，改成指向我們想要插入的值。代碼如下：
代碼：
void SListInsert(SListNode** pphead,dataType target ,dataType x)
{
assert(pphead);
SListNode* cur = *pphead;//表示當(dāng)前節(jié)點(diǎn)
SListNode* prev = NULL;//表示當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
while (cur)
{
SListNode* newnode = BuyNode(x);
if (cur->val == target)
{
if (prev == NULL)//當(dāng)?shù)谝粋€(gè)節(jié)點(diǎn)就是目標(biāo)值所在節(jié)點(diǎn)時(shí)
{
newnode->next = *pphead;
*pphead = newnode;
}
else//當(dāng)其他節(jié)點(diǎn)才是目標(biāo)值所在節(jié)點(diǎn)時(shí)
{
prev->next = newnode;
newnode->next = cur;
}
return ;
}
prev = cur;
cur = cur->next;
}
//當(dāng)鏈表循環(huán)完以后鏈表內(nèi)便沒(méi)有數(shù)據(jù)為目標(biāo)值的節(jié)點(diǎn)
printf("鏈表內(nèi)沒(méi)有要找的目標(biāo)值\n");
return ;
}七，鏈表的中間刪除
鏈表的中間刪除操作的作用是將目標(biāo)值所在節(jié)點(diǎn)刪除，釋放掉。這個(gè)操作的代碼和中間插入的代碼有異曲同工之妙，都要找到要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)然后再執(zhí)行下列的操作。也有兩種情況要討論——1，當(dāng)?shù)谝粋€(gè)節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)? ?2，當(dāng)其它節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)。
void SListErase(SListNode** pphead, dataType target)
{
assert(pphead);
assert(*pphead);
SListNode* cur = *pphead;
SListNode* prev = NULL;
while (cur)
{
SListNode* next = cur->next;
if (cur->val == target)
{
if (prev == NULL)
{
free(cur);
cur = next;
}
else
{
free(cur);
prev->next = next;
}
return ;
}
prev = cur;
cur = cur->next;
}
printf("鏈表內(nèi)沒(méi)有要?jiǎng)h除的目標(biāo)節(jié)點(diǎn)\n");
return;
}當(dāng)然，中間刪除與插入的代碼的寫(xiě)法不止這一種，我們還可以通過(guò)尋找某個(gè)值所在的節(jié)點(diǎn)來(lái)對(duì)鏈表進(jìn)行中間插入與刪除。這里讀者可以自己思考一下該如何寫(xiě)代碼。?如果要寫(xiě)這樣一個(gè)代碼的話還需要寫(xiě)一個(gè)find函數(shù)來(lái)找到這個(gè)節(jié)點(diǎn)然后利用這個(gè)函數(shù)來(lái)與中間插入，中間刪除函數(shù)配合著使用。
八，鏈表的銷毀
?這個(gè)代碼比較簡(jiǎn)單，但是一定要記得在刪除掉當(dāng)前節(jié)點(diǎn)的時(shí)候要記錄一下之后的節(jié)點(diǎn)。代碼如下：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-526295.html
代碼：
void SListDestory(SListNode** pphead)
{
SListNode* cur = *pphead;
while (cur)//一個(gè)一個(gè)節(jié)點(diǎn)銷毀
{
SListNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;//最后將外面的list置空
}到了這里，關(guān)于順序表與鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
