/* 链表 */#include<iostream>using namespace std;//单链表结点类型描述typedef struct Lnode{ ElemType data; struct Lnode *next;}LNode, *LinkList;//双链表typedef struct DNode{ ElemType data; int freq; struct DNode *prior, *next;}DNode, *DLinkList;/* 1. 递归地删除不带头结点的单链表L中所有值为x的结点 */void Dele_X(LinkList &L, ElemType x){ LNode *p; if (L == NULL) return; if (L->data == x){ p = L; L = L->next; free(p); Dele_X(L, x); } else Dele_X(L->next, x);}/* 2. 删除带头结点的单链表L中所有值为x的结点 */void Dele_X(LinkList &L, ElemType x){ LNode *pre = L, *p = L->next, *q; while (p != NULL){ if (p->data == x){ q = p; p = p->next; pre->next = p->next; free(q); } else { pre = p; p = p->next; } }}/* 3. 反向输出单链表L结点的值 */void R_Print(LinkList L){ if (L->next != NULL) R_Print(L->next); if(L != NULL) printf("%d", L->data);}/* 4. 删除带头结点的单链表中的最小值（唯一） */void Dele_Min(LinkList &L){ LNode *pre = L, *p = L->next; //pre指向前驱结点， p为工作指针 LNode *minPre = pre, *minP = p; //最小结点前驱及最小结点 while (p != NULL){ if (p->data < minP->next){ minPre = pre; minP = p; } p = p->next; pre = p; } minPre->next = minP->next; free(minP);}/* 5. 将带头结点的单链表就地逆置 */void Reverse(LinkList &L){ //采用头插法逆置 LNode *p = L->next, *r; L->next = NULL; while(p != NULL){ r = p->next; p->next = L->next; L->next = p; p = r; }}/* 6. 带头结点的单链表，使其元素递增有序 */void Sort(LinkList &L){ LNode *p = L->next, *pre; Lnode *r = p->next; p->next = NULL; p = r; while(p != NULL){ r = p->next; pre = L; while(pre->next != NULL && pre->next->data < p->data) pre = pre->next; p->next = pre->next; pre->next = p; p = r; }}/* 7. 删除无序带头结点的单链表中在给定区间的元素 */void RangeDelete(LinkList &L, int min, int max){ LNode *pre = L, *p = L->next; while(p != NULL){ if (p->data >= min && p->data <= max){ pre->next = p->next; p = p->next; free(p); } else{ pre = p; p = p->next; } }}/* 8. 给定两个单链表，找出这两个结点的公共结点 */LinkList Search_1st_Common(LinkList L1, LinkList L2){ int len1 = Length(L1), len2 = Length(L2), dis; LinkList longList, shortList; if (len1 < len2){ longList = L2; shortList = L1; dis = len2 - len1; } else{ longList = L1; shortList = L2; dis = len1 - len2; } while(dis--) longList = longList->next; while(longList != NULL){ if(shortList == longList) return longList; else{ longList = longList->next; shortList = shortList->next; } } return NULL;}/* 9. 按递增次数输出带头结点单链表，并释放结点所占空间（不允许用数组做辅助空间） */void Min_Dele(LinkList &head){ LNode *pre, *p, *u; while(head->next != NULL){ pre = head; p = pre->next; while(p != NULL){ if (p->next->data < pre->next->data) pre = p; p = p->next; } printf(pre->next->data); u = pre->next; pre->next = u->next; free(u); } free(head);}/* 10. 将带头结点的单链表A分解为两个带头结点的单链表A和B，使得A中为奇数序号的元素，B为偶数序号元素 */LinkList DisCreat(LinkList A){ int i = 0; LNode *B, *ra = A, *rb = B, *p; //ra和rb指向A，B的尾节点 B->next = NULL; p = A->next; A->next = NULL; while(p != NULL){ i ; if (i % 2 == 0){ rb->next = p; rb = p; } else{ ra->next = p; ra = p; } p = p->next; } ra->next = rb->next = NULL; return B;}/* 11. 在10题的基础上将B逆置，即B采用头插法 */LinkList DisCreat(LinkList A){ LNode *B, *ra = A, *p, *q; //ra和rb指向A，B的尾节点 B->next = NULL; p = A->next; A->next = NULL; while(p != NULL){ ra->next = p; ra = p; p = p->next; if (p != NULL) q = p->next; p->next = B->next; B->next = p; p = q; } ra->next = NULL; return B;}/* 12. 去掉递增有序单链表中重复值的元素 */void Dele_Same(LinkList &L){ LNode *p = L->next, *q; if (p == NULL) return; while(p->next != NULL){ q = p->next; if (p->data == q->data){ p->next = q->next; free(q); } else p = p->next; }}/* 13. 将两个递增单链表合成一个递减单链表 */void Merge(LinkList &L1, LinkList &L2){ LNode *r, *p1 = L1->next, *p2 = L2->next; L1->next = NULL; while (p1 && p2){ if (p1->data <= p2->data){ r = p1->next; p1->next = L1->next; L1->next = p1; p1 = r; } else{ r = p2->next; p2->next = L2->next; L2->next = p2; p2 = r; } } if (p1) p2 = p1; while(p2){ r = p2->next; p2->next = L1->next; L1->next = p2; p2 = r; } free(L2);}/* 14. 从两个递增单链表中的公共元素产生单链表C */LinkList Get_Common(LinkList A, LinkList B){ LNode *p = A->next, *q = B->next, *r, *s; LinkList C = (LinkList)malloc(sizeof(LNode)); r = C; while(p && q){ if (p->data < q->data) p = p->next else if(p->data > q->data) q = q->next; else{ s = (LNode*)malloc(sizeof(LNode)); s->data = p->data; r->next = s; r = s; p = p->next; q = q->next; } } r->next = NULL; return C;}/* 15. 两个单链表A和B递增，求交集放于A中 */LinkList Union(LinkList A, LinkList B){ LNode *pa, *pb, *pc, *u; pa = A->next; pb = B->next; pc = A; while(pa && pb){ if (pa->data == pb->data){ pc->next = pa; pc = pa; pa = pa->next; pb = pb->next; free(u); } else if(pa->data < pb->data){ u = pa; pa = pa->data; free(u); } else{ u = pb; pb = pb->next; free(pb); } while(pa){ u = pa; pa = pa->next; free(u); } while(pb){ u = pb; pb = pb->next; free(pb); } } pc->next = NULL; free(B); return A;}/* 16. 两个单链表A和B， 判断B是否为A 的连续子序列 */bool Pattern(LinkList A, LinkList B){ LNode *p = A, *pre = p, *q = B; while(p && q){ if (p->data == q->data){ p = p->next; q = q->next; } else{ pre = pre->next; p = pre; q = B; } } if (!q) return true; else return false;}/* 17. 判断带头结点的循环双链表是否对称 */bool symmetry(DLinkList L){ DNode *p = L->next, *q = L->prior; while(p != q && q->next !=p){ if (p->data == q->data){ p = p->next; q = q->prior; } else return false; } return true;}/* 18. 两个循环单链表A和B，将B连接到A之后，仍保持循环链表形式 */LinkList Link(LinkList A, LinkList B){ LNode *p, *q; p = A; while(p->next != A) p = p->next; q = B; while (q->next !=B) q = q->next; p->next = B; q->next = A; return A;}/* 19. 重复找到带头结点的循环单链表中的最小值输出并删除，直至单链表为空再删除头结点 */void Dele_Min(LinkList &L){ LNode *p, *pre, *minp, *minpre; while(L->next != NULL){ p = L->next; pre = L; minp = p; minpre = pre; while (p != L){ if (p->data < minp->data){ minp = p; minpre = pre; } pre = p; p = p->next; } printf("%d", *minp); minpre->next = minp->next; free(minp); } free(L);}/* 20. 对带头指针L带头结点的非循环双向链表，freq访问频度域（初值为0，每调用Locate（L,x）一次就加1）， 同时链表按freq递减排序，最近访问结点排在相同频度之前 */DLinkList Locate(DLinkList L, int x){ DNode *p = L->next, *q; //q为p的前驱 while(p && p->data != x) p = p->next; if (!p){ printf("不存在值为x的结点\n"); exit(0); } else{ p->freq ; if (p->next != NULL) p->next->prior = p->prior; p->prior->next = p->next; q = p->prior; while(q != L && q->freq <= p->freq) q = q->prior; p->next = q->next; q->next->prior = p; p->prior = q; q->next = p; } return p;}/* 21. 带头指针的单链表，查找链表中倒数第k个位置的结点，若查找成功，输出date域的值，并返回1， 否则只返回0*//* 设计思想：两个指针片p，q。p先移动k个位置后同步移动p，q */int Search(LinkList list, int k){ LNode *p = list->next, *q = list->next; int count = 0; while(p){ if (count < k) count ; else q = q->next; p = p->next; } if (count < k) return 0; else{ printf("%d", q->data); return 1; }}/* 22. 带头结点的单链表存储单词，当两个单词有相同后缀是，可共享相同后缀的存储空间。设str1和str2分别指向 两个单词所在单链表的头结点 ，找出str1 和 str2所指向两个链表公共后缀的起始位置*//* 设计思想：1.求出两表长度分别为m,n 2.让长的那个先走|m-n| 1个节点 3.之后同时移动两个指针，当两个指针同时指向同一地址时结束 */int Length(LinkList L){ int count = 0; LNode *p = L->next; while (p){ count ; p = p->next; } return count;}LNode* Find_Addr(LinkList str1, LinkList str2){ int m, n, count = 0;; LNode *p = str1->next, *q = str2->next; m = Length(str1); n = Length(str2); if (m > n) for (int i = 0; i < m-n 1; i ) str1 = str1->next; else for (int i = 0; i < n-m 1; j ) str2 = str2->next; while (str1 != str2){ p = p->next; q = q->next; } return p->next;} /* 时间复杂度O(len1 len2) *//* 23. 带头结点的单链表保存m个整数，删除绝对值相同的结点，仅保留第一次出现的结点 *//* 设计思想：空间换时间，设置辅助数组来保存第一次出现的数 */void Delete(LinkList &L, int n){ LNode *p = L, *r; int *a; a = (int *)malloc(sizeof(int)*(n 1)); memset(a, 0, sizeof(a)); while(p->next != NULL){ int m = abs(p->next->data); if (*(a m) == 0){ *(a m) = 1; p = p->next; } else{ r = p->next; p->next = r->next; free(r); } } free(a);}/* 时间复杂度O(m), 空间复杂度O(n) *//* 24. 判断一个链表是否有环，如果有，找出环的入口并返回，否则返回NULL */LNode* FindLoopStart(LNode *head){ LNode *fast = head, *slow = head; while (slow != NULL && fast->next !=NULL){ slow = slow->next; fast = fast->next->next; if (slow == fast) break; } if (slow == NULL || fast->next == NULL) return NULL; LNode *p1 = head, *p2 = slow; while(p1 != p2){ p1 = p1->next; p2 = p2->next; } return p1;}/* 25. 带头结点的单链表中{A1, A2, ..., An}，重新排列结点使其成为{A1, An, A2, An-1,...}, 要求空间复杂度为O(1) *//* 设计思想：1. 后半段原地逆置，设指针p和q，p每次走一步，q每次走两步,当q到结尾时，p指向中间节点 2.依次从前后两段各取一个结点按要求重排 */void Change_List(LNode *h){ LNode *p, *q, *r, *s; p = q = h; while(q->next != NULL){ p = p->next; q = q->next; if (q->next != NULL) q = q->next; } 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; q->next = s->next; s->next = q; s = q->next; q = r; }}来源：https://www.icode9.com/content-4-726801.html
联系客服
