[数据结构与算法]线性链表（线性表的单链表存储结构）

目录

一、单链表存储结构

二、基本操作&其他操作的函数定义

1.函数声明（12种基本操作）

2. 基本操作函数定义

(1)创建表

(2)销毁表

(3)清空表

(4)表判空

(5)求表长

(6)按位序取值

(7)按值查找位序

(8)查前驱

(9)查后继

(10)插入元素

(11)删除元素

(12)遍历元素

三、函数测试

四、全部代码

五、总结

一、单链表存储结构

//线性表的单链表存储结构
typedef struct LNode {
	int data;
	struct LNode* next;
}LNODE, *LINKLIST;

*代码段中的结构体定义也可以表示为

struct LNode {
	int data;
	struct LNode* next;
};
typedef struct LNode LNODE;
typedef struct LNode* LINKLIST;

二、基本操作&其他操作的函数定义

1.函数声明（12种基本操作）

//带头结点单链表的基本操作（12种）
LINKLIST InitList(LINKLIST L);                 //创建
void DestroyList(LINKLIST L);                  //销毁
void ClearList(LINKLIST L);                    //清空
bool ListEmpty(LINKLIST L);                    //判空
int ListLength(LINKLIST L);                    //求长度
bool GetElem(LINKLIST L, int i, int* e);       //按位序取值
int LocateElem(LINKLIST L, int e, bool(*compare)(int, int));      //按值查找位序
bool PriorElem(LINKLIST L, int cur_e, int* pre_e);                //查前驱
bool NextElem(LINKLIST L, int cur_e, int* next_e);                //查后继
bool ListInsert(LINKLIST L, int i, int e);                        //插入元素
bool ListDelete(LINKLIST L, int i, int* e);                       //删除元素
void ListTraverse(LINKLIST L, void(*visit)(int));                 //遍历输出链表元素
//几个常用函数
bool equal(int a, int b);              //判断俩元素是否相等
int compare(int a, int b);             //比较俩元素
void print(int a);                     //按十进制数打印元素
void print1(int* a);
void print2(int a);

2. 基本操作函数定义

(1)创建表

LINKLIST InitList(LINKLIST L) {
	L = (LNODE*)malloc(sizeof(LNODE));
	if (!L) {
		printf("内存分配失败!\n");
		exit(1);
	}
	L->data = 0;
	L->next = NULL;
	return L;
}

(2)销毁表

void DestroyList(LINKLIST L) {
	LINKLIST p = NULL;      
	while (L) {       //非空
		p = L->next;
		free(L);
		L = p;
	}
}

(3)清空表

void ClearList(LINKLIST L) {
	LINKLIST p = L->next;       //p指向首结点
	L->next = NULL;            //头结点指针域为空
	DestroyList(p);            //销毁p所指单链表
}

(4)表判空

bool ListEmpty(LINKLIST L) {
	if (L->next) {            //不为空
		return false;
	}
	else {
		return true;
	}
}

(5)求表长

int ListLength(LINKLIST L) {
	LINKLIST p = L->next;      //p指向第一个结点(不存在则为空)
	int i = 0;                 //计数器初值为零
	while (p) {                //未到表尾 NULL
		i++;
		p = p->next;
	}
	return i;
}

(6)按位序取值

bool GetElem(LINKLIST L, int i, int* e) {
	LINKLIST p = L->next;       //p指向第一个结点
	int j = 1;                  //计数器初值为1
	while (p && j < i) {            //循环 i-1 次 p指向第i个结点
		j++;
		p = p->next;
	}
	if (!p || j > i) {               //第i个结点不存在
		printf("第%d个结点不存在\n", i);
		return false;
	}
	*e = p->data;
	return true;
	
}

(7)按值查找位序

int LocateElem(LINKLIST L, int e, bool (*compare)(int, int)) {
	LINKLIST p = L->next;       //指向首结点
	int i = 0;
	while (p) {
		i++;
		if (compare(e, p->data)) {
			return i;
		}
		p = p->next;
	}
	return 0;                   //满足等值关系的结点不存在
}

(8)查前驱

