纯c语言代码，不涉及C++
0. 结点结构
typedef int ElemType;
typedef struct LNode {
ElemType data; //数据域
struct LNode* next; //指针域
}LNode, * LinkList;
1. 初始化
带头结点的初始化，即创建一个头结点，并让头指针指向头结点，头结点的next域初始化为NULL
void InitLink1(LinkList* L) {*L = (LinkList)malloc(sizeof(LNode));if (*L == NULL){printf("内存分配失败!\n");exit(1); //退出系统的操作}(*L)->next = NULL;
}2. 头插法
int headInsert(LinkList L,ElemType value) {LinkList s = (LinkList)malloc(sizeof(LNode));if (s == NULL){printf("内存分配失败!\n");return -2;}s->data = value;s->next = L->next;L->next = s;return 0; //插入成功
}3. 尾插法
int tailInsert(LinkList L,ElemType value) {LinkList s = (LinkList)malloc(sizeof(LNode));if (s == NULL){printf("内存分配失败!\n");return -2;}s->data = value;s->next = NULL;LinkList p = L;while (p->next != NULL) {p = p->next;}p->next = s;return 0; //插入成功
}4. 插入
/*
插入步骤3中判断 p == NULL 的原因：
当在遍历链表寻找插入位置的前一个结点时，可能会出现以下情况：
一：插入位置超出链表长度
如果要插入的位置 pos 大于链表的实际长度，那么在遍历过程中，指针 p 会沿着链表不断向后移动，最终会移动到链表的末尾（即 p->next == NULL），然后再尝试移动到下一个结点时，p 就会变成 NULL。
二：链表为空且插入位置不为 1
如果链表为空（只有头结点），并且要插入的位置 pos 大于 1，那么在遍历过程中，指针 p 从链表的头结点开始，由于链表没有其他结点，p 会在寻找插入位置的前一个结点时变成 NULL。
在上述两种情况下，如果继续进行插入操作会导致错误，因为此时 p 已经不指向链表中的有效结点，无法进行后续的插入操作。因此，当 p 为 NULL 时，说明插入位置不合法，函数会返回 -1 表示插入失败。
*/
int insertLNode1(LinkList L, int pos, ElemType value) {//1. 判断插入位置是否合理if (pos < 1){printf("插入位置不合法!\n");return -1;}//2. 找到待插入位置的前一个结点LinkList p = L; // 定义一个新指针，让其刚开始指向头结点int i = 0;while (p != NULL && i < pos - 1) {p = p->next;i++;}//3. 判断if (p == NULL){printf("插入位置不合法!\n");return -1;}LinkList s = (LinkList)malloc(sizeof(LNode)); //为要插入的数据分配空间if (s == NULL){printf("内存分配失败!\n");return -2;}s->data = value;s->next = p->next;p->next = s;return 0; //插入成功
}
5. 删除
即：删除第pos个位置上的值
int deleteNode(LinkList L, int pos) {if (pos < 1){printf("删除位置不合理!\n");return -1;}LinkList p = L;int i = 0;while (p != NULL && i < pos - 1) {p = p->next;i++;}if (p == NULL || p->next == NULL){printf("删除位置不合理!\n");return -1;}LinkList temp = p->next;p->next = temp->next;free(temp);return 0; //删除成功
}6. 按位查找
即:查找第pos个位置上的value值
int findValueByPos(LinkList L, int pos, ElemType* value) {if (pos < 1){printf("查找位置不合理!\n");return -1;}LinkList p = L->next;int i = 1;while (p != NULL && i < pos) {p = p->next;i++;}if (p == NULL){printf("查找位置超出链表长度!\n");return -1;}*value = p->data;return 0;
}7. 按值查找
即：查找value值在链表的第pos个位置
int findPosByvalue(LinkList L, ElemType value) {LinkList p = L->next;int pos = 1;while (p != NULL) {if (p->data == value){return pos;}p = p->next;pos++;}return -1; //查找失败
}8. 链表打印
void printLink1(LinkList L) {if (L == NULL || L->next == NULL){printf("链表为空!\n");return;//提前结束函数}/*对判断条件的分析
1. L == NULLL 是指向链表头结点的指针。当 L == NULL 时，意味着这个指针没有指向任何有效的头结点，也就是根本不存在链表，自然可以判定链表为空。这可能是由于初始化失败或者其他异常情况导致头结点的内存分配没有成功，使得头指针没有指向有效的内存区域。
2. L->next == NULL当 L->next == NULL 时，说明头结点的 next 指针为空。在带头结点的单链表中，头结点的 next 指针指向的是第一个存储实际数据的结点。如果这个指针为空，那就表示链表中没有存储实际数据的结点，也就是链表为空。虽然存在头结点，但它不存储实际数据，链表中没有有效的数据元素，所以可以判定链表为空。*/LinkList s = L->next; //即让指针s指向了头结点后的第一格结点while (s != NULL) {printf("%d ", s->data);s = s->next;}printf("\n--------------------------------\n");
}9. 释放空间
void freeList1(LinkList L) {LinkList p = L; // 定义一个临时指针指向头结点（和头指针一样，指向头结点，不同的是，该结点后续有变动）while (p != NULL) {LinkList temp = p; // 在每次循环中，创建一个临时指针 temp，并将其指向当前结点 p。这是因为在释放当前结点之前，需要先保存该结点的地址，以便后续调用 free 函数释放其内存。p = p->next;free(temp);}
}
10. 测试代码
int main() {//测试插入方法LinkList L1;InitLink1(&L1);insertLNode1(L1, 1, 11);insertLNode1(L1, 2, 22);insertLNode1(L1, 3, 33);printLink1(L1); // 11 22 33 freeList1(L1);// 测试头插法LinkList L2;InitLink1(&L2);headInsert(L2, 1);headInsert(L2, 2);headInsert(L2, 3);printLink1(L2); // 3 2 1freeList1(L2);// 测试尾插法LinkList L3;InitLink1(&L3);tailInsert(L3, 1);tailInsert(L3, 2);tailInsert(L3, 3);printLink1(L3); // 1 2 3// 测试删除deleteNode(L3, 3);printf("删除第三个结点后：");printLink1(L3); // 删除第三个结点后：1 2//测试按值查找printf("数值1在第%d个位置\n", findPosByvalue(L3, 1)); //数值1在第1个位置//测试按位查找ElemType value;findValueByPos(L3, 1, &value);printf("第1个位置的值为%d\n", value); //第1个位置的值为1freeList1(L3);return 0;
}11. 完整代码
#include<stdio.h>
#include<stdlib.h>
/*带头结点的单链表
*/typedef int ElemType;
typedef struct LNode {ElemType data; //数据域struct LNode* next; //指针域
}LNode, * LinkList;//操作1—— 带头结点的初始化，即创建一个头结点，并让头指针指向头结点，头结点的next域初始化为NULL
void InitLink1(LinkList* L) {*L = (LinkList)malloc(sizeof(LNode));if (*L == NULL){printf("内存分配失败!\n");exit(1); //退出系统的操作}(*L)->next = NULL;
}// 操作2——带头结点的插入操作
int insertLNode1(LinkList L, int pos, ElemType value) {//1. 判断插入位置是否合理if (pos < 1){printf("插入位置不合法!\n");return -1;}//2. 找到待插入位置的前一个结点LinkList p = L; // 定义一个新指针，让其刚开始指向头结点int i = 0;while (p != NULL && i < pos - 1) {p = p->next;i++;}//3. 判断if (p == NULL){printf("插入位置不合法!\n");return -1;}LinkList s = (LinkList)malloc(sizeof(LNode)); //为要插入的数据分配空间if (s == NULL){printf("内存分配失败!\n");return -2;}s->data = value;s->next = p->next;p->next = s;return 0; //插入成功
}// 操作2.1——带头结点的头插法建立单链表方法
int headInsert(LinkList L,ElemType value) {LinkList s = (LinkList)malloc(sizeof(LNode));if (s == NULL){printf("内存分配失败!\n");return -2;}s->data = value;s->next = L->next;L->next = s;return 0; //插入成功
}// 操作2.2——带头结点的尾插法建立单链表方法
int tailInsert(LinkList L,ElemType value) {LinkList s = (LinkList)malloc(sizeof(LNode));if (s == NULL){printf("内存分配失败!\n");return -2;}s->data = value;s->next = NULL;LinkList p = L;while (p->next != NULL) {p = p->next;}p->next = s;return 0; //插入成功
}// 操作3——删除第pos个位置上的值
int deleteNode(LinkList L, int pos) {if (pos < 1){printf("删除位置不合理!\n");return -1;}LinkList p = L;int i = 0;while (p != NULL && i < pos - 1) {p = p->next;i++;}if (p == NULL || p->next == NULL){printf("删除位置不合理!\n");return -1;}LinkList temp = p->next;p->next = temp->next;free(temp);return 0; //删除成功
}// 操作4——按位查找：查找第pos个位置上的value值
int findValueByPos(LinkList L, int pos, ElemType* value) {if (pos < 1){printf("查找位置不合理!\n");return -1;}LinkList p = L->next;int i = 1;while (p != NULL && i < pos) {p = p->next;i++;}if (p == NULL){printf("查找位置超出链表长度!\n");return -1;}*value = p->data;return 0;
}// 操作5——按值查找：查找value值在链表的第pos个位置
int findPosByvalue(LinkList L, ElemType value) {LinkList p = L->next;int pos = 1;while (p != NULL) {if (p->data == value){return pos;}p = p->next;pos++;}return -1; //查找失败
}// 操作6——带头结点的单链表打印操作
void printLink1(LinkList L) {if (L == NULL || L->next == NULL){printf("链表为空!\n");return;//提前结束函数}LinkList s = L->next; //即让指针s指向了头结点后的第一格结点while (s != NULL) {printf("%d ", s->data);s = s->next;}printf("\n--------------------------------\n");
}// 操作7——释放带头结点链表内存
void freeList1(LinkList L) {LinkList p = L; // 定义一个临时指针指向头结点（和头指针一样，指向头结点，不同的是，该结点后续有变动）while (p != NULL) {LinkList temp = p; // 在每次循环中，创建一个临时指针 temp，并将其指向当前结点 p。这是因为在释放当前结点之前，需要先保存该结点的地址，以便后续调用 free 函数释放其内存。p = p->next;free(temp);}
}int main() {//测试插入方法LinkList L1;InitLink1(&L1);insertLNode1(L1, 1, 11);insertLNode1(L1, 2, 22);insertLNode1(L1, 3, 33);printLink1(L1); // 11 22 33 freeList1(L1);// 测试头插法LinkList L2;InitLink1(&L2);headInsert(L2, 1);headInsert(L2, 2);headInsert(L2, 3);printLink1(L2); // 3 2 1freeList1(L2);// 测试尾插法LinkList L3;InitLink1(&L3);tailInsert(L3, 1);tailInsert(L3, 2);tailInsert(L3, 3);printLink1(L3); // 1 2 3// 测试删除deleteNode(L3, 3);printf("删除第三个结点后：");printLink1(L3); // 删除第三个结点后：1 2//测试按值查找printf("数值1在第%d个位置\n", findPosByvalue(L3, 1)); //数值1在第1个位置//测试按位查找ElemType value;findValueByPos(L3, 1, &value);printf("第1个位置的值为%d\n", value); //第1个位置的值为1freeList1(L3);return 0;
}12. 运行截图
