這篇文章給大家介紹C語言中怎么建立一個雙向鏈表，內(nèi)容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

創(chuàng)新互聯(lián)公司是一家專注于網(wǎng)站制作、網(wǎng)站設(shè)計與策劃設(shè)計,赤坎網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)公司做網(wǎng)站,專注于網(wǎng)站建設(shè)十載,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:赤坎等地區(qū)。赤坎做網(wǎng)站價格咨詢:028-86922220

C語言數(shù)據(jù)結(jié)構(gòu) 雙向鏈表的建立與基本操作

1.雙向鏈表的建立

雙向鏈表在初始化時，要給首尾兩個節(jié)點分配內(nèi)存空間。成功分配后，要將首節(jié)點的prior指針和尾節(jié)點的next指針指向NULL，這是十分關(guān)鍵的一步，因為這是之后用來判斷空表的條件。同時，當鏈表為空時，要將首節(jié)點的next指向尾節(jié)點，尾節(jié)點的prior指向首節(jié)點。

2.雙向鏈表的插入操作

由于定義雙向鏈表時指針域中多了一個prior指針，插入操作相應(yīng)變得復(fù)雜，但基本操作也并不難理解。只需記住在處理前驅(qū)和后繼指針與插入節(jié)點的關(guān)系時，應(yīng)始終把握好“有序原則”，即若將插入節(jié)點與兩個已存在的節(jié)點構(gòu)成三角形，則應(yīng)先處理“向上”的指針，再處理“向下”的指針。下面用代碼描述其過程:

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<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;
  /*鏈表為空時讓頭指向尾*/
  (*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ù)據(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("鏈表為空\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);
}

關(guān)于C語言中怎么建立一個雙向鏈表就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。

本文標題：C語言中怎么建立一個雙向鏈表
轉(zhuǎn)載來源：http://aaarwkj.com/article28/psoecp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、虛擬主機、網(wǎng)站內(nèi)鏈、手機網(wǎng)站建設(shè)、網(wǎng)站改版、網(wǎng)站維護

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)