双链表

客官°小女子只卖身不卖艺 2022-07-16 04:59 294阅读 0赞

双向链表  
  
双向链表中，每个结点都有两个指针域，一个指向其后继结点，另一个指针指向其前驱结点，如图1.1(a)所示，因此，可以从某个结点开始朝两个方向遍历整个链表。  
  
如果循环链表中每个结点都采用双向指针就构成了双向循环链表。图1.1(c)所示就是一个带头结点的双向循环链表，其尾结点的后继指针指向表的头结点，而表头结点的前驱指针指向表的尾结点。空的双向循环链表的结构如图1.1(b)所示。  
  
[![双链表][65380c30g73b4e51761f4_690]][65380c30g73b4e51761f4_690 1]  
  
  
双向链表中结点的类型定义如下:  
  
typedef int datatype;  
  
typedef struct node \*ptNode;  
  
struct note\{                              
datatype data;  
ptNode proir,next;  
\};  
  
双链表是一种对称的结构，既有向前链又有向后链，这就使得双链表的前插和后插及自身删除操作都很方便，只需要修改几个结点的指针域，而不必进行大量的数据交换或遍历操作。下面给出双向链表的插入和删除运算的算法。  
  
1 双向链表的前插运算  
  
在双链表中某个给定的结点P之前插入一个新结点S，其操作步骤如下：  
  
1）。将结点S的后继指向P本身；  
2）。将结点S的前驱指向结点P的前驱所指向的结点；  
3）。将结点P的前驱结点的后继修改为指向新结点S；  
4）。将结点P的前驱修改为指向结点S本身；  
  
插入新结点的过程如图1.2 (a)图所示。  
  
双链表中在结点P之前插入一个新结点S的算法如下：  
  
ptNode Insert\_before(ptNode head,ptNode p, int x)  
\{  
ptNode s;  
s=(ptNode)malloc(sizeof(node));//建立新结点  
s->data=x;//将x的值赋给s->data  
  s->next=p;//1)将新结点S的后继指向结点P  
s->prior=p->prior;//2)将新结点S的前驱指向原结点P的前驱  
p->prior->next=s;//3)原结点P前驱结点的后继指向新结点S  
p->prior=s;//4)原结点P的前驱指向新结点S  
return(head);//返回带头结点双链表的头指针  
\}  
  
2 双向链表的后插运算  
  
假设双链表中结点P的后继结点为Q，在结点P之后插入一个新结点S，其操作步骤如下：  
  
1）。将结点S的前驱指向P本身；  
2）。将结点S的后继指向结点P所指向的后继结点；  
3）。将结点P的后继结点Q的前驱结点修改为新结点S本身；  
4）。将结点P的后继结点修改为结点S本身；  
  
插入新结点的过程如图1.2 (b)图所示。  
双链表中在结点P之后插入一个新结点S的算法如下：  
  
ptNode Insert\_after(ptNode head,ptNode p, int x)  
\{  
ptNode s;  
s=(ptNode)malloc(sizeof(node));//建立新结点  
s->data=x;//将x的值赋给s->data  
  s->next=p->next;//1)将新结点S的后继指向结点P的后继  
s->prior=p;//2)将新结点S的前驱指向原结点P  
p->next->prior=s;//3)原结点P的后继结点的前驱指向新结点S  
p->next=s;//4)原结点P的后继指向新结点S  
return(head);//返回带头结点双链表的头指针  
\}  
  
3 双向链表的自身删除运算  
  
假设双链表中某给定结点P的前驱结点为Q,其后继结点为S,则双链表中删除结点P的步骤如下:  
  
1）。将结点P的前驱结点Q的后继结点指向结点P的后继结点S；  
2）。将结点P的后继结点S的前驱结点指向结点Q；  
  
插入新结点的过程如图1.2 (c)图所示。  
在双链表中删除某个结点P自身的算法如下:  
  
ptNode delete\_node(ptNode head,ptNode p)  
\{  
if(p!=NULL)  
\{  
p->prior->next=p->next;  
p->next->prior=p->prior;  
free(p);  
return(head);  
\}  
else  
\{  
return(NULL);  
\}  
\}  
  
