算法与数据结构之带头结点的单链表

单链表优缺点

链表是非随机存取的存储结构，和顺序表相比，链表存储结构在实现插入、删除的操作时，不需要移动大量数据元素(但不容易实现随机存取线性表的第 i 个数据元素的操作)。所以，链表适用于经常需要进行插入和删除操作的线性表，如飞机航班的乘客表等

单链表的定义

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

typedef struct Node
{
	int data;	//数据域
	struct Node *next;	//指针域
}NODE,*PNODE;

基本操作的实现

单链表的创建

单链表的创建分为两种，第一种在表头插入数据，第二种在表尾插入数据

在表头插入数据

PNODE Create1()
{
	int i,n;
	PNODE pNew,pHead=NULL;
	pHead=(PNODE)malloc(sizeof(NODE));
	if(NULL==pHead)
		exit(-1);
	pHead->next=NULL;	//先建立一个带头结点的单链表
	printf("请输入数据元素的个数：");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		pNew=(PNODE)malloc(sizeof(NODE));
		if(NULL==pNew)
			exit(-1);
		printf("请输入第%d个元素的值：",i+1);
		scanf("%d",&pNew->data);
		pNew->next=pHead->next;
		pHead->next=pNew;
	}
	return pHead;
}

在表尾插入数据

PNODE Create2()
{
	int i,n;
	PNODE pHead,pTail,pNew;
	pHead=(PNODE)malloc(sizeof(NODE));
	if(NULL==pHead)
		exit(-1);
	pHead->next=NULL;	//生成头结点
	pTail=pHead;
	printf("请输入数据元素的个数：");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		pNew=(PNODE)malloc(sizeof(NODE));
		if(NULL==pNew)
			exit(-1);
		printf("请输入第%d个元素的值：",i+1);
		scanf("%d",&pNew->data);
		pTail->next=pNew;
		pTail=pTail->next;
		pNew->next=NULL;
	}
	return pHead;
}

销毁单链表

销毁单链表指的是破除各个结点之间的关系，并且释放各个结点(包括头结点)内存空间

void Destroy(PNODE pHead)
{	//销毁pHead指向的单链表：头结点也不存在只剩一个头指针，
	//且头指针为NULL
	PNODE p;
	while(pHead!=NULL)
	{
		p=pHead->next;
		free(pHead);
		pHead=p;
	}
}

置空单链表

注意置空和销毁的区别，销毁到最后什么也没有，但是置空在最后会剩一个头指针和头结点

void Clear(PNODE pHead)
{	//将pHead指向的单链表置为空表，和初始状态一样，
	//只剩一个头指针和一个头结点，
	//且头结点的指针域为NULL
	PNODE p,q;
	p=pHead->next;//p指向第一个节点
	while(p!=NULL)
	{
		q=p->next;
		free(p);
		p=q;
	}
	pHead->next=NULL;
}

判断链表是否为空

bool Empty(PNODE pHead)
{
	if(pHead->next==NULL)
		return true;
	else
		return false;
}

返回单链表中元素个数

int	Length(PNODE pHead)
{
	int count=0;//定义临时变量，存储单链表元素个数
	PNODE p=pHead->next;
	while(p!=NULL)
	{
		count++;
		p=p->next;
	}
	return count;
}

返回第某个元素的值

将第i个元素的值赋给e

bool Get(PNODE pHead,int i,int *e)
{
	int k=1;
	PNODE p=pHead->next;
	while(k<i&&p!=NULL)
	{
		k++;
		p=p->next;
	}
	if(k>i||p==NULL)
		return false;
	*e=p->data;
	return true;
}

求某个元素的前驱元素

求cur_e的前驱元素，用pre_e保存

bool Prior(PNODE pHead,int cur_e,int *pre_e)
{
	PNODE p=pHead->next,q;//p指向第一个节点
	while(p->next)	//p所指节点有后继
	{
		q=p->next;	//q为p的后继
		if(q->data==cur_e)
		{
			*pre_e=p->data;
			return true;
		}
		p=q;	//p向后移
	}
	return false;
}

求某个元素的后继元素

求cur_e的后继元素，用next_e保存

bool Next(PNODE pHead,int cur_e,int *next_e)
{
	PNODE p=pHead->next;//p指向第一个节点
	while(p->next)	//p所指节点有后继
	{
		if(p->data==cur_e)
		{
			*next_e=p->next->data;
			return true;
		}
		p=p->next;	//p向后移
	}
	return false;
}

在第某个元素前面插入元素

在第i个元素前面插入元素e

bool Insert(PNODE pHead,int i,int e)
{
	int k=0;
	PNODE p=pHead,pNew;
	while(k<i-1&&p!=NULL)
	{
		k++;
		p=p->next;
	}
	if(NULL==p||k>i-1)
		return false;
	pNew=(PNODE)malloc(sizeof(NODE));
	if(pNew==NULL)
		exit(-1);
	pNew->data=e;
	pNew->next=p->next;
	p->next=pNew;
	return true;
}

删除第某个元素

删除单链表第i个元素，并用e保存

bool Delete(PNODE pHead,int i,int *e)
{
	int k=0;
	PNODE p=pHead,q;
	while(k<i-1&&p->next!=NULL)
	{
		k++;
		p=p->next;
	}
	if(k>i-1||p->next==NULL)
		return false;
	q=p->next; // 删除并释放结点
	p->next=q->next;
	*e=q->data;
	free(q);
	return true;
}

遍历链表中的所有元素

void Traverse(PNODE pHead)
{
	PNODE p=pHead->next;
	while(p!=NULL)
	{
		printf("%d	",p->data);
		p=p->next;
	}
	printf("\n");
}

对链表中的元素进行升序排序

void Sort(PNODE pHead)
{
	int i,j,temp;
	PNODE p,q;
	for(i=0,p=pHead->next;i<Length(pHead)-1;i++,p=p->next)
	{
		for(j=i+1,q=p->next;j<Length(pHead);j++,q=q->next)
		{
			if(p->data>q->data)
			{
				temp=p->data;
				p->data=q->data;
				q->data=temp;
			}
		}
	}
}

归并两个有序单链表

void MergeList(PNODE La,PNODE Lb,PNODE Lc)
{
	PNODE pa=La->next,pb=Lb->next,pc=Lc=La;
	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);
	Lb=NULL;
}