欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

单链表(不带头结点)

程序员文章站 2024-03-21 13:11:04
...

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


头文件

#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;
}