XX大学计算机学院实验报告 课程名称   数据结构  

　实验名称__线性表操作    实验报告要求：1.实验目的  2.实验内容   3.实验步骤   

　4.运行结果   5.流程图      6.实验体会   

　 一、实验目的 1 熟悉并掌握线性表的逻辑结构、物理结构。

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

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

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

　二、实验要求

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

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

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

　三、实验内容

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

　源程序：

　 #include<iostream.h> #include<conio.h> #include<stdlib.h>

　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!“<<endl; }

　void ListInsert_Sq(SqList&L,int i,int j)

　//在顺序线性表L中第i个位置之前插入新的元素j，

　//i的合法值为1<=i<=ListInsert_Sq(L)+1 {

　if(i<1||i>L.length+1)

　 cout<<“ERROR!“<<endl;

　 //i值不合法

　if(L.length>=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!“<<endl; }//ListInsert_Sq

　void ListDelete_Sq(SqList&L,int i,int&j)

　//在顺序线性表L中删除第i个元素，并用j返回其值

　//i的合法值为1<=i<=ListInsert_Sq(L) {

　if((i<1)||(i>L.length))

　 cout<<“ERROR!“<<endl;

　 //i值不合法

　int *p=&(L.elem[i-1]);

　//p为被删除元素的位置

　j=*p;

　 //被删除元素的值赋给j

　int *q=L.elem+L.length-1;

　 //表尾元素的位置

　for(++p;p<=q;++p)

　 *(p-1)=*p;

　--L.listsize;

　 //被删除元素之后的元素左移

　cout<<“OK!“<<endl;

　//表长减1 }//ListDelete_Sq

　bool compare(int m,int n) {

　if(m==n)

　 return true;

　else

　 return false; }

　int LocateElem_Sq(SqList L,int j)

　//在顺序线性表L中查找第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<L.listsize;i++)

　{

　 cout<<*p<<“

　 “;

　 p++;

　} }

　void main() {

　SqList List;

　InitList_Sq(List);

　int *p=List.elem;

　int m,n,j,k,x,y;

　for(int i=0;i<List.listsize;i++)

　{

　 cin>>x;

　 *p=x;

　 p++;

　 List.length++;

　}

　cout<<“插入请按1；删除请按2；寻找请按3“<<endl;

　for(k=0;k=10;k++)

　{

　 cin>>y;

　 if(y==1)

　 {

　cout<<“请输入插入位置和元素的值:“<<endl;

　cin>>m>>n;

　ListInsert_Sq(List,m,n);

　disp(List);

　 }

　 else if(y==2)

　 {

　cout<<“请输入要删除第几个元素:“<<endl;

　cin>>m;

　ListDelete_Sq(List,m,j);

　cout<<j<<endl;

　disp(List);

　 }

　 else

　 {

　cout<<“请输入所要查找的元素:“<<endl;

　cin>>m;

　cout<<LocateElem_Sq(List,m)<<endl;

　 }

　}

　cout<<endl; }  运行结果：

　   加强、提高题：

　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 <iostream.h> #include <conio.h> #include <stdlib.h>

　int a[100]; int josephus(int n,int s,int m) {

　if(!(n*s*m))

　{

　 cout<<“输入错误!!!“<<endl;

　 exit(0);

　}

　int x=1,y=n;

　int i=s-1;

　int j;

　while(y)

　{

　 for(i=0;i<n;i++)

　 {

　if(a[i]+1)

　 a[i]=x++;

　if(a[i]==m)

　{ a[i]=-1;

　 cout<<i+1<<“出局!“<<endl;

　 x=1;

　 y--;

　}

　 }

　 for(j=0;j<n;j++)

　 {

　if(a[j]+1)

　 a[j]=x++;

　if(a[j]==m)

　{

　 a[j]=-1;

　x=1;

　 y--;

　 if(!y)

　break;

　 else

　cout<<j+1<<“出局!“<<endl;

　}

　 }

　}

　return (j+1); }

　void main() {

　int n,s,m,y=0;

　int x;

　do{

　 for(int i=0;i<100;i++)

　 {a[i]=0;}

　 cout<<“请输入参加游戏的总人数:“<<endl;

　 cin>>n;

　 cout<<“请输入开始人的位置与报数长度:“<<endl;

　 cin>>s;

　 cin>>m;

　 x=josephus(n,s,m);

　 cout<<x<<“胜出!“<<endl;

　 cout<<“请选择:“<<endl;

　 cout<<“1.重新游戏。

　2.退出程序。:“<<endl;

　 cin>>y;

　}while(y==1);

　getch(); }

　  运行结果：

　   （2）提高：

　#include<iostream> 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<<“请输入参加游戏的总人数:“<<endl;

　cin>>n;

　cout<<“请输入开始人的位置:“<<endl;

　cin>>s;

　cout<<“请输入报数长度:“<<endl;

　cin>>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&&j<s)

　{

　 p=p->next;++j;

　}

　for(i=1;i<=n;i++)

　 {

　 for(j=1;j<m-1;j++)

　 {

　p=p->next;

　 }

　 q=p->next;p->next=q->next;

　 p=q->next;

　 k=q->a;

　 cout<<“输出的结果为:“<<k<<endl;

　 free(q);

　} }

　int main(int argc,char* argv[]) {

　JosephouCircle Jo1;

　Jo1.SetValue();

　Jo1.PickOut();

　return 0; }  运行结果：

　   四、实验体会与总结 1、对于线性链表和顺序表都属于线性表问题，但是线性链表比顺序表要灵活，方便； 2、线性表在做元素寻找的操作的时候，必须从头结点开始寻找。

　 体会：

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

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