数据结构线性表A学习教案.pptx

《数据结构线性表A学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构线性表A学习教案.pptx（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构(sh j ji u)线性表线性表A第一页，共33页。2 2(2，3，4，J，Q，K，A）学号学号姓名姓名性别性别年龄年龄班级班级2001011810205管春燕管春燕女女 182001级电信级电信016班班2001011810260周周 刚刚男男 182001级电信级电信017班班2001011810284石文娟石文娟女女 182001级通信级通信011班班2001011810360杨杨 扬扬男男 182001级通信级通信012班班：生活(shnghu)实例：第1页/共33页第二页，共33页。3 3简言之，线性结构(jigu)反映结点间的逻辑关系是 一对一(1:1)的线性结构

2、特点：在数据元素(yun s)的非空有限集中存在唯一的一个被称作“第一个”的数据元素(yun s)存在唯一的一个被称作“最后一个”的数据元素(yun s)除第一个元素(yun s)外，集合中的每个数据元素(yun s)均只有一个前驱除最后一个元素(yun s)外，集合中的每个数据元素(yun s)均只有一个后继若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为：（a1,a2 ,an）线性结构的定义：第2页/共33页第三页，共33页。4 4（逻辑、存储(cn ch)和运算）线性结构包括线性表、堆栈、队列(duli)、字符串、数组等

3、等，其中，最典型、最常用的是-线性表第2章第3页/共33页第四页，共33页。第第2章章 线性表线性表2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构 2.2 2.2 线性表的顺序线性表的顺序线性表的顺序线性表的顺序(shnx)(shnx)表示表示表示表示和实现和实现和实现和实现2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现线性表的链式表示和实现线性表的链式表示和实现2.4 2.4 应用举例应用举例应用举例应用举例 第4页/共33页第五页，共33页。6 6（a1,a2,ai-1，ai,ai1，,an）2.1 线性表的逻辑线性表的逻辑(lu j)结构结

4、构 2.1.1 线性表的定义：用数据(shj)元素的有限序列表示n=0时称为(chn wi)数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表线性终点第5页/共33页第六页，共33页。7 7例例例例1 1 分析一副扑克分析一副扑克分析一副扑克分析一副扑克(p k)(p k)的点数组成的英文的点数组成的英文的点数组成的英文的点数组成的英文表表表表(2(2，3 3，4 4，J J，QQ，K K，A A）例2 分析学生(xu sheng)情况登记表数据元素都是记录(jl);元素间关系是线性数据元素都是牌面点数;元素间关系是线性同一线性表中的

5、元素必定具有相同特性学号学号姓名姓名性别性别年龄年龄班级班级2001011810205管春燕管春燕女女 182001级电信级电信016班班2001011810260周周 刚刚男男 182001级电信级电信017班班2001011810284石文娟石文娟女女 182001级通信级通信011班班2001011810360杨杨 扬扬男男 182001级通信级通信012班班：第6页/共33页第七页，共33页。8 8练：判断练：判断练：判断练：判断(pndun)(pndun)下列叙述的正下列叙述的正下列叙述的正下列叙述的正误：误：误：误：1.线线性性表表的的逻逻辑辑(lu j)结结构构定定义义是唯一的，

6、不依赖于计算机。是唯一的，不依赖于计算机。2.线线性性结结构构反反映映结结点点间间的的逻逻辑辑(lu j)关系是一对一的。关系是一对一的。3.一一维维数数组组是是线线性性表表，但但二二维维或或N维数组不是。维数组不是。4.“同同一一数数据据逻逻辑辑(lu j)结结构构中中的的所所有有数数据据元元素素都都具具有有相相同同的的特特性性”是是指指数数据据元元素素所所包包含含的的数据项的个数都相等。数据项的个数都相等。第7页/共33页第八页，共33页。9 92.2 线性表的顺序线性表的顺序(shnx)表表示和实现示和实现2.2.1 顺序表的表示2.2.2 顺序表的实现2.2.3 顺序表的运算(yn s

7、un)效率分析顺序(shnx)表小结第8页/共33页第九页，共33页。10102.2.1 2.2.1 顺序顺序顺序顺序(shnx)(shnx)表表表表的表示的表示的表示的表示用用用用一一一一组组组组地地地地址址址址连连连连续续续续的的的的存存存存储储储储单单单单元元元元依依依依次次次次(yc)(yc)(yc)(yc)存储线性表的元素，可通过数组存储线性表的元素，可通过数组存储线性表的元素，可通过数组存储线性表的元素，可通过数组VnVnVnVn来实现。来实现。来实现。来实现。把逻辑上相邻的数据元素存储在物理上相邻的存储单元(cn ch dn yun)中的存储结构。线性表的顺序表示又称为顺序存储结

8、构或顺序映像。顺序存储定义：顺序存储方法：简言之，逻辑上相邻，物理上也相邻第9页/共33页第十页，共33页。1111线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构(jigu)(jigu)示意示意示意示意图图图图a a1 1a a2 2a ai ia ai+1i+1a an n 地址(dzh)内容 元素在表中的位序1i2n空闲(kngxin)区i+1Lb=LOC(a1)b+Lb+(i-1)Lb+(n-1)L第10页/共33页第十一页，共33页。1212线性表顺序存储特点线性表顺序存储特点线性表顺序存储特点线性表顺序存储特点(tdin)(tdin)：1.1.逻辑逻

9、辑逻辑逻辑(lu j)(lu j)上相邻的数据元素，其物理上也相邻；上相邻的数据元素，其物理上也相邻；上相邻的数据元素，其物理上也相邻；上相邻的数据元素，其物理上也相邻；2.2.若已知表中首元素在存储器中的位置，则其他元素若已知表中首元素在存储器中的位置，则其他元素若已知表中首元素在存储器中的位置，则其他元素若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）。计算方法是存放位置亦可求出（利用数组下标）。计算方法是存放位置亦可求出（利用数组下标）。计算方法是存放位置亦可求出（利用数组下标）。计算方法是（参见存储结构示意图）：（参见存储结构示意图）：（参见存储结构示意图）

10、：（参见存储结构示意图）：设首元素设首元素设首元素设首元素a1a1的存放地址为的存放地址为的存放地址为的存放地址为LOC(a1)LOC(a1)（称为首地址），（称为首地址），（称为首地址），（称为首地址），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L L字节，字节，字节，字节，则表中任一数据元素的存放地址为：则表中任一数据元素的存放地址为：则表中任一数据元素的存放地址为：则表中任一数据元素的存放地址为：LOC(ai)=LOC(a1)+L*LOC(ai)=LOC(a1)+L*（i-1i-1）LO

11、C(ai+1)=LOC(ai)+L LOC(ai+1)=LOC(ai)+L 注意：Java语言(yyn)中的数组的下标从0开始，即：Vn的有效范围是V0Vn-1第11页/共33页第十二页，共33页。1313一个一维数组，下标的一个一维数组，下标的范围是到，每个数组元素范围是到，每个数组元素用相邻的个字节用相邻的个字节(z ji)(z ji)存存储。存储器按字节储。存储器按字节(z ji)(z ji)编编址，设存储数组元素址，设存储数组元素 的的起始地址是，则起始地址是，则 的的起始地址是起始地址是 113例例例例1因此(ync)：LOC(M3)=98+5(3-0)=113解：地址(dzh)计算

12、通式为：LOC(ai)=LOC(a1)+L*（i-1）第12页/共33页第十三页，共33页。14142.2.2 2.2.2 顺序表的实现顺序表的实现顺序表的实现顺序表的实现(shxin)(shxin)（或操作）（或操作）（或操作）（或操作）回忆(huy)：数据结构基本运算操作有：修改、插入、删除、查找、排序1)修改 通过(tnggu)数组的下标便可访问某个特定元素并修改之。核心语句:Vi=x;显然，顺序表修改操作的时间效率是T(n)=O(1)第13页/共33页第十四页，共33页。15152)插入(ch r)在线性表的第 i个位置前插入(ch r)一个元素在线性表的第i个位置(wi zhi)前插

13、入一个元素的示意图如下：121321242830427712132124252830427712345678123456789插入(ch r)25第14页/共33页第十五页，共33页。1616实现步骤：？将第n至第i 位的元素向后移动一个位置(wi zhi)；将要插入的元素写到第i个位置(wi zhi)；表长加1。注意：事先应判断:插入位置(wi zhi)i 是否合法?表是否已满?应当有1in+1 或 i=1,n+1for(j=n;j=i;j-)aj+1=aj;ai=x;n+;/元素后移一个(y)位置/插入(ch r)x/表长加1 核心语句：第15页/共33页第十六页，共33页。17173)删

