《chapter2.1-2.2顺序表.ppt》由会员分享，可在线阅读，更多相关《chapter2.1-2.2顺序表.ppt（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构与算法数据结构与算法第第2 2章章 线性表线性表第2章 线性表2.1 线性表的概念线性表的概念2.2 顺序表顺序表2.3 链表链表第2章 线性表 唯一头元素唯一头元素 唯一尾元素唯一尾元素 除头元素外，均有一个直接前驱除头元素外，均有一个直接前驱 除尾元素外，均有一个直接后继除尾元素外，均有一个直接后继线性结构特点线性结构特点:OOOOO线性线性头头尾尾1 2 3 4 5线性表第2章 线性表 具有反对称性和传递性具有反对称性和传递性1.线性表的语言定义线性表的语言定义线性表是线性表是n个数据元素的有限序列。个数据元素的有限序列。例，例，英文字母表英文字母表 (A，B，C，Z)线性表中的
2、数据元素可以由若干个数据项组成。线性表中的数据元素可以由若干个数据项组成。例，例，包含大量记录的登记表包含大量记录的登记表线性表的定义第2章 线性表排名排名国家国家金牌金牌银牌银牌铜牌铜牌总数总数1美国4629291042中国382723883英国291719654俄罗斯242632822.线性表的形式定义线性表的形式定义其中其中a1 1是头元素，是头元素，an是尾元素，是尾元素，ai是第是第i个元素。个元素。ai-1-1是是ai的直接前驱，的直接前驱，ai是是ai-1-1的直接后继。的直接后继。当当2in时，时，ai有且只有一个直接前驱。有且只有一个直接前驱。当当1 1in-1-1时，时，a
3、i有且只有一个直接后继。有且只有一个直接后继。线性表可以表示为线性表可以表示为 n 个数据元素的有限序列个数据元素的有限序列:(a1 1，ai-1-1，ai，an)线性表的定义第2章 线性表线性表主主要要知知识识点点线性表抽象数据类型线性表抽象数据类型顺序表顺序表链表链表 栈栈 队列队列字符串字符串应用举例应用举例第2章 线性表线性表抽象数据类型数据集合数据集合:a0,a1,an-1,ai的数据类型为的数据类型为DataType操作集合操作集合:(1)Clear()置空线性表置空线性表(2)Append(T value)在表尾添加元素在表尾添加元素(3)Insert(int p,T value
4、)插入数据元素插入数据元素(4)Delete(int p)删除数据元素删除数据元素(5)GetValue(int p,T&value)取数据元素取数据元素第2章 线性表(6)SetValue(int p,T value)更改数据元素更改数据元素(7)GetPos(int p,T value)取数据元素取数据元素线性表的存储顺序存储顺序存储顺序表顺序表链式存储链式存储链表链表第2章 线性表用一组地址连续的存储单元依次存储线性表的数据元素。用一组地址连续的存储单元依次存储线性表的数据元素。a1a2aianbb+lb+(i-1-1)lb+(n-1-1)lb+nl存储地址存储地址内存状态内存状态设每个
5、元素需占用设每个元素需占用 l 个存储单元个存储单元LOC(ai)表示元素表示元素ai的存储地址的存储地址则则LOC(a1)是第一个数据元素是第一个数据元素a1的存储的存储地址，也是整个线性表的起始地址地址，也是整个线性表的起始地址LOC(ai+1)=LOC(ai)+lLOC(ai)=LOC(a1)+(i-1 1)l顺序表第2章 线性表例例2.4 在第在第 i 个数据元素之前插入一个新的元素个数据元素之前插入一个新的元素思想思想:1.将第将第 n 到到 i 个元素均向后移动一个位置。个元素均向后移动一个位置。2.将新元素放置在第将新元素放置在第 i 个位置。个位置。a1ai-1-1aian例，
6、在第例，在第 i 个元素前插入个元素前插入 ba1ai-1-1aianb第2章 线性表例，例，在第在第4个元素之前插入元素个元素之前插入元素25。451293369512345657693325插入插入25第2章 线性表算法时间复杂度算法时间复杂度:移动元素的个数取决于插入元素位置。移动元素的个数取决于插入元素位置。i=1，需移动，需移动 n 个元素；个元素；i=i，需移动，需移动 n i+1 个元素；个元素；i=n+1，需移动，需移动 0 个元素；个元素；第2章 线性表假设假设pi是在第是在第 i 个元素之前插入一个新元素的概率个元素之前插入一个新元素的概率则长度为则长度为 n 的线性表中插
7、入一个元素所需移动元的线性表中插入一个元素所需移动元素次数的素次数的期望值期望值为为:Eis=pi(n i+1)n+1i=1设在任何位置插入元素设在任何位置插入元素等概率等概率，pi=n+11Eis=(n i+1)=n+11i=1n+12nO(n)第2章 线性表例例2.5 删除第删除第 i 个数据元素个数据元素思想思想:a1ai-1-1ai+1ana1ai-1-1ai+1anai1.删除第删除第 i 个数据元素。个数据元素。2.将第将第 i+1 到到 n 个元素均向前移动一个位置。个元素均向前移动一个位置。第2章 线性表例，例，删除第删除第4个元素个元素25。删除删除2545129253369
8、1234567533695第2章 线性表算法时间复杂度算法时间复杂度:移动元素的个数取决于删除元素位置。移动元素的个数取决于删除元素位置。i=1，需移动，需移动n-1 1个元素；个元素；i=i，需移动，需移动n i 个元素；个元素；i=n，需移动，需移动0个元素；个元素；第2章 线性表假设假设qi是删除第是删除第 i 个元素的概率个元素的概率则长度为则长度为 n 的线性表中删除一个元素所需移动元的线性表中删除一个元素所需移动元素次数的素次数的期望值期望值为为:Edl=qi(n i)ni=1设删除任何位置的元素设删除任何位置的元素等概率等概率，qi=n1Edl=(n i)=n1i=1 n2n-1
9、 1O(n)第2章 线性表顺序表各操作的时间复杂度插入一个数据元素的时间复杂度为O(n),删除一个数据元素的时间复杂度为O(n),读取一个数据元素的时间复杂度都为O(1)修改一个数据元素的时间复杂度O(1)第2章 线性表 可随机存取表中任意数据元素，算法简单，空间利用率高；优点:直接可获取线性表的长度缺点:需要预先确定数据元素的最大个数，数据元素的插入、删除相对麻烦，插入和删除时需要移动较多的数据元素。顺序表特点第2章 线性表顺序表应用举例编程实现如下任务编程实现如下任务:建立一个线性表，首先依次建立一个线性表，首先依次输入数据元素输入数据元素1，2，3，10，然后删除数，然后删除数据元素据元
10、素5，最后依次显示当前线性表中的数据，最后依次显示当前线性表中的数据元素。要求采用顺序表实现，假设该顺序表的元素。要求采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过数据元素个数在最坏情况下不会超过100个。个。class SeqList;第2章 线性表多维数组数组（数组（ArrayArray）是数量和元素类型固定的有序序）是数量和元素类型固定的有序序列列静态数组必须在定义它的时候指定其大小和类型静态数组必须在定义它的时候指定其大小和类型动态数组可以在程序运行才分配内存空间动态数组可以在程序运行才分配内存空间第2章 线性表基本概念（续）多维数组（多维数组（Multi-arrayM
11、ulti-array）是向量的扩充）是向量的扩充向量的向量就组成了多维数组向量的向量就组成了多维数组可以表示为：可以表示为：ELEM AcELEM Ac1 1.d.d1 1cc2 2.d.d2 2 ccn n.d.dn n c ci i和和d di i是各维下标的下界和上界。所以其元素个数为：是各维下标的下界和上界。所以其元素个数为：第2章 线性表数组的空间结构二维数组二维数组二维数组二维数组 三维数组三维数组三维数组三维数组d11.3,d21.5,d31.5d11.3,d21.5,d31.5d11.3,d21.5,d31.5d11.3,d21.5,d31.5分别为分别为分别为分别为3 3 3
12、 3个维个维个维个维第2章 线性表数组的存储多维数组的逻辑特征：一个元素可能有多个直接前驱和多维数组的逻辑特征：一个元素可能有多个直接前驱和多个直接后继。多个直接后继。内存是一维的，所以数组的存储也只能是一维的内存是一维的，所以数组的存储也只能是一维的 数组顺序表数组顺序表以行为主序（也称为以行为主序（也称为“行优先行优先”）以列为主序（也称为以列为主序（也称为“列优先列优先”）第2章 线性表以列序为主序以列序为主序a00a10am-1-1,0a01a11am-1-1,1 1a0,n-1-1am-1-1,n-1-1a1 1,n-1-101n-1-1a00 a01 a02 a0,n-1-1a10
13、 a11 a12 a1 1,n-1-1am-1-1,0 am-1-1,1 1 am-1-1,2 am-1-1,n-1-1.Amn 第2章 线性表以行序为主序以行序为主序a00a01a0,n-1-1a10a11a1 1,n-1-1am-1-1,0 0am-1-1,n-1-1am-1-1,1 101m-1-1a00 a01 a02 a0,n-1-1a10 a11 a12 a1 1,n-1-1am-1-1,0 am-1-1,1 1 am-1-1,2 am-1-1,n-1-1.Amn第2章 线性表对于数组，一旦规定了维数和维界，如何计算数组元素的存储位置。对于数组，一旦规定了维数和维界，如何计算数组元
14、素的存储位置。a00a01a0,n-1-1a10a11a1 1,n-1-1am-1-1,0 0am-1-1,n-1-1am-1-1,1 101m-1-1设数组以设数组以行序行序为主序。为主序。设二维数组设二维数组 A(mn)其数组元素其数组元素 aij 的存储位置为的存储位置为LOC(i，j)=LOC(0，0)其中，其中，LOC(0，0)是是a00的存储位置；的存储位置；L是每个数组元素占用的存储单元数；是每个数组元素占用的存储单元数；L例，例，LOC(1，1)=LOC(0，0)+(n1+1)L+(ni+j)L第2章 线性表线性表的链式存储结构线性表的链式存储结构的特点是：的特点是：u用一组用
15、一组任意任意的存储单元存储线性表的数据元素。的存储单元存储线性表的数据元素。u存储单元可以是连续的，也可以是不连续的。存储单元可以是连续的，也可以是不连续的。链 表第2章 线性表结点结点:两部分信息组成，存储数据元素信息的两部分信息组成，存储数据元素信息的数据域数据域，存，存储直接后继存储位置信息的储直接后继存储位置信息的指针域指针域。datanext数据域数据域，存放数据信息，存放数据信息指针域指针域，指向下一个数据单元，指向下一个数据单元单链表第2章 线性表head:头指针头指针，指向链表中第一个结点。，指向链表中第一个结点。tail:尾指针尾指针0:空指针空指针，有时也表示为，有时也表示
16、为“NULL”或或“”。头结点头结点:记录线性表的某些性质信息记录线性表的某些性质信息(如长度如长度)。单链表a1a20anheadtaila1a20anheadtail第2章 线性表typedef struct LinkNode ELEM data；ListNode *next；空表空表:a1a20anheadtail0headtail第2章 线性表单链表特点缺点：缺点：不可随机存取表中任意数据元素不可随机存取表中任意数据元素不可直接获取线性表的长度不可直接获取线性表的长度优点：优点：插入、删除方便插入、删除方便第2章 线性表例，例，取第取第i=3个元素。个元素。p=L-nextj=1p=p
17、-nextj=2p=p-nextj=3e=p-data=Sun时间复杂度时间复杂度:O(n)ZhaoQian0Li LSuntail第2章 线性表优点优点:数据元素的数据元素的插入、删除插入、删除相对方便相对方便在在a，b之间插入元素之间插入元素x:abpxss-next=p-nextp-next=s第2章 线性表删除元素删除元素b:acpbq=p-nextp-next=p-next-next?1)p-next=q-nextq=p-next2)第2章 线性表单链表操作将两个有序单链表合并为一个有序单链表将两个有序单链表合并为一个有序单链表通过比较不断后移指针合并链表。通过比较不断后移指针合并链
18、表。第2章 线性表pa=La-next；pb=Lb-next；/分别指向第一个结点分别指向第一个结点pc-next=pa?pa:pb；/处理剩余部分处理剩余部分while (pa&pb)if (pa-data data)pc-next=pa；pc=pa；pa=pa-next；else pc-next=pb；pc=pb；pb=pb-next；void MergeList_L(LinkList&La，LinkList&Lb，LinkList&Lc)Lc=pc=La；delete Lb；第2章 线性表21350 Lb0627 La6789 Lcpapb,pcpa pcpb Lc pc pbpa Lc
19、 pc pa pbLcpb pa pcLc第2章 线性表双链表双链表的结点有双链表的结点有两个指针域两个指针域:一个指向直接后继，一个指向直接后继，一个指向直接前驱。一个指向直接前驱。priordatanext第2章 线性表性质性质:设设d 是指向某个结点的指针，则有是指向某个结点的指针，则有dd-next-prior=d-prior-next=d操作操作:只涉及单向的操作基本相同，但只涉及单向的操作基本相同，但插入、删除插入、删除操操作变化很大。作变化很大。空表空表:headACheadBtailtail第2章 线性表1)插入插入ABXsp1.找到要在之前插入的结点，找到要在之前插入的结点，
20、p记录。记录。2.s-prior=p-prior；3.p-prior-next-next=s；4.s-next=p；5.p-prior=s；第2章 线性表2)删除删除ACB1.找到要删除的结点，找到要删除的结点，p记录。记录。p2.p-prior-next-next=p-next-next；3.p-next-prior=p-prior；4.delete p；第2章 线性表表中最后一个节点的指针域指向头结点，形成一个环。表中最后一个节点的指针域指向头结点，形成一个环。a1anHead0从表的任意结点出发均可以找到表中的其他结点。从表的任意结点出发均可以找到表中的其他结点。优点优点:循环链表tail空表空表:Headtail第2章 线性表小结及后续内容顺序表的定义、插入、删除、查找操作单链表的定义、插入、删除、查找操作循环链表的定义、操作单链表的应用后续内容：栈第2章 线性表作业习题：2-8提交时间：上机时间检查第2章 线性表