[数据结构与算法]2021-09-08

链表

struct Student
{
char name[20];
struct B // 上面有名字 底下没有 不占空间 结构体定义==数据类型
// 24字节 数据类型不占空间
{
int a;
};
int age;
};

struct Student
{
char name[20];
struct // 上面没有名字 底下有 占空间
// 28字节
{
int a;
}B;
int age;
};

struct Student
{
char name[20];
struct B // 上面有名字 底下有 占空间
// 28字节
{
int a;
}B;
int age;
};

struct Student
{
char name[20];
struct // 上面没有名字 底下没有 占空间
// 28字节
{
int a;
};
int age;
};

双向链表
为什么要有双向链表？ 因为单链表有自身局限性（只能向后跑，不也能向前跑）
双向链表是啥？ 和单链表相比，多了一个直接前驱指针

特殊情况（容易出错的点）：
正常来说单链表需要处理2根线 而双向链表需要处理4根线
但是头插函数比较特殊，需要防止出现空链表导致少处理一根线
按位置删除函数也比较特殊，有可能删除的是最后一个节点
头删函数比较特殊 有可能只有一个有效节点需要删除

如果需要前驱 一般用于插入和删除操作等等
for(DNode *p=plist; p->next!=NULL; p=p->next);
如果不需要前驱 一般用于查找和打印
for(DNode *p=plist->next; p!=NULL; p=p->next);

dlist.h

#pragma once

typedef int ELEMTYPE;
typedef struct DNode
{
	int data;//数据域
	struct DNode* next;//直接后继指针；
	struct DNode* prior;//新添加的：直接前驱指针
}DNode,*PDNode;
//双向链表的函数声明:
//增删改查

//初始化
void Init_dlist(PDNode plist);//Node * == PDNode

//头插
bool Insert_head(PDNode plist, int val);

//尾插
bool Insert_tail(PDNode plist, int val);

//按位置插入  pos  
bool Insert_pos(PDNode plist, int pos, int val);

//头删
bool Del_head(PDNode plist);

// 尾删
bool Del_tail(PDNode plist);

//按位置删除 pos 
bool Del_pos(PDNode plist, int pos);

//按值删除 遇到值为val的第一个有效节点 删除掉 释放其内存
bool Del_val(PDNode plist, int val);

//查找search 查找值我val的第一个节点，返回其地址
struct DNode* Search(PDNode plist, int val);

//寻找值为val的节点的前驱
PDNode Get_prior(PDNode plist, int val);

//寻找值为val的节点的后继
PDNode Get_next(PDNode plist, int val);

//判空
bool IsEmpty(PDNode plist);

dlist.cpp

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

//初始化
void Init_dlist(PDNode plist)//Node * == PDNode
{
	assert(plist != NULL);
//	plist->data; 不使用  所以不需要初始化
	plist->next = NULL;
	plist->prior =NULL;
}

//头插
bool Insert_head(PDNode plist, int val)
{
	assert(plist != NULL);
	//1.创造新结点
	DNode* pnewnode = (DNode*)malloc(sizeof(DNode) * 1);
	assert(pnewnode != NULL);
	pnewnode->data = val;
	//2.找到合适的插入位置
	// 这个函数是头插 所以这一步不做处理
	//3.插入(双向链表的头插比较特殊，因为有可能只需要修改3条线）
	//3.1先处理自身两条线
	//3.2再处理特殊的那条线（下一个结点的前驱线）
	//3.3再处理头结点的next线
	pnewnode->next = plist->next;
	pnewnode->prior = plist;
	if (plist->next != NULL)
	{
		plist->next->prior = pnewnode;
	}
	plist->next = pnewnode;
	/*  这个代码正确
	pnewnode->next = plist->next;
	pnewnode->prior = plist;
	plist->next = pnewnode;
	//特殊的一步：有可能是个空链表，导致不需要更改下一个结点的前驱
	if (pnewnode->next != NULL)
	{
		pnewnode->next->prior = pnewnode;
	}
	*/
	return true;
}

