第02章_线性表-顺序存储2009_9

第02章_线性表-顺序存储2009_9

ID:42715531

大小:306.50 KB

页数:57页

时间:2019-09-20

第02章_线性表-顺序存储2009_9_第1页
第02章_线性表-顺序存储2009_9_第2页
第02章_线性表-顺序存储2009_9_第3页
第02章_线性表-顺序存储2009_9_第4页
第02章_线性表-顺序存储2009_9_第5页
资源描述:

《第02章_线性表-顺序存储2009_9》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、第2章线性表及其顺序存储2.1线性表概念2.2顺序表2.2.1顺序表2.2.2顺序表的实现2.3栈2.3.1栈概念2.3.2顺序栈及其实现2.3.3栈的应用之一------括号匹配2.4队列2.4.1队列概念2.4.2顺序队列及其实现2.4.3顺序循环队列及其实现2.1线性表线性表是一个线性结构,它是一个含有n≥0个结点的有限序列,对于其中的结点,有且仅有一个开始结点没有前驱但有一个后继结点,有且仅有一个终端结点没有后继但有一个前驱结点,其它的结点都有且仅有一个前驱和一个后继结点。一般地,一个线性表可以表示成一个线性序列:k1,k2,…,kn,其中k1是开始结点,kn是终端结点。第2章线

2、性表及其顺序存储2.1线性表概念2.2顺序表2.2.1顺序表2.2.2顺序表的实现2.3栈2.3.1栈概念2.3.2顺序栈及其实现2.3.3栈的应用之一------括号匹配2.4队列2.4.1队列概念2.4.2顺序队列及其实现2.4.3顺序循环队列及其实现2.2.1顺序表线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。如顺序表的每个结点占用len个内存单元,用location(ki)表示顺序表中第i个结点ki所占内存空间的第1个单元的地址。则有如下的关系location(ki+1)=location(ki)+lenlocat

3、ion(ki)=location(k1)+(i-1)len2.2顺序表顺序表的存储结构如下图所示:存储结构要体现数据的逻辑结构,顺序表的存储结构中,内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。顺序表类型的描述如下:ADTsequence_list{数据集合K:K={k1,k2,…,kn},n≥0,K中的元素是datatype类型数据关系R:R={r},r={

4、i=1,2,…,n-1}操作集合:(1)voidinit_sequence_list(sequence_list*slt)顺序表的初始化------置空表(2)voidinsert_sequence_lis

5、t(sequence_list*slt,datatypex)后部插入值为x结点(3)voidprint_sequence_list(sequence_listslt)打印顺序表的各结点值(4)intis_empty_sequence_list(sequence_listslt)判断顺序表是否为空(5)intfind_num_sequence_list(sequence_listslt,datatypex)查找值为x结点位置(6)intget_data_pos(sequence_listslt,inti)取得顺序表中第i个结点的值(7)voidinsert_pos_sequence_lis

6、t(sequence_list*slt,intposition,datatypex)(8)voiddelete_pos_sequence_list(sequence_list*slt,intposition)}ADTsequence_list;2.2.2顺序表的实现用C语言中的数组存储顺序表。C语言中数组的下标是从0开始的,即数组中下标为0的元素对应的是顺序表中的第1个结点,数组中下标为i的元素对应的是顺序表中的第i+1个结点。为了方便,将顺序表中各结点的序号改为和对应数组元素的下标序号一致,即将顺序表中各结点的序号从0开始编号。这样,一个长度为n的顺序表可以表示为{k0,k1,k2,…

7、,kn-1}顺序表的存储结构的C语言描述如下:/********************************//*顺序表的头文件,文件名sequlist.h*//********************************/#defineMAXSIZE100typedefintdatatype;typedefstruct{datatypea[MAXSIZE];intsize;}sequence_list;顺序表的几个基本操作的具体实现:/********************************************//*顺序表的初始化---置空表*//*文件名seqli

8、nit.c,函数名init_sequence_list()*//*******************************************/voidinit_sequence_list(sequence_list*slt){slt->size=0;}算法2.1顺序表的初始化---置空表/**********************************************//*在顺序表后部进行插入操作*//*文件名

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。