单向链表的简单实现

链表有单项链表和双向链表，在这里只讲单项链表的一些功能实现，包括链表的初始化，尾插、尾删，头插、头删，指定结点位置插入元素，删除一个x元素和所有x元素，以及删除指定位置的结点，冒泡排序等

首先定义出链表的结构，包括结点的定义和函数的声明

LinkList.h

#ifndef _LINKLIST_H__
#define _LINKLIST_H__


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

typedef int DataType;
typedef struct LinkNode		//定义一个结点
{
	struct LinkNode *next;
	DataType data;
}LinkNode,*pLinkNode;
typedef struct LinkList		//定义链表
{
	LinkNode *pHead;
}LinkList,*pLinkList; 

void Init(pLinkList pList);	//初始化
void Destory(pLinkList pList);	//销毁
void Print(pLinkList pList);	//输出
void PushBack(pLinkList pList,DataType x);	//尾插
void PopBack(pLinkList pList);	//尾删
void PushFront(pLinkList pList,DataType x);	//头插
void PopFront(pLinkList pList);	//头删
pLinkNode Find(pLinkList pList,DataType x);	//公共查找函数
void Insert(pLinkList pList,pLinkNode pos,DataType x);	//指定结点位置插入
void Remove(pLinkList pList,DataType x);	//删除一个X元素
void RemoveAll(pLinkList pList,DataType x);	//删除所有X元素
void Erase(pLinkList pList,pLinkNode pos);	//删除指定位置的结点
void BubbleSort(pLinkList pList);	//冒泡排序

#endif //_LINKLIST_H__

接下来就是各函数的实现部分：

@初始化:

只需将函数的头指针置为空

void Init(pLinkList pList)	//初始化
{
	assert(pList);
	pList->pHead = NULL;
}

@尾插：

首先得创建一个新结点，然后找到最后一个结点，将最后一个节点的next指针指向新结点

void PushBack(pLinkList pList,DataType x)	//尾插
{
	pLinkNode cur = NULL;
	pLinkNode newnode = NULL;
	assert(pList);
	cur = pList->pHead;
	newnode = BuyNode(x);
	//没有结点
	if(NULL == pList->pHead)
	{
		pList->pHead = newnode;
		newnode->next = NULL;
		return ;
	}
	//有一个或以上的结点
	while(cur->next)
	{
		cur = cur->next;
	}
	cur->next = newnode;
	newnode->next = NULL;
}

@尾删：

1.链表为空时不操作；2.链表不为空的情况下找到最后一个结点，将其free掉并将前一个结点的next指针置为空

void PopBack(pLinkList pList)	//尾删
{
	pLinkNode cur = NULL;
	pLinkNode prev = NULL;
	assert(pList);
	//没有结点
	if(NULL == pList->pHead)
	{
		printf("LinList is empty!\n");
		return ;
	}
	//有结点
	cur = pList->pHead;
	while(cur->next)
	{
		 prev = cur;
		 cur = cur->next;
	}
	free(cur);
	cur = NULL;
	prev->next = NULL;
}

@头插：

1.链表如果为空，将pHead指向新创建的结点；2.如果不为空，将pHead指向新创建的结点并将新结点的next指针指向原链表的第一个结点。如图：

@头删：

1.链表为空时不操作；2.链表不为空时，将pHead指向第二个结点并将第一个结点free掉

void PopFront(pLinkList pList)	//头删
{
	pLinkNode cur = NULL;
	pLinkNode del = NULL;
	assert(pList);
	//无节点
	if(NULL == pList->pHead)
	{
		printf("LinkList is empty!\n");
		return ;
	}
		return ;
	//有一个或以上结点
	cur = pList->pHead;
	del = cur;
	cur = cur->next;
	free(del);
	del = NULL;
	pList->pHead = cur;
}

@指定结点位置插入新元素：

1.链表为空的情况下不操作；2.链表只有一个结点并且在该结点位置前插入；3.链表有多个结点并找到指定位置插入