由此可见，自身删除前后被删除的指针并没有改变，只是它后一个结点的向前指针和前一个结点的向后指针发生了变化，不再指向此结点。  
  
这三种运算过程中，指针的变化情况分别如1.2 (a)、(b)、(c)图所示。  
[![双链表][65380c30gd342f73b0109_690] ][65380c30gd342f73b0109_690_]  
  
[![双链表][65380c30g85380c2ccbf2_690]][65380c30g85380c2ccbf2_690 1]

[![双链表][65380c30g853827b54089_690]][65380c30g853827b54089_690 1]图1.2双向循环链表的前插、后插和自身删除操作示意图

完整的双向循环链表的操作:查询、删除、显示、插入 C程序在VC上验证通过：  
  
  
\#include "stdafx.h"  
\#include <stdio.h>  
\#include <stdlib.h>  
\#include <string.h>  
\#include <conio.h>  
\#define N 10  
typedef struct node \*ptNode;  
struct node\{  
char name\[20\];  
ptNode prior,next;  
\};  
  
  
  
ptNode Creat(int n)  
\{  
ptNode head,ptr,newnode;  
int i;  
if((head=(ptNode)malloc(sizeof(node))) == NULL)  
\{  
 printf("分配内存失败!\\n");  
 exit(0);  
\}  
strcpy(head->name,"head");  
//head->name\[0\] = '\\0';//头结点初始化  
head->prior = NULL;  
head->next = NULL;  
ptr = head;  
for(i=0; i<n; i++)  
\{  
 if((newnode=(ptNode) malloc(sizeof(node))) == NULL)  
 \{  
  printf("cannot find space!\\n");  
  exit(0);  
 \}  
 ptr->next= newnode;//连接新结点  
 printf("Please input the %d man's name: ",i+1);  
 scanf("%s",newnode->name);  
 newnode->prior = ptr;//定义newnode的连接关系  
 newnode->next = NULL;  
 ptr = newnode;  
\}//end for  
head->prior = newnode;  
ptr->next = head;  
return(head);  
\}  
  
  
ptNode Search(ptNode head,char \*pEle)  
\{  
ptNode ptr;  
char \*pTemp;  
ptr = head->next;  
while(ptr != head)//以是否回到头结点为结束条件  
\{  
 pTemp = ptr->name;//pTemp暂存结点的名字地址  
 if(strcmp(pTemp,pEle) == 0)  
 \{  
  return(ptr);  
 \}  
 else  
 \{  
  ptr = ptr->next;//指向下一结点  
 \}  
\}  
printf("查找不到数据!\\n");  
return NULL;  
\}  
//在选定名字前插入  
void Insert\_before(ptNode head,char \*priorEle,char \*insertEle)  
\{  
ptNode ptr,newnode;  
if((ptr=Search(head,priorEle)) ==NULL)  
\{  
 printf("Can't find the data to insert!\\n");  
 exit(0);  
\}  
if((newnode=(ptNode)malloc(sizeof(node))) == NULL)  
\{  
 printf("分配内存失败!\\n");  
 exit(0);  
\}  
strcpy(newnode->name,insertEle);//给新结点加载值  
newnode->prior = ptr->prior;//前指针指向前结点,先处理以新结点为中心前后关系  
newnode->next = ptr;//新结点后指针指向定位结点  
(ptr->prior)->next = newnode;//前结点的由指针指向新结点  
ptr->prior = newnode;  
\}  
  
//在选定名字后插入  
void Insert\_after(ptNode head,char \*p,char \*insertEle)  
\{  
ptNode ptr,newnode;  
if((ptr=Search(head,p)) ==NULL)  
\{  
 printf("Can't find the data to insert!\\n");  
 exit(0);  
\}  
if((newnode=(ptNode)malloc(sizeof(node))) == NULL)  
\{  
 printf("分配内存失败!\\n");  
 exit(0);  
\}  
strcpy(newnode->name,insertEle);//给新结点加载值  
newnode->prior=ptr;  
newnode->next=ptr->next;  
ptr->next->prior=newnode;  
ptr->next=newnode;  
\}  
  
