c语言单链表集合的排序升序去重,数据结构第二章2013 .ppt

数据结构第二章2013

* * * * * * 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; } } P43 指针下移 修改或删除 插入 完成对多项式的插入算法(链表实现)。该算法的功能是：如果多项式中没有与新项指数相等的项，则将此项插入到多项式链表的适当位置，如果多项式中已有与新项相等的项，则合并。 typedef struct Pnode{ float coef; // 系数 int expn; // 指数 struct Pnode * link; } Pnode, *Ploynomial void Insert(Polynomial &pL, float c,int e) //多项式链表pL(有头结点)中插入系数为c、指数e的 新项 { Pnode * pa=pL, *pb, *p; while(pa->link && pa->link->expnlink; if(pa->link->expn= =e) { if(pa->link->coef+c!=0) pa->link->coef= pa->link->coef+c; else { pb=pa->link; pa->link=pa->link->link; delete pb} } else { p=(*Polynomial) malloc(sizeof(Pnode)); p->expn=e; p->coef=c; p->link=pa->link ；pa->link=p; } }; 小结 线性表 顺序表 链表 O O O O O 线性 头 尾 1 2 3 4 5 a1 a2 ai an … … b b+l … b+(i-1)l … b+(n-1)l b+nl 存储地址 内存状态 a1 a2 … 0 an Head 顺序表和链表的综合比较 线性表的长度n能否预先确定？执行中，n的变化范围多大？ 对线性表进行的主要操作是哪些？ 链表总结 单链表(next) 带tail/cur指针和长度信息的加强版单链表 双向链表 循环链表 双向循环链表 有序链表(按某一成员变量大小排序) 线性表的重要操作 初始化(构造)、销毁 访问结点i 定位(判断是否包含) 遍历 插入节点 删除结点 算法总结 集合的交、并、差 两个有序线性表的合成(merge) 线性表的去重/纯化(purge) 有序 无序 算法总结 两集合求交intersection Lc=La∩Lb for(a in La) if (locate(Lb, a)>=0) insert(Lc, ++Lc.len, a); 算法总结 两集合求并union Lb=La ∪ Lb for(a in La) if (locate(Lb, a)<0) insert(Lb, ++Lb.len, a); 算法总结 两集合求差subtraction Lc=La-Lb for(a in La) if (locate(Lb, a)<0) insert(Lc, ++Lc.len, a); 习题 概念：头指针、头结点，首元结点 设有头结点的单链表L，编程对表中任一值只保留一个结点，删除其余值相同的结点 有一带头结点的单链表，编程将链表颠倒过来，要求不用另外的数组或结点完成。 头指针、头结点，首元结点 。 带头结点的单链表head为空的判断条件是(????? )