2018.10.2 數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)---雙向鏈表的實(shí)現(xiàn)
/*
* 學(xué)習(xí)時(shí)間:2018-10-2
* 學(xué)習(xí)內(nèi)容:數(shù)據(jù)結(jié)構(gòu)之尾插法實(shí)現(xiàn)雙向鏈表,以及鏈表的增刪查改
* 學(xué)習(xí)人:田超
* QQ:770925351
* Email:770925351@qq.com
* 開發(fā)環(huán)境:Ubuntu 16.04 + CLion
* */
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
typedef struct DLNode //定義循環(huán)鏈表結(jié)構(gòu)體
{
int data;
struct DLNode *prior;
struct DLNode *next;
}DLNode;
void createDList(DLNode *&L,int a[],int n) //創(chuàng)建雙向鏈表
{
DLNode *s,*r; //s用于新建節(jié)點(diǎn),r用于跟蹤L的尾端節(jié)點(diǎn)
int i; //for循環(huán)臨時(shí)變量
L=(DLNode*)malloc(sizeof(DLNode)); //開辟循環(huán)鏈表頭結(jié)點(diǎn)空間
L->prior=NULL; //初始化頭結(jié)點(diǎn)前驅(qū)指針
L->next=NULL; //初始化頭結(jié)點(diǎn)后繼指針
r=L; //初始化r
for(i=0;i<n;i++)
{
s=(DLNode*)malloc(sizeof(DLNode)); //開辟新節(jié)點(diǎn)空間
s->data=a[i]; //將數(shù)值賦值給新節(jié)點(diǎn)的數(shù)據(jù)域
r->next=s; //將r指向的后繼變成s
s->prior=r; //將s指向的前趨設(shè)置為r
r=s; //r移位,變成鏈表的最后一個(gè)節(jié)點(diǎn)
}
r->next=NULL; //此時(shí)r為最后一個(gè)節(jié)點(diǎn),將它的后繼指針變成NULL,創(chuàng)建鏈表結(jié)束
}
void travelNode(DLNode *L)
{
DLNode *p=L->next;
while(p!=NULL)
{
printf("data=%d\n",p->data);
p=p->next;
}
}
DLNode* findNode(DLNode *L,int x) //在雙向鏈表中查找x元素
{
DLNode *p=L->next; //p為指向鏈表的指針,并初始化指向除頭節(jié)點(diǎn)第一個(gè)節(jié)點(diǎn)
while(p!=NULL) //當(dāng)p不為空時(shí)候,一直循環(huán)
{
if(p->data==x) //比較值的大小,如果相等,則找到,立即結(jié)束循環(huán)
break;
p=p->next; //沒有找到,p指向下一個(gè)節(jié)點(diǎn)
}
return p; //返回p指針,如果找到則會(huì)返回節(jié)點(diǎn)的地址,如果找不到,說明p到了最后一個(gè)節(jié)點(diǎn),最后一個(gè)節(jié)點(diǎn)的next指針是NULL
}
void insertNode_tail(DLNode *L,int x) //在雙向鏈表中插入x元素,尾插法
{
DLNode *p,*s; //s用來新建節(jié)點(diǎn),p用來尋找當(dāng)前鏈表中最后一個(gè)節(jié)點(diǎn)
p=L->next; //初始化p節(jié)點(diǎn)
while(p&&p->next!=NULL) //循環(huán)找到L的最后一個(gè)節(jié)點(diǎn),并賦值給p,在這里判斷的邏輯是:p不能為空且p的后繼指針不能為空,當(dāng)為空時(shí)候結(jié)束循環(huán),說明p是最后一個(gè)節(jié)點(diǎn)
{
p=p->next;
}
s=(DLNode*)malloc(sizeof(DLNode)); //新建節(jié)點(diǎn)
s->data=x; //將傳進(jìn)來的數(shù)據(jù)賦值給s
if(p==NULL) //如果此時(shí)鏈表為空,則插入的節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn)
{
s->prior=L; //s節(jié)點(diǎn)的前趨指向頭結(jié)點(diǎn)
s->next=p; //s節(jié)點(diǎn)的后繼指向p,也就是NULL
L->next=s; //此時(shí)s作為鏈表的第一個(gè)節(jié)點(diǎn),也就是L->next
}
else
{
s->prior=p; //將s的前趨指針指向p
s->next=p->next; //將s的后繼指針指向原先p的后繼,因?yàn)閜是最后一個(gè)節(jié)點(diǎn),所以是NULL,如果說是中間的節(jié)點(diǎn)的話,就不是NULL
p->next=s; //將p的后繼重新指向s
}
}
void insertNode_head(DLNode *L,int x) //在雙向鏈表中插入x元素,頭插法
{
DLNode *s; //s用來新建節(jié)點(diǎn)
s=(DLNode*)malloc(sizeof(DLNode)); //為s開辟空間
s->data=x; //將數(shù)據(jù)賦值給新建的節(jié)點(diǎn)s的data域
s->prior=L; //將s的前趨指針指向頭結(jié)點(diǎn)
s->next=L->next; //將s的后繼指針指向原先的第一個(gè)節(jié)點(diǎn)
if(L->next==NULL) //如果此時(shí)鏈表為空,那么s節(jié)點(diǎn)將
L->next=s;
else
{
L->next->prior=s; //將原先第一個(gè)節(jié)點(diǎn)的前趨指針指向s
L->next=s; //將頭節(jié)點(diǎn)的next指針指向s
}
}
int deleteNode(DLNode *L,int x) //在雙向鏈表中刪除節(jié)點(diǎn)
{
DLNode *p=L->next; //讓p指向除頭節(jié)點(diǎn)外的第一個(gè)節(jié)點(diǎn)
while(p!=NULL) //循環(huán)至最后一個(gè)節(jié)點(diǎn)
{
if(p->data==x) //如果找到節(jié)點(diǎn)
{
if(p->next==NULL) //如果找到的是最后一個(gè)節(jié)點(diǎn)
{
p->prior->next = p->next; //將p節(jié)點(diǎn)前趨的后繼指針指向NULL
free(p); //釋放空間
}
else
{
p->prior->next = p->next; //將p節(jié)點(diǎn)前趨的后繼指針指向p的后繼
p->next->prior = p->prior; //將p節(jié)點(diǎn)后繼的前趨指針指向p的前趨
free(p); //釋放空間
}
return TRUE; //返回真
}
p=p->next; //沒有找到將p指向下一個(gè)節(jié)點(diǎn)
}
return FALSE; //循環(huán)結(jié)束,沒有找到,返回假
}
int main()
{
int a[5]={1,2,3,4,5};
int n=5;
DLNode *L;
createDList(L,a,n);
travelNode(L);
printf("\n");
deleteNode(L,5);
travelNode(L);
printf("\n");
insertNode_tail(L,6);
travelNode(L);
printf("\n");
insertNode_head(L,7);
travelNode(L);
printf("\n");
return 0;
}
