数据结构本课程辅导与练习

数据结构(本)课程辅导与练习线性表一、相关术语线性表、直接前驱、直接后继、顺序表、链表、指针、指针变量、结点、数据域、单向链表、单向循环链表、双向循环链表、插入、删除二、线性表的定义及特点线性表(linear_list)是属于同一个数据对象的数据元素的有限序列。通常表示为：(%%，％.・.，%)其中n为线性表的长度，当n=0时，表示一个空表。线性表是一种最常用的数据结构，数据元素之间的关系表现为：除第一个元素无直接前驱，最后一个元素无直接后继外，其余元素均有且仅有一个直接前驱和一个直接后继。线性表的存储结构有两种实现方法式：顺序存储和链式存储。三、顺序表.顺序表的定义(1)顺序存储方法即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。(2)顺序表(SequentialList)用顺序存储方法存储的线性表简称为顺序表(SequentialList)。.结点ai的存储地址不失一般性，设线性表中所有结点的类型相同，则每个结点所占用存储空间大小亦相同。假设表中每个结点占用c个存储单元，其中第一个单元的存储地址则是该结点的存储地址，并设表中开始结点a1的存储地址(简称为基地址)是LOC(a1)，那么结点ai的存储地址LOC(aj可通过下式计算：LOC(ai)=LOC(a1)+(i-1)*cIWiWn注意：在顺序表中，每个结点ai的存储地址是该结点在表中的位置i的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址。是一种随机存取结构。.顺序表类型定义typedefstruct{datatypedata[MAXSIZE]；/*定义线性表为一维数组*/intlength；/*length为线性表当前的长度*/}SeqList；其中data是一维数组，MAXSIZE是数组data所能容纳元素的最大值，也称为顺序表的容量；length是线性表当前的实际长度，线性表中第1,2，…，length个元素分别存放在数组第0,1,…，length-1的位置上；datatype是线性表元素的类型，应视具体情况而定，可以是整形、字符型等，例如线性表是英文字母表，则datatype就是字符型。.顺序表的特点顺序表的特点是逻辑上相邻的结点其物理位置也相邻。.顺序表上实现的基本运算(1)插入线性表的插入运算是指在表的第i（1WiWn+1）个位置上，插入一个新结点x,使长度为n的线性表：（a1，…，ai1，a.，…a）变成长度为n+1的线性表：（a1，…，a.1，x，a.，…a）在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将表中位置为n，n-1，…，i上的结点，依次后移到位置n+1，n，…，i+1上，空出第i个位置，然后在该位置上插入新结点x。仅当插入位置i=n+1时，才无须移动结点，直接将x插入表的末尾。具体算法描述教材P9【算法2-1】线性表的顺序存储具有三个弱点：（1）在做插入或删除操作时，需要移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分的利用;（3）表的容量难以扩充。•算法分析①问题的规模表的长度L->length（设值为n）是问题的规模。②移动结点的次数由表长n和插入位置i决定算法的时间主要花费在for循环中的结点后移语句上。该语句的执行次数是n-i+1。当i=n+1：移动结点次数为0,即算法在最好时间复杂度是0（1）

当i=1：当i=1：移动结点次数为n,即算法在最坏情况下时间复杂度是0(n)(5)删除线性表的删除运算是指将表的第i(IWiWn)个结点删去，使长度为n的线性表(a/…，a」，a.,a.+i，…，a)变成长度为n-1的线性表(ai，…，ai-i，%,•••,an)在顺序表上实现删除运算必须移动结点，才能反映出结点间的逻辑关系的变化。若i=n,则只要简单地删除终端结点，无须移动结点；若1WiWn-1,则必须将表中位置i+1,i+2,…，n的结点，依次前移到位置i,i+1,…，n-1上，以填补删除操作造成的空缺。具体算法描述参见教材P11【算法2-2】•算法分析①结点的移动次数由表长n和位置i决定：i=n时，结点的移动次数为0,即为0(1)i=1时，结点的移动次数为n-1,算法时间复杂度分别是0(n)②移动结点的平均次数,顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是0(n)。四、链表.链接存储方法链接方式存储的线性表简称为链表(LinkedList)。链表的具体存储表示为:①用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）②链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链（link））注意：链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。.链表的结点结构datanextdata域：存放结点值的数据域next域：存放结点的直接后继的地址（位置）的指针域（链域）注意：①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。②每个结点只有一个链域的链表称为单链表（SingleLinkedList）。.malloc函数和free函数①生成结点变量的标准函数mallocp=（ListNode*）malloc（sizeof（ListNode））；/*函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中*/②释放结点变量空间的标准函数free（free(p)；/*释放p所指的结点变量空间*/4、单链表的运算(1)尾插法建表算法思路：从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到读入结束标志为止。头结点是在链表的开始结点之前附加一个结点。它具有两个优点：(1)由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理；(2)无论链表是否为空，其头指针都是指向头结点的非空指针(空表中头结点的指针域空)，因此空表和非空表的处理也就统一了。具体算法参见教材P15【算法2-3】。注意：(1)采用尾插法建表，生成的链表中结点的次序和输入顺序一致(2)须增加一个尾指针r,使其始终指向当前链表的尾结点(2)头插法建表算法思路：从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表头上,直到读入结束标志为止。具体算法参见教材P17【算法2-4】。注意：该方法生成的链表的结点次序与输入顺序相反。(3)按序号查找①链表不是随机存取结构在链表中，即使知道被访问结点的序号i,也不能像顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构。②查找的思想方法计数器j置为0后，扫描指针p指针从链表的头结点开始顺着链扫描。当p扫描下一个结点时，计数器j相应地加1。当j=i时，指针p所指的结点就是要找的第i个结点。而当p指针指为null且jWi时，则表示找不到第i个结点。注意：头结点可看做是第0个结点。③具体算法实现ListNode*GetNode(LinkListhead,inti){/*在带头结点的单链表head中查找第i个结点，若找到(OWiWn),则返回该结点的存储位置，否则返回NULL。*/intj;ListNode*p;p=head;j=0;/*从头结点开始扫描*/while(p->next&&j<i){/*顺指针向后扫描，直到p->next为NULL或i=j为止*/p=p->next;j++;if（i==j）returnp;/*找到了第i个结点*/elsereturnNULL;/*当i<0或i>0时，找不到第i个结点*/）（4）插入运算思想方法插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。具体步骤：（1）找到a-置p（2）生成一个数据域为x的新结点*s（3）令结点*p的指针域指向新结点（4）新结点的指针域指向结点ai。（2）具体算法实现参见教材P18【算法2-5】（3）算法分析算法的时间主要耗费在查找操作上，故时间复杂度亦为O（n）。（5）删除运算思想方法删除运算是将表的第i个结点删去。具体步骤：(1)找到ai-1的存储位置p(因为在单链表中结点ai的存储地址是在其直接前趋结点ai1的指针域next中)(2)令p->next指向ai的直接后继结点(即把曾从链上摘下)(3)释放结点ai的空间，将其归还给〃存储池〃。具体算法实现参见教材P20【算法2-6】注意：设单链表的长度为n,则删去第i个结点仅当IWiWn时是合法的。当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在(即p!二NULL)且*p不是终端结点(即p->next!二NULL)时，才能确定被删结点存在。线性表的链式存储结构一般来说克服了顺序存储结构的三个弱点，首先，插入和删除操作不需要移动元素，只修改指针；其次，不需要预先分配空间，可根据需要动态申请空间；其三是表容量只受可用内存空间的限制。•算法分析算法的时间复杂度也是O(n)。链表上实现的插入和删除运算，无须移动结点，仅需修改指针。五、顺序表和链表的比较顺序表和链表各有优缺点。在实际应用中究竟选用哪一种存储结构呢？这要根据具体问题的要求和性质来决定。通常有以下几方面的考虑：

顺序表链表基于空间考虑基于时间考虑分配方式静态分配。程序执行之前必须明确规定存储规模。若线性表长度n变化较大，则存储规模难于预先确定估计。过大将造成空间浪费，估计太小又将使空间溢出机会增多。动态分配只要内存空间尚有空闲，就不会产生溢出。因此，当线性表的长度变化较大，难以估计其存储规模时，以采用动态链表作为存储结构为好。存储密度为1。当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。<1存取方法随机存取结构，对表中任一结点都可在O（1）时间内直接取得线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜。顺序存取结构，链表中的结点，需从头指针起顺着链扫描才能取得。插入删除操作在顺序表中进行插入和删除，平均要移动表中近一半的结点，尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。在链表中的任何位置上进行插入和删除，都只需要修改指针。对于频繁进行插入和删除的线性表，宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜六、练习题（一）单项选择题.线性表在链式存储中各结点之间的地址（）。A.必须连续B.部分地址必须连续C.不能连续D.连续与否无所谓.有关线性表的正确说法是（ ）。A.每个元素都有一个直接前驱和一个直接后继B.线性表至少要求一个元素C.表中的元素必须按由小到大或由大到下排序D.除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继3.一个线性表第一个元素的存储地址是100,每个元素的长度为4,则第5个元素的地址是（）。A.110B.116C.100D.120.在一个长度为n的顺序存储线性表中，向第i个元素（1£i£n）之前插入一个新元素时，需要依次后移（）个元素。n-in-i+1n-i-1i.在一个长度为n的顺序存储线性表中，删除第i个元素（1£i£n）,需要前移（）个元素。A.n-in-i+1C.n-i-1D.i.链表不具有的特点是（）。A.可随机访问任一元素B.插入删除不需要移动元素C.不必要事先估计存储空间D.所需空间与线性表长度成正比.用链表表示线性表的优点是（ ）。A.便于随机存取B.花费的存储空间较顺序存储少C.便于插入和删除D.数据元素的物理顺序和逻辑顺序相同.带头结点的链表为空的判断条件是（ ）（设头指针为head）。head==NULLhead->next==NULLhead->next==headhead!=NULL.非空的单向循环链表的尾结点满足（ ）（设头指针为head,指针p指向尾结点）。A.p->next==NULLB.p==NULLp->next==headD.p==head10.在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（ ）。p=q->nextp->next=qC.p->next=q->nextD.q->next=NULL(二)填空题1.已知L是无表头结点的单链表，且P结点既不是首结点也不是尾结点，