第02章线性表A.ppt

《第02章线性表A.ppt》由会员分享，可在线阅读，更多相关《第02章线性表A.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第1章章绪论绪论第第2章章线性表线性表第第3章章栈和队列栈和队列第第4章章串串第第5章章数组和广义表数组和广义表第第6 6章章 树和二叉树树和二叉树第第7章章图图第第9章章查找查找第第10章章排序排序目目 录录1数据结构课程的起点数据结构课程的起点什么是什么是线性结线性结构？构？2线性结构的定义：线性结构的定义：若若结结构构是是非非空空有有限限集集，则则有有且且仅仅有有一一个个开开始始结结点点和和一一个个终终端端结结点点，并并且且所所有有结结点点都都最最多多只只有有一一个个直直接接前趋和一个直接后继。前趋和一个直接后继。可表示为：（可表示为：（a1,a2,an）简言，线性结构反映结点间的逻辑

2、关系是简言，线性结构反映结点间的逻辑关系是。特点特点 只有一个首结点和尾结点；只有一个首结点和尾结点；特特点点 除除首首尾尾结结点点外外，其其他他结结点点只只有有一一个个直直接接前前驱驱和一个直接后继。和一个直接后继。线性结构包括：线性结构包括：线性表、堆栈、队列、字符串、数组线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是等，其中最典型、最常用的是-线性表线性表一对一一对一(1:1)(1:1)3第2章 线性表2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构 2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现线性表的顺序表示和实现线性表的顺序

3、表示和实现2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现线性表的链式表示和实现线性表的链式表示和实现2.4 2.4 应用举例应用举例应用举例应用举例4（a1,a2,ai-1，ai,ai1，,an）2.1线性表的逻辑结构线性表的逻辑结构线性表的定义：线性表的定义：线性表的定义：线性表的定义：用数据元素的有限序列表示用数据元素的有限序列表示n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总为元素总个数，即表个数，即表长。长。n0n0空表空表线性终点

4、线性终点5 （A,B,C,D,ZA,B,C,D,Z）学号学号学号学号姓名姓名姓名姓名性别性别性别性别年龄年龄年龄年龄班级班级班级班级012003010622012003010622陈建武陈建武陈建武陈建武男男男男 19 1920032003级电信科级电信科级电信科级电信科03010301班班班班012003010704012003010704赵玉凤赵玉凤赵玉凤赵玉凤女女女女 18 1820032003级电信科级电信科级电信科级电信科03020302班班班班012003010813012003010813王王王王 泽泽泽泽男男男男 19 1920032003级电信科级电信科级电信科级电信科030

5、30303班班班班012003010906012003010906薛薛薛薛 荃荃荃荃男男男男 19 1920032003级电信科级电信科级电信科级电信科03040304班班班班012003011018012003011018王王 春春男男 1919191920032003级电信科级电信科级电信科级电信科03050305班班班班：例例2分析学生情况登记表是什么结构。分析学生情况登记表是什么结构。分析：分析：数据元素都是同类型（数据元素都是同类型（记录记录），元素间关系是线性的。），元素间关系是线性的。分析：分析：数据元素都是同类型（数据元素都是同类型（字母字母），），元素间关系是线性的。元素间关

6、系是线性的。注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性！例例1分析分析26个英文字母组成的英文表是什么结构。个英文字母组成的英文表是什么结构。6“同同同同一一一一数数数数据据据据逻逻逻逻辑辑辑辑结结结结构构构构中中中中的的的的所所所所有有有有数数数数据据据据元元元元素素素素都都都都具具具具有有有有相相相相同同同同的的的的特特特特性性性性”是是是是指指指指数数数数据据据据元元元元素素素素所所所所包包包包含含含含的的的的数数数数据据据据项项项项的的的的个个个个数数数数都都都都相相相

7、相等。等。等。等。是指各元素具有相同的数据类型是指各元素具有相同的数据类型是指各元素具有相同的数据类型是指各元素具有相同的数据类型试判断下列叙述的正误：试判断下列叙述的正误：72.2线性表的顺序表示和实现线性表的顺序表示和实现2.2.1顺序表的表示顺序表的表示2.2.2顺序表的实现顺序表的实现2.2.3顺序表的运算效率分析顺序表的运算效率分析82.2.12.2.1顺序表的表示顺序表的表示顺序表的表示顺序表的表示用用用用一一一一组组组组地地地地址址址址连连连连续续续续的的的的存存存存储储储储单单单单元元元元依依依依次次次次存储线性表的元素存储线性表的元素存储线性表的元素存储线性表的元素。把逻辑上