void Insert(pLinkList pList,pLinkNode pos,DataType x)	//指定结点位置插入
{
	pLinkNode cur = NULL;
	pLinkNode prev = NULL;
	pLinkNode newnode =	NULL;
	assert(pList);
	newnode = BuyNode(x);
	//无结点时
	if(NULL == pList->pHead)
	{
		pList->pHead = newnode;
		newnode->next = NULL;
		return ;
	}
	//有一个结点并且在该结点前插入
	if(pList->pHead == pos)
	{
		PushFront(pList,x);
		return ;
	}
	//有一个以上结点
	cur = pList->pHead;
	while(cur != pos)
	{
		prev = cur;
		cur = cur->next;
	}
	prev->next = newnode;
	newnode->next = cur;
}

@删除一个指定元素x：

1.空链表的情况下不操作；2.有一个结点时：判断该节点是不是要删除的元素；3.有多个结点时：查找要删除的元素，然后删除

void Remove(pLinkList pList,DataType x)	//删除一个X元素
{
	pLinkNode cur = NULL;
	pLinkNode prev = NULL;
	pLinkNode del = NULL;
	assert(pList);
	cur = pList->pHead;
	prev = pList->pHead;
	del = Find(pList,x);
	//无结点时
	if(NULL == pList->pHead)
	{
		printf("LinkList is empty!\n");
		return ;
	}
	//只有一个结点时
	if(NULL == cur->next)
	{
		if(cur->data == x)//该结点元素就是要删除的元素
		{
			free(cur);
			cur = NULL;
			pList->pHead = NULL;
			return ;
		}
	}
	//有多个结点时
	else
	{
		while(cur)
		{
			if(cur->data == x)		//第一个结点就是要删除的元素
			{
				del = cur;
				pList->pHead = cur->next;
				free(del);
				del = NULL;
				return ;
			}
			prev = cur;
			cur = cur->next;		//第二个结点开始，里边有需要删除的元素
			while(cur)
			{
				
				if(cur->data == x)
				{
					prev->next = cur->next;
					free(cur);
					cur = NULL;
					return ;
				}
				prev = cur;
				cur = cur->next;
			}
		}
	}
}

@删除所有指定元素x：

1.链表为空时不操作；2.有一个结点时：判断该结点是不是要删除的元素x；3.有多个结点时：首先判断第一个结点是不是要删除的元素x，如果是，删除并继续向后寻找，直到遍历完整个链表；如果不是，就从第二个结点开始遍历

void RemoveAll(pLinkList pList,DataType x)	//删除所有X元素
{
	pLinkNode prev = NULL;
	pLinkNode cur = NULL;
	assert(pList);
	//空链表
	if(NULL == pList->pHead)
	{
		printf("LinkList is empty!\n");
		return ;
	}
	cur = pList->pHead;
	//链表有一个结点
	if(NULL == cur->next)
	{
		if(cur->data == x)//并且该结点元素就是要删除的元素
		{
			free(cur);
			cur = NULL;
			pList->pHead = NULL;
			return ;
		}
	}
	//链表有多个结点
	cur = cur->next;
	prev = pList->pHead;
	while(cur)
	{
		if(prev->data == x)//第一个结点是要删除的元素x
		{
			pList->pHead = prev->next;
			free(prev);
			prev = NULL;
		}
		if(cur->data == x)//要删除的元素存在于第一个结点之后
		{
			prev->next = cur->next;
			free(cur);
			cur = NULL;
			cur = prev;
		}
		prev = cur;
		cur = cur->next;
	}
}

@删除指定位置的结点：

1.空链表时不操作；2.有一个结点时：判断该节点是不是要删除的结点pos；3.有多个结点时：判断第一个结点是不是要删除的结点，如果是，就将第一个结点删除并直接返回；如果不是，应继续遍历此链表知道找到要删除的结点

