【数据结构】C语言实现链表

快来打我* 2022-06-13 00:28 243阅读 0赞

链表的特点：  
长度不固定，可以任意增删。

存储空间不连续，数据元素之间使⽤指针相连，每个数据元素只能访问周围的⼀个元素（根据单链表还是双链表有所不同）。

存储密度小，因为每个数据元素，都需要额外存储⼀个指向下⼀元素的指针（双链表则需要两个指针）。

要访问特定元素，只能从链表头开始，遍历到该元素，时间复杂度为 O(n)O(n)。

在特定的数据元素之后插⼊或删除元素，不涉及到其他元素的移动，因此时间复杂度为O(1)。双链表还允许在特定的数据元素之前插

⼊或删除元素

单链表定义：

typedef int DataType;
    
    typedef struct LinkNode
    {
    	DataType _data;
    	struct LinkNode* next;
    }Node,*pNode;
    
    //void  InitList(PNode* pHead);//初始化
    //void  PrintList(PNode pHead);//打印
    //int  GetLinkNode(PNode pHead);//获取节点数
    //void DestoryNode(PNode* pHead);//销毁链表
    //void  PushBack(PNode* pHead, DataType data);//尾插
    //void  PopBack(PNode* pHead);//尾删
    //void  PushFront(PNode* pHead, DataType data);//头插
    //void  PopFront(PNode* pHead);//头删
    //PNode Find(PNode pHead, DataType data);//查找data的位置
    //void  Erase(PNode* pHead, PNode pos);//删除pos处的节点
    //void  EraseNoTaiNode(PNode  pos);//无头指针删除,可采用拷贝下一个结点数据，删除下一个结点
    //void  Insert(PNode pos, DataType data);//在pos后面插入一个节点
    //void  Remove(PNode* pHead, DataType data);//删除链表中的第一个data
    //void  RemoveAll(PNode* pHead, DataType data);//删除链表中所有的data
    //void  Test();//测试
    //PNode  BuyNode(DataType data);//开辟PNode空间存储data

具体实现代码：

LinkList.h

