溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

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

發(fā)布時間：2020-09-02 01:59:41 來源：腳本之家 閱讀：187 作者：jesson20121020 欄目：編程語言

數據結構  雙向鏈表的實現(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"); 
}

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

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

向AI問一下細節(jié)

免責聲明：本站發(fā)布的內容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。

AI
助
手