Java教程
线性链表（线性表的单链表存储结构）
本文主要是介绍线性链表（线性表的单链表存储结构），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
目录
一、单链表存储结构
二、基本操作&其他操作的函数定义
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);
五、总结
这篇关于线性链表（线性表的单链表存储结构）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
面向对象编程基础：初学者指南09-07
-
数据结构入门：了解基础概念与简单应用09-07
-
面向对象编程入门：掌握基本概念与实践09-07
-
数据结构入门：从基础概念到基本操作09-07
-
从零开始学数据库：入门级指南与实操技巧09-07
-
综合设备故障分析与预防：实例代码与优化策略09-07
-
数据库入门：轻松掌握数据管理基础09-07
-
面向对象入门：快速掌握对象编程基础09-07
-
数据库教程：入门与实践指南09-07
-
面向对象开发教程 - 从零基础到实践应用的进阶之路09-07
-
从入门到实践：Auth机制的简单教程09-07
-
快速上手 Drizzle ORM：入门级教程09-07
-
入门指南：轻松掌握公共API的使用09-07
-
深入浅出：Server Component 在现代Web开发中的应用与实践09-07
-
GET 起 TRPC：入门级教程，轻松掌握RESTful API的简洁之道09-07
栏目导航
