单链表实验报告

单链表的基本操作 1.实验题目

问题描述：实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。通过代码的编写理解并掌握单链表的过程编写以及作用。

2.实验要求

（1）依次从键盘读入数据，建立一个单链表并将单链表的初始化设置为空；（2）通过操作选择，输出单链表中的数据元素

（3）显示单链表的长度；

（4）根据指定条件能够查找出元素和修改元素； （5）实现在指定位置插入和删除元素的功能 （6）显示操作后的结果 3.算法设计

（1）用到的结构（逻辑结构、存储结构） 逻辑结构：线性结构 存储结构：带头结点的单链表 （2）算法设计思路

定义结点类型LNode，每个结点包括数据域data和指针域next。定义头指针LinkList。编写如下函数：

1、createlist(LinkList &L)；用尾插法创建一个带头结点的单链表。 2、print(LinkList L)；输出该单链表中的数据元素。 3、ListLength(LinkList L)；求该单链表的长度。

4、GetElem(LinkList &L,int i,ElemType &e)；查找第i个元素。 5、SetElem(LinkList &L,int i,ElemType m)；修改第i个元素。 6、ListInsert (LinkList &L, int i, ElemType e )；在第i个元素前插入一个元素。

7、ListDelete(LinkList &L,int i,ElemType &e2)；删除第i个元素。

8、main()；通过case结构来调用createlist(LinkList &L)、GetElem(LinkList

&L,int i,ElemType &e)、SetElem(LinkList &L,int i,ElemType m)、ListInsert (LinkList &L, int i, ElemType e )、ListDelete(LinkList &L,int i,ElemType &e2)

4.调试和测试

调试过程总结经过多次调试，本程序能很好的完成实验要求的各项功能。给出几组测试数据及实验结果：

4.1 系统界面

4.2 创建带头结点的单链表 完后以0结束）

（先输入单链表整数，每输入完一个整数后按回车键，数据输入

4.3 打印链表中的数据

4.4 打印链表长度

4.5 按位置取元素

4.6 修改链表中的元素

4.7 插入结点

4.8 按结点位置编号删除结点

4.8 显示做了修改后的链表元素：

5.实验总结

对比这次试验，在上机的时候明显感觉到比之前更加有思路，能够很好地找个关键性的语句对程序进行修改，这次试验虽然说比上次好，但是也暴漏出了许多的缺陷，在编写的时候，感觉整个流程都挺对，但是就是运行不出来，或者是不能够实现原有的功能，通过与同学的交流，然后慢慢地参照课本才将本次试验很好地完成。

6.附录（源程序） #include #include

#include\"stdafx.h\" #define OK 1 #define ERROR 0 typedef char ElemType; typedef int Status; typedef struct LNode

{ ElemType data; LNode *next; } LNode,*LinkList;

Status createlist(LinkList &L) //尾插法创建带头结点的单链表{ int ch;

L=new LNode; L->next=NULL;

printf(\"请输入单链表中的数据:\"); scanf(\"%d\LinkList r=L; while(ch!=0)

{ LinkList p=new LNode; p->data=ch; p->next=NULL; r->next=p; r=p;

scanf(\"%d\return OK; }

void print(LinkList L) //输出单链表 { LinkList p=L->next; printf(\"单链表为：\\n\"); while(p)

{ printf(\"%2d\p=p->next; }}

Status ListLength(LinkList L) //求单链表的长度 { int k=0;

LinkList p=L->next; while(p){ k++; p=p->next;}

printf(\"\\n\");

printf(\"单链表的长度为%d:\" , k); printf(\"\\n\"); return k; }

Status GetElem(LinkList &L,int i,ElemType &e) { LinkList p=new LNode; p=L->next; int j=1; while(p&&j { p=p->next;j++;

} //顺指针向后查找，直至p指到第i个结点或p为空止if(!p||j

return ERROR; //第i个结点不存在 e=p->data;

printf(\"第%2d个元素为:%2d\\n \printf(\"\\n\"); return OK;}

Status SetElem(LinkList &L,int i,ElemType m) { LinkList p=new LNode; p=L->next; int j=1; while(p&&j { p=p->next;j++;

} //顺指针向后查找，直至p指到第i个结点或p为空止 if(!p||j

return ERROR;//第i个结点不存在 p->data=m; printf(\"\\n\");

printf(\"第%2d个元素修改为:%2d\\n \printf(\"\\n\"); return OK; }

Status ListInsert (LinkList &L, int i, ElemType e ) { LinkList p=new LNode; p=L; int j=0;

while(p&&j { p=p->next;++j;

} //令指针p指向第i-1个结点 if(!p||j>i-1)

return ERROR; // i小于1或者大于表长+1 LinkList s=new LNode;

if(!s) return ERROR; //存储空间分配失败 s->data=e; s->next=p->next; p->next=s; printf(\"\\n\");

printf(\"在第%2d个位置插入元素:%2d\\n \printf(\"\\n\"); return OK; }

Status ListDelete(LinkList &L,int i,ElemType &e2) { LinkList p=L;int j=0; LinkList q;

while(p->next&&j

{ p=p->next;++j; //寻找第i个节点，并另p指向其前驱 }

if(!p->next||j>i-1)

return ERROR; //删除位置不合理 else

q=p->next;p->next=q->next; //修改指针 e2=q->data;

printf(\"删除了第%2d个元素:%d\\n \printf(\"\\n\");

delete q; //释放节点空间 return OK; } int scan() {int d;

printf(\"1. 创建带头结点的单链表\\n\"); printf(\"2.打印连表中的数据\\n\"); printf(\"3.打印链表长度\\n\"); printf(\"4.按位置取元素\\n\"); printf(\"5.修改链表中的元素\\n\"); printf(\"6.插入结点\\n\");

printf(\"7.按结点位置编号删除结点\\n\"); printf(\"其他键退出......\\n\");

printf(\"\\n请选择所要进行的操作\\n\"); scanf(\"%d\return(d);} void main()

{ printf(\"建立单链表，请先输入单链表整数，每输入完一个整数后按回车键，数据输入完后以0结束\");

printf(\"\\n\"); LinkList L; ElemType e; ElemType e2; int quit=0; int i1,i2,i3,i4,m,n; while(!quit) {switch(scan())

{case 1 :createlist(L); printf(\"\\n\\n单链表已创建！\\n\\n\");break; case 2 :print(L); printf(\"\\n\\n\"); break;

case 3 :ListLength(L); printf(\"\\n\\n\"); break;

case 4 :printf(\"请输入要查找的元素的位置\\n\\n\"); scanf(\"%d\GetElem(L,i1,e); ;break;

case 5 :printf(\"请输入要修改的元素的位置\\n\"); scanf(\"%d\

printf(\"请输入要修改的元素的值\\n\"); scanf(\"%d\SetElem(L,i2,m); break;

case 6 :printf(\"在第？个位置前插入元素\\n\"); scanf(\"%d\printf(\"插入的元素为:\\n\"); scanf(\"%d\ListInsert(L,i3,n); break;

case 7 :printf(\"请输入删除元素的位置:\\n\"); scanf(\"%d\ListDelete(L,i4,e2); break;

default:quit=1; }}}