//尾插
bool Insert_tail(PDNode plist, int val)
{
	assert(plist != NULL);
	//申请新节点
	DNode* pnewnode = (DNode*)malloc(sizeof(DNode) * 1);
	assert(pnewnode != NULL);
	pnewnode->data = val;
	//找到插入位置
	DNode* p = plist;
	for (p; p->next != NULL; p = p->next);
		//插入
		pnewnode->next = p->next;//pnewnode->next=NULL;
		pnewnode->prior = p;
		p->next = pnewnode;
		return true;
}

//按位置插入  pos  
bool Insert_pos(PDNode plist, int pos, int val)
{
	assert(plist != NULL);
	if (pos<0 || pos>Get_length(plist))
		return false;
	//1.申请新节点
	DNode* pnewnode = (DNode*)malloc(sizeof(DNode) * 1);
	assert(pnewnode != NULL);
	pnewnode->data = val;
	//2.找到插入位置 pos
	DNode* p = plist;
	for (int i = 0; i < pos; i++)
	{
		p = p->next;
	}
	//3. 插入
	pnewnode->next = p->next;
	pnewnode->prior = p;
	if (p->next != NULL)
	{
		p->next->prior = pnewnode;
	}
	p->next = pnewnode;
	return true;
}


//头删  需要更改两条线 第三条和第四条
bool Del_head(PDNode plist)
{
	assert(plist != NULL && plist->next != NULL);
	if (plist == NULL || plist->next == NULL)
		return false;
	DNode* p = plist->next;
	if (p->next != NULL)
	{
		p->next->prior = plist;//第三条线
	}
	plist->next = p->next;//第四条线
	free(p);
	p = NULL;
	return true;
}


//尾删
bool Del_tail(PDNode plist)
{
	assert(plist != NULL);
	//找到删除的结点
	DNode* p = plist;
	for (p; p->next != NULL; p = p->next);//这里for循环执行完 p指向最后一个节点
	//删除：1.变更连线 2.以及释放内存
		p->prior->next = NULL;
	free(p);
	p = NULL;
	return true;
}
//按位置删除 pos 
bool Del_pos(PDNode plist, int pos)
{
	assert(plist != NULL);
	if (pos < 0 || pos >= Get_length(plist))
		return false;
	//1.找到删除的结点
	DNode* p = plist;
	for (int i = 0; i <=pos; i++)
	{
		p = p->next;
	}//此时for循环执行完毕后 p不再是指向待删除结点的前驱，而是直接指向待删除结点

	//2.删除：1.更改连线 2.释放内存
	if (p->next != NULL)//如果待删除结点的下一个节点存在
	{
		p->next->prior = p->prior;
	}
	p->prior->next = p->next;
	free(p);
	p = NULL;
	return true;
}

//按值删除 遇到值为val的第一个有效节点 删除掉 释放其内存
bool Del_val(PDNode plist, int val)
{
	assert(plist != NULL);
	//1.通过search函数找到这个值为val的节点
	DNode* p = Search(plist, val);
	if (p == NULL)
	{
		return false;
	}
	//2.删除
	if (p->next != NULL)//如果待删除结点的下一个节点存在
	{
		p->next->prior = p->prior;
	}
	p->prior->next = p->next;//更改前驱节点的next域
	free(p);
	p = NULL;
	return true;
}

//查找search 查找值我val的第一个节点，返回其地址
struct DNode *Search(PDNode plist, int val)
{
	assert(plist != NULL);
	DNode* p = plist->next;
	for (p; p != NULL; p = p->next)
	{
		if (p->data == val)
		{
			return p;
		}
	}
	return NULL;
}

//寻找值为val的节点的前驱
PDNode Get_prior(PDNode plist, int val)
{
	assert(plist != NULL);
	DNode* p = Search(plist, val);
	
	return p == NULL ? NULL : p->prior;
}

//寻找值为val的节点的后继
PDNode Get_next(PDNode plist, int val)
{
	assert(plist != NULL);
	DNode* p = Search(plist, val);

	return p == NULL ? NULL : p->next;
}

//判空
bool IsEmpty(PDNode plist)
{
	assert(plist != NULL);
	return plist->next == NULL;
}


//获取其有效值长度
int Get_length(PDNode plist)
{
	assert(plist != NULL);
	int count = 0;
	for (DNode* p = plist->next; p != NULL; p = p->next)
	{
		count++;
	}
	return count;
}

//清空
void Clear(PDNode plist)
{
	Destroy(plist);
}

