第二讲关于数据结构基本介绍与基础内容.ppt

 第二章 线性表;2.1 线性表的逻辑结构 线性表(Linear List) ：由n(n≧0)个数据元素(结点)a1，a2， …an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作： (a1，a2，…an) 这里的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。;例3、学生健康情况登记表如下：;例4、一副扑克的点数 （2，3，4，…，J，Q，K，A）;ADT List{ 数据对象:D={ai|ai属于ElemSet, i=1,2,3,…n, n=0} 数据关系: R1={ai-1,ai|ai-1,ai属于D, i=1,2,…n, } 基本操作: InitList(L); 操作结果:构造一个空的线性表L; DestroyList(L); 初始条件:线性表L已经存在; 操作结果:销毁线性表L; ClearList(L); 初始条件:线性表L已经存在; 操作结果:将线性表L置为空;;ListEmpty(L); ListLength(L); GetElem(L,i,e); 初试条件:线性表L已经存在; 操作结果:用e返回L中第i个数据元素的值; LocateElem(L,e,compare()); PriorElem(L,cur_e,pre_e); NextrElem(L,cur_e,next_e); ListInsert(L,i,,e); ListDelete(L,i,e); ListTraverse(L,visit()); } ADT List; 算法2.1 例2-1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。; 算法2.2 例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。;void MergeList(List La，List lb，List Lc) ; if(ai=bj){ListInsert(Lc，++k，ai);++i;}; 用一组地址连续的存储单元依次存储线性表 中的数据元素，数据元素之间的逻辑关系通过数 据元素的存储位置直接反映。 ; 若假设每个数据元素占用k个存储单元，并且 已知第一个元素的存储位置LOC(a1)，则有 ;1 2 3 4 … n-1 n n+1 n+2 … M; 由于C语言中的数组类型具有随机存取的特性，因此可以用数组来描述数据结构中的顺序存储结构。又由于线性表的长度可变，且所需要最大存储空间随问题不同而不同，在语言中可用动态分配的一维数组.;顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问等等.; 该运算是在线性表的第i?1个数据元素与第i个数据元素之间插入一个由符号item表示的数据元素，使长度为n的线性表 ( a1, a2, … , ai-1, ai , ai+1, … ,an-1 , an ) ; ( a1, a2, … , ai-1, ai , ai+1, … ,an-1 , an ) ;算法(见课本P24) Void InsertList(SqList L，ElemType e ，int i) { ;if(L.length=ListSize) printf(“overflow”); exit(overflow);; 现在分析算法的复杂度。 从上面可以看出，当在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，该算法的时间主要耗费在移动元素上，而移动元素的个数与插入或删除的位置有关。; 若设pi为插入一个元素于线性表第i个位置的概率 (概率相等)，则在长度为n的线性表中插入一个元 素需要移动其他的元素的平均次数为： Eis= ?Pi(n-i+1) = ?(n-i+1)/(n+1) = n/2 称该算法的时间复杂度是O(n)。; 该运算是把线性表的第i个数据元素从线性表中去掉，使得长度为n 的线性表 ( a1, a2, … , ai-1, ai , ai+1, … ,an-1 , an ) ; ( a1, a