C语言无头节点单链表的实现

忘是亡心i 2022-05-20 23:44 158阅读 0赞

链表相对于顺序表来说，插入和删除更加方便，然而想要查找一个元素时却没有顺序表方便。

我们需要实现以下接口：

#ifndef __LINKLIST_H__ 
    #define __LINKLIST_H__ 
    
    #include <stdio.h>
    #include <string.h>
    #include <assert.h>
    #include <stdlib.h>
    
    typedef int DataType;
    typedef struct Node
    {
    	DataType data;
    	struct Node* next;
    }Node, *pNode, List, *pList;
    
    void InitLinkList(pList* pplist);
    pNode BuyNode(DataType d);
    void DestroyLinkList(pList* pplist);
    void PushBack(pList* pplist, DataType d);
    void PopBack(pList* pplist);
    void PushFront(pList* pplist, DataType d);
    void PopFront(pList* pplist);
    pNode Find(pList plist, DataType d);
    void Insert(pList* pplist, pNode pos, DataType d);//在指定位置之前插入一个值 
    void Erase(pList* pplist, pNode pos);//指定位置删除 
    void Remove(pList* pplist, DataType d);
    void RemoveAll(pList* pplist, DataType d);
    void ReMoveP(pList* pplist, DataType d);
    
    void EraseNotTailNode(pNode pos);
    void PrintLinkList(pList plist);
    int GetListLength(pList plist);
    void PrintTailToHead1(pList plist);//逆序打印单项链表 
    void PrintTailToHead2(pList plist)//逆序打印单项链表 
    
    #endif //__LINKLIST_H__

实现主函数及测试接口：

#define _CRT_SECURE_NO_WARNINGS 1
    #include "List.h"
    
    static pNode plist;
    void TestBack()
    {
    	PushBack(&plist, 1);
    	PushBack(&plist, 2);
    	PushBack(&plist, 3);
    	PushBack(&plist, 4);
    	PushBack(&plist, 5);
    	PushBack(&plist, 6);
    	PrintLinkList(plist);
    	PopBack(&plist);
    	PrintLinkList(plist);
    }
    void TestFront()
    {
    	
    	PushFront(&plist, 1);
    	PushFront(&plist, 2);
    	PushFront(&plist, 3);
    	PushFront(&plist, 4);
    	PushFront(&plist, 5);
    	PushFront(&plist, 6);
    	PrintLinkList(plist);
    	PopFront(&plist);
    	PrintLinkList(plist);
    }
    void TestFind()
    {
    	PushFront(&plist, 1);
    	PushFront(&plist, 2);
    	PrintLinkList(plist);
    	PushFront(&plist, 3);
    	PrintLinkList(plist);
    	PushFront(&plist, 4);
    	PushFront(&plist, 5);
    	PushFront(&plist, 6);
    	PrintLinkList(plist);
    	pNode tmp = NULL;
    	tmp = Find(plist, 3);
    	if (tmp)
    	{
    		printf("找到了，他的值为：%d\n", tmp->data);
    	}
    	Insert(&plist, tmp, 3);//在指定位置之前插入一个值 
    	Insert(&plist, tmp, 3);//在指定位置之前插入一个值 
    	Erase(&plist, tmp);//指定位置删除 
    	PrintLinkList(plist);
    	//EraseNotTailNode(tmp);
    	PrintLinkList(plist);
    }
    void TestRemove()
    {
    	PushFront(&plist, 1);
    	PushFront(&plist, 2);
    	PushFront(&plist, 6);
    	PushFront(&plist, 4);
    	PushFront(&plist, 5);
    	PushFront(&plist, 6);
    	PrintLinkList(plist);
    	Remove(&plist, 6);
    	PrintLinkList(plist);
    	//RemoveAll(&plist, 6);
    	//PrintLinkList(plist);
    
    }
    void TestLength()
    {
    	PushFront(&plist, 1);
    	PushFront(&plist, 2);
    	PushFront(&plist, 3);
    	PushFront(&plist, 4);
    	PushFront(&plist, 5);
    	PushFront(&plist, 6);
    	PrintLinkList(plist);
    	int len = GetListLength(plist);
    	printf("len = %d\n", len);
    }
    void TestPrintTailToHead()
    {
    	PushFront(&plist, 1);
    	PushFront(&plist, 2);
    	PushFront(&plist, 3);
    	PushFront(&plist, 4);
    	PushFront(&plist, 5);
    	PushFront(&plist, 6);
    	PrintLinkList(plist);
    	PrintTailToHead2(plist);//逆序打印单项链表 
    }
    
    int main()
    {
    	InitLinkList(&plist);
    	//TestBack();
    	//TestFront();
    	//TestFind();
    	//TestRemove();
    	//TestLength();
    	TestPrintTailToHead();
    	DestroyLinkList(&plist);
    	system("pause");
    	return 0;
    }

实现子函数：

