线性表的顺序结构及其应用

1、广西工学院计算机学院 数据结构课程实验报告书 实验一 线性表的顺序表结构及其应用 学生姓名：李四 学号： 2012 班级： 计 Y124 指导老师：王日凤 专业： 计算机学院软件学院 提交日期： 2013年 6 月 18 日 1实验目的 1）熟练掌握线性表的基本操作在链式存储结构上的实现。 （2）用线性表的链式操作实现线性表的合并。 2. 实验内容 1）要求用链式存储结构。然后实现如下操作： 初始化线性表 建立一个含 n 个数据的线性表，用头插法或尾插法。 查找：输入一个数， 查找线性表， 若有，则输出“查找成功” ，否则输 出“无此数” （流程图） 插入：输入一个数和插入位置，实现插入操作，

2、并显示插入成功。 删除：输入一个位置数，删除该位置上的数，并显示删除成功。 （流程图） 2）线性表的合并，已知两个升序线性表，要求合并成一个新的升序线性表。 3实验要求 1） 上机前交实验源程序（纸质版） ，由学习委员统一收好交老师（附上不交同学名 单）。 2） 用一切你能想到的办法解决遇到的问题，培养解决问题的能力。 3）实验报告（于本周五下午） 报告内容包括 ：实验目的、实验内容、实验代码、实验输入输出结果以及实验 体会供五部分。 线性表的链式存储结构如下： #define LIST_INIT_SIZE 100;/ 存储空间初始分配量 #define LISTINCREMENT 10;/

3、存储空间分配增量 typedef struct LNode ElemType data; / 存储空间基址 Struct LNode *next;/当前长度 LNode, *LinkList; 3主要算法 3.1 顺序存储结构 (1)结构定义： #include #include #include #include / 各头文件 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MAXSIZE 100 typedef int ElemType; / 定义宏参 / 定义静态表存储结构 typedef struct int elemM

