C语言::实现无头节点的单链表 - 高小调博客

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

本文主要介绍通过C语言程序来实现数据结构中无头节点的单链表.

需要用到的小伙伴直接拿去,不谢!!!

原型定义(SList.h)

#ifndef __SLIST_H__
#define __SLIST_H__
#include<assert.h>
#include<stdlib.h>
#include<stdio.h>
typedef int DataType;
//链表定义
typedef struct Node{
	DataType data;
	struct Node *next;
}Node,*PNode;
//初始化链表
void InitList(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);
//插入节点
void Insert(PNode pos, DataType data);
//创建新节点
PNode ByeNode(DataType data);
//打印链表
void PrintList(PNode pHead);
//删除节点
void Erase(PNode* pHead, PNode pos);
//根据数据删除节点
void Remove(PNode* pHead, DataType data);
//根据所给数据删除链表中所有节点
void RemoveAll(PNode* pHead, DataType data);
//销毁链表
void DestroyList(PNode* pHead);
//获得链表尾部
PNode Back(PNode pHead);
#endif

函数实现(SList.c)

#include"SList.h"
/*
*函数功能:初始化一个链表
*参数说明:pHead:第一个节点的二级指针
*返回值:无
*/
void InitList(PNode* pHead){
	assert(pHead);
	(*pHead) = NULL;
}
/*
*函数功能:创建一个新节点
*参数说明:data:新节点的数据
*返回值:成功返回创建后节点的地址,失败返回NULL
*/
PNode ByeNode(DataType data){
	PNode ret = (PNode)malloc(sizeof(Node));
	if( NULL!=ret ){
		ret->data=data;
		ret->next=NULL;
	}
	return ret;
}
/*
*函数功能:向链表尾部插入新数据
*参数说明:pHead,链表的第一个节点;data,新节点的数据
*返回值:无返回值
*/
void PushBack(PNode* pHead, DataType data){
	assert(pHead);
	//空链表
	if(NULL==*pHead){
		*pHead = ByeNode(data);
	//其他情况
	}else{
		PNode pCur = *pHead;
		while(NULL!=pCur->next){
			pCur = pCur->next;
		}
		pCur->next = ByeNode(data);
	}
}
/*
*函数功能:删除链表尾部数据
*参数说明:pHead,链表的第一个节点;
*返回值:无返回值
*/
void PopBack(PNode* pHead){
	assert(pHead);
	//空链表
	if(NULL == *pHead){
		return ;
	//只有一个节点的链表
	}else if(NULL == (*pHead)->next){
		free(*pHead);
		*pHead=NULL;
	//其它情况
	}else{
		PNode pCur = *pHead;
		//找到倒数第二个节点
		while(NULL != pCur->next->next){
			pCur = pCur->next;
		}
		//释放掉最后一个节点
		free(pCur->next);
		//避免野指针、链表结束标示
		pCur->next=NULL;
	}
}
/*
*函数功能:向链表头部插入新数据
*参数说明:pHead,链表的第一个节点;data,新节点的数据
*返回值:无返回值
*/
void PushFront(PNode* pHead, DataType data){
	assert(pHead);
//额外代码块
//解决C语言变量必须定义在语句前面的编译错误
{
	PNode pNewNode = ByeNode(data);
	//创建新节点失败
	if(!pNewNode){
		return ;
	}
	pNewNode->next = (*pHead);
	*pHead = pNewNode;
}
}
/*
*函数功能:删除链表头部数据
*参数说明:pHead,链表的第一个节点
*返回值:无
*/
void PopFront(PNode* pHead){
	assert(pHead);
	//空链表
	if(NULL == *pHead){
		return ;
	//一个节点以上
	}else{
		PNode DeletedNode = *pHead;
		*pHead = (*pHead)->next;
		free(DeletedNode);
		DeletedNode = NULL;
	}
}
/*
*函数功能:查找数据并返回其地址
*参数说明:pHead,链表的第一个节点;data,被查找的数据
*返回值:找到返回其地址,未找到返回NULL
*/
PNode Find(PNode pHead, DataType data){
	//空链表
	if(NULL==pHead){
		return NULL;
	}
	//额外代码块,解决编译错误
	{
		PNode pCur = pHead;
		while(pCur!=NULL){
			if(pCur->data==data){
				return pCur;
			}
			pCur = pCur->next;
		}
		return NULL;
	}
}
/*
*函数功能:在链表任意位置插入数据
*参数说明:pos,被插入前面的位置;data,被插入的数据
*返回值:无
*/
void Insert(PNode pos, DataType data){
	if(NULL==pos){
		return ;
	}
	{
		PNode pNewNode = ByeNode(data);
		//新节点创建失败
		if(!pNewNode){
			return ;
		}
		pNewNode->next = pos->next;
		pos->next = pNewNode;
	}
}
/*
*函数功能:将整个链表打印到屏幕上
*参数说明:pHead,链表第一个节点的指针
*返回值:无
*/
void PrintList(PNode pHead){
	//空链表
	if(!pHead){
		printf("NULL\n");
	}
	{
		PNode pCur = pHead;
		while(NULL!=pCur){
			printf("%d->",pCur->data);
			pCur = pCur->next;
		}
		printf("NULL\n");
	}
}
/*
*函数功能:删除链表Pos位置的元素
*参数说明:pHead,链表第一个节点的指针;pos,被删除元素的位置
*返回值:无
*/
void Erase(PNode* pHead, PNode pos){
	assert(pHead);
	//没有找到该元素
	if(NULL==pos){
		return ;
	}
	//空链表
	if(NULL==*pHead){
		return ;
	}
	//头节点
	if(pos == *pHead){
		PopFront(pHead);
	}else{
		PNode pPreNode = *pHead;
		//找pos的前一个元素
		while(pPreNode->next!=NULL){
			if(pPreNode->next==pos){
				break;
			}
			pPreNode = pPreNode->next;
		}
		//如果pos不在链表里
		if(pPreNode==NULL){
			return ;
		}else{
			pPreNode->next = pos->next;
			free(pos);
		}
	}
}
/*
*函数功能:删除链表中第一个值为data的元素
*参数说明:pHead,链表第一个节点的二级指针;data,被删除的元素
*返回值:无
*/
void Remove(PNode* pHead, DataType data){
	assert(pHead);
	//空链表
	if(NULL == *pHead){
		return ;
	}else{
		Erase(pHead, Find(*pHead,data));
	}
}
/*
*函数功能:删除链表中所有值为data的元素
*参数说明:pHead,链表第一个节点的二级指针;data,被删除的元素
*返回值:无
*/
void RemoveAll(PNode* pHead, DataType data){
	assert(pHead);
	//空链表
	if(NULL==*pHead){
		return ;
	}else{
		PNode pPre = NULL;
		PNode pCur = *pHead;
		while(NULL!=pCur){
			if(pCur->data==data){
				//找到了要删除的节点
				if(NULL==pPre){
					//被删除的恰好是头节点
					if(pCur->next==NULL){
						//即是头节点又是尾节点
						free(*pHead);
						*pHead=NULL;
						return ;
					}else{
					//正常的头节点
						pPre = pCur;
						pCur = pCur->next;
						*pHead = pCur;
						free(pPre);
						pPre=NULL;
					}
				}else{
					//被删除节点前一个节点指向\
					  被删除节点下一个节点
					pPre->next = pCur->next;
					pPre = pCur;
					pCur = pCur->next;
					free(pPre);
				}
			}else{
				//没有找到要删除的节点
				pPre = pCur;
				pCur = pCur->next;
			}
		}
	}
}
/*
*函数功能:删除整个链表
*参数说明:pHead,链表第一个节点的二级指针;
*返回值:无
*/
void DestroyList(PNode* pHead){
	PNode pCur = NULL;
	PNode pNext =NULL;
	assert(pHead);
	if(*pHead==NULL){
		//空链表
		return ;
	}
	pCur = *pHead;
	//c n
	//0 1 2 3 4 5 6 7 8 9
	//删除掉除头节点以外所有节点
	while(pNext=pCur->next){
		pCur->next = pNext->next;
		free(pNext);
	}
	free(*pHead);
	*pHead=NULL;
}
/*
*函数功能:找到链表的尾部
*参数说明:pHead,链表第一个节点的二级指针;
*返回值:无
*/
PNode Back(PNode pHead){
	PNode pCur = pHead;
	if(NULL==pHead){
		return ;
	}
	while(NULL!=pCur->next){
		pCur = pCur->next;
	}
	return pCur;
}

