C语言_数据结构总结4：不带头结点的单链表

纯C语言代码，不涉及C++

0. 结点结构

typedef int ElemType;
typedef struct LNode {
    ElemType data;  //数据域
    struct LNode* next;  //指针域
}LNode, * LinkList;

1. 初始化

不带头结点的初始化，即只需将头指针初始化为NULL即可

void InitLink2(LinkList* L) {*L = NULL;
}

2. 头插法

对于不带头结点的单链表，头插法的核心思想是：
每次插入新节点时，将新节点的 next 指针指向当前链表的头节点，然后更新链表的头指针，使其指向新节点。
这样新节点就成为了链表的第一个节点，插入操作的时间复杂度为 O(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;*L = 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;  //因为新结点s要插入到链表尾部//若链表为空，新结点就是头结点if (*L == NULL){*L = s;}else{//1.找到链表的尾结点LinkList p = *L;while (p->next != NULL) {p = p->next;}p->next = s;  //将新节点插入到尾结点后面}return 0; //插入成功
}

4. 插入

int insertLNode2(LinkList* L, int pos, ElemType value) {if (pos < 1) {printf("插入位置不合法!\n");return -1;}LinkList s = (LinkList)malloc(sizeof(LNode));if (s == NULL) {printf("内存分配失败!\n");return -2;}s->data = value;if (pos == 1) {s->next = *L;*L = s;}else {LinkList p = *L;int i = 1;while (p != NULL && i < pos - 1) {p = p->next;i++;}if (p == NULL) {printf("插入位置不合法,已超出链表长度!\n");free(s);return -1;}s->next = p->next;p->next = s;}return 0;
}

5. 删除

！不带头结点的单链表进行删除结点操作需要分情况考虑：

若要删除的是头节点，需要直接更新头指针；
若删除的是其他节点，需要找到该节点的前一个节点。

！在不带头结点的单链表删除操作中，当 pos == 1 时，不能直接使用 free(*L);，而要进行 *L = (*L)->next;

直接 free(*L); 存在的问题

free(*L); 这行代码的作用是释放 *L 所指向的内存空间。但执行完这一步后，链表的头指针 *L 仍然指向这块已经被释放的内存，形成了一个野指针。野指针是非常危险的，因为后续如果对这个野指针进行解引用操作（例如访问 (*L)->data 或 (*L)->next），会导致未定义行为，可能会使程序崩溃。而且，由于头指针没有更新，链表的后续节点就无法再被访问到，整个链表就丢失了。

*L = (*L)->next; 操作的意义

当 pos == 1 时，意味着要删除链表的第一个节点（即头节点）。*L = (*L)->next; 这行代码的作用是更新头指针，让它指向原来头节点的下一个节点。具体步骤如下：

1. 保存原头节点指针：

LinkList temp = *L;

》这行代码将原头节点的指针保存到临时变量 temp 中，方便后续释放该节点的内存。
     2. 更新头指针：

*L = (*L)->next;

》》将头指针 *L 更新为原头节点的下一个节点。这样，新的头指针就指向了链表的第二个节点（如果存在的话），链表仍然可以正常访问。
   3. 释放原头节点内存：

free(temp);

》》》释放临时变量 temp 所指向的内存，即原头节点的内存。

以下删除的操作完整代码：

int deleteNode(LinkList* L, int pos) {if (pos < 1){printf("删除位置无效!\n");return -1;}if (*L == NULL){printf("当前链表为空!\n");return -2;}if (pos == 1)  //即删除头结点，（更新头结点）{LinkList temp = *L;*L = (*L)->next;free(temp);}else{LinkList p = *L;int i = 1;//找到第pos-1个结点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;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;int pos = 1;while (p != NULL) {if (p->data == value){return pos;}p = p->next;pos++;}return -1;  //查找失败，未在该链表中找到该value值
}

8. 链表打印

void printLink2(LinkList L) {if (L == NULL) {printf("链表为空!\n");return;}LinkList s = L;while (s != NULL) {printf("%d ", s->data);s = s->next;}printf("\n--------------------------------\n");
}

9. 释放空间

void freeList2(LinkList L) {LinkList p = L;while (p != NULL) {LinkList temp = p;p = p->next;free(temp);}
}

10. 测试代码

