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<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;
  /*这一步很关键*/ 
  (*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){
    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("输入数据非法\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);
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

# C语言数据结构  # 双向链表详解  # 双向链表实例并分析  # C语言双向链表的原理与使用操作  # C语言算法学习之双向链表详解  # C语言类的双向链表详解  # C语言中双向链表和双向循环链表详解  # C语言实现数据结构和双向链表操作  # C语言 数据结构双向链表简单实例  # C语言之双向链表详解及实例代码  # C语言实现双向链表  # C语言超详细i讲解双向链表  # 链表  # 为空  # 这是  # 要将  # 值为  # 角形  # 我在  # 第一个  # 在此  # 只需  # 数据结构  # 希望能  # 要给  # 谢谢大家  # 把握好  # 过程中  # 则应  # 不同之处  # 并不难  # 线性表 

相关文章： 建站主机选购指南：核心配置与性价比推荐解析  如何在IIS7中新建站点？详细步骤解析  建站主机无法访问？如何排查域名与服务器问题  mc皮肤壁纸制作器,苹果平板怎么设置自己想要的壁纸我的世界？  如何快速生成ASP一键建站模板并优化安全性？  网站制作大概要多少钱一个,做一个平台网站大概多少钱？  详解jQuery停止动画——stop()方法的使用  重庆网站制作公司哪家好,重庆中考招生办官方网站？  建站主机类型有哪些？如何正确选型  音响网站制作视频教程,隆霸音响官方网站？  想学网站制作怎么学,建立一个网站要花费多少？  免费ppt制作网站,有没有值得推荐的免费PPT网站？  极客网站有哪些,DoNews、36氪、爱范儿、虎嗅、雷锋网、极客公园这些互联网媒体网站有什么差异？  建站之星安装步骤有哪些常见问题？  如何快速搭建虚拟主机网站？新手必看指南  深圳网站制作案例,网页的相关名词有哪些？  江苏网站制作公司有哪些,江苏书法考级官方网站？  GML (Geography Markup Language)是什么，它如何用XML来表示地理空间信息？  建站VPS配置与SEO优化指南：关键词排名提升策略  怎么制作网站设计模板图片,有电商商品详情页面的免费模板素材网站推荐吗？  学生网站制作软件,一个12岁的学生写小说，应该去什么样的网站？  宁波免费建站如何选择可靠模板与平台？  如何在Mac上搭建Golang开发环境_使用Homebrew安装和管理Go版本  Swift中swift中的switch 语句  如何规划企业建站流程的关键步骤？  油猴 教程,油猴搜脚本为什么会网页无法显示？  建站之星各版本价格是多少？  建站168自助建站系统：快速模板定制与SEO优化指南  如何在阿里云通过域名搭建网站？  视频网站制作教程,怎么样制作优酷网的小视频？  如何在建站宝盒中设置产品搜索功能？  微信小程序 五星评分(包括半颗星评分)实例代码  建站之星如何实现PC+手机+微信网站五合一建站？  建站之星代理如何优化在线客服效率？  建站之星在线版空间：自助建站+智能模板一键生成方案  建站之星后台管理系统如何操作？  建站之星安装提示数据库无法连接如何解决？  专业的网站制作设计是什么,如何制作一个企业网站，建设网站的基本步骤有哪些？  微信小程序 input输入框控件详解及实例（多种示例）  建站主机空间推荐 高性价比配置与快速部署方案解析  北京制作网站的公司,北京铁路集团官方网站？  清单制作人网站有哪些,近日“兴风作浪的姑奶奶”引起很多人的关注这是什么事情？  Python路径拼接规范_跨平台处理说明【指导】  ,巨量百应是干嘛的？  C++中的Pimpl idiom是什么，有什么好处？（隐藏实现）  免费网站制作模板下载,除了易企秀之外还有什么H5平台可以制作H5长页面，最好是免费的？  制作网站的模板软件,网站怎么建设？  建站主机服务器选购指南：轻量应用与VPS配置解析  如何制作网站标识牌,动态网站如何制作（教程）？  ,石家庄四十八中学官网？