C语言实现链表

╰+哭是因爲堅強的太久メ 2022-05-31 04:22 208阅读 0赞

**用C语言实现数据结构和算法莫过于最爽的事。 —摘自CoolShell**

> **PS：这里我用C语言实现的链表是不带头节点的单链表，这个是链表里面实际操作中最容易出错的一种链表，我在代码中会指出需要注意的内容说明**

--------------------

\---------->ListHead.h  
尾插：从单链表的尾部插入一个新的节点  
尾删：从单链表的尾部删除一个节点  
头插和头删就不用说明了吧。。。

#pragma once
    //这里之所以要定义一个DataType类型是为了方便以后更改链表中存储的数
    //据类型
    typedef int DataType;
    
    //定义链表的节点
    //将节点类型重命名为 Node 类型
    //将指向节点的指针重命名为 PNode 类型
    typedef struct ListNode
    { 
    	DataType _data;
    	struct ListNode* _Next;
    }Node,*PNode;
    
    void SListInit(PNode *ppHead);//初始化单链表的函数
    void SListPushTail(PNode *ppHead, DataType data);//尾插的函数
    void SListPopTail(PNode *ppHead);//尾删的函数
    void SListPushFront(PNode *ppHead, DataType data);//头插的函数
    PNode Find(PNode ppHead, DataType data);//查找数据的函数
    //任意位置插入的函数
    void SListPushInsert(PNode *ppHead, PNode pos, DataType data);
    //任意位置删除的函数
    void SListErase(PNode *ppHead, PNode pos);
    size_t Size(PNode pHead);//求单链表长度的函数
    size_t Empty(PNode pHead);//判断单链表是否为空的函数
    void SListDeatory(PNode *ppHead);//销毁一个单链表的函数
    PNode BuySListNode(DataType data);//申请新节点的函数
    void SListPrint(PNode pHead);//遍历打印单链表中数据的函数

\->List.c

#include<stdio.h>
    #include<assert.h>
    #include<stdlib.h>
    #include "ListHead.h"
    /* *初始化链表的函数需要注意穿进去的参数是一个二级指针，因为要给一级指针分 *配空间，根据函数传参的原理，必须要将一级指针的地址作为参数，而一级指针 *的地址就是二级指针。 */
    void SListInit(PNode *ppHead)
    { 
    	assert(ppHead);
    	*ppHead = NULL;
    }
    //因为要对链表进行内存分配，所以也要传二级指针
    void SListPushBack(PNode *ppHead, DataType data)
    { 
    	assert(ppHead);
    	//如果链表为空，则直接让头指针指向新申请的节点即可
    	if (*ppHead == NULL)
    	{ 
    		*ppHead = BuySListNode(data);
    	}
    	//否则从头开始遍历链表，直到当前节点的指针域指向NULL，然后让当前节
    	//点的指针域指向新申请的节点即可
    	else
    	{ 
    		PNode str = *ppHead;
    		while (str->_Next)
    			str = str->_Next;
    		str->_Next= BuySListNode(data);
    	}
    }
    
    PNode BuySListNode(DataType data)
    { 
    	PNode new_node = (PNode)malloc(sizeof(Node));
    	new_node->_data = data;
    	new_node->_Next = NULL;
    	return new_node;
    }
    //由于要删除链表的节点，即要释放链表占有的一部分内存，所以必须要传
    //一个二级指针
    void SListPopBack(PNode *ppHead)
    { 
    	assert(ppHead);
    	if (NULL == *ppHead)
    	{ 
    		return;
    	}
    	//如果当前只有一个节点，则释放掉当前节点，并将头指针指向NULL，避免
    	//出现野指针
    	if ((*ppHead)->_Next == NULL)
    	{ 
    		free(*ppHead);
    		*ppHead = NULL;
    	}
    	else
    	{ 
    		PNode str = *ppHead;
    		PNode prestr = NULL;
    		while (str->_Next)
    		{ 
    			prestr = str;
    			str = str->_Next;
    		}
    		free(str);
    		prestr->_Next = NULL;
    	}
    }
    void SListPushFront(PNode *ppHead, DataType data)
    { 
    	assert(ppHead);
    	PNode str= BuySListNode(data);
    	str->_Next = *ppHead;
    	*ppHead = str;
    }
    
    PNode Find(PNode pHead, DataType data)
    { 
    	assert(pHead);		
    	PNode str = pHead;
    	while (str && str->_data != data)
    		str = str->_Next;
    	if (str != NULL)
    		return str;
    	else
    		printf("没有找到！\n");
    	return NULL;
    }
    
    void SListPushInsert(PNode *ppHead, PNode pos, DataType data)
    { 
    	assert(ppHead);
    	assert(pos);
    	PNode new_node = NULL;
    	if (*ppHead == NULL)
    	{ 
    		return;
    	}
    	new_node=BuySListNode(data);
    	PNode prestr = NULL;
    	PNode str = *ppHead;
    	while (str!=pos)
    	{ 
    		prestr = str;
    		str = str->_Next;
    	}
    	new_node->_Next= str;
    	prestr->_Next = new_node;
    }
    
    void SListErase(PNode *ppHead, PNode pos)
    { 
    	assert(ppHead);
    	if (NULL == *ppHead || NULL == pos)
    	{ 
    		return;
    	}
    	PNode str = *ppHead;
    	PNode pre_str = NULL;
    	while (str != pos)
    	{ 
    		pre_str = str;
    		str = str->_Next;
    	}
    	pre_str->_Next = str->_Next;
    	free(str);
    }
    size_t Size(PNode pHead)            
    { 
    	assert(pHead);
    	Node *str = pHead;
    	int count = 0;
    	while (str)
    	{ 
    		str = str->_Next;
    		count++;
    	}
    	return count;
    }
    int Empty(PNode pHead)       
    { 
    	assert(pHead);
    	return (pHead == NULL);
    }
    void SListDeatory(PNode *ppHead)
    { 
    	assert(ppHead);
    	Node *str = NULL;
    	PNode prenode = *ppHead;
    	while (prenode)
    	{ 
    		str = prenode;
    		prenode = prenode->_Next;           
    		free(str);
    	}
    	*ppHead = NULL;//记得最后让头指针指向NULL
    }
    
    void SListPrint(PNode pHead)
    { 
    	assert(pHead);
    	PNode prenode = pHead;
    	while (prenode)
    	{ 
    		printf("%d--", prenode->_data);
    		prenode = prenode->_Next;
    	}
    	printf("NULL\n");
    }