[数据结构与算法]不带头结点的单链表实现示例（C语言）

不带头结点的单链表实现示例（C语言）

大部分代码为参考代码，在此基础上做了以下修改
代码较长，需耐心观看
其中   LinkList*  等价于 Lnode**       这俩个使用哪一个都可以，前提是在声明结构体的时候要加上。
修改的地方有：
	在指定位置插入一个元素
	删除指定位置的元素
	打印链表更加合理

心得：
最重要的还是懂得原理
如何创建一个不带头结点的链表
如何实现增、删、改、查、打印等功能
重点还是原理。
不行就画图，慢慢理清逻辑，下一次不就会了嘛
加油！

#include<stdio.h>
#include<assert.h>
#include<malloc.h>

//不带头节点的单链表

typedef int DataType;   //数据类型

typedef struct LinkNode
{
	DataType _data;          //数据域
	struct LinkNode *_pNext;  //指针域
}Lnode, *LinkList;

void LinkListInit(LinkList* pHead);   //链表初始化

Lnode* LinkListCreatNode(DataType data);  //创建新节点

void LinkListDestoryNode(LinkList* pHead); //销毁节点

void LinkListPrint(LinkList* pHead);   //遍历打印节点

void LinkListPushBack(LinkList* pHead, DataType data);  //尾插

void LinkListPopBack(LinkList* pHead);  //尾删

void LinkListPushFront(LinkList* pHead, DataType data);  //头插

void LinkListPopFront(LinkList* pHead);  //头删

int LinkListSize(LinkList* pHead);   //求链表长度

void LinkListDestory(LinkList* pHead);   //销毁链表

void LinkList_Insert_anysite(LinkList* pHead, DataType data, DataType pos);  //任意位置插入

void LinkList_del_anysite(LinkList* pHead,  DataType pos);  //任意位置删除

int LinkListEmpty(LinkList* pHead);   //判空


void LinkListInit(LinkList* pHead)   //链表初始化
{
	assert(pHead);
	*pHead = NULL;
}

Lnode* LinkListCreatNode(DataType data)  //创建新节点
{
	Lnode* pNewNode = (Lnode*)malloc(sizeof(Lnode));
	assert(pNewNode);

	pNewNode -> _data = data;
	pNewNode -> _pNext = NULL;
	return pNewNode;
}

void LinkListDestoryNode(LinkList* pHead) //销毁节点
{
	free(pHead);
	*pHead = NULL;
}

void LinkListPrint(LinkList* pHead)   //遍历打印节点
{
	Lnode* pCur = *pHead;
	for(pCur; pCur != NULL; pCur = pCur -> _pNext)
	{
		if(pCur -> _pNext != NULL)
		{
			printf("%d----->", pCur -> _data);
		}
		else
		{
			printf("%d\n", pCur -> _data);
		}
	}
}

void LinkListPushBack(LinkList* pHead, DataType data)  //尾插
{
	Lnode* NewNode = LinkListCreatNode(data);
	assert(pHead);
	 //如果链表为空，则直接让头指针指向新申请的节点即可
	if(*pHead == NULL)
	{
		*pHead = NewNode;
		return;
	}
	//否则从头开始遍历链表，直到当前节点的指针域指向NULL，然后让当前节
    //点的指针域指向新申请的节点即可
	Lnode* pTail = *pHead;
	while(pTail -> _pNext)
	{
		pTail = pTail -> _pNext;
	}
	pTail -> _pNext = NewNode;
}

void LinkListPopBack(LinkList* pHead)  //尾删
{
	assert(pHead);
	if(*pHead == NULL)
	{
		printf("链表为空！，删除失败！\n");
		return;
	}
   //如果当前只有一个结点，则释放该结点,
    //并将头指针指向NULL，防止出现野指针--相当于销毁结点
    if((*pHead) -> _pNext == NULL)
    {
    	free(pHead);
    	*pHead = NULL;
    }
     //定义两个指针，依次向后走
    //pTail不为空时，将其前一个结点指针pPreTail赋给pTail
    //当pTail为空时，释放pTail，pPreTail指向NULL
    Lnode* pTail = *pHead;
    Lnode* pPreTail = NULL;
    while(pTail -> _pNext)
    {
    	pPreTail = pTail;
    	pTail = pTail -> _pNext;
    }
    free(pTail);
    pPreTail -> _pNext = NULL;
}

