C語言線性表之雙鏈表詳解
定義
鏈表是通過一組任意的存儲單元來存儲線性表中的數據元素,每一個結點包含兩個域:存放數據元素信息的域稱為數據域,存放其後繼元素地址的域稱為指針域。因此n個元素的線性表通過每個結點的指針域連接成瞭一個“鏈條”,稱為鏈表。若此鏈表的每個結點中包含兩個指針域,則被稱為雙鏈表。
雙鏈表的結點結構定義如下:
typedef struct node { DataType data; struct node *llink; struct node *rlink; } DLinkList;
像單鏈表一樣,需要一個類似於“頭結點”一樣的結點(記為rear),其數據域為空,指針域的llink指針指向表頭結點,rlink指針指向表尾結點。而表頭結點的llink指針指向NULL,表尾結點的rlink指針指向NULL。
1.刪除
假設結點p是待刪除結點,我們隻需讓p的前一個結點的rlink指針(p->llink->rlink)指向p的後一個結點(p->rlink),並讓p的後一個結點的llink指針(p->rlink->llink)指向p的前一個指針(p->llink),然後釋放p所占內存空間,即可完成刪除操作。因為這是雙鏈表的刪除算法,因此待刪除結點在表頭或表尾會有略微的區別,但隻要抓住核心算法:
p->llink->rlink = p->rlink; p->rlink->llink = p->llink; free(p);
再對表頭表尾結點進行特殊處理(改變rear指針的指針域)即可。
雙鏈表刪除算法示例如下:
int DeleteDLinkList(DLinkList *rear, DLinkList *p) /*在雙鏈表刪除結點p,成功返回1,否則返回0*/ { DLinkList *q = p->rlink, *s = p->llink;/*q指向p的後繼,s指向p的前繼*/ if (s!=NULL && q==NULL)/*刪除的是最後一個結點*/ { rear->rlink = p->llink; p->llink->rlink = p->rlink; free(p); return 1; } if (s==NULL && q!=NULL)/*刪除的是第一個結點*/ { rear->llink = p->rlink; p->rlink->llink = p->llink; free(p); return 1; } if (s==NULL & q==NULL)/*雙鏈表隻有一個結點*/ { rear->rlink = rear->llink = NULL; free(p); return 1; } if (s!=NULL && q!=NULL) { p->llink->rlink = p->rlink; p->rlink->llink = p->llink; free(p); return 1; } return 0; }
2.插入
假設要把結點q插入到結點p與p的後一個結點之間,需要①先令q的llink指針(q->llink)和rlink指針(q->rlink)分別指向p和p的後一個結點(p->rlink),②再令p的後一個結點的llink指針(p->rlink->llink)指向q,③p的rlink指針(p->rlink)指向q。稍加分析可知,若①②③三個步驟順序錯誤,則無法完成插入。用代碼表示就是:
q->llink = p; q->rlink = p->rlink; p->rlink->llink = q; p->rlink = q;
同樣地,若要在表頭或表尾插入元素,則緊抓住核心算法稍作改變,並改變rear的指針域即可。
雙鏈表插入算法示例如下:
int Insert(DLinkList *rear, DLinkList *p, DataType x) { DLinkList *q = (DLinkList *)malloc(sizeof(DLinkList)); if (q == NULL) return 0; q->data = x;/*數據域賦值*/ if (p->rlink == NULL)/*在表尾插入元素*/ { rear->rlink = q; q->llink = p; q->rlink = p->rlink; p->rlink = q; return 1; } if (p == rear)/*若p為rear,認為在表頭插入元素*/ { q->llink = rear->llink->llink; q->rlink = rear->llink; rear->llink->llink = q; rear->llink = q; return 1; } q->llink = p; q->rlink = p->rlink; p->rlink->llink = q; p->rlink = q; return 1; }
3.建立
利用前面所講在表尾插入元素的辦法,我們可以每建立一個新結點就將其插入到表尾。當剛開始建立雙鏈表時,讓rear的llink指針(rear->llink)指向表頭結點,並讓表頭結點指向NULL;當建立結束時,讓rear的rlink指針(rear->rlink)指向最後一個結點,即可完成雙鏈表的建立。
DLinkList *CreateDLinkList(){ DLinkList *rear, *p, *q; rear = (DLinkList *)malloc(sizeof(DLinkList)); p = (DLinkList *)malloc(sizeof(DLinkList)); if (rear==NULL || p==NULL) { free(rear); free(p); return NULL; } DataType x; scanf(&x); p->data = x; rear->llink = p; p->llink = NULL; p->rlink = NULL; scanf(&x); while (x != flag)/*flag為建立結束的標志*/ { q = (DLinkList *)malloc(sizeof(DLinkList)); if (q == NULL) { DLinkList *pr; p = rear->llink; while (p != NULL) { pr = p->rlink; free(p); p = pr; } free(rear); return NULL; } q->data = x; q->llink = p; q->rlink = NULL; p->rlink = q; scanf(&x); } rear->rlink = q; return rear;}DLinkList *CreateDLinkList() { DLinkList *rear, *p, *q; rear = (DLinkList *)malloc(sizeof(DLinkList)); p = (DLinkList *)malloc(sizeof(DLinkList)); if (rear==NULL || p==NULL) { free(rear); free(p); return NULL; } DataType x; scanf(&x); p->data = x; rear->llink = p; p->llink = NULL; p->rlink = NULL; scanf(&x); while (x != flag)/*flag為建立結束的標志*/ { q = (DLinkList *)malloc(sizeof(DLinkList)); if (q == NULL) { DLinkList *pr; p = rear->llink; while (p != NULL) { pr = p->rlink; free(p); p = pr; } free(rear); return NULL; } q->data = x; q->llink = p; q->rlink = NULL; p->rlink = q; scanf(&x); } rear->rlink = q; return rear; }
4.查找
相對於單鏈表,雙鏈表的優勢是可以實現雙向的查找。假設讓指針p和指針q分別從表頭和表尾向中間遍歷雙鏈表的每一個結點,當p==q或p->llink==q時認為已遍歷結束。
DLinkList *SearchDLinkList(DLinkList *rear, DataType x) { DLinkList *p = rear->llink, *q = rear->rlink; while (p->data!=x && q->data!=x) { p = p->rlink; q = q->llink; if (p==q || p->llink==q) break; } if (p->data == x) return p; else if (q->data == x) return q; else return NULL; }
總結
本篇文章就到這裡瞭,希望能夠給你帶來幫助,也希望您能夠多多關註WalkonNet的更多內容