//销毁 不需要更改下一个节点的前驱  只需要沿着next这条线全部释放掉即可
//1.一直头删  2.不需要头结点参与释放
//第一种方法简单：原因是第一种方法只使用了一个临时指针，而第二种方法使用了两个临时指针
void Destroy(PDNode plist)
{
	assert(plist != NULL);
	while (plist->next != NULL)
	{
		DNode* p = plist->next;
		plist->next = p->next;
		free(p);
	}
}
void Destroy2(PDNode plist)
{
	assert(plist != NULL);
	DNode* p = plist->next;
	DNode* q = NULL;
	plist->next = NULL;
	while (p != NULL)
	{
		q = p->next;
		free(p);
		p = q;
	}
}

//打印
void Show(PDNode plist)
{
	for (DNode* p = plist->next; p != NULL; p = p->next)
	{
		printf("%d", p->data);
	}
	printf("\n");
}

循环链表

循环链表，将单链表中终端结点的指针由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

clist.h

//clist == circle list
#pragma once

//循环链表（相比较单链表，唯一的区别，就是让最后一个节点的next域不再指向NULL，而是指向头结点）

//循环链表的结构体定义
typedef int ELEM_TYPE;
typedef struct CNode
{
	ELEM_TYPE data;
	struct CNode* next;
}CNode, * PClist;

//循环链表可执行的操作：（增删改查）
//初始化
void Init_clist(PClist pl);

//头插
bool Insert_head(PClist pl, int val);

//尾插
bool Insert_tail(PClist pl, int val);

//按位置插入
bool Insert_pos(PClist pl, int pos, int val);

//头删
bool Del_head(PClist pl);

//尾删
bool Del_tail(PClist pl);

//按位置删除
bool Del_pos(PClist pl, int pos);

//按值删除，删除遇到的第一个值为val的节点 如果值为val的节点不存在，则返回false
bool Del_val(PClist pl, int val);

//查找  查找值为val的第一个节点，找到则返回其节点地址，否则返回NULL
struct CNode* Search(PClist pl, int val);

//判空
bool IsEmpty(PClist pl);

//获取循环链表有效元素个数
int Get_length(PClist pl);

//打印
void Show(PClist pl);

//清空
void Clear(PClist pl);

//销毁1 一直头删的方式释放内存
void Destroy(PClist pl);

//销毁2
void Destroy2(PClist pl);

//寻找值为val的节点的前驱
PClist Get_prior(PClist pl, int val);

//寻找值为val的节点的后继
PClist Get_next(PClist pl, int val);

clist.cpp

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"clist.h"

//初始化
void Init_clist(PClist pl)
{
	assert(pl != NULL);
	if (pl == NULL)
		return;

	//pl->data; 头结点的数据域不使用
	pl->next = pl;
}

//头插
bool Insert_head(PClist pl, int val)
{
	//assert pl

	//1.申请新节点
	CNode* pnewnode = (CNode*)malloc(sizeof(CNode) * 1);
	assert(pnewnode != NULL);
	pnewnode->data = val;

	//2.找到合适的插入位置
	//因为是头插函数 所以不需要找它的插入位置

	//3.插入
	pnewnode->next = pl->next;
	pl->next = pnewnode;

	return true;
}

//尾插
bool Insert_tail(PClist pl, int val)
{
	//assert
	//1.申请新节点
	CNode* pnewnode = (CNode*)malloc(sizeof(CNode));
	assert(pnewnode != NULL);
	pnewnode->data = val;

	//2.找到合适的插入位置
	CNode* p = pl;
	for (p; p->next != pl; p = p->next);//for循环执行完毕后 p就指向了最后一个节点

	//3.插入
	pnewnode->next = p->next;//pnewnode->next = pl;
	p->next = pnewnode;

	return true;
}

//按位置插入
bool Insert_pos(PClist pl, int pos, int val)
{
	//assert pl pos
	if (pos<0 || pos>Get_length(pl))
		return false;

	//1.申请新节点
	CNode* pnewnode = (CNode*)malloc(sizeof(CNode) * 1);
	assert(pnewnode != NULL);
	pnewnode->data = val;

	//2.找到合适的插入位置
	CNode* p = pl;
	for (int i = 0; i < pos; i++)
	{
		p = p->next;
	}

	//3.插入
	pnewnode->next = p->next;
	p->next = pnewnode;

	return true;
}

