线性表的操作算法实验报告
- 格式：doc
- 大小：355.00 KB
- 文档页数：18
实验报告
2013学年第一学期 任课老师：
课程名称 数据结构 班级 学号 姓名
实验名称 实验一 线性表的操作算法 实验时间
实验环境
Visual C++ 6.0
实验目的和内容要求
实验一 线性表的操作算法
1．实验目的
用C/C++,Java程序实现课本中的有关算法，以达到对算法熟练的目的。
2．实验内容
分别用数组和链表作为存储结构，实现线性表的插入、删除、查找、排序、合并等操作。
实验过程记录
（学生写出实验步骤及中间的结果与现象，在实验中做了什么，怎么做，发生的现象和中间结果）
链表：
1. 在写主函数之前，先创建一个长度为n的链表
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*LinkList;
2. 建立链表的函数框架，根据实验要求完善功能
插入：
int ListInsert(LinkList &L, int i, int e) {
LinkList p=L;
int j=0;
while(p&&j
p=p->next; ++j;
}
if(!p ||j>i-1) return 0;
LinkList s = (LinkList)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
return 1;
}
删除：
int ListDelete(LinkList &L, int i, int &e) {
LinkList p=L;
int j=0;
while(p->next&&j
p=p->next; ++j;
}
if(!(p->next)||j>i-1) return 0;
LinkList q=p->next;
p->next=q->next;
e=q->data;
free(q);
cout<<"被删除的元素数据为"<
return 0;
}
查找：
int GetElem(LinkList &L,int i, int &e) {
LinkList p=L->next;
int j=1;
while (p && j
p=p->next; ++j;
}
if (!p||j>i) return 0;
e=p->data;
cout<<"该元素的值为"<
return 1;
}
排序：
LinkList Sort(LinkList L)
{ LinkList p,q;
int temp;
for(p=L;p!=NULL;p=p->next)
{
for(q=p->next;q!=NULL;q=q->next)
{
if(p->data>q->data)
{
temp=q->data;
q->data=p->data;
p->data=temp;
}
}
}
return L;
}
合并:
void MergeList_L(LinkList &L,LinkList &La,LinkList &Lb) {
LinkList p,pa,pb;
p=L->next;
pa=La->next;
Lb=pb=L; //用L的头结点作为Lb的头结点
while (p&&pa) {
if (p->data<=pa->data) {
pb->next=p;
pb=p;
p=p->next;
}
else {
pb->next=pa;
pb=pa;
pa=pa->next;
}
}
pb->next=p?p:pa;
free(La);
}
3. 完成函数框架后开始写主函数，先输入一个链表L，然后出现功能栏目，可供选择，此处应做一个循环，使其可不断对该链表L操作，用多支选择语句加上do…while循环。
int main()
{
LinkList L;
int n,s,e,i,f,g,h;
cout<<"输入链表长度n:";
cin>>n;
cout<<"请输入L中的元素:"<
CreateList( L, n);
cout<<"输入的链表为:"<<" ";
LNode *q=L->next;while(q){cout
cout<
int choice;
cout<<"请选择功能:"<
cout<<"1.插入元素"<
cout<<"2.删除元素"<
cout<<"3.查找元素"<
cout<<"4.给元素排序"<
cout<<"5.合并链表"<
cout<<"0.退出程序"<
cout<<"PS:若先排序再合并，可将得到新的排序后的合并链表。"<
do{
cout<
cout<<"请选择功能:"<
cin>>choice;
switch(choice)
{
case 1:
{
cout<<"输入插入的位置:";
cin>>s; cout<<"输入插入的数据元素:";
cin>>e;
ListInsert( L, s, e);
cout<<"插入后的链表:"<<"\n";
q=L->next;
while(q){
cout q=q->next; } break; } case 2: { cout<<"输入删除位置:"; cin>>g; ListDelete( L, g, h); cout<<"删除后的链表:"<<"\n"; q=L->next; while(q){ cout q=q->next; } break; } case 3: { cout<<"输入查找位置:"; cin>>i; GetElem( L, i, f); break; } case 4: { LinkList p; Sort(L); cout<<"排序后的链表为:"< q=L->next; while(q){ cout q=q->next; } break; } case 5: { LinkList La,Lb; int m; cout<<"请输入另一个链表La的长度m:"; cin>>m; cout<<"请输入La中的元素:"< CreateList(La,m); cout<<"输入的链表La为:"<<" "; LNode *q=La->next; while(q){ cout q=q->next; } Sort(La); MergeList_L(L,La,Lb); cout< cout<<"合并后的链表:"<<"\n"; q=L->next; while(q){ cout q=q->next; } break; } } } while(choice!=0); return 0; } 数组： 同理，代码附在报告后。 实验结果分析与总结 1、程序运行结果（请提供所完成的各道题运行结果界面截图）： 2、在实验过程中遇到的问题与解决方法： 问题有很多，比如局部变量与全局变量的声明，常常顾此失彼，此处概念仍然不清。 数组的概念出从零开始的命名与使用者角度的转换也常常忘记，所以经常出现空出一位的表，那一位为系统随机赋值。 还有便是在值的传递上，思路不甚明确，导致常常断开，不能调用函数后改变表的值。 3、实验过程中的发现与收获，未解决或需进一步解决的问题： 在循环嵌套方面还是有些害怕，不能一次调试成功，常常需要加减来改变。 收获是学会了在写代码前画流程图来清晰思路，毕竟在算法这方面并不擅长，还需要更多的世间来适应并练习。 指导老师评阅意见 指导老师： 年 月 日 填写内容时，可把表格扩大。 附：实验源程序代码 顺序表（链表）： // 线性表（链表） #include #include "malloc.h" #include using namespace std; typedef struct LNode{ int data; struct LNode *next; }LNode,*LinkList; //创建一个长度为n的链表 void CreateList(LinkList &L, int n) { L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; for (int i=n; i>0; --i) { LinkList p = (LinkList)malloc(sizeof(LNode)); cin>>p->data; p->next = L->next; L->next = p; } } // 在链表L第i个元素之前插入元素e int ListInsert(LinkList &L, int i, int e) { LinkList p=L; int j=0;
