liaobiao.cpp

这是一个很经典的链表程序

#include <stdio.h>
#include <malloc.h>
#include "iostream.h"
//#include <string>
#define N 5
#define L sizeof(struct st)
	int j;
struct st
{
	long num;
// 	char name[10];
// 	int score;
	struct st *next;
};

struct st *create(void)
{
	struct st *head,*p,*last;
	int i;
	head=(struct st*) malloc(L);
	printf("input %d record \n",N);
	scanf("%d",&head->num);
	getchar();
	last=head;
	for (i=2;i<=N;i++)
	{
		p=(struct st*) malloc(L);
        scanf("%d",&p->num);
		last->next=p;
		last=last->next;

	}
	last->next=NULL;
	return head;



}

void printlist(struct st *head)
{
	struct st *p;
	printf("the linked list is :\n");
	p=head;
	while (p!=NULL)
	{
		printf("%d",p->num);
		cout<<endl;
		p=p->next;
	}
}


struct st *del(struct st *head,long key)
{
	struct st *p,*pre;
	p=head;
	while ((p->num!=key)&&(p->next!=NULL))
	{
		pre=p;
		p=p->next;

	}
	if (p->num==key)
	{
		if (p=head)
	
			head=head->next;
		else
		   pre->next=p->next;
		free(p);

		
	}
	else
		printf("num=%ld not been found!\n",key);

	return head;
}

//struct st *head, *insert;
struct st *ins(struct st *head,struct st *insert)

{
	struct st *p,*pre;
	p=head;
	if (head==NULL)
	{
		head=insert;
		insert->next=NULL;
	}
	else
	{
		while ((insert->num>p->num)&&(p->next!=NULL))
		{
			pre=p;
			p=p->next;
		}
		if (insert->num<p->num)
		{
			if (p==head)
			{
				head=insert;
			}
			else
			{
				pre->next=insert;
		    	insert->next=p;
			}
		}
		else
		{
			p->next=insert;
			insert->next=NULL;
		}
	}
	return head;
}

struct st *ReverseList(struct st *head) //链表逆序
{
	struct st *p,*q,*r;   
	p=head;   
	q=p->next;   
	while(q!=NULL)   
	{   
		r=q->next;   
		q->next=p;   
		p=q;   
		q=r;   
	}   
    
	head->next=NULL;   
	head=p;   
	return   head;   
}  


struct st *Merge(struct st *head1 , struct st *head2)
{
	if ( head1 == NULL)
		return head2 ;
	if ( head2 == NULL)
		return head1 ;
	struct st *head = NULL ;
	struct st *p1 = NULL;
	struct st *p2 = NULL;
	if ( head1->num < head2->num )
	{
		head = head1 ;
		p1 = head1->next;
		p2 = head2 ;
	}
	else
	{
		head = head2 ;
		p2 = head2->next ;
		p1 = head1 ;
	}
	struct st *pcurrent = head ;
	while ( p1 != NULL && p2 != NULL)
	{
		if ( p1->num <= p2->num )
		{
			pcurrent->next = p1 ;
			pcurrent = p1 ;
			p1 = p1->next ;
		}
		else
		{
			pcurrent->next = p2 ;
			pcurrent = p2 ;
			p2 = p2->next ;
		}
	}
	if ( p1 != NULL )
		pcurrent->next = p1 ;
	if ( p2 != NULL )
		pcurrent->next = p2 ;
	return head ;
}


struct st *MergeRecursive(struct st *head1 , struct st *head2)
{
	if ( head1 == NULL )
		return head2 ;
	if ( head2 == NULL)
		return head1 ;
	struct st *head = NULL ;
	if ( head1->num < head2->num )
	{
		head = head1 ;
		head->next = MergeRecursive(head1->next,head2);
	}
	else
	{
		head = head2 ;
		head->next = MergeRecursive(head1,head2->next);
	}
	return head ;
} 


void caidan()
{


		cout<<"新建一个链表！请选1"<<endl;
	    cout<<"再新建一个链表！请选2"<<endl;	
	    cout<<"插入一个数据到其中一个链表！请选3"<<endl;
	    cout<<"从其中一个链表中删除一个数据！请选4"<<endl;
	    cout<<"合并两个链表！请选5"<<endl;
	    cout<<"用递归的方法来合并两个链表！请选6"<<endl;
	    cout<<"退出，请选0";

	
		
	
	
}



void main()
{
	struct st *head;
	struct st *head1;
	struct st *p11;
	long key;
    int i;
	head=NULL;
	head1=NULL;

	int m;
	m=1;

	while (m)
	{
		caidan();
		cin>>i;

		switch(i)
		{
			
		case 1:
			cout<<"新建一个链表！";
			head=create();
			printlist(head);
			
			break;
		case 2:
			cout<<"再新建一个链表！";
			head1=create();
			printlist(head1);
			
			break;
		case 3:
			cout<<"插入一个数据到其中一个链表！";
			printf("插入一个数据到其中一个链表:\n");
			p11=(struct st *) malloc(L);
			scanf("%ld",&p11->num);
			head=ins(head,p11);
			printlist(head);
			
			break;
		case 4:
			cout<<"从其中一个链表中删除一个数据！";
			printf("从链表中选择要删除的数据:\n");
			scanf("%ld",&key);
			head=del(head,key);
			printlist(head);
			
			break;
		case 5:
			cout<<"逆序排列选择的链表！";
			head=ReverseList(head);//逆序排列
			printlist(head);
			
			break;
		case 6:
			cout<<"用一般的方法合并两个链表！";
			head=Merge(head,head1);//合并两个链表
			printlist(head);
			break;
		case 7:
			cout<<"用递归的方法合并两个链表！";
			
			head=MergeRecursive(head,head1);
			printlist(head);
			break;
		case 0:
			//exit(0);
			cout<<"谢谢使用！欢迎再次使用链表系统！";
			break;
			
			
			
			
	}


		if (i==0)
		{
			m=0;
		}


	}
	
    
	

  

// 	switch(i)
// 	{
// 
// 	case 1:
// 		cout<<"新建一个链表！";
//         head=create();
// 		printlist(head);
// 		
// 		break;
// 	case 2:
// 		cout<<"再新建一个链表！";
// 		head1=create();
// 	    printlist(head1);
// 		
// 		break;
// 	case 3:
// 		cout<<"插入一个数据到其中一个链表！";
//  	    printf("插入一个数据到其中一个链表:\n");
//     	p11=(struct st *) malloc(L);
//  	    scanf("%ld",&p11->num);
//  	    head=ins(head,p11);
//  	    printlist(head);
// 		
// 		break;
// 	case 4:
// 		cout<<"从其中一个链表中删除一个数据！";
//  	    printf("从链表中选择要删除的数据:\n");
//  	    scanf("%ld",&key);
//  	    head=del(head,key);
//  	    printlist(head);
// 		
// 		break;
// 	case 5:
// 		cout<<"逆序排列选择的链表！";
// 		head=ReverseList(head);//逆序排列
//     	printlist(head);
// 		
// 		break;
// 	case 6:
// 		cout<<"用一般的方法合并两个链表！";
// 		head=Merge(head,head1);//合并两个链表
//     	printlist(head);
// 		break;
// 	case 7:
// 		cout<<"用递归的方法合并两个链表！";
// 		
// 		head=MergeRecursive(head,head1);
// 	    printlist(head);
// 		break;
// 	case 0:
// 		//exit(0);
// 		cout<<"谢谢使用！欢迎再次使用链表系统！";
// 		break;
// 
// 
// 
// 		
// 	}
	

}