线性表数据结构.pptx

《线性表数据结构.pptx》由会员分享，可在线阅读，更多相关《线性表数据结构.pptx（49页珍藏版）》请在三一办公上搜索。

1、前言,数据结构是相互之间存在一种或多种特定关系的数据元素的集合。同样是结构，从不同的角度来讨论，会有不同的分类，如图1所示。逻辑结构：数据对象中数据元素之间的相互关系。物理结构：数据结构在计算机中的表示（映像）称为数据的物理（存储）结构。线性结构：线性表、栈和队列、串、数组和广义表。,图1 线性表的数据结构,前言,抽象数据类型(Abstract Data Type 简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系。抽象数据类型描述的一般形式如下：ADT 抽象数据类型名称 数据对象：数据关系：

2、操作集合：操作名1：操作名n：ADT抽象数据类型名称,线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继。可以有这样一些操作：插入一个元素、删除一个元素等。,线性表的概念及运算The Concepts and Operations of Linear List,线性表的顺序存储Sequence Storage of Linear List,线性表的链式存储 Linked Storage of Linear List,顺序表与链表的比较Comparision between the two Linear Li

3、sts,CONTENT,01,线性表的概念及运算,The Concepts and Operations of Linear List,PART ONE,1.线性表的概念及运算,线性表(Linear List)是由n(n0)个类型相同的数据元素a1,a2,，an组成的有限序列，记做（a1,a2,，ai-1，ai，ai+1，an）。对于n0，除第一个元素无直接前驱、最后一个元素无直接后继外，其余的每一个数据元素只有一个直接前驱和一个直接后继。线性表的特点同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。有序性：线性

4、表中相邻数据元素之间存在着序偶关系。,图1.1 线性表的逻辑结构,1.线性表的概念及运算,线性表存储方式实现线性表在计算机中的存放有顺序存储与链式存储两种方式。线性表顺序存储（顺序表）：采用静态分配方式，借助于C语言的数组类型，申请一组连续的地址空间，依次存放表中元素，其逻辑次序会在存储顺序之中。线性表链式存储（链表）：采用动态分配方式，借助于C语言的指针类型，动态申请与动态释放地址空间，故链表中的各结点的物理存储可以是不连续的。,1.线性表的概念及运算,抽象数据类型定义：ADT LinearList数据元素：D=ai|aiD0,i=1,2,，n n0，D0为某一数据对象结构关系：|ai,ai

5、+1D0，i=1,2,n-1基本操作：（1）InitList（L）操作前提：L为未初始化线性表。操作结果：将L初始化为空表。（2）DestroyList(L)操作前提：线性表L已存在。操作结果：将L销毁。（3）ClearList(L)操作前提：线性表L已存在。操作结果：将表L置为空表。,1.线性表的概念及运算,（4）EmptyList（L）操作前提：线性表L已存在。操作结果：如果L为空表则返回真，否则为假。（5）ListLength(L)操作前提：线性表L已存在。操作结果：如果L为空表则返回0，否则返回表中元素个数。（6）Locate(L,e)操作前提：表L已存在，e为合法元素值。操作结果：如

6、果L中存在元素e，则将“当前指针”指向元素e所在位置并返回真，否则返回假。,1.线性表的概念及运算,（7）GetData（L,i）操作前提：表L存在,且i值合法，即1iListlength（L）。操作结果：返回线性表L中第i个元素的值。（8）InsList(L,i,e)操作前提：表L已存在，e为合法元素，且1iListlength(L)+1。操作结果：在L中第i个位置插入新的数据元素e，L的长度加1。（9）DelList(L,i,&e)操作前提：表L已存在且非空，1iListlength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。ADT LinearList,02,

7、线性表的顺序存储,Sequence Storage of Linear List,PART TWO,2.线性表的顺序存储,2.1 基本概念,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。将顺序表归纳为：关系线性化，结点顺序存。假设线性表中有n个元素，每个元素占k个单元，第一个元素的地址为loc(a1)，则可通过如下公式计算出第i个元素的地址loc(ai)为：loc(ai)=loc(a1)+(i-1

8、)k 其中loc(a1)称为基地址。,2.1 基本概念,图2.1 顺序存储结构示意图,2.1 基本概念,顺序存储结构的C语言定义#definemaxsize=线性表可能达到的最大长度；typedef struct ElemType elemmaxsize；/*线性表占用的数组空间*/int last；/*记录线性表中最后一个元素在数组elem 中的位置（下标值），空表置为-1*/SeqList；注意区分元素的序号和数组的下标，如a1的序号为1，而其对应的数组下标为0。,2.2 基本算法,2.2.1 查找操作,按序号查找GetData(L,i)：要求查找线性表L中第i个数据元素，其结果是L.el

9、emi-1或L-elemi-1。按内容查找Locate(L,e)：要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。,2.2.1 查找操作,按内容查找：int Locate(SeqList L，ElemType e)i=0;/*i为扫描计数器，初值为0，即从第一个元素开始比较*/while(i=L.last)/*若没找到，则返回空序号*/,图2.2.查找操作,2.2.2 插入操作,线性表的插入运算是指在表的第i(1in+1)个位置，插入一个新元素e，使长度为n的线性表(e1，ei-1，ei，en

10、)变成长度为n+1的线性表（e1，,ei-1，e，ei，en）。线性表的插入运算算法已知：线性表(4,9,15,28,30,30,42,51,62)，需在第4个元素之前插入一个元素“21”。则需要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”插入到第4个位置。要点：将第9个到第4个的元素依次后移一个位置，将“21”插入到第4个位置。,2.2.2 插入操作,int InsList(SeqList*L,int i,ElemType e)int k;if(iL-last+2)/*首先判断插入位置是否合法*/printf(“插入位置i值不合法”)；return(ERROR);if(L-

11、last=maxsize-1)printf(“表已满无法插入”)；return(ERROR);for(k=L-last;k=i-1;k-)/*为插入元素而移动位置*/L-elemk+1=L-elemk;L-elemi-1=e;/*在C语言中数组第i个元素的下标为i-1*/L-last+;return(OK);,图2.3 插入操作,2.2.3 删除操作,线性表的删除运算是指将表的第i(1in)个元素删去，使长度为n的线性表(e1，,ei-1，ei，ei+1，en)，变成长度为n-1的线性表(e1，,ei-1，ei+1，en)。将线性表(4,9,15,21,28,30,30,42,51,62)中的

12、第5个元素删除。,图2.4.删除操作,2.2.3 删除操作,int DelList(SeqList*L,int i,ElemType*e)/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值*/int k;if(iL-last+1)printf(“删除位置不合法！”)；return(ERROR)；*e=L-elemi-1;/*将删除的元素存放到e所指向的变量中*/for(k=i;ilast;k+)L-elemk-1=L-elemk;/*将后面的元素依次前移*/L-last-;return(OK);,图2.5 删除操作,2.2.4 顺序表合并算法,已知：有两个顺序表LA和LB，其元素均为非

13、递减有序排列，编写一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排列。算法思想：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i、j分别指向表LA和LB中的元素，若LA.elemiLB.elemj，则当前先将LB.elemj插入到表LC中，若LA.elemiLB.elemj，当前先将LA.elemi插入到表LC中，如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。,2.2.4 顺序表合并算法,void merge(SeqList*LA,SeqList*LB,SeqList*LC)i=0;j=0;k=0;while(ilast,

14、2.3 优缺点分析,优点：1.无需为表示结点间的逻辑关系而增加额外的存储空间；2.可方便地随机存取表中的任一元素。缺点：1.插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低；2.由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配。因此当表长变化较大时，难以确定合适的存储规模。,03,线性表的链式存储,Linked Storage of Linear List,PART THREE,2.线性表的顺序存储,单链表的基本运算,3.2,3.1 基本概念,结点：存储线性表的每个数据元素值的信息与元素间逻辑关系（即后继结点地址信息）的两部

15、分存储映象。链表：采用链式存储结构的线性表称为链表。单链表：链表中的每个结点只有一个指针域，我们将这种链表称为单链表。单链表包括两个域：数据域用来存储结点的值；指针域用来存储数据元素的直接后继的地址（或位置）。头指针：指向链表头结点的指针。现在我们从两个角度来讨论链表：1.从实现角度看，链表可分为动态链表和静态链表；2.从链接方式的角度看，链表可分为单链表、循环链表和双链表。,图3.1 带头结点的单链表,3.1 基本概念,3.2 单链表的示例图,3.1 基本概念,单链表的存储结构描述,typedef struct Node/*结点类型定义*/ElemType data；struct Node*

16、next；Node,*LinkList；/*LinkList为结构指针类型*/,3.2 基本算法,3.2.1 建立单链表,尾插法建表,Linklist CreateFromTail()/*将新增的字符追加到链表的末尾*/LinkList L;Node*r,*s;int flag=1;L=(Node*)malloc(sizeof(Node);/*为头结点分配存储空间*/L-next=NULL;r=L;/*r指针始终动态指向链表的当前表尾*/while(flag)/*标志，初值为1。输入“$”时flag为0，建表结束*/c=getchar();if(c!=$)s=(Node*)malloc(siz

17、eof(Node);s-data=c;r-next=s;r=s else flag=0;r-next=NULL;,图3.3 尾插法建表,3.2.1 建立单链表,头插法建表,Linklist CreateFromHead()LinkList L;Node*s;int flag=1;/*设置一个标志，初值为1，当输入“$”时，flag为0，建表结束*/L=(Linklist)malloc(sizeof(Node)；/*为头结点 分配存储空间*/L-next=NULL;while(flag)c=getchar();if(c!=$)/*为读入的字符分配存储空间*/s=(Node*)malloc(siz

18、eof(Node);s-data=c;s-next=L-next;L-next=s;elseflag=0;,图3.4 头插法建表,3.2.2 单链表查找,按序号查找 算法描述：设带头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链表的头指针L出发，从头结点（L-next）开始顺着链域扫描，用指针p指向当前扫描到的结点,初值指向头结点（pL-next），用j做记数器，累计当前扫描过的结点数（初值为0），当j=i 时，指针p所指的结点就是要找的第i个结点。/*在带头结点的单链表L中查找第i个结点，若找到(1in)，则返回该结点的存储位置;否则返回NULL*/Node*Get(LinkLi

19、st L,int i)Node*p；p=L；j=0；/*从头结点开始扫描*/while(p-next!=NULL)&(jnext；j+；/*扫描下一结点*/*已扫描结点计数器*/if（i=j）return p；/*找到了第i个结点*/else return NULL；/*找不到，i0或in*/,图3.5 按序号查找,3.2.2 单链表查找,按值查找算法描述：按值查找是指在单链表中查找是否有结点值等于e的结点，若有的话，则返回首次找到的其值为e的结点的存储位置，否则返回NULL。查找过程从单链表的头指针指向的头结点出发，顺着链逐个将结点的值和给定值e作比较。/*在带头结点的单链表L中查找其结点值

20、等于key的结点，若找到则返回该结点的位置p，否则返回NULL*/Node*Locate(LinkList L,ElemType key)Node*p;p=L-next;/*从表中第一个结点比较*/while(p!=NULL)if(p-data!=key)p=p-next;else break;/*找到结点key，退出循环*/return p;,图3.6 按值查找,3.3.3 单链表插入,插入操作要在带头结点的单链表L中第i个数据元素之前插入一个数据元素e，需要首先在单链表中找到第i-1个结点并由指针pre指示，然后申请一个新的结点并由指针s指示，其数据域的值为e，并修改第i-1个结点的指针使

21、其指向s，然后使s结点的指针域指向第i个结点。void InsList(LinkList L,int i,ElemType e)/*在带头结点的单链表L中第i个结点之前插入值为e的新结点。*/Node*pre,*s;pre=L;int k=0;while(pre!=NULL,3.7 单链表插入,3.3.4 单链表删除,删除操作欲在带头结点的单链表L中删除第i个结点，则首先要通过计数方式找到第i-1个结点并使p指向第i-1个结点，而后删除第i个结点并释放结点空间。,void DelList(LinkList L,int i,ElemType*e)/*在带头结点的单链表L中删除第i个元素，并保存其

22、值到变量*e中*/Node*p,*r;p=L;int k=0;while(p-next!=NULL/*释放被删除的结点所占的内存空间*/,3.8单链表删除,3.3 其它链表,双向链表：在单链表的每个结点里再增加一个指向其前趋的指针域prior。这样形成的链表中就有两条方向不同的链，我们称之为双(向)链表(Double Linked List)。有时候以倒序扫描链表很方便。标准实现方法此时无能为力，然而解决方法却很简单。只要在数据结构上附加一个域，使它包含指向前一个单元的指针即可。其开销是一个附加的链，它增加了空间的需求，同时也使得插入和删除的开销增加一倍，因为有更多的指针需要定位。另一方面，它

23、简化了删除操作，因为你不再被迫使用一个指向前驱元的指针来访问一个关键字；这个信息是现成的。表示一个双链表。双向链表的结构定义：typedef struct Dnode ElemType data；struct DNode*prior，*next；DNode,*DoubleList；,3.9 双向链表,3.3 其它链表,循环链表(Circular Linked List)是一个首尾相接的链表。将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，并称为循环单链表。在循环单链表中，表中所有结点被链在一个环上。让最后的单元反过来直指第一个单元是一种流

24、行的做法。它可以有表头，也可以没有表头（若有表头，则最后的单元指向它），并且还可以是双向链表（第一个单元的前驱元指针指向最后的单元）。这无疑会影响某些测试，不过这种结构在某些应用程序中却很流行。显示了一个无表头的双向循环链表。,3.10 循环链表,04,顺序表与链表的比较,Comparision between the two Linear Lists,PART FOUR,4.顺序表与链表的比较,实际比较,4.1 简要概述,顺序表的特点是逻辑上相邻的数据元素，物理存储位置也相邻，并且，顺序表的存储空间需要预先分配。它的优点是：（1）方法简单，各种高级语言中都有数组，容易实现。（2）不用为表示节

25、点间的逻辑关系而增加额外的存储开销。（3）顺序表具有按元素序号随机访问的特点。缺点：（1）在顺序表中做插入、删除操作时，平均移动表中的一半元素，因此对n较大的顺序表效率低。（2）需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。,4.1 简要概述,在链表中逻辑上相邻的数据元素，物理存储位置不一定相邻，它使用指针实现元素之间的逻辑关系。并且，链表的存储空间是动态分配的。链表的最大特点是：插入、删除运算方便。缺点：（1）要占用额外的存储空间存储元素之间的关系，存储密度降低。存储密度是指一个节点中数据元素所占的存储单元和整个节点所占的存储单元之比。（2

26、）链表不是一种随机存储结构，不能随机存取元素。,4.2.1 基于空间的考虑,顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MaxSize”要有合适的设定，设定过大会造成存储空间的浪费，过小造成溢出。因此，当对线性表的长度或存储规模难以估计时，不宜采用顺序表。然而，链表的动态分配则可以克服这个缺点。链表不需要预留存储空间，也不需要知道表长如何变化，只要内存空间尚有空闲，就可以再程序运行时随时地动态分配空间，不需要时还可以动态回收。因此，当线性表的长度变化较大，难以估计其存储规模时，采用动态链表作为存储结构较好。存储密度(Storage Density)是指

27、结点数据结构本身所占的存储量和整个结点结构所占的存储量之比。一般地，存储密度越大，存储空间的利用率就高。显然，顺序表的存储密度为1，而链表的存储密度小于1。因此，当线性表的长度变化不大而且事先容易确定其大小时，为节省存储空间，则采用顺序表作为存储结构比较适宜。,4.2.2 基于时间的考虑,顺序存储是一种随机存取的结构，而链表则是一种顺序存取结构，因此它们对各种操作有完全不同的算法和时间复杂度。例如，要查找线性表中的第i个元素，对于顺序表可以直接计算出a(i)的的地址，不用去查找，其时间复杂度为0(1)。而链表必须从链表头开始，依次向后查找，平均需要0(n)的时间。因此，若线性表的操作主要是进行

28、查找，很少做插入和删除时，宜采用顺序表做存储结构。在顺序表中做插入，删除时平均移动表中一半的元素，当数据元素的信息量较大而且表比较长时，这一点是不应忽视的；在链表中的任何位置进行插入和删除时，都只需要修改指针。因此，对于频繁进行插入和删除的线性表，宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端，则宜采用为指针表示的单循环链表。,4.2.3 基于语言的考虑,顺序表容易实现，任何高级语言中都有数组类型；链表的操作是基于指针的。相对来讲前者简单些，也用户考虑的一个因素。在没有提供指针的高级语言环境中，若要采用链表结构，则可以使用光标实现的动态链表。虽然静态链表在存储分配上有不足之处，但

29、它是和动态链表一样，具有插入和删除方便的特点。值得指出的是，即使是对那些具有指针类型的语言，静态链表也有其用武之地。特别是当线性表的长度不变，仅需改变结点之间的相对关系时，静态链表比动态链表可能更方便。总之，两种存储结构各有长短，选择哪一种由实际问题中的主要因素决定。通常“较稳定”的线性表，即主要操作是查找操作的线性表，适于选择顺序存储；而频繁做插入删除运算的（即动态性比较强）的线性表适宜选择链式存储。,4.3 相关技术,线性表的操作特点顺链操作技术：从头开始，访问单链表L中结点i（p指向该结点）时，由于第i个结点的地址在第i-1个结点（pre指向该结点，为p的前驱）的指针域中存放，查找必须从

30、单链表的“首结点”开始（p=L）；通过p=p-next并辅助计数器来实现；指针保留技术：对第i个结点进行插入、删除等操作时，要对第i-1个结点的指针域进行链址操作（pre-next）。因此在处理过程中始终需要维持当前指针p及其前驱指针pre的关系，将这种技术简称为“指针保留技术”。,4.3 相关技术,链表处理中的相关技术单链表与多重链表的差别在于指针域的个数。一般链表与循环链表的差别在于是否首尾相接，将非空表、空表等多种情况统一处理，以方便运算。判断当前结点p是否为表尾：一般链表中，p结点是表尾的条件是：该结点的后继指针值为空指针即：p-next=NULL；循环链表中，p结点是表尾结点的条件是：该结点的后继指针值为头指针值即：p-next=head。链表的表长度n值并未显式保存：由于链表是动态生成的结构，其长度要通过顺链查找到表尾得到。因此在处理链表时，往往以当前处理位置结点p是否为表尾作为控制条件。,