资源描述：
《线性表的课外课件.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.1顺序表顺序表的存储结构如下图所示：存储结构要体现数据的逻辑结构，顺序表的存储结构中，内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。顺序表类型的描述如下：ADTsequence_list{数据集合K：K={k1,k2,…,kn},n≥0，
3、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)intis_empty_sequence_list(sequence
5、_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_sequence_list(sequence_list*slt,intposition)}AD
6、Tsequence_list；2.2.2顺序表的实现用C语言中的数组存储顺序表。C语言中数组的下标是从0开始的，即数组中下标为0的元素对应的是顺序表中的第1个结点，数组中下标为i的元素对应的是顺序表中的第i+1个结点。为了方便，将顺序表中各结点的序号改为和对应数组元素的下标序号一致，即将顺序表中各结点的序号从0开始编号。这样，一个长度为n的顺序表可以表示为{k0,k1,k2,…,kn-1}顺序表的存储结构的C语言描述如下：/********************************//*顺序表的头文件，文件名sequlist.h*//*
7、*******************************/#defineMAXSIZE100typedefintdatatype;typedefstruct{datatypea[MAXSIZE];intsize;}sequence_list;顺序表的几个基本操作的具体实现：/********************************************//*顺序表的初始化---置空表*//*文件名seqlinit.c,函数名init_sequence_list()*//*****************************
8、**************/voidinit_sequence_list(sequence_list*slt){slt->size=0;}算法2.1顺序表的初始化---置空表/**********************************************//*在顺序表后部进行插入操作*//*文件名seqlinse.c,函数名insert_sequence_list()*//**********************************************/voidinsert_sequence_list(sequen
9、ce_list*slt,datatypex){if(slt->size==MAXSIZE){printf("顺序表是满的!");exit(1);}slt->size
