资源描述：
《数据结构与算法 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、第2章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4线性表的应用示例线性结构是最简单且最常用的一种数据结构。包括线性表、栈、队列、串。线性结构具有下列特点：存在一个唯一的没有前驱的（头）数据元素。存在一个唯一的没有后继的（尾）数据元素。此外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。线性结构2.1线性表的类型定义线性表由一组具有相同属性的数据元素构成。数据元素在不同的具体情况下，可以有不同的含义。在一些复杂的线性表中，每一个数据元素又可以由若干个数据项组成
2、，在这种情况下，通常将数据元素称为记录（record）。职工号姓名基本工资岗位工资奖金应发工资扣款实发工资1201张强54030020010402010201301周敏500200200900208801202徐黎芬55030020010503010201105黄承振53025020098020960┇┇┇┇┇┇┇┇例如，职工工资表每一个职工的工资是一个记录（数据元素）。每个记录包含八个数据项。如果n>0，则除a0和an-1外，有且仅有一个直接前趋和一个直接后继数据元素。如果n=0，则为一个空表，表示无数据元素
3、。一个线性表是n（n≥0）个数据元素a0，a1，a2，…，an-1的有限序列。综上所述：LinearList=(D,R)其中，D={ai
4、ai∈ElemSet,i=0,1,2,…，n-1n≥1}R={
5、ai-1，ai∈D,i=1,2,…，n-1}Elemset为某一数据对象集；n为线性表的长度。抽象数据类型线性表的定义如下：ADTList{数据对象：D={ai
6、ai∈ElemSet,i=1,2,…，nn≥0}数据关系：R={
7、ai-1，ai∈D,i=2,…，n}基本操作：In
8、itList(&L)DestroyList(&L)ClearList(&L)ListEmpty(L)ListLength(L)GetElem(L,i,&e)抽象数据类型线性表的定义如下：LocateElem(L,e,compare())PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)ListInsert(&L,i,e)ListDelete(&L,i,&e)ListTraverse(L,visit())}ADTList2.2线性表的顺序表示和实现一、线性表的顺序
9、存储结构二、线性表在顺序存储结构下的运算一、线性表的顺序存储结构在线性表的顺序存储结构中，其前后两个元素在存储空间中是紧邻的，且前驱元素一定存储在后继元素的前面。由于线性表的所有数据元素属于同一数据类型，所以每个元素在存储器中占用的空间大小相同线性表的顺序存储结构:在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素。假设线性表中的第一个数据元素的存储地址为Loc(a0)，每一个数据元素占d字节，则,线性表中第i个元素ai在计算机存储空间中的存储地址为：Loc(ai)=Loc(a0)+i*d这是因为数
10、组具有如下特点：（1）数据中的元素间的地址是连续的；（2）数组中所有元素的数据类型是相同的。这与线性表的顺序存储空间结构是类似的。在程序设计语言中，通常利用数组来表示线性表的顺序存储结构。二、线性表在顺序存储结构下的运算定义ElemType为int类型typedefintElemType;顺序表存储空间的总分配量#defineMAXSIZE100#defineTRUE1#defineFALSE0顺序存储类型typedefstruct{ElemTypedata[MAXSIZE];/*存放线性表的数组*/intle
11、ngth;/*length是顺序表的长度*/}SeqList;1.求顺序表长度intListLength(SeqListL){return(L.length);}2.检查顺序表是否为空intListEmpty(SeqListL){if(L.length)return(FALSE);elsereturn(TRUE);}3.遍历顺序表voidListTraverse(SeqListL){inti;if(L.length<=0)printf("顺序表为空");else{printf("当前顺序表中的元素为:"
12、);for(i=0;i<=L.length-1;i++)printf("%d",L.data[i]);printf("");}0，1，2，…，i-1,i,i+1,…,length-1lengthMAXSIZE4.从顺序表中查找元素ElemTypeGetElem(SeqListL,inti){ElemTypee;e=L.data[i-1];//第i个元素return(e);}0，1，