void LinkListPushFront(LinkList* pHead, DataType data)  //头插
{
	assert(pHead);
	Lnode* NewNode = LinkListCreatNode(data);
	NewNode -> _pNext = (*pHead);
	*pHead = NewNode;
}

void LinkListPopFront(LinkList* pHead)  //头删
{
	Lnode* pDel = NULL;
	assert(pHead);
	if((*pHead) == NULL)
	{
        printf("链表为空！无法删除！\n");
        return;
	}
	pDel = *pHead;
	*pHead = pDel -> _pNext;
	free(pDel);
}

int LinkListSize(LinkList* pHead)   //求链表长度
{
	assert(pHead);
	Lnode* pSize = *pHead;
	int count = 0;
	while(pSize != NULL)
	{
		pSize = pSize -> _pNext;
		count++;
	}
	return count;
}

void LinkListDestory(LinkList* pHead)   //销毁链表
{
	assert(pHead);
	Lnode* pDpre = NULL;
	Lnode* pD = *pHead;
	 //定义两个指针同时向链尾走，pD不为空时，用pDpre标记pD
    //pD不断向后移同时释放pDpre，直至将整个链表结点全部释放
    while(pD)
    {
    	pDpre = pD;
    	pD = pD -> _pNext;
    	free(pDpre);
    }
     //切记将头指针指向空，不然将变成野指针
    *pHead = NULL;
}

void LinkList_Insert_anysite(LinkList* pHead, DataType data, DataType pos)  //任意位置插入
{
	assert(pHead);
	Lnode* pNewNode = LinkListCreatNode(data);

	//链表为空
	if(*pHead == NULL)
	{
		*pHead = pNewNode;
		return;
	}
	//在头部插入
	if(pos == 1)
	{
		LinkListPushFront(pHead, data);
		return;
	}
	if(pos > LinkListSize(pHead))
	{
		printf("插入位置有误！\n");
		return;
	}
    Lnode* pCur = *pHead;
    int i = 2;
    while(pCur -> _pNext != NULL)
    {
    	if(i == pos)
    	{
    		pNewNode -> _pNext = pCur -> _pNext;
    		pCur -> _pNext = pNewNode;
    	}
    	pCur = pCur -> _pNext;
    	i++;
    }
    return;
}

void LinkList_del_anysite(LinkList* pHead, DataType pos)  //任意位置删除
{
	assert(pHead);

    //考虑链表为空
    if ((*pHead) == NULL)
    {
        printf("链表为空！无法删除！\n");
        return;
    }

    if (pos == 1)
    {
        LinkListPopFront(pHead);
        return;
    }

    if(pos > LinkListSize(pHead))
	{
		printf("插入位置有误！\n");
		return;
	}

    int i = 1;
    Lnode* pE = *pHead;
    while ( pE != NULL)
    {
        if (pE->_pNext != NULL)
        {
            i++;
            if(i == pos)
            {
            	Lnode* p = pE->_pNext;
            	pE -> _pNext = pE -> _pNext -> _pNext;
            	free(p);
            }
            return;
        }
        pE = pE->_pNext;
        i++;    
    }
    return;
}

int LinkListEmpty(Lnode** pHead)   //判空
{
	assert(pHead);
    return ((*pHead) == NULL);
}

void LinkListTest()
{
    LinkList p;
    LinkListInit(&p);
    for(int i =1; i < 6; i++)
    {
    	LinkListPushBack(&p, i);
    }
    LinkListPushBack(&p, 5);
    LinkListPrint(&p);

    LinkListPopBack(&p);
    LinkListPrint(&p);

    LinkListPushFront(&p, 5);
    LinkListPushFront(&p, 6);
    LinkListPrint(&p);

    LinkListPopFront(&p); 
    LinkListPopFront(&p);
    LinkListPrint(&p);

    printf("链表长度为%d\n", LinkListSize(&p));

    LinkList_Insert_anysite(&p,6,4);
    LinkListPrint(&p);

    LinkList_del_anysite(&p,2);
    LinkListPrint(&p);

}
int main()
{
	LinkListTest();
}

结果图：