C語(yǔ)言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)和雙向鏈表操作
數(shù)據(jù)結(jié)構(gòu) 雙向鏈表的實(shí)現(xiàn)
雙向鏈表中的每一個(gè)結(jié)點(diǎn)都含有兩個(gè)指針域，一個(gè)指針域存放其后繼結(jié)點(diǎn)的存儲(chǔ)地址，另一個(gè)指針域則存放其前驅(qū)結(jié)點(diǎn)的存儲(chǔ)地址。
雙向鏈表結(jié)點(diǎn)的類型描述：
//雙向鏈表的類型描述
typedef int ElemType;
typedef struct node{
ElemType data;
struct node *prior,*next;
}DuLNode,*DuLinkList;
其中，prior域存放的是其前驅(qū)結(jié)點(diǎn)的存儲(chǔ)地址，next域存放的是其后繼結(jié)點(diǎn)的存儲(chǔ)地址。
雙向鏈表有兩個(gè)特點(diǎn)：
一是可以從兩個(gè)方向搜索某個(gè)結(jié)點(diǎn)，這使得鏈表的某些操作（如插入和刪除）變得比較簡(jiǎn)單； 二是無(wú)論利用前鏈還是后鏈都可以遍歷整個(gè)雙向鏈表。
雙向鏈表的操作基本和單鏈表的操作相同；
1. 頭插法創(chuàng)建帶頭結(jié)點(diǎn)的雙向鏈表Create_DLinkListF(int n)
//頭插法創(chuàng)建帶頭結(jié)點(diǎn)的雙向鏈表
DuLinkList Create_DLinkListF(int n){
DuLinkList L,p;
int i = n - 1;
ElemType x;
//新建頭結(jié)點(diǎn)
L = (DuLinkList)malloc(sizeof(DuLNode));
L->prior = NULL;
L->next = NULL;
//添加第一個(gè)結(jié)點(diǎn)
scanf("%d",&x);
p = (DuLinkList)malloc(sizeof(DuLNode));
p->data = x;
L->next = p;
p->prior = L;
p->next = NULL;
//加入其他結(jié)點(diǎn)
while(i > 0){
scanf("%d",&x);
p = (DuLinkList)malloc(sizeof(DuLNode));
p->data = x;
p->next = L->next;
L->next->prior = p;
p->prior = L;
L->next = p;
i--;
}
return L;
}
2. 尾插法創(chuàng)建帶頭結(jié)點(diǎn)的雙向鏈表Create_DLinkListR(int n)
//尾插法創(chuàng)建帶頭結(jié)點(diǎn)的雙向鏈表
DuLinkList Create_DLinkListR(int n){
DuLinkList L,p,lastNode;
int i = n - 1;
ElemType x;
//新建頭結(jié)點(diǎn)
L = (DuLinkList)malloc(sizeof(DuLNode));
L->prior = NULL;
L->next = NULL;
//添加第一個(gè)結(jié)點(diǎn)
scanf("%d",&x);
p = (DuLinkList)malloc(sizeof(DuLNode));
p->data = x;
L->next = p;
p->prior = L;
p->next = NULL;
lastNode = p;
//加入其他結(jié)點(diǎn)
while(i > 0){
scanf("%d",&x);
p = (DuLinkList)malloc(sizeof(DuLNode));
p->data = x;
lastNode->next = p;
p->prior = lastNode;
p->next = NULL;
lastNode = p;
i--;
}
return L;
}
3. 在指定結(jié)點(diǎn)之前插入新結(jié)點(diǎn)Insert_DLinkListBefore(DuLinkList p,ElemType x)
//在指定結(jié)點(diǎn)之前插入新結(jié)點(diǎn)
void Insert_DLinkListBefore(DuLinkList p,ElemType x){
DuLinkList newNode;
//判斷結(jié)點(diǎn)p之前的結(jié)點(diǎn)的合法性：
if(p->prior == NULL)
printf("結(jié)點(diǎn)不合法，不能在該結(jié)點(diǎn)之前插入結(jié)點(diǎn)\n");
else{
newNode = (DuLinkList)malloc(sizeof(DuLNode));
newNode->data = x;
newNode->next = p;
p->prior->next = newNode;
newNode->prior = p->prior;
p->prior = newNode;
}
}
4. 在指定結(jié)點(diǎn)之后插入新結(jié)點(diǎn)Insert_DLinkListAfter(DuLinkList p,ElemType x)
//在指定結(jié)點(diǎn)之后插入新結(jié)點(diǎn)
void Insert_DLinkListAfter(DuLinkList p,ElemType x){
DuLinkList newNode;
newNode = (DuLinkList)malloc(sizeof(DuLNode));
newNode->data = x;
//當(dāng)插入位置是最后一個(gè)結(jié)點(diǎn)之后時(shí)
if(p->next == NULL){
p->next = newNode;
newNode->prior = p;
newNode->next = NULL;
}
else{
newNode->next = p->next;
p->next->prior = newNode;
p->next = newNode;
newNode->prior = p;
}
}
5. 刪除指定結(jié)點(diǎn)Delete_DLinkList(DuLinkList p)
//刪除指定結(jié)點(diǎn)
void Delete_DLinkList(DuLinkList p){
//如果刪除的是最后一個(gè)元素
if(p->next == NULL)
p->prior->next = NULL;
else{
p->prior->next = p->next;
p->next->prior = p->prior;
}
free(p);
}
6. 后鏈輸出雙向鏈表Print_DLinkListN(DuLinkList L)
//后鏈輸出雙向鏈表
void Print_DLinkListN(DuLinkList p){
while(p != NULL){
printf("%d\t",p->data);
p = p->next;
}
printf("\n");
}
7.前鏈輸出雙向鏈表Print_DLinkListP(DuLinkList p)
//前鏈輸出雙向鏈表
void Print_DLinkListP(DuLinkList p){
while(p != NULL){
printf("%d\t",p->data);
p = p-prior;
}
printf("\n");
}
至于雙向鏈表的其他操作，如定位，和單鏈表的操作類同，不再贅述。
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
相關(guān)文章
Opencv下載和導(dǎo)入Visual studio2022的實(shí)現(xiàn)步驟
本文主要介紹了Opencv下載和導(dǎo)入Visual studio2022的實(shí)現(xiàn)步驟，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05
C++如何實(shí)現(xiàn)BCD碼和ASCII碼的相互轉(zhuǎn)換
這篇文章主要介紹了C++實(shí)現(xiàn)BCD碼和ASCII碼互轉(zhuǎn)，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-06-06
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言版五子棋游戲的實(shí)現(xiàn)代碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-07-07
C++實(shí)現(xiàn)LeetCode(6.字型轉(zhuǎn)換字符串)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(6.字型轉(zhuǎn)換字符串),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C語(yǔ)言安全編碼之?dāng)?shù)值中的sizeof操作符
這篇文章主要介紹了C語(yǔ)言安全編碼的數(shù)值中的sizeof操作符用法注意事項(xiàng),需要的朋友可以參考下2014-07-07
這篇文章主要介紹了QT QML的元素布局的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-02-02
Linux下C語(yǔ)言實(shí)現(xiàn)貪吃蛇小游戲
C++超詳細(xì)講解模擬實(shí)現(xiàn)vector