第8篇文章中我們介紹了下鏈?zhǔn)酱鎯?chǔ)中鏈表中的一種--單鏈表，但是單鏈表有一個(gè)缺點(diǎn)勒魔，就是無(wú)法快速訪問(wèn)到前驅(qū)結(jié)點(diǎn)甫煞，當(dāng)查找到某個(gè)元素時(shí)，如果想找前邊的元素結(jié)點(diǎn)冠绢，需要再次從頭開始遍歷抚吠，這樣就比較麻煩。
那么就有人會(huì)問(wèn)弟胀，是否可以在結(jié)點(diǎn)中再增加一個(gè)指針來(lái)指向前驅(qū)結(jié)點(diǎn)呢楷力？答案是肯定的，增加了指向前驅(qū)結(jié)點(diǎn)的指針的鏈表稱為
雙鏈表
什么是雙鏈表孵户？
雙鏈表萧朝，顧名思義就是可以向兩個(gè)方向走的鏈表。它的每一個(gè)結(jié)點(diǎn)都有兩個(gè)指針夏哭，一個(gè)指向后繼結(jié)點(diǎn)检柬，另一個(gè)指向前驅(qū)結(jié)點(diǎn)，如下圖所示
我們從上圖中可以看到竖配，第一個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)pre指向了NULL,當(dāng)然在設(shè)計(jì)時(shí)我們也可以把它指向頭結(jié)點(diǎn)何址，最后一個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)next指向了NULL，這種和單鏈表是一樣的进胯。
在雙鏈表中用爪，通過(guò)一個(gè)結(jié)點(diǎn)可以找到他的后繼結(jié)點(diǎn)，也就可以找到他的前驅(qū)結(jié)點(diǎn)龄减。
雙鏈表在結(jié)構(gòu)和算法描述上和單鏈表相同项钮，只是某些算法實(shí)現(xiàn)比單鏈表復(fù)雜一些班眯。例如在插入元素時(shí)希停，需要同時(shí)修改兩個(gè)方向的指針指向烁巫，根據(jù)上圖所示雙鏈表，我們?cè)谠?0和67中間插入新元素88宠能，來(lái)看一下圖示過(guò)程
從上面的步驟圖中亚隙，我們看出，在插入元素時(shí)违崇，需要同時(shí)修改兩個(gè)方向的指針指向阿弃，同理，在刪除元素時(shí)羞延，也要修改這兩個(gè)指針渣淳。這里就不畫圖展示了，大家“腦補(bǔ)一下就可以了~~~”
前面已經(jīng)學(xué)過(guò)了單鏈表的實(shí)現(xiàn)過(guò)程伴箩，雙鏈表的實(shí)現(xiàn)與單鏈表的實(shí)現(xiàn)大同小異入愧，接下來(lái)我們看看雙鏈表的實(shí)現(xiàn)過(guò)程。
雙鏈表的實(shí)現(xiàn)
學(xué)習(xí)完雙鏈表的定義與基本操作之后嗤谚，我們還是用c語(yǔ)言來(lái)實(shí)現(xiàn)一個(gè)雙鏈表棺蛛，此雙鏈表所具有的功能如下：
創(chuàng)建雙鏈表
獲取雙鏈表的長(zhǎng)度
判斷雙鏈表是否為空
插入、刪除巩步、查找元素
銷毀雙鏈表
-
打印雙鏈表
在學(xué)習(xí)完單鏈表時(shí)旁赊，我們每一種操作算法都有詳細(xì)的描述和實(shí)現(xiàn)代碼，雙鏈表與單鏈表有很多操作是相似的椅野，這里就不在詳細(xì)描述终畅，但是會(huì)給出關(guān)鍵代碼的解釋。dlist.h(頭文件)
#ifndef _DLIST_H_ #define _DLIST_H_ struct Node; typedef struct Head * pHead;//頭結(jié)點(diǎn)類型 typedef struct Node * pNode;//數(shù)據(jù)結(jié)點(diǎn)類型 //定義頭結(jié)點(diǎn) struct Head{ int length; pNode next; }; //定義數(shù)據(jù)結(jié)點(diǎn) struct Node{ int data; pNode pre;//指向前驅(qū)結(jié)點(diǎn)的指針 pNode next;//指向后繼結(jié)點(diǎn)的指針 }竟闪； pHead DlistCreate();//創(chuàng)建雙鏈表方法聲明 int getLength(pHead ph);//獲取鏈表長(zhǎng)度方法聲明 int IsEmpty(pHead ph);//判斷鏈表是否為空方法聲明 int DlistInsert(pHead ph,int pos,int val);//在鏈表的pos位置插入val元素方法聲明 pNode DlistDelete(pHead ph,int val);//刪除鏈表中元素val方法聲明 pNode DlistFind(pHead ph,int val);//查找鏈表中元素val方法聲明 void DlistDestory(pHead ph);//銷毀鏈表方法聲明 void printFront(pHead ph);//打印鏈表中的元素方法聲明（從頭開始打由搿） void printLast(pHead ph);（從尾部開始打印） #endif
dist.c(函數(shù)實(shí)現(xiàn)文件)
#include "dlist.h"
#include <stdio.h>
#include <stdlib.h>
//創(chuàng)建雙鏈表
pHead DlistCreate(){
pHead ph=(pHead)malloc(sizeof(struct Head));//為頭結(jié)點(diǎn)分配空間
if(ph==NULL){
printf("分配頭結(jié)點(diǎn)失斕绷术徊！");
return NULL;
}
//創(chuàng)建好頭結(jié)點(diǎn)后，初始化頭結(jié)點(diǎn)中的數(shù)組
ph->length=0;
ph->next=NULL;
return ph;
}
//獲取鏈表長(zhǎng)度
int getLength(pHead ph){
if(ph==NULL){
printf("傳入的雙鏈表有誤鲸湃！");
}
return ph->length;
}
//判斷鏈表是否為空
int IsEmpty(pHead ph){
if(ph==NULL){
printf("傳入的雙鏈表有誤赠涮！");
}
if(ph->length==0){
return 1;
}
else{
return 0;
}
}
//在鏈表的pos位置插入元素val
int DlistInsert(pHead ph,int pos,int val){
pNode pval=NULL;
if(ph==NULL||pos<0||pos>ph->length){
printf("插入元素時(shí)，傳入?yún)?shù)有誤");
}
//如果參數(shù)無(wú)誤暗挑，給元素分配結(jié)點(diǎn)空間
pval=(pNode)malloc(sizeof(struct Node));
pval->data=val;
//判斷在那個(gè)位置插入元素笋除，先判斷鏈表是否為空
if(IsEmpty(ph)){
ph->next=pval;
pval->next=NULL;
pval->pre=Null;
}
else{
pNode pCur=ph->next;
if(pos==0){
ph->next=pval;//將頭結(jié)點(diǎn)指向pval
pval->next=pCur;//pval的后繼指針指向pCur
pval->pre=NULL;//pval的前驅(qū)結(jié)點(diǎn)指向空
pCur->pre=pval; //讓pCur的前驅(qū)結(jié)點(diǎn)指向pval
}
else{
for(int i=1;i<pos;i++){
pCur=pCur->next;//遍歷鏈表，找到要插入的位置炸裆，并將pCur指針后移
}
//循環(huán)結(jié)束垃它，此時(shí)pCur指向的就是要插入的位置
//下方是將指針斷開，再連接的過(guò)程
pval->next=pCur->next;
pCur->next->pre=pval;
pval->pre=pCur;
pCur->next=pval;
}
}
ph->length++;
return 1;
}
//刪除鏈表ph中的元素val
pNode DlistDelete(pHead ph,int val){
if(ph==NULL||ph->length==0){
printf("參數(shù)傳入有誤！");
}
pNode pval=DlistFind(ph,val);//找到值所在的結(jié)點(diǎn)
if(pval==NULL){
return NULL;
}
printf("將其刪除\n");
pNode pRe=pval->pre;
pNode pNext=pval->next;
pRe->next=pNext;
pNext->pre=pRe;
return pval;
}
//查找某個(gè)元素
pNode DlistFind(pHead ph,int val){
if(ph==NULL){
printf("參數(shù)傳遞有誤国拇！")
}
pNode pTmp=ph->next;
//此過(guò)程與單鏈表沒(méi)有差別
do{
if(pTmp->data==val){
printf("有此元素洛史！\n");
return pTmp;
}
pTmp=pTmp->next;//如果上方判斷不成立，則繼續(xù)進(jìn)行下一個(gè)判斷
}
//循環(huán)條件是直到鏈表的結(jié)尾
while(pTmp->next!=NULL);
//如果上方都不成立酱吝，說(shuō)明鏈表中沒(méi)有這個(gè)元素也殖，直接返回NULL
return NULL;
}
//銷毀鏈表
void DlistDestory(pHead ph){
pNode pCur=ph->next;
pNode=pTmp;
if(ph==NULL){
printf("參數(shù)傳入有誤！")务热；
}
while(pCur->next!=NULL){
pTmp=pCur->next;
free(pCur);//將結(jié)點(diǎn)釋放
pCur=pTmp;
}
//回到初始化狀態(tài)
ph->length=0;
ph->next=NULL;
}
//打印鏈表中的元素忆嗜，從前往后打印
void printFront(pHead ph){
if(ph==NULL){
printf("參數(shù)輸入有誤！");
}
pNode pTmp=ph->next;
while(pTmp->next!=NULL){
printf("%d",pTmp->data);
pTmp=pTmp->next;
}
printf("\n")
}
//倒序打印
void printLast(pHead ph){
if(ph==NULL){
printf("參數(shù)輸入有誤崎岂！");
}
//現(xiàn)將指針移動(dòng)到最后的位置
pNode pTmp=ph->next;
while(pTmp->next!=NULL){
pTmp=pTmp->next;
}
for(int i=--ph->length;i>=0;i--){
printf("%d",pTmp->data);
pTmp=pTmp->pre;
}
}
ok捆毫，雙向鏈表基本的操作diamante就寫完了，接下來(lái)我們看一下測(cè)試文件
main.c
#define _CRT_SECURE_NO_WARNINGS
#include "dlist.h"
#include <stdio.h>
#include <stdlib.h>
int main(){
//創(chuàng)建一個(gè)雙鏈表
pHead ph=NULL;
ph=DlistCreate();
//向鏈表中插入元素
int num;
printf("請(qǐng)輸入要插入的元素冲甘，輸入0結(jié)束：\n");
while(1){
scanf("%d",&num);
if(num==0){
break;
DlistInsert(ph,0,num);//從頭添加元素
}
}
printf("雙鏈表的長(zhǎng)度是%d\n",getLength(ph));
printFront(ph);
DlistInsert(ph,3,99);//在3位置插入新元素99
printFront(ph);
printLast(ph);
//查找元素
int val;
printf("請(qǐng)輸入要查找的元素：\n");
scanf("%d",&val);
DlistFind(ph,val);
//刪除元素
int del;
printf("請(qǐng)輸入要?jiǎng)h除的元素：\n");
scanf("%d",&del);
DlistDelete(ph,val);
printFront(ph);
//銷毀鏈表
DlistDestoty(ph);
printf("雙鏈表銷毀成功：\n 此時(shí)鏈表的長(zhǎng)度為%d\n",ph->length);
system("pause");
return 0;
}
總結(jié)
我們上方的代碼實(shí)現(xiàn)了雙鏈表的增刪改查功能幾個(gè)功能冻璃。
雙鏈表的插入陌粹、刪除操作埠通，實(shí)現(xiàn)起來(lái)比單鏈表稍微復(fù)雜一丟丟~俊性，其他操作都無(wú)較大的改動(dòng)瘫里。
雙鏈表是可以倒序遍歷的甥厦，為了測(cè)試倒序功能特笋，我們?cè)谏戏酱a中實(shí)現(xiàn)了printLast()方法久橙，實(shí)現(xiàn)從后往前打印鏈表的元素茵肃。
雙鏈表中的每個(gè)結(jié)點(diǎn)都要記錄兩個(gè)指針律适，所以空間消耗要略多一些辐烂。不過(guò)由于它良好的對(duì)稱性，是的對(duì)結(jié)點(diǎn)前后兩個(gè)結(jié)點(diǎn)操作更加靈活捂贿，也使得算法的時(shí)間效率得到了提高纠修，說(shuō)到底，就是空間換時(shí)間厂僧。
多謝關(guān)注扣草，大家一起努力~~
