实验四 双向链表.doc

实验名称 ：实验四 双向或循环链表的基本操作一、实验项目名称：双向或循环链表的基本操作二、实验目的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）输入要查找的元素的位置，判断双链表中是否有该元素，如果是则输出该元素，如果没有，则提示没有该元素。插入元素：判断位置是否合法(iL.Length)，若合法进行查插入运算。需要引用DuLinkList,（DuLinkList &L）输入要插入的元素及其位置，插入数据然后输出数据。删除元素：判断位置是否合法(iL.Length)，若合法进行查删除运算。输入要插入的元素及其位置，删除该数据。本程序实现双链表的创建、查找、插入、删除、显示、菜单为主的六个函数组成。四、主要仪器设备及耗材 电脑运行环境：visual C+6.05、 实验步骤（1） 打开visual C+，新建工程console application工程，新建文件C+ source file。（2） 输入自己的程序代码（3） 如果有报错则修改程序。无则组建调试六、实验数据及处理结果 1、程序清单#include#include#include#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define OK 1#define ERROR 0#define OVERFLOW -2typedef struct DuLnodeint 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(%d,&x); 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(%d,&x); L.Length+; return OK;void DuLinkListDisplay(DuLinkList &L)DuLinkList * p=ahead-next;while(p!=ahead)printf(%d ,p-data);p=p-next;printf(n);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,i); 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)&(jnext;j+;if(i0)&(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;int DuinkListDelet(DuLinkList &L,int i) /删除元素 int e,j=0; DuLinkList *p=head-next;while(p-next!=ahead)&(jnext;j+; if(i0)&(j=i)e=p-data;p-prior-next=p-next;p-next-prior=p-prior;free(p);Display_Dul(L);return OK;int scan() int a; do printf(1. 输入元素 n); printf(2. 查找 n); printf(3. 插入n); printf(4. 删除n); printf(5. 显示数据n); printf(6. 退出程序n); printf(输入你想要的操作:); scanf(%d,&a); while(a6); return (a);int main() DuLinkList L;for(;) / 无限循环 switch(scan() int e,i; case 1:DuLinkListCreate(L); break; case 2:printf(请输入你想要查找的元素：); scanf(%d,&e); DuLinklistLocate(L,e); break; case 3:printf(请输入要插入的数的位置：); scanf(%d,&i); if(iL.L) printf(输入不合法); break; printf(请输入你要插入的元素：); scanf(%d,&e); DuLinkListInsert(L,i,e); break; case 4:printf(请输入你要删除的位置:); scanf(%d,&i); if(iL.L) printf(输入不合法n); break; DuLinkListDelet(L,i); break; case 5:DuLinkListDisplay(L); break; retur