计算机科学与技术学院
实验报告
课程名称：数据结构
专业：计算机科学与技术班级：2011 级 1 班学号：201113137024
姓名：镇方权
指导老师：邱奕敏
实验一
1.实验题目
设有两个无头结点的单链表，头指针分别为ha，hb，链中有数据域data，链域next，两链表的数据都按递增序存放，现要求将hb表归到ha表中，且归并后ha仍递增序，归并中ha表中已有的数据若hb中也有，则hb中的数据不归并到ha中，hb的链表在算法中不允许破坏。
2.程序核心代码
struct LNode
{
int data;
struct LNode *next;
};
typedef struct LNode *LinkList;
LinkList Union( LinkList ha, LinkList hb )
{
LinkList head = (LNode*)malloc(sizeof(LNode));
head->next = ha;
LNode* pa,*pb,*pTmp;
pa = ha->next;
pb = hb->next;
pTmp = ha;
while ( pa&&pb ) {
if ( pa->data < pb->data ) {
pTmp = pa;
pa = pa->next;
}
else if ( pa->data > pb->data ) {
LNode* Lr = (LNode*)malloc(sizeof(LNode));
Lr->data = pb->data;
Lr->next = pa;
pTmp->next = Lr;
pTmp = Lr;
pb = pb->next;
}
else {
pTmp = pa;
pa = pa->next;
pb = pb->next;
}
}
if ( pa ) {
pTmp->next = pa;
}
else {
while ( pb ) {
LNode* Lr = (LNode*)malloc(sizeof(LNode));
Lr->data = pb->data;
pTmp->next = Lr;
pTmp = Lr;
pb = pb->next;
}
pTmp->next = NULL;
}
free(head);
return ha;
}
int ListInsert(LinkList L,int i,int e)
{
int j=0;
LinkList p=L,s;
while(p&&jp=p->next;
j++;
}
if(!p||j>i-1) return 0;
s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */ s->data=e; /* 插入L中 */
s->next=p->next;
p->next=s;
return 1;
}
int main()
{
LinkList ha,hb;
int n,i;
int data;
InitList(&ha);
printf("请输入ha中数据的个数： ");
scanf("%d",&n);
printf("请依次输入ha中的数据：\n");
for(int i = 1;i <= n;i++)
{
scanf("%d",&data);
ListInsert(ha,i,data);
}
printf("ha= ");
LinkList p = ha->next;
while(p)
{
printf("%d ",p->data);
p = p->next;
}
printf("\n");
InitList(&hb);
printf("请输入hb中数据的个数： ");
scanf("%d",&n);
printf("请依次输入hb中的数据：\n");
for(i = 1;i <= n;i++)
{
scanf("%d",&data);
ListInsert(hb,i,data);
}
printf("hb= ");
p = hb->next;
while(p)
{
printf("%d ",p->data);
p = p->next;
}
printf("\n");
printf("hb归并到ha后，新的ha=");
p = Union(ha,hb)->next;
while(p)
{
printf("%d ",p->data);
p = p->next;
}
printf("\n");
system("pause");
return 0;
}
