实验一线性表操作实验报告
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、线性表在做元素寻找的操作的时候，必须从头结点开始寻找。
体会：
在编程序的时候，我们每个人肯定会遇到许多问题，我遇到的问题是：当我在运行程序的时候，在输入一个元素后，程序就不继续做下面的操作也不停止运行，自己寻找并修改了好久都没发现问题的所在，最后实在没办法，就去问同学，结果终于发现是一条语句在编写时出现了错误。所以，以后再写程序的时候我一定要再认真仔细一点仔细点。
教师评价 优 良 中 及格 不及格 教师签名 日期
