线性表的逻辑结构及其基本操作.ppt

2020 3 26 1 线性表的逻辑结构及其基本操作线性表的顺序存储结构线性表的链式存储结构静态链表应用实例 第二章线性表 2020 3 26 2 2 1 线性表的逻辑结构及其基本操作 线性表是n n 0 个相同类型数据元素a0 a1 an 1构成的有限序列 形式化定义 Linearlist D R 其中 D0为某个数据对象的集合N为线性表长度 2020 3 26 3 线性表的主要操作 初始化求长度取元素定位插入删除 2020 3 26 4 例 利用线性表的基本运算实现清除L中多余的重复节点 PURGE Linear list L inti 1 j x y while i LENGTH L x GET L i j i 1 while j LENGTH L y GET L j if x y DELETE L j elsej i 2020 3 26 5 2 2线性表的顺序存储结构 顺序表 设线性表的基地址为 LOC a1 ai的存储地址为 LOC ai LOC a0 i k1 i n a0 a1 ai an 1 a0 a1 ai an 1 0 1 n 1 Loc a0 Loc a0 k i Loc a0 i k Loc a0 n 1 k 2020 3 26 6 线性表的定义为 typedefintdatatype 假定线性表元素的类型为整型 definemaxsize1024 假定线性表的最大长度为1024typedefstruct datatypedata maxsize intlast 指向最后结点的位置 sequenlist 2020 3 26 7 1 先定义结构类型 再定义变量名structstudent intnum charname 20 charsex intage floatscore charaddr 30 Structstudentstudent1 student2 C语言中定义结构的方法 2020 3 26 8 2 在声明类型的同时定义结构变量structstudent intnum charname 20 charsex intage floatscore charaddr 30 student1 student2 2020 3 26 9 3 直接定义结构变量struct intnum charname 20 charsex intage floatscore charaddr 30 student1 student2 2020 3 26 10 例 defineMAXSIZEtypedefstruct charName 20 charSex intAge floatfareAmount datatype 2020 3 26 11 线性表元素的插入 在线性表L中第i个位置前插入新元素x intINSERT sequenlist L datatypex inti intj if L last maxsize 1 printf overflow n returnNULL 溢出elseif i L last 1 printf error n returnNULL 非法位置else for j L last j i 1 j L data j 1 L data j L data i 1 x L last L last 1 return 1 2020 3 26 12 线性表元素的删除 在线性表L中删除第i个元素 intDELETE sequenlist L inti intj if i L last 1 printf error n returnNULL 非法位置else for j i j L last j L data j 1 L data j L last 表长减1 return 1 2020 3 26 13 1 插入n 22 删除 n 1 23 按序号检索O 1 4 按内容检索n 2 算法复杂性分析 2020 3 26 14 顺序表的优点 无须为表示节点间的逻辑关系而增加额外的存储空间可以方便的随机存取表中的任一节点顺序表的缺点 插入和删除运算不方便由于要求占用连续的存储空间 存储分配只能预先进行 2020 3 26 15 2 3线性表的链式存储 h h 不带头节点的链表 带头节点的链表 2020 3 26 16 单链表结点的定义 typedefintdatatype typedefstructnode datatypedata structnode next linklist 节点的申请p malloc sizeof linkist 节点的释放free p 2020 3 26 17 头插法建立单链表 head 建立新节点 向新节点中添入内容 使新节点指向链首 改变头指针 s 2020 3 26 18 头插法建立单链表linklist CREATELIST charch linklist head s head NULL ch getchar while ch s malloc sizeof linklist s data ch s next head head s ch getchar return head 2020 3 26 19 尾插法建立单链表 head 建立新节点 向新节点中添入内容 将新节点链入链尾 改变尾指针 s 2020 3 26 20 linklist CREATELISTR charch linklist head s r head NULL r NULL ch getchar while ch s malloc sizeof linklist s data ch if head NULL head s elser next s r s ch getchar 尾插法建立单链表 if r NULL r next NULL returnhead 2020 3 26 21 按序号查找linklist GET linklist head inti intj linklist p p head j 0 while p next NULL 2020 3 26 22 按值查找linklist LOCATE linklist head datatypekey linklist p p head next 头结点不属于表while p NULL if p data key p p next elsebreak returnp 2020 3 26 23 后插运算INSERTAFTER linklist p datatypex linklist s s malloc sizeof linklist s data x s next p next p next s 2020 3 26 24 单个节点的后插操作 建立新节点 向新节点中添入内容 将新节点链入链中 改变新节点前一节点的指针 s p 2020 3 26 25 前插运算INSERTBEFORE linklist head linklist p datatypex linklist s q s malloc sizeof linklist s data x q head while q next p q q next s next p q next s 2020 3 26 26 单个节点的前插操作 建立新节点 向新节点中添入内容 查找插入点 将新节点链入链中 改变新节点前一节点的指针 s q p 2020 3 26 27 改进的前插操作 s p a 2020 3 26 28 s p p x a 2020 3 26 29 单链表的插入运算INSERT linklist L datatypex inti linklist p intj j i 1 p GET L j if p NULL printf error n elseINSERTAFTER p x 2020 3 26 30 删除后继节点 存储池 r p 2020 3 26 31 删除后继结点DELETEAFTER linklist p linklist r r p next p next r next free r 删除运算DELETE linklist L inti linklist p intj j i 1 p GET L j if p NULL 2020 3 26 32 循环链表 head head 非空表 空表 rear rear 2020 3 26 33 采用尾指针的循环链表 rear 2020 3 26 34 两循环链表的链接 存储池 p 2020 3 26 35 两循环链表的链接linklist CONNECT linklist ra linklist rb linklist p p ra next ra next rb next next free rb next rb next p returnrb 2020 3 26 36 双链表结点的描述 typedefstructdnode datatypedata structdnode prior next dlinklist 2020 3 26 37 双链表的前插操作DINSERTBEFORE dlinklist p datatypex dlinklist s s malloc sizeof dlinklist s data x s prior p prior s next p p prior next s p prior s 2020 3 26 38 s p x a 2020 3 26 39 双链表的删除操作DELETENODEp dlinklist p p prior next p next p next prior p prior free p 2020 3 26 40 静态链表的定义如下 definemaxsize1024 存储池最大容量typedefintdatatype typedefintcursor typedefstruct 结点类型 datatypedata cursornext node nodenodepool maxsize 存储池cursorav 2020 3 26 41 初始化可用空间表avINITIALIZE inti for i 0 i maxsize 1 i nodepool i next i 1 nodepool maxsize 1 next NULL av 1 2020 3 26 42 1 2 3 4 NULL 1 data next av Maxsize 1 Maxsize 1 2020 3 26 43 结点的分配算法cursorGETNODE cursorp if av NULL p NULL else p av av nodepool av next returnp 2020 3 26 44 结点的回收算法FREENODE cursorp nodepool p next av av p 2020 3 26 45 静态链表查找算法cursorFINDSTLIST cursorL inti cursorp intj p L j 0 while nodepool p next NULL 2020 3 26 46 静态链表插入算法intINSERTSTLIST cursorL datatypex inti cursorp s p FINDSTLIST L i 1 if p NULL s GETNODE if s NULL printf error n returnNULL else nodepool s data x nodepool s next nodepool p next nodepool p next s return 1 else printf error n returNULL 2020 3 26 47 静态链表删除算法DELETESTLIST cursorL inti cursorp q p FINDSTLIST L i 1 if p NULL 2020 3 26 48 顺序表与链表的比较 1 基于空间的考虑2 基于时间的考虑3 基于语言的考虑 2020 3 26 49 应用实例 以单链表存储结构实现线性表的就地逆转1 全局变量法2 参数法 2020 3 26 50 la 单链表的逆转 la la la la p p q p p q p p p p 2020 3 26 51 linklist la Voidconvers1 linklist p q p la next la next NULL While p NULL q p p p next q next la next la next q 2020 3 26 52 Voidconvers2 linklist la linklist p q p la next la next NULL While p NULL q p p p next q next la next la next q 2020 3 26 53 例 在一个给定的线性表中删除元素值在x到y之间的所有元素 要求以较高的效率实现算法思想 先将向量A中所有在x到y之间的元素置成一个特殊的值0 并不立即删除它们 然后从最后向前依次扫描 删除为0的元素 移动后面的元素 2020 3 26 54 voiddel A n x y intA intn x y inti k for i 1 i x 2020 3 26 55 例 用不多于3n 2的平均比较次数 在一个线性表中找出最大和最小值的元素 voidmaxmin A n intA intn intmax min i for i 2 imax max A i elseif A i min min A i printf max d min d n max min 2020 3 26 56 分析 最坏情况 元素以递减顺序排列 A i max 和 A i max 均成立 不须进行 A i min 的比较 所以总的比较次数为 n 1 平均 2 n 1 n 1 2 3n