14、除 删除线性表的第 i个位置(wi zhi)上的元素123456789121321242528304277123456781213212428304277删除(shnch)顺序表中某个指定的元素的示意图如下：第16页/共33页第十七页，共33页。1818实现步骤：？将第i 至第n 位的元素向前移动一个位置；表长减1。注意：事先需要判断(pndun)，删除位置i 是否合法?应当有1in 或 i=1,nfor(j=i+1;j=n;j+)aj-1=aj;n-;/元素(yun s)前移一个位置/表长减1 核心(hxn)语句：第17页/共33页第十八页，共33页。1919练习题：设有线性表 LA（3,5

15、,8,11）和 LB=（2,6,8,9,11,15,20）；若LA和LB分别表示两个集合A和B，求新集合 AA U B（并操作，相同(xin tn)元素不保留）；预测输出：LA=（3,5,8,11,2,6,9,15,20）按规律(gul)插入插入(ch r)到尾部 将LA与LB表归并，要求仍有序（相同元素要保留）预测输出：LC=（2,3,5,6,8,8,9,11,11,15,20）第18页/共33页第十九页，共33页。20202.2.3 2.2.3 顺序表的运算顺序表的运算顺序表的运算顺序表的运算(yn sun)(yn sun)效效效效率分析率分析率分析率分析算法时间算法时间算法时间算法时间(

16、shjin)(shjin)主要耗费在移动元素的操作主要耗费在移动元素的操作主要耗费在移动元素的操作主要耗费在移动元素的操作上，因此上，因此上，因此上，因此计算时间计算时间计算时间计算时间(shjin)(shjin)复杂度的基本操作（最深层复杂度的基本操作（最深层复杂度的基本操作（最深层复杂度的基本操作（最深层语句频度）语句频度）语句频度）语句频度）T(n)=O(T(n)=O(移动元素次数移动元素次数移动元素次数移动元素次数)移动元素的个数取决于插入或删除元素的位置移动元素的个数取决于插入或删除元素的位置移动元素的个数取决于插入或删除元素的位置移动元素的个数取决于插入或删除元素的位置.思考：若插

17、入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；若要考虑在各种位置插入（共n+1种可能）的平均移动次数，该如何(rh)计算？讨论1：若在长度为 n 的线性表的第 i 位前 插入一元素，则向后移动元素的次数f(n)为:f(n)=n i+1时间效率分析:第19页/共33页第二十页，共33页。2121讨论讨论讨论讨论2 2：若在长度：若在长度：若在长度：若在长度(chngd)(chngd)为为为为n n的线性表上的线性表上的线性表上的线性表上删除第删除第删除第删除第i i位元素，向前移动元素的次数位元素，向前移动元素的次数位元素，向前移动元素的次数位元素

18、，向前移动元素的次数f(n)f(n)为：为：为：为：f(n)=f(n)=思考：若删除尾结点，则根本无需移动（特别快）；若删除首结点，则表中元素全部要前移（特别慢）；若要考虑(kol)在各种位置删除（共n种可能）的平均移动次数，该如何计算？n i可以证明：插入(ch r)、删除操作平均需要移动一半元素(n/2)插入(ch r)、删除算法的平均时间复杂度为：O(n)显然，顺序表的 空间复杂度S(n)=0（没有占用辅助空间）第20页/共33页第二十一页，共33页。2222证明：假定在每个元素位置上插入(ch r)x的可能性都一样（即概率P相同），则应当这样来计算平均执行时间：将所有位置的执行时间相加

19、，然后取平均。若在首结点前插入(ch r)，需要移动的元素最多，后移n次；若在a1后面插入(ch r)，要后移n-1个元素，后移次数为n-1;若在an-1后面插入(ch r)，要后移1个元素；若在尾结点an之后插入(ch r)，则后移0个元素；所有可能的元素移动次数合计：0+1+n=n(n+1)/2所以(suy)平均移动次数为：n(n+1)/2(n+1)n/2 T(n)=O(n)共有多少种插入(ch r)形式?连头带尾有n+1种同理可证：顺序表删除一元素的时间效率为:f(n)=(n-1)/2 T(n)=O(n)第21页/共33页第二十二页，共33页。2323假定在表中任意位置假定在表中任意位置

20、假定在表中任意位置假定在表中任意位置(wi zhi)(wi zhi)插入、删除元素都是等概插入、删除元素都是等概插入、删除元素都是等概插入、删除元素都是等概率的，率的，率的，率的，插入概率插入概率插入概率插入概率p(i)=1/(n+1)p(i)=1/(n+1)，删除概率，删除概率，删除概率，删除概率q(i)=1/n q(i)=1/n，则：，则：，则：，则：插入(ch r)操作时间效率（平均移动次数）删除操作时间效率（平均移动(ydng)次数）故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低第22页/共33页第二十三页，共33页。2424顺序顺序(shnx(shnx)

21、表小结表小结链式存储(cn ch)结构见2.3节l l顺序存储结构的优缺点l l优点l l 逻辑相邻，物理相邻l l 可随机存取任一元素l l 存储空间使用紧凑l l缺点l l 插入、删除操作需要移动大量的元素l l 预先(yxin)分配空间需按最大空间分配，利用不充分l l 表容量难以扩充第23页/共33页第二十四页，共33页。25252.3 线性表的链式表示线性表的链式表示(biosh)和实现和实现2.3.1 链表的表示(biosh)2.3.2 链表的实现2.3.3 链表的运算效率分析链表小结(xioji)第24页/共33页第二十五页，共33页。26262.3.1 2.3.1 链表的表示链

22、表的表示链表的表示链表的表示(biosh)(biosh)链式存储结构特点：其结点在存储器中的位置(wi zhi)是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。如何(rh)实现？通过指针来实现注意：每个存储结点都包含两部分：数据域和指针域第25页/共33页第二十六页，共33页。27271536元素(yun s)21400元素(yun s)11346元素(yun s)3 元素41345h存储地址存储地址 存储内容存储内容 指针指针 1345 1345 元素元素1 1 1400 1400 1346 1346 元素元素4 4 .1400 1400 元素元素2 2 1536 1536 .1536

23、1536 元素元素3 3 1346 1346 链式存储 h第26页/共33页第二十七页，共33页。2828例例例例1 1 画出画出画出画出26 26 个英文字母表的链式存储个英文字母表的链式存储个英文字母表的链式存储个英文字母表的链式存储(cn ch)(cn ch)结结结结构。构。构。构。该字母表在内存的链式存放(cnfng)示意图如下：解：该字母表的逻辑(lu j)结构为：（a,b,y,z）aheadb/z各结点由两个域组成：数据域：存储元素数值数据；指针域：存储直接后继或者直接前驱的存储位置。指针数据指针数据指针或样式：第27页/共33页第二十八页，共33页。2929与链式存储有关与链式存

24、储有关(yugun)的术语：的术语：1、结点：数据元素的存储(cn ch)映像。由数据域和指针域两部分组成；2、链表：n 个结点由指针链组成一个链表。它是线性表的链式存储(cn ch)映像，称为线性表的链式存储(cn ch)结构3、单链表、双链表、多链表、循环链表：结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。a1heada2anhead循环(xnhun)链表示意图：第28页/共33页第二十九页，共33页。30304 4、头指针、头指针、头指针、头指针(zhzhn)(zhzhn)、头结点和首、头结点和

25、首、头结点和首、头结点和首元结点元结点元结点元结点 示意图如下示意图如下示意图如下示意图如下(rxi)(rxi)：头指针(zhzhn)头结点首元结点a1heada2infoan头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息;首元结点是指链表中存储线性表第一个数据元素a1的结点。第29页/共33页第三十页，共33页。3131一个线性表的逻辑(lu j)结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址存储地址数据

26、域数据域指针域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例例例例：答：头指针是指向链表中第一个结点的指针，因此关键是要寻找(xnzho)第一个结点的地址。7ZHAOH31头指针(zhzhn)的值是31第30页/共33页第三十一页，共33页。3232上例链表的逻辑(lu j)结构示意图有以下两种形式：ZHAOQIANLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WANGH区别：无头(w tu)结点 有头结点第31页/共33页第三十二页，共33页。3333答：讨论1.在链表中设置头结点有什么(shn me)好处？讨论2.如何(rh)表示空表？头结点即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理(chl)，编程更方便。答：无头结点时，当头指针的值为空时表示空表；有头结点时，当头结点的指针域为空时表示空表。头指针头指针头结点无头结点有头结点第32页/共33页第三十三页，共33页。