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讲解双向链表  # 链表  # 为空  # 这是  # 要将  # 值为  # 角形  # 我在  # 第一个  # 在此  # 只需  # 数据结构  # 希望能  # 要给  # 谢谢大家  # 把握好  # 过程中  # 则应  # 不同之处  # 并不难  # 线性表 

相关文章： 如何在阿里云虚拟机上搭建网站？步骤解析与避坑指南  定制建站流程步骤详解：一站式方案设计与开发指南  香港服务器WordPress建站指南：SEO优化与高效部署策略  整蛊网站制作软件,手机不停的收到各种网站的验证码短信,是手机病毒还是人为恶搞?有这种手机病毒吗？  建站之星客服服务时间及联系方式如何？  网站制作专业公司有哪些,如何制作一个企业网站，建设网站的基本步骤有哪些？  浅析上传头像示例及其注意事项  如何快速搭建高效WAP手机网站吸引移动用户？  C#如何在一个XML文件中查找并替换文本内容  如何快速打造个性化非模板自助建站？  专业网站设计制作公司,如何制作一个企业网站，建设网站的基本步骤有哪些？  如何选择适配移动端的WAP自助建站平台？  如何高效生成建站之星成品网站源码？  建站之星在线客服如何快速接入解答？  南平网站制作公司,2025年南平市事业单位报名时间？  建站之星伪静态规则如何设置？  开源网站制作软件,开源网站什么意思？  如何用已有域名快速搭建网站？  ,网站推广常用方法？  如何挑选优质建站一级代理提升网站排名？  如何通过商城免费建站系统源码自定义网站主题？  赚钱网站制作软件,建一个网站怎样才能赚钱?是如何盈利的？  宝盒自助建站智能生成技巧：SEO优化与关键词设置指南  如何快速登录WAP自助建站平台？  相亲简历制作网站推荐大全,新相亲大会主持人小萍萍资料？  威客平台建站流程解析：高效搭建教程与设计优化方案  网站制作免费,什么网站能看正片电影？  英语简历制作免费网站推荐,如何将简历翻译成英文？  建站之星Pro快速搭建教程：模板选择与功能配置指南  北京营销型网站制作公司,可以用python做一个营销推广网站吗？  如何通过.red域名打造高辨识度品牌网站？  如何高效利用200m空间完成建站？  教程网站设计制作软件,怎么创建自己的一个网站？  JS中使用new Date(str)创建时间对象不兼容firefox和ie的解决方法(两种)  如何通过虚拟主机快速完成网站搭建？  红河网站制作公司,红河事业单位身份证如何上传？  极客网站有哪些,DoNews、36氪、爱范儿、虎嗅、雷锋网、极客公园这些互联网媒体网站有什么差异？  巅云智能建站系统：可视化拖拽+多端适配+免费模板一键生成  如何在搬瓦工VPS快速搭建网站？  商务网站制作工程师,从哪几个方面把握电子商务网站主页和页面的特色设计？  建站主机无法访问？如何排查域名与服务器问题  电影网站制作价格表,那些提供免费电影的网站，他们是怎么盈利的？  模具网站制作流程,如何找模具客户？  GML (Geography Markup Language)是什么，它如何用XML来表示地理空间信息？  如何高效配置香港服务器实现快速建站？  微信小程序制作网站有哪些,微信小程序需要做网站吗？  建站之星各版本价格是多少？  如何在Golang中指定模块版本_使用go.mod控制版本号  如何用腾讯建站主机快速创建免费网站？  内部网站制作流程,如何建立公司内部网站？