双向链表
最后更新于：2022-04-01 09:42:50
~~~
#include<stdio.h>
#include<malloc.h>
#include<windows.h>
typedef int elemtype;
typedef struct dnode
{
elemtype data;
struct dnode *prior;
struct dnode *next;
}dlinklist;
void createlistf(dlinklist *&L,elemtype a[],int n) //建立双链表(头插法)
{
dlinklist *s;
int i;
L=(dlinklist *)malloc(sizeof(dlinklist));
L->prior=L->next=NULL;
for(i=0;i<n;i++)
{
s=(dlinklist *)malloc(sizeof(dlinklist));
s->data=a[i];
s->next=L->next;
if(L->next!=NULL)
L->next->prior=s;
L->next=s;
s->prior=L;
}
}
void creatlistr(dlinklist *&L,elemtype a[],int n) //尾插法建表
{
dlinklist *s,*p;
int i;
L=(dlinklist *)malloc(sizeof(dlinklist));
L->prior=L->next=NULL;
p=L;
for(i=0;i<n;i++)
{
s=(dlinklist *)malloc(sizeof(dlinklist));
s->data=a[i];
s->next=p->next;
p->next=s;
s->prior=p;
p=s;
s=p->next;
}
}
void listempty(dlinklist *L) //判断是否为空
{
if(L->next!=NULL)
printf("链表不为空\n");
else
printf("链表为空\n");
}
int listlength(dlinklist *L) //求链表长度
{
dlinklist *p=L;
int i=0;
while(p!=NULL)
{
i++;
p=p->next;
}
return i-1;
}
void listinsert(dlinklist *&L) //插入元素
{
dlinklist *p=L,*s;
int i,m,a;
printf("请输入需插入元素");
scanf("%d",&a);
printf("请输入需插入元素位置");
scanf("%d",&m);
if(m<0||m>listlength(L))
printf("输入错误\n");
else
{
for(i=0;i<m-1;i++)
p=p->next;
s=(dlinklist *)malloc(sizeof(dlinklist));
s->data=a;
s->next=p->next;
s->next->prior=s;
p->next=s;
s->prior=p;
printf("插入成功\n");
}
}
void listdelete(dlinklist *&L) //删除元素
{
dlinklist *p=L,*q;
int i,m,t;
printf("请输入需删除元素位置 ");
scanf("%d",&m);
if(m<0||m>listlength(L))
printf("输入错误\n");
else
{
for(i=0;i<m-1;i++)
p=p->next;
q=p->next;
p->next=q->next;
q->next->prior=p;
t=q->data;
free(q);
printf("成功删除元素%d\n",t);
}
}
void getelem(dlinklist *L) //取值
{
dlinklist *p=L;
int i=0,m;
printf("请输入取值元素 ");
scanf("%d",&m);
while(p!=NULL)
{
if(p->data==m)
printf("取值成功 %d元素在第%d位\n",m,i);
p=p->next;
i++;
}
if(p=NULL)
printf("没有此元素\n");
}
void locateelem(dlinklist *L) //查找
{
dlinklist *p=L;
int i=0,m;
printf("请输入需查找位置 ");
scanf("%d",&m);
if(m<=0||m>listlength(L))
printf("输入错误\n");
else
{
for(;i<m;i++)
p=p->next;
printf("第%d位的元素为%d\n",m,p->data);
}
}
void destroylist(dlinklist *&L) //销毁链表
{
dlinklist *p=L,*q;
char m;
getchar();
printf("确认要销毁链表请输入y否则不销毁 请输入:");
scanf("%c",&m);
if(m=='y')
{
q=p->next;
while(q!=NULL)
{
free(p);
p=q;
q=p->next;
}
free(p);
printf("链表已销毁\n");
exit(0);
}
printf("链表未销毁\n");
}
void displist(dlinklist *L) //输出双链表
{
dlinklist *s;
s=L->next;
while(s!=NULL)
{
printf(" %d",s->data);
s=s->next;
}
printf("\n");
}
void main()
{
printf(" ****************欢迎使用双链表基本运算系统****************\n");
printf(" ****************如有问题欢迎和我联系*****************\n");
dlinklist *p;
int a[5],i,m,t;
printf("请选择建表方式 1用头插法建表，2用尾插法建表 ");
scanf("%d",&t);
printf("请输入5个数\n");
for(i=0;i<5;i++)
scanf("%d",&a[i]);
if(t==1)
createlistf(p,a,5);
else if(t==2)
creatlistr(p,a,5);
else
printf("输入错误!");
printf("双链表建立完毕\n");
while(1)
{
printf("请选择:");
printf(" 1.输出链表\n");
printf(" 2.判断线性表(双链表)是否为空\n");
printf(" 3.求线性表(双链表)的长度\n");
printf(" 4.从线性表(双链表)中取值\n");
printf(" 5.在线性表(双链表)中查找元素\n");
printf(" 6.插入元素\n");
printf(" 7.删除元素\n");
printf(" 8.销毁链表\n");
printf(" 9.退出\n");
scanf("%d",&m);
switch(m)
{ case 1:displist(p);break;
case 2:listempty(p);break;
case 3: printf("链表长为:%d\n",listlength(p));break;
case 4:getelem(p);break;
case 5:locateelem(p);break;
case 6:listinsert(p);break;
case 7:listdelete(p);break;
case 8:destroylist(p);break;
case 9:exit(0);
default:printf("输入错误,请重新输入\n");
}
}
}
~~~