数据结构-线性表的单向链表的定义和实现

#include<iostream>
#include<stdlib.h> 
typedef int Elemtype;
using namespace std;

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;
//创建单向链表

void create_list(LNode *p)    //创建尾插入链表
{
	int i,n;
	LNode *s;
	cout<<"input the length of the list";
	cin>>n;
	for(i=1;i<=n;i++)
	{
		s=new LNode;
		cout<<"element:";
		cin>>s->data;
		p->next=s;
		p=s;
	}
} 

LNode *create_list(int n)   //创建头插入链表
{
	int i;
	LNode *L,*p;
	L=new LNode;
	L->next=NULL;
	for(i=n;i>=1;i--)
	{
		p=new LNode;
		cout<<"element:";
		cin>>p->data;
		p->next=L->next;
		L->next=p;
	}
	return (L);
}

void out_list(LNode *q)   //输出链表
{
	q=q->next;
	if(q==NULL)
	cout<<"Empty List!"<<endl;
	else
	{
		while(q!=NULL)
		{
			cout<<q->data;
			q=q->next;
		}
	}
	cout<<endl;
}

Elemtype GetElem(LNode *L,int i)   //查找线性链表第i个元素的值
{
	int j;
	LNode *p;
	p=L->next;
	j=1;
	while(p&&j<i)
	{
		p=p->next;
		j++;
	}
	if(!p||j>i)
	return (-1);
	else
	return (p->data);
}

void insert_L(LNode *L,int i,Elemtype e) //在带头结点的单向链表中第i个位置插入元素e
{
	LNode *p,*s;
	int j;
	p=L;
	j=1;
	while(p!=NULL&&j<i)
	{
		p=p->next;
		j++;
	}
	if(p==NULL||j>i)
	cout<<"ERROR!"<<endl;
	else
	{
		s=new LNode;
		s->data=e;
		s->next=p->next;  //
		p->next=s;        //如果这两句交换就不行
	}
}

Elemtype delete_list(LNode *L,int i)  //删除带头结点的单向链表的第i个元素
{
	LNode *p,*q;
	int j;
	Elemtype e;
	p=L;
	while(p->next!=NULL&&j<i)
	{
		p=p->next;
		j++;
	}
	if(p->next==NULL||j>i)
	cout<<"ERROR!"<<endl;
	else
	{
		q=p->next;
		e=q->data;
		p->next=q->next;
		delete(q);    //释放动态开辟空间
		return(e);
	}
}

void listdelete_L(LNode *L,Elemtype x) //在单向链表中查找x的值，并且删除它（假设链表元素值不重复）
{
	LNode *p,*q;
	p=L;
	while(p->next&&p->next->data!=x)  //找x的前驱
		p=p->next;
	if(!p->next)
	cout<<"Not find element"<<endl;
	else
	{
		q=p->next;
		p->next=q->next;
		delete(q);
	} 
}

LNode *merge_list(LNode *La,LNode *Lb)  //合并链表
{
	LNode *Lc,*pa,*pb,*pc;
	Lc=La;
	pc=La;
	pa=La->next;
	pb=Lb->next;
	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;
		}
	}
	if(pa!=NULL)
	pc->next=pa;
	else
	pc->next=pb;
	delete(Lb);        //释放动态开辟空间
	return(Lc);
}

//查找 删除 合并等对单向链表的操作，指针必须指向所找结点的前一个结点

int main()
{
//	LNode *p,s;
//	p=(LNode*)malloc(sizeof(LNode));
//	free(p);
//	LNode *head;             
//	head=new LNode;          
//	head->next=NULL;		 
//	create_list(head);
	
//	LNode *head;
//	head=create_list(5);
//	out_list(head);   
//	delete(head);
    return 0;
}