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