#define _CRT_SECURE_NO_WARNINGS 1
    #include "List.h"
    
    void InitLinkList(pList* pplist)
    {
    	(*pplist)= NULL;
    }
    pNode BuyNode(DataType d)
    {
    	pNode newNode = (pNode)malloc(sizeof(Node));
    	if (newNode == NULL)
    	{
    		perror("malldc error");
    		exit(EXIT_FAILURE);
    	}
    	newNode->data =d;
    	newNode->next = NULL;
    	return newNode;
    }
    void DestroyLinkList(pList* pplist)
    {
    	assert(pplist);
    	pNode cur = NULL;
    	cur = *pplist;
    	while (cur)
    	{
    		pNode del = cur;
    		cur = cur->next;
    		free(del);
    		del = NULL;
    	}
    	*pplist = NULL;
    }
    void PushBack(pList* pplist, DataType d)
    {
    	assert(pplist);
    	pNode newNode = BuyNode(d);
    	if ((*pplist) == NULL)
    	{
    		*pplist = newNode;
    	}
    	else
    	{
    		pNode cur = NULL;
    		cur = *pplist;
    		while (cur->next)
    		{
    			cur = cur->next;
    		}
    		cur->next = newNode;
    	}
    }
    void PopBack(pList* pplist)
    {
    	assert(pplist);
    	if ((*pplist)==NULL)
    	{
    		printf("链表为空！\n");
    		return;
    	}
    	else
    	{
    		pNode cur = NULL;
    		pNode del = NULL;
    		cur = *pplist;
    		del = cur->next;
    		while (cur->next->next)
    		{
    			cur = cur->next;
    			del = cur->next;
    		}
    		cur->next = del->next;
    		free(del);
    		del = NULL;
    	}
    }
    void PushFront(pList* pplist, DataType d)
    {
    	pNode newNode = BuyNode(d);
    	assert(pplist);
    	if ((*pplist) == NULL)
    	{
    		*pplist = newNode;
    	}
    	else
    	{
    		pNode cur = *pplist;
    		newNode->next = cur;
    		*pplist = newNode;
    	}
    }
    void PopFront(pList* pplist)
    {
    	assert(pplist);
    	if ((*pplist) == NULL)
    	{
    		printf("链表为空！\n");
    		return;
    	}
    	else
    	{
    		pNode del = NULL;
    		del = *pplist;
    		*pplist = (*pplist)->next;
    		free(del);
    		del = NULL;
    	}
    }
    pNode Find(pList plist, DataType d)
    {
    	if (plist == NULL)
    	{
    		printf("链表为空！\n");
    		return NULL;
    	}
    	else
    	{
    		pNode cur = plist;
    		while (cur)
    		{
    			if (cur->data == d)
    			{
    				return cur; 
    			}
    			cur = cur->next;
    		}
    		return NULL;
    	}
    }
    void Insert(pList* pplist, pNode pos, DataType d)//在指定位置之前插入一个值 
    {
    	assert(pplist);
    	assert(pos);
    	assert(*pplist);
    	pNode newNode = BuyNode(d);
    	if (pos == (*pplist))
    	{
    		newNode->next = *pplist;
    		*pplist = newNode;
    	}
    	else
    	{
    		pNode cur = *pplist;
    		while (cur&&cur->next != pos)
    		{
    			cur = cur->next;
    		}	
    		if (cur)
    			{
    				newNode->next = pos;
    				cur->next = newNode;
    			}
    	}
    }
    void Erase(pList* pplist, pNode pos)//指定位置删除 
    {
    	assert(pplist);
    	assert(pos);
    	if ((*pplist)==NULL)
    	{
    		return;
    	}
    	if ((*pplist)==pos)
    	{
    		*pplist = pos->next;
    		free(pos);
    		pos = NULL;
    	}
    	else
    	{
    		pNode cur = *pplist;
    		while (cur&&cur->next != pos)
    		{
    			cur = cur->next;
    		}
    		if (cur)
    		{
    			cur->next = pos->next;
    			free(pos);
    			pos = NULL;
    		}
    	}
    }
    void Remove(pList* pplist, DataType d)
    {
    	assert(pplist);
    	pNode cur = *pplist;
    	if ((*pplist) == NULL)
    	{
    		return;
    	}
    	if ((*pplist)->data == d)
    	{
    		*pplist = cur->next;
    		free(cur);
    		cur = NULL;
    	}
    	else
    	{
    		pNode del = cur;
    		while (cur&&del->data != d)
    		{
    			cur = cur->next;
    			del = cur->next;
    		}
    		if (cur)
    		{
    			cur->next = del->next;
    			free(del);
    			del = NULL;
    		}
    	}
    }
    void RemoveAll(pList* pplist, DataType d)
    {
    	assert(pplist);
    	pNode cur = *pplist;
    	if ((*pplist) == NULL)
    	{
    		return;
    	}
    	pNode pre = *pplist;
    	while (cur)
    	{
    		
    		if ((*pplist)->data == d)
    		{
    			cur = *pplist;
    			*pplist = (cur)->next;
    			free(cur);
    			cur = *pplist;
    		}
    		else if (cur->data == d)
    		{
    			pre->next = cur->next;
    			free(cur);
    			cur = pre->next;
    		}
    		pre = cur;
    		cur = cur->next;	
    	}
    }
    void EraseNotTailNode(pNode pos)
    {
    	assert(pos);
    	assert(pos->next);
    	pNode del = NULL;
    	del = pos->next;
    	pos->data = pos->next->data;
    	pos->next = del->next;
    	free(del);
    	del = NULL;
    }
    void PrintLinkList(pList plist)
    {
    	pNode cur = plist;
    	while (cur)
    	{
    		printf("%d->", cur->data);
    		cur = cur->next;
    	}
    	printf("NULL\n");
    }
    int GetListLength(pList plist)
    {
    	int count = 0;
    	pNode cur = plist;
    	while (cur)
    	{
    		count++;
    		cur = cur->next;
    	}
    	return count;
    }
    void PrintTailToHead1(pList plist)//逆序打印单项链表 
    {
    	if (plist == NULL)
    		return;
    	PrintTailToHead1(plist->next);
    	printf("%d ", plist->data);
    }
    void PrintTailToHead2(pList plist)//逆序打印单项链表 
    {
    
    	pNode tail = NULL;
    	pNode cur = plist;
    	if (plist == NULL)
    		return;
    	
    	while (plist != tail)
    	{
    		while (cur->next != tail)
    		{
    			cur = cur->next;
    		}
    		printf("%d ", cur->data);
    		tail = cur;
    		cur = plist;
    	}
    
    }

无头节点的单链表就完成了!