赞
踩
int search(int a[], int n, int k) {
for (int i = 1; i <= n; i++) {
if (a[i] == k) {
return i;
}
}
return 0;
}
非递归版本
int BinarySearch(SqList L, int key) { int low = 0, high = L.length - 1; int mid; while (low <= high) { mid = (low + high) / 2; if (L.data[mid] == key) { return mid; } //变换low和high else if (L.data[mid] > key) {//在左边 high = mid - 1; } else { low = mid + 1; } } return -1; }
递归版本
int BinarySearch(SqList L, int key, int low, int high) { int mid = (low + high) / 2; if (low > high) {//递归边界 return -1; } if (L.data[mid] == key) { return mid; } else if (L.data[mid] > key) { high = mid - 1; //BinarySearch(L, key, low, high);需要return回来,不然程序不会实现递归功能 return BinarySearch(L, key, low, high); } else { low = mid + 1; return BinarySearch(L, key, low, high); } }
顺序结构
void exchange(SqList& L, int k) {
if (L.data[0] == k) {
return;
}
int temp;
for (int i = 1; i < L.length; i++) {
if (L.data[i] == k) {
temp = L.data[i - 1];
L.data[i - 1] = L.data[i];
L.data[i] = temp;
return;
}
}
}
顺序表可以直接定义一个temp变量进行交换
链式结构
void LinkListSearch(LinkList& L, int k) {//带头结点的单链表 L
if (L->next->data == k)//第一个数据结点无前驱结点,若其为查找结点则返回
return;
LNode* p = L;//定义遍历指针 p
while (p->next->next) {//若 p->next->next 所指的结点不为空则继续循环
if (p->next->next->data == k) {//p->next->next 所指结点为查找结点则交换
LNode* q = p->next, * r = q->next;//定义两个指针辅助进行交换
q->next = r->next;//交换所找结点与其前驱结点位置
p->next = r;
r->next = q;
return;
}
p = p->next;//若此时 p->next->next 所指结点不是查找结点则继续遍历
}
}
这里是p指针指向头结点,判断其后一个的后一个结点是否等于k
void exchange(LinkList& L, int k) {//这里是带头结点的单链表 if (L->next->data == k) {//第一个数据结点无前驱结点,若其为查找结点则返回 return; } LNode* pre = L; LNode* p = pre->next; while (p->next != NULL) { if (p->next->data == k) { LNode* q = p->next; p->next = q->next; q->next = p; pre->next = q; return; } pre = p;//继续后移查找 p = pre->next; } }
这是笔者自己写的,定义pre指向头结点,p指向pre的后一个结点
非递归
//非递归
BiTNode* BST_search(BiTree T, int k) {
while (T != NULL) {
if (T->data == k) {
return T;
}
else if (T->data > k) {//去左子树查找
T = T->lchild;
}
else {//去右子树找
T = T->rchild;
}
}
return NULL;
}
递归
BiTNode* BST_search(BiTree T, int k) {
if (T == NULL) {
return NULL;
}
if (T->data == k) {
return T;
}
else if (k < T->data) {//查找的值小于根节点的值,说明在左子树
return BST_search(T->lchild, k);
}
else {
return BST_search(T->rchild, k);
}
}
这里递归调用时候别忘了写return
非递归插入结点
//非递归插入结点 int BST_insert(BiTree& T, int k) { if (T == NULL) { BiTNode* p = (BiTNode*)malloc(sizeof(BiTNode)); p->data = k; p->lchild = NULL; p->rchild = NULL; T = p; return 1; } while (T != NULL) { if (T->data == k) { return 0; } else if (k < T->data) {//左子树去插入 if (T->lchild == NULL) {//如果左子树没有结点,说明找到插入位置了 BiTNode* p = (BiTNode*)malloc(sizeof(BiTNode)); p->data = k; p->lchild = NULL; p->rchild = NULL; T->lchild = p; return 1; } else {//如果左子树有结点,继续遍历左子树 T = T->lchild; } } else {//去右子树插入k if (T->rchild == NULL) { BiTNode* p = (BiTNode*)malloc(sizeof(BiTNode)); p->data = k; p->lchild = NULL; p->rchild = NULL; T->rchild = p; return 1; } else { T = T->rchild; } } } }
递归插入结点
//递归插入结点 int BST_insert(BiTree& T, int k) { if (T == NULL) {//找到插入位置了 T = (BiTNode*)malloc(sizeof(BiTNode)); T->data = k; T->lchild = NULL; T->rchild = NULL; return 1; } if (T->data == k) { return 0; } else if (k < T->data) { return BST_insert(T->lchild, k); } else { return BST_insert(T->rchild, k); } }
构造二叉排序树
void Create_BST(BiTree& T, int A[], int n) {
T = NULL;//第一次调用 BST_Insert 函数前需将 T 初始化为空才可正常调用
int i = 0;//定义遍历索引 i
while (i < n) {//遍历数组 A
BST_insert(T, A[i]);//对数组 A 中每个元素进行二叉排序树的插入操作
i++;
}
}
int Min(BiTree T) {
while (T -> lchild != NULL) {
T = T->lchild;
}
return T->data;
}
int Max(BiTree T) {
while (T->rchild != NULL) {
T = T->rchild;
}
return T->data;
}
int depth(BiTree T, BiTNode*p) {
int n = 1;定义变量 n 用来记录 T 指针指向结点所在层次
while (p != T) {
if (p->data > T->data) {
T = T->rchild;
}
else {
T = T->lchild;
}
n++;//返回查找结点所在层次
}
return n;
}
void print_k(BiTree T, int k) {
if (T != NULL) {
print_k(T->rchild, k);
if (T->data >= k) {
printf("%d", T->data);
}
print_k(T->lchild, k);
}
}
if (T->data >= k) 不是T->rchild>=k,是因为这个if是在处理根了,中序遍历,中间的代码是处理根结点的;
对递归不太了解的,也可以用下面的,逻辑更清楚一些
void print_k(BiTree T, int k) {
if (T == NULL) {
return;
}
else{
print_k(T->rchild, k);
if (T->data >= k) {
printf("%d", T->data);
}
print_k(T->lchild, k);
}
}
代码的写法与之前写的不太相同,需要好好理解理解
int pre = -32767;//int变量的最小值,将其作为前驱, int Is_BST(BiTree T,int &pre) { int b1, b2;//用于记录左右子树是否为二叉排序树,是则返回 1,不是则返回 0 if (T == NULL) { return 1;//空树是二叉排序树 } else { b1 = Is_BST(T->lchild, pre);//用b1接收左子树情况 if (b1 == 0 || T->data <= pre) { return 0;//若左子树返回 0 或根结点小于等于左子树最大结点则不是 } pre = T->data;//递归判断右子树是否为二叉排序树 b2 = Is_BST(T->rchild, pre);//返回右子树判断结果 return b2; } }
这里T==NULL return 1在叶子结点的左右孩子那都会返回1,导致叶子结点以下只需要看pre和根结点的大小,
这里结尾是return b2
int hight(BiTree T) { int left, right; if (T == NULL) {//空树高度为0 return 0; } left = hight(T->lchild); right = hight(T->rchild); if (left == -1 || right == -1 || abs(left - right) > 1) {左子树或右子树不是 AVL 或左右子树高度差大于 1 则返回-1,说明不是平衡二叉树 return -1; } else {//是平衡二叉树 return max(left, right) + 1; } } int judgeAVL(BiTree T) { if (hight(T) == -1) { return 0; } else { return 1; } }
这里hight函数用来求平衡二叉树的高度,但是经过改写,即如果左子树或右子树不是平衡二叉树,返回-1,左右子树高度差大于 1(不是平衡二叉树)也返回-1,如果是平衡二叉树,需要返回包括根结点在内的左右子树的最大高度,后序递归需要继续比较。
int abs(int a) {//求绝对值,用于计算平衡因子 if (a >= 0) { return a; } else { return -a; } } int max(int x,int y) {//求两数之中最大值 if (x >= y) { return x; } else { return y; } }
BiTNode* Search_k(BiTree T, int k) {
if (k < 1 || T == NULL) {
return NULL;
}
else if (T->lsize == k) {
return T;
}
else if (T->lsize > k) {//往左子树找
return Search_k(T->lchild, k);
}
else {
return Search_k(T->rchild, k - T->lsize);
}
}
BiTNode* Search(BiTree T, int k) { if (k<1 || k>T->count) { return NULL; } if (T->lchild == NULL) {//没有左子树 if (k == 1) { return T; } else {//不是第一个结点,说明去右子树找,需要递归 return Search(T->rchild, k - 1);//若不是第一小,则递归的去右子树中找第 k-1 小的结点 } } else{//有左子树 if (T->lchild->count == k - 1) {//若左子树有 k-1 个结点,则根为第 k 小结点 return T; } else if (T->lchild->count > k - 1) {//在左子树去查找 return Search(T->lchild, k); } else { return Search(T->rchild, k - (T->lchild->count + 1));//T->lchild->count + 1表示左子树+根结点数量 } } }
下面是自己写错的,没有考虑没有左子树的情况;
BiTNode* Search(BiTree T, int k) {
if (k<1 || k>T->count) {
return NULL;
}
if (T->lchild->count == k - 1) {
return T;
}
else if (T->lchild->count > k - 1) {//在左子树去查找
return Search(T->lchild, k);
}
else {
return Search(T->rchild, k - (T->lchild->count + 1));
}
}
直接插入排序将要排序的元素划分为两部分,一部分是排好序的部分,另一部分是待排序的部分,然后从待排序部分中依次原则元素与排好序元素进行比较,找到插入位置进行插入,然后去处理下一个,直到全部元素均处理完,
顺序存储
void InsertSort(int A[], int n) {//数组从下标 1 开始存储数据 if (n == 1) { return;} int i, j; for (i = 2; i <= n; i++) { if (A[i] >= A[i - 1]); else {//后一个元素要比前一个元素小,需要寻找插入位置 A[0] = A[i];//将待排序元素复制到 A[0] j = i; while (A[0] < A[j - 1]) {//while循环寻找待排序元素插入位置 A[j] = A[j - 1];//元素后移,为待排序元素插入做准备 j--; } A[j] = A[0];//找到插入位置后,将待排序元素插入 } } } void InsertSort(int A[], int n) {//数组从下标 1 开始存储数据 int i, j; for (i = 2; i <= n; i++) {//遍历数组 if (A[i] < A[i - 1]) {//若遍历元素小于前一个元素则需寻找其插入位置 A[0] = A[i];//将待排序元素复制到 A[0] for (j = i - 1; A[0] < A[j]; j--)//寻找待排序元素插入位置 A[j + 1] = A[j];//元素后移,为待排序元素插入做准备 A[j + 1] = A[0];//找到插入位置后,将待排序元素插入 } } }
下面是笔者第一次写的代码,感觉怪怪的,而且代码运行会有错误,就是因为没有使用A[0]和A[j-1]比较。
void InsertSort(int A[], int n) {//数组从下标 1 开始存储数据 if (n == 1) { return;} int i, j; for (i = 2; i <= n; i++) { if (A[i] >= A[i - 1]); else { A[0] = A[i]; j = i; while (A[j] < A[j - 1]) { A[j] = A[j - 1]; j--; } A[j] = A[0]; } } }
链式存储
//链式存储 void InsertSort(LinkList& L) { if (L->next == NULL) {//若链表为空则直接结束 return; } LNode* pre, * q, * p, * r;//定义 pre 和 q 遍历已排序结点,p 和 r 遍历待排序结点 p = L->next->next;//让 p 指针指向第二个数据结点,即待排序的第一个结点 L->next->next = NULL;//断开链表,使 L 变成只有一个结点的有序链表 while (p != NULL) {//遍历待排序结点 pre = L;//初始化 pre 和 q 两个指针 q = pre->next; while (q != NULL && q->data < p->data) {//寻找待排序结点插入位置,如果q结点指针域不为空,且其值小于待排序第一个结点的值,说明需要继续找插入位置 pre = q; q = q->next; } //跳出循环后,说明q为空了或者左边的值大于等于右边的值,可以插入了,在pre和q之间进行插入 r = p->next;//记录下一个待排序结点位置,放置断链 p->next = q;//将 p 指针指向的待排序结点插入到有序链表中 pre->next = p; p = r;//更新 p 指针位置,使其指向下一个待排序结点 } }
void InsertSort(int A[], int m, int n) {//运用直接插入排序
int i, j;
for (i = m + 1; i <= m + n; i++) {//变量 i 负责遍历待排序元素
if (A[i] < A[i - 1]) {//若遍历元素小于前一个元素则需寻找其插入位置
A[0] = A[i];//将此遍历元素复制到 A[0]
for (j = i - 1; A[0] < A[j]; j--){//寻找遍历元素插入位置
A[j + 1] = A[j];//元素后移,为遍历元素插入做准备
}
A[j + 1] = A[0];//找到插入位置后,将待排序元素插入
}
}
}
void InsertSort(int A[], int n) {//数组中元素从下标 1 开始存储 int i, j, low, high, mid; for (i = 2; i <= n; i++) { //先将元素放在A[0]中,防止后序丢失 A[0] = A[i]; low = 1;//low 索引记录已排序的第一个元素位置 high = i - 1;//high 索引记录已排序的最后一个元素位置 while (low <= high) { mid = (low + high) / 2;//mid会根据high的变化而变化,因此需要放在循环里面 if (A[mid] < A[0]) {//如果要插入元素比中间元素大,要去右边 low = mid + 1; } else { high = mid - 1; } } //low>high说明找到要插入位置了,为low指向的位置,因此需要给他腾出空间插入 //这里j的位置可以自己推一下 for (j = i - 1; j >= low; j--) { A[j + 1] = A[j]; } //在low的位置插入元素 A[low] = A[0]; } }
void ShellSort(int A[], int n) {//数组中元素从下标 1 开始存储
int d, i, j;//定义变量 d 记录增量
for (d = n / 2; d >= 1; d = d / 2)//初始时增量为 n/2,之后每次增量更新为上一趟的一半
for (i = 1 + d; i <= n; i++)//遍历各个子表,下一个元素是d+1,如1,1+d,1+2d;2,2+d,2+2d
if (A[i] < A[i - d]) {//若此子表待排序元素小于上一个元素则需插入排序
A[0] = A[i];//将待排序元素复制到 A[0]
for (j = i - d; j > 0 && A[0] < A[j]; j = j - d)//寻找待排序元素插入位置
A[j + d] = A[j];//比待排序元素大的元素后移
A[j + d] = A[0];//插入待排序元素
}
}
void BubbleSort(int A[], int n) {//数组中元素从下标 0 开始存储 int i, j, temp; int flag;//定义 flag 用来记录每次冒泡过程中有无元素交换 for (i = 0; i < n - 1; i++) {//n 个元素进行冒泡排序最多进行 n-1 次冒泡,或者说每一次循环确定A[i]的元素,假如5个元素,A0-A4,所以i<n-1; flag = 0;//初始化 flag 标志 for (j = n - 1; j > i; j--) {//遍历待排序的元素进行冒泡,假如i=0时,j=4,3,2,1,需要进行4次j的变化,最后j为1,所以判断条件为j if (A[j - 1] > A[j]) {//若两元素出现逆序则需交换 temp = A[j]; A[j] = A[j - 1]; A[j - 1] = temp; flag = 1;//执行交换操作后需将 flag 标志置为 1 } } if (flag == 0)//若某一次冒泡过程中无交换,则证明已经有序直接结束 return; } }
void BubbleSort(int A[], int n) { int low = 0, high = n - 1;//定义两个索引分别记录待排序元素的低地址和高地址 int temp, flag = 1;//定义 flag 变量记录冒泡排序过程中有无元素交换,将flag设置为1,是为了进入while循环 while (low < high&& flag == 1) { flag = 0;//初始时让 flag 等于 0 代表目前还没有元素交换 for (int i = low; i < high; i++) {//从前往后冒泡 if (A[i] > A[i + 1]) {//若出现逆序则交换两个元素 temp = A[i]; A[i] = A[i + 1]; A[i + 1] = temp; flag = 1;//执行完交换操作后将 flag 变量改为 1 } } high--;//更新待排序元素的高地址 for (int i = high; i > low; i--) {//从后往前冒泡 if (A[i] < A[i - 1]) {//若出现逆序则交换两个元素 temp = A[i]; A[i] = A[i - 1]; A[i - 1] = temp; flag = 1;//执行完交换操作后将 flag 变量改为 1 } } low++;//更新待排序元素的低地址 } }
//划分函数,返回基准(已确定元素)的下标 int Partition(int A[], int low, int high) { int pivot = A[low];//定义一个基准,初始时赋值为 low 位置的元素 while (low < high) {//low 小于 high 才有意义 while (low < high && A[high] >= pivot) {//右边的大于或者等于基准,右边high左移 high--;//从右往左遍历寻找小于基准的元素 } //跳出while循环,说明找到小于基准的元素,则互换将其放到左边 A[low] = A[high]; while (low < high && A[low] <= pivot) {//左边的小于于或者等于基准,左边low左移 low++;//若左往右遍历寻找大于基准的元素 } //跳出while循环,说明找到大于基准的元素,则互换将其放到右边 A[high] = A[low]; } A[low] = pivot;//把基准放入其最终位置 return low;//返回本次划分所确定元素的位置 } void QuickSort(int A[], int low, int high) { if (low < high) {//low 小于 high 才有意义 int pivotpos = Partition(A, low, high);//划分数组,并返回确定元素位置,返回下标, QuickSort(A, low, pivotpos - 1);//递归划分左边待排序元素 QuickSort(A, pivotpos + 1, high);//递归划分右边待排序元素 } }
int Partition(int A[], int n) {//改写快速排序的划分算法
int low = 1, high = n;//定义并初始化高低索引
int pivot = A[high];//定义一个基准,初始时赋值为最后一个元素
while (low < high) {//low 小于 high 才有意义
while (low < high && A[low] <= pivot)
low++;//从左往右遍历寻找大于基准的元素
A[high] = A[low];//找到大于基准的元素后,则将其放到右边
while (low < high && A[high] >= pivot)
high--;//从右往左遍历寻找小于基准的元素
A[low] = A[high];//找到小于基准的元素后,则将其放到左边
}
A[low] = pivot;//把基准放入其最终位置
return low;//返回本次划分所确定元素的位置
}
int Search_k(int A[], int low, int high, int k) { int pivot = A[low]; int low_temp = low, high_temp = high;//定义并初始化高低索引 while (low < high) { while (low < high && A[high] >= pivot) { high--; } A[low] = A[high]; while (low < high && A[low] <= pivot) { low++;//从左往右遍历寻找大于基准的元素 } A[high] = A[low]; } A[low] = pivot; //接下来进行递归 if (low == k) {//若此次基准所在的最终位置就是 k 则直接返回此基准的值 return A[low]; } else if (low > k) {//这次划分的基准在k的右边,说明要去左边找 return Search_k(A, low_temp, low - 1, k); } else { return Search_k(A, low + 1, high_temp, k); } }
void Move(int A[], int n) { int low = 0, high = n - 1; int temp;//用于交换 while (low < high) { while (low < high && A[low] % 2 != 0) {//如果左边遍历的是奇数,继续往后遍历 low++; } while (low < high && A[high] % 2 != 1) {//如果右边遍历的是奇数,继续往前遍历 high--; } if (low < high) {//如果这时候两个没在一起,说明左右都找到元素了,交换 temp = A[low]; A[low] = A[high]; A[high] = temp; low++; high--; } } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。