资源描述：
《数据结构_ch2.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构DataStructure第2章线性表及线性表的顺序存储2.1线性表的定义2.2线性表的顺序存储结构（顺序表）2.3顺序表基本算法实现2.4顺序表的查找2.5插入与删除操作的效率分析2.6顺序表应用举例小结第一节线性表的定义2.1.1线性表实例1、需要准备一张大小适当的白纸2、登记预约情况3、取消预约（或已经用餐）4、将记录销毁或存档第一节线性表的定义2.1.1线性表实例创建一个空的线性表（准备一张白纸）插入一个新的元素（书写一个新顾客的信息）删除一个元素（划掉一个取消预定或已经就餐的顾客的信息）查找指定的元素（在划掉“约
2、翰”的信息之前，需要查找有关“约翰”的信息是否存在）清空线性表（将纸张销毁或存档）第一节线性表的定义2.1.2线性表的定义和基本操作线性表（LinearList）的定义：线性表是具有相同类型的n个数据元素组成的有限序列，通常记为(a1，a2，…ai-1，ai，ai+1，…an)。其中，ai是表中元素，n是表的长度，当n=0时线性表为空表。当n≠0时，a1是第一个元素，也称为表头元素，an是最后一个元素，也称为表尾元素。a1是a2的直接前驱元素，a2是a3的直接前驱元素，而a2是a1的直接后继元素，a3是a2的直接后继元素。第一节线
3、性表的定义2.1.2线性表的定义和基本操作线性表的基本操作包括：1、创建空的线性表；2、求线性表的长度；3、插入一个新的元素；4、删除一个元素；5、查找指定的元素；6、清空线性表。第一节线性表的定义2.1.3线性表的数学定义和逻辑图从集合论的观点出发，线性表是由两个集合构成的一个二元组。LinearList=(D,R)其中，D={ai
4、ai∈ElemSet,i=1,2,…,nn≥1}R={
5、ai,ai+1i∈D,i=1,2,…，n}Elemset为某一数据对象集；n为线性表的长度。n=0时，线性表为空表。第一节线
6、性表的定义2.1.3线性表的数学定义和逻辑图分数表=(D,R)D={99,100,88,76,89,56,96,98};R={<99,100>,<100,88>,<88,76>,<76,89>,<89,56>,<56,96>,<96,98>}第一节线性表的定义2.1.3线性表的数学定义和逻辑图学生名册表(“王雨”,“白雪”,“钱洋”,“赵纯”)的二元组表示是：名册表=(D,R)D={＂王雨＂,＂白雪＂,＂钱洋＂,＂赵纯＂};R={<＂王雨＂,＂白雪＂>,<＂白雪＂,＂钱洋＂>,<＂钱洋＂,＂赵纯＂>}第二节 线性表的顺序存储结构（
7、顺序表）下标从0开始下标从1开始第二节 线性表的顺序存储结构（顺序表）计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构，也称为顺序表（SequentialList）。intElement[MaxSize];/*存储线性表内容的数组*/intLength;/*线性表的长度*/第二节 线性表的顺序存储结构（顺序表）typedefintElemType;typedefstruct{ElemTypeElement[MaxSize];/*存储线性表内容的数组*/intLength;/*线性表的长度*/}
8、SeqList;/*说明List数据类型*/SeqListList;/*定义顺序表List*/第二节 线性表的顺序存储结构（顺序表）typedefintElemType;typedefstruct{ElemTypeElement[MaxSize];/*存储线性表内容的数组*/intLength;/*线性表的长度*/}SeqList;/*说明List数据类型*/SeqListList;/*定义顺序表List*/第三节 顺序表基本算法实现2.3.1线性表内容与线性表长度分别存储的算法实现intElement[MaxSize];/*存储
9、线性表的数据元素*/intLength;/*线性表长度*/1．构造一个空表算法2.1构造一个空表voidInit_SeqList(int*Length_pointer)/*构造一个空表*/{*Length_pointer=0;}2．插入一个元素（尾插）算法2.2插入一个元素（尾插）intInsert_Last(intElement[],int*Length_pointer,intx)/*插入一个元素(尾插)*/{if(*Length_pointer==MaxSize){printf("表满");returnOverFlow;}el
10、se{Element[*Length_pointer]=x;/*在表尾插入一个元素*/(*Length_pointer)++;/*线性表长度加1*/returnOK;/*插入成功，返回*/}}3．查找指定元素算法2.3查找指定元素xintLocat
