1.2 单链表定义及操作实现(链式结构)

1.单链表定义

链式存储：用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性

表简称线性链表。

为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接

后继结点的地址（或位置），称为指针（ pointer ）或链（ link ），这两部分组成了链表中

的结点结构。

data ：数据域，存放结点的值。

next ：指针域，存放结点的直接后继的地址。

链表是通过每个结点的指针域将线性表的 n 个结点按其逻辑次序链接在一起的。

每一个结只包含一个指针域的链表，称为单链表。

注意：

1）存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。

2）链表中结点的逻辑顺序和物理顺序不一定相同。

3）为操作方便，总是在链表的第一个结点之前附设一个头结点（头指针）head 指向第一个结点。头结点的数据域可以不存储任何信息（或链表长度等信息）。

2.结点的实现

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

结点是通过动态分配和释放来的实现，即需要时分配，不需要时释放。实现时是分别

使用 C 语言提供的标准函数： malloc （）， realloc （）， sizeof （）， free （）。

动态分配 p= （ LNode* ） malloc （ sizeof （ LNode ））；

3.单链表操作

3.1.创建结点

LNode* node_create(int value, LNode* next) {LNode* node = (LNode*)malloc(sizeof(LNode));if (node != nullptr) {node->data = value;node->next = next;}return node;
}

3.2.创建链表

/*** 创建一个空链表，只包含头结点head*/
LinkList list_create() {return node_create(0, nullptr);//return head node
}
/*** 创建链表，并以形参列表初始化调用方法：LinkList list = list_create({1,2,3,4});*/
LinkList list_create(std::initializer_list<int> args) {LinkList list = node_create(0, nullptr);//create head nodeLNode* curr = list;for (int i : args) {curr->next = node_create(i, nullptr);curr = curr->next;}return list;
}/*** 释放链表占用内存空间*/
bool list_free(LinkList list) {if (list == nullptr) {return false;}for (LNode* curr = list; curr != nullptr; ) {LNode* next = curr->next;free(curr);curr = next;}return true;
}

3.3.查找元素

3.3.1.按序号查找