8、相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。理上相邻的存储单元中的存储结构。线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或顺序映像。或顺序映像。顺序存储定义：顺序存储定义：顺序存储方法：顺序存储方法：特点：特点：逻辑上相邻的元素，物理上也相邻逻辑上相邻的元素，物理上也相邻可以利用可以利用数组数组VnVn来实现来实现注意：在注意：在C C语言中数组的下标是从语言中数组的下标是从0 0开始，即：开始，即：VnVn的有效范围是从的有效范围是从 V0V0Vn-1Vn-191.1.逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，

9、其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；2.2.若已知表中首元素在存储器中的位置，则其他元若已知表中首元素在存储器中的位置，则其他元若已知表中首元素在存储器中的位置，则其他元若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出素存放位置亦可求出素存放位置亦可求出素存放位置亦可求出（利用数组利用数组利用数组利用数组VnVn的的的的下标下标下标下标）。设首元素设首元素a1的存放地址为的存放地址为LOC(a1)（称为称为首地址首地址），），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元

10、素的则表中任一数据元素的存放地址存放地址为：为：LOC(ai+1)=LOC(ai)+LLOC(LOC(a ai i)=LOC()=LOC(a a11)+L*)+L*（i-1i-1）对上述公式的解释如图所示对上述公式的解释如图所示线性表顺序存储特点：线性表顺序存储特点：10a a a a1 1 1 1a a a a2 2 2 2a a a ai i i ia a a ai+1i+1i+1i+1a a a an n n n 地址地址 内容内容 元素在表中的位序元素在表中的位序1 1i i2 2n n空闲区空闲区i+1i+1Lb=LOC(a1)b+L Lb+(i-1)+(i-1)L Lb+(n-1)

11、+(n-1)L Lb+(max-1)+(max-1)L LLOC(LOC(a ai i)=LOC(a)=LOC(a11)+L*)+L*（i i-1-1）线性表的顺序存储结构示意图线性表的顺序存储结构示意图下标起下标起点是点是1 111设有一维数组设有一维数组设有一维数组设有一维数组，下标的范围是，下标的范围是，下标的范围是，下标的范围是到到到到，每个，每个，每个，每个数组元素用相邻的数组元素用相邻的数组元素用相邻的数组元素用相邻的个字节个字节个字节个字节存储。存储器按字节编存储。存储器按字节编存储。存储器按字节编存储。存储器按字节编址，设存储数组元素址，设存储数组元素址，设存储数组元素址，设存

12、储数组元素 的第一个字节的地址是的第一个字节的地址是的第一个字节的地址是的第一个字节的地址是98989898，则，则，则，则 的第一个字节的地址是多少？的第一个字节的地址是多少？的第一个字节的地址是多少？的第一个字节的地址是多少？答案：答案：113但此题要注意下标起点是从但此题要注意下标起点是从0 0开始：开始：LOC(M3)=98+5(4-1)=113解：解：已知地址计算通式为：已知地址计算通式为：LOC(ai)=LOC(a1)+L*（i-1）例例112charV30;voidbuild()/*字母线性表的生成，即字母线性表的生成，即建表操作建表操作*/inti;V0=a;for(i=1;i

13、=n-1;i+)Vi=Vi-1+1;核心语句：核心语句：法法法法1Vi=Vi-1+1;1Vi=Vi-1+1;法法法法2Vi=a+i;2Vi=a+i;法法法法3Vi=97+i;3Vi=97+i;例例2用数组用数组V来存放来存放26个英文字母组成的线性表（个英文字母组成的线性表（a，b，c，z），），写出在顺序结构上写出在顺序结构上生成生成和和显示显示该表的该表的C语言程序。语言程序。省略了省略了includeinclude语句语句13voidmain()/*主函数主函数，字母线性表的，字母线性表的生成和输出生成和输出*/n=26;/*n n是表长，是数据元素的个数，而不是是表长，是数据元素的个数

14、，而不是V V的的 实际下标实际下标*/build();display();voiddisplay()/*字母线性表的显示，即字母线性表的显示，即读表操作读表操作*/inti;for(i=0;i=i;j-)aj+1=aj;ai=x;n+;/元素后移一个位置元素后移一个位置/插入插入x x/表长加表长加1 1 核核心心语语句句2)2)插入插入:16在线性表的第在线性表的第i i个位置前插入一个元素的示意图：个位置前插入一个元素的示意图：121213132121242428283030424277771212131321212424252528283030424277771 12 23 34 45