//头删
bool Del_head(PClist pl)
{
	//assert

	//1.找到删除节点的前驱
	if (pl->next == pl)
		return false;

	//2.删除节点（2.1改变节点指向 2.2释放内存）
	CNode* p = pl->next;
	pl->next = p->next;
	free(p);
	p = NULL;

	return true;
}

//尾删
bool Del_tail(PClist pl)
{
	assert(pl != NULL && pl->next != pl);//断言头结点存在  断言不能光头结点存在
	if (pl == NULL || pl->next == pl)
	{
		return false;
	}

	//1.找到删除节点的前驱  走一步看两步
	CNode* p = pl;
	for (p; p->next != pl; p = p->next)//走一步
	{
		if (p->next->next == pl)//看两步
		{
			break;//for while  switch
		}
	}
	//2.删除节点
	CNode* q = p->next;
	p->next = q->next;//p->next = pl;
	free(q);
	q = NULL;

	return true;
}

//按位置删除
bool Del_pos(PClist pl, int pos)
{
	//assert pl pos
	if (pl == NULL || pos < 0 || pos >= Get_length(pl))
		return false;

	//1.找到删除节点的前驱
	CNode* p = pl;
	for (int i = 0; i < pos; i++)
	{
		p = p->next;
	}

	//2.删除
	CNode* q = p->next;
	p->next = q->next;
	free(q);
	q = NULL;

	return true;
}

//按值删除，删除遇到的第一个值为val的节点 如果值为val的节点不存在，则返回false
bool Del_val(PClist pl, int val)
{
	//assert
	//1.通过调用Get_prior函数来获取删除节点的前驱
	CNode* p = Get_prior(pl, val);
	if (p == NULL)
	{
		return false;
	}
	//2.删除

	CNode* q = p->next;
	p->next = q->next;
	free(q);
	q = NULL;

	return true;
}

//查找  查找值为val的第一个节点，找到则返回其节点地址，否则返回NULL
struct CNode* Search(PClist pl, int val)
{
	//assert
	CNode* p = pl->next;
	for (p; p != pl; p = p->next)
	{
		if (p->data == val)
		{
			return p;
		}
	}
	return NULL;
}

//判空
bool IsEmpty(PClist pl)
{
	//return pl->next == NULL; 单链表的判空
	return pl->next == pl;//循环链表的判空
}

//获取循环链表有效元素个数
int Get_length(PClist pl)
{
	//assert
	int count = 0;
	for (CNode* p = pl->next; p != pl; p = p->next)
	{
		count++;
	}
	return count;
}

//打印
void Show(PClist pl)
{
	//assert
	for (CNode* p = pl->next; p != pl; p = p->next)
	{
		printf("%d ", p->data);
	}
	printf("\n");
}

//清空
void Clear(PClist pl)
{
	Destroy(pl);
}

//销毁1 一直头删的方式释放内存
void Destroy(PClist pl)
{
	//assert
	while (pl->next != pl)
	{
		CNode* p = pl->next;
		pl->next = p->next;
		free(p);
	}
}

//销毁2
void Destroy2(PClist pl)
{
	//assert
	assert(pl != NULL && pl->next != pl);

	CNode* p = pl->next;
	CNode* q = NULL;

	while (p != pl)
	{
		q = p->next;
		free(p);
		p = q;
	}

	pl->next = pl;
}

//寻找值为val的节点的前驱
PClist Get_prior(PClist pl, int val)
{
	//assert
	CNode* p = pl;
	for (p; p->next != pl; p = p->next)
	{
		if (p->next->data == val)
		{
			return p;
		}
	}
	return NULL;
}

//寻找值为val的节点的后继
PClist Get_next(PClist pl, int val)
{
	//assert
	CNode* p = Search(pl, val);
	/*if(p == NULL)
		return NULL;
	return p->next;*/

	return p == NULL ? NULL : p->next;
}

双向循环链表
双向循环链表和双向链表的区别:
1.最后一个节点的next指针不再指向NULL 而是指向头结点
2.头结点的prior指针不再指向NULL，而是指向尾结点

dclist.h

