一章线性表.pptVIP

双向链表的删除操作 删除p结点 p-prior-next = p-next; p-next-prior = p-prior; free(p); 静态链表 线性表的应用 一元多项式的运算 逻辑结构 存储结构 struct Polynode { double coef; int exp; PolyNode *next; } PolyNode,*PolyList; 1.多项式链表的建立 Polylist Polycreate() { Polynode *head,*rear,*s; head = (Polynode *) malloc(sizeof(Polynode)); rear =head; scanf(“%d,%d”,c,e); while(c!=0) { s = (Polynode *) malloc(sizeof(Polynode)); s-coef =c; s-exp =e; rear-next=s; rear=s; scanf(“%d,%d”,c,e); } rear-next =NULL; return head; } 两个多项式相加 void Polyadd(Polylist pa,PolyList pb) { Polynode *p,*q,*tail,*temp; int sum; p=pa-next; q=pb-next; tail=pa; while(p!=NULL q!=NULL) { if(p-expq-exp) { tail-next=p; tail =p; p=p-next;} else if(p-exp==q-exp) { sum =p-coef+q-coef; if(sum!=0) { p-coef =sum; tail-next=p; tail=p; p=p-next; temp=q; q=q-next; free(temp); } else { temp=p; p=p-next; free(temp); temp=q;q=q-next; free(temp); } } else { tail-next = q; tail=q;q=q-next;} } if(p!=NULL) tail-next =p; else tail-next =q; } 多项式相加 分配一个结点 ListNode *p;//悬挂状态 p=(ListNode*)malloc(sizeof(ListNode)); 例2：链表置逆 分析 链表置逆 void ReverseLink(LinkList L) { p=L-next; L-next=NULL; while(p) { q=p-next; p-next=L-next; L-next =p; p=q; } } 二进制加1 二进制用链表表示，每一个结点代表一位，第一个结点代表最高位，依次存放，最后一个结点。 二进制加1 void BinAdd(LinkList L) { Node *q,*r,*temp,*s; q=L-next; r=L; while(q!=NULL) { if(q-data==0) r=q; q=q-next ; } If( r!=L) r-data=1; Else { temp=r-next; s=(Node *) malloc(sizeof(Node)); s-data =1 ;s-next =temp;r-next =s; r=s; } r=r-next; while(r!=NULL) { r-data=0; r=r-next; } } 2.3.2单链表的基本操作 初始化链表 建立链表 往链表中插入一个结点 在链表删除一个结点 遍历链表 1. 初始化单链表 void InitList(LinkList *L) { *L=(LinkList ) malloc(sizeof(Node)); *L-next = NULL; } 2. 建立单链表 头插入法 尾插入法 void CreateFromHead(LinkList L) { Node *s; char c; int flag=1; while(fla