单链表实验报告
实验一 线性表基本操作的编程实现
--线性表在链表存储下的主要操作实现
一、需求分析
【实验目的】
通过本次实验，对课堂上线性表的知识进行巩固，进一步熟悉线性表的链接存储及相应的基本操作；并熟练掌握VC++ 6.0操作平台，学会调试程序，以及编写电子实验报告
【实验要求】
编写线性表的基本操作，有构造线性表，线性表的遍历，插入，删除，查找，求表长等基本功能，在此基础上能够加入DOS下的图形界面以及学会文件的操作等功能，为以后的学习打下基础。
【实验任务】
(1).线性表基本操作的编程实现，掌握线性表的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、逆序、排序等操作，存储结构可以在顺序结构或链表结构中任选，可以完成部分主要功能，也可以用菜单进行管理完成大部分功能。还鼓励学生利用基本操作进行一些更实际的应用型程序设计。
(2).用菜单管理，把线性表的顺序存储和链表存储的数据插入、删除运算进行程序实现。建议实现键盘数据输入实现改实验的通用性。为了体现功能的正常性，至少要编制遍历数据的函数.
(3).注意事项:开发语言使用C++，尽量使用面向对象的思想和实现方法，可以改编成应用软件.
【实验类型】
验证型实验
二、概要设计
需要实现线性表的以下功能:
1、创建单链表
2、删除链表中的某个结点
3、输出单链表(遍历)
4、释放结点所占空间
5、查找第i个结点
6、插入一个结点
7、求链表的长度
二、详细设计
(1).数据结构
线性表的线性结构觉决定了它的性质：数据元素之间是一种线性关系，数据元素一个接一个的排列，除了最后一个数据，其他的数据面临的下一个数据有且仅有一个。
(2) .存储结构
单链表采用一个结点存放一个数据元素，每个结点除了包括存放数据元素值的数据域（data）外，还包括指向下一个元素的存储位置的指针域(next)。最后一个结点的指针域为空。
(3). 算法分析（函数功能的实现）
a.创建链表
创建链表的过程实际相当于申请了一个一个的节点，将这些节点用一种关系连接起来。本程序没有空置的头结点。创建的过程中分别对头结点和非头结点进行不同的处理。
(1).创建的过程
nodetype *create() //建立单链表,由用户输入各节data域之值
{
elemtype d;
nodetype *h=NULL,*s,*t;
int i=1;
cout＜＜"建立一个单链表"＜＜endl;
while(1)
{
cout＜＜"输入第"＜＜i＜＜"节点data域值:";
cin＞＞d;
if (d==0) break; //以0表示输入结束
if(i==1) //建立第一个节点
{
h=new nodetype;
h-＞data=d;
h-＞next=NULL;
t=h;
}
else //建立其于节点
{
s=new nodetype;
s-＞data=d;
s-＞next=NULL;
t-＞next=s;
t=s; //t始终指向生成的单链表最后一结点
}
i++;
}
return (h);
}
b．插入函数
链表的插入分为往前插和往后插两种操作，此程序采用了往后插的方法，同时实现了从键盘输入数据的功能。也考虑了特殊情况即链表的溢出，对此首先进行了判断，保证了程序的安全性和健壮性。在此过程中调用了另一函数find()；
nodetype *ins(nodetype *h,int i,elemtype x) //在第i个节点后插入data域为x的节点
{
nodetype *p,*s;
s=new nodetype; //建结点s
s-＞data=x;
s-＞next=NULL;
if(i==0) //插入到第一个位置
{
s-＞next=h;
h=s;
}
else
{
p=find(h,i); //查找第i个节点,并由p指向该节点
if (p!=NULL)
{
s-＞next=p-＞next;
p-＞next=s;
}
else
cout＜＜"输入的i值不正确"＜＜endl;
}
return h;
}
c.删除函数
对于删除，和插入一样也要通过改链来实现，不过在单链表中，当一个指针指向某一个节点时，是不能删除它的，因为地址存放在上一个节点的链域中，所以必须启动一个尾随指针。同插入一样，是删除某个结点后的数，也调用了find（）；函数，由于插入和删除类似所以不附上原程序。
d.输出函数(遍历)
采用while循环输出单链表的内容，用到了p1=p1-＞next以及输出函数cout＜＜信息；输出前同样对链表是否为空进行了判断,该函数比较简单，相应操作如下：
if (p==NULL)
cout＜＜"空表";
else
while(p!=NULL) //链表不为空时输出
{
cout＜＜p-＞data＜＜" ";
p=p-＞next;
}
e.求长度函数
此函数也进行了对链表的判断，其中用到指针，按顺序数指针个数并累加返回个数即可。
g.查找函数
这个函数是为了查找链表中某个结点并返回其指针，查找函数更重要的应用是在插入和删除中对它的调用使得程序变的简单。
h.其它函数
释放链表中的结点，考虑了链表是否为空相应的进行不同的操作。
四．调试分析
调试过程中遇到了许多问题．比如，第一遍上机时只是将主要的函数写上去了，而没有主函数，
最后检查程序时就比较麻烦，从第一个函数看起，加上后错误才减少；第二个是界面上的问题，我从
同学那拷过来的face是不能直接用的，其中有很多语句需要修改，也有一些不懂，比如其中的sleep(n)，
不知道是什么意思，n应该是多少等，后来才知道是界面延迟的时间，还有其中的case(０)，复了不同
的含义，调用过程中发生混乱．其他的函数方面就比较简单，我觉得做的过程中就是要先在纸上画出
简单的流程图，使思路清晰，这样编程时才不至于无从下手，另外编写函数时首先要考虑异常情况，
然后才是一般情况的处理．由于能力有限调试的结果只能放在exe文件中．
五．用户手册
┃ 单链表操作清单
┃ 1:创建单链表
┃ 2:删除一个结点
┃ 3:输出单链表
┃ 4:释放结点所占空间
┃ 5:查找第i个结点
┃ 6:插入一个结点
┃ 7:求链表的长度
┃ 0:退出本系统
请选择 :
六．附录
．create() 创建单链表，由用户输入各结点data域值，以０表示输入结束，最后返回建立的单链表头指针．
．disp(nodetype *h)：输出单链表h的所有结点的data域的值．
．len(nodetype *h)： 返回单链表h的长度．
．find(nodetype *h,int i): 返回单链表h中第i个结点的指针．
．ins(nodetype *h,int i,elemtype x)：在单链表h中第i个结点（i＞=0）之后插入一个data域为x的结点，并返回插入结点后的单链表的头指针．
．del(nodetype *h,int i): 删除单链表h中第i个结点，并返回插入结点后的单链表的头指针．
．dispose(nodetype *h): 释放单链表h中所有结点占用的存储空间．
七．心得体会
通过本次实验我对链表有了更深的了解，对链表的插删操作、遍历、查找等基本上掌握了。
同时，通过自己数次的调试、修改也搞懂了许多以前比较模糊的知识点，比如这次的界面是复制过来的，其中很多语句经过同学的讲解都理解了。但这次实验也有很多不尽人意的地方，比如由于没有将头结点空置，使得很多操作都比较复杂；还有就是本次实验电子报告中我原来打算加上各函数的简单流程图，但是由于我处理图形方面还比较不熟练，画了三四个小时也不太满意，所以索性将几个小时的努力通过del键结束了，所以这次报告不太令人满意，我将在以后的报告中加上示意图，多学习同学优秀的地方．也会在以后的学习过程中要尽量考虑周全，使程序更有实用价值，提高编程能力。
第二篇：单链表的基本算法实验报告
单链表的基本算法实验报告
单链表的的基本算法
1、需求分析
1.程序的功能
（1） 程序具备任意选择删除、插入、查找数据元素，和求单链表表长等几项功能。
（2） 当选择删除功能时，从键盘读入欲删除的元素位置，按指定位置删除；当选择插入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号；当选择求表长功能时，返回该单链表表长的数值。
2.输入输出的要求
（1） 从键盘读入一组整数，按输入顺序形成单链表。
（2）每种操作结束后，都能在屏幕上打印出此时单链表元素的遍历结果。
（3）测试数据
从键盘输入一组若干数字使之形成单链表
2、概要设计
1.本程序所用的抽象数据类型的定义
typedef struct
{
DataType items[LISTSIZE];
int length;
}SqList;
2． 主程序的流程及各程序模块之间的层次关系
先定义一个顺序表，结构体里的一位数组为顺序表内容，然后调用int InitList(SqList *L)初始化顺序表，然后已键盘输入的形式输入一组一维数组，保存到顺序表里，次数组以-222作为结束符号，然后调用int TraverseList(SqList L)遍历次顺序表，在主函数里实行do-while在里面进行意选择删除、插入、查找数据元素的功能。
删除功能 调用int ListInsertt(SqList *L)，int ListInsertt(SqList *L)又调用int ListDelete(SqList *L)，为嵌套调用。
插入功能 调用int ListInsert(SqList *L,int pos,DataType item)此函数。
查找功能 调用int Find(SqList L)；
在以上子函数中要用到int ListEmpty(SqList L)判空函数。
3、详细设计
1． 采用c语言定义相关的数据类型
（1）用C语言描述的单链表的节点结构
typedef struct Node
{
DataType data;
struct Node *next;
}LNode, *PNode,*LinkList;
四、调试分析
1.调试中遇到的问题及对问题的解决方法
在调试过程在运行插入和查找功能时把位置找错，总是找到正确位置的后一个，后来经过仔细阅读课本发现我把书上定义理解错了。果断改正。
2.算法的时间复杂度和空间复杂度
O(n), 空间同样为O(n).
5、源程序
#include＜stdio.h＞
#include＜malloc.h＞
typedef int DataType;
typedef struct Node
{
DataType data;
struct Node *next;
}LNode, *PNode,*LinkList;
int InitList(LinkList *h)/*初始化单链表*/
{
*h=(LinkList)malloc(sizeof(LNode));/*生成头结点*/
if(!h)
{
printf("初始化链表错误!\n");
return 0;
}
(*h)-＞next=NULL;/*头指针的指针域置为空*/
return 1;
}
int ListLength(LinkList h)/*求表长*/
{
int total=0;
PNode p=h-＞next;
while(p)
{
total++;
p=p-＞next;
}
printf("单链表长度为:%d\n",total);
return total;
}
int ListEmpty(LinkList h)/*判表空*/
{
if(h-＞next) return 0;
else return 1;
}
int ListInsert(LinkList h,int pos,DataType x)/*插入*/
{
PNode p=h,q;
int i=0;
while(p && i＜pos-1)
{
p=p-＞next;
i++;
}
if (!p || i＞pos-1)
{
printf("插入位置不合法!\n");
return 0;
}
q=(PNode)malloc(sizeof(LNode));/*生成新结点*/
if (!p)
{
printf("不能生成新结点\n");
return 0;
}
q-＞data=x;
q-＞next=p-＞next;
p-＞next=q;
return 1;
}
int ListInsertt(LinkList h)/*选择插入*/
{
int pos;
DataType x;
printf("请输入要插入的位置:");
scanf("%d",&pos);
printf("请输入要插入的数据:");
scanf("%d", &x);
ListInsert(h,pos,x);
return 1;
}
int ListDelete(LinkList h,int pos,DataType *item)/*删除*/
{
PNode p=h,q;
int i=0;
while(p-＞next && i＜pos-1)/*寻找被删结点的前驱*/
{
p=p-＞next;
i++;
}
if (!p-＞next || i＞pos-1)
{
printf("删除位置不合法!\n");
return 0;
}
q= p-＞next;
p-＞next=q-＞next;
*item=q-＞data;
free(q);
return 1;
}
int Find(LinkList h)/*查找数据*/
{
DataType item;
int pos=0;
PNode p=h-＞next;
printf("请输入要查找的数据:");
scanf("%d",&item);
while(p)
{
if(p-＞data==item)
{
printf("查找的数据位置序号是:%d\n",pos+1);
}
pos++;
p=p-＞next;
}
if(p)
{
printf("没有这个数据!\n");/*?*/
return 0;
}
return 1;
}
void TracerseList(LinkList h)/*遍历单链表*/
{
PNode p=h-＞next;
while(p)
{
printf("%d\t",p-＞data);
p=p-＞next;
}
printf("\n");
}
int ListDeletee(LinkList hh)/*要删除的数*/
{
int pos,items;
printf("请输入要删除的位置：");
scanf("%d", &pos);
if(ListEmpty(hh)==1)
{
printf("链表为空，非法删除!");
return 0;
}
ListDelete(hh,pos,&items);
TracerseList(hh);
return 1;
}
int main(void)
{
int op,i,data[100];
LinkList hh;
InitList(&hh);
printf("请输入单链表全部数据：");
for (i=0;i＜100;i++)
{
scanf("%d",&data[i]);
if (data[i]==-1) break;
ListInsert(hh,i+1,data[i]);
}
do
{
printf("\n 单链表数据 \n");
printf("................................");
printf("\n (1)单链表删除 \n");
printf(" (2)单链表插入 \n");
printf(" (3)单链表查找 \n");
printf(" (4)单链表表长 \n");
printf(" (0)结束单链表 \n");
printf("请选择功能(1,2,3,4,0):");
scanf("%d",&op);
if (op＜0 && op＞7) continue;
switch(op)
{
case 1: ListDeletee(hh);break;
case 2: ListInsertt(hh);TracerseList(hh);break;
case 3: Find(hh);TracerseList(hh);break;
case 4: ListLength(hh);TracerseList(hh);break;
case 0: return 1;
default:break;
}
}while(1);
return 0;
}
六、使用说明及测试结果
请输入单链表全部数据：1 2 3 4 5 6 7 -1
单链表数据
................................
(1)单链表删除
(2)单链表插入
(3)单链表查找
(4)单链表表长
(0)结束单链表
请选择功能(1,2,3,4,0):1
请输入要删除的位置：2
1 3 4 5 6 7
单链表数据
................................
(1)单链表删除
(2)单链表插入
(3)单链表查找
(4)单链表表长
(0)结束单链表
请选择功能(1,2,3,4,0):2
请输入要插入的位置:3
请输入要插入的数据:44
1 3 44 4 5 6 7
单链表数据
................................
(1)单链表删除
(2)单链表插入
(3)单链表查找
(4)单链表表长
(0)结束单链表
请选择功能(1,2,3,4,0):3
请输入要查找的数据:44
查找的数据位置序号是:3
1 3 44 4 5 6 7
单链表数据
................................
(1)单链表删除
(2)单链表插入
(3)单链表查找
(4)单链表表长
(0)结束单链表
请选择功能(1,2,3,4,0):4
单链表长度为:7
1 3 44 4 5 6 7
单链表数据
................................
(1)单链表删除
(2)单链表插入
(3)单链表查找
(4)单链表表长
(0)结束单链表
请选择功能(1,2,3,4,0):0
Press any key to continue
7、实验感悟
做数据结构上机实验感觉困难重重，有很多不懂的地方，由于以前C语言学得不是很扎实，所以在编写程序时候遇到很多问题，很多地方是照着课本上的源程序复制下来的，不知其原理。多亏有班上这方面学得好的同学的悉心指导才得以把程序做出来，在这里对他们表示感谢。当然，通过这个实验也学到很多东西，除知识性质的外还有就是要保持积极的心态，不懂的地方多向别人请教。