4、AXSIZE; / 定义数据类型 int length; / 记录当前长度 SqList; /=各函数声明 =/ void InitList(SqList / 建立线性表 int ListLength(SqList L);/ 计算表的长度 int ListEmpty(SqList L); / 判断表是否为空 int ListInsert(SqList / 插入数字 int search(SqList L); / 查找元素 int ListDelete(SqList / 删除元素 void print(SqList L); / 输出元素 void ListClear(SqList / 清空表 i

5、nt priorElem(SqList L,ElemType e); / 求前驱 int NextElem(SqList L,ElemType e); / 求后驱 void MergeList_Sq(SqList La,SqList Lb,SqList / 合并 void ListClear(SqList / 清空线性表 void ListSort(SqList / 元素排序 /=各函数声明 =/ / 建立线性表 void InitList(SqList L.length=0; / 初始化长度为 printf( 初始化完成 !n ); printf( 请输入你要储存数据的长度： ); scan

6、f( %d, L.length=n; for (i=1;i=L.length;i+) / 依次赋值 printf(请输入第个数据：,i); scanf( %d, printf( 输入完成 !n ); printf( 新列表为： ); print(L); / 输出函数 printf( n ); / 计算线性表长度 int ListLength(SqList L) / 初始条件 : 线性表 L 已存在 / 操作结果 : 返回线性表的长度值 return L.length; / 判断线性表是否为空 int ListEmpty(SqList L) / 初始条件 : 线性表 L 已存在 / 操作结果 :

7、 若长度为返回，否则返回 if (L.length=0) return 1; else return 0; / 插入数字 int ListInsert(SqList printf( 请输入您要插入的位置： ); scanf( %d, if (iL.length) printf( 您要插入的位置狱界 ! ); printf( n ); return ERROR; if (L.lengthMAXSIZE) printf( 序表上溢： ); return ERROR; printf( 请输入您要插入的数字： ); scanf( %d, q= for (p=p=q;-p) *(p+1)=*p; *q=

8、a; +L.length; printf( 插入成功 !n ); printf( 新列表为： ); print(L); printf( n ); / 查找数字 int search(SqList L) / 初始条件 : 线性表 L 已存在 / 操作结果 : 若查找成功返回和输出位置，否则返回 int num,i; printf( 查找数字 !n ); printf( 请输入你要查找的数字： ); scanf( %d, for (i=0;i=L.length;i+) if (num=L.elemi) printf( 查找成功！ n ); printf( 数据的位置为 : %d ,i); retu

9、rn 1; printf( 无此数 !n ); printf( n ); return 0; / 元素定位 int locateElem(SqList L,ElemType e) / 初始条件 : 线性表 L 已存在 / 操作结果:若定位成功返回位置 i ，否则返回 int i; for (i=1;i=L.length;i+) if (e=L.elemi) return i; return 0; / 求元素前驱 int priorElem(SqList L,ElemType e) / 初始条件 : 线性表 L 已存在 / 操作结果 : 若查找成功返回和输出前驱元素，否则返回 int i,pre

10、; i=locateElem(L,e); if (i) if (i=1) printf( 这是第一个元素，没有前驱 !n ); return 0; else pre=L.elemi-1; printf(所查元素啲前驱为：%d ,e,pre); return 1; else printf( 表中无此元素 !n ); return 0; / 求元素后驱 int NextElem(SqList L,ElemType e) / 初始条件 : 线性表 L 已存在 / 操作结果 : 若查找成功返回和输出后驱元素，否则返回 int i,next; i=locateElem(L,e); if (i) if (

11、i=L.length) printf( 这是最后一个元素，没有后驱 !n ); return 0; else next=L.elemi+1; printf(所查元素啲后驱为：%d ,e,next); return 1; else printf( 表中无此元素 !n ); return 0; / 删除元素 int ListDelete(SqList printf( 请输入您要删除的数字的位置数： ); scanf( %d, if (i+1L.length) printf(删除失败!n); return ERROR; p= q=L.elem+L.length; for (+p;p=q;+p) *(

12、p-1)=*p; -L.length; printf( 删除成功 !n ); printf( 新列表为： ); print(L); printf( n ); / 输出元素 void print(SqList L) / 初始条件 : 线性表 L 已存在 / 操作结果 : 输出线性表中的所有元素 int i; for (i=1;i=L.length;i+) printf( %d ,L.elemi); return ; / 清空线性表 void ListClear(SqList for (i=1;i=L.length;i+) L.elemi= 0 ; L.length=0; return ; / 线

13、性表合并 void MergeList_Sq(SqList La,SqList Lb,SqList while (i=La.length else Lc.elemk+=Lb.elemj+; while (i=La.length) Lc.elemk+=La.elemi+; while (j=Lb.length) Lc.elemk+=Lb.elemj+; Lc.length=k-1; / 元素排序 void ListSort(SqList for (i=1;i=L.lengthi+) flag=0; for (j=0;jL.elemj+1) L.elem0=L.elemj; L.elemj=L.e

14、lemj+1; L.elemj+1=L.elem0; / 主函数 void main() SqList L,La,Lb,Lc; ElemType e; int j, k; while (1) system( printf( printf( printf( cls ); / 清屏 ); ); ); nt* nt* 线性表的顺序结构及其应用 nt*n printf( t * 1. 建立线性表 2. 插入数字 *n printf( t * 3. 查找数字 4. 删除数字 * n printf( t * 5. 顺序表长度 6. 顺序表空否 * n printf( t * 7. 数据合并 8. 数字排序

15、 * n printf( t * 9. 清空序表 0. 返回 *n printf( t*n II printf( scanf( 请选择选项( -9): ); %d, ); ); ); ); ); ); if (k10) printf( printf( printf( getch(); continue ; switch (k) case 1: 输入有误，请重新输入 ! ); n ); nttt 按任意键进行重新操作 ! ); InitList(L); printf( n ); printf( nttt 按任意键进行重新操作 ! ); getch(); break ; case 2: print

16、f( 插入数字 !n ); ListInsert(L); printf( n ); printf( nttt 按任意键进行重新操作 ! ); getch(); break ; case 3: printf( 你要查找的是 : 1. 元素的位置 2. 元素的前驱 3. 元素的后 驱 n ); printf( 请选择项 : ); scanf( %d, if (j=1) search(L); if (j=2) printf( 请输入查找元素： ); scanf( %d, priorElem(L,e); if (j=3) printf( 请输入查找元素： ); scanf( %d, NextElem(

17、L,e); printf( n ); printf( nttt 按任意键进行重新操作 ! ); getch(); break ; case 4: printf( 删除数字 !n ); ListDelete(L); printf( n ); printf( nttt 按任意键进行重新操作 ! ); getch(); break ; case 5: printf( 计算线性表的长度 ?n ); j=ListLength(L); printf( 线性表的长度为 :%d ,j); printf( n ); printf( nttt 按任意键进行重新操作 ! ); getch(); break ; ca

18、se 6: printf( 判断线性表是否为空 ?n ); j=ListEmpty(L); if (j=1) printf( 线性表为空 ! ); else printf( 线性表不为空 ! ); printf( n ); printf( nttt 按任意键进行重新操作 ! ); getch(); break ; case 7: system( cls ); / 清屏 printf( La 和 Lb合并!n); printf(请输入La的数据!n); InitList(La); printf( n ); printf(请输入Lb的数据!n); InitList(Lb); printf( n )

19、; MergeList_Sq(La,Lb,Lc); printf( La和Lb合并成功!n); printf( La 和 Lb合并后为：)； print(Lc); printf( n )； printf( nttt 按任意键进行重新操作 ! )； getch()； break； case 8： printf(数字排序!n); printf(排序前： )； print(L); printf(n ); ListSort(L); printf( 排序成功 !n ); printf( 排序后 ： ); print(L); printf( n ); printf( nttt 按任意键进行重新操作 ! )

20、; getch(); break; case 9： printf( 你真确定要清空序表 ! 1.YES 2.NOn); printf( 请选择项 ： ); scanf( %d, if (j=1) ListClear(L); printf(清空序表成功呦 !n ); if (j=2) printf(n ); printf(nttt按任意键进行重新操作 ! ); getch(); break; case 0： printf( 你真确定要退出 ! 1.YES 2.NOn); printf( 请选择项 ： ); scanf( %d, if (j=1) printf(nttt 再见，欢迎再次使用 !nnttt); exit(OVERFLOW); - 10 - if (j= printf( printf( getch(); break; 3.流程图 n); nttt按任意键进行重新操作!); 开始 存在返回 if语句 存在前驱返 回元素 顺序表不为 空 输入元素 if语句 不存在, 返回0 / / 存在后驱返回 兀素 返