实验一线性表操作实验报告

作者：kaihong | 发布时间：2020-12-18 10:57:26 收藏本文下载本文

XX大学计算机学院实验报告课程名称数据结构实验名称__线性表操作实验报告要求：1.实验目的 2.实验内容 3.实验步骤 4.运行结果 5.流程图 6.实验体会一、实验目的 1 熟悉并掌握线性表的逻辑结构、物理结构。

2 熟悉并掌握顺序表的存储结构、基本操作和具体的函数定义。

3 熟悉VC++程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用。

4 熟悉VC++操作环境的使用以及多文件的输入、编辑、调试和运行的全过程。

二、实验要求 1 实验之前认真准备，编写好源程序。

2 实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。

3 不断积累程序的调试方法。

三、实验内容基本题: 1 对元素类型为整型的顺序存储的线性表进行插入、删除和查找操作。

源程序：

#include #include #include const LIST_INIT_SIZE=10;const LISTINCREMENT=1;typedef struct { int *elem;int length;int listsize;}SqList;void InitList_Sq(SqList&L)//构造一个空的线性表L { L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));if(!L.elem)exit(0);//存储分配失败 L.length=0;//空表长度为0 L.listsize=LIST_INIT_SIZE;//初始存储容量 cout<<“OK!“<L.length+1)cout<<“ERROR!“<=L.listsize)//当前存储空间已满，增加分配 { int *newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));if(!newbase)exit(0);//存储分配失败 L.elem=newbase;//新基址 L.listsize+=LISTINCREMENT;//增加存储容量 } int *q=&(L.elem[i-1]);for(int*p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=j;++L.length;cout<<“OK!“<L.length))cout<<“ERROR!“<第1个值与j满足compare()的元素的位序 //若找到，则返回其在L中的位序，否则返回0 { int i=1;//i的初值为第1个元素的位序 int *p=L.elem;//p的初值为第1个元素的存储位置 while(i<=L.length&&!compare(*p,j)){ ++i;p++;} if(i<=L.length)return i;else return 0;}//LocateElem_Sq void disp(SqList&L){ int *p=L.elem;for(int i=0;i>x;*p=x;p++;List.length++;} cout<<“插入请按1；

删除请按2；

寻找请按3“<>y;if(y==1){ cout<<“请输入插入位置和元素的值:“<>m>>n;ListInsert_Sq(List,m,n);disp(List);} else if(y==2){ cout<<“请输入要删除第几个元素:“<>m;ListDelete_Sq(List,m,j);cout<>m;cout<

加强、提高题：

2、编写一个求解Josephus问题的函数。用整数序列1, 2, 3, ……, n表示顺序围坐在圆桌周围的人。然后使用n = 9, s = 1, m = 5，以及n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 10作为输入数据，检查你的程序的正确性和健壮性。最后分析所完成算法的时间复杂度。定义JosephusCircle类，其中含完成初始化、报数出圈成员函数、输出显示等方法。（可以选做其中之一）

加强题：

1、采用数组作为求解过程中使用的数据结构。

提高题：

2、采用循环链表作为求解过程中使用的数据结构。运行时允许指定任意n、s、m数值，直至输入 n = 0 退出程序。

源程序：

（1）加强：

#include #include #include int a[100];int josephus(int n,int s,int m){ if(!(n*s*m)){ cout<<“输入错误！!“<>n;cout<<“请输入开始人的位置与报数长度:“<>s;cin>>m;x=josephus(n,s,m);cout<

2.退出程序。:“<>y;}while(y==1);getch();} 运行结果：

（2）提高：

#include using namespace std;typedef struct LNode { struct LNode *next;int a;}LNode,*LinkList;class JosephouCircle //定义一个类包括三个元素 { public: void SetValue();void PickOut();private: int n;int s;int m;};void JosephouCircle::SetValue()//设置初值的大小 { cout<<“请输入参加游戏的总人数:“<>n;cout<<“请输入开始人的位置:“<>s;cout<<“请输入报数长度:“<>m;} void JosephouCircle::PickOut(){ LinkList L;LNode *p,*q;int j,k;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;LNode*r;r=L;for(int i=1;i<=n;++i)// 构建一个循环链表 { p=(LinkList)malloc(sizeof(LNode));p->a=i;p->next=NULL;r->next=p;r=p;} p->next=L->next;p=L->next;j=1;while(p&&jnext;++j;} for(i=1;i<=n;i++){ for(j=1;jnext;} q=p->next;p->next=q->next;p=q->next;k=q->a;cout<<“输出的结果为:“<

四、实验体会与总结 1、对于线性链表和顺序表都属于线性表问题，但是线性链表比顺序表要灵活，方便；

2、线性表在做元素寻找的操作的时候，必须从头结点开始寻找。

体会：

在编程序的时候，我们每个人肯定会遇到许多问题，我遇到的问题是：当我在运行程序的时候，在输入一个元素后，程序就不继续做下面的操作也不停止运行，自己寻找并修改了好久都没发现问题的所在，最后实在没办法，就去问同学，结果终于发现是一条语句在编写时出现了错误。所以，以后再写程序的时候我一定要再认真仔细一点仔细点。

教师评价优良中及格不及格教师签名日期