15、 56 67 78 81 12 23 34 45 56 67 78 89 9插入插入2525252517实现步骤：实现步骤：实现步骤：实现步骤：n n将第将第将第将第i+1i+1 至第至第至第至第n n 位的元素向前移动一个位置；位的元素向前移动一个位置；位的元素向前移动一个位置；位的元素向前移动一个位置；n n表长减表长减表长减表长减1 1。注意：事先需要判断，注意：事先需要判断，注意：事先需要判断，注意：事先需要判断，删除位置删除位置删除位置删除位置i i 是否合法是否合法是否合法是否合法?应当符合条件：应当符合条件：应当符合条件：应当符合条件：1in 1in 或或或或 i=1,ni=1,

16、n删除删除线性表的第线性表的第i i个位置上的元素个位置上的元素for(j=i+1;j=n;j+)aj-1=aj;n-;/元素前移一个位置元素前移一个位置/表长减表长减1 1 核心语句：核心语句：3)3)删除删除:181 12 23 34 45 56 67 78 89 91212131321212424252528283030424277771 12 23 34 45 56 67 78 812121313212124242828303042427777删除顺序表中某个指定的元素的示意图：删除顺序表中某个指定的元素的示意图：顺序表插入和删除的完整程序请同学们自编。顺序表插入和删除的完整程序请同学

17、们自编。192.2.32.2.3顺序表的运算效率分析顺序表的运算效率分析顺序表的运算效率分析顺序表的运算效率分析n n算法时间主要耗费在算法时间主要耗费在算法时间主要耗费在算法时间主要耗费在移动元素移动元素移动元素移动元素的操作上，因此计的操作上，因此计的操作上，因此计的操作上，因此计算时间复杂度的基本操作（最深层语句频度）算时间复杂度的基本操作（最深层语句频度）算时间复杂度的基本操作（最深层语句频度）算时间复杂度的基本操作（最深层语句频度）T(n)=OT(n)=O(移动移动移动移动元素次数元素次数元素次数元素次数)而移动元素的个数取决于插入或删除元素的位置而移动元素的个数取决于插入或删除元素

18、的位置而移动元素的个数取决于插入或删除元素的位置而移动元素的个数取决于插入或删除元素的位置.思考：思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；若插入在首结点之前，则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共应当考虑在各种位置插入（共n+1种可能）的种可能）的平均平均移动次数才移动次数才合理。合理。讨论讨论1：若在长度为若在长度为n的线性表的第的线性表的第i位前位前插入插入一个一个元素，则向后移动元素的次数元素，则向后移动元素的次数f(n)为为:f(n)=ni+1时间效率时间效

19、率分析分析:20推推导导：假假定定在在每每个个元元素素位位置置上上插插入入x的的可可能能性性都都一一样样（即概率（即概率P相同），则应当这样来计算平均执行时间：相同），则应当这样来计算平均执行时间：将所有位置的执行时间相加，然后取平均。将所有位置的执行时间相加，然后取平均。将所有位置的执行时间相加，然后取平均。将所有位置的执行时间相加，然后取平均。若在首结点前插入，需要移动的元素最多，后移次数为若在首结点前插入，需要移动的元素最多，后移次数为n；若在若在a1后面插入，要后移后面插入，要后移n-1个元素，后移次数为个元素，后移次数为n-1;若在若在an-1后面插入，要后移次数为后面插入，要后移次

20、数为1；若在尾结点若在尾结点an之后插入，则后移次数为之后插入，则后移次数为0；故插入时的平均移动次数为：故插入时的平均移动次数为：n(n+1)/2（n+1）n/2O(n)共有多少种插入形式共有多少种插入形式?连头带尾有连头带尾有n+1种种!所有可能的元素移动次数合计所有可能的元素移动次数合计：0+1+n=n(n+1)/221同理可证：同理可证：顺序表删除一元素的时间效率为顺序表删除一元素的时间效率为:T（n)=(n-1)/2O(n)O(n)想一想：想一想：想一想：想一想：顺序表插入、删除算法的顺序表插入、删除算法的平均平均空间空间复杂度复杂度为多少？为多少？插入插入效率：效率：删除删除效率：