void Erase(pLinkList pList,pLinkNode pos)	//删除指定位置的结点
{
	pLinkNode cur = NULL;
	pLinkNode prev = NULL;
	assert(pList);
	//空链表
	if(NULL == pList->pHead)
	{
		printf("LinkList is empty!\n");
		return ;
	}
	cur = pList->pHead;
	//一个节点
	if(NULL == cur->next)
	{
		if(cur == pos)//判断这个结点是不是要删除的结点
		{
			free(cur);
			cur = NULL;
			pList->pHead = NULL;
		}
		return ;
	}
	//第一个结点就是要删除的结点
	if(pos == cur)
	{
		free(cur);
		cur = NULL;
		pList->pHead = NULL;
	}
	//链表有多个结点
	cur = cur->next;
	prev = pList->pHead;
	while(cur)
	{
		if(cur == pos)
		{
			prev->next = cur->next;
			free(cur);
			return ;
		}
		prev = cur;
		cur = cur->next;
	}
}

@排序（此处用冒泡排序）：

1.链表为空或者链表只有一个结点时：不需要排序；

2.排序时应定义一个尾指针来控制循环的次数

void BubbleSort(pLinkList pList)	//冒泡排序
{
	pLinkNode tail = NULL;
	pLinkNode cur = NULL;
	assert(pList);
	if((pList->pHead == NULL)||(pList->pHead->next == NULL))
	{
		printf("LinkList do not need to sort!\n");
		return ;
	}
	cur = pList->pHead;
	while(cur != tail)
	{
		while(cur->next != tail)
		{
			if(cur->data < cur->next->data)
			{
				DataType tmp = cur->data;
				cur->data = cur->next->data;
				cur->next->data = tmp;
			}
			cur = cur->next;
		}
		tail = cur;
		cur = pList->pHead;
	}
}

由于在实现某些函数时要创建一个新结点或者寻找一个结点位置，因此这里可以写两个函数来实现。 以下是所有函数的实现：

LinkList.c

#include"LinkList.h"

