数据结构

反转链表 原题链接：https://leetcode.cn/problems/reverse-linked-list/ 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 链表中节点的数目范围是 [0, 5000] -5000 <= Node.val <= 5000 1.利用外部空间主要思路：利用外部空间+STL算法 先申请一个动态扩容的数组或者容器，然后不断遍历链表，将链表中的元素添加到这个容器中。 再利用容器自身的 API，反转整个容器，这样就达到反转的效果了。 最后同时遍历容器和链表，将链表中的值改为容器中的值。 12345678910111213141516class Solution {public: int divide(int dividend, int divisor) { int flag = 0; int count = 0; if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) flag = 1; dividend = abs(dividend); divisor = abs(divisor); while (dividend - divisor >= 0) { dividend -= divisor; count++; } if (flag) count = -count; return count; }}; 2.双指针迭代3.优化的双指针4.递归

删除链表中所有值为x的元素 1.不带头结点（1）不带头结点递归删除 递归算法 删除不带头结点的单链表 L 中所有值为 x 的结点 12345678910111213141516171819202122232425262728#include "presetNoHead.h"//利用递归 删除指定元素void recursiveDelete(Node *&L, int x) { Node *p = L; if (L == NULL) return;//递归出口 if (L->data == x) { L = L->next;//L->next = L->next->next; free(p); recursiveDelete(L, x); } else { recursiveDelete(L->next, x);//L = L->next; }}int main() { int n; Node list; Node *L = &list; cout << "enter the length of this linklist : "; cin >> n; createLinkList(L, n); cout << "current linklist: " << endl; print(L); int x; cout << "enter the target : "; cin >> x; recursiveDelete(L, x); cout << "after the deletion : "; print(L); return 0;} （2）不带头结点非递归删除1234567891011121314151617181920212223242526272829303132333435363738394 ...

反向输出每个结点的值 L为不带头结点的单链表， 编写算法实现从尾到头 反向输出每个结点的值， 123456789101112131415161718192021#include "presetNoHead.h"void rPrint(Node *L) { if (L != NULL) { rPrint(L->next); cout << L->data << " "; } else { return; }}int main() { Node list; Node *L = &list; int n; cout << "enter the length of this linklist : "; cin >> n; createLinkList(L, n); cout << "current linklist: " << endl; print(L); cout << "Reverse order : "; rPrint(L); return 0;}

删除链表中的最小元素 L为带头结点的单链表 编写算法实现 删除一个最小值结点的高效算法 12345678910111213141516171819202122232425#include "presetHead.h"void minDelete(LinkList &L) { Node *p = L; Node *preMin = L;//指向最小值所存储的结点 的前一个结点 while (p->next != NULL) { if (p->next->data < preMin->next->data) { preMin = p; } p = p->next; } Node *q = preMin->next; preMin->next = q->next; free(q);}int main() { int n; cout << "enter the length of this linklist : "; cin >> n; LinkList L; createLinkList(L, n); cout << "current linklist: "; print(L); minDelete(L); cout << "after the deletion : "; print(L); return 0;}

链表原地翻转 带有头结点的单链表L 单链表就地逆置，要求辅助空间复杂度为O(1) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include <iostream>using namespace std;typedef struct Node { int data; struct Node *next;} Node, *LinkList;//头插法建立链表（有头结点）void createLinkList(LinkList &L, int n) { L = new Node; L->next = NULL; for (int i = 0; i < n; ++i) { Node *p = (Node *)malloc(sizeof(Node)); cin >> p->data; p->next = NULL; p->next = L->next; L->next = p; }}//链表数据打印void print(LinkList L) { Node *p = L->next; while (p != NULL) { //cout << p->data << ":" << p->next << " "; cout << p->data << " "; p = p->next; } cout << endl;}//利用头插法实现链表逆置void reverse(LinkList &L) { if (L == NULL) return; Node *p ...

链表插入排序

