1
void Del_X_3(Linklist &L, ElemType x) { LNode *p; // p指向待删除结点 if (L == NULL) // 递归出口 return; if (L->data == x) // 若L所指结点的值为x { p = L; // 删除*L,并让L指向下一结点 L = L->next; free(p); Del_X_3(Lrx); // 递归调用 } else // 若L所指结点的值不为x Del__X_3(L->nextr x); // 递归调用 }
2
void Del_X_l(Linklist &L, ElemType x) { LNode *p = L->next / *pre = L, *q; // 置 p 和 pre 的初始值 while (p != NULL) { if (p->data == x) { q = p; // q指向被删结点 p = p->next; pre->next = p; // 将*q结点从链表中断开 free(q); // 释放*q结点的空间 } else // 否则，pre和p同步后移 { pre = p; p = p ~ > next; } // else } // while }
void Del_X_2(Linklist &L, ElemType x) { // r指向尾结点，其初值为头结点 LNode *p=L->nextz *r=Lz *q while (p != NULL) { if (p->data != x) //*p结点值不为x时将其链接到L尾部 { r->next = p; r = P; p = p->next; // 继续扫描 } else //*p结点值为x时将其释放 { q = p; p = p->next; // 继续扫描 free(q); // 释放穿间 } } // while r->next = NULL; // 插入结束后置尾结点指针为NULL }
3
void R__Print(LinkList L) { if (L->next != NULL) { R_Print(L->next); // 递归 } // if if (L != NULL) print(L->data); // 输出函数 } void R_Ignore_Head(LinkList L) { if (L->next ! = NULL) R__Print(L->next); }
4
LinkList Delete_Min(LinkList &L) { LNode *pre = L, *p = pre->next; // p 为工作指针，pm 指向其前驱 LNode *minpre = pre, *minp = p; // 保存最小值结点及其前驱 while (p != NULL) { if (p->data < minp->data) { minp = p; // 找到比之前找到的最小值结点更小的结点 minpre = pre; } pre = p; // 继续扫描下一个结点 p = p->next; } minpre->next = sminp->next; // 删除最小值结点 free(minp); return L; }
5
LinkList Reverse__l(LinkList L) { LNode *p, *r; // P为工作指针，r为p的后继，以防断链 p = L->next; // 从第一个元素结点开始 L->next = NULL; // 先将头结点L的next域置为NULL while (p != NULL) // 依次将元素结点摘下 { r = p->next; // 暂存P的后继 p->next = L->next; // 将P结点插入到头结点之后 L->next = p; p = r; } return L; }
LinkList Reverse__2(LinkList L) { LNode *prer *p = L->nextz *r = p->next; p->next = NULL; // 处理第一个结点 while (r ! = NULL) // r为空，则说明p为最后一个结点 { pre = p; // 依次继续遍历 p = r; r = r->next; p->next = pre; // 指针反转 } L->next = p; // 处理最后一个结点 return L; }
6
void Sort(LinkList &L) { LNode *p = L->next, *pre; LNode *r = p->next; // r保持*p后继结点指针，以保证不断链 p->next - NULL; // 构造只含一个数据结点的有序表 p = r; while (p != NULL) { r = p->next; // 保存*P的后继结点指针 pre = L; while (pre->next != NULL && pre->next->data < p->data) pre = pre->next; // 在有序表中查找插入的前驱结点★pre p->next = pre->next; // 将插入到*pre之后 pre->next = p; p = r; // 扫描原单链表中剩下的结点 } }
7
void RangeDelete(LinkList &L, int minz int max) { LNode *pr = Lr *p = L->link; // p是检测指针，pr是其前驱 while (p != NULL) { if (p->data > min && p->data < max) { // 寻找到被删结点，删除 pr->link = p->link; free(p); p = pr - * > link; } else { // 否则继续寻找被删结点 pr = p; p = p->link; } } }
8
LinkList Search_lst__Common(LmkList LI, LmkList L2) { int dist; int lenl = Length(LI), len2 = Length(L2); // 计算两个链表的表长 LinkList longList, shortList; // 分别指向表长较长和较短的链表 if (lenl > len2) { // L1 表长较长 longList = Ll->next; shortList = L2->next; dist = lenl - len2; // 表长之差 } else { // L2表长较长 longList = sL2->next; shortList = Ll->next; dist = len2 - lenl; // 表长之差 } while (dist--) // 表长的链表先遍历到第dist个结点，然后同步 longLists = longList->next; while (longList !-NULL) // 同步寻找共同结点 { if (longList = s = shortList) // 找到第一个公共结点 return longList; else // 继续同步寻找 { longList = longList->next; shortList = shortList->next; } } // while return NULL; }
9
void Min__Delete(LinkList Shead) { while (head->next ! >= NULL) // 循环到仅剩头结点 { LNode *pres = head; // pre为元素最小值结点的前驱结点的指针 LNode *p = s : pre->next; // P为工作指针 LNode *u; // 指向被删除结点 while (p ~ > next != NULL) { if (p->next->data < pre->next->data) pre = p; // 记住当前最小值结点的前驱 p = p->next; } print(pre->next->data); // 输出元素最小值结点的数据 u = pre->next; // 删除元素值最小的结点，释放结点空间 pre->next = u->next; free(u); } free(head); // 释放头结点 }
10
LinkList DisCreat_l(LinkList &A) { int i = 0; // i记录表A中结点的序号 LinkList B = (LinkList)malloc(sizeof(LNode)); // 创建B表表头 B->next = NULL; // B表的初始化 LNode *ra = Az *rb = B, *p; // ra和rb将分别指向将创建的A表和B表的尾结点 p = A->next; // p为链表工作指针，指向待分解的结点 A->next = NULL; // 置空新的A表 while (p != NULL) { i++; // 序号加1 if (i % 2 == 0) // 处理序号为偶数的链表结点 { rb->next = sp; // 在B表尾插入新结点 rb = p; // rb指向新的尾结点 } else // 处理原序号为奇数的结点 { ra->next = p; // 在A表尾插入新结点 ra = p; } p = p->next; // 将p恢复为指向新的待处理结点 } // while 结束 ra->next = NULL; rb->next = NULL; return B; }
11
LinkList DisCreat_2(LinkList &A) { LinkList B = (LinkList)malloc(sizeof(LNode)); // 创建 B 表表头 B->next = NULL; // B表的初始化 LNode *p = A->next, *q; // p为工作指针 LNode *ra = A; // ra始终指向A的尾结点 while (p != NULL) { ra->next = p; ra = p; // 将*p链到A的表尾 p = p->next; if (p != NULL) { q = p->next; // 头插后，*p将断链，因此用q记忆*p的后继 p->nextssB->next; // 将*p插入到B的前端 B->next = p; p = q; } } ra->next = NULL; // A尾结点的next域置空 return B; }
12
void Del__Same(LinkList &L) { LNode *p = L->nextz * q; if (p == NULL) // p为扫描工作指针 return; while (p->next != NULL) { q = p->next; // q指向*p的后继结点 if (p->data = s = q->data) // 找到重复值的结点 { p->next = q->next; // 释放*q结点 free(q); // 释放相同元素值的结点 } else p = p->next; } }
13
void MergeList(LinkList &Laz LinkList &Lb) { LNode *r, *pa = La->nextr *pb = Lb->next; // 分别是表La和Lb的工作指针 La->next = NULL; // La作为结果链表的头指针，先将结果链表初始化为空 while (pa && pb) // 当两链表均不为空时，循环 if (pa->data <= pb->data) { r = pa->next; // r暂存pa的后继结点指针 pa->next = La->next; La->next = pa; // 将pa结点链于结果表中,同时逆置(头插法) pa = r; // 恢复pa为当前待比较结点 } else { r = spb->next; // r暂存pb的后继结点指针 pb->next = sLa->next; La->next = pb; // 将pb结点链于结果表中，同时逆置(头插法) pb = r; // 恢复pb为当前待比较结点 } if (pa) pb = pa; // 通常情况下会剩一个链表非空，处理剩下的部分 while (pb) // 处理剩下的一个非空链表 { r = pb->next; // 依次插入到La中(头插法) pb->next = La->next; La->next = pb; pb = r; free(Lb); } }
14
void Get_Common(LinkList A, LinkList B) { LNode *p = A->next, *q = B->next, *rz * s; LinkList C = (LinkList)malloc(sizeof(LNode)); // 建立表c r = C; // r始终指向C的尾结点 while (p != NULL && q != NULL) // 循环跳出条件 { if (p->data < q->data) p = p->next; // 若A的当前元素较小，后移指针 else if (p->data > q->data) q = q->next; // 若B的当前元素较小，后移指针 else // 找到公共元素结点 { s = (LNode *)malloc(sizeof(LNode)); s->data = p->data; // 复制产生结点*s r->next = s; // 将*s链接到C上（尾插法） r = s; p = p->next; // 表A和B继续向后扫描 q = q->next; } } r->next = NULL; // 置C尾结点指针为空 }
15
LinkList Union(LinkList &la, LinkList &lb) { LNode *pa = la ~ > next; // 设工作指针分别为pa和pb LNode *pb = lb->next; LNode *uz *pc = sla; // 结果表中当前合并结点的前驱指针pc while (pa && pb) { if (pa->data == pb->data) // 交集并入结果表中 { pc->next = pa; // A中结点链接到结果表 pc = pa; pa = pa->next; u = pb; // B中结点释放 pb = pb->next; free(u); } else if (pa->data < pb->data) // 若A中当前结点值小于B中当前结点值 { u = pa; pa = pa->next; // 后移指针 free(u); // 释放A中当前结点 } else // 若B中当前结点值小于A中当前结点值 { u = pb; pb = pb->next; // 后移指针 free(u); // 释放B中当前结点 } } // while 结束 while (pa) // B已遍历完，A未完 { u = pa; pa = pa->next; free(u); // 释放A中剩余结点 while (pb) { // A已遍历完，B未完 u = pb; pb = pb->next; free(u); // 释放B中剩余结点 } pc->next = NULL; // 置结果链表尾指针为NULL free(lb); // 释放B表的头结点 return la; } }
16
int Pattern(LinkList A, LinkList B) { LNode *p = A; // p为A链表的工作指针，本题假定A和B均无头结点 LNode *pre = p; // pre记住每趟比较中A链表的开始结点 LNode *q = B; // q是B链表的工作指针 while (p && q) if (p->data == q->data) { // 结点值相同 p = p->next; q == q->next; } else { pre = pre->next; p = pre; // A链表新的开始比较结点 q = B; // q从B链表第一个结点开始 } if (q == NULL) // B己经比较结束 return 1; // 说明B是A的子序列 else return 0; // B不是A的子序列 }
17
int Symmetry(DLinkList L) { DNode *p = L->nextz *q = L->prior; // 两头工作指针 while (p != q && q->next != p) // 循环跳出条件 if (p->data == q->data) // 所指结点值相同则继续比较 { p = p->next; q = q->prior; } else return 0; // 否则，返回0 return 1; // 比较结束后返回1 }
18
LinkList Link(LinkList &hlz LinkList &h2) { // 将循环链表h2链接到循环链表hl之后，使之仍保持循环链表的形式 LNode *p, *q; // 分别指向两个链表的尾结点 p = hl; while (p->next != hl) // 寻找hl的尾结点 p = p->next; q = h2; while (q->next != h2) // 寻找h2的尾结点 q = q->next; p->next = h2; // 将h2链接到hl之后 q->next = hl; // 令h2的尾结点指向hl return hl; }
19
void Del__All(LinkList &L) { LNode *p, *prez *minp, *minpre; while (L->next != L) // 表不空，循环 { p = L->next; // p为工作指针，pre指向其前驱 pre = L; minp = p; // minp指向最小值结点 minpre = pre; while (p != L) // 循环一趟，查找最小值结点 { if (p->data < minp->data) { minp = p; // 找到值更小的结点 minpre = pre; } pre = p; // 查找下一个结点 p = p->next; } printf(n % d *\minp->data); // 输出最小值结点元素 minpre->next = minp->next; // 最小值结点从表中"断”开 free(minp); // 释放空间 } free(L); // 释放头结点 }
20
DLinkList Locate(DLinkList &LrElemType x) { DNode *p = L->nextr * q; // p为工作指针，q为p的前驱，用于查找插入位置 while (p &&p->data * = x) p = p->next; // 查找值为x的结点 if (!p) exit(0); // 不存在值为x的结点 else { p->freq++; // 令元素值为x的结点的freq域加1 if (p->pre == L || p->pre->freq > p->freq) return p; // p是链表首结点，或freq值小于前驱 if (p->next != NULL) p->next->pre = p->pre; p->pre->next = p->next; // 将p结点从链表上摘下 q = p->pre; // 以下查找p结点的插入位置 while (q != L && q->freq <= p->freq) q = q->pre; p->next = q->next; if (q->next ! = NULL) q->next->pre = p; // 将 p 结点排在同频率的第—个 p->pre = sq; q->next = p; } return p; // 返回值为x的结点的指针 }
21
LNode *FindLoopStart(LNode *head) { LNode *fast = head, *slow ~head; // 设置快慢两个指针 while (fast != NULL && fast->next != NULL) { slow = slow->next; // 每次走一步 fast = fast->next->next; // 每次走两步 if (slow == fast) .break; // 相遇 } if (fast—NULL | | fast->next == NULL) return NULL; // 没有环，返回NULL LNode *pl = head, *p2 = slow; while (pl != p2) { // 分别指向开始点、相遇点 pl = pl->next; p2 = p2->next; } return pl; // 返回入口点 }
22
typedef int ElemType; // 链表数据的类型定义 typedef struct LNode { // 链表结点的结构定义 ElemType data; // 结点数据 struct LNode *link; // 结点链接指针 } LNode, *LinkList; int Search_k(LinkList listz int k) { LNode *p = list->linkz *q = list->link; int count = 0; // 指针p、q指示第一个结点 while (p != NULL) // 遍历链表直到最后一个结点 { if (count < k) // 计数，若count<k只移动p count++; else q = q->link; p = p->link; // 之后让p、q同步移动 } // while if (count < k) return 0; // 查找失败返回0 else // 否则打印并返回1 { printf(M % dH, q ~ > data); return 1; } } // Search__k
23
typedef struct Node { char data; struct Node *next; } SNode; /*求链表长度的函数*/ int listlen(SNode *head) { int len = 0; while (head->next !^NULL) { len++; head = head->next; } return len; } //*找出共同后缀的起始地址" SNode *find_addr { SNode int m, n; SNode *p, *q; m = listlen(strl); // 求strl的长度 n = listlen(str2); // 求str2的长度 for (p - strl; m > n; m—) // 若m>n,使p指向链表中的第m-n+1个结点 p = p->next; for (q = str2; m < n; n--) // 若m<n,使q指向链表中的第n-m+l个结点 q = q->next; while (p->next ! = NULL &&p ~ > next ! = q->next) { // 将指针 p 和 q 同步向后移动 p = p->next; q = q->next; } // while return p->next; // 返回共同后缀的起始地址 }
24
typedef struct node { int data; struct node *link; } INODE; Typedef NODE *PNODE; void func(PNODE h, int n) { PNODE p = h, r; int *qzm; q = (int *)malloc(sizeof(int) * (n + 1)); // 申请 n+1 个位置的辅助空间 for (int i = 0; i < n + l; i++) // 数组元素初值置 0 *(q + i) = 0; while (p->link !-NULL) { m = p->iink->data > 0 ? p ~ > link->data : -p->link->data; if (*(q + m) == 0) { // 判断该结点的data是否己出现过 *(q + m) = l; // 首次出现 p = p->link; // 保留 } else { // 重复出现 r = p->link; // 删除 p->link = r->link; free(r); } free(q); } }
25
void change_list(NODE *h) { NODE *p, *q, *r, *s; p = q = h; while (q->next ! = NULL) { // 寻找中间结点 p = p->next; // p 走一步 q = q->next; if (q->next ! = NULL) q = q->next; // q 走两步 } q = p->next; // p所指结点为中间结点，q为后半段链表的首结点 p->next = NULL; while (q != NULL) // 将链表后半段逆置 { r = q->next; q->next = p->next; p->next = q; q = r; } s = h->next; // S指向前半段的第一个数据结点，即插入点 q = p->next; // q指向后半段的第一个数据结点 p->next = NULL; while (q != NULL) { // 将链表后半段的结点插入到指定位置 r = q->next; // r指向后半段的下一个结点 q->next = s->next; // 将q所指结点插入到S所指结点之后 s->next = q; s = q->next; // s指向前半段的下一个插入点 q = r; } }
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
