参考视频 王道2021数据结构

链接： 王道2021数据结构链接
提取码：rpy8
–来自百度网盘超级会员V4的分享

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;

typedef struct LNode{
	ElemType data;
	LNode *next;
}LNode, *LinkList;


//初始化一个空的单链表(不带头结点)
bool IniList(LinkList &L){
	L = NULL;//防止脏数据
	return true;
}
//判断是否为空(不带头结点)
bool Empty(LinkList L){
	return (L = NULL);
}
/*---------------------------------------*/

//初始化一个空的单链表(带头结点)
bool IniList(LinkList &L){
	L = (LNode *)malloc(sizeof(LNode));//分配一个头结点
	if(L == NULL) return false;//内存不足,分配失败
	L->next = NULL;//头结点之后暂时还没有节点
	return true;
}
//判断是否为空(不带头结点)
bool Empty(LinkList L){
	return (L->next = NULL);
}
/*---------------------------------------*/ 
//按位插入(带头结点)06 5:53
bool ListInsert(LinkList &L, int i, ElemType e){
	//判断i是否合法
	if(i < 1) return false;
	//指针p指向当前扫描的节点(从头开始L)
	LNode *p = L;
	//j显示指向的是第几个节点(初始为0)
	int j = 0;
	//用while循环来移动p到第i-1个节点同时还要判断在移动的过程中地址是否为NULL(循环中j<i循环(i-j)次j<=i循环(i-j+1)次)
	while(p != NULL && j < i-1){
		p = p->next;
		j++;
	}
	//判断最后p到达的是否为NULL
	if(p = NULL) return false;
	//malloc申请空间
	LNode *s = (LNode *)malloc(sizeof(LNode));
	//赋值
	s->data = e;
	//将其插入
	s->next = p->next;
	p->next = s;
	//返回
	return true;
} 
//按位插入(不带头结点)06 10:34


//后插操作:在p节点之后插入元素e 13:05
bool InsertNextNode(LNode *p, ElemType e){
	//判断p指向的是否为空
	if(p == NULL) return false;
	//申请节点空间s
	LNode *s = (LNode *)malloc(sizeof(LNode));
	//判断申请是否成功(可以不写)
	if(s == NULL) return fasle;
	//赋值
	s->data = e;
	//插入
	s->next = p->next;
	p->next = s;
	//返回
	return ok;
}
//前插操作:在p节点之前插入元素06 15:28(偷天换日,其实新建节点还是插在原来的后面,只不过值不一样而已)
bool InsertPriorNode(LNode *p, ElemType e){
	//判断p指向是否为空
	if(p == NULL) return false;
	//申请节点空间s
	LNode *s = (LNode*)malloc(sizeof(LNode));
	//判断申请是否成功(可以不写)
	if(s == NULL) return false;
	//将p中数据转移到新建节点s中
	s->data = p->data;
	p->data = e;
	//将插入数据转移到p中a
	s->next = p->next;
	p->next = s;

	return true;
}
/*---------------------------------------------------------*/
//按位删除(带头结点) 06 17:06
bool ListDelete(LinkList &L, int i, ElemType &e){
	//判断i的值是否合法(是否小于1)
	if(i < 1) return false;
	//新建指针p指向L为0
	LNode *p = L;
	//j表示指向第几个节点
	int j = 0;
	//移动位置(如果要删除第i个,则移动到i-1的位置)
	while (p != NULL && j < i-1){
		p = p->next;
		j++;
	}
	//等移动完了之后看p所在位置否合法
	if(p == NULL) return false;
	//再看看要删除的节点,也就是p->next是否合法
	if(p->next == NULL) return false;
	//用q指向要删除的节点
	LNode *q = p->next;
	//将删除节点的值传给e
	e = q->data;
	//将要删除的节点断开
	p->next = q->next;
	//释放删除节点的空间
	free(q);
	//返回结果
	return true;
}

//按指定节点删除(带头结点的)06 19:29(其实删除的不是p,而是p的后继节点,但删除的值是p的,后继节点的值还保留着呢)
bool DeleteNode(LNode *p){
	//先判断p指向是否合法(为空)
	if(p == NULL) return false;
	//获得p节点的后继节点
	LNode *q = p->next;
	//将p的后继节点的值赋给p
	p-> data = q->data;
	//断开p的后继节点
	p->next = q->next;
	//释放断开的节点
	free(q);
	//返回结果
	return true;
}
/*---------------------------------------------------------*/
//按位查找,返回第i个元素(带头结点)07 3:25
LNode * GetElem(LinkList L, int i){
	//判断i是否合法
	if(i < 0) return NULL;
	//新建指针p指向L
	LNode *p = L;
	//j记录到第几个节点
	int j = 0;
	//移动(查找第i个,就要移动i次)
	while(p != NULL && j < i){
		p = p->next;
		j++;
	}
	//返回所查找的
	return p;
}
//按值查找,找到数据域==e的节点(带头结点)07 7:43
LNode * LocateElem(LinkList L, ElemType e){
	//新建节点p指向L的第一个节点
	LNode *p = L->next;
	//从第一个节点查找数据域为e的节点
	while (p != NULL && p->data != e){
		p = p->next;
	}
	//返回(找到后返回该节点指针,扶着返回NULL)
	return p;
}
//求表的长度(带头结点)
int Length(LinkList L){
	int len = 0;
	LNode *p = L;
	while(p->next != NULL){
		p = p->next;
		len++
	}
	return len;
}
/*----------------------------------------------------*/
//尾插法建立单链表(带头结点)08 7:13  尾插法建立头结点之后没有使其指向NULL因为后面会设置表尾指针为空
LinkList List_TailInsert(LinkList &L){
	//设置ElemType为整型
	int x;
	//建立头结点
	//新建r和s指针s为新增指针,r为表尾指针
	//输入节点的值
	//循环插入当输入9999时停止
		//为新增指针s分配内存
		//为s赋值
		//将s尾部插入
		//调整表尾指针r的位置
		//再次输入要插入的值
	//设置表尾指针为空
	//返回
}
//头插发建立单链表08 9:24
LinkList List_HeadInsert(LinkList &L){
	//创建头结点,分配内存空间
	//使头结点指向NULL
	//输入要插入的数据
	//循环插入当输入9999时停止
		//为s新增指针分配内存空间
		//赋值
		//插入(分两步)s插入p->next
		//p->next = s;
		//输入要插入的值
	//返回	
}
int main(void){
	LinkList L;

	InitList(L);

	return 0;
}