#pragma once
typedef int ELEM_TYPE;
typedef struct DCList
{
	ELEM_TYPE data;//数据域
	struct DCList* next;//后继指针
	struct DCList* prior;//前驱指针
}DCList, * PDClist;

//循环链表可执行的操作：（增删改查）
//初始化
void Init_dclist(PDClist pl);

//头插
bool Insert_head(PDClist pl, int val);

//尾插
bool Insert_tail(PDClist pl, int val);

//按位置插入
bool Insert_pos(PDClist pl, int pos, int val);

//头删
bool Del_head(PDClist pl);

//尾删
bool Del_tail(PDClist pl);

//按位置删除
bool Del_pos(PDClist pl, int pos);

//按值删除，删除遇到的第一个值为val的节点 如果值为val的节点不存在，则返回false
bool Del_val(PDClist pl, int val);

//查找  查找值为val的第一个节点，找到则返回其节点地址，否则返回NULL
PDClist Search(PDClist pl, int val);

//判空
bool IsEmpty(PDClist pl);

//获取循环链表有效元素个数
int Get_length(PDClist pl);

//打印
void Show(PDClist pl);

//清空
void Clear(PDClist pl);

//销毁1 一直头删的方式释放内存
void Destroy(PDClist pl);

//销毁2
void Destroy2(PDClist pl);

//寻找值为val的节点的前驱
PDClist Get_prior(PDClist pl, int val);

//寻找值为val的节点的后继
PDClist Get_next(PDClist pl, int val);

dclist.cpp

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


//循环链表可执行的操作：（增删改查）
//初始化
void Init_dclist(PDClist pl)
{
	assert(pl != NULL);
	if (NULL == pl)
		return;

	//pl->data; 头结点的数据域不使用 浪费掉
	pl->next = pl;
	pl->prior = pl;
}

DCList* BuyNode(int val)
{
	DCList* pnewnode = (DCList*)malloc(sizeof(DCList) * 1);
	assert(pnewnode != NULL);
	pnewnode->data = val;
	pnewnode->next = NULL;
	pnewnode->prior = NULL;

	return pnewnode;
}
//头插
bool Insert_head(PDClist pl, int val)
{
	//1.assert
	assert(pl != NULL);
	if (pl == NULL)
		return false;
	//2.申请新节点
	DCList* pnewnode = BuyNode(val);
	assert(pnewnode != NULL);

	//3.插入
	pnewnode->next = pl->next;
	pnewnode->prior = pl;

	if (pl->next != pl)//证明在头插之前，就至少存在一个有效节点
	{
		pl->next->prior = pnewnode;
	}

	pl->next = pnewnode;

	//下面的代码是对比双向链表新加入的代码
	if (pl->prior == pl)//（1.如果插入之前就有有效节点，则这个指针不需要修改 2.如果是个空的链表，则这个指针需要做修改）
	{
		pl->prior = pnewnode;//是让pl->prior 永远指向最后一个节点
	}

	return true;
}

//尾插
bool Insert_tail(PDClist pl, int val)
{
	//1.assert
	//2.创建新节点
	DCList* pnewnode = BuyNode(val);
	assert(pnewnode != NULL);

	//3.找到合适的插入位置
	DCList* p = pl;
	for (pl; p->next != pl; p = p->next);
	//此时 for循环执行结束，代表指针p此时指向最后一个节点

	//4.插入节点
	pnewnode->next = p->next;//pnewnode->next = pl;
	pnewnode->prior = p;

	p->next = pnewnode;

	//下面的代码是对比双向链表新加入的代码
	pl->prior = pnewnode;//因为是尾插函数，所以每次都得让pl->prior重新指向最后一个有效节点（新插入的节点）

	return true;
}

//按位置插入
bool Insert_pos(PDClist pl, int pos, int val)
{
	//1.assert  pl pos
	//2.申请新的节点
	DCList* pnewnode = BuyNode(val);
	assert(pnewnode != NULL);

	//3.找到合适的插入位置
	DCList* p = pl;
	for (int i = 0; i < pos; i++)
	{
		p = p->next;
	}

	//4.插入
	pnewnode->next = p->next;
	pnewnode->prior = p;
	if (p->next != pl)
	{
		p->next->prior = pnewnode;
	}
	else///else的代码是对比双向链表新加入的代码
	{
		pl->prior = pnewnode;
	}

	p->next = pnewnode;

	return true;
}

