체인 식 저장 선형 표 (헤드 노드 있 음)

/*
*
*    < >
*       （    ）
*/
#include <iostream>
#include <stdlib.h>
using namespace std;
typedef int ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode *next;
	
}LNode,*LinkList;//LNode      ，LinkList        

//         
int InitList(LinkList &head)
{
	head=(LinkList)malloc(sizeof(LNode));//head    ，     
	if(!head)
		return 1;
	head->next=NULL;//       
	return 0;
}

//        
void DestroyList(LinkList &head)
{
	LinkList p;
	if(head!=NULL)
		while (head->next!=NULL)
		{
			p=head->next;
			head->next=head->next->next;
			free(p);		//  p  
		}
		free(head);			//     
		head=NULL;			//     
		cout<<"        !"<<endl;
}

// head     
void ClearList(LinkList &head)
{
	LinkList p;
	if(head!=NULL)
		while (head->next!=NULL)//      ，   
		{
			p=head->next;
			head->next=head->next->next;
			free(p);
		}
		if(head->next==NULL)
			cout<<"        !"<<endl;
}

// head   ，   TRUE，    FALSE
int ListEmpty(LinkList head)
{
	if (head->next==NULL)
	{
		return 1;
	}
	else
		return 0;
}

//  head        
int ListLength(LinkList head)
{
	int num=0;
	LinkList p;
	if(head!=NULL)
		for(p=head;p->next != NULL;p=p->next)
			num++;
		return num;
}

// e  head  i       
int GetElem(LinkList head,int i,ElemType *e)
{
	int num;
	LinkList p;
	p=head;
	if(head != NULL)
		if(i>=1 && i<=ListLength(head))
			for(num=0;num<i;num++)
				p=p->next;
			*e=p->data;
		//	cout<<"  "<<i<<"          "<< *e << endl;
	return *e;
}

//  head  1  e              。
void LocateElem(LinkList head,ElemType e)
{
	int position=0;
	LinkList p=head;
	if(head!=NULL)
		while (p->next!=NULL)
		{
			position++;
			if(e==p->next->data)//         
					cout<<"   "<<e<<"           "<<position<<"  "<<endl;
			p=p->next;
		}
}

// cur_e head     ，      ，  pre_e      
void PriorElem(LinkList head,ElemType cur_e,ElemType *pre_e)
{
	LinkList p=head;
	int count=0;
	if(head!=NULL)
		while (p->next!=NULL)
		{
			count++;
			if(cur_e==p->next->data && cur_e!=head->data){			
				break;
			}
			p=p->next;
		}
		if(count != 1 && count != 0 && p->next != NULL)
		{
			cout<<cur_e<<"       ："<< p->data<<endl;
		}
		else
		{
			cout<<"         !!!!"<<endl;
		}
}

// cur_e head     ，       ，  next_e      
void NextElem(LinkList head,ElemType cur_e,ElemType *next_e)
{
	LinkList p=head;
	if(head!=NULL)
		while (p->next!=NULL)
		{
			if(cur_e==p->next->data){
				break;
			}
			p=p->next;
		}
		if (p->next!=NULL&&p->next->next!=NULL)
		{
			*next_e=p->next->next->data;
			cout<<cur_e<<"       ："<<*next_e<<endl;
		}
		else
			cout<<"          !!!!"<<endl;
}

// head  i             e，head    1
void ListInsert(LinkList &head,int i,ElemType e)
{
	LinkList p=head;
	LinkList s;
	int j=0;
	if(head!=NULL)
		while (p!=NULL && j<i-1)//         i-1   
		{
			p=p->next;
			j++;
		}
		if(!p || j>i-1)//i  1       1
		{
			cout<<"       !"<<endl;
			exit(0);
		}
		s=(LinkList)malloc(sizeof(*s));//               
		s->data=e;
		s->next=p->next;
		p->next=s;
}

//  head  i     ，  e    ，head    1
void ListDelete(LinkList &head,int i,ElemType *e)
{
	LinkList p=head;
	LinkList q;
	int j=0;
	while(p->next != NULL && j < i-1)//   i   ，  p     
	{
		p=p->next;
		j++;
	}
	if(!(p->next) || j > i-1)
	{
		cout<<"       !"<<endl;
		exit(0);
	}
	q=p->next;
	*e=q->data;
	p->next=q->next;
	cout<<"    "<<i<<"     "<< *e <<"   "<<endl;
	free(q);	//       
}

//   head         
void ListTraverse(LinkList head)
{
	LinkList p=head;
	if(head!=NULL)
	{
		p=p->next;
		cout<<"     ：";
		while (p != NULL)
		{
			cout<<p->data<<" ";
			p=p->next;
		}
		cout<<endl;
	}
}

void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)
{
	//       La,Lb          
	//  La Lb         Lc，Lc           
	InitList(La);
	InitList(Lb);
	InitList(Lc);
	int i,j;
	int a[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20};
	LinkList pa,pb,pc,pnew;
	for(i = 1 ; i < 5 ; i++)
		ListInsert(La,i,a[i-1]);
	cout<<"   La    ：";
	pnew=La->next;
	while(pnew!=NULL){
		cout<<pnew->data<<" ";
		pnew=pnew->next;
	}
	cout<<endl;
	for(j = 1 ; j < 8 ; j++)
		ListInsert(Lb,j,b[j-1]);
	cout<<"   Lb    ：";
	pnew=Lb->next;
	while(pnew!=NULL){
		cout<<pnew->data<<" ";
		pnew=pnew->next;
	}
	cout<<endl;
	pa=La->next;
	pb=Lb->next;
	pc=La;
	Lc=pc;	// La      Lc    
	while(pa!=NULL && pb!=NULL)
	{
		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);
	cout<<"      Lc ：";
	pnew=Lc->next;
	while(pnew!=NULL){
		cout<<pnew->data<<" ";
		pnew=pnew->next;
	}
	cout<<endl;
}
int main()
{
	LinkList L;
	ElemType j;
	int i;
	InitList(L);
	for(i=1,j=0;i<=10;i++)
		ListInsert(L,i,j++);
	ListTraverse(L);
/*
//  ListDelete  
	ElemType dNum;
	int dPosition;
	cout<<"          ：";
	cin>>dPosition;
	ListDelete(L,dPosition,&dNum);
	ListTraverse(L);
*/

/*
//  PriorElem   NexElem  
	ElemType cur_e,pre_e,next_e;
	cout<<"         ：";
	cin>>cur_e;
	PriorElem(L,cur_e,&pre_e);
	NextElem(L,cur_e,&next_e);
*/

/*
//  LocateElem  
	ElemType elem;
	cout<<"          ：";
	cin>>elem;
	LocateElem(L,elem);
*/

/*
//  GetElem  
	ElemType elem;
	int ePosition;
	cout<<"            ：";
	cin>>ePosition;
	GetElem(L,ePosition,&elem);
*/

/*
//  ListLength  
	int len;
	len=ListLength(L);
	cout<<"     ："<<len<<endl;
*/

/*
//  ListEmpty  
	int re =ListEmpty(L);
	cout<<re<<endl;//  0    ，1      
*/

/*
//  ClearList  
	ClearList(L);
*/

/*
//  DestroyList  
	DestroyList(L);
*/

/*
//  MergeList  
	LinkList La,Lb,Lc;
	MergeList(La,Lb,Lc);
*/

	return 0;
}