数据结构 (2)插入:在线性表两个确定的元素之间插入一个新的数据元素 (3)删除:删除表中某个数据元素。 (4)求表长:求线性表中数据元素的个数。 (5)査找;査找表中满足某种条件的数据元素 (6)合并:把两个线性表合并成一个线性表 (7)分拆:把一个线性表分拆成多个线性表。 (8)排序:按一个或多个数据项值的递增或递减次序重新排列表中数据元素。 上述这些运算中的基本运算是:查找、插入和删除。在实际问题中,根据需要选择相应 的运算。 22顺序表 221顺序表的结构 顺序表是线性表的顺序存储结构,即用一组连续的存储单元依次存放线性表的数据元素。 它的特点是:表中逻辑上相邻的数据元素存储在相邻的存存储地址内存内容元素位序 储位置,换句话说,以数据元素在计算机内“物理位置相 邻”来表示表中数据元素间的逻辑关系。若一个数据元素bm 占用m个存储单元,第…个元素存储位置为b,则这种存 储方式如图22所示。 b+(i-1)m 如图22所示,线性表中相邻的元素a1和a1的存储 位置LOC(a)和LOC(a1)也是相邻的,它们满足下列关b(n-1)m 系式: 图22线性表的顺序存储结构 LoC(aii-LOC(ai+m 如果用LOC(a)表示第一今元素的存储位置(通常称为线性表的起始位置或基地址),线 性表第i个数据元素的存储位置为: LoC(aiLoC(an+(i-1)m 也就是说,线性表中母个数据元素的存储位置都和线性表的起始位置差一个和数据元素在 线性表中的位序成正比的常数。因此,只要确定了存储线性表的起始位置,则线性表中任一 元素都可以随机存取,所以说顺序表是一种随机存储结构 由于高级语言中的一维数组也是用一组连续的存储单元进行存放的,所以顺序表可用C 语言的一维数组实现,数组的类型随线性表中数据元素的性质而定,数组的长度应大于等于 线性表的长度。因此顺序表可作如下描述: # define maxlen 1000∥定义顺序表可能的最大数据元素数目为1000 ypedef int elemtype;∥ elemtype表示元素类型,为简单起见定义为int typedef struct elemtype elem(maxlen len: iSqList; 16
第2章线性表 在上面描述中,顺序表 Sqlist是一个结构体类型,它由数组下标内容元素位序 两个成员组成:elem表示存储顺序表元素的数组,其长度 maxlen代表顺序表中元素数目的最大值;len表示顺序表的实 际长度。值得注意的是,C语言的数组下标从0开始,设线性 表(an,a,…,an),n≤max,则线性表的存储如图23。其n1[a 2:n 中数据元素占用了elem[]至 elem(n-1],elem[m至 elem[ maxlen-1]是备用空间。数据元素的存储位置可用数组的 maxlen-I 下标值来表示。 图2.3线性表在数组中存储 222顺序表的运算 在顺序表上的基本运算主要为插入、删除和査找。 1.插入 线性表的插入运算是指在第1≤i≤n)个数据元素之前插入一个新的数据元素,也就是 使长度为n的线性表(a1,a2,…a-1,an…an)变成长度为n+1的线性表(a,a2,…at,x, a,…,an)。在顺序表中插入一个新元素后,顺序表的数据元素间的逻辑关系发生了变化,使 得物理存储顺序也做出相应的改变。于是必须将第n个元素到第i个元素依次向后移动一个 位置,于是在a1和a之间空出一个位置,最后把要插入的新元素存入该位置上,线性表长 度增加1。如果新元素插入到表尾(即in+1),则不需移动元素。图2.4表示了在长度为9 的顺序表的第5个数据元素之前插入一个新元素的过程。其算法描述见算法21。 int SqInsert( SqList'L, elemtype x, int i) ∥在顺序表L的第i个数据元素之前插入一个数据元素x J, n, n('L).len if(i<l‖in) printf(“Eror!”) return(0);} if( n>=maxlen i printf("Overflow! ") return(0); J fCL).elem[i-l]=x; ( L).len++: return(1);3 for(j=n; j>=i; j-) (L).elemi(L).elem[j-1; (L).elem[i-1F=x: (·U)len+; return(1); 算法21 2.删除 线性表的删除是指将表的第i个元素删除,使线性表的长度由n变成n-1,并且其逻辑
数据结构 和顺序存储也发生相应的变化。即由 (a1,a,…a-t,an,a+1,…an) 变成为 (a1,a2,…a-1,a+1,…an) 可见,需将从a1到an依次向前移动一个位置。当in时,可将第i个元素直接删除。 在长度为9的顺序表中删除第5个元素的过程如图25所示。其算法描述见算法22 010 010 010 010 1|16 116 116 2「25 225 225 225 14 30剩除14→→414→435 535 14 561 661 635 6|6l 627 761 838 827 938 (a)插入前 (b)插入后 (a)删除前 (b)删除后 图24顺序表的插入 图25顺序表的删除 int SqDelete( Sqlist"L, int i, elemtype p) {在顺序表L中删除第ⅰ个数据元素,并用*p返回其值 d printf("Error!"): retum(0) P=(L).elem[i-1]; or(j=i-I; j<n-1; j++) (L).elem(L).elem[+1]: (L).len-, tum(1); 算法22 3.查找 线性表的查找是指找出指定数据元素在表中的位序。值得注意的是某元素在顺序表中的 位序为存储该数据元素的数组下标加1。其算法描述见算法2.3。 int SqSearch( SqList L, elemtype x {在顺序表L中查找数据元素x在表中的第一次出现的位置 Int J for(j=0; j <(L).len; j++) 18
第2章线性表 if((L). elem]==x) return(+1); retum(0); 算法23 4.顺序表基本运算的时间分析 在顺序表中某个位置上插入或删除一个数据元素时,其时间主要耗费在移动数据元素上。 在插入算法中,数据是从最后一个元素开始后移,直到第i个元素后移为止。通过以上 算法可看到,算法时间主要花在for循环语句上,该循环语句执行的次数为n-计+1。由此可见, 它不仅依赖于线性表长度n,还与元素插入的位置i有关。当产1时,全部元素均参加移动, 需要移动n次,循环语句执行n次:当n+1时,不需移动元素。可见算法在最坏情况下时 间复杂度为O(n),最好情况下时间复杂度为O(1)。由于元素移动的次数直接影响了算法执行 时间,下面讨论一下平均移动次数。 假设P为在第i个元素之前插入一个元素的概率,且设在线性表的任何位置上插入元素 的机会相等,则平均移动次数为 E=∑p(n-计+、1 罗i n(n+ n +1 n+122 其中,当1≤长≤n+1时,P 可见,在顺序存储的线性表宁插入一个数据元素,约平均移动线性表中一半的元素。显 然,该插入算法的平均时间复杂度为Om) 在删除算法中,第计1,计2,…,n个元素依次向前移,移动次数为n-i。当闩1时,需 要移动n-1次;当=n时,不需移动元素。可见算法在最坏情况下时间复杂度为O(n),最好 情况下时间复杂度为O()。假设删除线性表中的任一元素的概率相等,即概率为1/m,则删 除运算所需移动元素的平均移动次数为 ∑ E∑-(m-0=∑(n-0 n i=1 n n i=I 可见,在顺序存储的线性表中删除一个数据元素,约移动一半元素。显然,该删除算法 的平均时间复杂度为On 通过以上讨论可知,在线性表中插入和删除一个数据元素时约移动一半的数据元素,效 率比较低。 23链表 上一节介绍的顺序表结构简单,便于随机访问表中任一数据元素,但插入和删除运算必
数据结构 须移动大量元素,尤其是当线性表的数据元素含有复杂信息时,移动工作量很大,效率较低。 另外,顺序表的空间是预先分配的,表的容量难以扩充,必须按线性表的最大可能长度分配。 若是线性表长度变化较大时,则存储空间不能得到充分利用,且有时难以准确估计线性表的 最大长度,估计过小导致溢出,估计过大又会造成存储空间浪费。本节将讨论另一个存储结 构——链式存储结构,即链表 23.1单链表和循环单链表 1.存储结构 顺序表是利用一片地址连续的存储单元依次存放线性表的数据元素,因此在逻辑上相邻 的数据元素物理上也相邻。线性表的链式存储结构则是用一组任意的存储单元(可以是连 续的,也可以是不连续的)存放线性表的数据元素。为了表示数据元素间的逻辑关系,除 了存储数据元素自身信息外,还必须存放指示其后继元素的信息(直接后继的存储位置)。 这两部分信息组成一个结点,表示线性表中一个数据元素。可见,一个结点由两个域组成: 其中存储数据元素信息的域称为数据域,存储直接后继存储位置的域称为指针域,如下图 所示。 数据域指针域 由上述结构的n个结点链接成一个链表,由于该链表的每一个结点只包含一个指针域, 故又称单链表或线性链表。 例如,线性表(ONE,TWO, THREE,FOUR)的单链表存储如图26所示。 “头指针”h存储线性表第一个数据元素的地 址,即指向第一个数据元素,整个链表的存取必须 存储地址数据域|指针域 头指针h 从头指针开始。由于最后一个元素没有直接后继, 100 THREE|2100 链表中最后一个结点的指针域为“空”(即NUL, 1100Two1000 有时用“∧”表示)。可见,用单链表表示线性表 2100 FOUR NULL 时,数据元素之间的逻辑关系是由结点中的指针表 00 ONE1100 示的。逻辑上相邻的两个数据元素存储的物理位置 图26单链表示意图 不要求相邻。我们可以把单链表画成用箭头相链接 的结点序列,结点之间的箭头表示指针域中的指针,于是图26所示的单链表可画成如图27 所示的形式。 ONE TwO THREE FOUR 图27单链表的逻辑状态 单链表如为空表则头指针为空。有时为了操作方便,在单链表的第一个结点之前添加 个表头结点。表头结点的结构与表中结点结构相同,但表头结点的数据域不存放线性表 元素,或者闲置不用,或者存放其他特殊信息。表头结点的指针域存放第一个数据元素结 点地址,即指向第一个数据元素结点。当表空时,表头结点的指针域为空。头指针指向表 头结点,此时称其为带头结点的单链表。上述线性表带头结点的单链表如图28(a)所示