【前面使用的所有链表的定义在第29节】
试题16:两个整数序列A,B存在两个单链表中,设计算法判断B是否是A的连续子序列。
bool Pattern(LinkList L1,LinkList L2){
//此函数实现比较L1的子串中是否有L2
LNode *p, *q; //工作在L1,p记录L1子串的首元
LNode *r; //工作在L2
p = L1->next;
q = L1->next;
r = L2->next;
while(q!=NULL && r!=NULL){
if(q->data == r->data){ //p指针不动,q,r指针后移
q = q->next;
r = r->next;
}
else{
r = L2->next; //L2指针归零
p = p->next; //L1指针后移
q = p;
}
}
if(r == NULL){
return true;
}
else{
return false;
}
}
int main(){
LinkList L1, L2;
InitList(L1);
Create(L1);
PrintList(L1);
InitList(L2);
Create(L2);
PrintList(L2);
printf("%d",Pattern(L1,L2));
return 0;
}
输出:
当前单链表的所有元素:[3] [1] [2] [5] [4]
当前单链表的所有元素:[1] [2]
1
当前单链表的所有元素:[1] [2] [3] [4] [5]
当前单链表的所有元素:[6] [7] [8]
0
试题17:设计一个算法判断带头结点的循环双链表是否对称。
这里需要重新书写双链表的结构体定义,不能采用29节的代码。完整代码如下:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 100
#define ElemType int
#define Status int
//循环双链表的数据结构,一个结点,两个指针分别指向前驱和后继。
typedef struct LNode
{
ElemType data;
struct LNode *next,*prior;
}LNode, *LinkList;
//初始化
int InitList(LinkList &L)
{
L = (LNode *)malloc(sizeof(LNode));
L->next = NULL;
L->prior = NULL;
return 1;
}
//输出
void PrintList(LinkList L)
{
printf("当前单链表的所有元素:");
LNode *p;
p = L->next;
while (p != L)
{
printf("[%d] ", p->data);
p = p->next;
}
printf("\n");
}
//尾插法创建单链表
int Create(LinkList &L)
{
int n, e;
LNode *temp = L;//声明一个指针指向头结点,用于遍历链表
printf("请输入要输入元素的个数:");
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
LNode *a = (LNode*)malloc(sizeof(LNode));
printf("请输入第%d元素的值:", (i));
scanf("%d", &e);
a->data = e;
temp->next = a;
a->next = NULL;
a->prior = temp;
temp = temp->next;
}
temp->next = L;
L->prior = temp;
return 1;
}
//插入元素
int InsertList(LNode *L, int i, ElemType e)
{
LNode *p = L;
int j = 0;
while (p && (j < i - 1)) //寻找要插入位置的前驱结点,让p指向它
{
p = p->next;
++j;
}
if (!p || j > i - 1) return 0; //插入位置非法,返回0
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e; //创建一个新结点存放要插入的元素e
s->next = p->next; //把新结点的指针域指向p->next
s->prior = p;
p->next = s; //把p->next指向要插入的新结点
p = p->next;
s = s->next;
s->prior = p;
return 1;
}
//删除元素
int DeleteList(LNode *L, int i)
{
LNode *p = L;
int j = 0;
while (p->next && (j < i - 1)) //寻找要删除结点的前驱结点,让p指向它
{
p = p->next;
++j;
}
if (!p->next || j > i - 1) return 0; //删除位置非法,返回0
LNode *q;
q = p->next; //暂存删除结点,以便随后释放
p->next = q->next; //把p->next指向p->next->next,即q->next
q->next->prior = p;
free(q); //释放结点
return 1;
}
//按值查找元素
int LocateElem(LNode *L, ElemType e)
{
int i = 1;
LNode *p = L->next;
while (p!=L && p->data != e) //从第一个结点开始,依次向后遍历比较
{
p = p->next;
i++;
}
if(p) return i;
else return 0;
}
bool Symmetry(LinkList L){
//此函数实现判断循环双链表是否对称
LNode *p, *q;
p = L->next; //第一个元素
q = L->prior; //最后一个元素
while(p!=q&&p->next!=q){ //奇数个元素的结束条件:p=q,偶数个:p->next=q
if(p->data == q->data){
p = p->next;
q = q->prior;
}
else
return false;
}
return true;
}
int main(){
LinkList L1;
InitList(L1);
Create(L1);
PrintList(L1);
printf("%d",Symmetry(L1));
return 0;
}
输出:
当前单链表的所有元素:[1] [2] [3] [2] [1]
1
当前单链表的所有元素:[1] [2] [3] [3] [2] [1]
1
当前单链表的所有元素:[1] [2] [3] [4] [3] [3] [1]
0
试题18:有两个循环单链表,链表头指针分别是L1和L2,编写一个函数将链表L2链接到链表L1之后,要求链接后的链表仍保持循环链表形式。
这里同样不能直接采用29节的代码,不过在建立单链表的最后加一句temp=L即可。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 100
#define ElemType int
#define Status int
//循环单链表的数据结构,尾结点指针指向表头结点。
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
//初始化
int InitList(LinkList &L)
{
L = (LNode *)malloc(sizeof(LNode));
L->next = L;
return 1;
}
//输出
void PrintList(LinkList L)
{
printf("当前单链表的所有元素:");
LNode *p;
p = L->next;
while (p != L)
{
printf("[%d] ", p->data);
p = p->next;
}
printf("\n");
}
//尾插法创建单链表
int Create(LinkList &L)
{
int n, e;
LNode *temp = L;//声明一个指针指向头结点,用于遍历链表
printf("请输入要输入元素的个数:");
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
LNode *a = (LNode*)malloc(sizeof(LNode));
printf("请输入第%d元素的值:", (i));
scanf("%d", &e);
a->data = e;
temp->next = a;
a->next = NULL;
temp = temp->next;
}
temp->next = L;
return 1;
}
//插入元素
int InsertList(LNode *L, int i, ElemType e)
{
LNode *p = L;
int j = 0;
while (p && (j < i - 1)) //寻找要插入位置的前驱结点,让p指向它
{
p = p->next;
++j;
}
if (!p || j > i - 1) return 0; //插入位置非法,返回0
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e; //创建一个新结点存放要插入的元素e
s->next = p->next; //把新结点的指针域指向p->next
p->next = s; //把p->next指向要插入的新结点
return 1;
}
//删除元素
int DeleteList(LNode *L, int i)
{
LNode *p = L;
int j = 0;
while (p->next && (j < i - 1)) //寻找要删除结点的前驱结点,让p指向它
{
p = p->next;
++j;
}
if (!p->next || j > i - 1) return 0; //删除位置非法,返回0
LNode *q;
q = p->next; //暂存删除结点,以便随后释放
p->next = q->next; //把p->next指向p->next->next,即q->next
free(q); //释放结点
return 1;
}
//按值查找元素
int LocateElem(LNode *L, ElemType e)
{
int i = 1;
LNode *p = L->next;
while (p!=L && p->data != e) //从第一个结点开始,依次向后遍历比较
{
p = p->next;
i++;
}
if(p) return i;
else return 0;
}
LinkList Link(LinkList L1,LinkList L2){
//此函数实现判断循环双链表是否对称
LNode *p, *q;
p = L1->next; //L1工作指针
q = L2->next; //L2工作指针,首先找到L1,L2最后一个元素
while(p->next!=L1){
p = p->next;
}
while(q->next!=L2){
q = q->next;
}
p->next = L2->next;
q->next = L1;
free(L2);
return L1;
}
int main(){
LinkList L1,L2;
InitList(L1);
Create(L1);
PrintList(L1);
InitList(L2);
Create(L2);
PrintList(L2);
PrintList(Link(L1,L2));
return 0;
}
输出:
请输入要输入元素的个数:4
请输入第1元素的值:1
请输入第2元素的值:2
请输入第3元素的值:3
请输入第4元素的值:4
当前单链表的所有元素:[1] [2] [3] [4]
请输入要输入元素的个数:5
请输入第1元素的值:5
请输入第2元素的值:6
请输入第3元素的值:7
请输入第4元素的值:8
请输入第5元素的值:9
当前单链表的所有元素:[5] [6] [7] [8] [9]
当前单链表的所有元素:[1] [2] [3] [4] [5] [6] [7] [8] [9]
试题19:不断输出并删除最小值结点。此题非常同试题4.略过。
试题20:设头指针为L的带有表头结点的非循环双向链表,其每个结点中除有prior(前驱指针),data(数据),next(后继指针)域外,还有一个访问频度域freq。在链表被启用前,其值均初始化为零。每当在连表中进行一次Locate(L,x)运算时,令元素值为x的结点中freq域的值增1,并使此链表中结点保持按访问频度非递增的顺序排列,同时最近访问的结点排在频度相同的结点的前面,以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法,该运算为函数过程,返回找到结点的地址,类型为指针型。
思路:这题就调整指针。由于是双链表所以找前驱后继都很方便。重新书写双链表的结构体类型然后作答:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 100
#define ElemType int
#define Status int
//双链表带freq域的数据结构
typedef struct LNode
{
ElemType data;
int freq;
struct LNode *next,*prior;
}LNode, *LinkList;
//初始化
int InitList(LinkList &L)
{
L = (LNode *)malloc(sizeof(LNode));
L->next = NULL;
L->prior = NULL;
return 1;
}
//输出
void PrintList(LinkList L)
{
printf("当前链表的所有元素:");
LNode *p;
p = L->next;
while (p != NULL)
{
printf("[%d]%d ", p->data,p->freq);
p = p->next;
}
printf("\n");
}
//尾插法创建双链表
int Create(LinkList &L)
{
int n, e;
LNode *temp = L;//声明一个指针指向头结点,用于遍历链表
printf("请输入要输入元素的个数:");
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
LNode *a = (LNode*)malloc(sizeof(LNode));
printf("请输入第%d元素的值:", (i));
scanf("%d", &e);
a->data = e;
a->freq = 0;
temp->next = a;
a->prior = temp;
a->next = NULL;
temp = temp->next;
}
return 1;
}
//按位插入元素
int InsertList(LNode *L, int i, ElemType e)
{
LNode *p = L;
int j = 0;
while (p && (j < i - 1)) //寻找要插入位置的前驱结点,让p指向它
{
p = p->next;
++j;
}
if (!p || j > i - 1) return 0; //插入位置非法,返回0
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e; //创建一个新结点存放要插入的元素e
s->freq = 0;
s->next = p->next; //把新结点的指针域指向p->next
p->next->prior = s;
p->next = s; //把p->next指向要插入的新结点
s->prior = p;
return 1;
}
//删除元素
int DeleteList(LNode *L, int i)
{
LNode *p = L;
int j = 0;
while (p->next && (j < i - 1)) //寻找要删除结点的前驱结点,让p指向它
{
p = p->next;
++j;
}
if (!p->next || j > i - 1) return 0; //删除位置非法,返回0
LNode *q;
q = p->next; //暂存删除结点,以便随后释放
p->next = q->next; //把p->next指向p->next->next,即q->next
q->next->prior = p;
free(q); //释放结点
return 1;
}
//按值查找元素
int LocateElem(LNode *L, ElemType e)
{
int i = 1;
LNode *p = L->next;
LNode *q; //q用来向前遍历,寻找比其freq值大的结点
while (p&&p->data != e) //从第一个结点开始,依次向后遍历比较
{
p = p->next;
i++;
}
if(p){
p->freq ++;
q = p;
while(q->freq <= p->freq && q!=L){
q = q->prior;
}
p->prior->next = p->next;
p->next->prior = p->prior;
p->next = q->next;
p->prior = q;
q->next = p;
p->next->prior = p;
return i;
}
else
return 0;
}
int main(){
LinkList L;
InitList(L);
Create(L);
PrintList(L);
printf("查找的元素在第%d位\n",LocateElem(L, 2));
PrintList(L);
printf("查找的元素在第%d位\n",LocateElem(L, 1));
PrintList(L);
printf("查找的元素在第%d位\n",LocateElem(L, 1));
PrintList(L);
return 0;
}
输出:
请输入要输入元素的个数:4
请输入第1元素的值:1
请输入第2元素的值:2
请输入第3元素的值:3
请输入第4元素的值:4
当前链表的所有元素:[1]0 [2]0 [3]0 [4]0
查找的元素在第2位
当前链表的所有元素:[2]1 [1]0 [3]0 [4]0
查找的元素在第2位
当前链表的所有元素:[1]1 [2]1 [3]0 [4]0
查找的元素在第1位
试题21:编写算法判断链表是否有环。
暴力解:首先从头节点开始,依次遍历单链表的每一个节点。每遍历到一个新节点,就从头节点重新遍历新节点之前的所有节点,用新节点ID和此节点之前所有节点ID依次作比较。如果发现新节点之前的所有节点当中存在相同节点ID,则说明该节点被遍历过两次,链表有环;如果之前的所有节点当中不存在相同的节点,就继续遍历下一个新节点,继续重复刚才的操作。
优解:快慢指针法。
//前面共同的部分省略,这里给出创建带环链表的函数,以及本题要求的函数FindLoopStart
//创建一个带环的链表
int Create_Loop(LinkList &L)
{
int n, e;
LNode *temp = L; //声明一个指针指向头结点,用于遍历链表
printf("请输入要输入元素的个数:");
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
LNode *a = (LNode*)malloc(sizeof(LNode));
printf("请输入第%d元素的值:", (i));
scanf("%d", &e);
a->data = e;
temp->next = a;
a->next = NULL;
temp = temp->next;
}
temp->next = L->next->next; //尾指针指向第2个结点,这样就有了环,这个函数建立的环的起始结点就是第2个
return 1;
}
LinkList FindLoopStart(LinkList L){
LNode *fast, *slow;
fast = L;
slow = L;
while(fast!=NULL&&fast->next!=NULL){
slow = slow->next; //慢指针走一步
fast = fast->next->next; //快指针走两步
if(fast==slow){ //快慢指针相遇,退出,这时候有环
break;
}
}
if(fast==slow){ //有环的情况,一个从表头开始,一个从上面的相遇点开始,再次相遇的时候就是环的起始点
slow = L;
while(fast!=slow){
slow = slow->next;
fast = fast->next;
}
printf("%d\n", fast->data);
return fast;
}
else
printf("链表无环\n");
return NULL; //无环,返回NULL
}
int main(){
LinkList L1,L2;
InitList(L1);
Create(L1); //无环链表
PrintList(L1);
InitList(L2);
Create_Loop(L2); //有环链表
FindLoopStart(L1);
FindLoopStart(L2);
return 0;
}
输出:
链表无环
2
试题22:(2009年联考真题)
思路:设两个指针,一个指针先移动k,然后两个指针一起移动,最后第一个指针移到表尾第二个指针就是倒数第k个位置。
int Change(LinkList L,int k){
//此函数查找链表倒数第k个结点
LNode *p, *q;
p = L;
q = L;
for (int i = 0; i < k;i++){
p = p->next;
if(p == NULL)
return 0;
}
while(p !=NULL){
p = p->next;
q = q->next;
}
printf("%d\n", q->data);
return 1;
}
int main(){
LinkList L;
InitList(L);
Create(L);
PrintList(L);
printf("%d",Change(L,3));
return 0;
}
输出:
当前单链表的所有元素:[1] [2] [3] [4] [5]
3
1
当前单链表的所有元素:[1] [2] [3] [4] [5] [6]
4
1
当前单链表的所有元素:[1] [2]
0
试题23:(2012年联考真题)
这道题和前面题8完全一致(甚至这个题直接给了你拓扑结构,比题8还简单一些),可看上一节的解析。
试题24:(2015年联考真题)
此题的思路就是以空间换时间,因为题目中出现了.
int abs(int n){
//此函数用来求绝对值
if(n>0)
return n;
else
return -n;
}
LinkList Delete(LinkList &L,int n){
//此函数对链表中绝对值相等的结点只保留第一个,删除之后所有绝对值相等的结点
LNode *p, *q;
p = L;
q = L->next;
int a[n + 1]; //辅助数组
for (int i = 0; i < n + 1;i++){
a[i] = 0;
}
while(q!=NULL){
if(a[abs(q->data)]==0){
a[abs(q->data)] = 1;
p = p->next;
q = q->next;
}
else{
p->next = q->next;
free(q);
q = p->next;
}
}
return L;
}
int main(){
LinkList L;
InitList(L);
Create(L);
PrintList(L);
PrintList(Delete(L,5));
return 0;
}
输出:
当前单链表的所有元素:[1] [-1] [2] [-2] [3]
当前单链表的所有元素:[1] [2] [3]
前单链表的所有元素:[1] [-4] [3] [2] [-1]
当前单链表的所有元素:[1] [-4] [3] [2]
试题25:(2019年联考真题)
此题分三步走:(1)找中间结点(2)把后半段逆置(3)从前后两段每次取一个结点重排文章来源:https://www.uudwc.com/A/BvPBj/
LinkList Change(LinkList &L){
//此函数对链表a1,a2...an变为a1,an,a2,an-1...
LNode *p, *q, *r, *m;
p = L;
q = L;
while(q!=NULL && q->next !=NULL){
p = p->next;
q = q->next->next;
}
//到此指针p就是我们找的中间结点,下面对p后面的部分做倒序,也就是头插法
q = p->next;
p->next = NULL; //断链
r = q->next;
while(q!=NULL){
q->next = p->next;
p->next = q;
q = r;
if(r == NULL)
break;
r = r->next;
}
//到此我们完成了后面序列的倒序操作,接下来从L和p分别输出。
q = L->next;
r = p->next;
p->next = NULL;
p = q->next;
while(q!=NULL){
q->next = r;
if(r ==NULL)
break;
r = r->next;
q = q->next;
q->next = p;
if(p==NULL)
break;
p = p->next;
q = q->next;
}
return L;
}
int main(){
LinkList L;
InitList(L);
Create(L);
PrintList(L);
PrintList(Change(L));
return 0;
}
输出:文章来源地址https://www.uudwc.com/A/BvPBj/
当前单链表的所有元素:[1] [2] [3] [4] [5]
当前单链表的所有元素:[1] [5] [2] [4] [3]
当前单链表的所有元素:[1] [2] [3] [4] [5] [6]
当前单链表的所有元素:[1] [6] [2] [5] [3] [4]