[计算机软件及应用]数据结构线性表入门

《[计算机软件及应用]数据结构线性表入门》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2021/8/31算法与数据结构AlgorithmsandDataStructuresCH2线性表+++教授***信息技术大学计算机工程学院2.1基本概念与ADT2.2顺序表示2.3链接表示2.4应用举例2.5矩阵2.6广义表与动态存储管理提纲2021/8/312/1142.1基本概念与ADT2.2顺序表示2.3链接表示2.4应用举例2.5矩阵2.6广义表与动态存储管理2021/8/313/114线性结构：只有一个开始结点和一个结束结点，所有结点排成一个线性序列串、栈、队列都是线性结构线性表（简称为表）是零个或多个元素的有穷序列

2、。L=(k0,k1,…,kn-1)线性表的逻辑结构：L=其中K={k0,k1,…,kn-1}，R={

3、0≤i≤n-2}i称为元素ki的索引或下标基本概念2021/8/314/114表中所含元素的个数称为表的长度。长度为零的表称为空表。k0称为第一个元素，kn-1称为最后一个元素，ki(0≤i≤n-2)是ki+1的前驱，ki+1是ki的后继。k0只有一个后继，kn-1只有一个前驱2021/8/315/114例1：大写英文字母：(A,B,C,D,…,Z)1-10的整数：(1,2,3,4,…,10)例2：某院系的学生名册学号姓

4、名性别年龄专业名称……------------------------------------------------------------------------------------------------09001001张丰男17信息与计算科学09001002刘小红女18信息与计算科学09001003李静女18数学与金融工程09001004王建平男18数学与金融工程…………………2021/8/316/1142021/8/317/114某年南方GDP排名前20的城市同年南方GDP排名前20的城市List：线性表类型，DataType：元素类

5、型，Position：元素的下标类型。可说明如下:Listlist;DataTypex;Positionp;[注]元素的类型与讨论无关抽象数据类型(ADT)2021/8/318/114线性表的抽象数据类型(ADT)ADTListisoperationsListcreateNullList(void)//创建并且返回一个空线性表intinsertPre(Listlist,positionp,DataTypex)//在list中p位置前插入值为x的元素，并返回插入成功与否的标志intinsertPost(Listlist,positionp,DataT

6、ypex)//在list中p位置后插入值为x的元素，并返回插入成功与否的标志intdeleteV(Listlist,DataTypex)//在list中删除一个值为x的元素，并返回插入成功与否的标志2021/8/319/114intdeleteP(Listlist,positionp)//在list中删除位置为p的元素，并返回插入成功与否的标志。Positionlocate(Listlist,DataTypex)//在list中查找值为x的元素的位置。intisNull(Listlist)//判别list是否为空线性表。endADTList2021

7、/8/3110/1142.1基本概念与ADT2.2顺序表示2.3链接表示2.4应用举例2.5矩阵2.6广义表与动态存储管理2021/8/3111/114线性表最简单的存储方法是采用顺序方式，称作线性表的顺序表示，通常可称此时的线性表为顺序表具体做法是：将线性表中的元素一个接一个地存储在一片相邻的存储区域中。线性表的顺序存储结构是一种可以随机存取的存储结构。2021/8/3112/114假设每个元素占用c个存储单元，则下标为i+1的元素的存储位置与下标为i的元素的存储位置之间，满足下列关系：loc(ki+1)=loc(ki)+c通常把顺序表中k0的存

8、储位置loc(k0)，称为线性表的首地址或基地址，下标为i的元素ki的存储位置为：loc(ki)=loc(k0)+i*c存储结构2021/8/3113/1142021/8/3114/114顺序表定义(C语言)：2021/8/3115/114#defineMAXNUM100DataTypeelement[MAXNUM];#defineMAXNUM100intn;/*存放线性表中元素的个n≤MAXNUM*/DataType*element;/*element[0],element[1]，…，element[n-1]存放线性表中的元素*/设palist是

9、一个指向SeqList类型的指针变量，则：palist->MAXNUM：顺序表中最大元素的个数；palist->n：顺序表