数据结构之无头单向非循环链表（源代码）

绝地灬酷狼 2023-07-02 13:29 6阅读 0赞

## SList.h ##

//无头单向非循环链表
    
    #ifndef __SLIST_H__
    #define __SLIST_H__
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    #include<malloc.h>
    
    typedef int SLTDataType;
    typedef struct SListNode
    { 
    	SLTDataType _data;
    	struct SListNode* _next;
    }SListNode;
    
    typedef struct SList
    { 
    	SListNode* _head;
    }SList;
    
    void SListInit(SList* plist);
    void SListDestory(SList* plist);
    
    SListNode* BuySListNode(SLTDataType x);
    void SListPushBack(SList* plist, SLTDataType x);  //尾插
    void SListPopBack(SList* plist);   //删除最后一个元素
    void SListPushFront(SList* plist, SLTDataType x);  //头插
    void SListPopFront(SList* plist);   //删除第一个元素
    SListNode* SListFind(SList* plist, SLTDataType x);  //查找
    void SListInsertAfter(SListNode* pos, SLTDataType x);//在pos的后面进行插入
    void SListEraseAfter(SListNode* pos);   //删除pos后面的节点
    void SListRemove(SList* plist, SLTDataType x);  //删除某个给定的数
    
    void SListPrint(SList* plist)
    
    #endif //__SLIST_H__

## SList.c ##

#include "Slist.h"
    
    //初始化链表
    void SListInit(SList* plist)
    { 
    	assert(plist != NULL);
    	plist->_head = NULL;
    }
    
    //销毁链表
    void SListDestory(SList* plist)
    { 
    	assert(plist != NULL);
    	SListNode* cur = plist->_head;
    	while (cur != NULL)
    	{ 
    		SListNode* next = cur->_next;
    		free(cur);
    		cur = next;
    	}
    	plist->_head = NULL;
    }
    
    //构造一个新节点
    SListNode* BuySListNode(SLTDataType x)
    { 
    	SListNode* node = (SListNode*)malloc(sizeof(SListNode));
    	assert(node != NULL);
    	node->_data = x;
    	node->_next = NULL;
    	return node;
    }
    
    //尾插
    void SListPushBack(SList* plist, SLTDataType x)
    { 
    	assert(plist != NULL);
    	SListNode* newnode = BuySListNode(x);
    	SListNode* tail = plist->_head;
    	if (plist->_head == NULL)
    	{ 
    		plist->_head = newnode;
    	}
    	else
    	{ 
    		while (tail->_next != NULL)
    		{ 
    			tail = tail->_next;
    		}
    		tail->_next = newnode;
    	}
    }
    
    //删除最后一个元素
    void SListPopBack(SList* plist)
    { 
    	assert(plist != NULL);
    	SListNode* prev = NULL;
    	SListNode* tail = plist->_head;
    	if (tail->_next == NULL)
    	{ 
    		free(tail);
    		tail = NULL;
    		plist->_head = NULL;
    	}
    	else
    	{ 
    		while (tail->_next != NULL)
    		{ 
    			prev = tail;
    			tail = tail->_next;
    		}
    		free(tail);
    		tail = NULL;
    		prev->_next = NULL;
    	}
    }
    
    //头插
    void SListPushFront(SList* plist, SLTDataType x)
    { 
    	assert(plist != NULL);
    	SListNode* newnode = BuySListNode(x);
    	newnode->_next = plist->_head;
    	plist->_head = newnode;
    }
    
    //删除第一个元素
    void SListPopFront(SList* plist)
    { 
    	assert(plist != NULL);
    	SListNode* next = plist->_head->_next;
    	free(plist->_head);
    	plist->_head = next;
    }
    
    //查找
    SListNode* SListFind(SList* plist, SLTDataType x)
    { 
    	assert(plist != NULL);
    	SListNode* cur = plist->_head;
    	while (cur != NULL)
    	{ 
    		if (cur->_data == x)
    		{ 
    			return cur;
    		}
    		else
    		{ 
    			cur = cur->_next;
    		}
    	}
    	return cur;
    }
    
    //在pos的后面进行插入
    void SListInsertAfter(SListNode* pos, SLTDataType x)
    { 
    	assert(pos != NULL);
    	SListNode* newnode = BuySListNode(x);
    	assert(newnode != NULL);
    	newnode->_next = pos->_next;
    	pos->_next = newnode;
    }
    
    //在pos的前面进行插入
    void SListInsert(SListNode* pos, SLTDataType x)
    { 
    	assert(pos != NULL);
    	SListNode* newnode = BuySListNode(x);
    	assert(newnode != NULL);
    	newnode->_next = pos->_next;
    	pos->_next = newnode;
    	newnode->_data = pos->_data;
    	pos->_data = x;
    }
    
    //删除pos后面的节点
    void SListEraseAfter(SListNode* pos)
    { 
    	assert(pos != NULL);
    	if (pos->_next == NULL)
    	{ 
    		return;
    	}
    	SListNode* next = pos->_next->_next;
    	free(pos->_next);
    	pos->_next = next;
    }
    
    //删除某个给定的数
    void SListRemove(SList* plist, SLTDataType x)
    { 
    	assert(plist != NULL);
    	if (plist->_head->_data == x)
    	{ 
    		SListPopFront(plist);
    		return;
    	}
    	SListNode* cur = plist->_head;
    	SListNode* prev = NULL;
    	while (cur != NULL)
    	{ 
    		if (cur->_data == x)
    		{ 
    			prev->_next = cur->_next;
    			free(cur);
    			cur = NULL;
    			break;
    		}
    		else
    		{ 
    			prev = cur;
    			cur = cur->_next;
    		}
    	}
    }
    
    
    void SListPrint(SList* plist)
    { 
    	assert(plist != NULL);
    	SListNode* cur = plist->_head;
    	while (cur != NULL)
    	{ 
    		printf("%d->", cur->_data);
    		cur = cur->_next;
    	}
    	printf("NULL\n");
    }