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