//头删
bool Del_head(PDClist pl)
{
	//1.assert
	assert(pl != NULL && pl->next != pl);
	if (pl == NULL || pl->next == pl)
	{
		return false;
	}

	//2.找到删除的位置
	//3.删除
	DCList* p = pl->next;
	if (p->next == pl)//删除的节点就是仅存的节点
	{
		pl->next = pl->prior = pl;
		free(p);
		p = NULL;
	}
	else//删除的节点不是仅存的节点
	{
		pl->next = p->next;
		p->next->prior = pl;
		free(p);
		p = NULL;
	}

	return true;
}

//尾删
bool Del_tail(PDClist pl)
{
	//1.assert
	//2.找到删除的位置
	DCList* p = pl;
	for (p; p->next != pl; p = p->next);
	//此时 for循环执行结束，代表指针p此时指向最后一个节点

	//3.删除
	if (pl->next == p)//if(p->prior == pl)//删除的节点就是仅存的节点//
	{
		pl->next = pl;
		pl->prior = pl;
	}
	else//删除的节点不是仅存的节点
	{
		p->prior->next = pl;//删除节点的上一个节点的next域指向头结点
		pl->prior = p->prior;//让头节点的前驱指针指向新的最后一个节点（删除节点的上一个节点）
	}

	free(p);
	p = NULL;
	return true;
}


//按位置删除
bool Del_pos(PDClist pl, int pos)
{
	//assert pl pos

	if (pos == 0)
		return Del_head(pl);
	if (pos == Get_length(pl) - 1)
		return Del_tail(pl);

	//此时 剩下的情况都是中间节点删除
	DCList* p = pl;
	for (int i = 0; i < pos; i++)
	{
		p = p->next;
	}

	DCList* q = p->next;//q 指向的就是删除的节点本身
	p->next = q->next;
	q->next->prior = p;
	free(q);
	q = NULL;

	return true;
}

//按值删除，删除遇到的第一个值为val的节点 如果值为val的节点不存在，则返回false
bool Del_val(PDClist pl, int val)
{
	//assert
	DCList* p = Search(pl, val);
	if (p == NULL)
	{
		return false;
	}

	//这两行代码  兼容任何情况 
	p->prior->next = p->next;
	p->next->prior = p->prior;
	free(p);
	p = NULL;

	return true;
}

//查找  查找值为val的第一个节点，找到则返回其节点地址，否则返回NULL
PDClist Search(PDClist pl, int val)
{
	//assert
	DCList* p = pl->next;
	for (p; p != pl; p = p->next)
	{
		if (p->data == val)
		{
			return p;
		}
	}

	return NULL;
}

//判空
bool IsEmpty(PDClist pl)
{
	return pl->next == pl;
}

//获取循环链表有效元素个数
int Get_length(PDClist pl)
{
	int count = 0;
	DCList* p = pl->next;
	for (p; p != pl; p = p->next)
	{
		count++;
	}

	return count;
}

//打印
void Show(PDClist pl)
{
	DCList* p = pl->next;
	for (p; p != pl; p = p->next)
	{
		printf("%d ", p->data);
	}
	printf("\n");
}

//清空
void Clear(PDClist pl)
{
	Destroy(pl);
}

//销毁1 一直头删的方式释放内存
void Destroy(PDClist pl)
{
	while (pl->next != pl)
	{
		DCList* p = pl->next;
		pl->next = p->next;
		free(p);
		p = NULL;
	}

	pl->prior = pl;
}

//销毁2
void Destroy2(PDClist pl)
{
	DCList* p = pl->next;
	DCList* q;

	while (p != pl)
	{
		q = p->next;
		free(p);
		p = q;
	}

	pl->next = pl;
	pl->prior = pl;
}

//寻找值为val的节点的前驱
PDClist Get_prior(PDClist pl, int val)
{
	DCList* p = Search(pl, val);
	if (p == NULL)
	{
		return NULL;
	}

	return p->prior;
}

//寻找值为val的节点的后继
PDClist Get_next(PDClist pl, int val)
{
	DCList* p = Search(pl, val);
	if (p == NULL)
	{
		return NULL;
	}

	return p->next;
}