bool PriorElem(LINKLIST L, int cur_e, int* pre_e) {
	int loc = LocateElem(L, cur_e, equal);
	if (0 == loc) {
		printf("链表中不存在值域为%d的结点！\n", cur_e);
		return false;
	}
	else if (1 == loc) {
		printf("链表中值域为%d的结点是首结点，其不存在唯一前驱!", cur_e);
		return false;
	}
	else {
		GetElem(L, loc - 1, pre_e);
		return true;
	}
}

(9)查后继

bool NextElem(LINKLIST L, int cur_e, int* next_e) {
	int loc = LocateElem(L, cur_e, equal);
	if (0 == loc) {
		printf("链表中不存在值域为%d的结点！\n", cur_e);
		return false;
	}
	else if (ListLength(L) == loc) {
		printf("链表中值域为%d的结点是尾结点，其不存在唯一后继!", cur_e);
		return false;
	}
	else {
		GetElem(L, loc + 1, next_e);
		return true;
	}
}

(10)插入元素

bool ListInsert(LINKLIST L, int i, int e) {
	LINKLIST p = L;     //p指向头结点
	LINKLIST s = NULL;
	int j = 0;
	while (p && j < i - 1) {
		j++;
		p = p->next;
	}
	if (!p || j < i - 1) {
		printf("不能在第%d个位置插入结点!\n", i);
		return false;
	}
	s = (LNODE*)malloc(sizeof(LNODE));
	if (!s) {
		printf("内存分配失败!\n");
		exit(1);
	}
	s->next = p->next;
	p->next = s;
	s->data = e;
	return true;
	
}

(11)删除元素

bool ListDelete(LINKLIST L, int i, int* e) {
	LINKLIST p = L;      //p指向头结点
	LINKLIST s = NULL;
	int j = 0;
	while (p->next && j < i - 1) {
		j++;
		p = p->next;
	}
	if (!(p->next) || j < i - 1) {
		printf("不能在第%d个位置删除结点!\n", i);
		return false;
	}
	s = p->next;        //s指向第i个结点
	*e = s->data;
	p->next = s->next;
	free(s);
	return true;
}

(12)遍历元素

void ListTraverse(LINKLIST L, void(*visit)(int)) {
	LINKLIST p = L->next; //p指向头结点
	printf("L = ");
	while (p) {
		visit(p->data);
		p = p->next;
	}
}

三、函数测试

int main() {
	LINKLIST L = NULL;
	int e, e0;
	bool i;
	int j, k;
	L = InitList(L);
	for (j = 1; j <= 5; j++) {
		i = ListInsert(L, 1, j);
	}
	printf("在L的表头依次插入1-5后，");
	ListTraverse(L, print);
	printf("\n");
	i = ListEmpty(L);
	printf("表是否为空?");
	if (i) {
		printf(" True!");
		printf(" 表的长度 = %d\n", ListLength(L));
	}
	else {
		printf(" False!");
		printf(" 表的长度 = %d\n", ListLength(L));
	}
	ClearList(L);               //清空表
	printf("清空L后，");
	ListTraverse(L, print);
	printf("\n");
	i = ListEmpty(L);
	printf("表是否为空?");     //再次检测表是否空
	if (i) {
		printf(" True!");
		printf(" 表的长度 = %d\n", ListLength(L));
	}
	else {
		printf(" False!");
		printf(" 表的长度 = %d\n", ListLength(L));
	}
	for (j = 1; j <= 10; j++) {
		ListInsert(L, j, j);        //在L的表尾插入
	}
	printf("在L的表尾依次插入1-10后, ");
	ListTraverse(L, print);
	printf("\n");
	int loc = LocateElem(L, 0, equal);            //测试locateList()
	if (loc) {
		printf("第%d个结点的值域为0\n", loc);
	}
	else {
		printf("不存在值域为0的结点\n");
	}
	i = GetElem(L, 100, &e);
	i = GetElem(L, 2, &e);                      //测试GetElem()
	if (i) {
		printf("第2个结点的值域为%d\n", e);
	}
	i = PriorElem(L, e, &e0);
	if (i) {
		printf("第2个结点唯一前驱的值域为%d\n", e0);
	}
	i = NextElem(L, e, &e0);
	if (i) {
		printf("第2个结点唯一后继的值域为%d\n", e0);
	}
	DestroyList(L);
	return 0;
}

