个数据元素的空间 Status Initlist- Sa(sqList &L)I ∥构造一个空的线性表L L elem =(Elem'lype *)Malloc(LIST- INIT SIZE sizeof(ElenType)); (! L elem)it(0 DERFLON);∥存储分配失败 L length=0; ∥空表长度为0 L.1 assize= LIST INIT SIZE;∥初始存储容量 retun on: ∥ InitList.8 算法2.3 在这种存储结构中容易实现线性表的某些操作如随机存取第i个数据元素等。只 是要特别注意的是,C语言中数组的下标从“0”开始因此若L是SLit类型的顺序表, 则表中第i个数据元素是L.elem[i-1]。下面重点讨论线性表的插入和删除两种操作在 顺序存储表示时的实现方法。 如21节中所述线性表的插入操作是指在线性表的第i-1个数据元素和第i个数 据元素之间插入一个新的数据元素就是要使长度为n的线性表 变成长度为n+1的线性表 数据元素a;-1和a1之间的逻辑关系发生了变化。在线性表的顺序存储结构中由于逻辑 上相邻的数据元素在物理位置上也是相邻的,因此除非i=n+1,否则必须移动元素才 能反映这个逻辑关系的变化。 序号数据序号数据 序号数据序号数据 元素 元素 元素 112 1|12 12 213 213 耐除24 插入25 630 628 6|30 6!42 742 7|42 777 817 877 977 图23线性表插入 图24线性表删除 前后的状况 前后的状况 (a)镫入前n=8; (a)剩除前n=8; (b)播入后n=9 (b)删除后n=7
例如图23表示一个线性表在进行播入操作的前后其数据元素在存储空间中的 位置变化。为了在线性表的第4和第5个元素之间插入一个值为25的数据元素则需将 第5个至第8个数据元素依次往后移动一个位置。 一般情况下在第i(≤还≤n)个元素之前插入一个元素时,需将第n至第(共n-i +1)个元素向后移动一个位置如算法24所示。 Status ListInsert-Sq(SqList &L, int i, Blem lype e)1 ∥在顺序线性表L中第i个位置之前插入新的元素e ∥i的合法值为1≤ i<ListLength.q(L)+1 谁f(i<1|i> L length+1) return error;∥i值不合法 if{ ( L length>kL, istsizel)1∥当前存储空间已满,增加分配 newbase =(Elea Type *)realloc(L elem, (L listsize+ LISTINCREMENr)*sizeof(elemType)); if(! newbase)eit(wRL);∥存储分配失败 L, elen newbase ∥新基址 L listsize+= LISTINCREM ENT;∥增加存储容量 q&(Lele"[i-1]); ∥g为插入位置 for(p= & (L elea[ t, length-lD;p >s g:--p)*(p+1)=+p; ∥播入位置及之后的元素右移 q=e ∥插入e ++L. length;∥表长增1 ∥ ListInsert 算法2.4 反之线性表的删除操作是使长度为n的线性表 变成长度为n-1的线性表 a;-1a;+1,",a 数据元素a1-1、a18和a+1之间的逻辑关系发生变化为了在存储结构上反映这个变化,同 样需要移动元素。如图24所示为了删除第4个数据元素,必须将从第5个至第8个元 素都依次往前移动一个位置。 般情况下删除第;(1≤迳≤n)个元素时需将从第计1至第n(共n-i)个元素依 次向前移动一个位置,如算法25所示。 Status ListDelete Sq(sqList &L int i, Blea type &e)f ∥在顺序线性表L中劓除第i个元素并用e返回其值 ∥i的合法值为1≤ Listlength.( if(i<1)‖(i> L length) retum ERRC;∥i值不合法 p=&(L elea[i-1]); ∥p为被除元素的位量 ∥被剧除元素的值赋给e q= L elen+ L length-1: ∥表尾元素的位置 for(+p;p<=g;+p)(p-1)=*p;∥被删除元素之后的元素左移
--L.length; ∥表长减1 returm OK ∥ ListDelete.8q 算法2.5 从算法24和25可见当在顺序存储结构的线性表中某个位置上播入或删除一个 数据元素时,其时间主要耗费在移动元素上(换句话说,移动元素的操作为预估算法时间 复杂度的基本操作,而移动元素的个数取决于插入或删除元素的位置。 假设p是在第i个元素之前插入一个元素的概率则在长度为n的线性表中播入一 个元素时所需移动元素次数的期望值(平均次数)为 =∑;(n-i+1) (23) 假设q是删除第个元素的概率则在长度为n的线性表中删除一个元素时所需移 动元素次数的期望值(平均次数)为 qi(n-i) (24) 不失一般性,我们可以假定在线性表的任何位置上插入或删除元素都是等概率的,即 qi n 则式(23)和(24)可分别简化为式2.5)和(26) E n+1 (n-i+1) (25) n (26) 由式(25)和(26)可见,在顺序存储结构的线性表中插入或删除一个数据元素平均 约移劲表中一半元素。若表长为n,则算法 Listlnsert_S和 ListDelete Sq的时间复杂度 为O(n) 现在我们来讨论21节中例21和例22的操作在顺序存储结构的线性表中的实现 方法和时间复杂度的分析。容易看出,顺序表的“求表长”和“取第i个数据元素的时间复 杂度均为O(1),又这两个例子中进行的“插入”操作均在表尾进行,则不需要移动元素。 因此,算法21的执行时间主要取决于查找函数 Locateelem的执行时间。在顺序表L中 查访是否存在和e相同的数据元素的最简便的方法是,令e和L中的数据元素逐个比较 之如算法26所示。从算法26中可见。基本操作是“进行两个元素之间的比较”,若L 中存在和c相同的元素a,则比较次数为(1≤还≤ L length,否则为L. length,即算法 LocateElem Sq的时间复杂度为O( L length)。由此对于顺序表La和Db而言,uion 的时间复杂度为O( La length X Lb length) int LocateElem. Sq(SqList L, ElenType e, tatu(“ compare)( BlemType,le〗ype)) ∥在顺序线性表L中查找第!个值与e满足 compare()的元素的位序
∥若找到则返回其在L中的位序,否则返回0 ∥i的初值为第1个元素的位序 P= L, elem; ∥p的初值为第1个元素的存储位置 hile(i<=L1enth是!(* compare)(*p十,e)++i; if(i<= L length)return i elBe return 0 ∥ LocateElem 算法2.6 对于“顺序表的合并”,则从算法22可直接写出形式上极其相似的算法27。显然, 算法27中的基本操作为“元素赋值”,算法的时间复杂度为O( La. length+Lb. length)。 void MergeList Sq( sqList La, Sqlist Lb, SqList &Ic)t ∥已知顺序线性表Ia和功的元素按值非递减排列 ∥归并a和Lb得到新的顺序线性表tc,的元素也按值非递减排列 p=La.ele;pb=劻.ele; listsize Lc length = La length+ Eb length pc= Lc elem =(Elem't'ype*)Mlloc(Lc listsize* sizeof Elen ype)); 连(!Lc.elen)ert(0wERD);∥存储分配失败 pa. last La elea [a, length-1 pb Lb elem+ Lb. length-1 hl(p<= palast&p<=pb.last)∥归并 (“pa<=餐p)慚p+≡新p+; ●】sp++=“p++; hl(p<=pa.last)*p+=“阅++;∥插入la的剩余元素 i·(p<= pb_last)*p++=“p+t;∥入劻b的利余元素 ∥ Mergelist 算法2.7 若对算法27中第一个循环语句的循环体作如下修改;以“开关语句代替“条件语 句”,即分出元素比较的第三种情况当*阳=*p时只将两者中之一播入Lc,则该算法 完成的操作和算法 union完全相同而时间复杂度却不同。算法27之所以有线性的时 间复杂度,其原因有二:1)出于L和Lb中元素依值递增(同一集合中元素不等),则对 Lb中每个元素不需要在La中从表头至表尾进行全程搜索;2)由于用新表Lc表示“并 集”,则插入操作实际上是借助“复制"操作来完成的Φ。为得到元素依值递增(或递减)的 有序表可利用103节讨论的快速排序,其时间复杂度为O(nlgn)(其中n为待排序 的元素个数)。由此可见,若以线性表表示集合并进行集合的各种运算,应先对表中元素 进行排序。 ①若将Lb中元素插入LA,为保持La中元素递增有序必须移动元素(除养插入的元素值大于La中所有的元 素)
23线性表的链式表示和实现 从上一节的讨论中可见,线性表的顺序存储结构的特点是逻辑关系上相邻的两个元 素在物理位置上也相邻,因此可以随机存取表中任一元素它的存储位置可用一个简单、 直观的公式来表示。然而,从另一方面来看这个特点也铸成了这种存储结构的弱点:在 作插入或删除操作时需移动大量元素。本节我们将讨论线性表的另一种表示方法— 链式存储结构,由于它不要求逻辑上相邻的元素在物理位置上也相邻因此它没有顺序存 储结构所具有的弱点,但同时也失去了顺序表可随机存取的优点。 231线性链表 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这 组存储单元可以是连续的,也可以是不连续的)。因此为了表示每个数据元素a与其直 接后继数据元素a;+1间的逻辑关系,对数据元素a,来说除了存储其本身的信息之外, 还需存储一个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据 元素a1的存储映象,称为结点(Node)。它包括两个域其中存储数据元素信息的域称为 数据城;存储直接后继存储位置的域称为指针域。指针域中存储的信息称做指针或链。 n个结点(a(1≤≤n)的存储映象)链结成一个链表即为线性表 (a1,a2,…,an) 的链式存储结构。又由于此链表的每个结点中只包含一个指针域故又称线性链表或单 链衰。 例如图25所示为线性表 (ZHAO, QIAN, SUN, LL, ZHOU, WU, ZHENG, WANG) 的线性链表存储结构,整个链表的存取必须从头指针开始进行头指针指示链表中第一个 结点(即第一个数据元素的存储映象)的存储位置。同时.由于最后一个数据元素没有直 接后继,则线性链表中最后一个结点的指针为“空(NUL)。 存慵地址数据域指针域 QIAN 头指针H 173p5173 WANG NULL WU ZHAO ZHENG ZHOU 图25线性链表示例 用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示的。换 句话说指针为数据元素之间的逻辑关系的映象,则逻辑上相邻的两个数据元素其存储的