//void  InitList(PNode* pHead);//初始化
    //void  PrintList(PNode pHead);//打印
    //int  GetLinkNode(PNode pHead);//获取节点数
    //void DestoryNode(PNode* pHead);//销毁链表
    //void  PushBack(PNode* pHead, DataType data);//尾插
    //void  PopBack(PNode* pHead);//尾删
    //void  PushFront(PNode* pHead, DataType data);//头插
    //void  PopFront(PNode* pHead);//头删
    //PNode Find(PNode pHead, DataType data);//查找data的位置
    //void  Erase(PNode* pHead, PNode pos);//删除pos处的节点
    //void  EraseNoTaiNode(PNode  pos);//无头指针删除,可采用拷贝下一个结点数据，删除下一个结点
    //void  Insert(PNode pos, DataType data);//在pos后面插入一个节点
    //void  Remove(PNode* pHead, DataType data);//删除链表中的第一个data
    //void  RemoveAll(PNode* pHead, DataType data);//删除链表中所有的data
    //void  Test();//测试
    //PNode  BuyNode(DataType data);//开辟PNode空间存储data
    
    
    #ifndef __LINKLIST_H__
    #define __LINKLIST_H__
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<assert.h>
    
    typedef int DataType;
    
    typedef struct LinkNode
    {
    	DataType _data;
    	struct LinkNode* next;
    }Node,*pNode;
    
    //为新节点开辟空间
    pNode BuyNode(DataType data)
    {
    	pNode tmp = (pNode)malloc(sizeof(Node));
    	tmp->_data = data;
    	tmp->next = NULL;
    	return tmp;
    }
    
    
    
    //链表初始化
    void InitLinkList(pNode* pHead)
    {
    	*pHead = NULL;
    }
    //打印单链表
    void PrintLinkList(pNode pHead)
    {
    	assert(NULL != pHead);
    	pNode pCur = pHead;
    	while (pCur != NULL)
    	{
    		printf("%d ->", pCur->_data);
    		pCur = pCur->next;
    	}
    	printf("\n");
    }
    //尾插
    void PushBack(pNode* pHead, DataType data)
    {
    	assert(NULL != pHead);
    	pNode pCur = *pHead;
    	//判断节点是否为空
    	if (NULL == *pHead)
    	{
    		*pHead = BuyNode(data);
    	}
    	else
    	{
    		
    		while (NULL != pCur->next)
    		{
    			pCur = pCur->next;
    		}
    		pCur->next = BuyNode(data);
    	}
    
    }
    //尾删
    void PopBack(pNode* pHead)
    {
    	assert(NULL != pHead);
    	
    	pNode pCur = *pHead;
    
    	if (pCur == NULL)
    	{
    		printf("链表是空的\n");
    		return;
    	}
    	else if (NULL == pCur->next)
    	{
    		free(pCur);
    		*pHead = NULL;
    	}
    	else
    	{
    	    pCur = *pHead;
    		pNode pre = NULL;
    		while (NULL != pCur->next)
    		{
    			pre = pCur;
    			pCur = pCur->next;
    		}
    		pre->next = NULL;
    		free(pCur);
    		pCur = NULL;
    	}
    }
    //头插
    void PushFront(pNode* pHead, DataType data)
    {
    	assert(NULL != pHead);
    	pNode pCur;
    	pCur = BuyNode(data);
    	pCur->next = *pHead;
    	*pHead = pCur;
    }
    //头删
    void PopFront(pNode* pHead, DataType data)
    {
    	assert(NULL != pHead);
    	pNode pCur = *pHead;
    	if (NULL == pCur)
    	{
    		printf("链表是空的\n");
    		return;
    	}
    	else if (NULL == pCur->next)
    	{
    		free(pCur);
    		*pHead = NULL;
    	}
    	else
    	{
    		pNode pre = *pHead;
    		pre = pre->next;
    		*pHead = pre;
    		free(pCur);
    		pCur = NULL;
    	}
    }
    pNode Find(pNode pHead, DataType data)
    {
    	pNode pCur = pHead;
    	while (pCur)
    	{
    		if (pCur->_data == data)
    		{
    			printf("找到了。。。\n");
    			return pCur;
    		}
    		else
    		{
    			pCur = pCur->next;
    		}
    	}
    	printf("没有这个数\n");
    	return NULL;
    }
    //删除指定位置节点（是否为头结点！！！）
    void Erase(pNode* pHead, pNode pos)
    {
    	assert(NULL != pHead);
    	pNode pCur = *pHead;
    	if (pCur == pos && pCur->next == NULL)
    	{
    		free(pCur);
    		*pHead = NULL;
    		return;
    	}
    	else
    	{
    		while (pCur->next != pos && pCur)
    		{
    			pCur = pCur->next;
    		}
    		if (pCur)
    		{
    			pNode pre = pCur->next;
    			pCur->next = pre->next;
    			free(pre);
    		}
    		else
    		{
    			printf("没有找到\n");
    		}
    	}
    }
    //无头指针删除,可采用拷贝下一个结点数据，删除下一个结点
    void EraseNoTail(pNode* pHead, pNode pos)
    {
    	pNode del = pos->next;
    	pos->_data = del->_data;
    	pos->next = del->next;
    	free(del);
    	
    }
    //删除链表中第一个出现的data
    void Remove(pNode* pHead, DataType data)
    {
    	assert(NULL != pHead);
    	pNode pCur = *pHead;
    
    	//如果是头结点
    	if (pCur->_data == data)
    	{
    		*pHead = pCur->next;
    		free(pCur);
    		return;
    	}
    	else
    	{
    		while (pCur && pCur->next->_data != data)
    		{
    			pCur = pCur->next;
    		}
    		if (pCur)
    		{
    			pNode pre = pCur->next;
    			pCur->next = pre->next;
    			free(pre);
    			return;
    		}
    	}
    	printf("没有这个数\n");
    }
    
    //删除链表中所有data值
    void RemoveAll(pNode* pHead, DataType data)
    {
    	pNode pCur = *pHead;
    	if (pCur->_data == data && pCur->next == NULL)
    	{
    		free(pCur);
    		*pHead = NULL;
    		return;
    	}
    	pNode pre = *pHead;
    	while (1)
    	{
    		//注意pCur的判空位置
    		//while(pCur->_data != data && pCur)
    		//若为最后一个节点 按照上面的判断方式第一个条件此时pCur为NULL执行语句会引发异常
    		while (pCur && pCur->_data != data)
    		{
    			pre = pCur;
    			pCur = pCur->next;
    		}
    		if (pCur)
    		{
    			pre->next = pCur->next;
    			free(pCur);
    			pCur = pre->next;
    		}
    		else
    			return;
    	}
    }
    
    int GetLinkNode(pNode pHead)
    {
    	pNode pCur = pHead;
    	int number = 0;
    	while (pCur != NULL)
    	{
    		pCur = pCur->next;
    		number++;
    	}
    	return number;
    }
    void DestroyLinkList(pNode* pHead)
    {
    	pNode del = *pHead;
    	pNode pCur = *pHead;
    
    	while (del)
    	{
    		del = *pHead;
    		pCur = pCur->next;
    		*pHead = pCur;
    		free(del);
    	}
    }
    #endif 
    
    
    
     
    test.c
     
     
     #include"LinkList.h"
    
    void FunTest()
    {
    	Node link;
    	pNode Head = &link;
    	//初始化
    	InitLinkList(&Head);
    	//头插
    	PushBack(&Head, 1);
    	PushBack(&Head, 2);
    	PushBack(&Head, 3);
    	PushBack(&Head, 4);
    	PushBack(&Head, 5);
    	PushBack(&Head, 5);
    	PushBack(&Head, 7);
    	PushBack(&Head, 5);
    	PushBack(&Head, 5);
    	PushBack(&Head, 8);
    
    	//打印
    	PrintLinkList(Head);
    	//尾删、测试只有一个节点时的删除
    	PopBack(&Head);
    	PrintLinkList(Head);
    
    	//头插
    	PushFront(&Head, 6);
    	PrintLinkList(Head);
    	//头删
    	PopFront(&Head, 6);
    	PrintLinkList(Head);
    	//查找
    	Find(Head, 6);
    	 //删除指定位置节点
    	Erase(&Head, Find(Head,2));
    	PrintLinkList(Head);
    	//删除指定数字元素（第一个出现）
    	Remove(&Head, 5);
    	PrintLinkList(Head);
    	//删除所有指定元素
    	RemoveAll(&Head, 5);
    	PrintLinkList(Head);
    	//获取节点个数
    	printf("节点个数： %d\n", GetLinkNode(Head));
    	//销毁链表
    	DestroyLinkList(&Head);
    }
    
    int main()
    {
    	FunTest();
    	system("pause");
    	return 0;
    }