程序设计单链表实验报告.doc

课程设计报告
一．问题分析和需求定义
(1).线性表基本操作的编程实现，掌握线性表的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、逆序、排序等操作，存储结构可以在顺序结构或链表结构中任选，可以完成部分主要功能，也可以用菜单进行管理完成大部分功能。还鼓励学生利用基本操作进行一些更实际的应用型程序设计。
(2).用菜单管理，把线性表的顺序存储和链表存储的数据插入、删除运算进行程序实现。建议实现键盘数据输入实现改实验的通用性。为了体现功能的正常性，至少要编制遍历数据的函数.
数据的逻辑结构设计和运算定义
需要实现线性表的以下功能:
1、创建单链表2、删除链表中的某个结点3、输出单链表(遍历)4、释放结点所占空间
5、查找第i个结点6、插入一个结点7、求链表的长度
三. 数据的存储结构设计和算法设计
(1).数据结构
线性表的线性结构觉决定了它的性质：数据元素之间是一种线性关系，数据元素一个接一个的排列，除了最后一个数据，其他的数据面临的下一个数据有且仅有一个。
(2).存储结构
单链表采用一个结点存放一个数据元素，每个结点除了包括存放数据元素值的数据域（data）外，还包括指向下一个元素的存储位置的指针域(next)。最后一个结点的指针域为空。
(3). 算法分析（函数功能的实现）

创建链表的过程实际相当于申请了一个一个的节点，将这些节点用一种关系连接起来。本程序没有空置的头结点。创建的过程中分别对头结点和非头结点进行不同的处理。
(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始终指向生成的单链表最后一结点