单链表（不带头结点）

不带头结点的节点因为插入删除的时候会改变或者删除第一个节点，所以要引入二级指针进行一系列的操作

---

头文件

#pragma once
//不带头结点的单链表
typedef struct Node
{
	int data;//数据
	Node * next;//存放下一个元素的地址
}Node;
//初始化
void InitList(Node **ps);
//头插
bool Insert_Head(Node **ps,int val);
//尾插
bool Insert_Tail(Node **ps,int val);
//按位置插入
bool Insert_Pos(Node **ps,int pos,int val);
//删除某个节点
bool Delete_Node(Node **ps,int key);
//删除整个链表
bool Delete_List(Node **ps);
//查找
Node *Search(Node *ps,int key);
//链表长度
int GetLength(Node *ps);
//打印链表的值
void Show(Node* ps);

---

cpp文件

#include<iostream>
#include<assert.h>
#include"NoList.h"
using namespace std;

void InitList(Node* *ps)
{
	assert(ps != NULL);
	*ps = NULL;
}

static Node* BuyNode(int val)
{
	Node *pnewnode = new Node();
	pnewnode->data = val;
	pnewnode->next = NULL;
	return pnewnode;
}
bool Insert_Head(Node* *ps,int val)
{
	assert(ps != NULL);
	Node* pnewnode = BuyNode(val);
	pnewnode->next = *ps;
	*ps = pnewnode;
	return true;
}

bool Insert_Tail(Node* *ps,int val)
{
	assert(ps != NULL);
	Node* pnewnode = BuyNode(val);
	Node* pTail = *ps;
	if(pTail == NULL)
	{
		*ps = pnewnode;//////
	}
	else
	{	
		while(pTail->next != NULL)
		{
			pTail = pTail->next;
		}
		pTail->next = pnewnode;
	}
	return true;
}

bool Insert_Pos(Node* *ps,int pos,int val)
{
	assert(ps != NULL);
	Node * q = *ps;
	for(int i = 0;i<pos;i++)
	{
		q = q->next;
	}
	Node *p =BuyNode(val);
	p->next = q->next;
	q->next = p;
	return true;
}

bool Delete_Node(Node* *ps,int key)
{
	assert(ps != NULL);
	Node* p = Search(*ps,key);
	if(p == NULL)
	{
		return false;
	}
	//删除的节点是第一个节点也是最后一个节点
	if(p == *ps)
	{
		delete p;
		p = NULL;/////////////
		ps = NULL;/////////////
	}
	//删除的节点不是尾结点
	else if(p->next != NULL)
	{
		Node * q = p->next;
		p->data = q->data;
		p->next = q->next;

		delete q;
		q = NULL;
	}
	//节点有很多，删除的节点是尾结点
	else if(p ->next == NULL)
	{
		Node* q = *ps;
		for(;q->next!= NULL;q = q->next);

		/*q ->next = NULL;
		q->next ->data = NULL;
		delete (q->next);*/

		q ->next = NULL;
		delete (q->next);
		p = NULL;
	}
	return true;
}

bool Delete_List(Node* *ps)
{
	assert(ps != NULL);
	Node* p;
	//Node* q = p;
	while(*ps != NULL)
	{
		p = *ps;
		*ps = p->next;
		delete p;
	}
	return true;
}

Node* Search(Node* ps,int key)
{
	assert(ps != NULL);
	Node * q  = ps;
	while(q != NULL)
	{
		if(key == q->data)
		{
			return q;
		}
		q = q->next;
	}
	return NULL;
}

int GetLength(Node *ps)
{
	assert(ps != NULL);
	int length = 0;
	for(Node* q = ps;q!= NULL;q = q->next)
	{
		length++;
	}
	return length;
}

void Show(Node* ps)
{
	for(Node *q = ps;q!= NULL;q= q->next)
	{
		cout << q->data << " " ;
	}
	cout <<endl;
}

---

主函数

#include<iostream>
#include<assert.h>
#include"NoList.h"
using namespace std;

int main()
{
	Node* head;
	InitList(&head);

    /*
	for(int i = 0;i<10;i++)
	{
		Insert_Head(&head,i);
	}
    */

	for(int i = 0;i<10;i++)
	{
		Insert_Tail(&head,i,i);
	}
	Show(*&head);
	cout << GetLength(head) << endl;

	Insert_Pos(&head,5,111);
	Show(*&head);
	cout << GetLength(head) << endl;

	Delete_Node(&head,5);
	Show(head);
	cout << GetLength(head) << endl;

	Delete_List(&head);
	Show(head);
	return 0;
}