《數據結構》 2.3 循環鏈表

http://hncu.acmclub.com/index.php?app=problem_title&id=111&problem_id=1328

題目描述

雙向鏈表是在結點中既保存了后一個結點指針又保存了前一個結點指針的鏈表。這種鏈表較單向鏈表而言能夠快速查找某一結點的前后結點。下面給出雙向鏈表的定義、插入以及刪除算法描述。 圖1：雙向鏈表示例 （a）結點結構；（b）空的雙向循環鏈表；（c）含有三個結點的雙向循環鏈表 圖2：雙向鏈表的定義以及創建 雙向鏈表在插入與刪除時一定要注意其操作步驟的順序。下面給出雙向鏈表在插入與刪除時的圖示。 圖3：雙向鏈表插入與刪除的圖示 （a）雙向鏈表的刪除操作；（b）雙向鏈表的插入操作 圖4：雙向鏈表的查找以及插入 圖5：雙向鏈表的刪除操作

輸入格式

輸入數據只有一組，包含很多行。每行有1~3個整數。第一個整數如果是0，則表示輸出雙向鏈表中的所有元素；第一個整數如果是1，表示插入1個整數，其后跟2個整數i、e代表在第i個位置插入e；第一個整數如果是2，表示刪除1個整數，其后跟1個整數i，表示刪除的位置為i。
起始雙向鏈表為空表。保證鏈表中每個元素不會重復，同時所有的操作都合法。

輸出

當需要輸出雙向鏈表中的所有元素時輸出，每次輸出一行。整數間用一個空格隔開。

樣例輸入

1?1?2
0
1?2?7
0
2?1
0
1?2?4
1?3?5
1?2?6
0
2?3
0

樣例輸出

2
2?7
7
7?6?4?5
7?6?5

?

?

16號第3天改這道題 終于改對了 從這道題我發現自己之前寫的都錯了

#include<stdio.h> #include<stdlib.h>#define ERROR 0 #define OK 1typedef int Status; typedef int ElemType;//-----線性表的雙向鏈表存儲結構------- typedef struct Dulnode{int data;struct Dulnode *prior;struct Dulnode *next; }DuLNode,*DuLinkList;DuLinkList GetElemP_DuL(DuLinkList l,int i) {//找到雙向循環鏈表的第i個位置 DuLinkList s ;int j ;s = l->next ;for( j = 1; j < i&&s !=l; j++){s = s->next ;}return s; }Status ListInsert_DuL(DuLinkList l,int i,ElemType e) {//在帶頭結點的雙鏈表L中的第i個位置之前插入元素e //i的合法值為1<=i<= 表長+1; DuLinkList s ,p;if(!(p = GetElemP_DuL(l,i)))//在L中確定插入的位置指針p return ERROR;s= (DuLinkList)malloc(sizeof(DuLNode));s->data = e;p->prior->next = s;s->prior = p->prior ;s->next = p;p->prior = s;s = l->next ;return OK; }Status ListDelete_DuL(DuLinkList l,int i) { //刪除帶頭結點的雙鏈循環鏈表L中的第i個元素 //i的合法值1<= i<= 表長 DuLinkList p;if(!(p = GetElemP_DuL(l,i)))//在L中確定第i個元素的位置指針p return ERROR;p->prior->next = p->next ;p->next->prior = p->prior;free(p); }void print(DuLinkList l) {DuLinkList s = l->next ;int i = 0;while(s != l){if(i)printf(" ");printf("%d",s->data );s = s->next ;i++;}printf("\n");return ; }int main() {int n,i,e;DuLinkList l,s;l = (DuLinkList)malloc(sizeof(DuLNode));l->next = l ;l->prior = l ;while(scanf("%d",&n)!=EOF){switch(n){case 0:print(l);break;case 1:scanf("%d%d",&i,&e);ListInsert_DuL(l,i,e);break;case 2:scanf("%d",&i);ListDelete_DuL(l,i);break;}}return 0;}

轉載于:https://www.cnblogs.com/hellocheng/p/7350142.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的HNCU 1328: 算法2-18~2-19：双向循环链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。