数据结构02g.pptVIP

第2章 线性表 2.1 线性表的类型定义 线性表的示例一 例1、26个英文字母组成的字母表 （A，B，C、…、Z） (a1，a2，…,an) 例2、某校从1978年到1983年各种型号的计 算机拥有量的变化情况。 （6，17，28，50，92，188） (a1，a2，…,an) 线性表的示例二 抽象数据类型线性表的定义 初始化操作 结构销毁操作 引用型操作: ListEmpty( L ) ListLength( L ) PriorElem( L, cur_e, pre_e ) NextElem( L, cur_e, next_e ) GetElem( L, i, e ) LocateElem( L, e, compare( ) ) ListTraverse(L, visit( )) 加工型操作 ClearList( L ) PutElem( L, i, e ) ListInsert( L, i, e ) ListDelete(L, i, e) 线性表应用示例 2-1 算法分析 算法描述 编码实现 线性表应用示例 2-2 基本操作分析 编码实现 编码实现续 编码实现续 编码实现续 2.2 线性表的顺序表示和实现 ---顺序映象 顺序映象 线性表的顺序存储结构示意 LocateElem_Sq ListDelete_Sq(L, i, e)的实现分析 一、线性链表（单链表） 1 单链表 静态单链表 的存储结构定义 #define MAXSIZE 1000 typedef struct{ ElemType data; int cur; }component, S [MAXSIZE]; 静态单链表 的存储结构示例 静态单链表 的存储结构操作实现 链表的基本操作 生成结点和释放结点操作 ListInsert_L Status CreatPolyn ( polynomail P, int m ) { // 输入m项的系数和指数，建立表示一元多项式的有序链表P } // CreatPolyn InitList (P); e.coef = 0.0; e.expn = -1; SetCurElem (h, e); // 设置头结点的数据元素 for ( i=1; i=m; ++i ) { // 依次输入 m 个非零项 } return OK; scanf (e.coef, e.expn); if (!LocateElem ( P, e, (*cmp)()) ) if ( !InsAfter ( P, e ) ) return ERROR; 注意: 1.输入次序不限; 2.指数相同的项只能输入一次。 Status AddPolyn ( polynomial Pc, polynomial Pa, polynomial Pb) { // 利用两个多项式的结点构成“和多项式” Pc = Pa＋Pb … … if (DelAfter(Pa, e1)) a=e1.expn else a=MAXE; if (DelAfter(Pb, e2)) b=e2.expn else b=MAXE; while (!(a=MAXE b=MAXE)) { … … } … … } // AddPolyn switch (*cmp(e1, e2)) { case -1: { // 多项式PA中当前结点的指数值小 … … break; } case 0: { // 两者的指数值相等 e1.coef= a.coef + b.coef ; if ( a.coef != 0.0 ) InsAfter(Pc, e1); … … break; } case 1: { //多项式PB中当前结点的指数值小 … … break; } } 1.熟练掌握顺序表和链表两类存储结构的描述方法，以及线性表的各种基本操作的实现。 2.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 本章小结 示例：逆位