计划更新23王道数据结构所有课后代码习题的实现，虽然考试写的一般都是伪代码，但是强迫症的我还是全部实现了一遍，仓库在这里
- 线性表 14/14
- 链表 2/25
单链表结构体
#define ElemType int typedef struct LNode{ ElemType data; struct LNode* next; }LNode, *LinkList; 复制代码
我自己定义的一些方法，便于运行，尽量使用 malloc() 和 free() 进行内存管理（考试要求）：
// 创建一个不带头结点的单链表 LinkList createList(vector<int> data) { if (data.size() == 0) return NULL; LNode* head = (LinkList)malloc(sizeof(LNode)); head->data = data[0]; head->next = NULL; LNode* p = head; for (int i = 1; i < data.size(); i++) { LNode* q = (LNode*)malloc(sizeof(LNode)); q->data = data[i]; q->next = NULL; p->next = q; p = q; } return head; } // 创建一个带头结点的单链表 LinkList createHeadList(vector<int> data) { if (data.size() == 0) return NULL; LNode* head = (LinkList)malloc(sizeof(LNode)); head->next = NULL; LNode* p = head; for (int i = 0; i < data.size(); i++) { LNode* q = (LNode*)malloc(sizeof(LNode)); q->data = data[i]; q->next = NULL; p->next = q; p = q; } return head; } // 打印链表 void printList(LinkList L) { while (L != NULL) { cout << L->data << " "; L = L->next; } puts(""); } 复制代码
2.3.7, 1
- 链表具有天然的递归性，每一个结点都可以看作一个小的链表，它们又可以互相组合成新的链表
- 递归就是函数直接或间接调用函数本身
- 实现递归函数只需要弄明白两件事情：递推关系和递归出口
- 本题中递推关系是：当前结点为x就删除，不为x就处理下一个结点
- 递归出口是：当前结点为空
- 因为递归深度为O(n)，所以时间复杂度O(n)，空间复杂度O(n)
void delX(LinkList &L, int x) { if (L == NULL) return; // 1.递归出口 LNode* p; if (L->data == x) { // 2.L结点的值为x，删除L结点 p = L; L = L->next; free(p); delX(L, x); } else { // 3.L结点的值不为x，递归处理L结点的下一个结点 delX(L->next, x); } } 复制代码
2.3.7, 2
- 与第一题唯一不同就是带头结点，同样可以使用第一题的递归，函数完全不需要任何改变
void delX(LinkList &L, int x) { if (L == NULL) return; // 1.递归出口 LNode* p; if (L->data == x) { // 2.L结点的值为x，删除L结点 p = L; L = L->next; free(p); delX(L, x); } else { // 3.L结点的值不为x，递归处理L结点的下一个结点 delX(L->next, x); } } // 调用 delX(head->next, 3); 复制代码
- 经典双指针，p从头到尾扫描整个链表，pre指向p的前一个结点便于删除
- 时间复杂度O(n)，空间复杂度O(1)
void delX2(LinkList &L, int x) { LNode *pre = L, *p = L->next, *q; while (p != NULL) { if (p->data == x) { q = p; p = p->next; pre->next = p; free(q); } else { pre = p; p = p->next; } } }
