선형 표 의 단일 체인 표 학습 소결 (초학 데이터 구조 필수)

#include<iostream>
using namespace std;

#define ElemType char
#define ERROR 0
#define OK 1
typedef struct Node
{
	ElemType data;
	struct Node *next;
}Node,*LinkList;

void init_linklist(LinkList L)/*         */
{
	L=(Node*)malloc(sizeof(Node)); /*      */
	L->next=NULL;                      /*    */
}

void CreateFromHead(LinkList   L)
{ 
	Node *s;
	char 	c;
	int 	flag=1,k=0;
	while(flag)   /* flag   1，   "$" ， flag 0，    */
	{
		c=getchar();   
		if(c!='$')
		{
			s=(LinkList)malloc(sizeof(Node)); /*     s*/
			s->data=c;
			s->next=L->next;/* s      */
			L->next=s;
			if(k==0)
			{k=1;s->next=NULL;}          //       ，                     ，  k  ，      
		}
		else
			flag=0;
	}
}

void CreateFromTail(LinkList L)
{ 
	Node *r, *s;
	char c;
	int   flag =1; /*      ，   1，   "$" ，flag 0，    */
	r=L;                /*r             ，       ，        */
	while(flag)         /*         ，      s    */
	{
		c=getchar();
		if(c!='$')
		{
			s=(Node*)malloc(sizeof(Node));
			s->data=c;
			r->next=s;
			r=s;
		}
		else
		{
			flag=0;
			r->next=NULL;   /*        next     ，       */
		}
	}   
} 
ElemType Get (LinkList  L, int i)
/*         L    i   ，   (1≤i≤n)，           ; */
{  
	int j;
	Node  *p;
	p=L;
	j=0;   /*        */ 
	while ((p->next!=NULL)&&(j<i))
	{ 
		p=p->next;    /*       */
		j++;   /*          */
	}
	if(i == j)
		return p->data;   /*     i    */
	else 
		return NULL;   /*    ，i≤0 i>n */
} 
int Locate( LinkList L,ElemType key)
/*         L         key   ，            p，    NULL*/ 
{ 
	Node *p;
	int k=1;
	p=L->next;    /*           */
	while (p!=NULL)
	{
		if (p->data!=key)
			p=p->next; 
		else  
			break; /*     =key      */
		k++;
	}
	return k;
} 

int	ListLength(LinkList L)
/*         L   */
{   
	Node *p;
	int j;
	p=L->next;
	j=0;   /*          */
	while(p!=NULL)
	{	  
		p=p->next;
		j++;
	}
	return j;	/*j         */
}  

int InsList(LinkList L,int i,ElemType e)
/*         L  i       e    */
{  
	Node *pre,*s;
	int k;
	if(i<=0)return ERROR;
	pre=L;  
	k=0;                     /* " "  ，   i-1   */
	while(pre!=NULL&&k<i-1)  /*         i-1    ，  pre   i-1 */ 
	{ 
		pre=pre->next;
		k=k+1; 
	}									/*   i-1  */
	if(!pre)      /*     pre           i ，         */ 
	{ 
		printf("       !");
		return ERROR;
	}
	s=(Node*)malloc(sizeof(Node));   /*        S */
	s->data=e;                       /* e  s    */
	s->next=pre->next;				/*    ，      */
	pre->next=s;
	return OK;
}
int DelList(LinkList L,int i,ElemType *e)
/*         L    i   ，            *e */
{  
	Node *pre,*r;
	int k;
	pre=L;
	k=0;
	while(pre->next!=NULL && k<i-1)	/*       i     i-1 p   */
	{ 
		pre=pre->next; 
		k=k+1;
	}								/*   i-1   */
	if(!(pre->next))     /*  while     p->next=NULL i<1    ,               ，      i   。*/
	{
		printf("       i   !");
		return ERROR;
	}
	r=pre->next;
	pre->next=pre->next->next;    /*    ，    r*/
	*e = r->data;
	free(r);    /*               */
	printf("      !");
	return OK;
}
LinkList MergeLinkList(LinkList LA, LinkList LB)
/*         LA LB             LC*/
{  
	Node *pa,*pb;
	Node *r;
	LinkList LC;
	/* LC     。pa pb         LA LB       ,r   LC*/
	pa=LA->next;
	pb=LB->next;
	LC=LA;
	LC->next=NULL;
	r=LC;
	/*           ，               LC 。*/
	
	while(pa!=NULL && pb!=NULL)
	{
		if(pa->data <= pb->data)
		{
			r->next=pa;
			r=pa;
			pa=pa->next;
		}
		else
		{
			r->next=pb;
			r=pb;
			pb=pb->next;
		}
	}
	if(pa) /*  LA  ，  LA         LC  */
		r->next=pa;
	else	 /*    LB         LC  */
		r->next=pb;
	//	free(LB);                ，      ，        "  C  malloc free"
	
	return(LC);
}
void print(LinkList L)
{
	LinkList p=L->next;
	int i=0;
	while(p!=NULL)
	{
		cout<<p->data<<"  ";
		p=p->next;
	}
	cout<<endl;
}
int main()
{
	Node LA,LB;
	LinkList LC;
	int n;
	ElemType key;
	init_linklist(&LA);
	init_linklist(&LB);
	
	cout<<"        LB：(  $  )"<<endl;
	CreateFromTail(&LA);
	print(&LA);
	
	cout<<"        LB：(  $  )"<<endl;
	CreateFromHead(&LB);
	print(&LB);
	
	cout<<" LA            "<<endl;
	cin>>n;
	cout<<Get (&LA,n)<<endl;
	
	cout<<" LA            "<<endl;
	cin>>key;
	cout<<Locate(&LA,key)<<endl;
	
	cout<<" LA      ："<<endl;
	cout<<ListLength(&LA)<<endl;
	
	cout<<" LA     e(     e,     ElemType char  ，      9)"<<endl;
	cin>>n;
	cin>>key;
	if(InsList(&LA,n,key))
	{
		cout<<"    ！"<<endl;
		print(&LA);
	}
	else
		cout<<"    ！"<<endl;
	
	cout<<" LA     i   (    i)"<<endl;
	cin>>n;
	if(DelList(&LA,n,&key))
		cout<<"      :"<<key<<endl;
	else
		cout<<"    ！"<<endl;
	
	cout<<"  LA，LB     ："<<endl;
	LC=MergeLinkList(&LA,&LB);
	print(LC);
	return 0;
}