测试代码(test.c)

#include"SList.h"
void Test_InitList(){
	PNode pHead;
	InitList(&pHead);
}
void Test_PushBack(){
	PNode pHead;
	InitList(&pHead);
	//空链表
	PushBack(&pHead,0);
	//至少有一个节点
	PushBack(&pHead,1);
	PushBack(&pHead,2);
	PushBack(&pHead,3);
	PushBack(&pHead,4);
}
void Test_PopBack(){
	PNode pHead;
	InitList(&pHead);
	//空链表
	PushBack(&pHead,0);
	//至少有一个节点
	PushBack(&pHead,1);
	PushBack(&pHead,2);
	PushBack(&pHead,3);
	PushBack(&pHead,4);
	//其他情况
	PopBack(&pHead);
	PopBack(&pHead);
	PopBack(&pHead);
	//只有一个节点
	PopBack(&pHead);
	//空链表
	PopBack(&pHead);
}
void Test_PushFront(){
	PNode pHead;
	InitList(&pHead);
	PushFront(&pHead,5);
	PushFront(&pHead,4);
	PushFront(&pHead,3);
	PushFront(&pHead,2);
	PushFront(&pHead,1);
	PushFront(&pHead,0);
}
void Test_PopFront(){
	PNode pHead;
	InitList(&pHead);
	PushFront(&pHead,2);
	PushFront(&pHead,1);
	PushFront(&pHead,0);
	//一个节点以上
	PopFront(&pHead);
	PopFront(&pHead);
	PopFront(&pHead);
	//空链表
	PopFront(&pHead);
}
void Test_Find(){
	PNode pHead;
	InitList(&pHead);
	PushFront(&pHead,2);
	PushFront(&pHead,1);
	PushFront(&pHead,0);
	//第一个节点
	if(Find(pHead,0)){
		printf("0找到了!\n");
	}else{
		printf("0不存在!\n");
	}
	//中间节点
	if(Find(pHead,1)){
		printf("1找到了!\n");
	}else{
		printf("1不存在!\n");
	}
	//最后一个节点
	if(Find(pHead,2)){
		printf("2找到了!\n");
	}else{
		printf("2不存在!\n");
	}
	//不存在的数
		if(Find(pHead,15)){
		printf("15找到了!\n");
	}else{
		printf("15不存在!\n");
	}
}
void Test_Insert(){
	PNode pHead;
	InitList(&pHead);
	PushFront(&pHead,0);
	//尾部
	Insert(Find(pHead,0),1);
	//中间
	Insert(Find(pHead,1),5);
	Insert(Find(pHead,1),2);
	Insert(Find(pHead,2),3);
	Insert(Find(pHead,3),4);
	//异常
	Insert(Find(pHead,100),4);
}
void Test_PrintList(){
	PNode pHead;
	InitList(&pHead);
	PushFront(&pHead,0);
	//尾部
	Insert(Find(pHead,0),1);
	//中间
	Insert(Find(pHead,1),5);
	Insert(Find(pHead,1),2);
	Insert(Find(pHead,2),3);
	Insert(Find(pHead,3),4);
	//异常
	Insert(Find(pHead,100),4);
	PrintList(pHead);
}
void Test_Erase(){
	PNode pHead;
	InitList(&pHead);
	PushBack(&pHead,0);
	PushBack(&pHead,1);
	PushBack(&pHead,2);
	PushBack(&pHead,3);
	PushBack(&pHead,4);
	//中间节点
	Erase(&pHead,Find(pHead,1));
	Erase(&pHead,Find(pHead,2));
	Erase(&pHead,Find(pHead,3));
	//头节点
	Erase(&pHead,Find(pHead,0));
	//没找到数据的节点
	Erase(&pHead,Find(pHead,12311));
	//尾节点
	Erase(&pHead,Find(pHead,4));
	//空链表
	Erase(&pHead,Find(pHead,1123));
}
void Test_RemoveAll(){
	PNode pHead;
	InitList(&pHead);
	PushBack(&pHead,0);
	PushBack(&pHead,1);
	PushBack(&pHead,2);
	//头节点删除
	RemoveAll(&pHead,0);
	//恢复头节点
	PushFront(&pHead,0);
	//中间节点删除
	RemoveAll(&pHead,1);
	//中间节点恢复
	Insert(Find(pHead,0),1);
	//尾节点删除
	RemoveAll(&pHead,2);
	RemoveAll(&pHead,1);
	//即是头节点又是尾节点
	RemoveAll(&pHead,0);
}
void Test_DestroyList(){
	PNode pHead;
	InitList(&pHead);
	PushBack(&pHead,0);
	PushBack(&pHead,1);
	PushBack(&pHead,2);
	DestroyList(&pHead);
}
int main(){
	//Test_InitList();
	//Test_PushBack();
	//Test_PopBack();
	//Test_PushFront();
	//Test_PopFront();
	//Test_Find();
	//Test_Insert();
	//Test_PrintList();
	//Test_Erase();
	//Test_RemoveAll();
	//Test_DestroyList();
	return 0;
}

中秋快乐!!!

上一篇:
下一篇: