单链表试验报告

1、计算机与信息技术学院综合性、设计性实验报告专业：网络工程年级/班级：大二2016-2017学年第一学期0课程名称数据结构指导教师李四学号姓名16083240XX 张三项目名称单链表的基本操作实验类型综合性/设计性实验时间2017.10.3实验地点216机房一、实验目的(1)熟悉顺序表的创建、取值、查找、插入、删除等算法，模块化程序设计方法。CPU为Pentium 4以上的计二、实验仪器或设备(1) 硬件设备：算机，内存2G以上(2) 配置软件：Microsoft Windows 7 与 VC+6.0总体设计(设计原理、设计方案及流程等)设计原理：单链表属于线性表，线性表的存储结构的特点是：用一

2、组任意存储单元存储线性 表的数据元素，这组存储单元可以是连续的，也可以是不连续的。因此，对于某 个元素来说，不仅需要存储其本身的信息，还需要存储一个指示其直接后继的信 息。设计方案：采用模块化设计的方法，设计各个程序段，最终通过主函数实现各个程序段的功 能。设计时，需要考虑用户输入非法数值，所以要在程序中写入说可以处理非法 数值的代码。设计流程：1. 引入所需的头文件；2. 定义状态值；3. 写入顺序表的各种操作的代码；写入主函数，分别调用各个函数。在调用函数时，采用if结构进行判断输四、入值是否非法，从而执行相应的程序 实验步骤(包括主要步骤、代码分析等)#include<stdio.

3、h> / EOF(=*2或 F6),NULL#in clude<stdlib.h> / srand() ,rand( ),exil (n)#in clude<malloc.h> malloc( ),alloc( )/ealloc()#in clude<!imits.h> / INT_MAX 等#in clude<sth ngh>#in clude<ctypeh>#in clude<math.h> / floor(),ceil( ),abs()#in clude<iostream.h> / cout,ci

4、n#in clude<lime.h> / clock( ),CLK_TCK,clock_t#defi ne TRUE#defi ne FALSE#defi ne OK#defi ne ERROR 0#defi ne INFEASIBLE-1#define OVERFLOW -2 typedef int Status： / Status 其值是函数结果状态代码，如 typedef int ElemType; typedef struct LNode <OK等是函数的类型ElemType data; / struct LNode *next;/ LNode/LinkList： /

5、LinkList /初始化单链表结点的数据域结点的指针域为指向结构体LNode的指针类型算法步骤：1.生成新结点作为头结点，用头指针L指向头结点。2头结点的指针域置空。Status lnilList_L(LinkList &L)L=new LNode; L->next=NULL;/生成新结点作为头结点，用头指针L指向头结点;/头结点的指针域置空return OK：/单链表的取值算法步骤：1. 用指针P指首元结点，用j做计数器初值赋为1.2. 从首元结点开始依次顺着链域next向下访问，只要指向当前结点的指针(.NULL.井且没有到达序号为i的结点，则循环执行以下操作：P指向下一结

6、点；p不为空计数器j相应加1;3.退出循坏时，如果指针p为空，或者计数器j大于i .说明指定的序号i值不合法(i大于表长 n或i小于等于0),取值失败返回ERROR否则取值成功，此时pi时，p所指的结点就是要找的第i 个结点，用参数e保存当前结点的数据域，返回0K。Status GelElenri_L(LinkList L, int i, ElemType &e) <LinkList p; intj; p=L> next;j=1； while(p&&jvi)p=p>next; +j；if(!p|j>i) return ERROR;e=p->

7、data;return OK：/单链表的按值查找算法步骤：1.用指针P指首元结点。2从首元结点开始依次顺着链域next向下查找，只要指向当前结点的指针P不为空，并且P3所指结点的数据域不等于给定值 点a3.返回P。若查找成功.P此时即为结点的地址值.若查找失败，P的值即为NULL。 泊 t LocateElem_LLinkList L,ElemT ype e)&则循环执行以下操作：P指向下一个结LinkList p; int j： p=L> next;j=1:while( P&&p->data!=e)p=p>next; j卄；if(p) return;

8、 else return 0;/单链表的插入算法步骤：1.查找结点a“并由指针P指向该结点。234生成一个新结点*S O将新结点*s的数据域置为e将新结点*s的指针域指向结点 a.。 将结点*p的指针域指向新结点*s 5Status Listlnsert_L(LinkList &L,int i.ElemType e)LinkList p=L,s; intj=O;while(p&&G<i-1)p=p>next; +j；return ERROR：s=new LNode： s->data=e： s>next=p->next： p->next

9、=s;return OK;/单链表的删除1.查找结点并由指针p指向该结点。2临时保存待删除结点 a的地址在q中，以备释放。将结点y的指针域指向a的直接后继结点。释放结点a的空间。Status LislDelete_L(Li nkList & LJ nl i)LinkList p=L,q;345intj=O;while(p->next)&&( </)p=p>next; +j；if(!p->nexl)|G>i-1) (return ERROR;q=p->next; p->next=q->next; delete q;retur

10、n OK;/单链表的输出算法步骤：1.将指针P指向L的next域。输出P指针的数据。将指针P后移。循环第2,3步，直到P指针为空(NULL)。234void ListPrint_L(LinkList L)LinkLisI p; p=L->next： do (phntf("%5d"p->data); p=p->n ext;while(p);void main()int i,n,e; LinkLisI L： if(lnitList_L(L);printfC单链表创建成功！ n");printfC请输入您要输入的数据个数n:n"); scan

11、fC'%d'&n); printf("请输入您要输入的数据：n”)；for(i=1;iv=n;i+)(scanf("%d",&e)： Listlnsert_LLj,e);printfC当前单链表的内容为：n");ListP rint_L(L)：printf("n")；printfC请输入您要插入的数据e及其位置i,使用空格键隔开 scanf("%d %d：&e,&i);if(Lisllnsert_L(LJ,e)phntfC'当前单链表的内容为：'nJ; List

12、Print_L(L);elseprintfC'i 值越界！ n");printf("n")；printf("请输入您要取的数据序号：n”); scan f(”cr,&);if(GetElem_L(LJ,e)printfC 第4位数据的值为：dnT,e);elseprintfC'i 值越界！ n")；printfC请输入要查找的数据值：n”); scanfC'%d&e)： if(!LocateElem_L(L,e)printfC 查无此值！rf);elseprintf(”数据 (:在 d 号位置 n'

13、;e,LocateElem_L(L,e);phn tf(-请输入要删除的数据的序号:n")scan fC%d &);if(LislDelete_L(LJ)printfC删除后单链表的内容为：rf);ListPri nt_L(L);elsephntfC'输入有误！ J;phn tf( Jn ”);五、结果分析与总结9Sj?*»眾的胃容为，U 141928754輪MEMM入的（位JLft用Sft93耳:耳衣的内»为|13141961287513 H 1961 7S” Any to ewtinu*结果分析：如图1所示，输入正确数据时，程序各个功能执行正常。设置输入数据个数为5,可 以输入5个数据，按回车后，可以显示我们当前单链表中的数据内容。继续输入下 一指令：输入要插入的数据及位置，使用空格键隔开，回车后，可以看到已经成功 插入。继续输入所取的数据序号，可以查找该数据的值。输入要查找的数据，可