guofu.cpp

严崴敏的数据结构实验线形表的合并的C程序

#include<iostream.h>
#include<malloc.h>
#include<stdio.h>

#define TURE           1
#define FALSE          0
#define OK             1
#define ERROR          0
#define INFEASIBLE     -1
#define OVERFLOW       -2

#define LIST_INIT_SIZE 100 
#define LISTINCREMENT 10 

typedef int Status;


typedef struct LNode{ 
int          data;
struct LNode *next; 
}LNode, *LinkList; 

/*typedef struct {
	Link  cur;
	int  len;
	Link  head, tail;
}LinkList;*/


//初始化
Status InitList_L(LinkList &L){
	L=(LNode*)malloc(sizeof(LNode));
	if(L){
        L->data=NULL;
		L->next=NULL;
		return OK;
	}
	else
	return ERROR;
}

//销毁
Status Destroy_L(LinkList &L){
	while(L)L=NULL;
	return OK;
}

//插入元素
Status ListInsert_L(LinkList &L,int i,int e){
	LinkList s,p;
	int j;
	p=L;j=0;
	while(p&&j<i-1){p=p->next;++j;}
	if(!p||j>i-1)return ERROR;
	s=(LNode*)malloc(sizeof(LNode));
	s->data=e;s->next=p->next;
	p->next=s;
	return OK;
}

//清空表
Status ClearList_L(LinkList &L){
	while(L!=NULL){
		LinkList p;
		p=L;
		L=L->next;
		free(p);
	}
	return OK;
}

//删除元素
Status ListDelete_L(LinkList &L,int i,int &e){
	LinkList p,q;
	int j;
	p=L;j=0;
	while(p->next&&j<i-1){
		p=p->next;++j;
	}
	if(!(p->next)||j>i-1)return ERROR;
	q=p->next;p->next=q->next;
	e=q->data;
	free(q);
	return OK;
}

//打印线性表
Status PrintList_L(LinkList L){
	LinkList p;
	p=L->next;
	while(p!=NULL){
		cout<<p->data<<endl;
		p=p->next;
	}
	return OK;
}

//合并算法
Status MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
	LinkList pa,pb,pc;
	pa=La->next;pb=Lb->next;
	Lc=pc=La;
	while(pa&&pb){
		if(pa->data<=pb->data){
			pc->next=pa;pc=pa;pa=pa->next;
		}
		else{pc->next=pb;pc=pb;pb=pb->next;}
	}
	pc->next=pa?pa:pb;
	free(Lb);
	return OK;
}



void main(){
	LinkList L;
	LinkList La,Lb,Lc;
	InitList_L(L);
	InitList_L(La);
	InitList_L(Lb);

	int i,e;
	for(i=1;i<=5;i++){
		e=i*2;
	    ListInsert_L(L,i,e);
		cout<<e<<endl;
	}

	for(i=5;i>=1;i--){
	ListDelete_L(L,i,e);
	cout<<e<<endl;
	}

	ClearList_L(L);
	Destroy_L(L);
	
	cout<<"La的元素为："<<endl;
	for(i=1;i<=5;i++){
		ListInsert_L(La,i,i);
		cout<<i<<endl;	
	}
	cout<<"Lb的元素为："<<endl;
	for(i=1;i<=5;i++){
		e=2*i;
		ListInsert_L(Lb,i,e);
		cout<<e<<endl;
	}
	cout<<"lc的元素为："<<endl;
	MergeList_L(La,Lb,Lc);
    PrintList_L(Lc);
	
}