双链表C++实验报告

《程序设计实践》报告

一、题目

1. 实现循环双链表各种基本运算的算法，完成如下功能：

(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) 删除h的第3个元素； (11) 输出循环双链表h； (12) 释放循环双链表h。

二、问题分析及求解基本思路

这是一个双链表的创建、初始化、插入元素、删除元素、输出等基本操作的函数编写。想到可以用结构体来定义双链表节点（包含指针域和数据域），然后按功能依次编写函数，最后在主函数中调用就行了。

三、问题求解的整体框架结构

第一定义双链表结构，第二部分就是在主函数外部定义那些基本操作的函数，第三部分就是主函数及里面的调用。 四、主要算法

在主函数外编写以下函数：void InitList(DLinkList *&L)//初始化双循环链表 {

L=(DLinkList *)malloc(sizeof(DLinkList)); L->prior=L->next=NULL; }；

void DestroyList(DLinkList *&L)//释放双循环链表{ DLinkList *p=L,*q=p->next; while(q!=NULL)

{

free(p); p=q;

q=q->next; }

free(p); }；

int IsEmpty(DLinkList *L)//判断它是否为空{ return(L->next==NULL); }

int ListLength(DLinkList *L)//求双循环链表的长度 {

DLinkList *p=L; int i=0;

while(p->next!=NULL) { i++;

p=p->next; }

return(i); }；

int ListLength(DLinkList *L)//求双循环链表的长度{ DLinkList *p=L->next; while(p!=NULL) {

cout<data; p=p->next; }

cout<

void DispList(DLinkList *L)//输出双循环链表{ int j=0;

DLinkList *p=L;

while(j

p=p->next; }

if(p==NULL) return 0; else

e=p->data; return 1; }；

int GetElem(DLinkList *L,int i,ElemType &e)//获取位置i的元素{ int n=1;

DLinkList *p=L->next;

while(p!=NULL &&p->data!=e) { n++;

p=p->next; }

if(p==NULL) return 0; else

return n; }；

int ListInsert(DLinkList *&L,int i,ElemType e)//在位置i插入某元素{ int j=0;

DLinkList *p=L,*s;

while(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 *&L,int i,ElemType &e)//删除第i个元素，用e返回该其值{ int j=0;

DLinkList *p=L,*q;

while(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; delete(q); return 1; } }

，然后就在主函数中调用即可。

五、测试

六、总结

完成效果挺满意的，基本达到题目要求。有点不就是容量不够大。