//查找第i(i>=1)个元素
int get_elem(LinkList list, int i) {if (list == nullptr || i < 1 || i > INT_MAX) {return INT_MIN;//return invalid value}int j = 1;LNode* cur = list->next;while (cur != nullptr && j < i) {cur = cur->next;j += 1;}return i == j ? cur->data : INT_MIN;
}

3.3.2.按值查找

/*** 按值查找* 按值查找是在链表中，查找是否有结点值等于给定值 key 的结点? 若有，则返回首次找到的值为 key 的结点的存储位置；否则返回 NULL	*/
LNode* node_locate(LinkList list, int key) {if (list == nullptr || list->next == nullptr) {return nullptr;}LNode* cur = list->next;for (; cur != nullptr && cur->data != key; cur = cur->next);return cur == nullptr || cur->data != key ? nullptr : cur;
}

3.4.插入元素

/*** 插入运算是将值为 e 的新结点插入到表的第 i 个结点的位置上，即插入到 ai-1 与 ai之间。*/
bool list_insert(LinkList list, int i, int e) {if (list == nullptr) {return false;}LNode* cur = list;//head nodefor (int j = 1; cur != nullptr && j < i; cur = cur->next)j += 1;if (cur == nullptr) {//cur point (i-1) nodereturn false;}LNode* node = node_create(e, cur->next);cur->next = node;return true;
}

3.5.删除元素

3.5.1.按序号删除

/*** 按序号删除* 删除单链表中的第 i 个结点* 时间复杂度也是 O（n）*/
bool list_delete(LinkList list, int i, int* e) {if (list == nullptr || list->next == nullptr) {return false;}LNode* cur = list;for (int j = 1; cur != nullptr && j++ < i; cur = cur->next);//cur结点指向a[i-2]结点if (cur == nullptr || cur->next == nullptr) {return false;}LNode* curi = cur->next;//curi结点指向a[i-1]结点，需要被删除if (e != nullptr) {*e = curi->data;}cur->next = curi->next;free(curi);return true;
}

3.5.2.按值删除

/*** 按值删除* 删除单链表中值为 key 的第一个结点。*/
bool list_delete(LinkList list, int key) {if (list == nullptr || list->next == nullptr) {return false;}LNode* prev = list,*curr = list->next;while(curr != nullptr && curr->data != key) {prev = curr;curr = curr->next;}if (curr == nullptr || curr->data != key) {//未找到，返回失败return false;}prev->next = curr->next;free(curr);//释放被删除元素的内存空间return true;
}

3.5.3.按值删除变形1

/*** 按值删除* 删除单链表中值为 key 的所有结点。*/
bool list_delete_all(LinkList list, int key) {if (list == nullptr || list->next == nullptr) {return false;}LNode *prev = list, *curr = list->next;while (curr != nullptr) {if (curr->data == key) {prev->next = curr->next;free(curr);curr = prev->next;}else {prev = curr;curr = curr->next;}}return true;
}

3.5.4.按值删除变形2

/*** 去重函数* 删除单链表中所有值重复的结点，使得所有结点的值都不相同* 基本思想：从单链表的第一个结点开始，对每个结点进行检查：检查链表中该结点的所有后继结点，只要有值和该结点的值相同，则删除之；然后检查下一个结点，直到所有的结点都检查。*/
bool list_unique(LinkList list) {if (list == nullptr || list->next == nullptr) {return false;}LNode* curr = list->next;while (curr != nullptr) {LNode* pi = curr->next;//内层循环指针LNode* prev = curr;//内层循环指针while (pi != nullptr) {if (curr->data == pi->data) {prev->next = pi->next;free(pi);pi = prev->next;}else {prev = pi;pi = pi->next;}}curr = curr->next;}return true;
}

3.6.链表合并

/*** 设有两个有序的单链表，它们的头指针分别是 La 、Lb，将它们合并为以 Lc 为头指针的有序链表若 La，Lb 两个链表的长度分别是 m，n，则链表合并的时间复杂度为 O(m+n)*/
LinkList merge_linklist(LinkList la, LinkList lb) {if (la == nullptr || la->next == nullptr) {//la为空，直接返回lbreturn lb;}else if (lb == nullptr || lb->next == nullptr) {return la;}LinkList lc = list_create();LNode* pc = lc;LNode* pa = la->next, * pb = lb->next;//[1]每次从la,lb取出数据并比较，将小的数据存入lcwhile (pa != nullptr && pb != nullptr) {if (pa->data <= pb->data) {pc->next = node_create(pa->data, nullptr);pc = pc->next;pa = pa->next;}else {pc->next = node_create(pb->data, nullptr);pc = pc->next;pb = pb->next;}}//[2]lb的数据取完，将剩余la数据全部存入lcwhile (pa != nullptr) {//pb == nullptr pc->next = node_create(pa->data, nullptr);pc = pc->next;pa = pa->next;}//[3]la的数据取完，将剩余lb数据全部存入lcwhile (pb!= nullptr) {//pa == nullptrpc->next = node_create(pb->data, nullptr);pc = pc->next;pb = pb->next;}return lc;
}

3.7.辅助函数

3.7.1.打印链表

/*** 打印单链表(辅助函数)*/
bool list_print(LinkList list) {if (list == nullptr) {return false;}printf("[");for (LNode* cur = list->next; cur != nullptr; cur = cur->next) {printf("%d", cur->data);printf("%s", cur->next == nullptr ? "" : ",");}printf("]\n");
}

3.7.2包含头文件

#ifndef __IOSTREAM_H__
#define __IOSTREAM_H__
#include <iostream>
#endif#ifndef __STDIO_H__
#define __STDIO_H__
#include <stdio.h>
#endif#ifndef __STDARG_H__
#define __STDARG_H__
#include <stdarg.h>
#endif#ifndef __INITIALIZER_LIST__
#define __INITIALIZER_LIST__
#include <initializer_list>
#endif

3.7.3测试函数

void test1() {LinkList list = list_create({1,2,3,4,5});list_print(list);int e = get_elem(list, 3);printf("%d\n", e);printf("len = %d\n", get_length(list));printf("node_locate(list, 3) = %x\n", node_locate(list, 3));printf("node_locate(list, 7) = %x\n", node_locate(list, 7));list_free(list);
}void test2() {LinkList list = list_create({1,2,3,4});list_print(list);list_insert(list, 2, 8);printf("list_insert(list, 2, 8)\n");list_print(list);list_free(list);
}void test3() {LinkList list = list_create({1,2,3,4});list_print(list);list_delete(list, 2, nullptr);list_print(list);list_delete(list, 2, nullptr);list_print(list);list_delete(list, 2, nullptr);list_print(list);list_free(list);
}void test4() {LinkList list = list_create({1,2,3,4});list_print(list);list_delete(list, 2);list_print(list);list_delete(list, 4);list_print(list);list_free(list);
}void test5() {LinkList list = list_create({1,2,3,6,2,2,7,8});list_print(list);list_delete_all(list, 2);list_print(list);list_free(list);
}void test6() {LinkList list = list_create({ 1,2,3,6,2,2,7,8 });list_print(list);list_unique(list);list_print(list);list_free(list);
}void test7() {LinkList la = list_create({1,3,5,9});LinkList lb = list_create({2,4,6,7,8,10});list_print(la);list_print(lb);LinkList lc = merge_linklist(la, lb);list_print(lc);
}