资源描述：
《2第二章 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第二章线性表Chapter2LinearList数据结构课程——涉及数学、计算机硬件和软件数据结构定义——指相互有关联的数据元素的集合，用D_S=(D,R)表示数据结构内容——数据的逻辑结构、存储结构和运算算法效率指标——时间效率和空间效率要点回顾数据的逻辑结构数据的存储结构数据的运算线性结构非线性结构顺序存储链式存储线性表、栈、队列、串、数组树形结构图形结构散列存储索引存储插入、删除、修改、查找、排序等逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构线性表的逻辑结构线性表的顺序存储结构线性表的链式存
2、储结构（单链表）应用实例本章内容若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为：（a0,a1,……,an-1）线性结构的定义：线性结构的特点：①只有一个首结点和一个尾结点；②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型最常用的是------（a0,a1…ai-1，ai,ai＋1，…,an-1）2.1线性表的逻辑结构1.线性表的定义：用数据元素的有限序列表示n=0时
3、称为数据元素线性起点（首结点）ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置空表线性终点（尾结点）n为元素总个数，即表长例1分析26个英文字母组成的英文表（A,B,C,D,……,Z）学号姓名性别年龄班级09048001于春梅女18微电09109048002何仕鹏男18电子09109048003王爽女18通信09109048004王亚武男18通信091：：：：：例2分析学生情况登记表每个数据元素由5个数据项组成;元素之间的关系是线性的数据元素都是字母;元素之间的关系是线性的同一线性表
4、中的元素必定具有相同特性2.线性表的基本操作Initiate(L)初始化操作。建立一个空线性表L。Length(L)求表长。求给定线性表L中数据元素的个数。Get(L,i)读取元素。读取线性表L中第i个数据元素。Insert(L,i,x)前插。在线性表L中第i个数据元素ai之前插入一个新的数据元素x。Delete(L,i,x)删除。删除线性表L中第i个的数据元素,并将其保存在x中。Locate(L,x)定位函数。返回线性表L中元素值等于x的数据元素ai的序号i。2.2线性表的顺序存储结构—顺序表一、顺序
5、表用一组地址连续的存储单元存储线性表的各个数据元素，称作线性表的顺序存储结构，简称顺序表。顺序表的特点：1.逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标，参见存储结构示意图）。逻辑地址数据元素存储地址数据元素0a0Loc(a0)a01a1Loc(a0)+Ka1…………iaiLoc(a0)+i*Kai……n-1an-1Loc(a0)+(n-1)*Kan-1线性表的顺序存储结构示意图首地址每个元素占K字节一个一维数组Ｍ，下标的范围是０到
6、９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是98，则Ｍ[３]的第一个字节的地址是113例1：因此：LOC(M[3])=98+5×3=113解：地址计算通式为：LOC(ai)=LOC(a0)+L*i用c语言定义顺序表#defineMaxlen100typedefstruct{charname[10];charsex[3];intage;}elemtype;elemtypeList[Maxlen];intnum=-1;/*定义数据类型*//*定义顺序表*
7、//*最后一个数据元素的下标*//*顺序表最大长度*/姓名性别年龄张三男18李四女19………………typedefstruct{elemtypeList[Maxlen];intnum;}SeqList;LL->numL->List[0]L->List[1]L->List[2]…L->List[Maxlen-1]SeqLista;SeqList*L;a.num，a.List[0]……numList[0]List[1]…用c语言定义顺序表二、顺序表的基本操作1.初始化ListInitiate(L)voidLi
8、stInitiate(SeqList*L){L->num=-1;}/*num表示线性表最后一个元素的下标*/2.求表长ListLength(L)intListLength(SeqListL){returnL.num+1;}3.取数据元素ListGet(L，i，x)intListGet(SeqListL,inti,elemtype*x){if(i<0
9、
10、i>L.num){printf(“ERROR!”);return0;}else{*x=