void Init(pLinkList pList)	//初始化
{
	assert(pList);
	pList->pHead = NULL;
}
void Destory(pLinkList pList)	//销毁
{
	pLinkNode cur = NULL;
	pLinkNode del = NULL;
	assert(pList);
	cur = pList->pHead;
	if(NULL == pList->pHead)//空链表
		return ;
	while(cur)		//有一个或以上结点
	{
		del = cur;
		cur = cur->next;
		free(del);
		del = NULL;
	}
	pList->pHead = NULL;
}
void Print(pLinkList pList)	//输出
{
	pLinkNode cur = NULL;
	assert(pList);
	cur = pList->pHead;
	while(cur)
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	printf("over!\n");
}
pLinkNode BuyNode(DataType x)//创建一个新结点
{
	pLinkNode NewNode = NULL;
	NewNode = (pLinkNode)malloc(sizeof(LinkNode));
	if(NULL == NewNode)
	{
		printf("out of memory!\n");
		exit(EXIT_FAILURE);
	}
	NewNode->data = x;
	return NewNode;
}
void PushBack(pLinkList pList,DataType x)	//尾插
{
	pLinkNode cur = NULL;
	pLinkNode newnode = NULL;
	assert(pList);
	cur = pList->pHead;
	newnode = BuyNode(x);
	//没有结点
	if(NULL == pList->pHead)
	{
		pList->pHead = newnode;
		newnode->next = NULL;
		return ;
	}
	//有一个或以上的结点
	while(cur->next)
	{
		cur = cur->next;
	}
	cur->next = newnode;
	newnode->next = NULL;
}
void PopBack(pLinkList pList)	//尾删
{
	pLinkNode cur = NULL;
	pLinkNode prev = NULL;
	assert(pList);
	//没有结点
	if(NULL == pList->pHead)
	{
		printf("LinList is empty!\n");
		return ;
	}
	//有结点
	cur = pList->pHead;
	while(cur->next)
	{
		 prev = cur;
		 cur = cur->next;
	}
	free(cur);
	cur = NULL;
	prev->next = NULL;
}
void PushFront(pLinkList pList,DataType x)	//头插
{
	pLinkNode newnode = NULL;
	pLinkNode cur = NULL;
	assert(pList);
	newnode = BuyNode(x);
	//没有结点
	if(NULL == pList->pHead)
	{
		pList->pHead = newnode;
		newnode->next = NULL;
		return ;
	}
	//有一个或以上结点
	cur = pList->pHead;
	pList->pHead = newnode;
	newnode->next = cur;
}
void PopFront(pLinkList pList)	//头删
{
	pLinkNode cur = NULL;
	pLinkNode del = NULL;
	assert(pList);
	//无节点
	if(NULL == pList->pHead)
	{
		printf("LinkList is empty!\n");
		return ;
	}
		return ;
	//有一个或以上结点
	cur = pList->pHead;
	del = cur;
	cur = cur->next;
	free(del);
	del = NULL;
	pList->pHead = cur;
}
pLinkNode Find(pLinkList pList,DataType x)	//公共查找函数
{
	pLinkNode cur = NULL;
	assert(pList);
	if(NULL == pList->pHead)
	{
		printf("LinkList is empty!\n");
		return pList->pHead;
	}
	cur = pList->pHead;
	while(cur)
	{
		if(cur->data == x)
			return cur;
		cur = cur->next;
	}
}
void Insert(pLinkList pList,pLinkNode pos,DataType x)	//指定结点位置插入
{
	pLinkNode cur = NULL;
	pLinkNode prev = NULL;
	pLinkNode newnode =	NULL;
	assert(pList);
	newnode = BuyNode(x);
	//无结点时
	if(NULL == pList->pHead)
	{
		pList->pHead = newnode;
		newnode->next = NULL;
		return ;
	}
	//有一个结点并且在该结点前插入
	if(pList->pHead == pos)
	{
		PushFront(pList,x);
		return ;
	}
	//有一个以上结点
	cur = pList->pHead;
	while(cur != pos)
	{
		prev = cur;
		cur = cur->next;
	}
	prev->next = newnode;
	newnode->next = cur;
}
void Remove(pLinkList pList,DataType x)	//删除一个X元素
{
	pLinkNode cur = NULL;
	pLinkNode prev = NULL;
	pLinkNode del = NULL;
	assert(pList);
	cur = pList->pHead;
	prev = pList->pHead;
	del = Find(pList,x);
	//无结点时
	if(NULL == pList->pHead)
	{
		printf("LinkList is empty!\n");
		return ;
	}
	//只有一个结点时
	if(NULL == cur->next)
	{
		if(cur->data == x)//该结点元素就是要删除的元素
		{
			free(cur);
			cur = NULL;
			pList->pHead = NULL;
			return ;
		}
	}
	//有多个结点时
	else
	{
		while(cur)
		{
			if(cur->data == x)		//第一个结点就是要删除的元素
			{
				del = cur;
				pList->pHead = cur->next;
				free(del);
				del = NULL;
				return ;
			}
			prev = cur;
			cur = cur->next;		//第二个结点开始，里边有需要删除的元素
			while(cur)
			{
				
				if(cur->data == x)
				{
					prev->next = cur->next;
					free(cur);
					cur = NULL;
					return ;
				}
				prev = cur;
				cur = cur->next;
			}
		}
	}
}
void RemoveAll(pLinkList pList,DataType x)	//删除所有X元素
{
	pLinkNode prev = NULL;
	pLinkNode cur = NULL;
	assert(pList);
	//空链表
	if(NULL == pList->pHead)
	{
		printf("LinkList is empty!\n");
		return ;
	}
	cur = pList->pHead;
	//链表有一个结点
	if(NULL == cur->next)
	{
		if(cur->data == x)//并且该结点元素就是要删除的元素
		{
			free(cur);
			cur = NULL;
			pList->pHead = NULL;
			return ;
		}
	}
	//链表有多个结点
	cur = cur->next;
	prev = pList->pHead;
	while(cur)
	{
		if(prev->data == x)//第一个结点是要删除的元素x
		{
			pList->pHead = prev->next;
			free(prev);
			prev = NULL;
		}
		if(cur->data == x)//要删除的元素存在于第一个结点之后
		{
			prev->next = cur->next;
			free(cur);
			cur = NULL;
			cur = prev;
		}
		prev = cur;
		cur = cur->next;
	}
}
void Erase(pLinkList pList,pLinkNode pos)	//删除指定位置的结点
{
	pLinkNode cur = NULL;
	pLinkNode prev = NULL;
	assert(pList);
	//空链表
	if(NULL == pList->pHead)
	{
		printf("LinkList is empty!\n");
		return ;
	}
	cur = pList->pHead;
	//一个节点
	if(NULL == cur->next)
	{
		if(cur == pos)//判断这个结点是不是要删除的结点
		{
			free(cur);
			cur = NULL;
			pList->pHead = NULL;
		}
		return ;
	}
	//第一个结点就是要删除的结点
	if(pos == cur)
	{
		free(cur);
		cur = NULL;
		pList->pHead = NULL;
	}
	//链表有多个结点
	cur = cur->next;
	prev = pList->pHead;
	while(cur)
	{
		if(cur == pos)
		{
			prev->next = cur->next;
			free(cur);
			return ;
		}
		prev = cur;
		cur = cur->next;
	}
}
void BubbleSort(pLinkList pList)	//冒泡排序
{
	pLinkNode tail = NULL;
	pLinkNode cur = NULL;
	assert(pList);
	if((pList->pHead == NULL)||(pList->pHead->next == NULL))
	{
		printf("LinkList do not need to sort!\n");
		return ;
	}
	cur = pList->pHead;
	while(cur != tail)
	{
		while(cur->next != tail)
		{
			if(cur->data < cur->next->data)
			{
				DataType tmp = cur->data;
				cur->data = cur->next->data;
				cur->next->data = tmp;
			}
			cur = cur->next;
		}
		tail = cur;
		cur = pList->pHead;
	}
}

