已知递增有序的两个单链表A和B分别存储一个集合,设计程序实现两个集合的交集运算A=A∩B。
//伪代码struct node *pA = pListAHead; //有序列表A struct node *pB = pListBHead; //有序列表Bstruct node *pCHead = NULL; //A与B交集头struct node *pCEnd = NULL; //A与B交集尾while (pA != NULL && pB != NULL){ if (pA->value == pB->value) { //相等,同时后移 if (pCEnd == NULL) { pCHead = new node(); pCHead->value = pA->value; pCHead->next = NULL; pCEnd = pCHead; } else { pCEnd->next = new node(); pCEnd = pCEnd->next; pCEnd->next = NULL; pCEnd->value = pA->value; } pA = pA->next; pB = pB->next; continue; } else if (pA->value > pB->value) { //最小的相比,B小 B后移 pB = pB->next; continue; } else { //最小的相比,A小 A后移 pA = pA->next; }}
# #include
# #include
#
# typedef struct node
# {
# int data;
# struct node* next;
# }Link;
#
# //链表初始化 必须建立递增的链表
# Link* CreateLa(Link *head,int n)
# {
# Link *p;
# //头插法
# //for(int i=0;i<n;i++)
# //{
# // p = (Link *)malloc(sizeof(Link));
# // p->data = 2*i;
# // p->next = head->next;
# // head->next = p;
# //}
# //尾插法
# for(int i=0;i<n;i++)
# {
# p = (Link *)malloc(sizeof(Link));
# p->data = 2*i;
# head->next = p;
# head = p;
#
# }
# head->next = NULL;
# return head;
# }
#
# Link* CreateLb(Link *head,int n)
# {
# Link *p;
# //尾插法
# for(int i=0;i<n;i++)
# {
# p = (Link *)malloc(sizeof(Link));
# p->data = i+1;
# head->next = p;
# head = p;
#
# }
# head->next = NULL;
# return head;
# }
# void Print(Link *head)
# {
# Link *p = head->next;
# while(p!=NULL)
# {
# printf("%d",p->data);
# p = p->next;
# }
# }
#
# Link *Intersection(Link *La,Link *Lb,Link *Lc)
# {
# Link *pa,*pb,*pc,*p;
# pc = Lc;
# pa = La->next;
# pb = Lb->next;
# while(pa!=NULL&&pb!=NULL)
# {
# if(pa->datadata)
# {
# pa = pa->next;
# }
# if(pa->data>pb->data)
# {
# pb = pb->next;
# }
# else
# {
# p = (Link *)malloc(sizeof(Link));
# p->data = pa->data;
# pc->next = p;
# pc = p;
# pa = pa->next;
# pb = pb->next;
# }
# }
# pc->next = NULL;
# return Lc;
# }
# int main()
# {
# int a,b;
# Link *La,*Lb,*Lc;
# La = (Link *)malloc(sizeof(Link));
# Lb = (Link *)malloc(sizeof(Link));
# Lc = (Link *)malloc(sizeof(Link));
# La->next = NULL;
# Lb->next = NULL;
# Lc->next = NULL;
# printf("请输入链表a的数目:");
# scanf("%d",&a);
# printf("
请输入链表b的数目:");
# scanf("%d",&b);
# CreateLa(La,a);
# printf("链表la为:
");
# Print(La);
# CreateLb(Lb,b);
# printf("
链表lb为:
");
# Print(Lb);
# Intersection(La,Lb,Lc);
# printf("
链表lc为:
");
# Print(Lc);
# puts("
");
# system("pause");
# }
//伪代码
struct node *pA = pListAHead; //有序列表A
struct node *pB = pListBHead; //有序列表B
struct node *pCHead = NULL; //A与B交集头
struct node *pCEnd = NULL; //A与B交集尾
while (pA != NULL && pB != NULL)
{
if (pA->value == pB->value)
{
//相等,同时后移
if (pCEnd == NULL)
{
pCHead = new node();
pCHead->value = pA->value;
pCHead->next = NULL;
pCEnd = pCHead;
}
else
{
pCEnd->next = new node();
pCEnd = pCEnd->next;
pCEnd->next = NULL;
pCEnd->value = pA->value;
}
pA = pA->next;
pB = pB->next;
continue;
}
else if (pA->value > pB->value)
{
//最小的相比,B小 B后移
pB = pB->next;
continue;
}
else
{
//最小的相比,A小 A后移
pA = pA->next;
}
}
已知递增有序的两个单链表A,B分别存储了一个集合。设计算法实现求两个...
1、首先,用for循环输入两个集合放到a、b两个数组中,如下图所示。2、然后用两个for循环和if语句来判断两个数组有没有一样的元素。如果有,进行赋值。可以根据自己的数据,来进行输入,如下图所示。3、最后用for循环进行输出,如下图所示。4、最后点击页面上方的编译运行,就能看到结果,如下图所示...
已知递增有序的两个单链表A和B分别存储一个集合,设计程序实现两个集合的...
\/\/伪代码struct node *pA = pListAHead; \/\/有序列表A struct node *pB = pListBHead; \/\/有序列表Bstruct node *pCHead = NULL; \/\/A与B交集头struct node *pCEnd = NULL; \/\/A与B交集尾while (pA != NULL && pB != NULL){ if (pA->value == pB->value) { \/\/相等,...
设有两个按元素值递增有序的顺序表A和B(单链表A和B),
设有两个按元素值递增有序的顺序表A和B(单链表A和B),编一程序讲A表和B表归并成一个新的递增有序的顺序表C(单链表C,值相同的元素均保留在C表中)。用VC++6.0设计一下程序... 设有两个按元素值递增有序的顺序表A和B(单链表A和B),编一程序讲A表和B表归并成一个新的递增有序的顺序表C(单链表C,值...
已知递增有序的单链表 A,B和C分别存储了一个集合设计算法实现 A:=A∪...
首先由于a,b,c都是递增的,所以可以利用它的单调性。在求 B∩C 时,两个指针分别指向链表头 (tb,tc) 若 b[tb]<c[tc] 那么和c[tc]相等的b集合中的值一定存在tb之后,所以一直将tb指针向后跳,直到b[tb]>=c[tc] 相反的话类似。当得到一个 b[tb]==c[tc] 时,将它加入bc中,两个...
编程实现将两个递增有序的顺序表进行合并
如果是python的话就非常简单。。。>>> a = [1,2,3,6,7,9,10,32,56]>>> b = [2,4,5,6,8,33,57]>>> x= list(set(a+b))>>> x.sort()>>> x [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 32, 33, 56, 57]>>> ...
编写函数,求两个按值递增有序的整数数组a和b,合并成一个按值递增有序...
http:\/\/zhidao.baidu.com\/s\/shareQB\/index.html?fr=android_app&share_time=1480259949000&qid=798793761&createTime=1480246863000 那个里面只要把c数组的定义放到函数参数就可以了。
数据结构的编程题,关于单链表。
1、该单链表已经是递增有序的了,那么只需在遍历这个单链表的过程中,将e与遍历到的这个节点、这个节点的下一个节点的值相比较,如果e的值大于当前节点,且e小于等于当前节点下一节点,那么将e插入到当前节点后 2、若循环起始节点为a节点,其下一节点a->next=b;则对a与b进行原地转置首先需要将b...
C语言。设有递增有序顺序表,实现其插入元素后依然有序?
从现有数组的最后一个元素开始,在下标不小于0的范围内,向前比较,若当前元素大于要插入的数,就把它后移一位。直到不需后移时,把要插入的数插入到当前位置的后一位就可以了。
设A和B是两个按元素值递增有序的单链表,试写程序将A和B归并为按按元素...
可以用 头插法来做
有序表的二分查找是不是要求数字是递增的?
不一定,但一定是有序数列,递减也行
范忠赛博: /* 链表节点 */ typedef struct Node {int data;struct Node *next; } Node;/* 合并两个升序链表为降序链表 */ Node *merge_lists(Node *a, Node *b) {Node *pa = a->next, *pb = b->next, *t; /* 新链表的头结点使用 a 的头结点 */a->next = NULL;...
闽清县13760554056: 已知两个顺序表A和B分别表示两个集合,其元素递增排列,编写一个函数求出A和B的交集要用简单的c++写啊,刚学不太会啊已知两个整数集合A和B,它们... - ?
范忠赛博:[答案] 由于问题与问题补充不一致,问题是要求交集,是找A和B的相同元素,问题补充里是求并集,强调不是归并,我按并集写的,如果是交集再稍加修改就可以了. LinkList *LinkMag(LinkList *ha, LinkList *hb)//假设ha和hb是带头结点的链表 { \x09Link *p...
闽清县13760554056: 急求!数据结构高手快来,帮我做这一题??
范忠赛博: 已知递增有序的两个单链表A、B分别表示两个集合(元素无重复) 1.求 A ∪B,并将结果存在A表,不单独分配空间 2.求A∩B,并将结果存在B表,不单独分配空间 这是我们马上要交的作业,会得帮帮我!
闽清县13760554056: 在c++题,,,设有两个按元素递增有序的单链表A和B,编一程序将A和B表归并成一个新的递增有序的单链表C - ?
范忠赛博: 与上楼差不多,但是最好是void Merger(LIST A,LIST B,LIST &C)因为这样能把C改变,不然会出现问题,C无法返回到主函数去.
闽清县13760554056: 已知两个单链表A与B分别表示两个集合,其元素类型为int且递增排列,其头结点指针分别为a,b.编写一个函数 - ?
范忠赛博: void List_Insert(List A,List B,List &C) { int i=0,j=0,k=0; while(A.elem[i]&&B.elem[j]) { if(A.elem[i] if(A.elem[i]>B.elem[j]) j++; if(A.elem[i]==B.elem[j]) { C.elem[k++]=A.elem[i]; i++; j++; } }
闽清县13760554056: 已知两个链表A和分别表示两个集合,其元素递增排列,请设计算法求出A与B的差集,并存放在A中, - ?
范忠赛博: int purge_L(LinkList &La, List Lb) { //找出有序单链表La和Lb中不同的元素,存放在La中,返回La中元素个数LNode *pa,*pb,*p,*deb;int count=0;p=La;pa = La->next;pb = Lb->next;while ( pa && pb ){if ( pa->data < pb->data ){ // 如果 pa->...
闽清县13760554056: 已知两个链表A和B分别表示两个集合,其元素递增排列.请设计算法求出A与B的交集,并存放于A链表中.求大神啊 - ?
范忠赛博: void Mix(LinkList& La, LinkList& Lb, LinkList& Lc, ) {pa=la->next;pb=lb->next;∥设工作指针pa和pb;Lc=pc=La; //用La的头结点作为Lc的头结点while(pa&&pb) if(pa->data==pb->data)∥交集并入结果表中. { pc->next=pa;pc=pa;pa=pa->next; ...
闽清县13760554056: 已知两个顺序表A和B分别表示两个集合,其元素递增排列,编写一个函数求出A和B的交集 - ?
范忠赛博: 由于问题与问题补充不一致,问题是要求交集,是找A和B的相同元素,问题补充里是求并集,强调不是归并,我按并集写的,如果是交集再稍加修改就可以了. LinkList *LinkMag(LinkList *ha, LinkList *hb)//假设ha和hb是带头结点的链表 {Link...
闽清县13760554056: 设A和B是两个单链表其表中元素递增有序试写一算法将A和B归并成一个按元素值递减有序的单链表C并要求辅助空间为O(1) - ?
范忠赛博:[答案] node *mergelink(node *p, node *q){ node *h, *r; h = (node*) malloc (sizeof(node)); h->next = NULL; r = h; while (p != NULL && q != NULL) { if (p->data data) { ...
闽清县13760554056: 已知递增有序的单链表A,B,(A,B中的元素个数分别为m,n,且A,B中都带有头结点),分别存储了一个集合?
范忠赛博: 当集合A={1, 1, 2, 3, 5} B={1, 3, 5}时,A的第一个1可以被删除、如果加上你那句话的话,第二个1不能被删除了,这就是原因所在.