一、实验目的
1. 了解线性表的逻辑结构特性,以及这种特性在计算机内的两种存储结构。
2. 重点是线性表的基本操作在两种存储结构上的实现;本次实验以顺序存储的操作为侧重点;并进一步学习结构化的程序设计方法。
二、实例
1. 线性表的顺序存储表示(结构)及实现。
阅读下列程序请注意几个问题:
(1)关于线性表的顺序存储结构的本质是:在逻辑上相邻的两个数据元素ai-1, ai,在存储地址中也是相邻的,既地址连续。不同的教材有不同的表示,有的直接采用一维数组,这种方法有些过时。有的采用含‘动态分配’一维数组的结构体,这种方法过于灵活抽象(对读者要求过高)。我们采用的是含‘静态’一维数组和线性表长的结构体: typedef struct
{ ElemType a[MAXSIZE]; /* 一维数组 子域 */ int length; /* 表长度子域 */ }SqList; /* 顺序存储的结构体类型 */
(2)本程序是一个完整的、子函数较多的源程序。目的为学生提供一个示范,提供顺序存储表示的资料,供学生参考。比如,主函数中简单“菜单设计”(do-while循环内嵌套一个 switch结构)技术。在学习数据结构的初级阶段,并不强要求学生一定使用“菜单设计”技术,同学们可以在main()函数中直接写几个简单的调用语句,就象前面的复数处理程序中的main()一样。但是随着学习的深入,尽早学会使用“菜单设计”技术,会明显提高编程和运行效率。 [源程序] (略)
三、实验题
1. 一个线性表有n个元素(n 第一步:创建顺序表,并输出原始数据 第二步:排序,输出排好序的线性表 第三步:输入要插入的元素x 第四步:将x插入已排序的线性表中,使线性表仍然有序 第五步:输出最终结果 要求: 1、70分程序 //事先直接给定有序表 #include<> #define MAXSIZE 50 typedef struct { int a[MAXSIZE]; int length; }List; void main() { List L; int i,j; int x; =10; for(i=0;i<10;i++) [i]=2*i; printf(\"事先给定的有序表为(当前表长为10):\\n\"); for(i=0;i<;i++) printf(\"%4d\ printf(\"\\n请输入一个数x\"); scanf(\"%d\ for(i=9;i>=0;i--) { if(x<[i]) [i+1]=[i]; else {[i+1]=x; //printf(\"%d\ ++; break;} } for(i=0;i<;i++) printf(\"%4d\ } 2、80分程序: //事先直接给定有序表,用函数实现数据元素x的插入 #include<> #define MAXSIZE 50 typedef struct { int a[MAXSIZE]; int length; }List; void Insert(List *L,int x); void main() { List L; int i,j; int x; =10; for(i=0;i<10;i++) [i]=2*i; printf(\"事先给定的有序表为(当前表长为10):\\n\"); for(i=0;i<;i++) printf(\"%4d\ printf(\"\\n\"); //以下程序段请填空完成:现有一元素x要插入到线性表的适当位置上,并保持线性表原有的顺序不变。 printf(\"请输入要插入的元素x:\"); scanf(\"%d\ Insert(&L,x); } //请完成Insert()函数 3、100分程序: //按步骤完成全部功能,并用函数实现 #include<> #define MAXSIZE 50 typedef struct { int a[MAXSIZE]; int length; }List; //请注意该顺序表的结构 void Create(List *L); void Sort(List *L); void Display(List L); void Insert(List *L,int x); main() { int i,x; List L; printf(\"1、创建线性表(初始化和尾部插入)\\n\");Create(&L); Display(L); printf(\"2、对线性表进行排序\\n\");Sort(&L); Display(L); printf(\"3、请输入要插入的元素:\");scanf(\"%d\ printf(\"4、将x插入到有序表中\\n\");Insert(&L,x); Display(L); } void Create(List *L) { //请填空完成创建无序链表的函数 } void Sort(List *L) { int i,j,t; for(i=0;i t=L->a[j];L->a[j]=L->a[j+1];L->a[j+1]=t; } } void Display(List L) { //请完成显示顺序表的函数 } void Insert(List *L,int x) { //请完成往有序表L中插入元素x的函数,使顺序表仍然有序 } 四、要求 1、可以要求分组完成,组内成员不可超过3人,第一人为满分(根据程序所得的分数),第二人减去5分,第三人减去10分 2、独立完成的为满分,鼓励大家独立完成 3、下课前提交源程序,文件名为组内同学的名字(区分先后顺序) 4、实验报告在一周内上交,可三人一组(实验报告作为资料保存,不做打分依据) 因篇幅问题不能全部显示,请点此查看更多更全内容