21、效率：教材教材教材教材P25P25算法算法算法算法2.52.5也是对执行效率的推导：也是对执行效率的推导：也是对执行效率的推导：也是对执行效率的推导：因为没有因为没有占用辅助占用辅助空间！空间！O(1)O(1)即插入、删除算法的平均时间复杂度为即插入、删除算法的平均时间复杂度为O(n)22课堂讨论课堂讨论n n顺序表各种操作算法的顺序表各种操作算法的“通式通式”该如何书写该如何书写？采用采用抽象数据类型抽象数据类型来表示来表示顺序表的存储结构是一维数组，如果插入的顺序表的存储结构是一维数组，如果插入的元素个数元素个数超过超过数组定义的数组定义的长度长度怎么办？怎么办？采用采用动态分配动态分配的

22、一维数组的一维数组23线性表的抽象数据类型定义线性表的抽象数据类型定义（见教材（见教材（见教材（见教材P19P19）ADTList数据对象：数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：数据关系：R1=|ai1,aiD,i=2,n基本操作：基本操作：n n初始化、撤销、清空、判空；初始化、撤销、清空、判空；初始化、撤销、清空、判空；初始化、撤销、清空、判空；n n求表长、表头、表尾、前趋、后继；求表长、表头、表尾、前趋、后继；求表长、表头、表尾、前趋、后继；求表长、表头、表尾、前趋、后继；n n读元素、查找（含定位）、遍历；读元素、查找（含定位）、遍历；读元素、查找（含

