数据结构单链表插入、删除和修改实验报告
- 格式：doc
- 大小：244.00 KB
- 文档页数：10
1
计算机学院
实验报告
课程名称： 数据结构
实验名称： 单链表
学生姓名： ***
学生学号： ***********
实验日期： 2012
2 一、实验目的
1．理解数据结构中带头结点单链表的定义和逻辑图表示方法。
2．掌握单链表中结点结构的C++描述。
3．熟练掌握单链表的插入、删除和查询算法的设计与C++实现。
二、实验内容
1． 编制一个演示单链表插入、删除、查找等操作的程序。
三、实验步骤
1．需求分析
本演示程序用C++6.0编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。
① 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数。
② 输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。
③ 程序所能达到的功能：完成单链表的生成（通过插入操作）、插入、删除、查找操作。
④ 测试数据：
A． 插入操作中依次输入11，12，13，14，15，16，生成一个单链表
B． 查找操作中依次输入12，15，22返回这3个元素在单链表中的位置
C． 删除操作中依次输入2，5，删除位于2和5的元素
2．概要设计
1）为了实现上述程序功能，需要定义单链表的抽象数据类型：
（1）insert
初始化状态：单链表可以不为空集；操作结果：插入一个空的单链表L。
（2）decelt
操作结果：删除已有的单链表的某些结点。
（3）display
操作结果：将上述输入的元素进行排列显示。
（4）modify
操作结果：将上述输入的某些元素进行修改。
（5）save 3 操作结果：对上述所有元素进行保存。
（6）load
操作结果：对上述元素进行重新装载。
3．使用说明
程序执行后显示
======================
1.单链表的创建
2.单链表的显示
3.单链表的长度
4.取第i个位置的元素
5.修改第i个位置的元素
6.插入元素到单链表里
7.删除单链表里的元素
8.合并两个单链表
9.退出系统
=======================
5.源代码：
#include
using namespace std;
#define true 1
#define false 0
#define ok 1
#define error 0
#define overflow -2
typedef int Status;
typedef int ElemType;
typedef struct LNode
{ ElemType data;
struct LNode *next;
}LNode,*LinkList; 4 void CreateList(LinkList &L,int n)
{ LinkList p;
L=new LNode;
L->next=NULL;
LinkList q=L;
for(int i=1;i<=n;i++)
{ p=new LNode;
cin>>p->data;
p->next=NULL;
q->next=p;
q=p; }
}
Status GetElem(LinkList L,int i,ElemType &e)
{ LinkList p=L->next;
int j=1;
while(p&&j
{ p=p->next;
++j; }
if(!p||j>i) return error;
e=p->data;
return ok;
}
Status LinkInsert(LinkList &L,int i,ElemType e)
{ LinkList p=L;
int j=0;
while(p&&j
{ p=p->next;
++j; }
if(!p||j>i-1)
return error;
LinkList s=new LNode;
s->data=e;
s->next=p->next; 5 p->next=s;
return ok;
}
Status ListDelete(LinkList &L,int i,ElemType &e)
{ LinkList p=L;
LinkList q;
int j=0;
while(p->next&&j
{
p=p->next;
++j; }
if(!(p->next)||j>i-1) return error;
q=p->next;
p->next=q->next;
e=q->data;
delete(q);
return ok;
}
void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)
{
LinkList pa,pc,pb;
pa=La->next;
pb=Lb->next;
Lc=pc=La;
while(pa&&pb)
{ if(pa->data<=pb->data)
{ pc->next=pa;
pc=pa;
pa=pa->next; }
else
{ pc->next=pb;
pc=pb; 6 pb=pb->next; }
}
pc->next=pa?pa:pb;
delete(Lb);
}
void show(LinkList L)
{ LinkList p;
p=L->next;
while(p)
{ cout
p=p->next; }
cout<
}
int Length(LinkList L,int i)
{ i=0;
LinkList p=L->next;
while(p)
{ ++i;
p=p->next; }
return i;
}
void xiugai(LinkList L)
{ int i,j=1;
ElemType k;
ElemType e,m;
LinkList p=L->next;
cout<<"请输入要修改的元素位置(0
cin>>i;
GetElem(L,i,e);
cout<<"该位置的元素:"<
cout<<"修改后的元素值:";
cin>>k;
while(p&&jnext;
++j; }
m=p->data;
p->data=k;
cout<<"修改后的单链表显示如下:"<
show(L);
}
void hebing()
{ int a,b;
LinkList La,Lb,Lc;
cout<<"请输入第一个有序链表的长度:"<
cin>>a;
cout<<"请输入第一个有序链表的元素共（"<
CreateList(La,a);
show(La);
cout<<"请输入第二个有序链表的长度:"<
cin>>b;
cout<<"请输入第二个有序链表的元素共（"<
CreateList(Lb,b);
show (Lb);
MergeList(La,Lb,Lc);
cout<<"合并后的有序链表如下："<
show(Lc);
}
void main()
{ int select;
int x;
ElemType y;
LinkList list;
for(;;)
{ cout<<" 单链表的基本操作"<
cout<<" 1.单链表的创建"<
cout<<" 2.单链表的显示"<
cout<<" 4.取第i个位置的元素"<
cout<<" 5.修改第i个位置的元素"<
cout<<" 6.插入元素到单链表里"<
cout<<" 7.删除单链表里的元素"<
cout<<" 8.合并两个单链表"<
cout<<" 9.退出系统"<
cout<<"请选择:";
cin>>select;
switch(select)
{ case 1:cout<<"请输入单链表的长度:"<
cin>>x;
cout<<"请输入"<
CreateList(list,x);
break;
case 2: cout<<"单链表显示如下:"<
show(list);
break;
case 3: int s;
cout<<"单链表的长度为:"<
break;
case 4: cout<<"请选择所要取出元素的位置:";
cin>>x;
while(x<0||x>Length(list,s))
{ cout<<"输入有误，请重新输入"<
cout<<"请选择所要取出元素的位置:";
cin>>x; }
GetElem(list,x,y);
cout<<"该位置的元素为:"<
