数据结构 线性表.docx

第1讲线性表本章主要掌握如下内容：线性表的定义和基本操作，线性表的实现，线性表的顺序存储结构及链式存储结构，线性表的应用。厂待京.知识点分析（一）线性表的定义和基本操作1 .线性表基本概念1）定义：是由相同类型的结点组成的有限序列。如：由n个结点组成的线性表（气,a,叩a1是最前结点，an是最后结点。结点也称为数据元素或者记录。2）线性表的长度：线性表中结点的个数称为其长度。长度为0的线性表称为空表。3）结点之间的关系：设线性表记为（a.a,a，a, a，a），称a是a的直接前驱结点（简称前驱），1 2i-1 i i+1 ni-1 i- .a是a.的直接后继结点（简称后继）。i+1 i4）线性表的性质： 线性表结点间的相对位置是固定的，结点间的关系由结点在表中的位置确定。 如果两个线性表有相同的数据结点，但它们的结点顺序不一致，该两个线性表也是不相等的。注意：线性表中结点的类型可以是任何数据（包括简单类型和复杂类型），即结点可以有多个成分， 其中能唯一标识表元的成分称为关键字（key），或简称键。以后的讨论都只考虑键，而忽略其它成分，这 样有利于把握主要问题，便于理解。经典例题解析线性表的特点是每个元素都有一个前驱和一个后继。（）【答案】错误。【解析】线性表的第一个数据元素没有前驱，最后一个元素没有后继。其余的所有元素都有一个前 驱和后继。2.线性表的抽象数据类型线性表是一个相当灵活的数据结构，其长度可以根据需要增加或减少。从操作上讲，用户不仅可以对 线性表的数据元素进行访问操作，还可以进行插入、删除、定位等操作。1）线性表的基本操作假设线性表L有数据对象 D=a. | a.ElemSet，i=1,2,3,，n，n>=0,数据元素之间的关系R= <气一1，气小疽或员，2,，n,则线性表L的基本操作如下所示： InitList（&L）：其作用是构造一个长度为0的线性表（空线性表）； DestoryList（&L）：其作用是销毁当前的线性表L； ClearList（&L）：清空线性表L，使之成为空表； ListLength（L）：返回线性表L的长度，即线性表中数据元素的个数； ListEmpty（L）:判断线性表L是否为空表，是则返回True，否则返回False； GetElem（L,i,&e）：将线性表L中第i个数据元素的值返回到变量e中； LocateELem(L,e,compare():判断线性表L中是否存在与e满足compare ()条件的数据元 素，有则返回第一个数据元素； PriorElem(L,cur_e,&pri_e)：返回线性表L中数据元素cur_e的前驱结点； NextElem(L,cur_e,&next_e):返回线性表L中数据元素cur_e的后继结点； ListInsert(&L,i,e)：向线性表L的第i个位置之前插入一个数据元素，其值为e； ListDelete(&L,i,&e)：删除线性表L的第i个数据元素，并将该数据元素的值返回到e中； ListTraverse(L,visit()：遍历线性表中的每个数据元素。2) 线性表的操作举例 用两个线性表La，Lb分别表示两个集合A、B，现要求两个集合的合集，使得A=AUB。操作如下： 依次取出Lb中的元素，然后到La中去找，如果找不到，则将该元素加入La中，同时修改La的长度，如 果Lb中的元素同La中的元素相同，那么按照集合的概念，不再加入到La中。算法描述为：Vbid union(List &La , List Lb)( La_len = length(La) ; Lb_len=length(Lb);for (i = 1 ; i <= Lb_len ; i+) GetElem(Lb,i,e) ; /取出Lb的第i个元素，并将之赋值给eif (!LocateElem(La,e,equal) ListInsert(La,+La_len ,e) ; 有序线性表合并问题：利用抽象数据类型实现两个线性表的合并已知线性表La和Lb中的数据元素按照非递减有序排列，现在要求La和Lb归并为一个新的有序线 性表Lc，使得Lc仍然是非递减有序排列。思想如下：先设Lc为空表，从La、Lb的开头开始，比较La、Lb当前两个元素的大小，将较小者插入到Lc中。 为了比较方便，我们辅设两个指针i和j，让它们分别指向La和Lb即将参与比较的元素。将较小元素插入Lc后，该较小元素所在的线性表上辅设的指针向后移动一个位置(+ 1)，另一个指 针不变，继续参与下一轮比较，这样一直比到某一个线性表结束(i>La_length | | j>Lb_length)。最后再将还没有比较完的线性表中剩余的元素全部插入Lc中即可。算法如下：void MergeList(List La , List Lb , List &Lc)InitList(Lc) ;i=j=1 ; 两个指针初始化，i指向La的第一个元素，j指向Lb的第一个元素k=0 ； 用于存储Lc当前元素个数，初始为0La_Length = length(La) ; Lb_Length= length(Lb);while (i<=La_Length && j<= Lb_Length)GetElem(La,i,ai) ;GetElem(Lb,j,bj);if (ai<=bj) ListInsert(Lc,+k ,ai);i+ ;else ListInsert(Lc,+k,bj);j+; /while/将La或Lb中剩余所有元素全部插入Lc中，以下两句只可能执行一句。while (i<=La_len)( GetElem(La,i+ ,ai) ; ListInsert(Lc,+k,ai) ;While (j<= Lb_len)( GetElem(Lb,j+ , bj) ; ListInsert(Lc,+k ,bj);经典例题解析假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并 为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【解析】因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链 入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时，将链 表结点逆置。LinkedList Union(LinkedList la,lb)la,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法将两链表合并成 一个按元素值递减次序排列的单链表。( pa=la->next; pb=lb->next;pa，pb 分别是链表 la 和 lb 的工作指针la->next=null;la作结果链表的头指针，先将结果链表初始化为空。while(pa!=null && pb!=null) 当两链表均不为空时作( if(pa->data<=pb->data) r=pa->next;将pa的后继结点暂存于r。pa->next=la->next;将pa结点链于结果表中，同时逆置。la->next=pa;pa=r;恢复pa为当前待比较结点。else r=pb->next;将pb的后继结点暂存于r。pb->next=la->next; 将pb结点链于结果表中，同时逆置。la->next=pb;pb=r; 恢复pb为当前待比较结点。while(pa!=null) 将la或lb表的剩余部分链入结果表，并逆置。r=pa->next; pa->next=la->next; la->next=pa; pa=r; while(pb!=null)r=pb->next; pb->next=la->next; la->next=pb; pb=r; 算法Union结束。算法讨论上面两链表均不为空的表达式也可简写为while (pa&&pb),两递增有序表合并成递减有序 表时，上述算法是边合并边逆置。也可先合并完，再作链表逆置。后者不如前者优化。算法中最后两个while 语句，不可能执行两个，只能二者取一，即哪个表尚未到尾，就将其逆置到结果表中，即将剩余结点依次 前插到结果表的头结点后面。(二)线性表的实现1 .顺序存储结构线性表有两种存储方式：顺序存储和链式存储。顺序存储利用大数组或分配了连续内存空间的指针实 现，链式存储利用链表实现。1) 存储方法：利用一个足够大的数组，从第一个元素开始将线性表的结点依次存储在数组中。我们 知道，数组是顺序存储的，利用数组的目的是用数组的顺序存储来体现线性表中结点的先后次序。由此得 到的线性表称为顺序表，具有“随机存取”的特点。 2) 地址表示及计算：线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元 素。设每个元素占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置，则第i+1 个元素的存储位置LOC (ai+i)和第i个元素的存储位置LOC (ai)有如下关系：LOC (ai+i) = LOC(ai)+L假设LOC (a )是线性表第一个数据元素a的存储位置(线性表的起始位置)，则数据元素a的地址计 算公式为：111LOC (ai) = LOC(ai)+ (i-1)XL假设m>n，则有：LOC (a ) = LOC(a ) + (m-n)XL3) 线性表的顺序存储结构定义：# define List_INIT_SIZE 100初始分配量# define LISTINCREMENT 10/ 分配增量typedef struct ElemType *elem ;/带有连续地址块的指针变量，相当于一维数组(向量)int length ； /x线性表的当前长度，即当前数据元素的个数，初始值为0int ListSize ; /线性表当前分配的存储容量(以sizeof(ElemType)为单位) SqList ；线性表初始化时，利用下面的语句为指针成员elem分配连续地址空间：L.elem = (ElemType *) malloc(LIST_INIT_SIZE *sizeof(ElemType);4) 顺序表的各种操作 初始化线性表Status Init_Sq(SqList &L) 构造一个空的线性表L.elem = (ElemType * ) malloc( List_INIT_Size * sizeof(ElemType);if (!L.elem) exit(OVERFLOW) ; / 存储分配失败L.length = 0 ;L.ListSize = List_INIT_Size ;return OK ;重要说明： elem为指针变量。在堆上分配了内存空间的指针变量相当于一个数组，而elem则变为指 向数组基地址的指针变量，可用elemi来表示数组的第i个元素。(elem可看成是数组的 名字) !L.elem 也可写成 L.elem = NULLllllllllllll 之所以用给指针变量分配内存空间的方法定义数组，是因为线性表在使用时很可能是动态 的。如果用数组定义的话，其长度是固定的，不利于动态使用，缺少灵活性。 在第i个元素之前插入一个新元素需要将第i个元素到第n个元素均向后移动一个单位，插入的新元素成为第i个元素，原 来的第i个元素成为第i+1个元素，原来的第n个元素成为第n+1个元素，线性表的长度加1。Status listInsert_Sq(Sqlist &L,int i , ElemType e) / i 的合法取值范围是：1<=i<=ListLength(L) + 1if (i<1 | i > L.length +1) return ERROR ;if (L.length >= L.ListSize)如果存储空间已满，则增加分配 newbase = (ElemType *) realloc(L.elem,(L.ListSize + LISTINCREMENT)*sizeof(ElemType);if (!newbase) exit(OVERFLOW) ; / 存储分配失败L.elem = newbase ; / 新基址L.ListSize += LISTINCREMENT ; / 增加存储容量 q = &(L.elemi-1) ; / q 为插入位置for ( p = &(L.elemL.length-1); p>=q ; -p)*(p+1) = *p ;插入位置以及以后的元素右移*q = e ; /插入 e+L.length ; /表的长度增1return OK ;重要说明：插入操作的主要工作都放在移动元素上。假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：1v +1nE is = (n - i + 1)=i 1除非插入在线性表的最后，否则都要移动元素。 删除第i个元素，并返回其值Status ListDelete_Sq(SqList &L , int i , ElemType &e) if (i<1) II (i>L.length) return ERROR ;P= &(L.elemi-1);e = * p ;q = L.elem + L.length -1 ; /表尾元素位置for (+p ; p<= q ; +p)*(p-1) = *p ; /被删除元素之后的所有元素左移-L.length;return OK ;重要说明：在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为:E危1才- i)=守i 15) 顺序存储方式的特点：优点：能直接访问线性表的任一结点，访问时间几乎不受结点存储位置的影响，这就是所谓的“随 机存取”机制。缺点： 数组长度固定，动态性太差； 执行结点插入、删除操作将移动大量数据。6) 重要结论： 一般情况下，在顺序表的第i(1<=i<=n)个元素之前插入一个元素，需要将第n至i的元素(共n-i+1个元素)向后移动一个位置。 . . 一般情况下，删除顺序表的第i (1<=i<=n)个元素时需要将第i+1到第n个元素(共n-i个 元素)依次向前移动一个位置。 在顺序表中插入或者删除一个数据元素，平均约需移动一半元素，设表长为n，则插入算法 和删除算法的时间复杂度为O(n)。7) 一个应用：顺序表的合并有两个线性表La、Lb，其数据元素均是非递减排列的，要求合并La、Lb为一个新的线性表 Lc，且Lc也是非递减排列的。void MergeList_Sq(SqList La , SqList Lb , SqList &Lc)( pa = La.elem ; pb = Lb.elem ; /取得 La , Lb 的基地址Lc.ListSize = La.Length + Lb.Length ;pc = Lc.elem = (ElemType *) malloc(Lc.ListSize*sizeof(ElemType);if (!Lc.elem) exit(OVERFLOW);pa_Last = pa + La.length -1 ;pb_Last = pb + Lb.length - 1 ;归并while (pa <= pa_Last && pb<= pb_Last)if (*pa<=*pb) *pc+ = *pa+ ;else *pc+=*pb+ ;插入La、Lb的剩余元素while (pa <= pa_Last) *pc+ = *pa+ ;while (pb <= pb_Last) *pc+ = *pb+ ;重要说明： 由于合并后数据元素要放到Lc中，所以算法的主要操作是“复制”。如果将Lb中的数据插 入到La中，则需要移动La的元素。 La、Lb均为顺序表，否则无法进行合并操作。如果原来的线性表不是顺序表，需要用排序 算法先进行排序。有关排序算法，后文有专门介绍。经典例题解析1. 下述哪一条是顺序存储结构的优点？()A. 存储密度大B-插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示【答案】A。【解析】顺序存储利用物理的邻接关系表示数据元素之间的逻辑关系，因此没有必要设置指针域， 所以其存储密度比链式存储大，但是插入运算和删除运算都需大量移动数据元素，并不方便；D选项并不 是顺序存储结构的优点。2. 下面关于线性表的叙述中，错误的是哪一个？()A. 线性表采用顺序存储，必须占用一片连续的存储单元。B. 线性表采用顺序存储，便于进行插入和删除操作。C. 线性表采用链接存储，不必占用一片连续的存储单元。D. 线性表采用链接存储，便于插入和删除操作。【答案】B。【解析】线性表采用顺序存储，并不便于进行插入和删除操作。3. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用() 存储方式最节省时间。A.顺序表B-双链表C.带头结点的双循环链表D.单循环链表【答案】A。【解析】“存取任一指定序号”最好的方法是实现“随机存取”，则可采用顺序表。并且，因为插 入和删除操作都是在最后进行的，因此无需大量移动数据元素，选项A是最合适的。4. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为()(1<=i<=n+1)。A. O(0) B. O(1)C. O(n)D. O(n2)【答案】C。【解析】顺序存储的线性表在插入新元素时，涉及到大量数据元素的移动，其时间复杂度为O(n)。5. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为()。A. O(n) O(n) B. O(n) O(1) C. O(1) O(n)D. O(1) O(1)【答案】C。【解析】顺序存储可以实现“随机存取”，因此访问结点的时间复杂度为O(1)，而插入、删除结 点由于涉及到大量移动元素，故其时间复杂度为O(n)。2 .链式存储结构2.1链式存储结构之一：单链表利用单链表(也称线性链表)来实现，从链表的第一个数据元素开始，依次将线性表的结点存入。需 要注意的是，链表的每个数据元素除了要存储线性表的数据元素信息之外，还要有一个成分存储其后继结 点的指针，单链表就是通过这个指针来表明数据元素之间的先后关系的。单链表在保存时，一般在第一个结点之前辅设一个结点，称为头结点。头结点的数据域可以不存任何 信息，也可以存储线性表的长度等附加信息，其指针域中存储指向第一个结点的指针(即第一个元素结点 的存储位置)。故单链表的头指针指向头结点，如果头结点的指针域为空，则说明是空表(head->next =NULL)。图1-1带头结点的单链表1) 单链表结构typedef struct LNode(ElemType data ;struct LNode * next ;LNode , *LinkList ;2) 单链表的各种操作取得第i个元素的值Status GetElem_L(LinkList L , int i , ElemType &e) /L为带头结点的单链表的头指针p = L.next ; /p指向第一个结点j = 1 ;while （p && j<i）（ p = p->next ;j+ ；if （!p II j>i） return ERROR ; / 不存在e= p->data ;return OK ;说明：读取第i个元素须从头指针开始查找，因此单链表是一种“非随机存取”的数据结构。 单链表的插入操作：在单链表L的某结点（设该结点由指针p指向）之后插入一个新的数据元素。设该新数据元素由s指向。操作如下：s->next = p->next : p->next = s;（注意语句顺序） 单链表的删除操作：在单链表L中的某结点（该结点由指针p指向）之后的结点需要删除，则操作为: q = p->next : p->next = q->next :free（q）;如果不考虑释放被删除的结点，则下面的操作也是正确的：p->next = p->next->next ;3）链式存储的特点优点：每个数据元素的实际存储位置可以任意，数据元素的插入、删除变得非常容易；缺点： 每个数据元素增加了后继指针成分，增加了存储空间，降低了存储密度；不能随机访问线性表的任一结点。（同顺序存储恰恰相反）4）静态链表有时也可以采用一维数组来描述线性链表，其类型说明如下所示。#define MAXSIZE 100tyepdef struct ElemType data ;int cur ; component , SLinkListMAXSIZE;可以看出，以上结构中没有出现“指针”类型的指针域，而是利用一个指示器cur来表示结点在数组 中的相对位置。可以将数组的第0分量看成头结点，其指针域（cur）指示链表的第一个结点。这种存储 结构仍需要分配较大的连续空间，但是在进行线性表的插入及删除操作时不需要移动元素，而仅需要修改 指针，因此仍然具有链式存储结构的主要优点。为了和指针描述的线性链表相区别，我们称这种用数组实 现的链表为静态链表。经典例题解析1. (1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3)静态链表 与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是()A. (1), (2)B. (1)C. (1), (2) ,(3) D. (2)【答案】B。【解析】静态链表使用结构体数组来实现线性链表的功能。因为其用游标cur来指示下一个数据元 素的存储位置，因此存取数据时静态链表同线性链表(单链表)是相似的。也就是说，静态链表在存取表 中第i个元素的时间同i是相关的。2. 线性表(气，气，,气)以链接方式存储时，访问第i位置元素的时间复杂性为()D. O （i-1）A. O (i)B. O (1) C. O (n)【答案】C。 【解析】略。)。C. p=NILD. p= head3. 非空的循环单链表head的尾结点p f满足( A. p f .link=head B. p f .link=NIL 【答案】A。 【解析】略。2.2链式存储结构之二：循环链表表中最后一个结点的指针指向头结点，整个链表形成一个环。其特点为：从表中任何一个结点出发， 都可以找到表中其它结点。设p指向最后一个结点(如上图)，则循环结束的条件是：p.冲眼亍H，. H为线性表的头指针。 循环链表在实现时，有时设置尾指针，而不设置头指针，如下图所示。图1-3设置尾指针的循环链表将B接到A的后面，语法为: q = rear2.next ;rear2.next = rearl.next ;rearl.next = q.next ;链接后，得到：图1-4连接两个链表此时，B中原来的头结点就可以被释放了，如可用free（q）;经典例题解析1.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（） 存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表（1双链表D .仅有尾指针的单循环链表【答案】D。【解析】仅有尾指针的单循环链表，可以非常方便的找到尾结点，尾结点后面的第一个结点往往 是头结点，头结点的下一个结点就是第线性表的第一个结点。对最后一个元素和第一个元素操作对带尾指 针的单循环链表是非常方便的。2.3链式存储结构之三：双向循环链表单链表的数据结构中只提供一个指向后继的指针域，因此，当需要查找某结点的前驱时，只能从表头 指针出发，效果较差。为解决此问题，提出了双向链表的思想。双向链表是为了方便查找结点的前驱而设 计的，表中的结点不仅有一个指向其直接后继的指针域，还有一个指向其直接前驱的指针域，如下图所示。1）双向循环链表的数据结构Typedef struct DuLNode（ ElemType data ;struct DulNode * prior ; / 前驱指针struct DulNode * next ; / 后继指针 DulNode , *DuLinkList ;priordatanext图1-5双向循环链表设d为指向某结点的指针，则下式成立：d->next ->prior =d->prior->next = d2）双向链表的插入、删除操作同单链表相比，双向链表的插入、删除操作需同时修改两个指针，因此操作较为复杂。插入一个结点步骤：s->prior = p->prior ;p->prior->next = s ; s->next = p ;p->prior = s ;删除一个结点b步骤：p->prior->next = p->next ; p->next->prior = p->prior ; free(p);