数据结构_实验一_线性表操作.doc

中国矿业大学计算机科学与技术系试验报告
课程名称________数据结构_______试验名称_____线性表操作__________________
班级____信息安全08-1_____姓名___________学号___________仪器组号_______实验日期___09-11-18___
实验报告要求：1.实验目的2.实验内容3.实验步骤4.程序清单
5.运行结果6.流程图7.实验体会一、实验目的：
1、并掌握线性表的逻辑结构、物理结构。
2、并掌握顺序表的存储结构、基本操作和具体的函数定义。
3、VC++程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用。
4、悉VC++操作环境的使用以及多文件的输入、编辑、调试和运行的全过程。

二、实验要求：
1实验之前认真准备，编写好源程序。
2实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。
3不断积累程序的调试方法。

三、实验内容
基本题:
1对元素类型为整型的顺序存储的线性表进行插入、删除和查找操作。
加强、提高题：
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退出程序。
四、程序清单
基本题:
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>

constLIST_INIT_SIZE=10;
constLISTINCREMENT=1;

typedefstruct{
int*elem;
intlength;
intlistsize;
}SqList;

voidInitList_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;
}

voidListInsert_Sq(SqList&L,inti,inte){
//在顺序线性表L中第i个位置之前插入新的元素e，
//i的合法值为1<=i<=ListInsert_Sq(L)+1
if(i<1||i>L.length+1) //i值不合法
cout<<"ERROR!"<<endl;
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=e;
++L.length;
cout<<"OK!"<<endl;
}//ListInsert_Sq

voidListDelete_Sq(SqList&L,inti,int&e){
//在顺序线性表L中删除第i个元素，并用e返回其值
//i的合法值为1<=i<=ListInsert_Sq(L)
if((i<1)||(i>L.length))
cout<<"ERROR!"<<endl; //i值不合法
int*p=&(L.elem[i-1]); //p为被删除元素的位置
e=*p; //被删除元素的值赋给e
int*q=L.elem+L.length-1; //表尾元素的位置
for(++p;p<=q;++p)
*(p-1)