链表合并(菜鸟求救)
已有a、b两个链表,每个链表中的结点包括学号、成绩。要求把两个链表合并,按学号升序排列。
关于写的合并的那个函数 感觉很稀烂 不知道能不能简化一下
基本思路就是：若链表a是有序的 然后遍历a 将b中的数于a中的数一一比较了 分了三种情况：
1.链表b的数小于a的第一个结点 2.遍历a后 链表b的数 比所有的数都大 3.b中数插入a中间
不知道这样对么。有什么好的方法 求高手指点 本人刚学习链表这一块 谢谢 了
struct student *sort(struct student *heada,struct student *headb)
{
struct student *pa1,*pa2,*pb1,*pb2;
pa1=pa2=heada;
pb1=pb2=headb;
while (pa2->next!=NULL&&pb2->next!=NULL) // 遍历链表a
{
if (pb1->num<pa1->num) //小于第一个结点num
{
pb2->next=headb;
headb=heada; //将头指针a赋给头指针b
pb2->next=pa2->next;
}
if (pb1->num>pa1->num)
{
pb2->next=pb1;
pa2->next=headb; //尾结点
}
if (pb1->num>pa2->num&&pb1->num<pa1->num)
{
pa2->next=pb2;
pb2->next=pa1;
pb1=headb=pb2;
}
}
return heada;
}
[解决办法]
#include <iostream>#include <stdlib.h>using namespace std;typedef struct Node{ int data; struct Node *next;}node;typedef struct Node *linklist;void creat(linklist *L,int n)//去掉你的void *{ linklist r,p; *L=r=(linklist)malloc(sizeof(node)); int i;//不要的变量都删除掉 data for(i=0;i<n;i++) { p=(node *)malloc(sizeof(node)); cout<<"please input one number:"<<endl; cin>>p->data; r->next=p; r=p; } cout<<"the linklist is full"<<endl; r->next=NULL;}void visit(linklist L){ linklist p=L->next; cout<<"linklist's data: \n"; while(p) { cout<<p->data<<" "; p=p->next; } cout<<endl;}void mergelinklist(linklist &L1,linklist &L2,linklist &L3){ linklist p1,p2,p3; p1=L1->next; //修改处 p2=L2->next; // L3=p3=L1; while(p3->next ) { p3=p3->next; //遍历到末尾; } while(p2) { linklist temp=(node *)malloc(sizeof(node)); temp->data=p2->data; temp->next=NULL;//插入节点 p3->next=temp;// p3=temp; p2=p2->next; }// /*排序好了*/ linklist p11,p33; int temp; for(p33=L3->next;p33 != NULL; p33=p33->next) { for(p11=p33->next;p11 != NULL;p11=p11->next) { if(p33->data > p11->data) { temp=p11->data; p11->data=p33->data; p33->data=temp; } } }}int main(){ linklist L1,L2,L3; creat(&L1,3); creat(&L2,3); visit(L1); visit(L2); cout<<"合并后： \n"; mergelinklist(L1,L2,L3); visit(L3); return 0;}
[解决办法]
#include <stdio.h>#include <stdlib.h>#include <malloc.h> //#define NULL 0 没有必要struct student{ int num; //学号 int score; //分数 struct student *next; //下一结点}; struct student *creat(void){ struct student *p1,*p2,*head; int n=0; p1 = p2 = (struct student *)malloc(sizeof(struct student)); //创建头结点 head= NULL; printf("\n请输入学号与分数，以0结束输入!\n");//最好要有输入提示 scanf("%d,%d",&p1->num,&p1->score); while (p1->num!=0) //输入0 结束 { n=n+1; if(n==1) //判断头结点 head=p1; else p2->next=p1; p2=p1; //保存前驱结点 p1=(struct student *)malloc(sizeof(struct student)); //开辟新的结点 scanf("%d,%d",&p1->num,&p1->score); } p2->next=NULL; return head;}struct student *insert(struct student *head,struct student *pi) //插入结点{ struct student *pf,*pb; pb=pf=head; if(head==NULL) //空链表 插入 { head=pi; head->next=NULL; return head; } while((pb->next!=NULL)&&(pb->num<pi->num)) //比较大小 按顺序插入 { pf=pb; pb=pb->next; } if(pb->num>=pi->num) //找到了所要插入的位置 （从小到大） { if(pb==head) //插入到 链表 的 头 { head=pi; pi->next=head; } else { //插入到普通位置 pf->next=pi; pi->next=pb; } } else //插入到链表的 尾 { pb->next=pi; pi->next=NULL; } return head;}struct student *sort(struct student *heada,struct student *headb)// 若链表a是有序的 插入排序{ struct student *pb,*pb1; pb = pb1 = headb; if((heada == NULL)&&(headb != NULL)) { heada = headb; } else if((headb == NULL)&&(heada != NULL)) { headb = heada; } else { while(pb1!= NULL) //控制listb,将listb中的结点依次插入lista中 { pb = pb1; pb1 = pb1->next; heada=insert(heada,pb); } } return heada;}void print(struct student *head){ struct student *p; p=head; while(p!=NULL) { printf("%d,%d\n",p->num,p->score); p=p->next; }}int main(int argc,char *argv[]){ struct student *heada,*headb,*pb; printf("input the list a:"); heada=creat(); //创建链表a print(heada); printf("\ninput the list b:"); headb=creat(); //创建链表b print(headb); printf("\nthe new list :\n"); pb = sort(heada,headb); //升序合并链表a和b print(pb); }