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. 刪除

！不帶頭結點的單鏈表進行刪除結點操作需要分情況考慮：

若要刪除的是頭節點，需要直接更新頭指針；
若刪除的是其他節點，需要找到該節點的前一個節點。

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個結點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個結點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;
}