#include<stdio.h>
#include<malloc.h>
typedef int elemtype;/*定义数据域类型*/
typedef struct linknode/*定义结点类型*/
{
elemtype data;
struct linknode *next;
}nodetype;
nodetype *creat()/*建立单链表，由用户输入各结点data域的值，以0表示结束*/
{
elemtype d;
nodetype *h=NULL,*s,*t;
int i=1;
printf("建立一个单链表","\n");
while(1)
{
printf("输入第i个结点的data域的值：");
scanf("elemtype",&d);
if(d==0) break;/*以0表示输入结束*/
if(i==1) /*建立第一个结点*/
{
h=(nodetype*)malloc(sizeof(nodetype));
h->data=d;h->next=NULL;t=h;
}
else/*建立其他结点*/
{
s=(nodetype*)malloc(sizeof(nodetype));
s->data=d;s->next=NULL;t->next=s;
t=s;/*t始终指向生成的单链表的最后一个结点*/
}
i++;
}
return h;
}
int length(nodetype*h)/*返回单链表的长度*/
{int i=0;
nodetype *p=h;
while(p!=NULL)
{p=p->next;i++;}
return i;
}
nodetype*find(nodetype*h,int i)/*返回第i个结点的指针*/
{nodetype*p=h;
int j=1;
if(i>length||i<=0) return NULL;
else
{while(p!=NULL&&j<i)/*查找第i个结点，并由p指向该结点*/
{j++;p=p->next;}
return p;
}
}
nodetype *insert(nodetype*h,int i,elemtype x)/*在单链表head中第i个结点（i>=0)
之后插入一个data域为x的结点*/
{nodetype*p,*s;
s=(nodetype*)malloc(sizeof(nodetype));/*创建结点s*/
s->data=x;s->next=NULL;
if(i==0)/*i=0:s作为单链表的第一个结点*/
{s->next=h;h=s;}
else
{p=find(h,i);/*查找第i个结点，并由p指向该结点*/
if(p!=NULL)
{s->next=p->next;p->next=s;}
else printf("输入的i值不正确\n");
}
return h;
}
nodetype*delete(nodetype*h,int i)/*删除第i个结点*/
{nodetype*p=h,*s;
int j=1;
if(i==1)/*删除第1个结点*/
{ h=h->next;free(p);}
else
{p=find(h,i-1);/*查找第i个结点，并由p指向该结点*/
if(p!=NULL&&p->next!=NULL)
{s=p->next;/*s指向要删除的结点*/
s->next=p->next;free(s);
}
else printf("输入的i值不正确\n");
}
return h;
}
void disp(nodetype*h)/*输出由h指向的单链表的所有data域值*/
{nodetype*p=h;
printf("输出一个单链表\n");
if(p=NULL)
printf("空表");
while(p!=NULL)
{printf("p->data");
p=p->next;
}
printf("\n");
}
nodetype*order(nodetype*h)
{nodetype*head,*p=h,*q,*r,*t;
head=(nodetype*)malloc(sizeof(nodetype));/*head为哨兵*/
head->data=0;/*存放有序单链表的结点个数*/
head->next=NULL;
while(p!=NULL)
{if(head->data=0)/*有序单链表为空的情况*/
{head->next=p;
q=p->next;
p->next=NULL;
p=q;
}
else
{q=head->next;r=head;
while(q!=NULL&&p->data>q->data)/*找到r结点，将p结点插入其后*/
{ r=q;
q=q->next;
}
t=p->next;
p->next=r->next;
r->next=p;
p=t;
}
head->data++;
}
t=head;
head=head->next;
free(t);/*删除哨兵*/
return head;
}
nodetype*combine(nodetype*ha,nodetype*hb)
{
nodetype*hc=ha,*pa=ha,*pb=hb,*q,*r;
if(length(pa)!=length(pb))
{printf("两个单链表的长度不同\n");
return NULL;
}
while(pa!=NULL)
{q=pa->next;
r=pb->next;
pa->next=pb;
pb->next=q;
pa=q;
pb=r;
}
return (hc);
}
void main()
{ int i,k;elemtype x;
nodetype*head,*ha,*hb,*hc,*hd,*he;
head=creat();
disp(head);
ha=insert(head,i,x);
{scanf("%d,elemtype",&i,&x);}
hb=delete(head,k);
{scanf("%d",&k);}
hc=order(ha);
hd=order(hb);
disp(hc);
disp(hd);
he=combine(hc,hd);
disp(he);
}
急需，请高手快点帮忙.......谢谢.....
