回 帖 发 新 帖 刷新版面

主题:虾米跪求课程设计 实现两个链表的合并....

基本功能要求:
建立两个链表A和B,链表元素个数分别为m和n个。
假设元素分别为(x1,x2,…xm),和(y1,y2, …yn)。把它们合并成一个线形表C,使得:
当m>=n时,C=x1,y1,x2,y2,…xn,yn,…,xm
当n>m时,C=y1,x1,y2,x2,…ym,xm,…,yn
输出线形表C
用直接插入排序法对C进行升序排序,生成链表D,并输出链表D。
测试数据:
(1) A表(30,41,15,12,56,80)
B表(23,56,78,23,12,33,79,90,55)
(2)A表(30,41,15,12,56,80,23,12,34)
B表(23,56,78,23,12)

回复列表 (共4个回复)

沙发

哈哈,你的和我的课程设计一样,我也做这个题目,我也发了帖子了,我现在有一个,你可以看下了……
#include<stdio.h>   //预编译命令
#include<iostream.h>
struct list//定义结构体
{
int num;
list*next;
};
list*head,*end;         //定义全局变量

list*creat()//创建链表的函数
{
list*p=NULL;
list*q=NULL;
head=NULL;
int num;
printf("Input number:\n");
scanf("%d",&num);
while(num!=0)
{
  p=new list;      //开辟空间
  p->num=num;
  if(head==NULL)
   head=p;
  else
   q->next=p;
  q=p;
  scanf("%d",&num);
}
end=q;   //将链表的结尾最后一个结点赋给end
end->next=head;  //让最后一个结点的的下个结点的地址不为空而指向头指针
return(head);
}

void print(list*head)//打印循环链表的函数
{
int k=0;
list*r=head;
do
{
  cout.width(2);
  k=k+1;
  cout<<k<<":"<<r->num<<endl;
  r=r->next;
}while(r!=head);
}

void insert(list*pHead,list*pNode)   //插入接点的函数
{
list*q,*r;
//第一种情况,链表为空
if(pHead==NULL)
{
  pHead=pNode;    //链表头指向pNode
  return;      //完成插入操作,返回
}

//第二种情况,pNode结点num的值小于链表头结点num的值
//则将pNode的值插到链表头部
if(pNode->num<=pHead->num)
{
  pNode->next=pHead;   
  pHead=pNode;    
  return;
}
//第三种情况,循环查找正确位置
r=pHead;
q=pHead->next;
while(q!=pHead)
{
  if(pNode->num>q->num)
  {
   r=q;
   q=q->next;
  }
  else
   break;
}
r->next=pNode;
pNode->next=q;
}

list*together(list*p1,list*p2)      //定义两个链表合并的函数
{
list*q,*r;
q=p2;

do
{
  r=new list;   //开辟空间
  r->num=q->num;  //将q的值赋给r
  r->next=NULL;       //让r的下一个指针的地址为空,目的是使它成为一个独立的结点
  insert(p1,r);  //调用插入结点的函数
  q=q->next;   //指针向后拨一个接点
}while(q!=p2);   //当在最后一个结点时停止循环
return(p1);    //返回头指针
}

void main()   //主函数
{
list*list1,*list2;
printf("Input list1\n");
printf("If number is 0,stop inputing\n");
printf("数据请从小到大输入\n");
list1=creat();    //调用创建链表的函数
print(list1);    //打印第一个链表


printf("Input list2\n");
printf("If number is 0,stop inputing\n");
printf("数据请从小到大输入\n");
list2=creat();   //调用创建链表的函数
print(list2);   //打印第二个循环链表

head=together(list1,list2);    //调用合并两个链表的函数
printf("The new list is:\n");
print(head);       //打印最后结果
}

板凳


 跟上面的问题题目一样,但要求两个链表中的元素为[size=4]字符[color=808000][/color][color=800000]型[/color],[/size]该怎么做呀,还望大虾指教,谢谢

3 楼


啥子哟!运行不出来!一大堆错误!
唬人啊

4 楼


我有一个但不是交叉合并!
只能连接到尾部!绝对可运行!

#include <stdio.h>
#include <malloc.h>
#define null 0
#define len sizeof(struct list)
struct list
{int data;
struct list * next;
};
int n;
struct list * creat(void)
{struct list *head;
struct list * p1,* p2;
n=0;
p1=p2=(struct list *)malloc (len);
scanf("%d",&p1->data);
head=null;
while(p1->data!=0)
{n=n+1;
if(n==1)
head=p1;
else
p2->next=p1;
p2=p1;
p1=(struct list *)malloc (len);
scanf("%d",&p1->data);
}
p2->next=null;
return(head);
}

 struct list * join_list(struct list *a_head,struct list *b_head)
{
  struct list *p;
  p=a_head;
  if(a_head==NULL)
     printf("NULL");
   else
      { while(p->next!=NULL)
        {
        p=p->next;
         }
    p->next=b_head;
    return a_head;
        }

}
  void print (struct list * head)
{struct list *p;
printf("the new list is:\n");
p=head;
if(head!=null)
do
{
printf("%d\t",p->data);
p=p->next;
}while(p!=null);
}
 main()
 {
     int len1=0,len2=0;

     struct list *head1,*head2,  *pa,*pb;

     printf("input list1:\n");
 head1=creat();
 printf("input list2:\n");
 head2=creat();
 pa=head1;
 pb=head2;
 while(pa->next!=null)
 {
     len1++;
 pa=pa->next;
 }
 while(pb->next!=null)
 {
     len2++;
     pb=pb->next;
 }

 if(len1>len2)
{
join_list(head1,head2);
 print(head1);
 }
 else
 {
join_list(head2,head1);
 print(head2);
 }

 }合并算法改一下就可以了!
































我来回复

您尚未登录,请登录后再回复。点此登录或注册