单链表实验报告
————————————————————————————————作者:————————————————————————————————日期:
计算机与信息技术学院综合性、设计性实验报告
专业:网络工程年级/班级:大二 2016—2017学年第一学期
课程名称数据结构指导教师李四
学号姓名16083240XX 张三
项目名称单链表的基本操作实验类型综合性/设计性实验时间2017.10.3 实验地点216机房
一、实验目的
(1)熟悉顺序表的创建、取值、查找、插入、删除等算法,模块化程序设计方法。
二、实验仪器或设备
(1)硬件设备:CPU为Pentium 4以上的计算机,内存2G以上
(2)配置软件:Microsoft Windows 7与VC++6.0
三、总体设计(设计原理、设计方案及流程等)
设计原理:
单链表属于线性表,线性表的存储结构的特点是:用一组任意存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。因此,对于某个元素来说,不仅需要存储其本身的信息,还需要存储一个指示其直接后继的信息。
设计方案:
采用模块化设计的方法,设计各个程序段,最终通过主函数实现各个程序段的功能。设计时,需要考虑用户输入非法数值,所以要在程序中写入说可以处理非法数值的代码。
设计流程:
1.引入所需的头文件;
2.定义状态值;
3.写入顺序表的各种操作的代码;
写入主函数,分别调用各个函数。在调用函数时,采用if结构进行判断输入值是否非法,从而执行相应的程序
四、实验步骤(包括主要步骤、代码分析等)
#include<stdio.h>// EOF(=^Z或F6),NULL
#include<stdlib.h> // srand(),rand(),exit(n)
#include<malloc.h> // malloc( ),alloc( ),realloc()等
#include
#include
#include #include #include<iostream.h> // cout,cin #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #defineINFEASIBLE -1 #define OVERFLOW -2 typedef int Status; // Status是函数的类型, //其值是函数结果状态代码,如OK等 typedef int ElemType; typedef struct LNode { ElemType data; //结点的数据域 struct LNode *next; //结点的指针域 }LNode,*LinkList; //LinkList为指向结构体LNode的指针类型//初始化单链表 算法步骤: 1.生成新结点作为头结点,用头指针L指向头结点。 2.头结点的指针域置空。 Status InitList_L(LinkList &L) { ?L=new LNode;?//生成新结点作为头结点,用头指针L指向头结点; L->next=NULL; ?//头结点的指针域置空 return OK; } //单链表的取值 算法步骤: 1.用指针P指首元结点,用j做计数器初值赋为1. 2.从首元结点开始依次顺着链域next向下访问,只要指向当前结点的指针p不为空 (NULL),并且没有到达序号为i的结点,则循环执行以下操作: P指向下一结点; 计数器j相应加1; 3.退出循环时,如果指针p为空,或者计数器j大于i,说明指定的序号i值不合法(i 大于表长n或i小于等于0),取值失败返回ERROR,否则取值成功,此时j=i时,p所指的结点就是要找的第i个结点,用参数e保存当前结点的数据域,返回OK。 Status GetElem_L(LinkList L, inti,ElemType &e) { ?LinkList p; ?int j; ?p=L->next; ?j=1; ?while(p&&j<i) { ?p=p->next; ?++j; } ?if(!p||j>i) return ERROR; ?e=p->data; ?returnOK; } //单链表的按值查找 算法步骤: 1.用指针p指首元结点。 2.从首元结点开始依次顺着链域next向下查找,只要指向当前结点的指针p不为空, 并且p所指结点的数据域不等于给定值e,则循环执行以下操作:p指向下一个结点。 3.返回p。若查找成功,p此时即为结点的地址值,若查找失败,p的值即为NULL。int LocateElem_L(LinkList L,ElemType e) { ?LinkListp; ?int j; p=L->next; j=1; while(p&&p->data!=e) ?{ ?p=p->next; j++; } ?if(p) return j; ?else return 0; } //单链表的插入 算法步骤: 1.查找结点ai-1并由指针p指向该结点。 2.生成一个新结点*s。 3.将新结点*s的数据域置为e。 4.将新结点*s的指针域指向结点ai。 5.将结点*p的指针域指向新结点*s。 Status ListInsert_L(LinkList &L,int i,ElemType e) { ?LinkList p=L,s; int j=0; ?while(p&&(j { ??p=p->next; ?++j; ?} ?if(!p||j>i-1) { return ERROR; ?} ?s=new LNode; s->data=e; ?s->next=p->next; p->next=s; ?returnOK; } //单链表的删除 1.查找结点ai-1并由指针p指向该结点。 2.临时保存待删除结点a i的地址在q中,以备释放。 3.将结点*p的指针域指向a i的直接后继结点。 4.释放结点ai的空间。 Status ListDelete_L(LinkList &L,int i) { LinkList p=L,q; ?int j=0; while((p->next)&&(j<i-1)) { p=p->next; ++j; } if((!p->next)||(j>i-1)) { ??return ERROR; } q=p->next; ?p->next=q->next; delete q; return OK; } //单链表的输出 算法步骤: 1.将指针p指向L的next域。 2.输出p指针的数据。 3.将指针p后移。 4.循环第2,3步,直到p指针为空(NULL)。 void ListPrint_L(LinkList L) { ?LinkList p; p=L->next; ?do ?{ ??printf("%5d",p->data); ?p=p->next; }while(p); } void main() { ?int i,n,e; LinkListL; if(InitList_L(L)); printf("单链表创建成功!\n"); printf("请输入您要输入的数据个数n:\n"); scanf("%d",&n); printf("请输入您要输入的数据:\n"); ?for(i=1;i<=n;i++) { scanf("%d",&e); ListInsert_L(L,i,e); ?} ?printf("当前单链表的内容为:\n"); ListPrint_L(L); ?printf("\n"); printf("请输入您要插入的数据e及其位置i,使用空格键隔开:\n");?scanf("%d %d",&e,&i); ?if(ListInsert_L(L,i,e)) ?{ ?printf("当前单链表的内容为:\n"); ListPrint_L(L); } ?else { ?printf("i值越界!\n"); }? printf("\n"); ?printf("请输入您要取的数据序号:\n"); ?scanf("%d",&i); if(GetElem_L(L,i,e)) { ?printf("第%d位数据的值为:%d\n",i,e); } else { ??printf("i值越界!\n"); } ?printf("请输入要查找的数据值:\n"); ?scanf("%d",&e); if(!LocateElem_L(L,e)) ?{ printf("查无此值!\n"); } ?else ?{ printf("数据%d在%d号位置\n",e,LocateElem_L(L,e));??} printf("请输入要删除的数据的序号:\n"); ?scanf("%d",&i); if(ListDelete_L(L,i)) ?{ ??printf("删除后单链表的内容为:\n"); ??ListPrint_L(L); } else { ?printf("输入有误!"); ?} ?printf("\n"); } 五、结果分析与总结 图1 结果分析: 如图1所示,输入正确数据时,程序各个功能执行正常。设置输入数据个数为5,可以输入5个数据,按回车后,可以显示我们当前单链表中的数据内容。继续输入下一指令:输入要插入的数据及位置,使用空格键隔开,回车后,可以看到已经成功插入。继续输入所取的数据序号,可以查找该数据的值。输入要查找的数据,可以返回该数据的位置。输入要删除的数据,可以返回删除该元素后的单链表的内容。 总结: 在单链表中,对数据元素a 来说,除了存储其本身的信息之外,还需存储一个指 i 示其直接后继的信息。这两部分信息组成数据元素a 的存储映像,称为结点。它 i 包括两个域;其中存储数据元素的域称为数据域;存储直接后继的域称为指针域。 教师签名: 年月日