数据结构课件第2章线性表.ppt

《数据结构课件第2章线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性结构包括线性表、栈、队列、串、数组和广义表。其特点是：在数据元素的非空有限集合中存在惟一的一个被称作“第一个”的数据元素；存在惟一的一个被称作“最后一个”的数据元素；除第一个数据元素之外，集合中的每个数据元素均只有一个前驱；除最后一个数据元素之外，集合中的每个数据元素均只有一个后继。第2章线性表1第2章线性表22.1线性表的逻辑结构2.2线性表的顺序存储结构2.3线性表的链式存储结构2.4线性表两种存储结构比较2.1线性表的逻辑结构3例2-126个英文字母组成的字母表：（A，B，C，…，Z）是一个线性表，表中数据元素是单个字母字符。例2-2某校从1978年到1983年各种型号的计算机拥有

2、量的变化情况可以用一个线性表表示：（6，17，28，50，92，188）表中数据元素是整数。例2-3一个学校的学生健康情况登记表如下图所示。表中每个学生的情况为一个记录，它的姓名、学号、性别、年龄、班级和健康情况等六个数据项组成。姓名学号性别年龄班级健康情况王小林790631男18计91健康陈红790632女20计91一般刘建平790633男21计91健康张立立790634男17计91神经衰弱42.1线性表的逻辑结构2.1线性表的逻辑结构5线性表中的数据元素可以是各种各样的，但同一线性表中的元素必须具有相同的特性，即属同一数据对象，且相邻数据元素之间存在着序偶关系。线性表的定义线性表的基本操

3、作一个线性表（linear_list）是n（n≥0）个具有相同属性的数据元素的有限序列，其中各元素有着依次相邻的逻辑关系。线性表中数据元素的个数n称为线性表的长度。当n=0时该线性表称为空表。当n>0时该线性表可以记为：（a1，a2，a3，…，ai，…，an）62.1.1线性表的定义72.1.2线性表的基本操作InitList(L)操作结果：构造一个空的线性表L。DestroyList(L)初始条件：线性表L已存在。]操作结果：将L销毁。DelList(L,i,e)初始条件：线性表L已存在且非空，1≤i≤ListLength(L)操作结果：删除L的第i个数据元素，并用e返回其值,L的长

4、　　　　度减一。2.2线性表的顺序存储结构线性表的顺序存储表示8基本操作在顺序表上的实现线性表顺序存储的小结(1)定义用一组地址连续的存储单元依次存储线性表中的各个数据元素，称为线性表的顺序存储。92.2.1线性表的顺序存储表示12in空闲LOC(a1)LOC(a1)+kLOC(a1)+(i-1)kLOC(a1)+(n-1)k线性表的最大空间a1a2aian存储地址内存状态数据元素在线性表中的位序因为表中各数据元素具有相同的属性，所以占用的存储空间也相同。假设线性表中每个数据元素占用k个存储单元，第1个数据元素的起始地址为LOC(a1)，则：第2个数据元素的起始地址为：LOC(a2)=LOC

5、(a1)+k……第i个数据元素的起始地址为：LOC(ai)=LOC(a1)+(i-1)k(i=1,2,3,…,n)……第n个数据元素的起始地址：LOC(an)=LOC(a1)+(n-1)k——定位公式10(2)特点只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。顺序存储结构的特点是：逻辑上相邻的数据元素在物理存储上（在存储器中）也相邻。(1)定义用一组地址连续的存储单元依次存储线性表中的各个数据元素，称为线性表的顺序存储。112.2.1线性表的顺序存储表示(3)线性表的顺序存储结构可以使用一维数组来表示线性表的顺序存储结构

6、。线性表的顺序存储结构的Ｃ语言描述如下。12#defineMAXSIZE100/*此处的宏定义常量表示线性表可能达　　　　　　　　　到的最大长度*/typedefstruct{ElemTypeelem[MAXSIZE];/*线性表占用的数组空间*/intlast;}SeqList;/*顺序表的类型名*/数组指针，指示线性表的基地址。2.2.1线性表的顺序存储表示记录线性表中最后一个元素在数组elem[]中的位置(下标值),空表置-1(1)算法思想按序号查找GetData(L,i):要求查找线性表L中第i个数据元素,其结果是L.elem[i-1]或L->elem[i-1].按内容查找Locat

7、e(L,e):要求查找线性表L中与给定值e相等的数据元素,结果:若在表L中找到与e相等的元素,则返回该元素在表中的序号;若找不到,则返回一个”空序号”,如-1.132.2.2基本操作在顺序表上的实现1.查找操作(2)算法编写{i=0;/*i为扫描计数器,初值为0*/while((i<=L.last)&&(L.elem[i]!=e))/*顺序扫描线性表*/i++;intLocate(SeqListL,ElemT