实验四 双向链表重点讲义

1、 实验名称 ：实验四 双向或循环链表的基本操作一、实验项目名称：双向或循环链表的基本操作二、实验目的1）通过实验理解双向链表或循环链表的结构。 2）通过实验掌握双向链表或循环链表的基本操作。三、实验基本原理 1、数据结构 2、算法思想 1.构思：双向循环链表的创建建立在双向链表上，所以建立双向循环表每个结点都有三个属性：数据域、上个结点、下个结点，其中第一个结点的上一个结点是最后一个结点，最后一个结点的下一个结点就是第一个结点，所以就构成了双向循环链表。双链表的单元类型定义Type struct DuLNode Elemtype data; Struct DuLNode *prior;/建立表

2、头结点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,（DuLinkLi

3、st &L）输入要查找的元素的位置，判断双链表中是否有该元素，如果是则输出该元素，如果没有，则提示没有该元素。插入元素：判断位置是否合法(i<1|i>L.Length)，若合法进行查插入运算。需要引用DuLinkList,（DuLinkList &L）输入要插入的元素及其位置，插入数据然后输出数据。删除元素：判断位置是否合法(i<1|i>L.Length)，若合法进行查删除运算。输入要插入的元素及其位置，删除该数据。本程序实现双链表的创建、查找、插入、删除、显示、菜单为主的六个函数组成。四、主要仪器设备及耗材 电脑运行环境：visual C+6.05、

4、实验步骤（1） 打开visual C+，新建工程console application工程，新建文件C+ source file。（2） 输入自己的程序代码（3） 如果有报错则修改程序。无则组建调试六、实验数据及处理结果 1、程序清单#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define OK 1#define ERROR 0#define OVERFLOW -2typedef struct

5、 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.Len

6、gth=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(DuLink

7、List &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->

8、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)&&(j<i-1) p=p->next;j+;if(i>0)&&(j=i-1) s=(D

9、uLinkList*)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)&&(j<i-1) /找到第i个结点p=

10、p->next;j+; if(i>0)&&(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("

11、;5. 显示数据n"); printf("6. 退出程序n"); printf("输入你想要的操作:"); scanf("%d",&a); while(a<0&&a>6); return (a);int main() DuLinkList L;for(;) / 无限循环 switch(scan() int e,i; case 1:DuLinkListCreate(L); break; case 2:printf("请输入你想要查找的元素："); scanf("

12、%d",&e); DuLinklistLocate(L,e); break; case 3:printf("请输入要插入的数的位置："); scanf("%d",&i); if(i<1|i>L.L) printf("输入不合法"); break; printf("请输入你要插入的元素："); scanf("%d",&e); DuLinkListInsert(L,i,e); break; case 4:printf("请输入你要删除的位置:"); scanf("%d",&i); if(i<1|i>L.L) printf("输入不合法n"); break; DuLinkListDelet(L,i); break; cas