1.定义
typedef int ElemType; typedef struct LinkNode { ElemType data; struct LinkNode* next; }LinkNode, *LinkList;
2.初始化单链表(带头结点)
bool initList(LinkList& L) { L = (LinkNode*)malloc(sizeof(LinkNode)); if (L == NULL) return false; L->next = NULL; return true; }
3.判断链表为空
bool emptyList(LinkList L) { return (L->next == NULL); }
4. 创建单链表
4.1 头插法建立单链表
算法思想
- 先将插入结点的指针域修改为L的后继
- 再将头结点L的后继更新为 pNode
代码
void headInsertCreateList(LinkList& L, int arr[], int arrLength) { // 初始化单链表,带头结点 L = (LinkNode*)malloc(sizeof(LinkNode)); L->next = NULL; LinkNode* pNode = NULL; // 将每个元素加入链表中 for (int idx = 0; idx < arrLength; idx++) { pNode = (LinkNode*)malloc(sizeof(LinkNode)); pNode->data = arr[idx]; // step1:先将插入结点指针域修改为L的后继 pNode->next = L->next; // step2:再将头结点L的后继更新为pNode L->next = pNode; } }
4.2 尾插法建立单链表
算法思想
- 先将插入结点的指针域改为tail指针的指针域
- 尾指针后继改为pNode
- 更新尾指针
代码
void tailInsertCreateList(LinkList& L, int arr[], int arrLength) { // 初始化单链表,带头结点 L = (LinkNode*)malloc(sizeof(LinkNode)); L->next = NULL; LinkNode* tail = L; // 表尾结点指针 LinkNode* pNode = NULL; for (int i = 0; i < arrLength; i++) { pNode = (LinkNode*)malloc(sizeof(LinkNode)); pNode->data = arr[i]; // step1:先将插入结点的指针域改为tail指针的指针域 pNode->next = tail->next; // step2:尾指针后继改为pNode tail->next = pNode; // step3:更新尾指针 tail = pNode; } }
5.链表递归
问题
L为带头结点的单链表,使用递归求解:
(1)求单链表中的最大整数
(2)求链表中的结点数
(3)求链表中所有元素的平均值
算法思想
带头结点的链表,递归时,需要将头结点和其他数据结点分开,因为头结点不存数据。
注意递归的终止条件,
代码
求链表中的最大值
int getListMaxValue(LinkNode* pNode) { if (pNode == NULL) return INT_MIN; // 递归求解L后面的最大值 ElemType tmp = getListMaxValue(pNode->next); return tmp > pNode ->data ? tmp : pNode ->data; }
求链表的结点数量
int getListNodes(LinkNode* pNode) { if (pNode == NULL) return 0; // pNode 后子表长度 + 当前结点数 return getListNodes(pNode->next) + 1; }
求链表的元素之和
int getListElemSum(LinkNode* pNode) { if (pNode == NULL) return 0; // L 当前结点元素 + L后结点元素之和 return pNode->data + getListElemSum(pNode->next); }
求链表元素的平均值
float getListElemAverage(LinkList L) { LinkNode* pNode = L->next; int sum = getListElemSum(pNode); int nodes = getListNodes(pNode); return (float)sum / nodes; }
6.链表插入
6.1 按位序插入
问题
在第i个位置插入元素e
算法思想
- 一个只有头结点的空链表,链中存在0个数据结点,因此就可以将头结点是为单链表中第0个数据结点。
- 使用计数器,每访问一个结点,计数器就增加一。
- 适用于结点编号的场景。
注意边界条件
代码
bool insertElemList(LinkList& L, int i, ElemType elem) { if (i < 1) return false; // 当前扫描到的结点 LinkNode* curNode = L; // 当前curNode是第几个结点 int idxCurNode = 0; while (curNode != NULL && idxCurNode < i - 1) { curNode = curNode->next; idxCurNode++; } // i值不合法 if (curNode == NULL) return false; LinkNode* tmp = (LinkNode*)malloc(sizeof(LinkNode)); tmp->data = elem; // 将结点tmp连接到curNode之后 tmp->next = curNode->next; curNode->next = tmp; return true; }
6.2 后插操作
问题
在pNode结点之后插入元素elem
算法思想
注意不要断链
代码
bool nextInsertElemList(LinkNode* pNode, ElemType elem) { if (pNode == NULL) return false; LinkNode* tmp = (LinkNode*)malloc(sizeof(LinkNode)); if (tmp == NULL) return false; tmp->data = elem; // 将tmp结点插入pNode之后 tmp->next = pNode->next; pNode->next = tmp; return true; }
6.3 前插操作
问题
在pNode结点之前插入元素elem
算法思想
pNode后面插入一个结点tmp,将pNode结点的数据复制到tmp结点,新数据放入pNode结点
代码
bool priorInsertElemList(LinkNode* pNode, ElemType elem) { if (pNode == NULL) return false; LinkNode* tmp = (LinkNode*)malloc(sizeof(LinkNode)); if (tmp == NULL) return false; // 将pNode的元素复制到tmp中 tmp->data = pNode->data; // 新元素复制到pNode中 pNode->data = elem; // 将tmp插入pNode之后,实现前插操作 tmp->next = pNode->next; pNode->next = tmp; return true; }
7.链表删除
7.1 按位序删除
问题
删除单链表中第i个结点
算法思想
- 寻找链表中的第 i-1 个结点(删除结点的前一个)
- 删除第i个结点
代码
bool deleteElemList(LinkList& L, int i, ElemType& elem) { if (i < 1) return false; // 当前扫描到的结点 LinkNode* curNode = L; // 当前curNode是第几个结点 int idxCurNode = 0; while (curNode != NULL && idxCurNode < i - 1) { curNode = curNode->next; idxCurNode++; } // 索引i不合法 if (curNode == NULL) return false; // 第i-1个结点之后无其他结点 if (curNode->next == NULL) return false; // 暂存要删除的结点 LinkNode* tmp = curNode->next; elem = tmp->data; // 将删除的结点从链表中断开 curNode->next = tmp->next; // 释放内存 free(tmp); return true; }
7.2 删除指定结点
问题
删除指定结点
算法思想
- 取出该结点的后继,
- 将后继的值赋予自身;
- 删除后继结点;
- 时间复杂度为O(1)
代码
bool deleteListNode(LinkNode* pNode) { if (pNode == NULL) return NULL; // pNode后继结点 LinkNode* nextNode = pNode->next; // 将pNode的后继结点的值复制到pNode中 pNode->data = nextNode->data; // 将pNode的后继从链断开 pNode->next = nextNode->next; // 释放空间 free(nextNode); return false; }
8.链表查找
8.1 按位查找
问题
按位查找,返回第i个元素(带头结点)
算法思想
- 注意终止条件
- 使用计数器标记访问过结点的数量
代码
LinkNode* getElemList(LinkList L, int i) { if (i < 1) return false; // 当前扫描到的结点 LinkNode* pNode = L; // 当前curNode是第几个结点 int idxNode = 0; while (pNode != NULL && idxNode < i) { pNode = pNode->next; idxNode++; } return pNode; }
8.2 按值查找
问题
按值查找
算法思想
- 注意区分终止条件
代码
LinkNode* localElemList(LinkList L, ElemType elem) { LinkNode* pNode = L->next; // 从第一个结点开始查找数据域为elem的结点 while (pNode != NULL && pNode->data != elem) { pNode = pNode->next; } return pNode; }
8.3 查找倒数第m个结点
问题
设计高效算法查找带头结点单链表倒数第m个位置(m为正整数)的结点,并输出该结点的值
算法思想
- 先搜索距离第一个数据结点m个位置的元素,即用指针pCur指向第m+1个数据结点;
- 然后用pNode指向第一个结点,此时两个指针之间相距m个元素;
- 后移两个指针,当pCur指向空结点时,pNode指向距离空结点m个位置的结点;
- 此时,pNode结点即为倒数第m个结点。
代码
LinkNode* getRevElem(LinkList L, int m) { // 指向头结点 LinkNode* pCur = L; // 头结点为第0个结点 int nodeNum = 0; // 依次访问结点,查找第m个结点 while (pCur != NULL) { // 结点编号加一 nodeNum++; // 找到第m个结点 if (nodeNum == m) { // 指向第m个结点 pCur = pCur->next; // 停止查找 break; } pCur = pCur->next; } // 指向第m+1个元素 pCur = pCur->next; LinkNode* pNode = L->next; // 将pCur移动到表末尾空结点 while (pCur != NULL) { pNode = pNode->next; pCur = pCur->next; } return pNode; }
9.其他
9.1 合并链表
问题
已知单链表La和Lb的元素按值非递减排列
合并La,Lb后的新链表Lc也按非递减排列
算法思想
- 注意和顺序表的区分
代码
void mergeList(LinkList La, LinkList Lb, LinkList& Lc) { LinkNode* paNode = La->next; LinkNode* pbNode = Lb->next; // 用La的头结点作为Lc的头结点 /*LinkNode* pcNode = La; Lc = pcNode;*/ LinkNode* pcNode = Lc; while (paNode != NULL && pbNode != NULL) { if (paNode->data <= pbNode->data) { pcNode->next = paNode; pcNode = pcNode->next; paNode = paNode->next; } else { pcNode->next = pbNode; pcNode = pcNode->next; pbNode = pbNode->next; } } pcNode->next = paNode ? paNode : pbNode; }
测试代码
// 链表合并 printf("链表合并\n"); int arr1[] = {8,7,6,5,4,3,2,1}; int arr1Length = 8; LinkList Lc, Ld, Le; headInsertCreateList(Lc, arr1, arr1Length); headInsertCreateList(Ld, arr1, arr1Length); initList(Le); printList(Lc); printList(Ld); printList(Le); mergeList(Lc,Ld, Le); printList(Le);

9.2 链表逆置
问题
链表逆置
算法思想
- 将头结点取下,从第一个结点开始;
- 依次插到头结点后面(头插法建立单链表)
- 直到最后一个结点为止
代码
void reverseList(LinkList& L) { // 工作指针,先指向链表头结点 LinkNode* pNode = L->next; // pNode的后继,防止断链 LinkNode* nextNode; // 将L的头结点置为NULL,准备用头插法 L->next = NULL; // 依次取下头节点,使用头插法插入 while (pNode != NULL) { // 暂存pNode结点 nextNode = pNode->next; // 将pNode结点插入到头节点之后 pNode->next = L->next; L->next = pNode; // 更新pNode结点 pNode = nextNode; } }