C語言雙向鏈表的原理與使用操作
更新時間：2022年05月23日 10:50:40 作者：Mi?ronin
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據結點中都有兩個指針，分別指向直接后繼和直接前驅。本文主要介紹了C語言算法中雙向鏈表的實現(xiàn)，需要的可以參考一下
一.引入
我們在單鏈表中，有了next指針，這個指針是用來指向下一個節(jié)點的，如果我們需要查找下一個結點的時間復雜度為o(1),如果我們需要查找上一個節(jié)點的時候，那么時間復雜度就變?yōu)閛(n)了，需要從頭進行遍歷一遍；這時我們就會想：如果可以向前查找就方便了許多，因此我們引入了雙向鏈表。
二.雙向鏈表的定義
雙向鏈表：是在單鏈表的每個節(jié)點中，再設置一個指向前驅結點的指針域。
顧名思義就是鏈表由單向的變成了雙向的，每一個節(jié)點由原來的一個指針變?yōu)閮蓚€指針，一個用來指向直接后繼，另一個用來指向直接前驅。
三.雙向鏈表與單鏈表對比
通過對比可以更好認識二者的聯(lián)系與區(qū)別。
3.1圖示對比
單鏈表：
雙向鏈表：
3.2代碼對比
單鏈表代碼如下：
typedef struct Node{ //定義單鏈表結點類型
int data; //數(shù)據域，可以是別的各種數(shù)據類型
struct Node *next; //指針域
}LNode, *LinkList;
雙向鏈表代碼如下：
typedef struct DulNode{
int data; // 數(shù)據域
struct DulNode *prior; // 向前的指針
struct DulNode *next; // 向后的指針
}DulNode,*DuLinkList;
四.雙向鏈表的操作
雙向鏈表是單鏈表中擴展出來的結構，所以有很多的操作是和單鏈表相同的，如求長度，查找元素，獲取一個元素，這里我們對雙向鏈表進行創(chuàng)建，插入，刪除，銷毀的一系列操作。
4.1雙向鏈表的創(chuàng)建
雙向鏈表在初始化時，要給首尾兩個節(jié)點分配內存空間。成功分配后，需要將首節(jié)點的prior指針和尾節(jié)點的next指針都指向NULL，這是十分關鍵的一步，因為這是之后用來判斷空表的條件。并且當鏈表為空時，要將首節(jié)點的next指向尾節(jié)點，尾節(jié)點的prior指向首節(jié)點。
pElem CreatList(){
pElem head = (pElem)malloc( sizeof(eElem) );
assert( head != NULL ); //進行斷言
head->next = head->prior = NULL；//初始化鏈表指針置空
return head;
}
4.2雙向鏈表的插入
雙向鏈表的插入其實并不復雜，只是在原有單鏈表的基礎上多了連接一個向前的指針而已。但是需要注意的是操作的順序很重要，不可以寫反了。
以下面這個為例，假設存儲元素e的結點為s，要實現(xiàn)將結點s插入到結點p和p->next之間
核心代碼就只有以下四行：
s->prior=p; //把p賦值給s的前驅
s->next=p->next;// 把p->next賦值給s的后繼
p->next->prior=s;// 把s賦值給p->next的前驅
p->next=s; //把s賦值給p的后繼
切記順序不可以記錯 在寫代碼的時候可以將操作步驟畫出來，理清實施步驟的順序。
4.3雙向鏈表的刪除
如果將插入操作的原理理解后，那么刪除就很好理解了。
刪除只需要兩個步驟：
核心代碼只有三行：
p->prior->next=p->next; //把p->next賦值給p->prior的后繼
p->next->prior=p->prior;//把p->prior賦值給p->next的前驅
free(p); //釋放結點
4.4雙向鏈表的銷毀
銷毀一個雙向鏈表的操作同單鏈表的相似。指針不斷向后運動，每運動一個結點，釋放上一個結點。
代碼如下：
void DestroyList( pElem head ){
pElem tmp;
while( head->next != NULL ){
tmp = head; // 指針不斷后移
head = head->next;
free(tmp);
}
free(head);
}
五.總結
雙向鏈表相比于單鏈表來說，是更復雜一些的，畢竟多了一個prior指針，對于插入和刪除需要特別注意這兩種操作的核心思想以及操作順序。另外雙向鏈表，帶來了方便，可以有效提高算法的時間性能。
六.全部代碼
這里引用一位大佬寫的代碼，將頭插法和尾插法創(chuàng)建表都寫了，寫的很細節(jié)，很清楚大家可以參考一下。
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int status;
typedef int elemtype;
typedef struct node{
elemtype data;
struct node * next;
struct node * prior;
}node;
typedef struct node* dlinklist;
status visit(elemtype c){
printf("%d ",c);
}
/*雙向鏈表初始化*/
status initdlinklist(dlinklist * head,dlinklist * tail){
(*head)=(dlinklist)malloc(sizeof(node));
(*tail)=(dlinklist)malloc(sizeof(node));
if(!(*head)||!(*tail))
return ERROR;
/*這一步很關鍵*/
(*head)->prior=NULL;
(*tail)->next=NULL;
/*鏈表為空時讓頭指向尾*/
(*head)->next=(*tail);
(*tail)->prior=(*head);
}
/*判定是否為空*/
status emptylinklist(dlinklist head,dlinklist tail){
if(head->next==tail)
return TRUE;
else
return FALSE;
}
/*尾插法創(chuàng)建鏈表*/
status createdlinklisttail(dlinklist head,dlinklist tail,elemtype data){
dlinklist pmove=tail,pinsert;
pinsert=(dlinklist)malloc(sizeof(node));
if(!pinsert)
return ERROR;
pinsert->data=data;
pinsert->next=NULL;
pinsert->prior=NULL;
tail->prior->next=pinsert;
pinsert->prior=tail->prior;
pinsert->next=tail;
tail->prior=pinsert;
}
/*頭插法創(chuàng)建鏈表*/
status createdlinklisthead(dlinklist head,dlinklist tail,elemtype data){
dlinklist pmove=head,qmove=tail,pinsert;
pinsert=(dlinklist)malloc(sizeof(node));
if(!pinsert)
return ERROR;
else{
pinsert->data=data;
pinsert->prior=pmove;
pinsert->next=pmove->next;
pmove->next->prior=pinsert;
pmove->next=pinsert;
}
}
/*正序打印鏈表*/
status traverselist(dlinklist head,dlinklist tail){
/*dlinklist pmove=head->next;
while(pmove!=tail){
printf("%d ",pmove->data);
pmove=pmove->next;
}
printf("\n");
return OK;*/
dlinklist pmove=head->next;
while(pmove!=tail){
visit(pmove->data);
pmove=pmove->next;
}
printf("\n");
}
/*返回第一個值為data的元素的位序*/
status locateelem(dlinklist head,dlinklist tail,elemtype data){
dlinklist pmove=head->next;
int pos=1;
while(pmove&&pmove->data!=data){
pmove=pmove->next;
pos++;
}
return pos;
}
/*返回表長*/
status listlength(dlinklist head,dlinklist tail){
dlinklist pmove=head->next;
int length=0;
while(pmove!=tail){
pmove=pmove->next;
length++;
}
return length;
}
/*逆序打印鏈表*/
status inverse(dlinklist head,dlinklist tail){
dlinklist pmove=tail->prior;
while(pmove!=head){
visit(pmove->data);
pmove=pmove->prior;
}
printf("\n");
}
/*刪除鏈表中第pos個位置的元素，并用data返回*/
status deleteelem(dlinklist head,dlinklist tail,int pos,elemtype *data){
int i=1;
dlinklist pmove=head->next;
while(pmove&&i<pos){
pmove=pmove->next;
i++;
}
if(!pmove||i>pos){
printf("輸入數(shù)據非法\n");
return ERROR;
}
else{
*data=pmove->data;
pmove->next->prior=pmove->prior;
pmove->prior->next=pmove->next;
free(pmove);
}
}
/*在鏈表尾插入元素*/
status inserttail(dlinklist head,dlinklist tail,elemtype data){
dlinklist pinsert;
pinsert=(dlinklist)malloc(sizeof(node));
pinsert->data=data;
pinsert->next=NULL;
pinsert->prior=NULL;
tail->prior->next=pinsert;
pinsert->prior=tail->prior;
pinsert->next=tail;
tail->prior=pinsert;
return OK;
}
int main(void){
dlinklist head,tail;
int i=0;
elemtype data=0;
initdlinklist(&head,&tail);
if(emptylinklist(head,tail))
printf("鏈表為空\n");
else
printf("鏈表不為空\n");
printf("頭插法創(chuàng)建鏈表\n");
for(i=0;i<10;i++){
createdlinklisthead(head,tail,i);
}
traverselist(head,tail);
for(i=0;i<10;i++){
printf("表中值為%d的元素的位置為",i);
printf("%d位\n",locateelem(head,tail,i));
}
printf("表長為%d\n",listlength(head,tail));
printf("逆序打印鏈表");
inverse(head,tail);
for(i=0;i<10;i++){
deleteelem(head,tail,1,&data);
printf("被刪除的元素為%d\n",data);
}
traverselist(head,tail);
if(emptylinklist(head,tail))
printf("鏈表為空\n");
else
printf("鏈表不為空\n");
printf("尾插法創(chuàng)建鏈表\n");
for(i=0;i<10;i++){
//inserttail(head,tail,i);
createdlinklisttail(head,tail,i);
}
traverselist(head,tail);
printf("逆序打印鏈表");
inverse(head,tail);
}
到此這篇關于C語言雙向鏈表的原理與使用操作的文章就介紹到這了,更多相關C語言雙向鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家介紹了C語言中Static關鍵字，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
這篇文章主要為大家詳細介紹了C++設計模式之Proxy模式的相關資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-07-07
C語言連續(xù)生成隨機數(shù)的實現(xiàn)方法
這篇文章主要介紹了C語言連續(xù)生成隨機數(shù)的實現(xiàn)方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-01-01
這篇文章主要為大家詳細介紹了C語言實現(xiàn)串的順序存儲表示與基本操作，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-09-09
今天小編就為大家分享一篇opencv3/C++輪廓的提取與篩選方式，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12
這篇文章主要為大家詳細介紹了C++實現(xiàn)求動態(tài)矩陣各元素的和，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10
今天小編就為大家分享一篇關于C語言字符串另類用法的實現(xiàn)，小編覺得內容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
枚舉和模擬其實是沒什么算法可言的，大多數(shù)都是按照題目意思去寫，這里提供快排和歸并的兩個模板，感興趣的朋友來看看吧2022-04-04
這篇文章主要介紹了C++設計模式之建造者模式,一個復雜對象是由多個部件組成的,建造者模式是把復雜對象的創(chuàng)建和部件的創(chuàng)建分別開來,分別用Builder類和Director類來表示,需要的朋友可以參考下2014-09-09
C++11中l(wèi)onglong超長整型和nullptr初始化空指針
本文介紹?C++11?標準中新添加的?long?long?超長整型和?nullptr?初始化空指針，在?C++11?標準下，相比?NULL?和?0，使用?nullptr?初始化空指針可以令我們編寫的程序更加健壯，本文結合示例代碼給大家詳細講解，需要的朋友跟隨小編一起看看吧2022-12-12