句容网站,百度商城,建站之星备案,直装模板下载【前面使用的所有链表的定义在第29节】
试题16#xff1a;两个整数序列A#xff0c;B存在两个单链表中#xff0c;设计算法判断B是否是A的连续子序列。
bool Pattern(LinkList L1,LinkList L2){
//此函数实现比较L1的子串中是否有L2LNode *p, *q; //工作在L1,p记录L1子串…【前面使用的所有链表的定义在第29节】
试题16两个整数序列AB存在两个单链表中设计算法判断B是否是A的连续子序列。
bool Pattern(LinkList L1,LinkList L2){
//此函数实现比较L1的子串中是否有L2LNode *p, *q; //工作在L1,p记录L1子串的首元LNode *r; //工作在L2p 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节的代码。完整代码如下
#includestdio.h
#includestdlib.h
#includestring.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; //插入位置非法返回0LNode *s (LNode *)malloc(sizeof(LNode));s-data e; //创建一个新结点存放要插入的元素es-next p-next; //把新结点的指针域指向p-nexts-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; //删除位置非法返回0LNode *q;q p-next; //暂存删除结点以便随后释放p-next q-next; //把p-next指向p-next-next即q-nextq-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!qp-next!q){ //奇数个元素的结束条件pq,偶数个p-nextqif(p-data q-data){p p-next;q q-prior;}elsereturn 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节的代码不过在建立单链表的最后加一句tempL即可。
#includestdio.h
#includestdlib.h
#includestring.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; //插入位置非法返回0LNode *s (LNode *)malloc(sizeof(LNode));s-data e; //创建一个新结点存放要插入的元素es-next p-next; //把新结点的指针域指向p-nextp-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; //删除位置非法返回0LNode *q;q p-next; //暂存删除结点以便随后释放p-next q-next; //把p-next指向p-next-next即q-nextfree(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工作指针首先找到L1L2最后一个元素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)运算的算法该运算为函数过程返回找到结点的地址类型为指针型。
思路这题就调整指针。由于是双链表所以找前驱后继都很方便。重新书写双链表的结构体类型然后作答
#includestdio.h
#includestdlib.h
#includestring.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; //插入位置非法返回0LNode *s (LNode *)malloc(sizeof(LNode));s-data e; //创建一个新结点存放要插入的元素es-freq 0;s-next p-next; //把新结点的指针域指向p-nextp-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; //删除位置非法返回0LNode *q;q p-next; //暂存删除结点以便随后释放p-next q-next; //把p-next指向p-next-next即q-nextq-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 (pp-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;}elsereturn 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!NULLfast-next!NULL){slow slow-next; //慢指针走一步fast fast-next-next; //快指针走两步if(fastslow){ //快慢指针相遇退出这时候有环break;}}if(fastslow){ //有环的情况一个从表头开始一个从上面的相遇点开始再次相遇的时候就是环的起始点slow L;while(fast!slow){slow slow-next;fast fast-next;}printf(%d\n, fast-data);return fast;}elseprintf(链表无环\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
试题222009年联考真题 思路设两个指针一个指针先移动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
试题232012年联考真题 这道题和前面题8完全一致甚至这个题直接给了你拓扑结构比题8还简单一些可看上一节的解析。
试题242015年联考真题 此题的思路就是以空间换时间因为题目中出现了.
int abs(int n){
//此函数用来求绝对值if(n0)return n;elsereturn -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]
试题252019年联考真题 此题分三步走1找中间结点2把后半段逆置3从前后两段每次取一个结点重排
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(pNULL)break;p p-next;q q-next;}return L;
}int main(){LinkList L;InitList(L);Create(L);PrintList(L);PrintList(Change(L));return 0;
}
输出
当前单链表的所有元素[1] [2] [3] [4] [5]
当前单链表的所有元素[1] [5] [2] [4] [3]当前单链表的所有元素[1] [2] [3] [4] [5] [6]
当前单链表的所有元素[1] [6] [2] [5] [3] [4]
