数据结构，线性表，链表常见算法

算法和问题来自于试卷，辅导书，以及网络。

// 数据结构 typedef struct LNode{ int data; struct Lnode *next; }LNode,*LinkList;

算法2.2.11

假设有两个单链表，其中元素递增排列，编写算法将这两个链表归并为一个按元素值递减次序排列的单链表，要求利用原来两个单链表的节点存放归并后的节点。

分析：假设有A,B两个链表，均带有头节点，将他们的节点依次取下比较，对较小的采用头插法即可。

void mergeDescendList(LinkList &A, LinkList &B) { Lnode *pa=A->next,pb=B->next,*q; //pa，pb遍历A,B表，q用于头插法 A->next=NULL; B->next=NULL; while(pa!=NULL&&pb!=NULL) { if(pa->data<pb->data) { q=pa->next; pa->next=A->next; A->next=pa; pa=q; } else { q=pb->next; pb->next=A->next; A->next=pb; pb=q; } } //该循环选择较小值头插到A中 while(pa!=NULL) { q=pa->next; pa->next=A->next; A->next=pa; pa=q; } while(pb!=NULL) { q=pb->next; pb->next=A->next; A->next=pb; pb=q; } //对仍有剩下的表进行插入 free(B); }

算法2.2.12

假设有两个单链表A,B，其中元素递增排列，编写算法将这两个链表A,B中的公共元素产生链表C，并且不破坏A,B中节点。

分析：A,B均有序，则可从两表中的第一个节点开始，如果两节点值相同，则申请新节点插入到C中，若不等，则将较小的那个节点后移，继续比较。

void mergeCommon(LinkList &A, LinkList &B) { Lnode *pa=A->next,pb=B->next,*q; //pa，pb遍历A,B表，q用于尾插法 LinkList C=(LinkList)malloc(sizeof(Lnode)); q=C; while(pa!=NULL&&pb!=NULL) { if(pa->data==pb->data) { s=(Lnode*)malloc(sizeof(Lnode)); s->data=pa->data; s->next=q->next; q->next->s; q=q->next; pa=pa->next; pb=pb->next; } else if(pa->data>pb->data) pb=pb->next; else pa=pa->next; } q->next=NULL; }

算法2.2.13

假设有两个单链表A,B，其中元素递增排列，编写算法求A,B元素的交集，并且存放在A中。

分析：类似2.2.12,不同之处在于要释放不等的节点。可参照前两个算法的做法。

void mergeCommon1(LinkList &A, LinkList &B) { Lnode *pa=A->next,pb=B->next,*q,*r; //pa，pb遍历A,B表，q用于尾插法 A->next=NULL; q=A;r=A; while(pa!=NULL&&pb!=NULL) { if(pa->data==pb->data) { q=pa->next; pa->next=r->next; r->next=pa; r=r->next; pa=q; //到此，A表中节点保留，还需释放B表节点 q=pb; pb=pb->next ; free(q); //释放 } else if(pa->data>pb->data) { q=pb; pb=pb->next ; free(q); } else { q=pa; pa=pa->next ; free(q); } } while(pa!=NULL) { q=pa; pa=pa->next ; free(q); } while(pb!=NULL) { q=pb; pb=pb->next ; free(q); } r->next=NULL; free(B); }

算法2.2.14

假设有两个单链表A,B，编写算法，判断序列B是否是序列A的连续子序列。

分析：类似串算法中的朴素匹配算法，对B中的每个元素逐个与A中元素比较.

bool subSequence(LinkList &A, LinkList &B) { Lnode *pa=A->next,pb=B->next; q=pa->next; //q指针指示开始匹配的A的下一个 while(pa!=NULL&&pb!=NULL) { if(pa->data==pb->data) { pa=pa->next; pb=pb->next; } else { pb=B->next; pa=q; q=q->next } //若不等，B从头开始，A跳到下一个 } if(pb==NULL) return 1; //循环结束，若pb指针已经指向空，说明B匹配成功 else return 0 ; }

算法2.2.15

假设有两个循环单链表，表头指针为h1，h2，编写函数将链表h2链接到h1之后，链接后的链表仍然保持循环链表状态。

分析：略

void connCycle(LinkList &h1, LinkList &h2) { Lnode *p=h2->next,*q=h1->next; h2->next==NULL; while(q->next!=h1) q=q->next; //目前q指向h1末尾，p指向h2第一个元素 q->next=p; while(p->next!=h2) p=p->next; p->next=h1; free(h2); }

算法2.2.16

假设有一个带头结点的循环单链表，节点均为正整数。设计算法找出单链表中最小的元素输出，并删除该节点，直到单链表为空，再删除最小的节点。

分析：略

void deleteMin(LinkList &h) { Lnode *p=h->next,*pre=h; Lnode *minp=p,*minpre=pre; while(h->next!=h) { while(p->next!=h) { if(p->next->data<minp->data) { minpre=p; minp=pre->next; } pre=p; p=p->next; } preitf("%d",minp->data); minpre->next=minp->next; free(minp); } free(h); }

算法2.2.17

假设有一个带头结点的单链表,只知道它的头指针为L，设计算法找出单链表中倒数第k个节点上的位置，若查找成功，输出该节点的值，返回1；否则返回0，要求不能改变链表。(2009)

分析： 思路一：遍历链表获得表长,之后再遍历到第n-k+1个元素输出该值即可,共需要两次扫描，时间复杂度为o(n)。 思路二：高效算法，可设置两个指针p，q，开始时都指向表中第一个元素，p先开始遍历，当遍历到第k个元素时，q和p同时遍历，当p到达最后一个时q即到达倒数第k个。

int findK(LinkList L,int k) //思路一 { int n=0,i=0; Lnode *p=L; if(L->next==NULL) return 0; while(p->next=NULL) { p=p->next; ++n; } p=L; if(k>n) return 0; while(i!=n-k+1) { ++i; p=p->next; } printf("%d",p->data); return 1; } bool findK(LinkList L,int k) //思路二 { int n=0; Lnode *p=L->next,*q=p; if(L->next==NULL) return 0; while(p!=NULL) { p=p->next; ++n; if(n>=k) q=q->next; } if(n<k) return 0; //表长小于k 返回错误 else { printf("%d",q->data); return 1; } }

算法2.2.18

假设用带头结点的单链表保存单词，当两个单词有相同后缀时可共享相同的后缀存储空间，如"loading"和"being"。设计算法，找出单链表str1,str2的共同后缀的起始位置(2012)

分析：可先对两表进行遍历，获得两表表长，对长的那一个表，先用指针遍历到和短表相同的长度的位置，再同时遍历两表，同时判断两个指针是否指向同一位置，若指向地址相同，则停止遍历

Lnode *commonH(LinkList str1,LinkList str2) { int m,n,i=0; Lnode *p=str1,*q=str2; while(p->next!=NULL) { ++m; p=p->next; } //m为str1表长 while(q->next!=NULL) { ++n; q=q->next; //n为str2表长 } p=str1->next; q=str2->next; if(m>n) while(i++<m-n) p=p->next; if(m<n) while(i++<n-m) q=q->next; //两个while循环将较长的表从第m-n+1或n-m+1处开始遍历 while(p->next!=q->next&&p->next!=NULL) { p=p->next; q=q->next; } return p->next; }

算法2.2.19

假设用单链表保存m个整数，节点结构为data,link，并且|data|<=n。设计一个尽可能高效的算法，对于链表中data绝对值相等的节点，仅保存第一次出现的节点，删除剩余绝对值相等的节点(2015)

分析：若采用朴素的思想，对每个链表中的节点需要比较一次，时间复杂度达到了o(n²)。可以考虑采用以空间换时间的方法，申请一个长度为n+1的数组，初始值均为0，对其中出现的每个值将其存入下标为data的位置，并更改data处的值为1，对于链表以后的元素，判断是否在数组中下标为1，若是，则删除。

void deleteF(LinkList &L) { int A[n+1]; Lnode *p=L->link,*pre=L,*q; for(int i=0;i<n+1;i++) A[i]=0; while(p!=NULL) { if(A[p->data]==0) { A[p->data]==1; p=p->link; } if(A[p->data]==1) { q=p; p=p->link; pre->link=q->link; free(q); } } }