资源描述：
《数据结构第02章_线性表(I)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构李云清杨庆红揭安全第2章线性表及其顺序存储线性表是一种常用的数据结构，本章介绍线性表及其顺序存储，并对栈和队列及它们的顺序实现给出了详细的设计描述。2.1线性表线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：k1,k2,…,kn，其中k1是开始结点，kn是终端结点。2.2.1顺序表线性表采用顺序存储的方式存储就称之为顺序
2、表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。如顺序表的每个结点占用len个内存单元，用location(ki)表示顺序表中第i个结点ki所占内存空间的第1个单元的地址。则有如下的关系location(ki+1)=location(ki)+lenlocation(ki)=location(k1)+(i-1)len2.2顺序表顺序表的存储结构如下图所示：存储结构要体现数据的逻辑结构，顺序表的存储结构中，内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。顺序表类型的描述如下：ADTsequence_lis
3、t{数据集合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_list(sequence_list*slt,datatypex)后部插入值为x结点(3)voidprint_sequence_list(sequence_listslt)打印顺序表的各结点值(4)
5、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_list(sequence_list*slt,intposition,datatypex)(8)voiddelete_pos_sequen
6、ce_list(sequence_list*slt,intposition)}ADTsequence_list；2.2.2顺序表的实现用C语言中的数组存储顺序表。C语言中数组的下标是从0开始的，即数组中下标为0的元素对应的是顺序表中的第1个结点，数组中下标为i的元素对应的是顺序表中的第i+1个结点。为了方便，将顺序表中各结点的序号改为和对应数组元素的下标序号一致，即将顺序表中各结点的序号从0开始编号。这样，一个长度为n的顺序表可以表示为{k0,k1,k2,…,kn-1}顺序表的存储结构的C语言描述如下：/************
7、********************//*顺序表的头文件，文件名sequlist.h*//********************************/#defineMAXSIZE100typedefintdatatype;typedefstruct{datatypea[MAXSIZE];intsize;}sequence_list;顺序表的几个基本操作的具体实现：/********************************************//*顺序表的初始化---置空表*//*文件名seqlinit.c,
8、函数名init_sequence_list()*//*******************************************/voidinit_sequence_list(sequence_list*slt){slt->size=0;}算法2.1顺序表的初始化---置空表/**********************************************//*在顺序表后部进行插入操作*//*文件名seqlinse.c,函数名insert_sequence_list()*//****************
9、******************************/voidinsert_sequence_list(sequence_list*slt,datatypex){if(slt->size==MAXSIZE){printf("顺序表是满的!");exit(