顺序表删除最小元素 从顺序表中删除具有最小值的元素（假设唯一），并由函数返回被删除元素的值。 删除后空出的位置由最后一个元素填补， 若顺序表为空则显示错误信息并退出运行。 preset.h12345678910111213141516171819202122232425#ifndef _PRESET_H#define _PRESET_H#include <iostream>using namespace std;#define MAXLENGTH 50typedef struct { int elem[MAXLENGTH]; int length;} SqList;void print(SqList sql) { if (sql.length == 0) { cout << "null" << endl; return; } for (int i = 0; i < sql.length; ++i) { cout << sql.elem[i] << " "; } cout << endl;}#endif 参考代码123456789101112131415161718192021222324252627282930313233343536#include "preset.h"//删除最小的元素bool listDelete(SqList &sql, int &e) { if (sql.length == 0) return false; int index = 0; int min = sql.elem[0]; for (int i = 1; i < sql.length; ++i) { if (sql.elem[i] < min) { min = sql.elem[i]; index = i; } ...

顺序表子表右移 2010 将n个整数存放到一维数组R中，设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0<p<n)个位置。 顺序序列中的元素 循环左移p个位置 将一维数组R中保存的序列 循环左移p个位置（要求在时间和空间两方面 都尽可能高效的算法） 即将R中的数据(X0, X1, X2… Xn-1)变换为(Xp, Xp+1, Xp+2…Xp-1) 12345678910111213141516171819202122232425262728293031323334#include "preset.h"//顺序序列中的元素 循环左移p个位置void listReverse(SqList &sql, int left, int right) { //int p = 0; //int q = sql.length - 1; while (left < right) { int temp = sql.elem[left]; sql.elem[left] = sql.elem[right]; sql.elem[right] = temp; left++; right--; }}//逆置前n个元素、逆置后m个元素void test(SqList &sql, int p) { cout << "Reverse all: " << endl; listReverse(sql, 0, sql.length - 1); print(sql); cout << "Reverse the first " << p << " elements:" << endl; listReverse(sql, 0, p - 1); print(sql); cout << "Reverse the last " << sql.length - p << " ...

有序顺序表合并求中位数 2011 寻找序列A和B的中位数 一个长度为L的升序序列S，处于第[L/2]个位置的数称为S序列的中位数。 现有两个等长的升序序列A和B，试设计一个在时间和空间复杂度都尽可能高效的算法，找出两个序列A和B的中位数，要求： 12345678910111213141516171819202122232425262728293031323334#include "preset.h"//顺序表合并（利用三个int类型指针i\j\k）bool merge(SqList a, SqList b, SqList &c) { if (c.length < a.length + b.length) return false; int i = 0, j = 0, k = 0; //逐个比较 将较小的插入顺序表c中 while (i < a.length && j < b.length) { if (a.elem[i] <= b.elem[j]) { c.elem[k] = a.elem[i]; i++; k++; } else { c.elem[k] = b.elem[j]; j++; k++; } } //剩余元素直接插入结果 while (i < a.length) { c.elem[k] = a.elem[i]; k++; i++; } while (j < b.length) { c.elem[k] = b.elem[j]; k++; j++; } //修改顺序表c的长度 c.length = a.length + b.length; return true;}int main() { SqList a = {{11, 13, 15, 17, 19}, 5}; print(a); SqList ...

寻找主元素 2013 已知一个整数序列A=(a0, a1,… an-1)其中0 ≤ ai ≤ n，若存在ap1=ap2= … =apm=x且 m > n/2则称x为A的主元素。 假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法找出A的主元素（存在输出该元素否则输出-1）。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include "preset.h"#include <map>//主元素抵消思路bool half(SqList sql, int &res) { int temp = sql.elem[0]; int count = 1; for (int i = 1; i < sql.length; ++i) { if (sql.elem[i] == temp) count++; else { if (count > 0) { count--; } else { temp = sql.elem[i]; count = 1; } } } int k = 0; for (int i = 0; i < sql.length; ++i) { if (sql.elem[i] == temp) ++k; } if (k > (sql.length / 2)) { res = temp; return true; } return false;}//哈希map思路bool hashmapp(SqList sql ...