数据结构实验报告
二．程序设计相关信息
（1）实验题目：编写一个程序algo2-3.cpp，实现双链表的各种基本运算，并在此基础上设计一个主程序完成如下功能：
1.初始化双链表h；
2.依次采用尾插法插入a，b，c，d，e元素；
3.输出双链表h；
4.输出双链表h长度；
5.输出双链表h是否为空；
6.判断双链表h的第3个元素；
7.输出元素‘a’的位置；
8.在第4个元素位置上插入‘f’元素；
9.输出双链表h；
10.删除L的第3个元素；
11.输出双链表h；
12.释放双链表h。

（2）实验目的：熟悉双链表的基本操作并掌握尾插法建表。

（3）算法描述或流程图
(4)源代码
#include<stdlib.h> #include<stdio.h>
typedef struct DNode
{ char data;
struct DNode *next;
struct DNode *prior;
}DNode,DLinkList;
void initlist(DLinkList *&h) { h=(DLinkList*)malloc(sizeof(DLinkList)) ;
h->next=NULL;
h->prior=NULL;
}
void destroylist(DLinkList *&h)
{ DLinkList *p=h,*q=p->next;
while(q!=NULL)
{free(p);
p=q;
q=p->next;
}
free(p);
}
int getelem(DLinkList *h,int i,char &e)
{int j=0;
DLinkList *p=h;
while(j<i&&p!=NULL)
{j++;
p=p->next;
}
if(p==NULL)
return 0; else
{ e=p->data;
return 1;
}
}
int listempty(DLinkList *h)
{ return(h->next==NULL&&h->prior==NULL);
}
int listlength(DLinkList *h)
{ DLinkList *p=h;int n=0;
while(p->next!=NULL)
{n++;
p=p->next;
}
return (n);
}
void displist(DLinkList *h)
{ DLinkList *p=h->next;
while(p!=NULL)
{printf("%c ",p->data);
p=p->next;
}
printf("\n");
}
int locateelem(DLinkList *h,char e)
{ DLinkList *p=h->next;
int i=1;
while(p!=NULL&&p->data!=e)
{p=p->next;
i++;
}
if(p==NULL)
return 0;
else
return i;
}
int listinsert(DLinkList *&h,int i,char e) {int j=0;
DLinkList *p=h,*s;
while(j<i-1&&p!=NULL)
{j++;
p=p->next;
}
if(p==NULL)
return 0;
else
{s=(DLinkList*)malloc(sizeof(DLinkList)); s->data=e;
s->next=p->next;
if(p->next!=NULL) p->next->prior=s;
s->prior=p;
p->next=s;
}
return 1;
}
int listdelete(DLinkList*&h,int i)
{int j=0;
DLinkList *p=h,*q;
while(j<i-1&&p!=NULL)
{j++;
p=p->next;
}
if(p==NULL)
return 0;
else
{q=p->next;
if(q==NULL) return 0;
p->next=q->next;
if(p->next!=NULL) p->next->prior=p;
free(q);
return 1;
}
}
void main()
{DLinkList *h,*s,*r;int i;char e;
initlist(h);
r=h;
for(i='a';i<'f';i++)
{s=(DLinkList*)malloc(sizeof(DLinkList));
s->data=i;
r->next=s;s->prior=r;
r=s;
}
r->next=NULL;
printf("输出双链表h:");
displist(h);
listlength(h);
printf("双链表的长度为%d\n",listlength(h));
listempty(h);
printf("双链表是否为空，1表示是，0表示否：%d\n",listempty(h)) ; getelem(h,3,e);
printf("输出双链表的第三个元素：%c\n",e);
locateelem(h,'a');
printf("a的位置为%d\n",locateelem(h,'a'));
listinsert(h,4,'f');
printf("输出插入后的双链表h:");
displist(h);
listdelete(h,3);
printf("输出删除后的双链表h:");
displist(h);
destroylist(h);
}
（5）实验结果：。