实验名称 ：实验四 双向或循环链表的基本操作
一、实验项目名称：双向或循环链表的基本操作 二、实验目的
1）通过实验理解双向链表或循环链表的结构。 2）通过实验掌握双向链表或循环链表的基本操作。
三、实验基本原理
1、数据结构
2、算法思想
1.构思：双向循环链表的创建建立在双向链表上，所以建立双向循环表每个结点都有三个属性：数据域、上个结点、下个结点，其中第一个结点的上一个结点是最后一个结点，最后一个结点的下一个结点就是第一个结点，所以就构成了双向循环链表。 双链表的单元类型定义
Type struct DuLNode {
Elemtype data;
Struct DuLNode *prior;//建立表头结点
Struct DuLNode *next;//建立表尾结点 } DuLNode,*DuLinkList;
3、算法描述
①建立一个双链表，输入元素。由p和s两个指针来存放元素。以0判断是否结束，如果不为0 ，则继续，为0则截止。
s->data=e;
s->next=p->next; s->prior=p; p->next->prior=s; p->next=s; p=s;
②查找元素：首先判断位置是否合法(p->data!=e&& p->next!=head)若合法进行查找运算。 需要引用DuLinkList,（DuLinkList &L）输入要查找的元素的位置，判断双链表中是否有该元素，如果是则输出该元素，如果没有，则提示没有该元素。
③插入元素：判断位置是否合法(i<1||i>L.Length)，若合法进行查插入运算。需要引用DuLinkList,（DuLinkList &L）输入要插入的元素及其位置，插入数据然后输出数据。
④删除元素：判断位置是否合法(i<1||i>L.Length)，若合法进行查删除运算。输入要插入的元素及其位置，删除该数据。
本程序实现双链表的创建、查找、插入、删除、显示、菜单为主的六个函数组成。
四、主要仪器设备及耗材
电脑
运行环境：visual C++6.0
五、实验步骤
（1）打开visual C++，新建工程console application工程，新建文件C++ source file。 （2）输入自己的程序代码
（3）如果有报错则修改程序。无则组建调试
六、实验数据及处理结果 1、程序清单
#include
#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef struct DuLnode {
int data;
Struct DuLNode *prior;//建立表头结点 Struct DuLNode *next;//建立表尾结点
int L;
}DuLinkList; DuLinkList *ahead;
int DuLinkListCreate(DuLinkList &L) { DuLinkList *p,*s;
int x;
ahead=(DuLinkList*)malloc(sizeof(DuLinkList));
ahead->data=-1; ahead->next=ahead; ahead->prior=ahead;
p=ahead; L.Length=0;
printf(\请输入元素，输入0结束\\n\ scanf(\ while(x!=0) {
s=(DuLinkList*)malloc(sizeof(DuLinkList)); s->data=x; s->next=p->next; s->prior=p; p->next->prior=s; p->next=s; p=s;
scanf(\ L.Length++; }
return OK;
}
void DuLinkListDisplay(DuLinkList &L) { DuLinkList * p=ahead->next; while(p!=ahead)
{printf(\ p=p->next;
}
printf(\
}
int DuLinkListLocate(DuLinkList &L,int e) //{ DuLinkList * p=ahead->next; int i=1;
if(p==NULL)
return ERROR;
while(p->data!=e&& p->next!=ahead) {p=p->next;
i++;
查找元素 }
if(p->data==e)
printf(\查找的位置是：%d \\n\ else
printf(\并没有这个元素\\n\
return OK;
}
int DuLinkListInsert(DuLinkList &L,int i,int e) // { int j; j=0;
DuLinkList *p=ahead->next,*s;
while((p->next!=ahead)&&(j
}
if((i>0)&&(j=i-1))
{
s=(DuLinkList*)malloc(sizeof(DuLinkList)); s->data=e; s->prior=p->prior; p->prior->next=s; s->next=p; p->prior=s;
}
DuLinkListDisplay(L); return OK;
}
插入元素