数据结构 课件 链表应用与变形.ppt

链表应用与变形 数据结构电子教案 第二章 线性表 多项式 循环链表 双向链表 单链表的应用 多项式存储 多项式 (Polynomial) n阶多项式 Pn(x) 有 n+1 项。 系数 a0, a1, a2, …, an 指数 0, 1, 2, …, n。按升幂排列 多项式的链表存储表示 多项式顺序存储表示的缺点 插入和删除时项数可能有较大变化，因此要移动大量数据 不利于多个多项式的同时处理 采用多项式的链表表示可以克服这类困难： 多项式的项数可以动态地增长，不存在存储溢出问题。 插入、删除方便，不移动元素。 多项式的链表结构 在多项式的链表表示中，每个结点三个数据成员： 通过链接指针，可以将多项式各项按指数递增的顺序链接成一个单链表。 在此结构上，新项的加入和废项的删除执行简单的链表插入和删除操作即可解决。 两个多项式的相加算法 设两个多项式都带表头结点，检测指针pa和pb分别指示两个链表当前检测结点，并设结果多项式的表头指针为C，存放指针为pc，初始位置在C的表头结点。 当pa和pb没有检测完各自的链表时，比较当前检测结点的指数域： 指数不等：小者加入C链，相应检测指针pa或者pb进1； 指数相等：对应项系数相加。若相加结果不为零，则结果加入C链，pa与pb进1。 多项式链表的相加 AH = 1 - 3x6 + 7x12 BH = - x4 + 3x6 - 9x10 + 8x14 CH = 1 - x4 - 9x10 + 7x12 + 8x14 当pa或pb指针中有一个为NULL，则把另一个链表的剩余部分加入到C链。 void Add(Polynomal A, Polynomal B, Polynomal C) { //友元函数：两个带表头结点的按升幂排列的 //多项式链表的头指针分别是 A.first 和 B.first, //返回的是结果多项式链表 C. Term *pa, *pb, *pc, *p, temp; float sum; pc = C.poly.first; //结果链尾指针 pa = A.poly.first-link; //A链检测指针 pb = B.poly.first-link; //B链检测指针 while (pa != NULL pb != NULL) if (pa-exp == pb-exp) { //对应项指数相等 sum = pa-coef + pb-coef; if ( fabs(sum) 0.001) temp.set(sum, pa-exp); pc = C.poly.InsertAfter(temp); pa = pa-link; pb = pb-link; } else if (pa-exp pb-exp) { //pa指数小 temp.set(pa-coef, pa-exp); pc = C.poly.InsertAfter (temp); pa = pa-link; } else { //pb指数小 temp.set(pb-coef, pb-exp) pc = C.poly.InsertAfter (temp); pb = pb-link; } p = (pa != NULL)? pa : pb; //p指示剩余链 while (p != NULL) { temp.set(p-coef, p-exp); pc = C.poly.InsertAfter(temp); p = p-link; } }; 带表头结点的循环链表类的定义 template class T struct CircLinkNode { //链表结点类定义 T data; CircLinkNodeT * link; CircLinkNode ( CircLinkNodeT *next = NULL ) { link = next; } CircLinkNode ( T d, CircLinkNodeT *next = NULL ) { data = d; link = next; } bool Operator==(T x) { return data =