数结_2静态链和多项式.ppt

§2.3 线性表的链式表示和实现 2.3.1 单链表 2.3.2 循环链表 2.3.3 双向链表 2.3.4 静态链表 2.3.4 静态链表 用数组模拟链表： #define MAXSIZE 1000 typedef struct{ ElemType data; int cur; //游标 cursor } SLinkList[ MAXSIZE ]; //存储池类型 SLinkList space ; //定义一个存储池space space数组中有两条链：线性表链和备用链 教材P33，算法2.15 int malloc_sl (SLinkList space) { //向备用链申请结点----删除备用链中的第一个结点 //若备用链非空返回第一个结点的下标，否则返回 0 i =space[0].cur; //获得备用链第一个结点的下标 if ( i ) space[0].cur=space[ i ].cur; // 修改头结点的后继指针 return i; // 返回结点下标 } 例：删除静态链表L中第i个元素 status ListDelete_sl ( SLinkList space, int L, int i ) { // L是头结点的游标 int p=L, j=1, q; while (space[p].cur ji-1) { p= space[p].cur; j++; } //找ai-1 if ( p==0 || ji-1) return ERROR； // i 非法 q = space[ p ].cur; space[ p ].cur = space[ q ].cur; //修改游标 free_sl (space, q); return OK; } // end ListDelete_sl 在静态链表L的第i个元素前插入新结点e status ListInsert_sl (SLinkList space, int L, int i, ElemType e) { // L是头结点的游标 int p=L, j=1, s; while (space[p].cur ji-1) {p=space[p].cur; j++;} //找ai-1 if (p==0 || ji-1) return ERROR； // i 非法 s＝malloc_sl (space) if ( !s ) return OVERFLOW; space[ s ].data=e; space[ s ].cur=space[ p ].cur; space[ p ].cur=s; //修改游标 return OK; } // end ListInsert_sl 教材P33－34，算法2.17 A=(A-B)U(B-A) 1、从键盘输入A表的m个元素，用尾插法建单链表，尾指针是r； 第二章 线性表 §2.1 线性表的定义 §2.2 线性表的顺序表示和实现----顺序表 §2.3 线性表的链式表示和实现 §2.4 线性表的应用举例----多项式的表示与实现 §2.4 一元多项式的表示与运算 一元多项式： Pn(x) = p0 + p1x + p2x2 + ... + pn-1xn-1 + pnxn 可用系数组成的线性表表示： P ( p0, p1, p2, ... , pn-1, pn ) 这里指数隐含在元素在线性表中的位序里。 稠密多项式：0系数很少 稀疏多项式：0系数非常多 多项式的基本运算： 创建多项式 CreatePolyn(P); 销毁多项式 DestroyPolyn(P) 打印多项式 PrintPolyn(P) 求项数 LengthPolyn(P) 多项式求和 AddPolyn(Pa, Pb) 多项式求差 SubstractPo