算法思想：采用归并的思想，设置两个工作指针pa和pb，对两个链表进行归并扫描, 只有同时出现在两集合中的元素才链接到结果表中且仅保留一个,其他的结点全部释放， 当一个链表遍历完毕后,释放另一个表中剩下的全部结点。
LinkList Union(LinkList &la,LinkList &lb){ LNode *pa=la->next,*pb=lb->next,*head,q; //设工作指针分别为pa和pb,q为要释放的结点 head=la; //head为la的表头结点 while(pa!=NULL && pb!=NULL){ if(pa->data < pb->data){ //若A中当前结点值小于B中当前结点值 q=pa; pa=pa->next; //后移结点 free(q); //释放A中当前结点 } else if(pa->data > pb->data){ //同上 q=pb; pb=pb->data; free(q); } else{ //交集并入结果表中 head->next=pa; //A中结点链接到结果表 head=pa; pa=pa->next; q=pb; //B中释放结点 pb=pb->next; free(q); } } while(pa){ //B已遍历完，A未完 q=pa; pa=pa->next; free(q); //释放A中剩余结点 } while(pb){ //同上 q=pb; pb=pb->next; free(q); } head->next=NULL; // 置结果链表尾指针为NULL free(lb); //释放B表的头结点 return la; }算法思想:因为两个整数序列已存入两个链表中,操作从两个链表的第一个结点开始,若对 应数据相等,则后移指针:若对应数据不等,则A链表从上次开始比较结点的后继开始,B链表 仍从第一个结点开始比较,直到B链表到尾表示匹配成功。A链表到尾而B链表未到尾表示失败 操作中应记住A链表每次的开始结点,以便下次匹配时好从其后继开始。
int Pattern(LinkList A,LinkList B){ LNode *p=A,*pre,*q=B; //p为A链表的工作指针,q为B链表的工作指针，本题假设A和B均无头结点 pre=p; //pre记住每趟比较中A链表的开始结点 while(p&&q){ if(p->data==q->data){ p=p->next; q=q->next; } else{ pre=pre->next; p=pre; //A链表新的开始比较结点 q=B; //q从B链表第一个结点开始 } } if(q==NULL){ //B已经结束 return 1; //1说明B是A的子序列，0不是A的子序列 } else{ return 0; } }算法思想:让p从左向右扫描,q从右向左扫描,直到它们指向同一结点(p==q,当循环双 链表中结点个数为奇数时)或相邻(p->next=q或q-> prior=p,当循环双链表中结点个数为偶 数时)为止,若它们所指结点值相同,则继续进行下去,否则返回0。若比较全部相等,则返回1
int Symmetry(DLinkList L){ DNode *p=L->next,*q=L->prior; //两头工作指针 while(p!=q || q->next!=p){ //循环工作条件 if(p->data==q->data){ //所指结点值相同则继续比较 p=p->next; q=q->prior; } else{ return 0; //否则，返回0 } } return 1; //比较结束后返回1 }算法思想:先找到两个链表的尾指针,将第一个链表的尾指针与第二个链表的头结点链接起 来,再使之成为循环的。
LinkList Link(LinkList &h1,LinkList &h2){ LNode *p,*q; //分别指向两个链表的尾结点 p=h1; while(p->next!=NULL){ //寻找h1的尾结点 p=p->next; } q=h2; while(q->next!=NULL){ //寻找h2的尾结点 q=q->next; } p->next=h2; //将h2链接到h1之后 q->next=h1; //将h1的尾结点指向h1 return h1; }表中结点值最小的结点并输出,然后将该结点从中删除,直到单链表空为止,再删除表 头结点。 算法思想:对于循环单链表L,在不空时循环:每循环一次查找一个最小结点(由minp指向最小值结 点, minpre指向其前驱结点)并删除它。最后释放头结点
void Del_All(LinkList &L){ LNode *minpre,*minp,*pre,*p; while(L->next!=L){ p=L->next; pre=L; minp=p;minpre=pre; while(p!=L){ if(p->data < minp->data){ minp=p; minpre=pre; } pre=p; p=p->next; } printf("%d",minp->data); minpre->next=minp->next; free(minp); } free(L); }指针)、data(数据)和next(后继指针)域外,还有一个访问频度域freq.在 链表被启用前,其值均初始化为零。每当在链表中进行一次 Locate(L,x)运算时, 令元素值为ⅹ的结点中freq域的值增1,并使此链表中结点保持按访问频度非增 (递减)的顺序排列,同时最近访问的结点排在频度相同的结点前面,以便使频繁 访问的结点总是靠近表头。试编写符合上述要求的 Locate(L,x)运算的算法,该 运算为函数过程,返回找到结点的地址,类型为指针型 算法思想:首先在双向链表中查找数据值为x的结点,查到后,将结点从链表上摘下,然后 再顺着结点的前驱链查找该结点的插入位置(频度递减,且排在同频度的第一个,即向前找到第 比它的频度大的结点,插入位置为该结点之后),并插入到该位置。
DLinkList Locate(DLinkList &L,ElemType x){ DNode *p=L->next,*q; //p为工作指针，q为p的前驱，用于查找插入位置 while(p && p->data!=x){ p=p->next; //查找值为x的结点 } if(!p){ printf("不存在值为x的结点\n"); exit(0); } else{ p->freq++; //令元素值为x的结点的freq域+1 if(p->next!=NULL){ p->next-pred=p->pred; } p->pred->next=p->next; //将p结点从链表上摘下 q=p->nextpred; //以下查找p结点的插入位置 while(q!=L && q->freq <= p->freq){ q=q->pred; } p->next=q->next; q->next->pred=p; //将p结点插入，一定是排在同一频率的第一个 p->pred=q; q->next=p; } return p; //返回值为x的结点的指针 }假设该链表只给出了头指针1ist.在不改变链表的前提下,请设计一个尽可能高效的 算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结 的data域的值,并返回1;否则,只返回0.要求： 1)描述算法的基本设计思想 2)描述算法的详细实现步骤 3)根据设计思想和实现步骤,采用程序设计语言描述算法(使用C、C++或Java语言 实现)关健之处请给出简要注释 1)算法的基本设计思想如下 问题的关键是设计一个尽可能高效的算法,通过链表的一次遍历,找到倒数第k个结点的位 置。算法的基本设计思想是:定义两个指针变量p和q,初始时均指向头结点的下一个结点(链 表的第一个结点),p指针沿链表移动:当p指针移动到第k个结点时,q指针开始与p指针同 步移动;当p指针移动到最后一个结点时,q指针所指示结点为倒数第k个结点。以上过程对链 表仅进行一遍扫描。 2)算法的详细实现步骤如下 ① count=0,p和q指向链表表头结点的下一个结点 ②若p为空,转⑤ ③若 count等于k,则q指向下一个结点:否则, count= count+1 ④p指向下一个结点,转② ⑤若 count等于k,则查找成功,输出该结点的data域的值,返回1:否则,说明k值 超过了线性表的长度,查找失败,返回0 ⑤算法结束
typedef int ElemType; //链表数据的类型定义 typedef struct LNode{ //链表结点的结构定义 ElemType data; //结点数据 struct LNode *link; //结点链接指针 }LNode,*LinkList; int Search_k(LinkList list,int k){ //查找链表list倒数第k个结点，并输出该结点data域的值 LNode *p=list->link,*q=list->link; //指针p、q指示第一个结点 int count=0; while(p!=NULL){ //遍历链表直到最后一个结点 if(count<k) count++; //计数，若count<k只移动p else q=q->link; p=p->link; //之后让p、q同步移动 } if(count<k){ return 0; //若查找失败返回0 } else{ //否则打印并返回1 printf("%d",q->data); return 1; } }可共享相同的后缀存储空间,例如,"loading"和"being"的存储映像如下图所示
设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为[data][next] 请设计一个时间上尽可能高效的算法,找出由str1和str2所指向两个链表共同后缀 的起始位置(如图中字符i所在结点的位置P).要求 1)给出算法的基本设计思想 2)根据设计思想,采用C或C艹或Java语言描述算法,关键之处给出注释 3)说明你所设计算法的时间复杂度. 1)算法的基本设计思想如下 ①分别求出str1和str2所指的两个链表的长度m和n ②将两个链表以表尾对齐:令指针P、q分别指向atx1和atr2的头结点,若m2n,则 指针p先走,使p指向链表中的第m=n+1个结点:若m<n,则使q指向链表中的第 n一m+1个结点,即使指针p和q所指的结点到表尾的长度相等 ③反复将指针p和q同步向后移动,当p、q指向同一位置时停止,即为共同后级的起始 位置,算法结束。
typedef struct Node{ char data; struct Node *next; }SNode; init listlen(SNode *head){ //求链表长度的函数 int len=0; while(head->next!=NULL){ len++; head=head->next; } return len; } SNode* find_addr(SNode *str1,SNode *str2){ int m,n; SNode *p,*q; m=listlen(str1); //求str1的长度 n=listlen(str2); //求str2的长度 for(p=str1;m>n;m--){ //若m>n,使p指向链表中的第m-n+1个结点 p=p->next; } for(q=str2;m<n;n--){ //若m<n,使p指向链表中的第n-m+1个结点 q=q->next; } while(p->next!=NULL && p->next!=q->next){ //将指针p和q同步向后移动 p=p->next; q=q->next; } return p->next; //返回共同后缀的起始地址 }(n为正整数).现要求设计一个时间复杂度尽可能高效的算法,对于链表中data的绝对值 相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。例如,若给定的单 链表head如下:
要求： 1)给出算法的基本设计思想 2)使用C或C艹语言,给出单链表结点的数据类型定义 3)根据设计思想,采用C或C+语言描述算法,关键之处给出注释 4)说明你所设计算法的时间复杂度和空间复杂度
1)算法的基本设计思想 ·算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值,从而只需对链 表进行一趟扫描 因为|data|<=n,故辅助数组q的大小为n+1,各元素的初值均为0。依次扫描链表中的 各结点,同时检查q[ |data|]的值,若为0则保留该结点,并令 g[Idatal1=1;否则将 该结点从链表中删除。
typedef struct node{ int data; struct node *link; }NODE; Typedef NODE *PNODE; void func(PNODE h,int n){ PNODE p=h,r; int *q,m; q=(int*)malloc(sizeof(int)*(n+1)); //申请n+1个位置的辅助空间 for(int i=0;i<n+1;i++){ //数组元素初值置为 *(q+i)=0; } while(p->link!=NULL){ m=p->link->data>0? p->link->data:-p->link->data; if(*(q+m)==0){ //判断该结点的data是否已出现过 *(q+m)=1; //首次出现 p=p->link; //保留 } else{ //重复出现 r=p->link; //删除 p->link=r->link; free(r); } } free(q); }1)算法的基本设计思想 设置快慢两个指针分别为fat和s1ow,初始时都指向链表头head,slow每次走一步, 即s1ow=s1ow->next;fast每次走两步,即fast=faat->next->next,由于fast比s1ow 走得快,如果有环,fast一定会先进入环,而s1ow后进入环,当两个指针都进入环后,经过 若干次操作后两个指针定能在环上相遇。这样就可以判断一个链表是否有环 如下图所示,当s1ow刚进入环时,faat早已进入环。因为fat每次比s1ow多走一步 且fast与s1ow的距离小于环的长度,所以fast与s10w相遇时,s1ow所走的距离不超过环 的长 如下图所示,设头结点到环的入口点的距离为a,环的入口点沿着环的方向到相遇点的距离 为x,环长为x,相遇时fast绕过了n圈,则有2(a+x)=a+nx+x,即a=n*x-x,显然从头结点到环的入口点的距离等于n倍的环长减去 环的入口点到相遇点的距离。因此可设置两个指针,一个指向head,一个指向相遇点,两个指 针同步移动(均为一次走一步),相遇点即为环的入口点
LNode* FindLoopStart(LNode *head){ LNode *fast=head,*slow=head; //设置快慢两个指针 while(slow!=NULL && fast->next!=NULL){ slow=slow->next; //每次走一步 fast=fast->next->next; //每次走两步 if(slow==fast)break; //相遇 } if(slow==NULL || fast->next==NULL){ return NULL; //没有环，返回NULL } LNode *p1=head,*p2=slow; //分别指向开始点、相遇点 while(p1!=p2){ p1=p1->next; p2=p2->next; } return p1; //返回入口点 }请设计一个空间复杂度为O(1)且时间上尽可能高效的算法,重新排列L中的各结点,得 到线性表L=(a1,an,a2,an-1,a3,an-2,…),要求: 1)给出算法的基本设计思想 2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释 3)说明你所设计的算法的时间复杂度
1)算法的基本设计思想 先观察L=(a,a2,a,…,an2,an1,a)和L=(,a,、an1,2,2),发现L是由L摘取第 个元素,再摘取倒数第一个元素…依次合并而成的。为了方便链表后半段取元素,需要先将 L后半段原地逆置[题目要求空间复杂度为O1),不能借助栈,否则每取最后一个结点都需要遍 历一次链表。①先找出链表L的中间结点,为此设置两个指针p和q,指针p每次走一步,指针 q每次走两步,当指针q到达链尾时,指针p正好在链表的中间结点:②然后将L的后半段结点 原地逆置。③从单链表前后两段中依次各取一个结点,按要求重排。
void change_list(NODE* h){ NODE *p,*q,*r,*s; p=q=h; while(q->next!=NULL){ //寻找中间结点 p=p->next; //p走一步 q=q->next; if(q->next!=NULL) q=q->next; //q走两步 } q=p->next; //p所指结点为中间结点，q为后半段链表的首结点 p->next=NULL; while(q!=NULL){ //将链表后半段逆置 r=q->next; q->next=p->next; p->next=q; q=r; } s=h->next; //s指向前半段的第一个数据结点，即插入点 q=p->next; //q指向后半段的第一个结点 p->next=NULL; while(q!=NULL){ //将链表后半段的结点插入到指定位置 r=q->next; //r指向后半段的下一个结点 q->next=s->next; //将q所指结点插入到s所指结点之后 s->next=q; s=q->next; //s指向前半段的下一个插入点 q=r; } }