void Print(ptNode head)  
\{  
ptNode ptr;  
ptr = head->next;  
//printf("\\n正向循环双链表为:\\n");  
while(ptr != head)  
//while(ptr != NULL)  
\{  
 printf("%s ",ptr->name);  
 ptr = ptr->next;  
\}  
printf("\\n");  
\}  
void opposite(ptNode head)//反向输出  
\{  
ptNode ptr;  
ptr=head->next;  
while(ptr->next!=head)  
  ptr=ptr->next;  
//printf("\\n反向循环双链表为:\\n");  
while(ptr!=head)  
\{  
  printf("%s ",ptr->name);  
  ptr=ptr->prior;  
\}  
printf("\\n");  
\}  
  
void Delete(ptNode ptr)  
\{  
(ptr->next)->prior = ptr->prior;//(ptr->next)->prior下一结点的左指针被赋前指针  
(ptr->prior)->next = ptr->next;  
free (ptr);  
\}  
  
  
  
void main(void)  
\{  
int number;  
char studName\[20\];  
char insertName\[20\];  
ptNode head,searchpoint;  
int flag=1;  
char j;  
//number = N;  
puts("输入双链表的最大结点数:");  
scanf("%d",&number);  
head = Creat(number);  
Print(head);  
opposite(head);  
while(flag)  
\{ printf("请选择:\\n");  
printf("1.显示所有元素\\n");  
printf("2.删除一个元素\\n");  
printf("3.元素前插入一个元素\\n");  
  printf("4.元素后插入一个元素\\n");  
printf("5.退出程序\\n");  
scanf(" %c",&j);  
switch(j)  
  \{  
 case '1':  
  printf("\\n正向循环双链表为:\\n");  
  Print(head);  
  printf("\\n反向循环双链表为:\\n");  
  opposite(head);  
  break;  
 case '2':  
  printf("\\n输入要删除的数据:\\n");  
  scanf("%s",studName);  
  searchpoint = Search(head,studName);  
  Delete(searchpoint);  
  printf("\\n删除后的链表为:\\n");  
  Print(head);  
   break;  
 case '3':  
  printf("在双链表中指定一个元素的名字和要插入的数据(如aa bb):\\n");  
  //scanf("%s",studName);  
  //printf("输入想要插入的数据:\\n");  
  scanf("%s%s",studName,insertName);  
  Insert\_before(head,studName,insertName);  
  Print(head);  
   break;  
 case '4':  
  printf("在双链表中指定一个元素的名字和要插入的数据(如aa bb):\\n");  
  //scanf("%s",studName);  
  //printf("输入想要插入的数据:\\n");  
  scanf("%s%s",studName,insertName);  
  Insert\_after(head,studName,insertName);  
  Print(head);  
   break;  
 default:  
   flag=0;  
   printf("程序结束，按任意键退出!\\n");  
  \}  
\}  
getch();  
\}

[65380c30g73b4e51761f4_690]: http://s5.sinaimg.cn/middle/65380c30g73b4e51761f4&690
[65380c30g73b4e51761f4_690 1]: /images/20220716/ba3cbf23d9ae4ce5bfbd42d922afbdf4.png
[65380c30gd342f73b0109_690]: http://s10.sinaimg.cn/middle/65380c30gd342f73b0109&690
[65380c30gd342f73b0109_690_]: /images/20220716/a1fa121ac52b496e8f3029f805167fdf.png
[65380c30g85380c2ccbf2_690]: http://s3.sinaimg.cn/middle/65380c30g85380c2ccbf2&690
[65380c30g85380c2ccbf2_690 1]: /images/20220716/b02206a358a341eebf72f5a5a0867374.png
[65380c30g853827b54089_690]: http://s10.sinaimg.cn/middle/65380c30g853827b54089&690
[65380c30g853827b54089_690 1]: /images/20220716/94e22cad8ad5446c860577b3c00ef9fe.png