实验四 双向链表.docx

实验名称 ：实验四 双向或循环链表的基本操作一、实验项目名称：双向或循环链表的基本操作二、实验目的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）输入要查找的元素的位置，判断双链表中是否有该元素，如果是则输出该元素，如果没有，则提示没有该元素。③插入元素：判断位置是否合法(i1||iL.Length)，若合法进行查插入运算。需要引用DuLinkList,（DuLinkList L）输入要插入的元素及其位置，插入数据然后输出数据。④删除元素：判断位置是否合法(i1||iL.Length)，若合法进行查删除运算。输入要插入的元素及其位置，删除该数据。本程序实现双链表的创建、查找、插入、删除、显示、菜单为主的六个函数组成。四、主要仪器设备及耗材电脑运行环境：visual C++6.0实验步骤打开visual C++，新建工程console application工程，新建文件C++ source file。输入自己的程序代码如果有报错则修改程序。无则组建调试六、实验数据及处理结果 1、程序清单#includestdio.h#includemalloc.h#includestdlib.h#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define OK 1#define ERROR 0#define OVERFLOW -2typedef 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(%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)