文章內(nèi)容

1. 鏈表的概念及結(jié)構(gòu)

2. 鏈表的分類

3.鏈表實現(xiàn)

4.代碼

---

文章目錄

1. 鏈表的概念及結(jié)構(gòu)

概念：鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表
中的指針鏈接次序?qū)崿F(xiàn)的 。

?

?現(xiàn)實中 數(shù)據(jù)結(jié)構(gòu)中

?鏈表和順序表的區(qū)別

?

2. 鏈表的分類

實際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來就有8種鏈表結(jié)構(gòu)：

?2.1單向或者雙向

?2.2 帶頭或者不帶頭

?2.3循環(huán)或者非循環(huán)

?雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實際中最常用還是兩種結(jié)構(gòu)：

?1. 無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)
構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。

2. 帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都
是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶
來很多優(yōu)勢，實現(xiàn)反而簡單了，后面我們代碼實現(xiàn)了就知道了。

3.鏈表實現(xiàn)

3.1無頭單向非循環(huán)單鏈表

1.主要功能

?2.接口實現(xiàn)

?

?

?

?

?

?

?

?

?

?

?

?

?以上就是鏈表每個接口的實現(xiàn)了！！！！

3.2帶頭雙向循環(huán)鏈表

1.主要功能

在理解單鏈表的基礎(chǔ)上，理解帶頭雙向循環(huán)鏈表就簡單很多了；

2.接口實現(xiàn)

?

?

?

?

?

?

?

?

?

?

?4.代碼

?1.單鏈表

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType;
typedef struct SListNode
{SLDataType data;struct SListNode* next;
}SLTNode;//打印鏈表
void SLTPrint(SLTNode* phead);//創(chuàng)建一個新節(jié)點
SLTNode* BuySListNode(SLDataType x);//尾插
void SLTPushBack(SLTNode** pphead, SLDataType x);//頭插
void SLTPushFront(SLTNode** pphead, SLDataType x);//尾刪
void SLTPopBack(SLTNode** pphead);//頭刪
void SLTPopFront(SLTNode** pphead);//尋找
SLTNode* SLTFind(SLTNode* phead, SLDataType x);// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x);// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLDataType x);// 刪除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);// 刪除pos的后一個位置
void SLTEraseAfter(SLTNode* pos);//銷毀鏈表
void SLTDestroy(SLTNode** pphead);

#define _CRT_SECURE_NO_WARNINGS 1#include "SList.h"//打印鏈表
void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}//創(chuàng)建一個新節(jié)點
SLTNode* BuySListNode(SLDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("BuySListNode fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}//尾插
void SLTPushBack(SLTNode** pphead, SLDataType x)
{SLTNode* newnode = BuySListNode(x);if (*pphead == NULL){//改變指向結(jié)構(gòu)體的指針，所以要用二級指針*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}//改變結(jié)構(gòu)體，用結(jié)構(gòu)體指針tail->next = newnode;}
}//頭插
void SLTPushFront(SLTNode** pphead, SLDataType x)
{SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;}//尾刪
void SLTPopBack(SLTNode** pphead)
{//空assert(*pphead);//一個節(jié)點if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//一個以上節(jié)點SLTNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}//頭刪
void SLTPopFront(SLTNode** pphead)
{//kongassert(*pphead);//非空SLTNode* newnode = (*pphead)->next;free(*pphead);*pphead = newnode;}//尋找
SLTNode* SLTFind(SLTNode* phead, SLDataType x)
{assert(phead);while (phead){if (phead->data == x){return phead;}phead = phead->next;}return NULL;
}// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{assert(pphead);assert(pos);//頭插if (*pphead == pos){SLTPushFront(pphead,x);return;}SLTNode* prev = *pphead;SLTNode* newnode = BuySListNode(x);while(prev){if (prev->next == pos){prev->next = newnode;newnode->next = pos;return;}else{prev = prev->next;}}
}// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLDataType x)
{assert(pos);SLTNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;}//SLTNode*  posafter = pos->next;
//pos->next = newnode;
//newnode->next = posafter;// 刪除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(*pphead);assert(pos);if (*pphead == pos){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}}// 刪除pos的后一個位置
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//檢查尾節(jié)點assert(pos->next);SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}//銷毀鏈表
void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur){SLTNode* next = cur;next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

?

2.雙向鏈表

#pragma once#include <stdio.h>
#include <assert.h>
#include <stdlib.h>typedef int LTDataTpye;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataTpye data;}LTNode;//創(chuàng)建新節(jié)點
LTNode* BuyLTnode(LTDataTpye x);//初始化
LTNode* LTInit();//打印鏈表
void LTPrint(LTNode* phead);//頭插
void LTPushFront(LTNode* phead, LTDataTpye x);//頭刪
void LTPopFront(LTNode* phead);//尾插
void LTPushBack(LTNode* phead, LTDataTpye x);//尾刪
void LTPopBack(LTNode* phead);//尋找
LTNode* LTFind(LTNode* phead, LTDataTpye x);//在pos之前插入
void LTInsert(LTNode* pos, LTDataTpye x);//消除pos位置的元素
void LTErase(LTNode* pos);//銷毀鏈表
void LTDestroy(LTNode* phead);

#define _CRT_SECURE_NO_WARNINGS 1
#include "DList.h"//創(chuàng)建新節(jié)點
LTNode* BuyLTnode(LTDataTpye x)
{LTNode* node = (LTNode *)malloc(sizeof(LTNode));if (node == NULL){perror("BuyLTNode");exit(-1);}node->data = x;node->prev = NULL;node->next= NULL;return node;
}//初始化
LTNode* LTInit()
{LTNode* phead = BuyLTnode(0);phead->next = phead;phead->prev = phead;return phead;
}//打印鏈表
void LTPrint(LTNode* phead)
{assert(phead);printf("phead<=>");LTNode* cur = phead->next;while (cur!= phead){printf("%d<=>",cur->data);cur = cur->next;}printf("\n");
}//頭插
void LTPushFront(LTNode* phead, LTDataTpye x)
{assert(phead);LTNode* newnode = BuyLTnode( x);LTNode* after = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = after;after->prev = newnode;}//頭刪
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* first = phead->next;LTNode* second = first->next;free(first);phead->next = second;second->prev = phead;}//尾插
void LTPushBack(LTNode* phead, LTDataTpye x)
{assert(phead);LTNode* newnode = BuyLTnode(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}//尾刪
void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* first = tail->prev;free(tail);first->next = phead;phead->prev = first;}//尋找
LTNode* LTFind(LTNode* phead, LTDataTpye x)
{assert(phead);LTNode* cur = phead->next;while (cur !=phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}//在pos之前插入
void LTInsert(LTNode* pos, LTDataTpye x)
{assert(pos);LTNode* first = pos->prev;LTNode* newnode = BuyLTnode(x);first->next = newnode;newnode->prev = first;pos->prev = newnode;newnode->next = pos;}//消除pos位置的元素
void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posafter = pos->next;free(pos);posprev->next = posafter;posafter->prev = posprev;}//銷毀鏈表
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != (phead)){LTNode* cur1 = cur;cur = cur->next;free(cur1);}free(phead);phead == NULL;}