单链表实验报告

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

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

3、h> / EOF(二 AZ或 F6),NULL#in clude<stdlib.h> / sran d( ) ,ran d( ),exit (n)#in clude<malloc.h> / malloc( ),alloc( ),realloc()等#in clude<limits.h> / INT_MAX等#in cludevstri n g.h>#in clude<ctype.h>#in clude<math.h> / floor(),ceil( ),abs()#in clude<iostream.h> /

4、cout,ci n#in clude<time.h> / clock( ),CLK_TCK,clock_t#defi ne TRUE1#defi ne FALSE0#defi ne OK1#defi ne ERROR 0#defi ne INFEASIBLE -1是函数的类型#define OVERFLOW -2 typedef int Status; / Status/ 其值是函数结果状态代码，如0K 等typedef int ElemType; typedef struct LNode ElemType data;/struct LNode *next;结点的数据域/ LNod

5、e,*LinkList; /LinkList /结点的指针域为指向结构体 LNode 的指针类型算法步骤：1. 生成新结点作为头结点，用头指针 L 指向头结点2. 头结点的指针域置空。/ 生成新结点作为头结点，用头指针 L 指向头结点；/ 头结点的指针域置空Status InitList_L(LinkList &L) L=new LNode;L->next=NULL;return 0K; / 单链表的取值算法步骤：1. 用指针 P 指首元结点，用 j 做计数器初值赋为 1.2. 从首元结点开始依次顺着链域 next 向下访问，只要指向当前结点的指针 p 不为空 (NULL并且没有

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

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

8、;&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<i-1)p=p->nex

9、t;+j;if(!p|j>i-1)return ERROR;s=new LNode; s->data=e; s->next=p->next;p->next=s;return OK;/ 单链表的删除1. 查找结点 ai-1 并由指针 p 指向该结点。2. 临时保存待删除结点ai的地址在q中，以备释放。3. 将结点*p的指针域指向ai的直接后继结点。4. 释放结点 ai 的空间。Status ListDelete_L(Li nkList & L,i nt i)LinkList p=L,q;int j=0;while(p->next)&&(

10、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-&g

11、t;data);p=p->next;while(p);void main()int i,n,e;LinkList L;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(" 当

12、前单链表的内容为： n");ListPrint_L(L);：n");printf("n");printf(" 请输入您要插入的数据 e 及其位置 i ，使用空格键隔开 scanf("%d %d",&e,&i);if(ListInsert_L(L,i,e)printf(" 当前单链表的内容为： n"); ListPrint_L(L);elseprintf("i 值越界！ n");printf("n");printf(" 请输入您要取的数据序号

13、： n"); scanf("%d",&i);if(GetElem_L(L,i,e)printf ( ” 第4 位数据的值为 ： dn",i,e);elseprintf("i 值越界！ n");printf(" 请输入要查找的数据值： n"); scanf("%d",&e); if(!LocateElem_L(L,e)printf(" 查无此值 !n");elseprintf(" 数据 %c 在 %d 号位置 n",e,LocateElem_

14、L(L,e);prin tf(" 请输入要删除的数据的序号： n");scan f("%d", &i);if(ListDelete_L(L,i)printf ( ” 删除后单链表的内容为： n");ListPri nt_L(L);elseprintf(" 输入有误！ ");prin tf("n ” );五、结果分析与总结图1结果分析：如图1所示，输入正确数据时，程序各个功能执行正常。设置输入数据个数为5,可以输入5个数据，按回车后，可以显示我们当前单链表中的数据内容。继续输 入下一指令：输入要插入的数据及位置，使用空格键隔开，回车后，可以看到已经成功插入。继续输入所取的数据序号，可以查找该数据的值。输入要查找的数