毕业答辩ppt模板-安徽大学.ppt

线性结构的定义：线性结构的定义：若若结结构构是是非非空空有有限限集集，则则有有且且仅仅有有一一个个开开始始结结点点和和一一个个终终端端结结点点，并并且且所所有有结结点点都都最最多多只只有有一一个个直直接接前前趋趋和和一一个个直直接后继。接后继。可表示为：（可表示为：（a a1 1,a,a2 2 ,a,an n）简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是的。的。特点特点 只有一个首结点和尾结点；只有一个首结点和尾结点；特特点点 除除首首尾尾结结点点外外，其其他他结结点点只只有有一一个个直直接接前前驱驱和和一一个个直接后继。直接后继。线性结构包括：线性结构包括：线性表、堆栈、队列、字符串、数组线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是等，其中最典型、最常用的是-线性表线性表一对一一对一(1:1)1第第2章章线性表线性表2.12.1线性表的基本概念线性表的基本概念线性表的基本概念线性表的基本概念 2.22.2线性表的顺序表示和实现线性表的顺序表示和实现线性表的顺序表示和实现线性表的顺序表示和实现2.32.3线性表的链式表示和实现线性表的链式表示和实现线性表的链式表示和实现线性表的链式表示和实现2.42.4应用举例应用举例应用举例应用举例22.1线性表的基本概念线性表的基本概念、线性表、线性表它是一种最简单的线性结构。是一种可以在任它是一种最简单的线性结构。是一种可以在任意位置进行插入和删除数据元素操作的，由意位置进行插入和删除数据元素操作的，由n（n0)个相同类型数据元素个相同类型数据元素a0,a1,an-1组成的线性组成的线性结构。结构。3（a0,a1,ai-1，ai,ai1，,an-1）线性表的逻辑结构：线性表的逻辑结构：线性表的逻辑结构：线性表的逻辑结构：n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总为元素总个数，即表个数，即表长。长。n0n0空表空表线性终点线性终点4（A,B,C,D,Z）学号学号姓名姓名性别性别年龄年龄班级班级012003010622陈建武陈建武男男192003级电信级电信0301班班012003010704赵玉凤赵玉凤女女182003级电信级电信0302班班012003010813王王泽泽男男192003级电信级电信0303班班012003010906薛薛荃荃男男192003级电信级电信0304班班012003011018王 春男 19 192003级电信级电信0305班班：例例2分析学生情况登记表是什么结构。分析学生情况登记表是什么结构。分析：分析：数据元素都是同类型（数据元素都是同类型（记录记录），元素间关系是线性的。），元素间关系是线性的。分析：分析：数据元素都是同类型（数据元素都是同类型（字母字母），），元素间关系是线性的。元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性！例例1分析分析26个英文字母组成的英文表是什么结构。个英文字母组成的英文表是什么结构。5、线性表抽象数据类型、线性表抽象数据类型 它包括两个方面：它包括两个方面：数据集合：数据集合：a0,a1,an-1ai的数据类型为的数据类型为DataType操作集合操作集合：(1)ListInitiate(L)初始化线性表初始化线性表(2)ListInsert(L,i,x)插入数据元素插入数据元素(3)ListLength(L)求当前数据元素个数求当前数据元素个数(4)ListDelete(L,i,x)删除数据元素删除数据元素(5)ListGet(L,i,x)取数据元素取数据元素等等63 3、线性表的存储结构、线性表的存储结构(1)顺序存储结构顺序存储结构:它是使用一片它是使用一片地址连续地址连续的有限内存的有限内存单元空间存储数据元素的一种计算机存储数据方法。单元空间存储数据元素的一种计算机存储数据方法。特点：特点：(任意两个在逻辑上相邻的数据元素在物理位置任意两个在逻辑上相邻的数据元素在物理位置上也必然相邻上也必然相邻)逻辑上相邻的元素，物理上也相邻。逻辑上相邻的元素，物理上也相邻。(2)(2)链式存储结构链式存储结构:它是把数据元素和指针定义成一个它是把数据元素和指针定义成一个存储体，使用指针把发生联系的数据元素链接起来存储体，使用指针把发生联系的数据元素链接起来的一种计算机存储数据方法。的一种计算机存储数据方法。特点：特点：任意两个在任意两个在逻辑上相邻逻辑上相邻的数据元素在的数据元素在物理上不物理上不一定相邻一定相邻，数据元素的逻辑次序是通过链中的指针，数据元素的逻辑次序是通过链中的指针链接实现的。链接实现的。72.2线性表的顺序表示和实现线性表的顺序表示和实现一一、顺序表的存储结构顺序表的存储结构二、二、顺序表的实现顺序表的实现三、三、顺序表的运算效率分析顺序表的运算效率分析8一、一、顺序表的存储结构表示顺序表的存储结构表示 1、顺序表顺序表：用一组用一组地址连续地址连续的存储单元依次存储线的存储单元依次存储线性表的各个数据元素。即采用顺序存储结构的线性性表的各个数据元素。即采用顺序存储结构的线性表。它通常采用静态数组实现数据元素的存储。表。它通常采用静态数组实现数据元素的存储。可以利用可以利用数组数组VnVn来实现来实现注意：在注意：在C C语言中数组的下标是从语言中数组的下标是从0 0开始，即：开始，即：Vn Vn的有效范围是从的有效范围是从 V0 V0Vn-1Vn-19(1)逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；(2)若已知表中首元素在存储器中的位置，则其他若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出元素存放位置亦可求出（利用数组利用数组VnVn的的下标下标）。）。设首元素设首元素a0的存放地址为的存放地址为LOC(a0)（称为称为首地址首地址），），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：为：LOC(ai+1)=LOC(ai)+LLOC(LOC(a aii)=LOC()=LOC(a a00)+L*i)+L*i对上述公式的解释如图所示对上述公式的解释如图所示2、线性表顺序存储特点：、线性表顺序存储特点：10a a0 0a a1 1a ai ia ai+1i+1a an-1n-1 地址地址 内容内容 元素在表中的位序元素在表中的位序0 0i i1 1n-1n-1空闲区空闲区i+1i+1Lb=LOC(a0)b+L Lb+i+iL Lb+(n-1)+(n-1)L Lb+(MaxSize-1)+(MaxSize-1)L LLOC(aLOC(aii)=LOC(a)=LOC(a00)+L*i)+L*i3、线性表的顺序存储结构示意图、线性表的顺序存储结构示意图114 4、用、用C C语言描述语言描述 typedef struct DateType listMaxSize;int size;SeqList;/*MaxSize表示数组的最大元素个数，list表示顺序表的数组名，size表示顺序表中当前存储的数据元素个数，它必须满足size MaxSize，SeqList是该结构体的名字。*/12设有一维数组设有一维数组，下标的范围是，下标的范围是到到，每个数组元素用相邻的每个数组元素用相邻的个字节个字节存储。存储器存储。存储器按字节编址，设存储数组元素按字节编址，设存储数组元素 的第一个的第一个字节的地址是字节的地址是，则，则 的第一个字节的的第一个字节的地址是多少？地址是多少？113LOC(M3)=98+53=113解：解：已知地址计算通式为：已知地址计算通式为：LOC(ai)=LOC(a0)+L*i例例113charV30;voidbuild()/*字字母母线线性性表表的的生生成成，即即建建表表操操作作*/inti;V0=a;for(i=1;i=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语言程序。语言程序。14voidmain(void)/*主函数主函数，字母线性表的，字母线性表的生成和输出生成和输出*/n=26;/*n n是表长，是数据元素的个数，而不是是表长，是数据元素的个数，而不是V V的的 实际下标实际下标*/build();display();voiddisplay()/*字母线性表的显示，即字母线性表的显示，即读表操作读表操作*/inti;for(i=0;i=i;j-)aj+1=aj;ai=x;n+;/元素后移一个位置元素后移一个位置/插入插入x x/表长加表长加1 1 核核心心语语句：句：2)2)插入插入17在线性表的第在线性表的第i i个位置前插入一个元素的示意图如下：个位置前插入一个元素的示意图如下：12132124283042771213212425252830427712345678123456789插入插入2525252518实现步骤：实现步骤：将第将第i+1至第至第n位的元素向前移动一个位置；位的元素向前移动一个位置；表长减表长减1。注意：事先需要判断，注意：事先需要判断，删除位置删除位置i是否合法是否合法?删除线性表的第删除线性表的第i i个位置上的元素个位置上的元素for(j=i+1;j=n-1;j+)aj-1=aj;n-;/元素前移一个位置元素前移一个位置/表长减表长减1 1 核心语句：核心语句：3)3)删除删除19123456789121321242528304277123456781213212428304277删除顺序表中某个指定的元素的示意图如下：删除顺序表中某个指定的元素的示意图如下：20例：建立一个线性表，先依次输入数据元素1，2，3，4，10，然后删除，最后依次显示当前线性表中的数据元素。假设该线性的数据元素个数最坏情况下不会超过100个。实现方法：1、采用直接编写一个主函数实现。2、利用已设计实现的抽象数据类型模块。（存放在头文件名为SeqList.h中，通过#include“SeqList.h”）21三、三、顺序表操作的效率分析顺序表操作的效率分析算法时间主要耗费在算法时间主要耗费在移动元素移动元素的操作上，因此的操作上，因此计算时间复杂度的基本操作（最深层语句频度）计算时间复杂度的基本操作（最深层语句频度）T(n)=O(移动移动元素次数元素次数)而移动元素的个数取决于插入或删除元素的位置而移动元素的个数取决于插入或删除元素的位置.思考：思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；若插入在首结点之前，则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共应当考虑在各种位置插入（共n+1种可能）的种可能）的平均平均移动次数才合理。移动次数才合理。时间效率分析时间效率分析:22推推导导：假假定定在在每每个个元元素素位位置置上上插插入入x x的的可可能能性性都都一一样样（即即概率概率P P相同），则应当这样来计算平均执行时间：相同），则应当这样来计算平均执行时间：将所有位置的执行时间相加，然后取平均。将所有位置的执行时间相加，然后取平均。将所有位置的执行时间相加，然后取平均。将所有位置的执行时间相加，然后取平均。若在首结点前插入，需要移动的元素最多，后移若在首结点前插入，需要移动的元素最多，后移n n次；次；若在若在a a1 1后面插入，要后移后面插入，要后移n-1n-1个元素，后移次数为个元素，后移次数为n-1n-1;若在若在a an-1n-1后面插入，要后移后面插入，要后移1 1个元素；个元素；若在尾结点若在尾结点a an n之后插入，则后移之后插入，则后移0 0个元素；个元素；所有可能的元素移动次数合计所有可能的元素移动次数合计：0+1+n0+1+n=n(n+1)/2=n(n+1)/2故插入时的平均移动次数为：故插入时的平均移动次数为：n(n+1)/2n(n+1)/2（n+1n+1）n/2n/2O(n)O(n)O(n)O(n)共有多少种插入形式共有多少种插入形式?连头带尾有连头带尾有n+1n+1种种!23同理可证：同理可证：顺序表删除一元素的时间效率为顺序表删除一元素的时间效率为:T T（n)=(n-1)/2 n)=(n-1)/2 O(n)O(n)O(n)O(n)插入插入效率：效率：删除删除效率：效率：教材教材P33有对执行效率的推导：有对执行效率的推导：（与课本略有区别）（与课本略有区别）即插入、删除算法的平均即插入、删除算法的平均时间复杂度为时间复杂度为O(n)24链式存储结构链式存储结构本节小结本节小结线性表线性表顺序存储结构特点顺序存储结构特点：逻辑关系上相邻的两个元素：逻辑关系上相邻的两个元素在物理存储位置上也相邻；在物理存储位置上也相邻；优点：优点：可以随机存取表中任一元素，方便快捷；可以随机存取表中任一元素，方便快捷；缺点：缺点：在插入或删除某一元素时，需要移动大量元素。在插入或删除某一元素时，需要移动大量元素。解决问题的思路：解决问题的思路：改用另一种线性存储方式：改用另一种线性存储方式：25作业：P55 2-1,2-2,2-11,2-1526