數據結構 雙向鏈表的實現
雙向鏈表中的每一個結點都含有兩個指針域，一個指針域存放其后繼結點的存儲地址，另一個指針域則存放其前驅結點的存儲地址。
雙向鏈表結點的類型描述：
//雙向鏈表的類型描述 typedef int ElemType; typedef struct node{ ElemType data; struct node *prior,*next; }DuLNode,*DuLinkList; 其中，prior域存放的是其前驅結點的存儲地址，next域存放的是其后繼結點的存儲地址。
雙向鏈表有兩個特點：
一是可以從兩個方向搜索某個結點，這使得鏈表的某些操作（如插入和刪除）變得比較簡單； 二是無論利用前鏈還是后鏈都可以遍歷整個雙向鏈表。
雙向鏈表的操作基本和單鏈表的操作相同；
1. 頭插法創建帶頭結點的雙向鏈表Create_DLinkListF(int n)
//頭插法創建帶頭結點的雙向鏈表 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. 尾插法創建帶頭結點的雙向鏈表Create_DLinkListR(int n)
//尾插法創建帶頭結點的雙向鏈表 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"); } 至于雙向鏈表的其他操作，如定位，和單鏈表的操作類同，不再贅述。
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
