数据结构(C语言)链表.ppt

单链表特点 是一种动态存储结构 指针占用了额外的存储空间 不能随机存取，而是顺序存取 适合做动态操作 带头结点的单链表很多时候可以使算法简化 Combine two Linked chain Two linked chains la lb Their elements are in no-descending order Combine these two chains, Add(la, lb), using the structure of la and lb The result chain’s elements have to be in no-descending order Node add(Node la, Node lb){ Node pa, pb, pc, lc; pa = la.next ; pb = lb.next; pc = la; lc = la; while( pa != null pb!= null){ if(pa.element = pb.element){ pc.next = pa; pc = pa; pa = pa.next; }else{ pc.next = pb; pc = pb; pb = pb.next; } }/*end for while*/ if(pa !=null) pc.next =pa; else pc.next = pb; free (lb); return lc; } Polynomial’ Addition in chain Structure Data Structure of Polynomial struct Pnode{ float col; int exp; struct Pnode *next; } coef exp next -1 A 7 0 3 1 9 8 5 17 ^ -1 B 8 1 22 7 -9 8 ^ -1 C 7 0 11 1 22 7 5 17 ^ 一元多项式相加 Polynomial’ Addition in chain Structure 设p,q分别指向A,B中某一结点，p,q初值是第一结点 比较 p.exp与q.exp p.exp q.exp: p结点是和多项式中的一 项，p后移,q不动 p.exp q.exp: q结点是和多项式中的一项， 将q插在p之前,q后移,p不动 p.exp = q.exp: 系数相加 0：从A表中删去p, 释放p,q，p,q后移 ?0：修改p系数域, 释放q，p,q后移 直到p或q为NULL 若q==NULL，结束 若p==NULL，将B中剩余部分连到A上即可 Polynomial’ Addition in chain Structure Algorithm Pnode * polyAdd(Pnode * a, Pnode * b){ 1)set 2 temp pointer at the beginning of two chains; 2)if any of the 2 pointer is null then turn to step 7 ; 3)compare the current 2 nodes with its data; 4)if these 2 nodes can add, just add these 2 nodes; 5)else copy the big one to the result chain; 6)continue to search next node turn to step 2; 7)copy the left node to the result chain; 8)return the result chain; } The final program q -1 pa 7 0 3 1 9 8 5 17 ^ -1 pb 8 1 22 7 -9 8 ^ p pre q -1 pa 7 0 3 1 9 8 5 17 ^ -1 pb 8 1