.数组
1.1.将一个数组前后翻转
bool Delete_Min(int A[], n, &min) { if (!n) return false; //数组长度为0，返回false int temp = INT_MAX, m; //INT_MAX为int类型的最大值 for (int i = 0; i < n; i++) { //遍历数组，找到数组当前的最小元素 if (A[i] < temp) { temp = A[i]; //更新数组最小值 m = i; //记录数组下标 } } min = temp; //min保存最小值 A[m] = A[n - 1]; //m用数组中最后一个元素替换 return true; }
1.2.删除数组中值为x的元素
int DeleteX(int A[], x, n){ int i = 0, j = 0; for (i = 0; i < n; i++) { if (A[i] != x) { //当前元素的值不为x A[j] = A[i]; //将其保存到数组下标为j的元素中 j++; } } n = j; return n; //返回删除x后的数组元素个数 }
1.3.将两个有序数组合并成一个有序数组
int* Merge(int A[], B[], lenA, lenB) { int *C = (int*)malloc((lenA + lenB) * sizeof(int)); int a = 0, b = 0, c = 0; for (c = 0; a < lenA && b < lenB; c++) { //选择两个数组中的较小值放入数组C中 if (A[a] <= B[b]) C[c] = A[a++]; else C[c] = B[b++]; } while (a < lenA) C[c++] = A[a++]; //将剩余数组放入C中 while (b < lenB) C[c++] = B[b++]; return C; }
1.4.真题
void ans(int A[], n, p){ int B[n], i, j; for (i = 0, j = p; j < n; i++, j++) B[i] = A[j]; //数组后部分前移 for (j = 0; j < p; i++, j++) B[i] = A[j]; //数组前部分后移 for (i = 0; i < n; i++) cout << B[i]; //输出循环前移后的数组 }
int res(int A[], int B[], int n){ int i, j, k, mid; for (i = 0, j = 0, k = 0; k < n; k++){ if (A[i] <= B[j]) { //当前A数组的元素小，保存A[i] mid = A[i]; i++; } else { //当前B数组的元素小，保存B[j] mid = B[j]; j++; } } return mid; }
void Qsort(int A[], L, R){ if (L >= R) return; //当前数组区间<= 1，返回 随机选择数组中一个元素和A[L]交换 //快速排序优化，使得基准元素的选取随机 int key = A[L], i = L, j = R; //选择A[L]作为基准元素，i和j分别为左右指针 while(i < j) { while (i < j && key < A[j]) j--; while (i < j && A[i] <= key) i++; if (i < j) swap(A[i], A[j]); //交换A[i]和A[j] } swap(A[i], A[L]); Qsort(A, L, i - 1); //递归排序左区间 Qsort(A, i + 1, R); //递归排序右区间 } int ans(int A[], int B[], int n) { int C[2n], i, j; for (i = 0; i < n; i++) C[i] = A[i]; //复制数组A和数组B的元素 for (j = 0; j < n; i++, j++) C[i] = B[j]; Qsort(C, 0, 2n - 1); //对数组C进行快速排序 return C[n - 1]; //返回中位数 }
int ans(int A[], n){ int count[n]; for (int i = 0; i < n; i++) count[i] = 0; //初始化count数组 //遍历A数组，其元素的值作为count数组下标的元素+1，表示该元素在A数组中出现次数 for (int i = 0; i < n; i++) count[A[i]]++; for (int i = 0; i < n; i++) { //当前元素出现次数符合主元素定义 if (count[i] > n / 2) return i; //返回i，即该元素的值 } return -1; //没有元素符合主元素定义 }
int ans(int A[], n) { bool B[n + 2]; //B用来标记数组中出现的正整数 for (int i = 0; i < n; i++) B[i] = false; //初始化B数组 for (int i = 0; i < n; i++) { if (A[i] > 0) B[A[i]] = true; //该元素大于0，则在B数组中标记为已经出现 } for (int i = 1; i < n; i++) { if (B[i] == false) return i; //返回数组B中第一个false的元素下标 } }
void Qsort(int A[], L, R) { if (L >= R) return; //数组区间<= 1，返回 随机选择数组中一元素和A[L]交换;//快排优化，使得基准元素的选取随机 int key = A[L], i = L, j = R; //A[L]为基准元素，ij为左右指针 while (i < j) { while (i < j && key < A[j]) j--; while (i < j && A[i] <= key) i++; if (i < j) Swap(A[i], A[j]); //交换A[i]和A[j] } Swap(A[L], A[i]); Qsort(A, L, i - 1); //递归排序左区间 Qsort(A, i + 1, R); //递归排序右区间 } int ans(int A[], n) { Qsort(A, 0, n - 1); //快速排序 int i = 0; while (A[i] <= 0) i++; //找到数组中第一个大于0的元素 if (n == i) return 1; //数组中没有元素大于0，返回1 else { if (A[i] != 1) return 1; //第一个整数不是1，则返回1 else { //第一个整数为1，找到数组中正整数第一个间断点 int j = i + 1; while (j < n) { if (a[j] == a[j - 1]) j++; //相邻元素相等 else if (a[j] == a[j - 1] + 1) j++; //相邻元素是连续数 else return A[j - 1] + 1; //相邻元素是间断点 }//while }//else }//else }
int Dis(int a, b, c){ int res = abs(a - b) + abs(a - c) + abs(b - c); //计算绝对值 return res; } int Ans(int A[], int B[], int C[], int n1, int n2, int n3){ int min = INT_MAX, i, j, k, temp; //min取整型的最大值 for (int i = 0; i < n1; i++) { //循环遍历数组A for (int j = 0; j < n2; j++) { //循环遍历数组B for (int k = 0; k < n3; k++) { //循环遍历数组C temp = Dis(A[i], B[j], C[k]); if (temp < min) min = temp; //当前元素之间的距离更小，更新最小距离 }//for }//for }//for return min; //返回最小距离 }
2.链表
2.1.链表的数据结构定义
2.1.1.单链表
2.1.1.单链表
typedef struct LNode { struct LNode *next; int data; }LNode, *LinkList;
2.1.2.双链表
typedef struct LNode { struct LNode *prior, *next; int data; }LNode, *LinkList;
2.2.链表的操作
2.2.1.头插法（插入到链表头）
void HeadInsert(LinkList &L, int key) { LNode *p = (LNode*)malloc(sizeof(LNode)); p->data = key; p->next = L->next; L->next = q; }
2.2.2.尾插法（插入到链表尾）
void TailInsert(LinkList &L, int key) { LNode *q = (LNode*)malloc(sizeof(LNode); q->data = key; q->next = NULL; LNode *p = L->next, *pre = L; while (!p) { pre = p; p = p->next; } pre->next = q; }
2.2.3.链表逆置（头插法实现）
void Reverse(LinkList &L) { LNode *p = L->next, *q = NULL; L->next = NULL; //将L表断开 while (!p) { q = p->next; //q指向p的下一个结点 p->next = L->next; //头插法 L->next = p; p = q; } }
2.2.4.链表的遍历
LNode *p = L->next; while (!p) { visit(p); p = p->next; }
2.2.5.链表的删除
void Delete(LinkList &L, int &key) { LNode *p = L->next, *pre = L; 移动p和pre到指定结点 //pre指向p的前驱结点 key = p->data; //key保存p的data领 pre->next = p->next; //pre的next指针指向p的后继节点 free(p); }
2.3.链表算法题
2.3.1.删除值为x的结点
1.void DeleteX(LinkList &L, int x){ LNode *p = L->next, *pre = L; while (p) { if (p->data == x) { //当前元素值为x pre->next = p->next; free(p); p = pre->next; } else { //当前元素值非x，p和pre向后移动 p = p->next; pre = pre->next; } } }
2.3.2.单链表就地逆置
void reverse(LinkList &L){ LNode *p = L->next, *q; L->next = NULL; //断链 while (p) { q = p->next; //q指向p的下一个结点 p->next = L->next; //头插法 L->next = p; p = q; } }
2.3.3.将链表排序
LNode *Sort(LinkList L) { LNode* p = (LNode*)malloc(sizeof(Lnode)); p->next = NULL; LNode* t = L->next, * tpre = L, *min, *minpre, *r = p; int m = INT_MAX; while (t) { while (t) { //遍历链表 if (t->data < m) { //更新最小值结点 min = t; minpre = tpre; m = t->data; }//if tpre = t; t = t->next; }//while minpre->next = min->next; //将min从L中删除 r->next = min; //将min插入p r = min; //r后移 m = INT_MAX; //重新初始化 t = L->next; tpre = L; }//while r->next = NULL; return p; }
2.3.4.拆分链表
LNode* (LinkList &L) { LNode *p = (LNode*)malloc(sizeof(LNode); p->next = NULL; //p为新链的头结点 LNode *q = L->next, *t = NULL, *r = L; r->next = NULL; //r结点始终指向L的最后一个结点 while (q) { t = q->next; r->next = q; //奇数结点尾插法 r = q; q = t; t = q->next; q->next = p->next; //偶数节点头插法 p->next = q; q = t; } r->next = NULL; //将r的next指针置空 return p; }
