第二章 线性表.docx

《第二章 线性表.docx》由会员分享，可在线阅读，更多相关《第二章 线性表.docx（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章线性表Status DeleteK(SqList &a,int i,int k)删除线性表a中第i个元素起的k个元素 (return OK;/DeleteKStatus Insert_SqList(SqList &va,int x)把 x 插入递增有序表 va 中return OK;/Insert_SqListint ListComp(SqList A,SqList B)比较字符表A和B,并用返回值表示结果，值为正, 表示AB;后为负，表示AvB;值为零，表示A=Breturn 0;/ListCompLNode* Locate(LinkList LJnt x)链表上的元素查找，返回指针(

2、for(p=l-next;p&p-data!=x;p=p-next);return p;/Locateint Length(LinkList L)求链表的长度(for(k=0,p=L;p-next;p=p-next,k+);return k;/Lengthvoid ListConcat(LinkList ha,LinkList hb,LinkList &hc)把链表 hb 接在 ha 后面形成链表he) 此时P指向最后一个奇数结点if(p-next=L) p-next=L-pre-pre;else p-next=l-pre;p=p-next; /此时p指向最后一个偶数结点while(p-pre

3、-pre! =L) (p-next=p-pre-pre;p=p-next;)p-next=L;按题目要求调整了 next链的结构，此时pre链仍为原状 for(p=L;p-next!=L;p=p-next) p-next-pre=p;/OEReform分析:next链和pre链的调整只能分开进行.如同时进行调整的话，必须使用堆栈保 存偶数结点的指针，否则将会破坏链表结构，造成结点丢失.DuLNode * Locate_DuList(DuLinkedList &L,int x)带 freq 域的双向循环链表上的 查找if(p=L) return NULL; 没找至Up-freq+;q=p-pre

4、;while(q-freqfreq) q=q-pre; 查找插入位置if(q!=p-pre)(p-pre-next=p-next;p-next-pre=p-pre;q-next-pre=p;p-next=q-next;qnext=p;p-pre=q; 调整位置)return p;/Locate_DuListfloat GetValue_SqPoly(SqPoly P,int x0)求升幕顺序存储的稀疏多项式的值 |Poly Term *q;sum=0;ex=0;while(q-coef)(while(exexp) xp*=xO;sum+=q-coef*xp;q+；return sum;/Get

5、Value_SqPolyvoid Subtract_SqPoly(SqPoly Pl,SqPoly P2,SqPoly &P3)求稀疏多项式Pl 减P2 的差式P3(Poly Term *p,*q,*r;Create_SqPoly(P3); /建立空多项式 P3while(p-coef&q-coef)(if(p-expexp)(r-coef=p-coef;r-exp=p-exp;p+;r+;else if(p-expexp)(r-coef-q-coef;r-exp=q-exp;q+;r+;)elseif(p-coef-q-coef)!=0) /只有同次项相减不为零时才需要存入P3中(r-coe

6、f=p-coef-q-coef;r-exp=p-exp;r+;/ifp+;q+;/else/whilewhile(p-coef) 处理Pl或P2的剩余项(r-coef=p-coef;r-exp=p-exp;p+;r+;)while(q-coef)(r-coef=-q-coef;r-exp=q-exp;q+;r+;/Subtract_SqPoly void QiuDao_LinkedPoly(LinkedPoly &L)对有头结点循环链表结构存储的稀疏 多项式L求导(P=L-next;L-next=p-next;p=p-next; /跳过常数项)while(p!=L)(p=p-next;)/Qi

7、uDao_LinkedPolyvoid Divide_LinkedPoly(LinkedPoly &L,&A,&B)把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B(p=L-next;A=(PolyNode*)malloc(sizeof(PolyNode);B=(PolyNode*)malloc(sizeof(PolyNode);pa=A;pb=B;while(p!=L)pa-next=p;pa=p;)else(pb-next=p;pb=p;)p=p-next;/whilepa-next=A;pb-next=B;/Divide_I Jn kedPol yhc=ha;p=ha;wh

8、ile(p-next) p=p-next;p-next=hb;/ListConcat见书后答案.Status Insert(LinkList &L,int i,int b)在无头结点链表L的第i个元素之前插入元素 b (p=L;q=(LinkList*)malloc(sizeof(LNode);if(i=l)()else(while(il) p=p-next;q-next=p-next;p-next=q; /插入在第i个元素的位置 )/InsertStatus Delete(LinkList &L,int i)在无头结点链表L中删除第i个元素 (if(i=l) L=L-next; 删除第一个元

9、素 else(P=L;while(-il) p=p-next;p-next=p-next-next;i 个元素)/DeleteStatus Delete_Between(Linklist &L,int mink,int maxk)/删除元素递增排列的链表 L 中值大于mink且小于maxk的所有元素 (P=L;while(p-next-datanext; /p 是最后个不大于 mink 的元素if(p-next) /如果还有比mink更大的元素 (q=p-next;while(q-datanext; /q 是第个不小于 maxk 的元素 p-next=q;/Delete_BetweenStat

10、us Delete_Equal(Linklist &L)/删除元素递增排列的链表L中所有值相同的元 素 _p=L-next;q=p-next; p,q 指向相邻两元素while(p-next)(if(p-data! =q-data)(p=p-next;q=p-next; /当相邻两元素不相等时,p,q都向后推一步)else(while(q-data=p-data)(free(q);q=q-next;)p-next=q;p=q ;q=p-next; /当相邻元素相等时删除多余元素/else/while/Delete_Equalvoid reverse(SqList &A)顺序表的就地逆置(for

11、(i=l J=A.length;inext;q=p-next;s=q-next;p-next=NULL;while(s-next)(q-next=p;p=q;q=s;s=s-next; /把L的元素逐个插入新表表头)q-next=p;s-next=q;L-next=s;/LinkList_re verse分析:本算茯的思想是，逐个地把L的当前元素q插入新的链表头部,p为新表表头.void mergel(LinkList &A,LinkList &B,LinkList &C)把链表 A 和 B 合并为 C,A 和B的元素间隔排列，且使用原存储空间p=A-next;q=B-next;C=A; wh

12、ile(p&q)s=p-next;p-next=q; 将 B 的元素插入 if(s)( 一 t=q-next;q-next=s; 如A非空，将A的元素插入) p=s;q=t;/while/merge 1void reverse_merge(LinkList &A,LinkList &B,LinkList &C)把元素递增排列的链 表A和B合并为C,且C中元素递减排列，使用原空间 _ pa=A-next;pb=B-next;pre=NULL; /pa 和 pb 分别指向 A,B 的当前元素 while(pa|pb)(if(pa-datadata| |! pb) _pc=pa;q=pa-next;

13、pa-next=pre;pa=q; / A 的元素插入新表 ) else 一pc=pb;q=pb-next;pb-next=pre;pb=q; 将 B 的元素插入新表 pre=pc; )C=A;A-next=pc; 构造新表头 /reverse_merge分析:本M去的思想是，按从小到大的顺序依次把A和B的元素插入新表的头部 pc处，最后处理A或B的剩余元素.void SqList_Intersect(SqList A,SqList B,SqList &C)求元素递增排列的线性表 A 和B的元翥的交集并存入C中i=l;j=l;k=O;i+;j+;就添加到C中/while/SqList_Inte

14、rsectvoid LinkList_Intersect(LinkList A,LinkList B,LinkList &C)在链表结构上重做上 题(p=A-next;q=B-next;pc=(LNode*)malloc(sizeof(LNode);while(p&q)(if(p-datadata) p=p-next;else if(p-dataq-data) q=q-next;else(s=(LNode*)malloc(sizeof(LNode);s-data=p-data;pc-next=s;pc=s;p=p-next;q=q-next;)/whileC=pc; /LinkList_Int

15、ersectvoid SqList_Intersect_True(SqList &A,SqList B)求元素递增排列的线性表 A 和 B 的元素的交集并存直A中(i=l;j=l;k=O;i+;j+; /且C中没有，就添加到C中 )/while /SqList_Intersect_Truevoid LinkList_Intersect_True(LinkList &A,LinkList B)在链表结构上重做上题p=A-next;q=B-next;pc=A;while(p&q)(if(p-datadata) p=p-next;else if(p-dataq-data) q=q-next;else

16、 if(p-data! =pc-data)(pc=pc-next;pc-data=p-data;p=p-next;q=q-next;)/while/LinkLi st_Intersect_T ruevoid SqList_Intersect_Delete(SqList &A,SqList B,SqList C) (i=0;j=0;k=0;m=0; i指示A中元素原来的位置,m为移动后的位置else/while/ SqList_Intersect_Delete分析:先从B和C事找出共有元素，记为same,再在A中从当前位置开始，凡小于 same 的元素均保留(存到新的位置)，等于same的就跳过

17、,到大于same时就再找下一个same.void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)在链表结构上 重做上题p=B-next;q=C-next;r=A-next;while(p&q&r)if(p-datadata) p=p-next;else if(p-dataq-data) q=q-next;else(u=p-data; /确定待删除元素uwhile(r-next-datanext; 确定最后一个小于u的元素指针r if(r-next-data=u)(s=r-next;while(s-data=u)( 一t=

18、s;s=s-next;free(t); /确定第一个大于u的元素指针s/whiler-next=s; /删除r和s之间的元素/ifwhile(p-data=u) p=p-next;while(q-data=u) q=q-next;/else/while /LinkList_Intersect_DeleteStatus Delete_Pre(CiLNode *s)删除单循环链表中结点s的直接前驱(P=S；while(p-next-next! =s) p=p-next; /找到 s 的前驱的前驱 pp-next=s;return OK;/Delete_PreStatus DuLNode_Pre(D

19、uLinkList &L)完成双向循环链表结点的pre域(for(p=L;!p-next-pre;p=p-next) p-next-pre=p;return OK;/DuLNode_Pres=L-next;A=(CiList*)malloc(sizeof(CiLNode);p=A;B=(CiList*)malloc(sizeof(CiLNode);q=B;C=(CiList*)malloc(sizeof(CiLNode);r=C; /建立头结点 while(s)if(isalphabet(s-data)p-next=s;p=s;)else if(isdigit(s-data)(q-next=s

20、;q=s; else(r-next=s;r=s;)/whilep-next=A;q-next=B;r-next=C; /完成循环链表/LinkList_Dividevoid Print_XorLinkedList(XorLinkedList L)从左向右输出异或链表的元素值(while(p)(printf(n %dn ,p-data);q=XorP(p-LRPtr,pre);pre=p;p=q; 任何一个结点的LRPtr域值与其左结点指针进行异或运算即得到其右结点指针)/Print_XorLinkedListStatus Insert_XorLinkedList(XorLinkedList &

21、L,int x,int i)在异或链表 L 的第 i 个元 素前插入元素x(r=(XorNode*)malloc(sizeof(XorNode);r-data=x;if(i=l) /当插入点在最左边的情况(r-LRPtr=p;return OK;)j=l ;q=p-LRPtr; /当插入点在中间的情况while(+j LRPtr,pre); pre=p;p=q;/while 在p,q两结点之间插入if(!q) return INFEASIBLE; /i 不可以超过表长p-LRPtr=XorP(XorP(p-LRPtr,q),r);q-LRPtr=XorP(XorP(q-LRPtr,p),r);

22、r-LRPtr=XorP(p,q); /修改指针return OK;/Insert_XorLinkedListStatus Delete_XorLinkedList(XorlinkedList &L,int i)删除异或链表 L 的第 i 个元素 (if(i=l) /册Ij除最左结点的情况(q=p-LRPtr;q-LRPtr=XorP(q-LRPtr,p);return OK;)j=l;q=p-LRPtr;while(+jLRPtr,pre);pre=p;p=q;/while /找到待删结点qif(!q) return INFEASIBLE; /i 不可以超过表长(p-LRPtr=XorP(p-LRPtr,q);return OK;)r=XorP(q-LRPtr,p); /q为中间结点的情况，此时p,r分别为其左右结点p-LRPtr=XorP(XorP(p-LRPtr,q),r);r-LRPtr=XorP(XorP(r-LRPtr,q),p); /修改指针free(q);return OK; /Delete_XorLinkedListwhile(p-next!=L&p-next-next!=L) (p-next=p-next-next;p=p-next;