2020考研-王道数据结构-线性表-链表 布满荆棘的人生 2022-02-03 06:19 252阅读 0赞 # 注意 # #### 1. 每道题目以函数的形式给出。 #### #### 2. 为了提高代码的可读性，STL库中的有的函数不在重复，比如Reverse、Swap、Sort等函数。 #### #### 3. 语言采用的是C++11标准，所以大家编译调试的需要注意，某些函数C++98的编译器不支持。 #### #### 4. 数据结构、元素定义、相关辅助函数请看以下定义。 #### typedef int ElemType; typedef struct Node { ElemType data; struct Node *next; }LinkList, *PLinkList; // type == 1 带头节点 // 计算链表的长度 int length(PLinkList &la, int type) { int res = 0; PLinkList tmp = la; while (tmp){ res++; tmp = tmp->next; } return type ? res - 1 : res; } // type == 0, 不带头节点， type == 1 带头节点 // 顺次打印链表 void printLinkList(PLinkList list, int type) { if (list == NULL) return; PLinkList tmp = list; if (type == 1) tmp = list->next; while (tmp) { cout << tmp->data << " "; tmp = tmp->next; } cout << endl; return; } // type == 0, 不带头节点， type == 1 带头节点 // 创建一个链表 void createLinkList(PLinkList &list, int type, int len) { PLinkList tmp = list; // 如果先前传进来的list列表不是空表就释放掉 while (list){ list = list->next; free(tmp); tmp = list; } // 建表 list = new LinkList(); list->next = NULL; tmp = list; for (int i = 0; i < len; i++) { tmp->next = new LinkList(); tmp->next->next = NULL; tmp->next->data = rand() % 10; tmp = tmp->next; } if (type == 0) { tmp = list; list = list->next; free(tmp); } return; } # 1. 第一题 # ##### 题目简述 ##### 删除不带头节点的链表中所有值为x的元素，递归实现。 ##### 代码 ##### // P1 删除所有值为x的结点 不带头节点，递归实现 void delete_x_nohead(PLinkList &list, ElemType x) { if (list == NULL) return; if (list->data == x) { PLinkList tmp = list; list = list->next; free(tmp); } delete_x_nohead(list->next, x); } # 2. 第二题 # ##### 题目简述 ##### 删除带头节点的链表中所有值为x的元素。 ##### 代码 ##### // P2 删除所有值为x的节点 带头节点 void delete_x_head(PLinkList &list, ElemType x) { PLinkList tmp = list; PLinkList del = NULL; while (tmp->next) { if (tmp->next->data == x) { del = tmp->next; tmp->next = del->next; free(del); } else tmp = tmp->next; } return; } # 3. 第三题 # ##### 题目简述 ##### 反向输出带头节点的链表。 ##### 题目思路 ##### 很简单的一种递归，和栈的原理一样，需要注意的是，如果是带头节点的链表传参时，应该略过头节点，比如反向输出带头节点的链表list时，应该传入**reversePrintLinkList(list->next)。** ##### 代码 ##### // P3 L带头节点，反向输出链表 void reversePrintLinkList(PLinkList list) { if (list == NULL) return; reversePrintLinkList(list->next); cout << list->data << " "; return; } # 4. 第四题 # ##### 题目简述 ##### 带头节点的链表中删除最小值的元素。 ##### 代码 ##### // p4 带头节点删除最小值元素 void delete_min(PLinkList &list) { PLinkList minp = list; PLinkList tmp = list; while (tmp->next) { if (tmp->next->data < minp->next->data) { minp = tmp; } tmp = tmp->next; } PLinkList delp = minp->next; minp->next = delp->next; free(delp); return; } # 5. 第五题 # ##### 题目简述 ##### 将带头节点的单链表倒置，不允许使用额外空间。 ##### 代码 ##### // p5 倒置带头节点的链表， 不允许使用额外空间 void reverseLinkList(PLinkList &list) { PLinkList cur = list->next, tail = NULL; while (cur) { PLinkList p = cur->next; cur->next = tail; tail = cur; cur = p; } list->next = tail; return; } # 6. 第六题 # ##### 题目简述 ##### 将带头节点的单链表按升序排序。 ##### 题目思路 ##### 课本上给出的做法时使用插入排序，那样做的时间复杂度时O(n\*n)，下面这种做法是课本中提到的第二种以空间换时间的一种做法，先放到数组里再利用快排进行排序，最后再放回单链表，这样做的时间复杂度是O(n \* lg(n))。 ##### 代码 ##### // p6 头节点的单链表，使其递增有序， 书上的第二种方法 空间换时间 时间复杂度 O(n*lg(n)) void sort_headLinkList(PLinkList &list) { vector<ElemType> vec; PLinkList tmp = list; while (tmp->next) { vec.push_back(tmp->data); tmp = tmp->next; } sort(vec.begin(), vec.end()); tmp = list->next; for (int i = 0; i < vec.size(); i++, tmp = tmp->next) tmp->data = vec[i]; return; } # 7. 第七题 # ##### 题目简述 ##### 删除带头节点的单链表中，节点的值介于A和B之间的所有节点。 ##### 代码 ##### // p7 删除带头节点的链表中的介于A和B之间的值 void deleteValueInA_B(PLinkList &list, ElemType A, ElemType B) { PLinkList tmp = list; while (tmp->next) { if (tmp->next->data <= B && tmp->next->data >= A) { PLinkList del = tmp->next; tmp->next = del->next; free(del); } else tmp = tmp->next; } return; } # 8. 第八题 # ##### 题目简述 ##### 找出两个带头节点的单链表中的公共节点，并以表的形式返回。 ##### 代码 ##### // p8 找出带头节点两个单链表中的公共节点，并以表lc返回 void findSameNode(PLinkList la, PLinkList lb, PLinkList &lc) { lc = new LinkList(); // 清空表lc, 创建一个头节点 lc->next = NULL; int lena = length(la, 1), lenb = length(lb, 1); if (lena < lenb){ swap(la, lb); swap(lena, lenb); } PLinkList ta = la->next, tb = lb->next; for (int i = 0; i < lena - lenb; i++, ta = ta->next); while (ta && ta != tb){ ta = ta->next; tb = tb->next; } lc = ta; return; } # 9. 第九题 # ##### 题目简述 ##### 升序输出带头节点的单链表，并释放节点。 ##### 代码 ##### // p9 升序输出带头节点的单链表。并释放节点 void printfIncrease(PLinkList la){ PLinkList il = NULL, jl = NULL; PLinkList minl = la; while (la->next){ minl = la; il = la; while (il->next){ if (minl->next->data > il->next->data){ minl = il; } il = il->next; } cout << minl->next->data << " "; jl = minl->next; minl->next = jl->next; free(jl); } return; } # 10. 第十题 # ##### 题目简述 ##### 将带头节点的链表A按照序号为奇数还是偶数，分成两个带头节点的单链表。 ##### 代码 ##### // p10 将带头节点的链表按照奇序号和偶序号分为两个带头节点的链表 void assortWithID1(PLinkList list, PLinkList &la, PLinkList &lb) { la = new LinkList(); la->next = NULL; lb = new LinkList(); lb->next = NULL; //清空两个将要返回值的链表 int cnt = 1; // 节点序号计数器 PLinkList tmp = list->next; PLinkList ta = la, tb = lb; // 记录奇偶链表的尾节点 // 注意这种方式没有产生新的节点，是将list中的节点分到了la，lb中 // 那么，这种方式当while循环结束后，已经改变了list链表 while (tmp) { if (cnt & 1){ // 为奇数保存到链表la ta->next = tmp; ta = tmp; } else{ // 为偶数保存到链表lb tb->next = tmp; tb = tmp; } tmp = tmp->next; cnt++; } ta->next = NULL; tb->next = NULL; } # 11. 第十一题 # ##### 题目简述 ##### 将偶数个元素的、带头节点的链表list，按照奇数、偶数拆分成两个链表， la采用头插法，lb采用尾插法。 ##### 代码 ##### // p11 将偶数个元素的、带头节点的链表list，按照奇数、偶数拆分成两个链表， // la采用头插法，lb采用尾插法 void assortWithID2(PLinkList list, PLinkList &la, PLinkList &lb) { la = new LinkList(); lb = new LinkList(); // 清空将要返回结果的两个单链表 la->next = lb->next = NULL; PLinkList tmp = list->next; PLinkList ta = la; // la是尾插法，所以要记录尾巴的位置 // 因为题目中说了一定是偶数个元素，所以一次循环可以更改两个元素 while (tmp) { ta->next = new LinkList(); // 刚才的p10 说了，那样的做法会改变list 下面这种则不会 ta->next->data = tmp->data; // copy ta->next->next = NULL; ta = ta->next; tmp = tmp->next; PLinkList t = new LinkList(); t->next = lb->next; t->data = tmp->data; lb->next = t; // 头插法， 最好画图模拟，好理解 tmp = tmp->next; } return; } # 12. 第十二题 # ##### 题目简述 ##### 带头节点、有序的单链表中，去掉重复元素。 ##### 代码 ##### // p12 带头节点、有序的单链表中，去掉重复元素 void deWeightLinkList(PLinkList &list) { if (!list->next) return; // 保证链表中至少含有一个元素，否则循环会报错 PLinkList tmp = list->next; while (tmp->next) { if (tmp->data == tmp->next->data) { PLinkList dl = tmp->next; tmp->next = dl->next; free(dl); } else tmp = tmp->next; } return; } # 13. 第十三题 # ##### 题目简述 ##### 将两个带头节点的有序的单链表，合并成一个递减的链表，要求不能产生新节点，要用原来链表中的节点。 ##### 代码 ##### // p13 将两个带头节点的有序的单链表，合并成一个递减的链表 // 要求不能产生新节点，要用原来链表中的节点 void mergeToDecline(PLinkList la, PLinkList lb, PLinkList &lc) { lc = new LinkList(); lc->next = NULL; // 清空链表 PLinkList ta = la->next, tb = lb->next; PLinkList p1 = NULL, p2 = NULL; // 辅助临时节点 while (la || lb){ if (la && lb){ if (la->data > lb->data) p1 = lb, lb = lb->next; else p1 = la, la = la->next; } else if (la) p1 = la, la = la->next; else p1 = lb, lb = lb->next; p1->next = lc->next; lc->next = p1; } return; } # 14. 第十四题 # ##### 题目简述 ##### 要求从la和lb的公共节点中产生表lc，不能破坏表la，lb的节点，其中要求la，lb，lc均为带头节点的单链表。 ##### 代码 ##### // p14 要求从la和lb的公共节点中产生表lc，不能破坏表la，lb的节点 // 都是带头节点的 void getPublicNodeFromAB(PLinkList la, PLinkList lb, PLinkList &lc) { lc = new LinkList(); lc->next = NULL; // 清空表lc PLinkList ta = la->next, tb = lb->next, tc = lc; while (ta && tb) { if (ta->data == tb->data){ tc->next = new LinkList(); tc->next->data = ta->data; tc->next->next = NULL; tc = tc->next; ta = ta->next; tb = tb->next; } else if (ta->data < tb->data) ta = ta->next; else tb = tb->next; } return; } # 15. 第十五题 # ##### 题目简述 ##### 找出链表a和b的交集。 ##### 题目思路 ##### 这个不难看出和上一题的思路是相同的，所以代码完全参考第十四题即可，如果说不同的地方的话，那就是，14题的代码，并没把其余节点释放空间，而15题需要把非公共节点释放掉。 # 16. 第十六题 # ##### 题目简述 ##### 判断表b是不是表a的连续子序列。 ##### 代码 ##### // p16 判断lb是否是la的连续子序列 no test bool isAIncluedB(PLinkList la, PLinkList lb) { PLinkList ta = la->next, tb = lb->next; PLinkList pre = la->next; while (tb && ta){ if (ta->data == tb->data){ ta = ta->next; tb = tb->next; } else { ta = pre->next; tb = lb->next; } } if (tb) return false; return true; } # 17. 第十七题 # ##### 题目简述 ##### 判断循环双链表是否对称。 ##### 代码 ##### #include <iostream> #include <algorithm> #include <cstring> #include <ctime> using namespace std; typedef int Elemtype; typedef struct dnode{ Elemtype data; struct dnode *pre, *next; }DNode, *LDNode; // 创建一个双向循环链表 void createDNode(LDNode &list, int len) { list = new DNode(); list->pre = list; list->next = list; LDNode tail = list; for (int i = 0; i < len; i++) { LDNode tmp = new DNode(); tmp->data = rand() % 2; tmp->next = tail->next; tmp->pre = tail; tail->next->pre = tmp; tail->next = tmp; tail = tmp; } return; } void printFrontToBack(LDNode list) { LDNode tmp = list->next; while (tmp != list) { cout << tmp->data << " "; tmp = tmp->next; } cout << endl; return; } void printBackToFront(LDNode list) { LDNode tmp = list->pre; while (tmp != list) { cout << tmp->data << " "; tmp = tmp->pre; } cout << endl; return; } // 是否对称 bool isSymmetry(LDNode list) { LDNode l = list->next, r = list->pre; while (l != r && l->next != r) { if (l->data != r->data) return false; else { l = l->next; r = r->pre; } } if (l->next == r) return l->data == r->data; return true; } int main() { srand(time(0)); LDNode list = NULL; createDNode(list, 4); printFrontToBack(list); printBackToFront(list); if (isSymmetry(list)) cout << "对称" << endl; else cout << "不对称" << endl; return 0; } # 18.19. 第十八、十九题 # ##### 题目简述 ##### 都是循环单链表的题目，所以代码写到了一起。 18. 把两个循环单链表合并成一个。 19. 循环输出循环单链表中的最小值节点，并释放掉，直至表空。 ##### 代码 ##### #include <iostream> #include <algorithm> #include <cstring> #include <ctime> using namespace std; typedef int Elemtype; typedef struct node { Elemtype data; struct node *next; }LNode, *PLNode; // 创建循环单链表 void createCycleLNode(PLNode &list, int len) { list = new LNode(); list->next = list; PLNode tail = list; for (int i = 0; i < len; i++) { PLNode tmp = new LNode(); tmp->next = tail->next; tmp->data = rand() % 10; tail->next = tmp; tail = tmp; } return; } // 输出循环单链表 void printCycleLNode(PLNode list) { PLNode tmp = list->next; while (tmp != list) { cout << tmp->data << " "; tmp = tmp->next; } cout << endl; return; } // p18 把lb加到la上使之循环结构依旧成立 void addCycleLNode(PLNode &la, PLNode lb) { if (!lb->next) return; PLNode taila = la, tailb = lb; while (taila->next != la) taila = taila->next; // 找到a的尾巴 while (tailb->next != lb) tailb = tailb->next; // 找到b的尾巴 taila->next = lb->next; tailb->next = la; } // p19 找出循环单链表的最小值的节点并删除 void printMinDel(PLNode &list) { PLNode pre = list; PLNode tmp = list->next; while (list->next != list) { pre = list; PLNode t2 = list; while (t2->next != list){ if (t2->next->data < pre->next->data) pre = t2; t2 = t2->next; } cout << pre->next->data << " "; PLNode del = pre->next; pre->next = del->next; free(del); } cout << endl; } int main() { srand(time(0)); PLNode list1 = NULL, list2 = NULL; createCycleLNode(list1, 2); createCycleLNode(list2, 5); addCycleLNode(list1, list2); printCycleLNode(list1); printMinDel(list1); return 0; } # 20. 第二十题 # ##### 题目简述 ##### 在结构体中加入freq，频率定义。 定义Locate(list，x)操作，把list中值为x的元素的freq++，并按照元素的freq属性，降序排序。 ##### 代码 ##### #include <iostream> #include <algorithm> #include <ctime> using namespace std; typedef int Elemtype; typedef struct dnode { Elemtype data; struct dnode *pre, *next; int freq; // 频率 }DNode, *PDNode; // 创建一个双向循环链表 void createDNode(PDNode &list, int len) { list = new DNode(); list->next = list; list->pre = list; PDNode tail = list; for (int i = 0; i < len; i++) { PDNode tmp = new DNode(); tmp->next = tail->next; tmp->pre = tail; tmp->data = rand() % 10; tmp->freq = 0; tmp->next->pre = tmp; tail->next = tmp; tail = tmp; } return; } // 从前打印双向链表 void printFrontToBack(PDNode list){ PDNode tmp = list->next; while (tmp != list) { cout << tmp->data << " "; tmp = tmp->next; } cout << endl; return; } // 从后往前打印双向链表 void printBackToFront(PDNode list) { PDNode tmp = list->pre; while (tmp != list) { cout << tmp->data << " "; tmp = tmp->pre; } cout << endl; return; } void Locate(PDNode &list, Elemtype x) { PDNode tmp = list->next; while (tmp != list) { if (tmp->data == x) { tmp->freq++; PDNode p = tmp; while (p->pre != list && p->freq >= p->pre->freq){ swap(p->data, p->pre->data); swap(p->freq, p->pre->freq); p = p->pre; } } tmp = tmp->next; } return; } int main() { srand(time(0)); PDNode list = NULL; createDNode(list, 20); printFrontToBack(list); while (true) { int n; cin >> n; Locate(list, n); printFrontToBack(list); } return 0; } # 21. 第二十一题 # ##### 题目简述 ##### 查找链表中的倒数第k个元素。 ##### 代码 ##### // p21 查找倒数第k个元素 ElemType findLastK(PLinkList list, int k) { ElemType res; int cnt = 0; PLinkList tp = list->next; PLinkList rp = tp; while (tp) { if (cnt < k) { cnt++; } else rp = rp->next; tp = tp->next; } if (cnt == k) return rp->data; cerr << "error!" << endl; return -1; } # 22. 第二十二题 # ##### 题目简述 ##### 找到链表中的公共节点，和前面的第八题类似。 ##### 代码 ##### #include <iostream> #include <algorithm> #include <string> using namespace std; typedef char Elemtype; typedef struct node{ Elemtype data; struct node *next; }StrList, *PStrList; int len(PStrList list){ int cnt = 0; PStrList tmp = list->next; while (tmp) { cnt++; tmp = tmp->next; } return cnt; } // 创造链表字符串 void createStrList(PStrList &list, string str) { list = new StrList(); list->next = NULL; PStrList tail = list; for (int i = 0; i < str.size(); i++) { PStrList p = new StrList(); p->next = tail->next; p->data = str[i]; tail->next = p; tail = p; } return; } // 输出链表字符串 void printStrList(PStrList list) { PStrList tmp = list->next; while (tmp){ cout << tmp->data; tmp = tmp->next; } cout << endl; return; } // p22 找到公共节点 PStrList findPublicNode(PStrList la, PStrList lb) { PStrList res = NULL; int lena = len(la), lenb = len(lb); if (lena < lenb) { swap(la, lb); swap(lena, lenb); } PStrList ta = la, tb = lb; for (int i = 0; i < lena - lenb; i++) ta = ta->next; while (ta->next){ if (ta->next == tb->next) return ta->next; ta = ta->next; tb = tb->next; } return res; } void mergeList(PStrList &la, PStrList &lb) { int lena = len(la), lenb = len(lb); PStrList ta = la, tb = lb, publicnodea = NULL, publicnodeb = NULL; if (lena > lenb) for (int i = 0; i < lena - lenb; i++) ta = ta->next; if (lenb > lena) for (int i = 0; i < lenb - lena; i++) tb = tb->next; while (ta->next){ if (ta->next->data != tb->next->data) { publicnodea = ta->next; publicnodeb = tb->next; } ta = ta->next; tb = tb->next; } publicnodea->next = publicnodeb->next; return; } int main() { PStrList list = NULL, list2 = NULL; createStrList(list, "zhuyunpeng"); createStrList(list2, "sunrongxiaopeng"); mergeList(list, list2); printStrList(list); printStrList(list2); PStrList publicnode = findPublicNode(list, list2); if (publicnode == NULL) cout << "未找到！" << endl; else cout << publicnode->data << endl; return 0; } # 23. 第二十三题 # ##### 题目简述 ##### 删除链表中的元素的绝对值重复的元素，要求|data| <= n。 ##### 代码 ##### // p23 删除重复元素，时间复杂度尽可能小, |data| <= n void repeatElemtype(PLinkList &list, int n) { int *cnt = new int[n + 1]; memset(cnt, 0, sizeof(int) * (n + 1)); PLinkList tmp = list; while (tmp->next) { int t = abs(tmp->next->data); if (!cnt[t]) cnt[t]++, tmp = tmp->next; else{ PLinkList del = tmp->next; tmp->next = del->next; free(del); } } }
还没有评论，来说两句吧...