c語言 建立雙向連結清單 prior,next,C語言資料結構 雙向連結清單的建立與基本操作

C語言資料結構 雙向連結清單的建立與基本操作

雙向連結清單比單連結清單有更好的靈活性，其大部分操作與線性表相同。下面總結雙向連結清單與單連結清單之間的不同之處及我在實作過程中所遇到的問題。

1.雙向連結清單的建立

雙向連結清單在初始化時，要給首尾兩個節點配置設定記憶體空間。成功配置設定後，要将首節點的prior指針和尾節點的next指針指向NULL，這是十分關鍵的一步，因為這是之後用來判斷空表的條件。同時，當連結清單為空時，要将首節點的next指向尾節點，尾節點的prior指向首節點。

2.雙向連結清單的插入操作

由于定義雙向連結清單時指針域中多了一個prior指針，插入操作相應變得複雜，但基本操作也并不難了解。隻需記住在處理前驅和後繼指針與插入節點的關系時，應始終把握好“有序原則”，即若将插入節點與兩個已存在的節點構成三角形，則應先處理“向上”的指針，再處理“向下”的指針。下面用代碼描述其過程:

pinsert->prior=p;

pinsert->next=p->next;

p->next->prior=pinsert;

p->next=pinsert;

3.雙向連結清單的删除操作

了解了雙向連結清單的插入操作後，删除操作便十分容易了解。下面用代碼描述其過程:

p->prior->next=p->next;

p->next->prior=p->prior;

free(p);

雙向連結清單的其他操作與單連結清單類似，在此不再贅述，完整的代碼如下:

#include

#include

#include

#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;

}

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;

}

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){

visit(pmove->data);

pmove=pmove->next;

}

printf("\n");

}

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");

}

status deleteelem(dlinklist head,dlinklist tail,int pos,elemtype *data){

int i=1;

dlinklist pmove=head->next;

while(pmove&&i

pmove=pmove->next;

i++;

}

if(!pmove||i>pos){

printf("輸入資料非法\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("頭插法建立連結清單\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("尾插法建立連結清單\n");

for(i=0;i<10;i++){

//inserttail(head,tail,i);

createdlinklisttail(head,tail,i);

}

traverselist(head,tail);

printf("逆序列印連結清單");

inverse(head,tail);

}

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支援！