C语言单链表

迷南。 2022-06-08 00:57 147阅读 0赞

链表是一种常见的数据结构，它是动态地进行存储分配的一种结构。每一个存储单元称为一个节点，都由两部分组成，一个是存储数据的数据域，另一个是存储下一个节点地址的指针域。

![SouthEast][]

链表分为单向链表、双向链表，循环链表等；单链表还可以分为带头节点的和不带头节点的。一般的链表都是不带头节点的实现。下面是用C语言对单链表的简单接口实现：包括链表节点的创建、头插尾插、头删尾删、查找指定元素、删除指定元素等几个函数。首先声明，为了使程序更通用，我们将类型int重命名为Datatype，以后更换数据类型修改程序时，将更为方便。

链表的结构：

typedef int DataType;
    typedef struct Node 
    {
    	DataType data;
    	struct Node* next;
    }Node, *pNode, *pList;

函数的声明：

void InitLinkList(pList* pplist);//初始化
    pNode BuyNode(DataType d);//创建节点
    void PushFront(pList* pplist, DataType d);//头插节点
    void PopFront(pList* pplist);//头删节点
    void PushBack(pList *pplist, DataType d);//尾插节点
    void PopBack(pList *pplist);//尾删节点
    void Display(pList plist);//打印链表
    void DestroyList(pList* pplist);//销毁链表 
    pNode Find(pList plist, DataType d);//查找指定元素
    void Insert(pList *pplist, pNode pos, DataType d);//指定位置后插入元素
    void Remove(pList *pplist, DataType d);//删除指定元素
    void RemoveAll(pList *pplist, DataType d);//删除指定的所有元素

以下是具体的实现代码：

void InitLinkList(pList* pplist)//初始化链表
    {
    	assert(pplist);
    	*pplist = NULL;
    }
    pNode BuyNode(DataType d)//创建节点
    {
    	pNode tmp = malloc(sizeof(Node));
    	if (tmp == NULL)
    	{
    		perror("malloc");
    		exit(EXIT_FAILURE);
    	}
    	tmp->data = d;
    	tmp->next = NULL;
    	return tmp;
    }
    void PushFront(pList* pplist, DataType d)//头插
    {
    	assert(pplist);
    	pNode tmp = BuyNode(d);
    	if (*pplist == NULL)
    	{
    		*pplist = tmp;
    	}
    	else
    	{
    		tmp->next = *pplist;
    		*pplist = tmp;
    	}
    }
    void PopFront(pList* pplist)//头删
    {
    	pList cur = *pplist;
    	assert(pplist);
    	if (cur == NULL)
    		return;
    	else
    	{
    		*pplist = cur->next;
    		free(cur);
    		cur = NULL;
    	}
    }
    void PushBack(pList *pplist, DataType d)//尾插
    {
    	assert(pplist);
    	pNode tmp = BuyNode(d);
    	pList cur = *pplist;
    	if (*pplist == NULL)//链表无节点
    	{
    		*pplist = tmp;
    		return;
    	}
    	else
    	{
    		while (cur->next)
    		{
    			cur = cur->next;
    		}
    		cur->next = tmp;
    	}
    }
    void PopBack(pList *pplist)//尾删
    {
    	assert(pplist);
    	pList cur = *pplist;
    	pNode tmp = cur;
    	if (*pplist == NULL)
    		return;
    	if (cur->next == NULL)
    	{
    		free(*pplist);
    		*pplist = NULL;
    		return;
    	}
    	while (cur->next)//cur为要删除的节点,tmp为要删除的节点的前一个
    	{
    		tmp = cur;
    		cur = cur->next;
    	}
    	tmp->next = NULL;
    	free(cur);
    	cur = NULL;
    }
    void Display(pList plist)//打印链表
    {
    	pList cur = plist;
    	if (cur == NULL)
    		return;
    	while (cur)
    	{
    		printf("%d->", cur->data);
    		cur = cur->next;
    	}
    	printf("over\n");
    }
    void DestroyList(pList* pplist)//销毁链表
    {
    	pList cur = *pplist;
    	while (cur)
    	{
    		pNode del = cur;
    		cur = cur->next;
    		free(del);
    		del = NULL;
    	}
    	*pplist = NULL;
    }
    pNode Find(pList plist, DataType d)//查找某个指定元素
    {
    	pList cur = plist;
    	while (cur)
    	{
    		if (cur->data == d)
    			return cur;
    		else
    			cur = cur->next;
    	}
    	return NULL;//如果没找到返回NULL
    }
    void Insert(pList *pplist, pNode pos, DataType d)//在指定位置后插入元素
    {
    	assert(pplist);
    	assert(pos);
    	pNode tmp = BuyNode(d);
    	if (*pplist == NULL)//空链表直接插入元素
    	{
    		*pplist = tmp;
    		return;
    	}
    	tmp->next = pos->next;
    	pos->next = tmp;
    }
    void Remove(pList *pplist, DataType d)
    //要删除指定元素，我们可以先用前面已经实现的Find函数，找到指定元素的位置，然后再删除
    {
    	assert(pplist);
    	pList cur = *pplist;
    	if (cur == NULL)
    	{
    		return;
    	}
    	pNode pos = Find(*pplist, d); 
    	if (pos != NULL)
    	{
    		if (pos->next == NULL)//尾节点
    		{
    			PopBack(pplist);
    		}
    		else//非尾
    		{
    			pNode del = pos->next;//将指定节点的下一个节点数据域和指针域的内容赋给指定的节点，然后删除指定节点的下一个节点
    			pos->data = pos->next->data;
    			pos->next = pos->next->next;
    			free(del);
    			del = NULL;
    		}
    	}
    }
    void Remove_2(pList *pplist, DataType d)
    //除过上面的方法，我们还可以遍历链表一遍，找到指定元素，进行删除
    {
    	assert(pplist);
    	pList cur = *pplist;
    	if (cur == NULL)
    	{
    		return;
    	}
    	while (cur)
    	{
    		if (cur->data == d)
    		{
    			if (cur->next == NULL)
    			{
    				PopBack(pplist);
    				break;
    			}
    			pNode del = cur->next;删除的节点非尾
    			cur->data = del->data;
    			cur->next = del->next;
    			free(del);
    			del = NULL;
    		}
    		cur = cur->next;
    	}
    }
    void RemoveAll(pList *pplist, DataType d)//删除指定的所有元素
    {
    	assert(pplist);
    	pList cur = *pplist;
    	while (cur)
    	{
    		if (cur->data == d)
    		{
    			if (cur->next == NULL)//尾节点
    			{
    				PopBack(pplist);
    				break;
    			}
    			Remove(pplist, d);//非尾
    		}
    		if (cur->data != d)//等于d则删除，不等于d则继续遍历链表
    		{
    			cur = cur->next;
    		}
    	}
    }

[SouthEast]: /images/20220608/5c19e40ca1b4494c85d5cbefcc3883a2.png