双链表
双向链表
双向链表中，每个结点都有两个指针域，一个指向其后继结点，另一个指针指向其前驱结点，如图1.1(a)所示，因此，可以从某个结点开始朝两个方向遍历整个链表。
如果循环链表中每个结点都采用双向指针就构成了双向循环链表。图1.1(c)所示就是一个带头结点的双向循环链表，其尾结点的后继指针指向表的头结点，而表头结点的前驱指针指向表的尾结点。空的双向循环链表的结构如图1.1(b)所示。
双向链表中结点的类型定义如下:
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)图所示。
完整的双向循环链表的操作:查询、删除、显示、插入 C程序在VC上验证通过：
#include “stdafx.h”
#include
#include
#include
#include
#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
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();
}
淩亂°似流年
矫情吗；*
分手后的思念是犯贱
柔情只为你懂
小灰灰
还没有评论，来说两句吧...