快捷導(dǎo)航

C語(yǔ)言雙向鏈表的原理與使用操作

更新時(shí)間：2022年05月23日 10:50:40 作者：Mi?ronin

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。本文主要介紹了C語(yǔ)言算法中雙向鏈表的實(shí)現(xiàn)，需要的可以參考一下

一.引入

我們?cè)趩捂湵碇?，有了next指針，這個(gè)指針是用來(lái)指向下一個(gè)節(jié)點(diǎn)的，如果我們需要查找下一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為o(1),如果我們需要查找上一個(gè)節(jié)點(diǎn)的時(shí)候，那么時(shí)間復(fù)雜度就變?yōu)閛(n)了，需要從頭進(jìn)行遍歷一遍；這時(shí)我們就會(huì)想：如果可以向前查找就方便了許多，因此我們引入了雙向鏈表。

二.雙向鏈表的定義

雙向鏈表：是在單鏈表的每個(gè)節(jié)點(diǎn)中，再設(shè)置一個(gè)指向前驅(qū)結(jié)點(diǎn)的指針域。

顧名思義就是鏈表由單向的變成了雙向的，每一個(gè)節(jié)點(diǎn)由原來(lái)的一個(gè)指針變?yōu)閮蓚€(gè)指針，一個(gè)用來(lái)指向直接后繼，另一個(gè)用來(lái)指向直接前驅(qū)。

三.雙向鏈表與單鏈表對(duì)比

通過(guò)對(duì)比可以更好認(rèn)識(shí)二者的聯(lián)系與區(qū)別。

3.1圖示對(duì)比

單鏈表：

雙向鏈表：

3.2代碼對(duì)比

單鏈表代碼如下：

typedef struct Node{ //定義單鏈表結(jié)點(diǎn)類型
	int data; //數(shù)據(jù)域，可以是別的各種數(shù)據(jù)類型
	struct Node *next; //指針域
}LNode, *LinkList;

雙向鏈表代碼如下：

typedef struct DulNode{
	int data;			// 	數(shù)據(jù)域
	struct DulNode *prior;		//  向前的指針
	struct DulNode *next;		//  向后的指針
}DulNode,*DuLinkList;

四.雙向鏈表的操作

雙向鏈表是單鏈表中擴(kuò)展出來(lái)的結(jié)構(gòu)，所以有很多的操作是和單鏈表相同的，如求長(zhǎng)度，查找元素，獲取一個(gè)元素，這里我們對(duì)雙向鏈表進(jìn)行創(chuàng)建，插入，刪除，銷毀的一系列操作。

4.1雙向鏈表的創(chuàng)建

雙向鏈表在初始化時(shí)，要給首尾兩個(gè)節(jié)點(diǎn)分配內(nèi)存空間。成功分配后，需要將首節(jié)點(diǎn)的prior指針和尾節(jié)點(diǎn)的next指針都指向NULL，這是十分關(guān)鍵的一步，因?yàn)檫@是之后用來(lái)判斷空表的條件。并且當(dāng)鏈表為空時(shí)，要將首節(jié)點(diǎn)的next指向尾節(jié)點(diǎn)，尾節(jié)點(diǎn)的prior指向首節(jié)點(diǎn)。

pElem CreatList(){
	pElem head = (pElem)malloc( sizeof(eElem) );
	assert( head != NULL );		//進(jìn)行斷言
	head->next = head->prior = NULL；//初始化鏈表指針置空
	return head;
}

4.2雙向鏈表的插入

雙向鏈表的插入其實(shí)并不復(fù)雜，只是在原有單鏈表的基礎(chǔ)上多了連接一個(gè)向前的指針而已。但是需要注意的是操作的順序很重要，不可以寫(xiě)反了。

以下面這個(gè)為例，假設(shè)存儲(chǔ)元素e的結(jié)點(diǎn)為s，要實(shí)現(xiàn)將結(jié)點(diǎn)s插入到結(jié)點(diǎn)p和p->next之間

核心代碼就只有以下四行：

s->prior=p; //把p賦值給s的前驅(qū)
s->next=p->next;// 把p->next賦值給s的后繼
p->next->prior=s;// 把s賦值給p->next的前驅(qū)
p->next=s; //把s賦值給p的后繼

切記順序不可以記錯(cuò) 在寫(xiě)代碼的時(shí)候可以將操作步驟畫(huà)出來(lái)，理清實(shí)施步驟的順序。

4.3雙向鏈表的刪除

如果將插入操作的原理理解后，那么刪除就很好理解了。

刪除只需要兩個(gè)步驟：

核心代碼只有三行：

p->prior->next=p->next; //把p->next賦值給p->prior的后繼
p->next->prior=p->prior;//把p->prior賦值給p->next的前驅(qū)
free(p); //釋放結(jié)點(diǎn)

4.4雙向鏈表的銷毀

銷毀一個(gè)雙向鏈表的操作同單鏈表的相似。指針不斷向后運(yùn)動(dòng)，每運(yùn)動(dòng)一個(gè)結(jié)點(diǎn)，釋放上一個(gè)結(jié)點(diǎn)。

代碼如下：

void DestroyList( pElem head ){
	pElem tmp;
	while( head->next != NULL ){
		tmp = head;		//  指針不斷后移
		head = head->next;
		free(tmp);
	}
	free(head);
}

五.總結(jié)

雙向鏈表相比于單鏈表來(lái)說(shuō)，是更復(fù)雜一些的，畢竟多了一個(gè)prior指針，對(duì)于插入和刪除需要特別注意這兩種操作的核心思想以及操作順序。另外雙向鏈表，帶來(lái)了方便，可以有效提高算法的時(shí)間性能。

六.全部代碼

這里引用一位大佬寫(xiě)的代碼，將頭插法和尾插法創(chuàng)建表都寫(xiě)了，寫(xiě)的很細(xì)節(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;
    /*這一步很關(guān)鍵*/ 
    (*head)->prior=NULL;
    (*tail)->next=NULL;
    /*鏈表為空時(shí)讓頭指向尾*/
    (*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");
}
/*返回第一個(gè)值為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;
}
/*返回表長(zhǎng)*/
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個(gè)位置的元素，并用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ù)據(jù)非法\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("鏈表為空\(chéng)n");
    else
        printf("鏈表不為空\(chéng)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("表長(zhǎng)為%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("鏈表為空\(chéng)n");
    else
        printf("鏈表不為空\(chéng)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);
}

到此這篇關(guān)于C語(yǔ)言雙向鏈表的原理與使用操作的文章就介紹到這了,更多相關(guān)C語(yǔ)言雙向鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: