文档介绍:数据结构实验报告
(实验一&实验二)
班级:软件121
学号:201200834122
姓名:程猛实验一
线性表的基本操作及应用
【实验目的】
理解线性表的逻辑结构特性是数据元素之间存在着线性关系,掌握顺序表的特点是逻辑上相邻的元素的存储地址也相邻,熟练掌握线性表的查找、插入和删除等算法并灵活运用这些算法。
【实验内容】(任选一题)
1、建立一个顺序表,要求完成以下操作:实现顺序表的初始化、销毁顺序表、重置顺序表为空表、判断顺序表是否是空表、求顺序表的元素个数、取顺序表中的一个数据、查找顺序表中的一个元素值、查找某一位置元素的前驱和后继、将一个值插入到指定的位置、删除指定位置的元素。
按此方法定义另一个顺序表,实现两个顺序表的合并;如果这两个顺序表元素值是有序的,实现这两个顺序表的合并,并使合并后的数据也是有序排列的。
要求
(a)顺序表的初始状态可直接赋值,也可将初态置为空表,从键盘读入数据元素。
(b)每做一次操作将结果打印出来。
2、建立单链表L(分别采用头插法和尾插法),打印单链表中的数据、打印单链表长度、按值查找元素、按位置取元素、插入结点和删除结点。
(a)初始将单链表置空
(b)在单链表中插入元素
(c)按值查找元素
(d)按位置取元素
(e)插入结点
(f)删除结点
3、以循环单链表为存储结构,编写程序求解约瑟夫问题。
编号为1,2,···,n的n个人围坐在一圆桌旁,从第s个人开始报数,报到第m的人退席,下一个人又重新从1开始报数,依此重复,直至所有的人都退席。
要求
(a) 循环单链表的初始状态可直接赋值,也可将初态置为空表,从键盘(文件)读入数据元素。
(b)输出删除元素的顺序
(c)分析算法的时间性能
【源代码】
#include ""
#include <>
#include <>
#define SIZE 10
#define REMENT 5
typedef struct
{
int *elem;
int length;
int lsize;
}Sqlist;
Sqlist L;
void state_initlist(Sqlist &L)//线性表的初始化
{
=(int*)malloc(SIZE*sizeof(int));
=0;
=SIZE;
}
void creatlist(Sqlist &L)//线性表的建立
{
int *p;
int e;
=(int*)malloc(sizeof(int));
printf("请输入线性表的数据:\n");
scanf_s("%d",&e);
*()=e;
for(int i=1;i<10;i++)
{
p=(int*)malloc(sizeof(int));
scanf_s("%d",p);
e=*p;
*( +i)=e;
++;
}
}
int insertelem(Sqlist &L,int i,int e)//插入
{
int *p,*q;
if(i<0||i>-1 )
exit(0);
if( >= )
{
=(int*)realloc( ,( +REMENT)*sizeof(int));
if(! )
exit(0);
+=REMENT;
}
q= +i;
for(p= +;p>=q;p--)
{
*(p+1)=*p;
}
*q=e;
++ ;
return 0;
}
int deletlist(Sqlist &L,int i)//删除
{
int *p,*q;
int e;
if(i<0||i> )
exit(0);
q= +i;
e= [i];
for(p= + ;q<=p;q++)
*q=*(q+1);
-- ;
return 0;
}
void main()
{
int i,a,b,k;//(1)
do
{
printf("请选择要进行的操作:.初始化 \n");
scanf("%d"