int main() {//测试插入方法LinkList L1;InitLink2(&L1);insertLNode2(&L1, 1, 11);insertLNode2(&L1, 2, 22);insertLNode2(&L1, 3, 33);printLink2(L1);  // 11 22 33 freeList2(L1);// 测试头插法LinkList L2;InitLink2(&L2);headInsert(&L2, 1);headInsert(&L2, 2);headInsert(&L2, 3);printLink2(L2);  // 3 2 1freeList2(L2);// 测试尾插法LinkList L3;InitLink2(&L3);tailInsert(&L3, 1);tailInsert(&L3, 2);tailInsert(&L3, 3);printLink2(L3);  // 1 2 3// 测试删除deleteNode(&L3, 3);printf("删除第三个结点后：");printLink2(L3);  //删除第三个结点后：1 2//测试按值查找printf("数值1在第%d个位置\n", findPosByvalue(L3, 1));  // 数值1在第1个位置//测试按位查找ElemType value;findValueByPos(L3, 1, &value);printf("第1个位置的值为%d\n", value);  // 第1个位置的值为1freeList2(L3);return 0;
}

11. 完整代码

#include<stdio.h>
#include<stdlib.h>
/*不带头结点的单链表
*/typedef int ElemType;
typedef struct LNode {ElemType data;  //数据域struct LNode* next;  //指针域
}LNode, * LinkList;// 操作1——不带头结点的初始化，即只需将头指针初始化为NULL即可
void InitLink2(LinkList* L) {*L = NULL;
}// 操作2——不带头结点的插入操作
int insertLNode2(LinkList* L, int pos, ElemType value) {if (pos < 1) {printf("插入位置不合法!\n");return -1;}LinkList s = (LinkList)malloc(sizeof(LNode));if (s == NULL) {printf("内存分配失败!\n");return -2;}s->data = value;if (pos == 1) {s->next = *L;*L = s;}else {LinkList p = *L;int i = 1;while (p != NULL && i < pos - 1) {p = p->next;i++;}if (p == NULL) {printf("插入位置不合法!\n");free(s);return -1;}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;*L = s;  //更新头结点指向新结点return 0;  //插入成功
}//操作2.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;  //因为新结点s要插入到链表尾部//若链表为空，新结点就是头结点if (*L == NULL){*L = s;}else{//1.找到链表的尾结点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;}if (*L == NULL){printf("当前链表为空!\n");return -2;}if (pos == 1)  //即删除头结点，（更新头结点）{LinkList temp = *L;*L = (*L)->next;free(temp);}else{LinkList p = *L;int i = 1;//找到第pos-1个结点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;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;int pos = 1;while (p != NULL) {if (p->data == value){return pos;}p = p->next;pos++;}return -1;  //查找失败，未在该链表中找到该value值
}// 操作6——不带头结点的单链表打印操作
void printLink2(LinkList L) {if (L == NULL) {printf("链表为空!\n");return;}LinkList s = L;while (s != NULL) {printf("%d ", s->data);s = s->next;}printf("\n--------------------------------\n");
}// 操作7——释放不带头结点链表内存
void freeList2(LinkList L) {LinkList p = L;while (p != NULL) {LinkList temp = p;p = p->next;free(temp);}
}int main() {//测试插入方法LinkList L1;InitLink2(&L1);insertLNode2(&L1, 1, 11);insertLNode2(&L1, 2, 22);insertLNode2(&L1, 3, 33);printLink2(L1);  // 11 22 33 freeList2(L1);// 测试头插法LinkList L2;InitLink2(&L2);headInsert(&L2, 1);headInsert(&L2, 2);headInsert(&L2, 3);printLink2(L2);  // 3 2 1freeList2(L2);// 测试尾插法LinkList L3;InitLink2(&L3);tailInsert(&L3, 1);tailInsert(&L3, 2);tailInsert(&L3, 3);printLink2(L3);  // 1 2 3// 测试删除deleteNode(&L3, 3);printf("删除第三个结点后：");printLink2(L3);  //删除第三个结点后：1 2//测试按值查找printf("数值1在第%d个位置\n", findPosByvalue(L3, 1));  // 数值1在第1个位置//测试按位查找ElemType value;findValueByPos(L3, 1, &value);printf("第1个位置的值为%d\n", value);  // 第1个位置的值为1freeList2(L3);return 0;
}

12. 运行截图