#include "stdafx.h"
#include "iostream.h"
#include  "malloc.h"


//****************************定義數(shù)據(jù)類型*********************************


typedef struct linknode//定義接點(diǎn)類型
{
	char data;
	struct linknode *next;
}nodetype;


//**************************建立單鏈表并負(fù)值*******************************
nodetype *create()
 
{
	char d;
	nodetype *h=NULL,*s,*t;
	int i=1;
	cout <<"建立單鏈表<<endl<<請(qǐng)輸入結(jié)點(diǎn)值以輸入0為輸入結(jié)束"<<endl;

	while (i)
	{
		cout <<"輸入第"<< i <<"個(gè)結(jié)點(diǎn)值 ";
		cin >>d;
		if (d=='0') 
			break;
		if (i==1)//建立第一個(gè)結(jié)點(diǎn)
		{
			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;
		}
		i++;

	}
	return h;
}

//********************************輸出數(shù)據(jù)********************************

void disp(nodetype *h)
{
	nodetype *p=h;
	cout <<"	";
	if (p==NULL)
		cout <<"空表";
	while (p!=NULL)
	{
		cout << p->data<<"	";
		p=p->next;
	}
	cout << endl;
}

//*******************************計(jì)算鏈表長度******************************

int len(nodetype *h)
{
	int i=0;
	nodetype *p=h;
	while (p!=NULL)
	{
		p=p->next;
		i++;
	}
	return i;
}

//******************************就地逆置單鏈表*****************************

nodetype *invert(nodetype *h)
{
	nodetype *p,*q,*r;
	if (len(h)<=1)
	{
		cout <<"至少為2個(gè)接點(diǎn)的鏈表"<<endl;
		return NULL;
	}
	else 
	{
		p=h;
		q=p->next;
		while (q!=NULL)
		{
			r=q->next;
			q->next=p;
			p=q;
			q=r;
		}
		h->next=NULL;
		h=p;
		return h;
	}
}

//*******************************銷毀單鏈表********************************

void dispose(nodetype *h)
{
	nodetype *pa=h, *pb;
	if (pa!=NULL)
	{
		pb=pa->next;
		if (pb==NULL)
			free(pa);
		else
		{
			while (pb!=NULL)
			{
				free(pa);
				pa=pb;
				pb=pb->next;
			}
			free(pa);
		}
	}
}