第2章线性表1.pptVIP

顺序表的应用:集合的“并”运算 void Union ( SeqList A, SeqList B ) { int n = Length ( A ); int m = Length ( B ); for ( int i = 0; i m; i++ ) { int x = GetData ( B, i ); //在B中取一元素 int k = Locateelem (A, x,commpare()); //在A中查找它 if ( !k) //若未找到插入它 { Insert ( A, x, n ); n++; } } } 顺序表的应用:集合的“并”运算，合并后放到一个新的线性表中 void Union ( SeqList la, SeqList lb,sqlist lc ) { pa=la.elem; pb=lb.elem; Lc.listsize=la.length+lb.length; Pc=lc.elem=(elemtype*)malloc(lc.listsize*sizeof(elemtype)); If(!lc.elem) exit(overflow); pa_last=la.elem+la.length-1; Pb_last=lb.elem+lb.length-1; While(pa=pa_last pb=pb_last) { if(*pa=*pb) *pc++=*pa++; Else *pc++=*pb++; } 顺序表的应用:集合的“并”运算，合并后放到一个新的线性表中（续） While(pa=pa_last) *pc++=*pa++; While(pb=pb_last) *pc++=*pb++; } 优点： （1）无须为表示结点间的逻辑关系而增加额外的存储空间。 （2）可以方便地随机存储表中的任一结点。 缺点： （1）插入和删除平均须移动一半结点。 （2）存储分配只能预先进行（静态） 过大 浪费 过小 溢出 ?顺序表的优、缺点： 第 二 章 线性表（linear list) 线性结构的特点是： （1）存在唯一一个称为“第一个”的数据元素 （2）存在唯一一个被称为“最后一个”的数据元素 （3）除第一个之外，集合中的每个数据元素均只有一个前驱 （4）除最后一个之外，集合中每个数据元素均只有一个后继。 2—4章都为线性结构 ? 2.1 线性表的类型定义 线性表（linear_list）:一个线性表是n个数据元素的有限集合。 数据元素可以是一个字符，一条记录等。但同一个线性表中的数据是具有相同的特性。相邻数据元素之间存在着序偶关系。 即 是由n(n=0)个数据元素（结点）a1,a2,a3, ……an组成的有限序列。 其中： n为数据元素的个数，也称为表的长度。 当n=0 时，称为空表。 非空的线性表(n0) 记作： （ a1,a2,a3, ……an） 例1、26个英文字母组成的字母表 （A，B，C、…、Z） 例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。 （6，17，28，50，92，188） 例3、学生健康情况登记表如下： 姓 名 学 号 性 别 年龄 健康情况 王小林 790631 男 18 健康 陈 红 790632 女 20 一般 刘建平 790633 男 21 健康 张立立 790634 男 17 神经衰弱 …….. …….. ……. ……. ……. 线性表一个相当灵活的数据结构， 线性表的基本操作由 （1）存取 （2）插入 （3）删除 （4）查找 （5）合并 （6）分解 （7）排序 （8）求线性表的长度 最基本运算 抽象数据类型线性表的定义： ADT LIST{ 数据对象：D={ai|ai∈elemset,i=1,2,…n,n0} 数据关系:R1={ai-1,ai|ai-1,ai ∈D，i=2,…,n} 基本操作： 初始化，插入，删除等 } ADT list 例子：借助于基本操作来完成两个线性表的合并，每个线性表都是一个集合。 设两个线性表分别为LA,LB 算法实现： Void union(list la,list lb) {La_len=listlength(la); Lb_len=listlength(lb