|
目录
一、基本操作实现
1.单链表存储结构
2. 函数声明
3. 基本操作函数定义（与带头结点实现有差别的操作）
(1)创建
(2)销毁&清空
(3)插入元素
(4)删除元素
二、基本操作函数测试
三、 全部代码
四、总结
一、基本操作实现
1.单链表存储结构
//线性链表_不带头结点
#include<stdio.h>
#include<stdlib.h>
//线性表的单链表存储结构
typedef struct LNode {
int data;
struct LNode* next;
}LNODE, * LINKLIST;
2. 函数声明
//不带头结点单链表的基本操作（12种）
LINKLIST InitList(LINKLIST L); //创建
void DestroyList(LINKLIST L); //销毁
LINKLIST 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); //查后继
LINKLIST ListInsert(LINKLIST L, int i, int e); //插入元素
LINKLIST ListDelete(LINKLIST L, int i, int* e); //删除元素
void ListTraverse(LINKLIST L, void(*visit)(int));
3. 基本操作函数定义（与带头结点实现有差别的操作）
(1)创建
不同于创建带头单链表需要实现：指针L指向头结点，头结点指针域置空
创建不带头单链表需要实现：指针L置空
两者都需要改变L，所以都需要return L
注意：指针L作为参数传入函数，在函数内部并不能改变L的值。在函数内部对L的赋值操作本质是对形式参数（或称为副本）的改变，影响不到实际参数。所以必须return形式参数的值，在main函数中对指针L进行赋值，来改变L的值。
LINKLIST InitList(LINKLIST L) {
L = NULL;
return L;
}
(2)销毁&清空
清空操作区别于销毁操作，增加了return NULL。
原因是：表L销毁后不再对表进行操作，表指针L指向未知区域，无关紧要。对表进行清空操作，表L必须回到初始化后的状态，也就是表指针置空。否则指针L作为野指针会影响后续操作。
void DestroyList(LINKLIST L) {
LINKLIST p = NULL;
while (L) { //非空
p = L->next; //p指向下一个结点
free(L); //释放首结点
L = p; //L指向新首结点
}
}
LINKLIST ClearList(LINKLIST L) {
LINKLIST p = L; //p指向首结点
DestroyList(p);
return NULL;
}
(3)插入元素
区别于带头结点链表可以将头结点看作“第0号结点”进行插入操作。
不带头结点必须区分插入元素位序是否为 1 。
若为一：需要改变指针L
不为一：不需要改变指针L, 找到合法 第 i-1 号元素的充要条件：（p && j ==?i - 1)?
? ? ? ? j == i - 1 即 从首结点移动了 i - 2 次找到 i - 1 号元素?
? ? ? ? p != NULL 即 i - 1 号元素不是表尾（NULL）
LINKLIST ListInsert(LINKLIST L, int i, int e) {
LINKLIST p = L;
LINKLIST s = NULL;
int j = 1; //计数器置1
if (i < 1) {
printf("插入失败，输入的位序不能小于1\n");
return L;
}
if (i == 1) { //插入位序为1,需要改变 链表指针
s = (LNODE*)malloc(sizeof(LNODE));
s->data = e;
s->next = L;
L = s; //改变链表指针L
return L;
}
else { //插入位序不为1
while (p && j < i - 1) {
j++;
p = p->next;
}
if (p && j == i - 1) { //从1号元素移动i-2次 且 未到表尾 找到合法 i-1 号元素
s = (LNODE*)malloc(sizeof(LNODE));
s->data = e;
s->next = p->next;
p->next = s;
return L;
}
else {
printf("插入失败，输入的位序有误\n");
return L;
}
}
}
(4)删除元素
同不带头结点单链表的插入操作一样，需要区分删除位序是否为一。
区别于插入操作，删除操作找到合法 第 i-1 号元素的充要条件：（p->next?&& j ==?i - 1)?
p->next == NULL 则说明指针p指向了尾结点。若p指向尾结点则待删除结点作为”下一号“结点，
是NULL，显然删除NULL是没有意义的。
LINKLIST ListDelete(LINKLIST L, int i, int* e) {
LINKLIST p = NULL;
LINKLIST s = NULL;
int j = 1; //计数器置1
if (!L) {
printf("删除失败，链表为空\n");
return L;
}
if (i == 1) {//删除首结点，要改变链表指针L
p = L->next; //p指向2号元素
*e = L->data; //返回待删结点值
free(L); //释放首元素
L = p; //改变L
return L;
}
else { //删除的结点位序不为1
p = L;
while (p->next && j < i - 1) {
j++;
p = p->next;
}
if (p->next && j == i - 1) { //从1号元素移动i-2次 且 未到尾结点 找到合法i-1号元素
s = p->next; //s指向第 i 个结点
*e = s->data;//返回第i个结点值
p->next = s->next;
free(s);
return L;
}
else {
printf("删除失败，输入的位序有误\n");
return L;
}
}
}
二、基本操作函数测试
int main() {
LINKLIST L = NULL;
int i;
int e, e_;
L = InitList(L);
//测试 Empty
if (ListEmpty(L)) printf("此表为空\n"); //此表为空
else printf("此表不为空,Length = %d\n", ListLength(L));
for (i = 1; i <= 5; i++) { //在表头插入 1 - 5
L = ListInsert(L, 1, i);
}
printf("在表头插入1-5后，");
//测试Traverse
ListTraverse(L, print); // L = 5 4 3 2 1
printf("\n");
//测试ListLength
if (ListEmpty(L)) printf("此表为空\n");
else printf("此表不为空,Length = %d\n", ListLength(L)); //此表不为空, Length = 5
//测试ClearList
L = ClearList(L);
if (ListEmpty(L)) printf("此表为空\n"); //此表为空
else printf("此表不为空,Length = %d\n", ListLength(L));
for (i = 1; i <= 10; i++) { //在表尾插入1 - 10
L = ListInsert(L, i, i);
}
printf("在表尾插入1-10后，");
ListTraverse(L, print); // L = 1 2 3 4 5 6 7 8 9 10
printf("\n");
//测试 GetElem
if (GetElem(L, -1, &e_)) printf("Get elem: %d\n", e_); //输入位序不能小于1
if (GetElem(L, 20, &e_)) printf("Get elem: %d\n", e_); //输入位序错误
for (i = 1; i <= 10; i++) {
if (GetElem(L, i, &e_)) printf("number%d--elem: %d\n", i, e_); //i = 1 - 10 number i -- elem: i
}
//测试LocateElem
if (LocateElem(L, 0, equal)) printf("value = 0, loc = %d\n", LocateElem(L, 0, equal));//位序不能小于1
if (LocateElem(L, 11, equal)) printf("value = 0, loc = %d\n", LocateElem(L, 0, equal));//位序有误
for (i = 5; i >= 1; i--) {
if (LocateElem(L, i, equal))
printf("value = %d, loc = %d\n", i, LocateElem(L, i, equal)); // i = 5 - 1 value = i, loc = i
}
//测试 PriorElem & nextElem
if (PriorElem(L, 23, &e_)) printf("Prior elem: %d\n", e_); //不存在
if (PriorElem(L, 1, &e_)) printf("Prior elem: %d\n", e_); //首结点无前驱
if (PriorElem(L, 3, &e_)) printf("Prior elem: %d\n", e_); //Prior = 2
if(NextElem(L, 254, &e_)) printf("next elem: %d\n", e_); //不存在
if (NextElem(L, ListLength(L), &e_)) printf("next elem: %d\n", e_); //尾结点无后继
if (NextElem(L, 3, &e_)) printf("next elem: %d\n", e_); //next = 4;
//测试ListInsert
L = ListInsert(L, 12, 11); //位序有误
L = ListInsert(L, -2, 11); //位序小于1
L = ListInsert(L, 0, 11); //位序小于1
L = ListInsert(L, 11, 11);
L = ListInsert(L, 1, 0); //插入到表首
printf("进行插入操作后，"); // L = 0 1 2 .... 10 11
ListTraverse(L, print);
printf("\n");
//测试ListDelete
L = ListDelete(L, 13, &e); //有误
L = ListDelete(L, -3, &e); //小于1
L = ListDelete(L, 1, &e);
L = ListDelete(L, 11, &e);
printf("进行删除操作后，"); // L = 1 2 3....10
ListTraverse(L, print);
printf("\n");
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); //销毁
LINKLIST 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); //查后继
LINKLIST ListInsert(LINKLIST L, int i, int e); //插入元素
LINKLIST 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 i;
int e, e_;
L = InitList(L);
//测试 Empty
if (ListEmpty(L)) printf("此表为空\n"); //此表为空
else printf("此表不为空,Length = %d\n", ListLength(L));
for (i = 1; i <= 5; i++) { //在表头插入 1 - 5
L = ListInsert(L, 1, i);
}
printf("在表头插入1-5后，");
//测试Traverse
ListTraverse(L, print); // L = 5 4 3 2 1
printf("\n");
//测试ListLength
if (ListEmpty(L)) printf("此表为空\n");
else printf("此表不为空,Length = %d\n", ListLength(L)); //此表不为空, Length = 5
//测试ClearList
L = ClearList(L);
if (ListEmpty(L)) printf("此表为空\n"); //此表为空
else printf("此表不为空,Length = %d\n", ListLength(L));
for (i = 1; i <= 10; i++) { //在表尾插入1 - 10
L = ListInsert(L, i, i);
}
printf("在表尾插入1-10后，");
ListTraverse(L, print); // L = 1 2 3 4 5 6 7 8 9 10
printf("\n");
//测试 GetElem
if (GetElem(L, -1, &e_)) printf("Get elem: %d\n", e_); //输入位序不能小于1
if (GetElem(L, 20, &e_)) printf("Get elem: %d\n", e_); //输入位序错误
for (i = 1; i <= 10; i++) {
if (GetElem(L, i, &e_)) printf("number%d--elem: %d\n", i, e_); //i = 1 - 10 number i -- elem: i
}
//测试LocateElem
if (LocateElem(L, 0, equal)) printf("value = 0, loc = %d\n", LocateElem(L, 0, equal));//位序不能小于1
if (LocateElem(L, 11, equal)) printf("value = 0, loc = %d\n", LocateElem(L, 0, equal));//位序有误
for (i = 5; i >= 1; i--) {
if (LocateElem(L, i, equal))
printf("value = %d, loc = %d\n", i, LocateElem(L, i, equal)); // i = 5 - 1 value = i, loc = i
}
//测试 PriorElem & nextElem
if (PriorElem(L, 23, &e_)) printf("Prior elem: %d\n", e_); //不存在
if (PriorElem(L, 1, &e_)) printf("Prior elem: %d\n", e_); //首结点无前驱
if (PriorElem(L, 3, &e_)) printf("Prior elem: %d\n", e_); //Prior = 2
if(NextElem(L, 254, &e_)) printf("next elem: %d\n", e_); //不存在
if (NextElem(L, ListLength(L), &e_)) printf("next elem: %d\n", e_); //尾结点无后继
if (NextElem(L, 3, &e_)) printf("next elem: %d\n", e_); //next = 4;
//测试ListInsert
L = ListInsert(L, 12, 11); //位序有误
L = ListInsert(L, -2, 11); //位序小于1
L = ListInsert(L, 0, 11); //位序小于1
L = ListInsert(L, 11, 11);
L = ListInsert(L, 1, 0); //插入到表首
printf("进行插入操作后，"); // L = 0 1 2 .... 10 11
ListTraverse(L, print);
printf("\n");
//测试ListDelete
L = ListDelete(L, 13, &e); //有误
L = ListDelete(L, -3, &e); //小于1
L = ListDelete(L, 1, &e);
L = ListDelete(L, 11, &e);
printf("进行删除操作后，"); // L = 1 2 3....10
ListTraverse(L, print);
printf("\n");
DestroyList(L);
return 0;
}
//基本操作函数实现
LINKLIST InitList(LINKLIST L) {
L = NULL;
return L;
}
void DestroyList(LINKLIST L) {
LINKLIST p = NULL;
while (L) { //非空
p = L->next; //p指向下一个结点
free(L); //释放首结点
L = p; //L指向新首结点
}
}
LINKLIST ClearList(LINKLIST L) {
LINKLIST p = L; //p指向首结点
DestroyList(p);
return NULL;
}
bool ListEmpty(LINKLIST L) {
if (L) { //首结点不为null
return false;
}
else {
return true;
}
}
int ListLength(LINKLIST L) {
LINKLIST p = L; //p指向第一个结点(不存在则为空)
int i = 0; //计数器初值为零
while (p) { //未到表尾 NULL
i++;
p = p->next;
}
return i;
}
bool GetElem(LINKLIST L, int i, int* e) {
LINKLIST p = L; //p指向第一个结点
int j = 1; //计数器初值为1
if (i < 1) {
printf("位序i的值不能小于1\n");
return false;
}
while (p && j < i) {//定位第i个元素
j++;
p = p->next;
}
if (p && j == i) { //遍历i-1次到第i个结点 且 未到表尾null
*e = p->data;
return true;
}
else {
printf("输入的位序有误!\n");
return false;
}
}
int LocateElem(LINKLIST L, int e, bool (*compare)(int, int)) {
LINKLIST p = L; //指向首结点
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的结点是首结点，其不存在唯一前驱!\n", 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的结点是尾结点，其不存在唯一后继!\n", cur_e);
return false;
}
else {
GetElem(L, loc + 1, next_e);
return true;
}
}
LINKLIST ListInsert(LINKLIST L, int i, int e) {
LINKLIST p = L;
LINKLIST s = NULL;
int j = 1; //计数器置1
if (i < 1) {
printf("插入失败，输入的位序不能小于1\n");
return L;
}
if (i == 1) { //插入位序为1,需要改变 链表指针
s = (LNODE*)malloc(sizeof(LNODE));
s->data = e;
s->next = L;
L = s; //改变链表指针L
return L;
}
else { //插入位序不为1
while (p && j < i - 1) {
j++;
p = p->next;
}
if (p && j == i - 1) { //从1号元素移动i-2次 且 未到表尾 找到合法 i-1 号元素
s = (LNODE*)malloc(sizeof(LNODE));
s->data = e;
s->next = p->next;
p->next = s;
return L;
}
else {
printf("插入失败，输入的位序有误\n");
return L;
}
}
}
LINKLIST ListDelete(LINKLIST L, int i, int* e) {
LINKLIST p = NULL;
LINKLIST s = NULL;
int j = 1; //计数器置1
if (!L) {
printf("删除失败，链表为空\n");
return L;
}
if (i == 1) {//删除首结点，要改变链表指针L
p = L->next; //p指向2号元素
*e = L->data; //返回待删结点值
free(L); //释放首元素
L = p; //改变L
return L;
}
else { //删除的结点位序不为1
p = L;
while (p->next && j < i - 1) {
j++;
p = p->next;
}
if (p->next && j == i - 1) { //从1号元素移动i-2次 且 未到尾结点 找到合法i-1号元素
s = p->next; //s指向第 i 个结点
*e = s->data;//返回第i个结点值
p->next = s->next;
free(s);
return L;
}
else {
printf("删除失败，输入的位序有误\n");
return L;
}
}
}
void ListTraverse(LINKLIST L, void(*visit)(int)) {
LINKLIST p = L; //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);
四、总结
1. 注意区分 带头|不带头结点 单链表的基本操作。
由于带头单链表的头结点可以视为第0个结点，因此在插入、删除等操作中更加方便。
2. 需要改变链表指针L时，必须使用return L（返回形参L的值），并在函数外，进行赋值操作。
（左值为实参L， 右值为返回的形参L)
|