学途智助
首页
分类
标签
关于网站
登录
eeettt123
2024-12-08
66
作者编辑
数据结构 408算法题 一些回答
对各个基础结构的记忆 代码题预测 哈夫曼 并查集 堆 kmp 栈 符号匹配 中缀 从前后到中 从中到前后 后序 非递归 要会栈 队列调用以供使用。 写成了就那样子吧 233 dfs 图论若干 bfs dfs 拓扑排序等等等等 图学若干算法。在邻接表的问题 ### 各种排序手写 难得主要是快排堆排序 个人写的堆排序 ```c++ int heap[100]; void headadjust( int root,int length){ int rootvalue = heap[root]; for(int child=root*2;child<=length;child*=2){ if(heap[child]<heap[child+1] && child<length) child++ ;//找到更大的堆 毕竟是大根堆 所以孩子要选最大的那个 if(rootvalue>=heap[child]) break;//说明这个根是他子树最大了。 else { heap[root]=heap[child]; root=child;//孩子当爹 ，爹到下一级子树 然后在循环里，他就会检测 这个下一级子树满足大根堆吗 ? } } heap[root] = rootvalue ; } void buildheap(int length ) { for(int i=1;i<=length;i++) heap[i] =a[i-1]; for(int i=length/2;i>=1;i--){ headadjust( i,length) ;//先从小分支开始下坠 } } void heapsort(int arr[],int length) { buildheap( length ); for(int i=length;i>1;i--){ swap(heap[i],heap[1]) ;//把大根的大堆顶放到最后 实现从大到小 headadjust( 1,i-1) ; } } ``` 手写的归并排序 ```c++ int b[100]; void merge (int low,int mid,int r){ // cout<<"merge 被调用了 参数low mid r 分别是" <<low<<" " <<mid<<' '<<" "; int high =r ; int length = high-low +1; rep(i,low,high) b[i]=a[i]; int i,j,k; for( i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){ if(b[i]<=b[j]) a[k] = b[i++]; //这里要有等号不然不稳定了了 else a[k]=b[j++]; }//合并链表 xs while(i<=mid) a[k++]=b[i++]; //合并有序数组 while(j<=high) a[k++]=b[j++]; } void mergesort(int l,int r){ // cout<<"mergesort 被调用了"<<l<<' '<<r; int mid =(l+r)/2; if(l<r){ mergesort(l,mid); mergesort(mid+1,r); merge(l,mid,r); } }; ``` ```c++ #include <stdio.h> #include<iostream> #define rep(i,a,b) for(int i=(int )a ;i<=(int) b ;i++) using namespace std; void fastsort(int A[], int low, int high); int Partition(int A[], int low, int high); void sort() ; int a[] = {9, -3, 5, 2, 6, 8, -6, 1, 3}; int n = sizeof(a) / sizeof(a[0]); // 计算数组A的大小 int main() { // 打印原始数组 printf("Original array: \n"); for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); // 调用快速排序 // fastsort(a, 0, n - 1); sort(); // 打印排序后的数组 printf("Sorted array: \n"); for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); return 0; } void swap(int &a,int &b){ int c=a; a=b; b=c; } //用第一个元素将待排序序列划分成左右两个部分 int Partition(int a[], int low, int high){ int pivot=a[low]; while(low<high){ while(a[high]>pivot && low<high) high--; a[high]=a[low]; //high 走完之后走到的那个 位置因为a[high]=a[low]; 此时 就是没用的 就是可以让low 用来填这个位置使用 } a[low] =pivot; // ahigh 先换alow的后果 return low; while(a[low]<pivot &&low<high) low++; a[low]=a[high]; } void fastsort(int a[], int low, int high){ if(low<high) { int pivotposition=Partition(a,low,high); fastsort(a,low,pivotposition-1); fastsort(a, pivotposition+1,high); } } void insert(int divide ,int low,int high,int data){ int i; // cout<<"datais= "<<data <<"high ="<<high<<endl; for( i=high;i>=low&& data<a[i];i-=divide) { a[i+divide]=a[i]; } a[i+divide] =data; } void insertsort(){ rep(i,1,n-1){ if(a[i]<a[i-1]){ insert(1,0,i-1,a[i]); } } } void shellsort (){ int dk,i,j; for(int dk=n/2;dk>=1;dk/=2){ for(i=dk;i<=n;++i){ if(a[i]<a[i-dk]) insert(dk,0,i-dk,a[i]); //debug个鬼鬼鬼鬼md 不dubug 老师看不出 } cout<<"dk="<<dk; cout << endl; rep(i,0,n-1){ cout<<a[i]<<' '; } cout << endl; } } void choicesort(){ rep(i,0,n-1){ int min =i; rep(j,i+1,n-1){ if(a[j]<a[min]) { min=j; } } if(min!=i) swap(a[i],a[min]); } //手写差不多得了 } void bubblesort(){ for(int i= 0;i<n;i++){ for(int j=i+1;j<n;j++){ if(a[j] <a[i]) { swap(a[j],a[i]); } } } } int heap[100]; void headadjust( int root,int length){ int rootvalue = heap[root]; for(int child=root*2;child<=length;child*=2){ if(heap[child]<heap[child+1] && child<length) child++ ;//找到更大的堆 毕竟是大根堆 所以孩子要选最大的那个 if(rootvalue>=heap[child]) break;//说明这个根是他子树最大了。 else { heap[root]=heap[child]; root=child;//孩子当爹 ，爹到下一级子树 然后在循环里，他就会检测 这个下一级子树满足大根堆吗 ? } } heap[root] = rootvalue ; } void buildheap(int length ) { for(int i=1;i<=length;i++) heap[i] =a[i-1]; for(int i=length/2;i>=1;i--){ headadjust( i,length) ;//先从小分支开始下坠 } void heapsort(int arr[],int length) { buildheap( length ); for(int i=length;i>1;i--){ swap(heap[i],heap[1]) ;//把大根的大堆顶放到最后 实现从大到小 headadjust( 1,i-1) ; } cout<<endl<<"排序后" ; rep(i,1,length){ cout<<heap[i] <<" "; } } void sort(){ heapsort(heap,n); } ``` ### 2024 算法题 本题目我认为解法就是拓扑排序过程中检测入度同时只能存在一个入度唯一的备选项，或者说stack push在for循环的时候看push 了几次。也就是说每次从选取一个节点，做入度删除或，造成的后果是只能使得现存图上只存在一个入度为0。 ```c++ #include <iostream> #include <vector> #include <queue> using namespace std; const int MAX_VERTICES = 100; // 假设图中最多有100个顶点 // 邻接矩阵表示图 int graph[MAX_VERTICES][MAX_VERTICES]; int V; // 图中顶点的数量 // 函数声明 void addEdge(int src, int dest); void printGraph(); bool isCyclicUtil(int v, int visited[], int recursionStack[]); bool isCyclic(); void topologicalSort(); // 添加边 void addEdge(int src, int dest) { graph[src][dest] = 1; // 有向边从src到dest } // 打印图 void printGraph() { for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { cout << graph[i][j] << " "; } cout << endl; } } // 检测图中是否有环（辅助函数） bool isCyclicUtil(int v, int visited[], int recursionStack[]) { visited[v] = 1; recursionStack[v] = 1; for (int i = 0; i < V; i++) { if (graph[v][i] == 1 && !visited[i]) { if (isCyclicUtil(i, visited, recursionStack)) { return true; } } else if (graph[v][i] == 1 && recursionStack[i]) { return true; } } recursionStack[v] = 0; return false; } // 检测图中是否有环 bool isCyclic() { int visited[MAX_VERTICES] = {0}; int recursionStack[MAX_VERTICES] = {0}; for (int i = 0; i < V; i++) { if (!visited[i]) { if (isCyclicUtil(i, visited, recursionStack)) { cout << "Graph contains cycle" << endl; return true; } } } return false; } // //void topologicalSortUtil(int v, int visited[], vector<int> &result) { // visited[v] = 1; // for (int i = 0; i < V; i++) { // if (graph[v][i] == 1 && !visited[i]) { // topologicalSortUtil(i, visited, result); // } // } // result.push_back(v); //} // //// 拓扑排序 //void topologicalSort() { // if (isCyclic()) { // cout << "Topological sorting is not possible for cyclic graph" << endl; // return; // } // // int visited[MAX_VERTICES] = {0}; // vector<int> result; // // for (int i = 0; i < V; i++) { // if (!visited[i]) { // topologicalSortUtil(i, visited, result); // } // } // // reverse(result.begin(), result.end()); // for (int i = 0; i < result.size(); i++) { // cout << result[i] << " "; // } // cout << endl; //} // 拓扑排序的辅助函数 int indegree[100]; void getindegree() { for(int i=0;i<V;i++) { for(int j=0;j<V;j++){ if(graph[j][i] ==1) indegree[i] ++ ; } } } void printindegree(){ for(int i=0;i<V;i++){ cout<<indegree[i]; }; cout<<endl; } int stk[100],top=0; void stkpush(int data){ stk[top++]=data; } bool stkempty(){ if(top<=0) return true; else return false; } int stkpop(){ int data; if(!stkempty()){ data=stk[--top]; } else cout<<"出错了栈空了"; } int print[100] , printcnt=0; bool toposort(){ int nums=0; for(int i=0;i<V ;i++){ int cnt=0; if(indegree[i]==0){ cnt++; stkpush(i) ; nums++; } if(cnt>1){ return false; } } while(!stkempty()){ int v1=stkpop(); int cnt=0; print[printcnt++]=v1 ; for(int i =0;i<V;i++){ if( 1==graph[v1][i]){ indegree[i]--; printf("在%d的邻接边 %d -- ",v1,i) ; if(indegree[i]==0){ cnt++; stkpush(i) ; nums++; } cout<<" cnt = "<<cnt<<endl; if(cnt>1) return false; } } } if(nums==V) return true; else return false; } int main() { // 初始化图的顶点数量 V = 8; //addEdge(1, 7); //addEdge(1, 3); //addEdge(3, 4); //addEdge(7, 4); //addEdge(7, 5); //addEdge(4, 6); //addEdge(3, 6); //addEdge(0,2); addEdge(0, 1); addEdge(1, 2); addEdge(2, 3); addEdge(3, 4); addEdge(4, 5); addEdge(5, 6); addEdge(6, 7); addEdge(4, 8); // 打印图 cout << "Graph: " << endl; printGraph(); getindegree(); printindegree(); if(toposort()) cout<<"成功了"; else cout<<"失败了" ; // //addEdge(5, 6); for(int i=0;i<V;i++){ cout<<print[i]; } return 0; } ``` ### ### 2014 算法题 思路 层次遍历 记录高度，计算wpl 直接weight * h ）（根节点高度为1 的话就h-1) ```c++ #include<iostream> #include<stdio.h> typedef struct btnode_struct{ btnode * leftchild,rightchild; int weight ;//不放设置为整数 } int wpl ;//全局变量声明 void pre(btptr currentNode ,int depth){ if(currentNode->leftchild== NULL && currentNode ->rightchild==NULL){ wpl=wpl + depth*currentNode->weight； //加上当前叶子节点的权重*深度 } if(currentNode->leftchild!= NULL ) pre( currentNode->leftchild,depth+1); if(currentNode->rightchild!= NULL ) pre( currentNode->rightchild,depth+1); return ; } int main(){ /* 题设实现若干树初始化 假定根节点为root */ pre(root,0); cout<<wpl;//wpl是全局变量哦，其他函数体统一访问调用。 } ``` 思路大错误 wpl定义不明白清楚 wpl是计算 叶子节点的路径长度 。所以 huffman 可以那么算 为此只需要检测叶节点既可。 ##### 验证部分使用kmichat写的构造树的结构的函数 ```c++ #include <iostream> #include <stdio.h> typedef struct btnode { btnode *leftchild, *rightchild; int weight; // 节点权重 } btnode, *btptr; int wpl; // 全局变量声明 // 前序遍历计算WPL void pre(btptr currentNode, int depth) { if (currentNode->leftchild == NULL && currentNode->rightchild == NULL) { wpl = wpl + depth * currentNode->weight; // 加上当前叶子节点的权重*深度 } if (currentNode->leftchild != NULL) pre(currentNode->leftchild, depth + 1); if (currentNode->rightchild != NULL) pre(currentNode->rightchild, depth + 1); return; } // 创建新节点 btptr createNode(int weight) { btptr newNode = new btnode; newNode->weight = weight; newNode->leftchild = NULL; newNode->rightchild = NULL; return newNode; } // 递归构建树 void buildTree(btptr &node, int weight) { // 读取节点权重，如果权重为-1，则该节点为空 std::cin >> weight; if (weight == -1) { node = NULL; } else { node = createNode(weight); buildTree(node->leftchild, weight); buildTree(node->rightchild, weight); } } int main() { // 假定根节点为root btptr root = NULL; std::cout << "Enter the weight of the root node (-1 for no node): "; buildTree(root, 0); pre(root, 0); std::cout << "\nWPL: " << wpl << std::endl; // wpl是全局变量哦，其他函数体统一访问调用。 return 0; } ``` 测试用例 ```c++ 5 3 1 -1 -1 2 -1 -1 4 -1 -1 ``` ### 2017算法题 ```c++ #include <iostream> #include <stdio.h> using namespace std; typedef struct btnode { struct btnode *lc, *rc; char data[10]; // 节点权重 } btnode, *btptr; midorder(btptr bt,int depth ){ if(bt->lc!=NULL|| bt->rc !=NULL) { //左右子树非空 不是叶子节点 //输出左括号 对于左子树和右子树 分别要输出括号来区分。 if(depth!=1)cout<<"("; if(bt->lc!=NULL)midorder(bt->lc,depth+1); cout<<bt->data; if(bt->rc!=NULL)midorder(bt->rc,depth+1); if(depth!=1) cout<<")";//输出右括号。 } else cout << bt->data;//叶子只要输出值就行了 。 //一点小错误就是根节点不用输出左右括号的。为此维护一个depth 或者验证一下等不等于root，但是传递root 指针直接传递，太傻了，直接用depth } int main() { } ``` ### 2022 算法 中序遍历 **一定要审题** 从0 开始这个数组，计算左孩子右孩子不要算错了 ```c++ #include <iostream> #include <stdio.h> using namespace std; typedef struct btnode { int data[100] ; int nums; }sqbitree; int checkarray[100]; int cnt = 0 sqbitree *a = sqbitree; //本质上实现中序遍历在 数组上面 void midorder( sqbitree * a,int root ){ int lc = root *2+1 int rc = root *2 +2; if(lc<=a->nums && a->data[lc] !=-1 ){ midorder(a,lc); } //中序遍历 checkarrcy[cnt++] = a->data[root] ; if(lc<=a->nums && a->data[rc] !=-1 ) midorder(a,rc); } int check() { for(int i = 0;i<cnt-1;i++){ if(checkarray[i]>checkarray[i+1]) return 0; } return 1; }//检验是不是中序序列是不是升序 //优化部分是不用数组，直接比较上一个值就行 //优化后 int midorder( sqbitree * a,int root ,int val){ //val是上一个访问的值 int lc = root *2+1 int rc = root *2 +2; int result=true; if(lc<=a->nums && a->data[lc] !=-1 ){ result= midorder(a,lc,val); } //中序遍历 if(a->data[root]<) return false; if(lc<=a->nums && a->data[rc] !=-1 ) result = midorder(a,rc,val); return result; }//这优化麻烦不如我之前的方法。 ```
算法竞赛
考研
赞
博客信息
作者
eeettt123
发布日期
2024-12-08
其他信息 : 其他三字母的人名首字母都是其他同学发布的哦
