C語言實現(xiàn)數(shù)據(jù)結構和雙向鏈表操作

來源：本站原創(chuàng)|時間：2020-01-10|欄目：C語言|點擊：次

數(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"); 
}

至于雙向鏈表的其他操作，如定位，和單鏈表的操作類同，不再贅述。

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

上一篇：C語言數(shù)據(jù)結構雙向鏈表的建立與基本操作

欄目：C語言

下一篇：使用remalloc的注意事項說明(必看篇)

本文標題：C語言實現(xiàn)數(shù)據(jù)結構和雙向鏈表操作

本文地址：http://www.jygsgssxh.com/a1/Cyuyan/1695.html

更多C語言

您可能感興趣的文章

閱讀排行

本欄相關

隨機閱讀

^{<var id="hnwcm"></var>}

雷火电竞-中国电竞赛事及体育赛事平台

C語言

C語言實現(xiàn)數(shù)據(jù)結構和雙向鏈表操作

您可能感興趣的文章

閱讀排行

本欄相關

隨機閱讀