[新大纲] 3 线性表.ppt

1、第二部分数据结构，讲师：王永波，中国矿业大学环境与测绘学院，2013年10月26日，大纲，概述线性表栈、队列树和二叉树图的搜索与排序，2。线性表，1。定义和运算，定义n(0)个数据元素的有限序列存储结构序列表(向量)，链表的特点是除了第一个元素外，其他每个元素都有一个和。除了最后一个元素，其他所有元素都只有一个直接后继元素。1。定义和操作，基本操作插入：在两个确定的元素之间插入一个新元素；删除线性表中的元素；根据一定的要求在线性表中找到一个元素；根据给定的要求对表格中的元素重新排序；2.顺序存储线性表；线性表中的元素通过顺序存储结构/向量存储结构存储在连续的存储空间中。一维数组可以用来描述存储

2、结构。众所周知，线性表中的每个元素占用L个单位，线性表的第一个存储地址是adr(a1)=b，那么线性表中的第ith元素的存储地址是adr(ai)=adr(a1) (i-1)l，2.1序列表类的定义，以及模板类SEqlist/序列表存储数组/最大允许长度int MaxSize/当前最后一个元素下标int lastpublic : SEQlist(int MaxSize=DefaultSize)；SeqList()删除数据；int Length()常量返回最后1；/查找int find(类型，int locate (int I)常量；/定位整数插入(整数1，类型，7，2.2)。插入线性表意味着在第

3、i(1i n 1)个元素之前插入新的数据元素x，使得长度为n的线性表成为长度为n 1的线性表。操作：将第(n-I 1)个元素移回，2.2。步骤2:在ai-1之后插入X；第三步：桌子的长度是1。伪代码描述，插入(int i，int，2.2.2)序列表删除算法，删除(int i) /删除位置I的int k元素；如果(I最后)/下表将1作为起始索引打印(“表中的位置I没有元素n”)；出口(-1)；对于(k=I；k=last-1；K )/后面的元素向前移动列表k=最后一个1；最后-；2.2.3序列表插入和删除算法的时间复杂度，序列表插入和删除算法的运算时间主要花在移动元素上，所以花在移动元素上的时间可

4、以视为序列表插入和删除算法所消耗的时间。时间复杂度t (n)=o (n)，edel=1/n *(n-1)(n-2)210=(n-1)/2，2.3。搜索序列表、25 34 57 16 48 09、0 12 3 25 34 57 16 48 09、I、25 34 57 16 48 09、I、搜索成功，2.3.1序列表搜索算法伪码，怎么写？请完成内部查找(类型/节点数据，整数列表节点*链接；/节点指针；类列表/链表类定义私有：列表节点*第一个，*当前；/头指针public: /链表操作；3.3在第一个节点前插入一个链表，将其插入链表的中间，并将其插入链表的末尾，3.3.1在第一个节点前插入，伪代码n

5、ew node-link=first；first=newnode思考：以上两种说法能按顺序颠倒吗？(插入前)(插入后)，3.3.2在链表中间插入，伪代码new node-link=current-link；current-link=new node；(插入前)(插入后)，3.3.3在链表的末尾插入，伪代码new node-link=current-link；current-link=new node；(插入前)(插入后)，3.3.4用于链表插入的伪代码程序，int list:3360 insert (int x，int I)/插入一个新元素x ListNode * p=当前链表的第I个节点；当

6、前=第一；对于(k=0；k链接；如果(当前=空，在3.3.4链表中插入伪代码程序，列表节点*新节点=/创建新节点，新列表节点(x，空)；如果(第一个=空| i=0) /插入到新节点表的前面-链接=第一个；first=current=newnode否则/插入表中或在newnode-link=current-link的末尾。current=current-link=new node；返回1；3.4删除单个链表中的节点，第一种情况：删除表中的第一个元素，第二种情况：删除表或表尾中的元素，并删除单个链表中具有ai的节点、AI-1、AI 3.4.1删除链表中节点的伪代码程序，int list :3360

7、 remove(int I)/删除链表中的第I个节点ListNode *p，* q；int k=0；如果(i=0) /删除表中的第一个节点q=第一个；current=first=first-link；否则p=当前值。当前=第一；/查找第I-1个节点(k=0；k链接；3.4.1用于删除链表节点的伪代码程序，如果(current=null | | current-link=null)cout link；/重新链接当前=当前链接=q链接；类型x=q-数据。删除q；/删除q返回x；/返回第一个节点的值，3.4.2带表头节点的单链表，位于表的前面，没有数据，只标记表头。设置表头节点的目的是统一空表和非空

8、表的操作，简化链表操作的实现。非空表，空表，插入带有标题节点的单个链表，new node-link=p-link；p-link=new node；插入、删除带有标题节点的单个链表，q=p-link；p链接=q链接；删除q；(非空表)，(空表)，3.5单链表的特点，它是一个动态结构，整个存储空间由多个链表共享，指针占用的额外存储空间不能随机访问，搜索速度慢，链表搜索只能从头指针开始，只能沿着链表的方向在单个链表中移动，时间复杂度为O(n)。4.循环链表，对单个链表的访问是一种顺序访问。从一个节点开始，你可以找到它的直接后继节点，但是你找不到它的直接前驱节点。将单个链表最后一个节点的指针字段改为链

9、表头节点(或第一个节点)的地址，使整个链表形成一个环。它被称为单循环链表，具有单链表的特点，但不需要增加额外的存储空间。只有表格的链接方式略有改变，使得表格的处理更加方便灵活。4.循环链表，可以从循环链表中的任何节点找到表中的其他节点，提高了搜索效率。循环链表的操作与单一链表的操作基本相同。唯一的区别在于最后一个节点的判断。循环条件不同的单链表P或p-link=NULL循环链表P或p-link=H使用循环链表实现某些操作比从某个节点找到其直接的前身(单链表只能从头开始)更方便，4.1循环链表的表达式形式，带头节点的一般循环链表，(非空表)，4.2空循环链表的判断和特点，先空循环链表的条件。ne

10、xt=first Features从表中的任何节点，您都可以在表中找到时间复杂度为0(n)的其他节点。5.双链表是指线性链表的每个节点的结构，它可以向前后两个方向移动(遍历):双链表通常采用带有头节点的循环链表的形式。双循环链表为空头的条件。prior=head。下一个=头特征查找其前一个节点的时间复杂度为0(1)，非空表为空表，5。双链表，节点指向，p=p-rlink-rlink=p-rlink，5.1双循环链表的搜索算法，搜索成功，搜索不成功，搜索为15、搜索为25、5.2双向循环链表的插入算法(空表)，然后插入25，当前，新节点链接=当前；new node-RLink=current-R

11、Link；current-RLink=new node；/(1)电流=电流-RLink；电流-rLink-lLink=电流；/(3)问题2(1)(3)你能把它倒过来吗？怎么写？5.3插入双向循环链表(空链表)算法，插入25后，新节点-链表=当前；new node-RLink=current-RLink；(=第一个)当前-RLink=new node；current=current-RLink；电流-rLink-lLink=电流；(first-LinLk=current)，5.4双向循环链表删除算法，删除48，非空表，current-rlink-link=current-link；电流-线性链接

12、-线性链接=电流-线性链接；5.2双向循环链表的删除算法2，current-rlink-llink=current-llink；电流-线性链接-线性链接=电流-线性链接；6、链表存储结构的特点，插入和删除操作对于数据的不连续存储非常方便，顺序访问不需要事先知道线性表的长度，线性表的长度允许有很大的变化，逻辑上相邻，物理上不一定相邻，存储结构复杂，需要额外的存储空间。链表存储结构适用于表中元素频繁变化的线性表。当读取操作比插入和删除操作更频繁时，就不适合使用链表。基于面向对象的思想，分别设计并建立了一个序列表类和一个链表类，并实现了它们的相关功能。7.1序列表函数设计，类SeqList public:/构造，析构函数SEQlist()；SeqList()；Public: /复制构造函数，赋值操作SeqList(常量SeqList /搜索，int LoCation(int I)