~~~
#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");
}
}
}
~~~
