目录
一、单链表存储结构
//线性表的单链表存储结构
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);