LinkList   merge_1(LinkList LA,LinkList LB)
{  /*                        */
	Node *p, *q;
	p=LA;
	q=LB;
	while (p->next!=LA)	p=p->next;	/*   LA   ， p   */
	while (q->next!=LB)	q=q->next;	/*   LB   ， q   */
	q->next=LA;	/*   LB     ，     LA     */
	p->next=LB->next; /*   LA    ，     LB        */
	free(LB);
	return(LA);
}
LinkList  merge_2(LinkList RA,LinkList RB)
{  /*                      */
	Node *p;
	p=RA->next; /*    RA      */
	RA->next=RB->next->next;/*  RB         RA       */
	free(RB->next);/*    RB    */
	RB->next=p;/*  RA        RB       */
    return  RB;/*           */
}

int DlinkIns(DoubleList L,int i,ElemType e)
{
	DNode  *s,*p;
	int k;
	p=L;  
	k=0;                     /* " "  ，   i-1   */
	while(p->next!=L&&k<i)  /*         i-1    ，  p   i */ 
	{ 
		p=p->next;
		k=k+1; 
	}									/*   i-1  */
	if(p->next == L)      /*     p           i ，         */ 
	{ 
		printf("       !");
		return ERROR;
	}
	s=(DNode*)malloc(sizeof(DNode));
 	if (s)
	{
		s->data=e;
		s->prior=p->prior;		
		p->prior->next=s;	
		s->next=p;			
		p->prior=s;			
		return OK;
	}
	else 
		return ERROR;
}
int	DlinkDel(DoubleList L,int i,ElemType *e)
{
	DNode  *p;
	int k;
	p=L;  
	k=0;                     /* " "  ，   i   */
	while(p->next!=L && k<i)  /*         i    ，  p   i */ 
	{ 
		p=p->next;
		k=k+1; 
	}								
	if(p->next == L)       
	{ 
		return ERROR;
	}
	else
	{
		*e=p->data;
		p->prior->next=p->next;
		p->next->prior=p->prior;
		free(p);
		return OK;
	}
}

void initial(StaticList space, int *av)
{
    int k;
	space[0].cursor=0;      /*                 0*/
	for(k=0;k<Maxsize-1;k++)
		space[k].cursor=k+1;    /*  */
	space[Maxsize-1].cursor=0;    /*    */
	*av=1;  /*           */
}
int getnode(StaticList space, int *av)
/*             ，              */
{
	int i;
	i=*av;
	*av=space[*av].cursor;
	return i;
}
void   freenode(StaticList space, int *av, int k)
/*     k            */
{
	space[k].cursor=*av;
	*av=k;
}