数据结构顺序表的实现
更新时间:2023-10-20 12:32:01 阅读量: 综合文库 文档下载
实验3 顺序表
一、实验目的
1. 熟练掌握顺序表的类型定义和基本操作算法(以建立、插入、删除、遍历、排序和归并等操作为重点)的实现。
2. 通过实验加深对C语言的使用(特别是函数、数组、结构体和指针)。
3. 掌握模块化程序设计方法。
二、预备知识
1. 顺序表的类型定义
//线性表存储空间的初始分配量 #define LIST_Init_Size 100 //线性表存储空间的分配增量 #define LISTINCREMENT 10 typedef struct{
ElemType *elem; //存储区域基地址 int length; //当前有效长度 int listsize; //当前分配的存储容量 } SqList, *PSqList;
2. 顺序表的基本操作
1)初始化线性表InitList(&L)
该运算的结果是构造一个空的线性表L,为线性表分配存储空间用于存放数据元素。
2)销毁线性表DestroyList(&L )
该运算的结果是释放线性表L占用的内存空间。 3)判定是否为空表ListEmpty(L)
该运算返回一个值表示L是否为空表。若L为空表,则返回1,否则返回0。 4)求线性表的长度ListLength(L)
该运算返回顺序表L的长度。实际上只需返回length成员的值即可。 5) PriorElem( L, cur_e, &pre_e )
该运算返回给定数据元素的前驱数据元素的值 6)NextElem( L, cur_e, &next_e )
该运算返回给定数据元素的后继数据元素的值 7)输出线性表DispList(L)
该运算当线性表L不为空时,顺序输出L中各数据元素的值。 8)求某个数据元素值GetElem(L,i,&e)
该运算返回L中第 i(1≤i≤ListLength(L))个元素的值,存放在e中。 8)按元素值查找LocateElem(L,e)
该运算顺序查找第1个值域与e相等的数据元素的序号。若这样的元素不存在,则返回值为0。
9)插入数据元素ListInsert(&L,i,e)
该运算在顺序表L的第i个位置(1≤i≤ListLength(L)+1)上插入新的元素e。 10) 删除数据元素ListDelete(&L,i,&e)
该运算删除顺序表L的第i(1≤i≤ListLength(L))个元素。 11)清空线性表ClearList( &L )
删除线性表L中的所有数据元素,但不释放已分配给线性表的存储空间。
2. 两个有序表的归并算法
void MergeList(SqList La, SqList Lb, PSqList PLc) {
InitList(PLc); // 构造空的线性表 Lc i = j = 1; k = 1; La_len = ListLength(La); Lb_len = ListLength(Lb);
while ((i <= La_len) && (j <= Lb_len)) // La 和 Lb 均不空 {
GetElem(La, i, ai); GetElem(Lb, j, bj);
if (ai <= bj) { // 将 ai 插入到 Lc 中 ListInsert(Lc, k++, ai); i ++; }
else { // 将 bj 插入到 Lc 中 ListInsert(Lc, k++, bj); j ++; } }
while (i<=La_len) //若La不空, 插入La中剩余的数据元素 {
GetElem(La, i++, ai); ListInsert(Lc, k++, ai); }
while (j<=Lb_len) //若 Lb不空, 插入Lb中剩余的数据元素 {
GetElem(Lb, j++, bj); ListInsert(Lc, k++, bj); } }
三、实验题目
1. 用C语言实现顺序表的ADT(包括顺序表的类型定义和基本操作),假定数据元素的类型为整型。 2.设计一个测试应用程序完成如下功能: ⑴建立顺序L;
⑵依次插入数据元素13,5,27,9,32,123,76,98,54,87; ⑶输出顺序表L; ⑷输出顺序表L的长度; ⑸判断顺序表L是否为空; ⑹输出顺序L的第3个数据元素; ⑺输出数据元素76的位置; ⑻在第4个位置上插入数据元素56; ⑼输出顺序表L的长度; ⑽删除顺序表L的第7个元素; ⑾输出顺序表L; ⑿销毁顺序表L;
以上为必做题。下面为选做题。
⒀建立两个有序的顺序表La和Lb,并分别向顺序表La和Lb插入为m个和n个有序的整数;(注意:m和n的大小,具体的整数值都由自己确定) ⒁输出顺序表La和Lb;
⒂将顺序表La和Lb归并为新的有序表Lc;
⒃输出顺序表Lc;
⒄销毁顺序表La、Lb和Lc。
四、实验要求
1. 顺序表类型定义和基本操作函数声明放在Sqlist.h文件中; 2. 基本操作函数的实现放在Sqlist.c文件中; 3. 测试应用程序放在SqListTestApp.c文件中。
正在阅读:
数据结构顺序表的实现10-20
九年级英语unit7练习206-29
小学音乐课堂教学反思5篇02-21
教师演讲稿-爱生如子 爱校如家12-30
BPSK与QPSK调制解调系统性能仿真01-05
抗日战争电影观后感04-01
怎样制定六年级毕业班数学复习计划11-29
开展技能比武活动方案08-12
2015-2020年中国再生金属行业分析与发展战略研究报告 - 图文04-05
夹具设计工艺过程卡与工序卡08-18
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 数据结构
- 顺序
- 实现
- 塔机检测试题-选择题答案
- 氮族元素练习题(三)
- 2019版高考化学一轮复习 选考 物质结构与性质模块综合检测
- “节能减排”背景下10 kV配电网能耗降低途径分析
- 大学物理学下册答案第12章
- 初二语文教案-语文八年级下人教版第21课《与朱元思书》教案5 精品
- 美孚公司标杆管理
- 联村联户宣传标语
- 6.分光光度法
- Zemax在《应用光学》中的应用研究
- 新编日语(1至4册)-语法
- 从\\"Made in China\\"到\\"Design in China\\"
- 诵读比赛主持词
- 2016-2020年中国城市燃气行业深度调研及投资前景预测报告 - 图文
- 安益238号渝南资产应收账款投资(一期)信托计划
- AETOS艾拓思:个人投资者在汇市上的生存之道
- 部编人教版八年级语文下册第1课《社戏》精品教案
- NOIP2014普及组复赛 螺旋矩阵
- 2008~2009学年第二学期九年级第一次月考
- 关于将环洞庭湖生态经济圈纳入国家发展战略的提案