数据结构C语言版第二章严蔚敏PPT课件

。1，第2章线性表，2.1线性表的概念和运算2.2线性表序列存储2.3线性表链存储2.4单变量多项式的表示和加法，2.1线性表的概念和运算，4。线性表的逻辑结构，1。线性表的定义，线性表是一个有N个数据元素的有限序列。注(A1、AI-1，AI，AI 1，安)，2。线性表的长度，线性表中元素的个数n (n=0)，当n=0时，称为空表。位序，ai是第I个元素，I是线性表中数据元素ai的位序。一个例子是英语字母表(a，b，z)；车辆登记表。线性表的特征恒等式：线性表由相似的数据元素组成，每个人工智能必须属于同一个数据对象。很差：线性表由有限数量的数据元素组成，表长度是表中数据元素的数量。有序性：线性表中相邻的数据元素之间有一种有序-均匀的关系。线性表的基本操作，初始化InitList(/当前长度intlistsize/分配的存储容量 SQLIST；/ElemTypeElemMAXSIZE；typedef # ElemType#是根据具体问题确定的数据类型typedefintStatus在顺序表上实现基本操作，初始化StatusInitList_Sq(SqList，15，插入顺序表：在表中的第四个元素之前插入“21”。在序列表中插入元素。16，插入statuslistinsert _ sq (sqlist，17，/越界处理，new base=(elem type *)real loc(l . elem，(l.listsizelist增量)* size of(elem type)；如果(！newbase)退出(OVERFLOW)；L.elem=newbase，列表大小=列表增量；18，算法时间复杂度：时间主要花费在移动元素上，并且移动元素的数量取决于插入元素的位置。i=1，需要移动n个元素；i=i，需要移动ni1个元素；i=n 1，需要移动0个元素；19，假设pi是在第I个元素之前插入新元素的概率，20，删除图的序列表中的元素，删除序列表：删除第五个元素，21，删除statuslistdelete _ sq (SQLIST)，22，算法时间复杂度：时间主要花费在移动元素上，并且移动元素的数量取决于被删除元素的位置。i=1，需要移动n-1个元素；i=i，nI元素需要移动；i=n，需要移动0个元素；23，假设qi是删除第I个元素的概率。24、顺序表的合并以及表中元素的非递减排列。虚列列表(SQLISTLA，SQLISTLB，SQLIST，25，顺序表的基本点：不需要添加额外的存储空间来表示元素之间的逻辑关系，并且存储密度高(100%)；表中的任何元素都可以随机访问。当插入或删除一个元素时，它平均需要移动表中一半的元素。具体的数字与元素的位置有关。在等概率条件下，插入n/2，删除(n-1)/2；O(n)存储分配只能提前完成。两个各有n个元素的有序表合并成一个有序表，比较的最小次数为：n，26岁，工作：2.11，27，2.3线性表的链式表示和实现。线性表的链式存储结构的特征在于：用一组任意存储单元存储线性表的元素，并且不要求逻辑上相邻的元素在物理位置上相邻；插入或删除时不需要移动大量元素；失去顺序表可以随机访问的优势。28，1。线性链表(单链表)，节点：数据元素的存储图像。数据字段用于存储节点的值。指针字段用于存储数据元素的紧接着的地址(或位置)。头指针指示链表中第一个节点的存储位置，单个链表可以由头指针唯一确定。30，单个链表的存储映像，31中，头节点与链表的第一个节点之前的节点相连，并且头指针指向头节点。设置头节点的目的是统一空表和非空表的操作，简化链表操作的实现。第一个元素节点链表中存储线性表中第一个数据元素的节点。嘿。32，单链表存储结构描述：typedeftrulnode elemtypedata；结构代码*下一步；代码，*链接列表；(1)初始化线性表初始化列表(1)此操作创建一个空隙减少列表(链接表1)链接表p=L，q=p-下一个；while(q！=空)免费(p)；p=q；q=p-next；免费(p)；，35，(3)如果单个链表L没有数据节点，则线性表是否为空表列表空(L)返回真，否则返回假。输入列表为空(链接列表)返回(下一个=空)；，36，(4)找出线性表列表长度(L)并返回单个链表中的数据节点数。inti=0；同时(p-next！=空) I；p=p-下一个；返回(I)；，37，(5)输出线性表DispList(L)逐个扫描单个链表L的每个数据节点，并显示每个节点的数据字段值。空显示列表(链接表)链接表=下一个；同时(p！=NULL) printf(“% c”，p-data)；p=p-下一个； printf( n )；，38，statusgetelem (linklist l，inti，elem type)；(6)取表元素，从头指针L开始，从头节点开始沿链域扫描(L-next)；使用j作为计数器来累计当前扫描的节点数。当j=i时，指针p所指的节点是要找到的第I个节点。例如，39，取I=第3个元素。e=p-data=孙，时间复杂性：O(n)，40，在单个链表的第一个节点之前插入一个节点的过程。41，(7)插入statuslistinsert (linklist)的过程。42、删除单个链表的第I个节点的过程。43，(8)删除状态列表(链接列表)的过程，44、动态建立单个链表的过程，建立单个链表的头部插入方法。45，(9)建立表的头插入方法CreateList_H(链表，46，建立表的尾部插入方法，47，(10)尾部插入法建立表CREATE LIST _ T(链表，48，(11)根据元素值搜索LocateElem(L，E)的思想：在单个链表L中从头开始寻找第一个值范围等于E的节点，如果有这样的节点，返回到该位置，否则返回到0。intLocateElem(链接列表，电子邮件)链接列表=L-下一个；intn=1；同时(p！=NULL。49，练习：已知l是前导节点的非空单链表，指针p所指的节点既不是第一个节点，也不是最后一个节点删除*p节点的直接后继节点的语句序列q=p-next；p-next=q-next；自由(q)；删除*p节点的直接前置节点的语句序列q=L；同时(q-next-next！=p)q=q-下一个；s=q-下一个；q-next=p；免费；嘿。50，删除语句序列q=L的*p节点；while(q-next！=p)q=q-下一个；q-next=p-next；免费(p)；删除语句序列q=L-头元素节点的下一个；l-next=q-next；自由(q)；删除语句序列，同时(p-next-next！=空)p=p-下一个；q=p-next；p-next=空；自由(q)；51、链式结构的特点，非随机存储结构，所以取表元素比取顺序表慢。该方法节省了大量内存，适用于插入和删除操作。事实上，空间用于时间，指针被添加到节点，因此这两个操作被转换成指针操作；与线性表的实现方法相比，不同序列表的实现方法简单，数组类型在各种高级语言中都有，易于实现。链表的操作是基于指针的，这相对比较复杂。从存储的角度来看，序列表的存储空间是静态分配的，在程序执行前必须明确指定其存储大小，也就是说，“MAXSIZE”应该预先设置好，太大会造成浪费，太小会造成溢出。链表动态分配存储空间，无需预先估计存储大小。可以看出，当难以估计线性表的长度或存储大小时，使用链表。线性表操作的实现不同于通过序列号访问数据元素，使用顺序表优于链表。插入和删除操作，使用链表优于顺序表。53，作业：2.42.19，54，3。静态链表。一些高级编程语言没有指针类型，如FORTRAN和JAVA。我们可以使用数组来表示和实现一个链表，称为静态链表。可以定义如下：# DefineMaxSize 1000/typedefstruct ElEMTypeData；intcur/光标，指示器组件，链接列表MAXSIZE；嘿。55，i=si。弯曲的；Malloc:i=s0。弯曲的；第一个可用的节点位置(s0)。cur)s0。cur=si。弯曲的；Free:/释放k个节点sk。cur=s0。弯曲的；s0。cur=k；在r si之后插入I。cur=sr。弯曲的；sr。cur=I；Delete:/p是直接的前兆线性表的链式存储结构是一种顺序存取存储结构，不具有对任何元素进行随机存取的特性。设置主节点的作用是使链表第一个位置的操作与表中其他位置的操作一致，不需要特殊处理，统一空表和非空表的处理。练习2.22编写一个算法，将单个链表翻转到位。无效反向_L(链表，58、循环链表循环链表是链式存储结构的另一种形式；您可以从当前节点访问任何节点。循环单链表；多循环链表。59、单循环链表，设置尾部指针后比设置头部指针好。嘿。60，仅用尾部指针连接两个单循环链表L1和L2，操作如下：p=R1-下一步；/保存L1头节点指针R1-下一个=R2-下一个-下一个；/无首尾连接(R2-下一个)；/释放第二个表的头节点R2-下一个=p；以循环列表中的I元素为例。p=L-下一个；j=1；如果(p=L|ji)返回错误；e=p-数据；返回确定；除了算法中的循环结束条件不是p是否为空，而是p是否等于头指针之外，该操作与线性单链表的操作基本相同。62，双链表，希望找到时间复杂度为O(1)的前驱，我们可以用空间来交换时间，并且每个节点向前驱添加一个指针字段，这样链表就可以双向搜索。由这种节点结构形成的链表称为双链表。节点：63的结构图，双链表的逻辑表示、l、64、2。双链表typedefruddulnode elemtypedata；结构节点*优先；结构节点*下一步；DuLNode，* DuLinkList，65，双循环链表，p-下一个优先级=p-优先级-下一个；p，66，双链表的前(后)插入，s-price=p-price；p-优先-下一个=s；s-next=p；p-先验=s；q，s-next=q-next；q-下一个优先=s；s优先=q；q-next=s；，67，删除双链表，p-优先-下一个=p-下一个；p-下一个优先=p-优先；嘿。68，删除语句序列q=p-下一个直接后继节点的* p；p-next=p-next-next；p-下一个-优先=p；自由(q)；删除直接前置节点*p的语句序列q=p-previor；p-优先=p-优先-优先；p-前-后=p；自由(q)；69，分配：2.82.9，70，循环列表算法示例(1)，假设单个循环列表，其节点包含三个字段pre、data、link。其中数据是数据字段；Pre是一个指针字段，其值为空。链接是指向后续节点的指针字段。请设计一个算法将这个表变成一个双循环链表。是一个单循环链表，其节点包含三个字段：pre、data和link。其中数据是数据字段；Pre是空指针字段，link是指向以下内容的指针字段。该算法将其转换成一个双循环链表。 while(la-link-pre=null) la-link-pre=la/将节点la后的pre指针指向Lala=la-link；/la指针向后移动 /算法结束，71，循环列表算法示例(2)，称为双循环列表，从第二个节点到表的末尾依次递增，(设置a1优先级；/*q指向最后一个