建设网站哪家公司比较好,广州展厅设计公司有哪些,wordpress 内容页摘要,南海网站推广已知两个链表L1和L2分别表示两个集合#xff0c;其中元素递增排列。请设计一个算法#xff0c;用于求出L1与L2的交集#xff0c;并存放在L1链表中。
代码思路#xff1a; 我们创建一个辅助链表L3#xff0c;用于存储L1和L2链表的交集#xff0c;用s遍历L3各个元素
用p和…已知两个链表L1和L2分别表示两个集合其中元素递增排列。请设计一个算法用于求出L1与L2的交集并存放在L1链表中。
代码思路 我们创建一个辅助链表L3用于存储L1和L2链表的交集用s遍历L3各个元素
用p和q分别遍历链表L1和L2因为是两个链表都是递增的所以每次比较p和q结点那个元素更小更小的往后移。如果p和q指向结点大小一样则把它们记录到s中。
过程示意图如下 最后当某个链表遍历结束循环也可以结束了因为一个链表后面没东西了咋能和另一个链表有交集呢
然后题目要求把交集放在L1中所以把L3的复制进去即可。
//两个递增链表求交集
void JiaoJi(LinkList* L1, LinkList* L2) {LNode* p (*L1)-next;//用p遍历L1LNode* q (*L2)-next;//用q遍历L2LinkList L3 (LNode*)malloc(sizeof(LNode));//辅助链表用于存放公共元素LNode* s (LNode*)malloc(sizeof(LNode));//用s遍历L3L3-next s;LNode* pre L3;//记录s前一个位置while (pq) {if (p-next NULL || q-next NULL) {//下一轮退出循环记录当前s位置pre-nextNULL;}if (p-data q-data) {LNode* tmp (LNode*)malloc(sizeof(LNode));tmp-next NULL;s-data p-data;s-next tmp;s s-next;p p-next;q q-next;pre pre-next;}else if (p-data q-data) {q q-next;}else {p p-next;}}s L3-next;//s复位p (*L1)-next;//p复位LNode* tmp (LNode*)malloc(sizeof(LNode));while (s!NULL) {//因为L3是L1和L2的交集所以L3的长度是一定小于等于L1的这里判断条件给一个s即可if (s-next NULL) {//出循环的前一个记录一下此时的p位置tmp p;}p-data s-data;p p-next;s s-next;}tmp-next NULL;//把L1后面的非交集部分断掉
}
int main() {LinkList L1;LinkList L2;InitList2(L1);//初始化一个1 2 3 4 5 6 7 8 9 10的带头结点链表L1InitList3(L2);//初始化一个4 5 6 7 8 9的带头结点链表L2printf(初始L1为);print2(L1);printf(\n);printf(初始L2为);print2(L2);printf(\n);JiaoJi(L1, L2);printf(L1和L2交集为);print2(L1);return 0;
}注初始化带头单链表和打印函数
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includestdbool.h
#includemalloc.h
//单链表定义
//链表结点
int A[10] { 1,2,3,4,5,6,7,8,9,10 };
int B[6] { 4,7,8,9,11,13 };//4,7,8,9,11,13
typedef struct {//定义单链表结点类型int data;//数据域struct LNode *next;//指针域
}LNode, *LinkList;//带头结点初始化-尾插法
void InitList2(LinkList* L) {(*L) (LNode*)malloc(sizeof(LNode));(*L)-next NULL;LNode* rear (*L);//标记表尾int i 0;for (i 0;i 10;i) {LNode* p (LNode*)malloc(sizeof(LNode));//创建一个新结点p-data A[i];//新结点赋值rear-next p;//接到L上rear p;//标记表尾}rear-next NULL;
}//带头结点初始化-尾插法
void InitList3(LinkList* L) {(*L) (LNode*)malloc(sizeof(LNode));(*L)-next NULL;LNode* rear (*L);//标记表尾int i 0;for (i 0;i 6;i) {LNode* p (LNode*)malloc(sizeof(LNode));//创建一个新结点p-data B[i];//新结点赋值rear-next p;//接到L上rear p;//标记表尾}rear-next NULL;
}void print2(LinkList L) {//打印带头结点的链表LNode* i L-next;//用i指针遍历整个链表while (i ! NULL) {printf(%d , i-data);i i-next;}
}
