对于常见算法折半查找、冒泡排序、快排、广度优先搜索、二叉树遍历的逐字逐句解析

改进的折半查找

int binary_search(int buffer[], int n, int key){//在有n个元素的buffer数组中查找key元素int l = 0, r = n - 1, m; //定义左边界，右边界，中间位置while(l < r){  //l == r时跳出循环m = (l + r) / 2;  //取l到r的中间位置if (buffer[m] < key) l = m + 1; //若m处的元素值比key小，说明要找的元素在m + 1到r之间，则令l = m + 1;else r = m;  //若m处元素值大于等于key，说明要找的元素在l到m之间，则令r = m;} //（实际功能）找第一个大于等于key的元素//离开循环时无论l处的元素是否等于key，一定满足l左端的元素比key小，l右端的元素大于等于keyif (buffer[l] == key) return 1;  //若l处元素等于key，则查找成功，否则查找失败else return -1;
}

冒泡排序

void BubbleSort(int A[], int n){for (int i = 0; i < n - 1; i ++ ){bool tag = false; //表示本趟冒泡排序是否发生交换的标志for (int j = 1; j < n; j ++ ) { //一趟冒泡排序if (A[j] < A[j - 1]){       //若后一个的元素比前一个元素小swap(A[j], A[j - 1]);  //交换两个值tag = true;             //true代表本趟发生了冒泡排序}}if (!tag) return; // 若本趟没发生冒泡排序，则说明已经有序。}
}

快速排序

struct TypeDate{string name;int age;
};int QuitPass(TypeDate array[], int left, int right){TypeDate Key = Array[left];  //以最左端的数字作为排序的基准元素while(left < right){  //从序列两端交替向中间扫描，left == right时，代表排序完成while(left < right) { // 找到right左边第一个比key小的元素，放在left处if (Array[right].name < key.name){ //若找到执行以下语句Array[left] = Array[right]; //将从right向左找到的第一个比key小的元素放在left处；left ++; //left右移一位,用于在下一个while中查找左边第一个比key大的元素break; // 跳出该循环}right --; //若未找到，right左移一位，继续查找}while(left < right){  //找到left右端第一个比key大的元素，放在right处if(Array[left].name > key.name) { //若找到，则执行以下语句Array[right] = Array[left]; //将找到的元素放在right处right --; //right左移一位，用于下一个while查找比key大的数break; //跳出循环}left ++; //若未找到，left右移一位，继续查找}}Array[left] = key; // 跳出循环时，left == right， 将key放在该位置return left; //返回left
}void QuicSort(TypeDate Array[], int left, int right){if (left >= right) return;int mid = QuitPass(Array, left, right); //经过一次快排后，比Array[mid]小的元素一定在mid左边，比Array[mid]大的元素一定在mid右边QuickSort(Array, left, mid - 1);   //继续递归调用QuickSort对left到mid - 1进行排序QuickSort(Array, mid + 1, right);   //继续递归调用QuickSort对mid + 1到right进行排序
}

广度优先搜索

struct Node{int data;Node *A[10]; //指向子节点的指针Node(){ //构造函数for (int i = 0; i < 10; i ++ ) A[i] = NULL;}
};struct Queue{  //队列结构，存储指向树的节点的指针Node *Buffer[n];   //存储节点int front, rear;   //头指针和尾指针int inc(int d){return (d + 1) % n;} //循环队列尾指针后移一位bool full(){return inc(rear) == front}; //循环队列判满bool empty(){return front == rear;} //循环队列判空bool append (Node *p){ //向队列中添加节点if (full()) return false; //若队满，则添加失败rear = inc(rear); //队尾指针后移一位Buffer[rear] = p; //填入新节点return true;}Node *RemoveHead(){if (empty()) return NULL;  //若队列为空则返回NULLfront = inc(front);    //头指针后移一位return Buffer[front];}Queue(){front = rear = 0;} //构造函数（初始化）
};//只能处理无环图
void BreadthFirstSearch(Node *pRoot) { //广度优先搜索Queue R;  //定义一个队列Node *p;R.append(pRoot); //第一个节点入队while(!R.empty()){ //队列不为空，执行循环p = R.RemoveHead(); // 取队头元素visit(p);  //访问p节点for(int i = 0; i < 10; i ++ ) { //编历其连接的节点if (p->A[i] != NULL)  //若存在相连接的节点，入队R.append(p->A[i]);}}
}

相关问题及解答

问题：
队列类中的front、rear的准确含义（功能、用途、谁指向数据元素）；广度优先搜索函数中对象R的功能和作用（存储什么，为什么要用队列来存储这些东西？）
解答：（非专业 ）

1. front 是指队头元素的前一个元素的下标， rear是值队尾元素的下标 ， rear 指向队尾元素 ；
2. front 用于取队头元素或删除队头元素， rear用于在队尾添加元素， R存储的是图中节点的信息；
3. 为什么用队列来存储：
   第一是 因为队列的存储机制为先进先出，而广度优先搜索算法恰好需要保证优先访问已访问顶点的未访问邻接点。因此队列最适合广度优先算法的存储法则。
   第二是 队列这种数据结构只支持两个基本操作：将新元素从队尾加入队列和将队首元素移出队列。相比于其他数据结构，队列因为操作简单而效率更高。

二叉树遍历

需求：
你能将二叉树遍历程序改造一下，用来对二叉树的结点进行简单的统计吗？比如求结点个数，求结点数据的总和，求数据能被3整除的结点个数…

struct Tree{int data;Tree *left, *right;Tree(){left = NULL;right = NULL;}
};int num, sum, t;   //变量与需求一一对应
void search(Tree *phead){if (phead == NULL) return;//先序遍历num++;sum += phead->data;if (phead->data % 3 == 0) t++;search(phead->left);search(phead->right);//中序遍历search(phead->left);num++;sum += phead->data;if (phead->data % 3 == 0) t++;search(phead->right);//后序遍历search(phead->left);search(phead->right);num++;sum += phead->data;if (phead->data % 3 == 0) t++;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！