test.c

#define _CRT_SECURE_NO_WARNINGS
#include"LinkList.h"

void menu()
{
	printf("***********************************\n");
	printf("******** 0.结束    1.输出 *********\n");
	printf("******** 2.尾插    3.尾删 *********\n");
	printf("******** 4.头插    5.头删 *********\n");
	printf("******** 6.删除x   7.删除所有x ****\n");
	printf("******** 8.插入指定元素 ***********\n");
	printf("******** 9.删除指定结点 ***********\n");
	printf("******** 10.排序         ***********\n");
}
int main()
{
	LinkList mylist;
	int input = 1;
	DataType data = 0;
	DataType p = NULL;
	pLinkNode pos = NULL;
	Init(&mylist);
	while(1)
	{
		menu();
		printf("请输入选项:");
		scanf("%d",&input);
		printf("\n");
		switch(input)
		{
		case 0:
			exit(0);
			break;
		case 1:
			Print(&mylist);
			break;
		case 2:
			printf("请输入插入的数：");
			scanf("%d",&data);
			PushBack(&mylist,data);
			break;
		case 3:
			PopBack(&mylist);
			break;
		case 4:
			printf("请输入插入的数：");
			scanf("%d",&data);
			PushFront(&mylist,data);
			break;
		case 5:
			PopFront(&mylist);
			break;
		case 6:
			printf("输入要删除的数：");
			scanf("%d",&data);
			Remove(&mylist,data);
			break;
		case 7:
			printf("输入要删除的数：");
			scanf("%d",&data);
			RemoveAll(&mylist,data);
			break;
		case 8:
			printf("请输入要在哪一个位置前插入:");
			scanf("%d",&p);
			printf("请输入要插入的数：");
			scanf("%d",&data);
			pos = Find(&mylist,p);
			Insert(&mylist,pos,data);
			break;
		case 9:
			printf("输入要删除某个位置的结点:");
			scanf("%d",&data);
			pos = Find(&mylist,data);
			Erase(&mylist,pos);
			break;
		case 10:
			BubbleSort(&mylist);
			break;
		default:
			printf("无效选择!\n");
			break;
		}
	}
	Destory(&mylist);
	system("pause");
	return 0;
}

Biegral Blog

单向链表的简单实现

阅读排行

分类

归档