test1.cpp

链表倒置操作演示程序

//Release Date:Apr. 1st 2007
//Author:MeteorJ
//Subject:Reverse the Link List



#include<stdio.h>
#include<stdlib.h>

typedef int Node_data;
/*
*
* link struct
*
*/
typedef struct Node
{
	Node_data data;
	struct Node *next;
}Lnode,*Lklist;

/*
*
* linklist initiation
*
*/
void init_lklist(Lklist &L) 
{
	Lklist s;
	s=new Lnode;
	s->next=NULL;
	L=s;
}

/*
*
* insert an element into the linklist
*
*/

void insert_lklist(Lklist L,int i,Node_data x)
{
	Lklist p,s;
	int j=0;
	p=L;
    s=new Lnode;
	while(p&&j<i-1)
	{
		p=p->next;
		++j;
	}
	if(!p||j>i-1)
	{
		printf("ERROR!Linklist is Empty Or the wrong location!");
		return;
	}
	s->data=x;
	s->next=p->next;
	p->next=s;
}

/*
*
* create a linklist
*
*/

void create_lklist(Lklist &L,int d)
{
	Node_data new_elem;
	int i=1;
	while(i<=d)
	{
		printf("input the new:\n");
	    scanf("%d",&new_elem);
		insert_lklist(L,i,new_elem);
		i++;
	}
}

/*
*
* get an element from the linklist
*
*/

Node_data get_lklist(Lklist L,int i)
{
	Lklist p;
	int j=1;
	Node_data e;
	p=L->next;
	while(p&&j<i)
	{
		p=p->next;
		++j;
	}
	if(p||j<=i)
	e=p->data;
	return e;
}

/*
*
* delete an element from the linklist
*
*/

void delete_lklist(Lklist L,int i){
	 Lklist p,q;
	 int j=0;	 
	 p=L;
	 while(p->next&&j<i-1){
		 p=p->next;++j;
	 }
	 if(!(p->next)||j>i-1){
		 printf("Empty Link list Or Wrong Location!\n");
		 return;
	 }
	 q=p->next;
	 p->next=q->next;
	 free(q);
 }

/*
*
* display the linklist
*
*/

void disp_lklist(Lklist L)
{
	Lklist p;
    p=L->next;
	while(p)
	{
		printf("%d -> ",p->data);
		p=p->next;
	}
	printf("\n");
}

/*
*
* Reverse the linklist method A
*
*/

void Reverse1(Lklist &L)
{
	int i=2;
	Lklist t1;
	Node_data t2;
	t1=L->next;
	while(t1->next!=NULL)
	{
		t1=t1->next;
		i++;
	}
	while(i>1)
	{
	t2=L->next->data;
	insert_lklist(L,i,t2);
	delete_lklist(L,1);
	i--;
	}
}

/*
*
* Reverse the linklist method B
*
*/
void Reverse2(Lklist &L)
{
 int k=1; 
 Lklist p1,q1;
 q1=L->next;
 
while(q1->next!=NULL)
{
	k++;
	q1=q1->next;
}
 for(int m=0;m<k-1;m++)
{ 
  p1=L->next;
  L->next=p1->next;
  p1->next=q1->next;
  q1->next=p1;
}
}



/*
*
* command menu
*
*/

void menu()
{
	printf("***********************************\n");
	printf("LinkList Reverse Test Program By MeteorJ\n");
	printf("***********************************\n");
	printf("Choose command you want:\n");
	printf("1 - Create a Link List ;\n");
	printf("2 - Reverse the Link List ;\n");
	printf("3 - Quit the Program .\n");
}	

/*
*
* main function
*
*/

void main()
{
	char inputchar;
	int run_args=1;
	Lklist L;
	init_lklist(L);
	while(run_args)
	{
	menu();
	scanf("%c",&inputchar);
	switch (inputchar)
	{
	case '1':
		create_lklist(L,5);
		disp_lklist(L);
		break;
	
	case '2':
		printf("Reverse the Link List:(method A)\n");
		Reverse1(L);
		disp_lklist(L);
		printf("Reverse the Link List again:(method B)\n");
		Reverse2(L);
		disp_lklist(L);
        break;

	case '3':
		run_args=0;
		break;
	default:
		break;
	}
	}




}