23、定位）、遍历；读元素、查找（含定位）、遍历；n n插入、删除插入、删除插入、删除插入、删除ADTList24线性表的基本操作如何表示？线性表的基本操作如何表示？线性表的基本操作如何表示？线性表的基本操作如何表示？（见教材（见教材（见教材（见教材P19P19）InitList(&L);/建空表，初始化建空表，初始化DestoryList(&L);/撤销表，释放内存撤销表，释放内存intLengthList(L);/求表中元素个数，即表长求表中元素个数，即表长LocateElem(L,e，compare()/查找查找ePriorElem(L,cur_e,&pre_e);/求当前元素求当前元素e的前

24、驱的前驱NextElem(L,cur_e,&next_e);/求当前元素求当前元素e的的后继后继ListInsertBefore(&L,i,e);/把把e插入插入到第到第i个元素之前个元素之前ListDelete(&L,i,&e);/删除删除第第i个元素并个元素并“看看”此元素此元素ListTraverse(L,Visit();/“看看”表中全部元素（遍历）表中全部元素（遍历）l初始化、撤销、清空、判空；初始化、撤销、清空、判空；l求表长、表头、表尾、前趋、后继；求表长、表头、表尾、前趋、后继；l读元素、查找（含定位）、遍历；读元素、查找（含定位）、遍历；l插入、删除插入、删除25顺序表操作的

25、典型例子顺序表操作的典型例子教材教材例例2-1：求两个线性表的：求两个线性表的“并并”，即：，即：LAULB=?算法至少有两种：算法至少有两种：LA和和LB都是都是无序表无序表，则从，则从LB中取元素逐一与中取元素逐一与LA中所有元素比较，相同则不插入中所有元素比较，相同则不插入LA中；中；若若LA和和LB已经是已经是有序表有序表，则，则“归并归并”的时间的时间效率可以大大提高。效率可以大大提高。26动态数组简介先为顺序表空间设定一个初始分配量，一旦因先为顺序表空间设定一个初始分配量，一旦因先为顺序表空间设定一个初始分配量，一旦因先为顺序表空间设定一个初始分配量，一旦因插入元素而插入元素而插入

26、元素而插入元素而空间不足空间不足空间不足空间不足时，可为顺序表增加一个时，可为顺序表增加一个时，可为顺序表增加一个时，可为顺序表增加一个固定长固定长固定长固定长度的空间增量度的空间增量度的空间增量度的空间增量。#defineLIST_INIT_SIZE100/存储空间的初始分配量存储空间的初始分配量#defineLISTINCREMENT10/存储空间的分配增量存储空间的分配增量typedefstructElemType*elem;/表基址表基址(用指针用指针*elem表示表示）intlength;/表长度表长度（表中有多少个元素表中有多少个元素）intlistsize;/当前分配的表尺寸当前

27、分配的表尺寸（字节单位字节单位）SqList;注：三个分量可简写为：注：三个分量可简写为：L.elemL.lengthL.listsize存储结构描述如下（存储结构描述如下（见教材见教材P22P22）：）：数据类数据类型待定型待定27sizeof(x)算符：计算变算符：计算变量量x的长度的长度(字节数字节数)malloc(m)函数：新开一片大小函数：新开一片大小为为m字节字节的连续空间，并把该的连续空间，并把该区首址作为函数返回值。区首址作为函数返回值。StatusInitList_Sq(SqList&L)/创建一个空线性表创建一个空线性表L.elem=(ElemType*)malloc(LI

28、ST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);/分配失败，结束程序分配失败，结束程序L.length=0;/暂无元素放入，空表暂无元素放入，空表L.listsize=LIST_INIT_SIZE;/表尺寸表尺寸=初始初始分配量分配量returnOK;/InitList_S动态创建一个动态创建一个动态创建一个动态创建一个空空空空顺序表的算法：顺序表的算法：顺序表的算法：顺序表的算法：28realloc(*p,newsize)函数：新开一片大函数：新开一片大小为小为newsize的的连续空间连续空间，并把以，并把以*p为首为首址的原

29、空间数据都拷贝进去。址的原空间数据都拷贝进去。动态顺序表的插入算法动态顺序表的插入算法动态顺序表的插入算法动态顺序表的插入算法StatusListInsert_Sq(SqList&L,inti,ElemTypee)/在顺序线性表中第在顺序线性表中第i i个位置个位置之前之前插入新的元素插入新的元素e eif(iL.length+1)returnERROR;/检验检验i值的合法性值的合法性if(L.length L.listsize)/若表长超过表尺寸则要增加尺寸若表长超过表尺寸则要增加尺寸 newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTLI

30、STINCREMENTINCREMENT)*sizeof(ElemType);if(newbase=NULL)exit(OVERFLOW);/分配失败则退出并分配失败则退出并报错报错L.elem=newbase;/重置新基址重置新基址L.listsize=L.listsize+LISTINCREMENTLISTINCREMENT;/增加表尺寸增加表尺寸29q=&L.elemi-1;/q为插入位置为插入位置for(p=&L.elemL.length-1;p=q;-p)*(p+1)=*p;/插入位置及之后的元素统统后移插入位置及之后的元素统统后移,p为元素位为元素位置置*q=e;/插入插入e+L.

31、length;/增加增加1个数据元素，则表长个数据元素，则表长+1returnOK;/ListInsert_Sq动态数组的核心是动态数组的核心是reallocrealloc(void(void*ptrptr,newsizenewsize)函数！函数！30动态顺序表的删除算法动态顺序表的删除算法动态顺序表的删除算法动态顺序表的删除算法StatusListDelete_Sq(SqList&L,inti,ElemType&e)/在顺序表在顺序表L中删除第中删除第i个元素，用个元素，用e返回其值返回其值if(iL.length)returnERROR;/i值不合法，返回值不合法，返回p=&L.elem

32、i-1;/p是被删除元素的位置是被删除元素的位置e=*p;/被删除元素的值赋给被删除元素的值赋给eq=L.elem+L.length-1;/q是表尾的位置是表尾的位置for(+p;p=q;p+)*(p-1)=*p;/待删元素后面的统统前移待删元素后面的统统前移-L.length;/表长表长-1returnOK;/ListDelete_Sq31链式存储结构链式存储结构2.22.2节小结节小结线性表线性表顺序存储结构特点顺序存储结构特点：逻辑关系上相邻的两个元：逻辑关系上相邻的两个元素在物理存储位置上也相邻；素在物理存储位置上也相邻；优点：优点：可以随机存取表中任一元素，方便快捷；可以随机存取表中任一元素，方便快捷；缺点：缺点：在插入或删除某一元素时，需要移动大量元素。在插入或删除某一元素时，需要移动大量元素。解决问题的思路：解决问题的思路：改用另一种线性存储方式：改用另一种线性存储方式：32