《数据结构二单元作业及课件》由会员分享，可在线阅读，更多相关《数据结构二单元作业及课件（81页珍藏版）》请在金锄头文库上搜索。
1、数据结构二单元作业数据结构二单元作业及课件及课件教学重点与难点重点：重点：u顺序表与链表类的描述方法；顺序表与链表类的描述方法；u在两种存储结构上实现线性表的基在两种存储结构上实现线性表的基 本操作的算法。本操作的算法。难点：难点：u线性表在两种存储结构上的插入、删除线性表在两种存储结构上的插入、删除算法及动态链表的创建算法。算法及动态链表的创建算法。课前思考课前思考u按数据元素之间的逻辑关系不同，数按数据元素之间的逻辑关系不同，数 据结构有哪几类？据结构有哪几类？u你能举出几个你熟悉的你能举出几个你熟悉的“序列序列”的例子来的例子来 吗？吗？ 线性结构、树型结构、图型结构和线性结构、树型结构
2、、图型结构和集合四类。集合四类。 如：如：00，1 1，2 2，9“9“ A A，B B，C C，ZZ。?线性结构的线性结构的基本特征基本特征为为: :1集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”；2集合中必存在唯一的一个集合中必存在唯一的一个“最后元素最后元素”；3除最后元素在外，均有除最后元素在外，均有唯一的后继唯一的后继；4除第一元素之外，均有除第一元素之外，均有唯一的前驱唯一的前驱。 线性结构线性结构 是是 一个数据元素的一个数据元素的有序（次序）集有序（次序）集线性表线性表是一种最简单的线性结构线性结构2.1 线性表的类型定义线性表的类型定义2.3线性表类型的实
3、现线性表类型的实现链式映象链式映象2.4一元多项式的表示一元多项式的表示2.2线性表类型的实现线性表类型的实现顺序映象顺序映象l线性表定义：一个线性表是线性表定义：一个线性表是n个数据元素的有限序列个数据元素的有限序列例例英文字母表（英文字母表（A,B,C,.Z)是一个线性表是一个线性表例例数据元素数据元素抽象数据类型线性表线性表的定义如下：ADTList 数据对象数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 称 n 为线性表的表长表长;称 n=0 时的线性表为空表空表数据关系数据关系：R1 |ai-1 ,aiD, i=2,.,n 设线性表为 (a1，a2, .，
4、ai，.，an),称i为ai 在线性表中的位序位序 基本操作：基本操作： 结构初始化操作结构初始化操作结构销毁操作结构销毁操作引用型操作引用型操作 加工型操作加工型操作 ADT List2.1线性表的类型定义线性表的类型定义 InitList(&L)操作结果：操作结果：构造一个空的线性表L。初始化操作初始化操作结构销毁操作结构销毁操作DestroyList(&L)初始条件：操作结果：线性表 L 已存在。销毁线性表 L。ListEmpty(L)ListLength(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e) GetElem(L,i,&
5、e)LocateElem(L,e,compare()ListTraverse(L,visit()引用型操作引用型操作: : ListEmpty(L)（线性表判空）（求数据元素的前驱）pre_e 返回它的前驱pre_e 返回它的后继用 e 返回L中第 i 个元素的值返回L中第中第1个个与e满足满足关系compare( )的元素的位序。若不存在，则返回值为0。遍历判断是否为空加工型操作加工型操作 ClearList(&L)PutElem(&L,i,&e)ListInsert(&L,i,e)ListDelete(&L,i,&e) 将L重置为空表。L中第i个元素赋值同e的值。在L的第i个元素之前插入插
6、入新的元素e，L的长度增1。删除L的第i个元素，并用e返回其值，L的长度减1。算法实现：算法实现：voidunion(List&La,ListLb)/将所有在线性表将所有在线性表Lb中但不在中但不在La中的数据元素插入到中的数据元素插入到La中中La_len=ListLength(La);Lb_len=ListLength(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中不
7、存在和中不存在和e相同相同的数据元素，则插入之的数据元素，则插入之求集合求集合A与与B的并集的并集巳知线性表巳知线性表LALA和线性表和线性表LBLB中的数据元素按值非递减中的数据元素按值非递减有序排列，现要求将有序排列，现要求将LALA和和LBLB归并为一个新的线性表归并为一个新的线性表LCLC，且，且LCLC中的元素仍按值非递减有序排列。中的元素仍按值非递减有序排列。 求解：设两个指针:i指向LA中的元素a, j指向LB中的元素b。 LC中的元素c=a(ab)。 此问题的算法如下：例例2-2void MergeList(List La, List Lb, List &Lc)/ 本算法将非递
8、减的有序表 La 和 Lb 归并为 Lc / merge_listwhile (i = La_len) & (j = Lb_len) /La和和Lb均不空均不空InitList(Lc); / 构造空的线性表 Lci = j = 1; k = 0;La_len = ListLength(La); Lb_len = ListLength(Lb);while (i = La_len) / 当La不空时 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); /插入插入La表中剩余元素表中剩余元素 while (j = Lb_len) / 当Lb不空时 GetElem
9、(Lb, j+, bj); ListInsert(Lc, +k, bj); /插入插入Lb表中剩余元素表中剩余元素GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)ListInsert(Lc,+k,ai);+i;elseListInsert(Lc,+k,bj);+j;用一组地址连续地址连续的存储单元依次存放依次存放线性表中的数据元素 a1 a2 ai-1 ai an线性表的起始地址线性表的起始地址称作线性表的基地址称作线性表的基地址以“存储位置相邻存储位置相邻”表示有序对 即：LOC(ai) = LOC(ai-1) + C 一个数据元素所占存储量一个数据元素
10、所占存储量所有数据元素的存储位置均取决于所有数据元素的存储位置均取决于第一个数据元素的存第一个数据元素的存储位置储位置 LOC(ai) =LOC(a1) + (i-1)C 基地址基地址顺序映像的顺序映像的C语言描述语言描述typedefstruct SqList; / 俗称 顺序表顺序表#define LIST_INIT_SIZE 80 / 线性表存储空间的初始分配量#define LISTINCREMENT 10 / 线性表存储空间的分配增量ElemType *elem; / 存储空间基址int length; / 当前长度int listsize; / 当前分配的存储容量 / (以size
11、of(ElemType)为单位)elemlengthlistsizeSeqListElemType线性表的基本操作在顺序表中的实现线性表的基本操作在顺序表中的实现InitList(&L)/结构初始化结构初始化LocateElem(L,e,compare()/查找查找ListInsert(&L,i,e)/插入元素插入元素ListDelete(&L,i)/删除元素删除元素Status InitList_Sq( SqList& L ) / 构造一个空的线性表 / InitList_Sq算法时间复杂度时间复杂度：O(1)L.elem = (ElemType*) malloc(LIST_INIT_SIZ
12、E sizeof(ElemType);if (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = LIST_INIT_SIZEreturn OK;#defineLIST_INT_SIZE100#defineLISTINCREAMENT10typedefstructElemType*elem；/*线性表占用的数组空间。线性表占用的数组空间。*/intlength；/*线性表的长度线性表的长度*/intlistsize；/*当前分配的存储容量当前分配的存储容量(以以sizeof(ElemType)为单位为单位)/*SeqList；例如：顺序表 237
13、54138546217L.elemL.lengthL.listsizee=38pppppi 1 2 3 4 1 850p可见，基本操作是：将顺序表中的元素逐个和给定值 e 相比较。intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType) / 在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回 0 / LocateElem_Sq O(ListLength(L)算法的算法的时间复杂度时间复杂度为：为：i = 1; / i i 的初值为第的初值为第 1 1 元素的位序元素的位序p =
14、L.elem; / p p 的初值为第的初值为第 1 1 元素的存储位置元素的存储位置while (i = L.length &!(*compare)(*p+, e) +i;if (i = L.listsize) / 当前存储空间已满，增加分配newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType);if (!newbase) exit(OVERFLOW); / 存储分配失败 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存储容
15、量if (i L.length+1) return ERROR; / 插入位置不合法 q = &(L.elemi-1); / q 指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移元素右移 *q = e; / 插入e +L.length; / 表长增1returnOK; / ListInsert_Sq算法时间复杂度为算法时间复杂度为: :O(ListLength(L)考虑移动元素的平均情况考虑移动元素的平均情况: : 假设在第 i 个元素之前插入的概率为 ， 则在长度为n 的线性表中插入一个元素所
16、需插入一个元素所需移动元素次数的期望值移动元素次数的期望值为： 若假定假定在线性表中任何一个位置上进行插入插入的概率的概率都是相等相等的，则移动元素的期望值移动元素的期望值为：实现步骤：实现步骤：将第将第i+1至第至第n位的元素向前移动一个位置；位的元素向前移动一个位置；表长减表长减1。注意注意：事先需要判断，事先需要判断，删除位置删除位置i是否合法是否合法?3)3)删除删除 删除线性表的第删除线性表的第i i个位置上的元素个位置上的元素 使：长度为n的线性表变为长度为n-1的线性表。（a1,a2,ai-1,ai,ai+1,an）（a1,a2,ai-1,ai+1,an）顺序表删除的演示顺序表删
17、除的演示Status ListDelete_Sq(SqList &L, int i, ElemType &e) / ListDelete_Sqfor (+p; p = q; +p) *(p-1) = *p; / 元素左移元素左移-L.length; / 表长减表长减1 1return OK;算法时间复杂度算法时间复杂度为为: : O(ListLength(L)p = &(L.elemi-1); / p 为被删除元素的位置为被删除元素的位置e = *p; / 被删除元素的值赋给被删除元素的值赋给eq = L.elem+L.length-1; / 表尾元素的位置表尾元素的位置if (i L.len
18、gth) return ERROR; / 删除位置不合法删除位置不合法考虑移动元素的平均情况考虑移动元素的平均情况: : 假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值移动元素次数的期望值为：若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值移动元素的期望值为：小结小结线性表线性表顺序存储结构特点顺序存储结构特点：逻辑关系上相邻的：逻辑关系上相邻的两个元素在物理存储位置上也相邻；两个元素在物理存储位置上也相邻；优点：优点：可以随机存取表中任一元素可以随机存取表中任一元素O(1)；存储；存储空间使用紧凑空间使用紧凑缺点：缺
19、点：在插入，删除某一元素时，需要移动大在插入，删除某一元素时，需要移动大量元素量元素O(n); ;预先分配空间需按最大空预先分配空间需按最大空间分配，利用不充分间分配，利用不充分; ;表容量难以扩充表容量难以扩充为克服这一缺点，我们引入另一种存储形式：为克服这一缺点，我们引入另一种存储形式：链式存储结构链式存储结构见见2.3节节链表的表示链表的表示特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点数据域：元素本身信息指针域：指示直接后继的存储位置数据域 指针域结点头结点头结点 a1
20、a2 . an 头指针头指针空指针线性表为空表时，头结点的指针域为空 头指针头指针是指向链表中第一个结点（或为是指向链表中第一个结点（或为头结点头结点或或为首元为首元结点结点）的指针。）的指针。单链表可由一个头指针唯一确定单链表可由一个头指针唯一确定。头结点头结点是在链表的是在链表的首元结点首元结点之前之前附设附设的一个结点；数据的一个结点；数据域内只放空表标志和表长等信息域内只放空表标志和表长等信息;首元结点首元结点是指链表中存储线性表第一个数据元素是指链表中存储线性表第一个数据元素a1的结的结点。点。 一个线性表的逻辑结构为：一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZH
21、OU,WU,ZHENG,WANGZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存），其存储结构用单链表表示如下，储结构用单链表表示如下，请问其请问其头指针头指针的的值值是多少是多少？例例：答：答：头指针头指针是指向是指向链表中第一个结点链表中第一个结点的指针，因此关键的指针，因此关键是要寻找是要寻找第一个结第一个结点点的的地址地址。7ZHAOH31头指针的值是头指针的值是31上例链表的逻辑结构示意图有以下上例链表的逻辑结构示意图有以下两种形式两种形式：ZHAOQIANLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WA
22、NGH区别：区别：无头结点无头结点有头结点有头结点答：答：讨论1. 在链表中设置头结点有什么好处？讨论2. 如何表示空表空表？头结点头结点即在链表的首元结点之前附设的一个结点，该结即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对进行操作时，可以对空表、非空表空表、非空表的情况以及对的情况以及对首元结点首元结点进行进行统一处理，编程更方便。统一处理，编程更方便。答：答：无头结点时，无头结点时，当头指针的值为空当头指针的值为空时表示空表；时表示空表；有头结点时，有头结点时，当头结
23、点的指针域为空当头结点的指针域为空时表示空表。时表示空表。头指针头指针头指针头指针头结点头结点无头结点无头结点有头结点有头结点二、结点和单链表的二、结点和单链表的 C语言描述语言描述typedefstructLnodeElemTypedata;/数据域structLnode*next;/指针域Lnode,*LinkList;/ *LinkList为Lnode类型的指针介绍三个有用的库函数（都在介绍三个有用的库函数（都在中）：中）：sizeof(x)计算变量计算变量x的长度；的长度；malloc(m)开辟开辟m字节长度的地址空间，并返字节长度的地址空间，并返回这段空间的首地址；回这段空间的首地址
24、；free(p)释放指针释放指针p所指变量的存储空间，所指变量的存储空间，即彻底删除一个变量。即彻底删除一个变量。三、单链表操作的实现三、单链表操作的实现GetElem(L,i,e) / 取第取第i i个数据元素个数据元素ListInsert(&L,i,e) / 插入插入数据元素数据元素ListDelete(&L,i,e) / 删除删除数据元素数据元素ClearList(&L) / 重置线性表为空表重置线性表为空表CreateList(&L,n) / 生成含生成含n 个数据元素的链表个数据元素的链表L 线性表的操作 GetElem(L,i,&e)在单链表中的实现:211830754256ppp
25、j1 2 3Status GetElem_L(LinkList L, int i, ElemType &e) /L是带头结点的链表的头指针，以是带头结点的链表的头指针，以e返回第返回第i个元素个元素 / GetElem_L算法算法时间复杂度时间复杂度为为:O(ListLength(L)p = L-next; j = 1; / p p指向第一个结点，指向第一个结点，j j为计数器为计数器while(p&jnext;+j; / 顺指针向后查找，直到顺指针向后查找，直到 p p 指向第指向第 i i 个元素或个元素或 p p 为空为空if ( !p | ji ) return ERROR; / 第
26、i 个元素不存在e = p-data; / 取得第 i 个元素return OK;ai-1 线性表的操作 ListInsert(&L,i,e) 在单链表中的实现： 有序对有序对改变为改变为和和eaiai-1在链表中插入一个元素的示意图如下：在链表中插入一个元素的示意图如下：xsbapabp插入步骤（即核心语句）插入步骤（即核心语句）：Step 1Step 1：s-next=p-next;Step 2Step 2：p-next=s；p-nexts-next元素x结点应预先生成：S=(LinkList)malloc(m);S-data=x;S-next=p-next Status Status L
27、istInsert_L(LinkList L, intint i, ElemType e) / L L 为带头结点的单链表的头指针，在链表中为带头结点的单链表的头指针，在链表中第第i i个结点个结点之前插入新的元素之前插入新的元素 e e / LinstInsert_Lp = L; j = 0;while(p & j next; +j; / 寻找第寻找第i-1个结点个结点if (!p|j i-1) return ERROR; / i大于表长或者小于大于表长或者小于1s = (LinkList) malloc malloc ( sizeof sizeof (LNode); / 生成新结点s-da
28、ta = e; s-next = p-next; p-next = s; / 插入returnreturn OK;算法的算法的时间复杂度时间复杂度为:O(ListLength(L)单链表结点插入的演示单链表结点插入的演示链表ListDelete(&L,i,&e) 的操作实现:在链表中删除某元素的示意图如下：在链表中删除某元素的示意图如下：cabp删除步骤（即核心语句）：删除步骤（即核心语句）：q=p-next;/保存b的指针，靠它才能指向cp-next=q-next;/a、c两结点相连两结点相连free(q)；/删除删除b结点，彻底释放结点，彻底释放p-next思考：思考： 省略省略free(
29、q)语句语句行不行？行不行？(p-next)-nextStatus ListDelete_L(LinkList L, int i, ElemType &e) / 删除以 L 为头指针(带头结点)的单链表中第 i 个结点 / ListDelete_L算法的算法的时间复杂度时间复杂度为: O(ListLength(L)p = L; j = 0;while (p-next & j next; +j; /寻找第 i-1 个结点if (!(p-next) | j i-1)returnERROR; / 删除位置不合理q=p-next;p-next=q-next; / 删除并释放结点e = q-data;
30、free(q);return OK;单链表结点的删除演示单链表结点的删除演示操作 ClearList(&L)在链表中的实现:void ClearList(&L) / 将单链表重新置为一个空表 while (L-next) p=L-next;L-next=p-next; / ClearListfree(p);算法时间复杂度：O(ListLength(L)如何从顺序表构造一个单链表？如何从顺序表构造一个单链表？链表是一个动态的结构，它不需要链表是一个动态的结构，它不需要予分配空间，因此予分配空间，因此生成链表的过程生成链表的过程是一个结点是一个结点“逐个插入逐个插入” ” 的过程。的过程。例如：逆
31、位序输入例如：逆位序输入 n n 个数据元素的值，个数据元素的值， 建立带头结点的单链表。建立带头结点的单链表。操作步骤：操作步骤：一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素an，建立结点并插入；建立结点并插入；三、输入数据元素三、输入数据元素an-1，建立结点并插入；建立结点并插入；ananan-1四、依次类推，直至输入四、依次类推，直至输入a a1 1为止。为止。void CreateList_L(LinkList &L, int n) / 逆序输入 n 个数据元素，建立带头结点的单链表 / CreateList_L算法的算法的时间复杂度时间复杂度为:O(Lis
32、tlength(L)L = (LinkList)malloc (sizeof(LNode);L-next = NULL; / 先建立一个带头结点的单链表for (i = n; i 0; -i) p = (LinkList)malloc (sizeof(LNode); scanf(&p-data); / 输入元素值 p-next = L-next; L-next = p; / 插入头插法建单链表的演示头插法建单链表的演示尾插法建单链表的演示尾插法建单链表的演示应用举例：两个链表的归并算法要求：算法要求：已知：已知：线性表线性表A、B，分别由，分别由单链表单链表LA,LB存储，存储，其中数据元素按
33、值其中数据元素按值非递减有序非递减有序排列排列.要求：要求：将将A，B归并归并为一个新的线性表为一个新的线性表C,C的数据的数据元素仍按值非递减排列元素仍按值非递减排列。设线性表。设线性表C由由单链表单链表LC存储。存储。假设假设：A=（3，5，8，11），），B=（2，6，8，9，11）预测：预测：合并后合并后C=（2,3,5,6,8,8,9,11，11）用链表可表示为：用链表可表示为： 3 511 / 8 LaLa 2 611 / 8 LbLb 9 2 3 6 5 LcLc 8头结点头结点算法分析：算法分析：算法主要包括：算法主要包括：搜索、比较、插入搜索、比较、插入三个操作：三个操作：搜
34、索：搜索：需要需要两个指针两个指针搜索两个链表；搜索两个链表；比较：比较：比较结点数据域中数据的大小；比较结点数据域中数据的大小；插入：插入：将两个结点中数据将两个结点中数据小的结点插入新链表。小的结点插入新链表。La3 5 8 11 Lb2 6 8 119 PaPbPaPbPa、Pb用于搜索用于搜索La和和Lb，Pc指向新链表当前结点指向新链表当前结点Lc Pa3 PcPa5 Pc11Pc2 PbPcPa算法实现：算法实现： VoidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)/按值排序的单链表按值排序的单链表LA,LB，归并为，归并为LC
35、后也按值排序后也按值排序free(Lb);/释放释放Lb的头结点的头结点/MergeList_Lpc-next=pa?pa:pb;/插入剩余段插入剩余段while(pa&pb)/将将pa、pb结点按大小依次插入结点按大小依次插入C中中if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-nextpa=La-next;pb=Lb-next;Lc=pc=La；/初始化初始化式式A?B:C值为：值为：若若A为真为真,则则B；否则；否则C讨论讨论1：链表能不能首尾相连？怎样实现？链表能不能首尾相连？怎样实现？答：能。
36、只要将表中最后一个结点的指针域答：能。只要将表中最后一个结点的指针域指向头结点即可指向头结点即可 ( (P-next=headP-next=head; ;) ) 。这种形。这种形成环路的链表称为成环路的链表称为循环链表循环链表。其它链表形式循环链表是表中最后一个结点的指针指向头结点，使链表循环链表是表中最后一个结点的指针指向头结点，使链表构成环状构成环状特点：从表中任一结点出发均可找到表中其他结点，提高特点：从表中任一结点出发均可找到表中其他结点，提高查找效率查找效率操作与单链表基本一致操作与单链表基本一致,循环条件不同循环条件不同单链表单链表p或或p-link=NULL循环链表循环链表p或或
37、p-link=Hhh空表空表l循环链表循环链表(circularlinkedlist)循环链表中尾指针的应用考虑如何实现将带有尾指针的两个循环论链表合并为一个？考虑如何实现将带有尾指针的两个循环论链表合并为一个？anAa2a1ana2a1Brear3148155722linklist connect(linklist &reara，linklist rearb) p=reara-next;/p指向A的头结点 reara-next=(rearb-next)-next； free(rearb-next); rearb-next=p; return(reara); 例、在单循环链表上实现将两个线性表
38、例、在单循环链表上实现将两个线性表(a(a1 1，a a2 2，a a3 3，aan n) )和和(b(b1 1，b b2 2，b3b3，bbn n) )链接成一个线性表的运算。链接成一个线性表的运算。reara31481557 rearb31481557 讨论讨论2：单链表只能查找结点的直接后继，单链表只能查找结点的直接后继，能不能查找直接前驱？如何实现？能不能查找直接前驱？如何实现？答：能。只要把单链表再多开一个指针域即可答：能。只要把单链表再多开一个指针域即可( (例例如用如用*next*next和和*prior*prior; ;) ) 。双向链表在非线性结构（如树结构）中将大量使用。双
39、向链表在非线性结构（如树结构）中将大量使用。这种有两个指针的链表称为这种有两个指针的链表称为双向链表双向链表。其特点是。其特点是可以双向查找表中结点。参见教材可以双向查找表中结点。参见教材P3539P3539。2.双向链表双向链表typedefstruct DuLNode ElemType data; / 数据域 struct DuLNode *prior; / 指向前驱的指针域struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuLinkList;priorelementnext（double linked list）单链表具有单向性的缺点，在查找某节点的
40、直接前趋的时间复杂度将达到O(n)。双向循环链表双向循环链表空表空表非空表非空表 a1 a2 . an双向链表的操作特点：双向链表的操作特点：“查询查询” ” 和单链表相同。和单链表相同。“插入插入” ” 和和“删除删除”时需要同时修时需要同时修改两个方向上的指针。改两个方向上的指针。ai-1aie.s-next=p-next;.p-next=s;.s-next-prior=s;.s-prior=p;psai-1ai插入插入ai-1删除删除aiai+1p-next=p-next-next;p-next-prior=p;pai-1顺序表与链表的比较顺序表与链表的比较l存取方式存取方式u顺序表可以
41、顺序表可以随机存取，随机存取，也可以也可以顺序存取顺序存取u链表是链表是顺序存取顺序存取的的, ,查找的时间复杂度为查找的时间复杂度为O(n)l插入插入/ /删除时移动元素个数删除时移动元素个数u顺序表平均需要移动近顺序表平均需要移动近一半一半元素元素, , O(n)u链表链表不需要不需要移动元素，只需要修改指针移动元素，只需要修改指针O(1)u若插入若插入/ /删除仅发生在表的两端，宜采用删除仅发生在表的两端，宜采用带尾指针带尾指针的循环的循环链表链表l考虑如何选择合适的存储结构？考虑如何选择合适的存储结构？链表的运算效率分析链表的运算效率分析1.查找查找因线性链表只能顺序存取，即在查因线性
42、链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度找时要从头指针找起，查找的时间复杂度为为O(n)。时间效率分析2.插入和删除插入和删除因线性链表不需要移动元素，只要修因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为改指针，一般情况下时间复杂度为O(1)。但是，如果要在单链表中进行前插或删除操作，由于但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为要从头查找前驱结点，所耗时间复杂度为O(n)。空间效率分析链表中每个结点都要增加一个指针空间，相当于总链表中每个结点都要增加一个指针空间，相当于总共增加了共增加了n个整型变量，空间复杂度为个整
43、型变量，空间复杂度为O(n)。在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表示: P = (p0, p1, ，pn)一元多项式一元多项式但是对于形如但是对于形如 S(x)=1+3x100002x20000的多项式，上述表示方法是否合适？的多项式，上述表示方法是否合适？ 一般情况下的一元稀疏多项式一元稀疏多项式可写成 Pn(x)=p1xe1+p2xe2+pmxem其中其中：pi 是指数为ei的项的非零系数， 0e1e2 exp与q-expp-exp exp: p结点是结果多项式中的一项， p后移,q不动p-exp q-exp: q结点是结果多项式中的一项， 将q插在p之前,q
44、后移,p不动p-exp = q-exp: 系数相加0：从A表中删去p, 释放p,q，p,q后移0：修改p系数域, 释放q，p,q后移直到p或q为NULL 若q=NULL，结束 若p=NULL，将B中剩余部分连到A上即可l运算规则void addpolyn (polynomial &pa, polynomial &pb)qa=pa-next;qb=pb-next;pre=pa;while (qa&qb) a=qa-expn;b=qb-expn;switch(*cmp(a,b)case -1:pre=qa;qa=qa-next; break;case 0: sum=qa-coef+qb-coef;
45、 if (sum0.0)qa-coef=sum;pre=qa; elsepre-next=qa-next;free(qa); qa=pre-next;u=qb;qb=qb-next;free(u); break;case 1: u=qb-next;qb-next=qa;pre-next=qb; pre=qb;qb=u; break; /switch/whileif(qb) pre-next=qb; free(qb);线性表线性表逻辑结构逻辑结构基基本本概概念念抽抽象象数数据据类类型型定定义义线性表定义线性表定义逻辑特征逻辑特征ADT定义定义基本操作基本操作存储结构存储结构顺顺序序存存储储链链式
46、式存存储储其其它它存存储储顺序表特点顺序表特点类型定义类型定义基本操作基本操作的实现与时的实现与时间性能间性能单链表特点单链表特点类型定义类型定义基本操作基本操作 的实现与的实现与时间性能时间性能循环循环双向双向静态静态比较比较应用应用多多项项式式相相加加本章小结（本章小结（讨论题形式讨论题形式） 线线性性表表逻逻辑辑结结构构特特点点是是，只只有有一一个个首首结结点点和和尾尾结结点点；除除首首尾尾结结点点外外其其他他结结点点只只有有一一个个直直接接前前驱驱和和一一个个直直接接后后继继。简简言言之，线性结构反映结点间的逻辑关系是一对一（之，线性结构反映结点间的逻辑关系是一对一（1:11:1）的。
47、）的。问问1：线性表的逻辑结构特点是什么？其顺序存储线性表的逻辑结构特点是什么？其顺序存储结构和链式存储结构的特点是什么？结构和链式存储结构的特点是什么？答：答： 顺序存储时顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。理统一）；要求内存中可用存储单元的地址必须是连续的。链式存储时链式存储时，相邻数据元素可随意存放，但所占存储空间，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。系的指针。 顺序存
48、储的顺序存储的优点优点是存储密度大，存储空间是存储密度大，存储空间利用率高。利用率高。缺点缺点是插入或删除元素时不方便。是插入或删除元素时不方便。 链式存储的链式存储的优点优点是插入或删除元素时很方是插入或删除元素时很方便，使用灵活。便，使用灵活。缺点缺点是存储密度小，存储空间是存储密度小，存储空间利用率低。利用率低。答：答：问问2：顺序存储和链式存储各有哪些优缺点？顺序存储和链式存储各有哪些优缺点？事实上，链表插入、删除运算的快捷是以空间事实上，链表插入、删除运算的快捷是以空间代价来换取时间。代价来换取时间。问问3：在什么情况下用顺序表比链表好？：在什么情况下用顺序表比链表好？顺序表适宜于做
49、顺序表适宜于做查找查找这样的静态操作；链表宜这样的静态操作；链表宜于做于做插入、删除插入、删除这样的动态操作。这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。删除操作，则采用链表。答：答：2.2请编写一个计算头指针为请编写一个计算头指针为h的单链表长度的算法的单链表长度的算法a1a2L头指针头指针a4a32.19 2.19 删除有序表中所有其值大于删除有序表中所有其值大于 mink且小于且小于maxk的数据元素。的数据元素。2.22逆置线性链表逆置线性链表编写算法题编写算法题