四、全部代码

//线性链表
#include<stdio.h>
#include<stdlib.h>
//线性表的单链表存储结构
typedef struct LNode {
	int data;
	struct LNode* next;
}LNODE, *LINKLIST;

//带头结点单链表的基本操作（12种）
LINKLIST InitList(LINKLIST L);                 //创建
void DestroyList(LINKLIST L);                  //销毁
void ClearList(LINKLIST L);                    //清空
bool ListEmpty(LINKLIST L);                    //判空
int ListLength(LINKLIST L);                    //求长度
bool GetElem(LINKLIST L, int i, int* e);       //按位序取值
int LocateElem(LINKLIST L, int e, bool(*compare)(int, int));      //按值查找位序
bool PriorElem(LINKLIST L, int cur_e, int* pre_e);                //查前驱
bool NextElem(LINKLIST L, int cur_e, int* next_e);                //查后继
bool ListInsert(LINKLIST L, int i, int e);                        //插入元素
bool ListDelete(LINKLIST L, int i, int* e);                       //删除元素
void ListTraverse(LINKLIST L, void(*visit)(int));                 //遍历输出链表元素
//几个常用函数
bool equal(int a, int b);              //判断俩元素是否相等
int compare(int a, int b);             //比较俩元素
void print(int a);                     //按十进制数打印元素
void print1(int* a);
void print2(int a);
int main() {
	LINKLIST L = NULL;
	int e, e0;
	bool i;
	int j, k;
	L = InitList(L);
	for (j = 1; j <= 5; j++) {
		i = ListInsert(L, 1, j);
	}
	printf("在L的表头依次插入1-5后，");
	ListTraverse(L, print);
	printf("\n");
	i = ListEmpty(L);
	printf("表是否为空?");
	if (i) {
		printf(" True!");
		printf(" 表的长度 = %d\n", ListLength(L));
	}
	else {
		printf(" False!");
		printf(" 表的长度 = %d\n", ListLength(L));
	}
	ClearList(L);               //清空表
	printf("清空L后，");
	ListTraverse(L, print);
	printf("\n");
	i = ListEmpty(L);
	printf("表是否为空?");     //再次检测表是否空
	if (i) {
		printf(" True!");
		printf(" 表的长度 = %d\n", ListLength(L));
	}
	else {
		printf(" False!");
		printf(" 表的长度 = %d\n", ListLength(L));
	}
	for (j = 1; j <= 10; j++) {
		ListInsert(L, j, j);        //在L的表尾插入
	}
	printf("在L的表尾依次插入1-10后, ");
	ListTraverse(L, print);
	printf("\n");
	int loc = LocateElem(L, 0, equal);            //测试locateList()
	if (loc) {
		printf("第%d个结点的值域为0\n", loc);
	}
	else {
		printf("不存在值域为0的结点\n");
	}
	i = GetElem(L, 100, &e);
	i = GetElem(L, 2, &e);                      //测试GetElem()
	if (i) {
		printf("第2个结点的值域为%d\n", e);
	}
	i = PriorElem(L, e, &e0);
	if (i) {
		printf("第2个结点唯一前驱的值域为%d\n", e0);
	}
	i = NextElem(L, e, &e0);
	if (i) {
		printf("第2个结点唯一后继的值域为%d\n", e0);
	}
	DestroyList(L);
	return 0;
}
//基本操作函数实现
LINKLIST InitList(LINKLIST L) {
	L = (LNODE*)malloc(sizeof(LNODE));
	if (!L) {
		printf("内存分配失败!\n");
		exit(1);
	}
	L->data = 0;
	L->next = NULL;
	return L;
}
void DestroyList(LINKLIST L) {
	LINKLIST p = NULL;      
	while (L) {       //非空
		p = L->next;
		free(L);
		L = p;
	}
}
void ClearList(LINKLIST L) {
	LINKLIST p = L->next;       //p指向首结点
	L->next = NULL;            //头结点指针域为空
	DestroyList(p);            //销毁p所指单链表
}
bool ListEmpty(LINKLIST L) {
	if (L->next) {            //不为空
		return false;
	}
	else {
		return true;
	}
}
int ListLength(LINKLIST L) {
	LINKLIST p = L->next;      //p指向第一个结点(不存在则为空)
	int i = 0;                 //计数器初值为零
	while (p) {                //未到表尾 NULL
		i++;
		p = p->next;
	}
	return i;
}
bool GetElem(LINKLIST L, int i, int* e) {
	LINKLIST p = L->next;       //p指向第一个结点
	int j = 1;                  //计数器初值为1
	while (p && j < i) {            //循环 i-1 次 p指向第i个结点
		j++;
		p = p->next;
	}
	if (!p || j > i) {               //第i个结点不存在
		printf("第%d个结点不存在\n", i);
		return false;
	}
	*e = p->data;
	return true;
	
}
int LocateElem(LINKLIST L, int e, bool (*compare)(int, int)) {
	LINKLIST p = L->next;       //指向首结点
	int i = 0;
	while (p) {
		i++;
		if (compare(e, p->data)) {
			return i;
		}
		p = p->next;
	}
	return 0;                   //满足等值关系的结点不存在
}
bool PriorElem(LINKLIST L, int cur_e, int* pre_e) {
	int loc = LocateElem(L, cur_e, equal);
	if (0 == loc) {
		printf("链表中不存在值域为%d的结点！\n", cur_e);
		return false;
	}
	else if (1 == loc) {
		printf("链表中值域为%d的结点是首结点，其不存在唯一前驱!", cur_e);
		return false;
	}
	else {
		GetElem(L, loc - 1, pre_e);
		return true;
	}
}
bool NextElem(LINKLIST L, int cur_e, int* next_e) {
	int loc = LocateElem(L, cur_e, equal);
	if (0 == loc) {
		printf("链表中不存在值域为%d的结点！\n", cur_e);
		return false;
	}
	else if (ListLength(L) == loc) {
		printf("链表中值域为%d的结点是尾结点，其不存在唯一后继!", cur_e);
		return false;
	}
	else {
		GetElem(L, loc + 1, next_e);
		return true;
	}
}
bool ListInsert(LINKLIST L, int i, int e) {
	LINKLIST p = L;     //p指向头结点
	LINKLIST s = NULL;
	int j = 0;
	while (p && j < i - 1) {
		j++;
		p = p->next;
	}
	if (!p || j < i - 1) {
		printf("不能在第%d个位置插入结点!\n", i);
		return false;
	}
	s = (LNODE*)malloc(sizeof(LNODE));
	if (!s) {
		printf("内存分配失败!\n");
		exit(1);
	}
	s->next = p->next;
	p->next = s;
	s->data = e;
	return true;
	
}
bool ListDelete(LINKLIST L, int i, int* e) {
	LINKLIST p = L;      //p指向头结点
	LINKLIST s = NULL;
	int j = 0;
	while (p->next && j < i - 1) {
		j++;
		p = p->next;
	}
	if (!(p->next) || j < i - 1) {
		printf("不能在第%d个位置删除结点!\n", i);
		return false;
	}
	s = p->next;        //s指向第i个结点
	*e = s->data;
	p->next = s->next;
	free(s);
	return true;
}
void ListTraverse(LINKLIST L, void(*visit)(int)) {
	LINKLIST p = L->next; //p指向头结点
	printf("L = ");
	while (p) {
		visit(p->data);
		p = p->next;
	}
}
//几个常用函数定义
bool equal(int a, int b) {       //判断元素值是否相等
	if (a == b) {
		return true;
	}
	else {
		return false;
	}
}
int compare(int a, int b) {
	if (a > b) {
		return 1;
	}
	else if (a == b) {
		return 0;
	}
	else {
		return -1;
	}
}
void print(int a) {
	printf("%d ", a);
}
void print1(int* a);
void print2(int a);

五、总结