第二章 线性表.docx

第二章线性表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,并用返回值表示结果，值为正, 表示A>B;后为负，表示AvB;值为零，表示A=Breturn 0;/ListCompLNode* Locate(LinkList LJnt x)链表上的元素查找，返回指针(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->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;while(q->freq<=p->freq) 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(ex<q->exp) xp*=xO;sum+=q->coef*xp;q+；return sum;/GetValue_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->exp<q->exp)(r->coef=p->coef;r->exp=p->exp;p+;r+;else if(p->exp<q->exp)(r->coef-q->coef;r->exp=q->exp;q+;r+;)elseif(p->coef-q->coef)!=0) /只有同次项相减不为零时才需要存入P3中(r->coef=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;)/QiuDao_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;while(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(i>l) 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; 删除第一个元素 else(P=L;while(-i>l) 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->data<=mink) p=p->next; /p 是最后个不大于 mink 的元素if(p->next) /如果还有比mink更大的元素 (q=p->next;while(q->data<maxk) q=q->next; /q 是第个不小于 maxk 的元素 p->next=q;/Delete_BetweenStatus 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(i=l J=A.length;i<j;i+J)/reversevoid LinkList_reverse(Linklist &L)链表的就地逆置;为简化算法,假设表长大于2 p=L->next;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; while(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->data<pb->data| |! pb) _pc=pa;q=pa->next;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_Intersectvoid LinkList_Intersect(LinkList A,LinkList B,LinkList &C)在链表结构上重做上 题(p=A->next;q=B->next;pc=(LNode*)malloc(sizeof(LNode);while(p&&q)(if(p->data<q->data) p=p->next;else if(p->data>q->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_Intersectvoid 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->data<q->data) p=p->next;else if(p->data>q->data) q=q->next;else 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的就跳过,到大于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->data<q->data) p=p->next;else if(p->data>q->data) q=q->next;else(u=p-data; /确定待删除元素uwhile(r->next->data<u) r=r->next; 确定最后一个小于u的元素指针r if(r->next->data=u)(s=r->next;while(s->data=u)( 一t=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(DuLinkList &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;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 &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 <i&&q)q=XorP(p->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);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(+j<i&&q)(q=XorP(p->LRPtr,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;