基 础 算 法 总 结(原创)
由 王宇 原创并发布:
算法:数据的组织方法,数据结构是算法的载体。
数据结构包括:数组、链表、树、堆栈、队列
以下代码均在linux 环境下,gcc v4.5 编译调试通过。
排序:
直接插入排序:
时间复杂度:O(N^2)
思想:
R[n] 分成两个序列区:有序区R(j) (j = 0 j<i), 无序区R[i] (i=1...n-1),将无序区中的元素,插入到有序区适当的位置
实现代码:
#include<stdio.h> int main() { int R[16]={2,5,1,4,8,6,0,9,3,7,11,10,12,15,14,13}; int i,j,temp,n=16,p; for(i=1;i<n;i++) //R[i=1......n-1] 无序区中遍历 { for(j=0;j<i;j++) //R[i] 有序区中遍历 { if(R[j]<R[i]) //比较交换 { temp=R[j]; R[j]=R[i]; R[i]=temp; } } } for(p=0;p<n;p++) //打印输出结果 { printf("%d, ",R[p]); } printf("\n"); return 0; }
希尔插入:
时间复杂度:O(N*(logN))
思想:
分治法,直插法:按照步长,进行分组,然后进行各组的插入排序.减少交换次数
实现代码:
#include<stdio.h> int main() { int R[16]={2,5,1,4,8,6,0,9,3,7,11,10,12,15,14,13}; int i,j,temp,n=16,p,step; /*缩减法,分组*/ for(step = n/2;step > 0;step /= 2) { /*直接插入法,排序*/ for(i=step;i<n;i++) //无序区中遍历 { for(j=i-step;j<i;j++) //有序区中遍历 { if(R[j]<R[i]) //比较交换 { temp=R[j]; R[j]=R[i]; R[i]=temp; } } } } for(p=0;p<n;p++) //打印输出结果 { printf("%d, ",R[p]); } printf("\n"); return 0; }
选择排序:
时间复杂度:O(N^2)
思路:
R[n]分成两个序列区:在R[j]序列中选择最小的 (j =i+1 j<n),放入R[i]位置,作为已经排好的序列.(i = 0 i < n)
实现代码:
#include<stdio.h> int main() { int R[10] = {4,3,5,7,6,2,1,8,9,0}; int i,j,temp,n=10,p; for(i = 0;i < n;i++) //将选择的值,放在R[i]的位置 { for(j = i+1;j < n ;j++) //R[n]序列中选择最小的 { if(R[j] > R[i]) //比较交换 { temp=R[j]; R[j]=R[i]; R[i]=temp; } } } for(p=0;p < n;p++) //打印输出结果 { printf("%d",R[p]); } printf("\n"); return 0; }
冒泡排序:
时间复杂度:O(N^2)
思路:
R[n]序列,i=0,R[i]同R[i+1]比较,交换n-1次
#include<stdio.h> int main() { int R[10]={7,3,8,4,9,5,6,2,1,0}; int i,j,n=10,p,q,temp; for(i=n-1;i>0;i--) //n-1次交换 { for(j=0;j<i;j++) // i=0 R[i] 同 R[i+1]比较 { q=j+1; if(R[q]>R[j]) //比较交换 { temp=R[j]; R[j]=R[q]; R[q]=temp; } } } for(p=0;p<n;p++)//打印输出结果 { printf("%d",R[p]); } printf("\n"); return 0; }
快递排序 (不稳定排序):
时间复杂度:O(N*LogN)
思路:分治法,基准法:R[n]中找到基准点pivot,分成左右两个区域R[0..pivot-1] R[pivot+1..n-1],一部分的所有数据,要比另一部分的数据都小,递归解决
#include<stdio.h> /*递归,分治*/ void quickSort(int *R,int low,int height) { int pivot; if(low<height) { pivot=partition(R,low,height); //寻找基准 quickSort(R,low,pivot-1); //R[0..pivot-1] quickSort(R,pivot+1,height); //R[pivot+1..n-1] } } /*基准法*/ int partition(int *R,int i,int j) { int pivot=R[i]; while(i<j) { while(i<j && pivot<R[j] ) //从左向右同基准比较并移动交换 { j--; } if(i<j) R[i++]=R[j]; while(i<j && pivot>R[i]) //从右向左同基准比较并移动交换 { i++; } if(i<j) R[j--]=R[i]; } R[i]=pivot; return i; } int main() { int R[10]={0,2,8,4,7,3,6,5,1,9}; int p; quickSort(R,0,9); //调用快速排序 for(p=0;p<10;p++) //打印输出结果 { printf("%d",R[p]); } printf("\n"); return 0; }
归并排序 (稳定排序):
思路:
归并,二分法(递归)
归并操作:
R[n]无序队列m处分两组R[0..m]R[m+1...n-1]申请长度n的空间R1[n]
对比两个分组,将较小的先放入R1
将第一组剩余的放入R1
将第二组剩余的放入R1
将R1复制回R中
#include<stdio.h> #include<stdlib.h> void merge(int *R,int low,int mid,int high) { int i=low,j=mid+1,p=0; int *R1; R1=(int *)malloc((high-low+1)*sizeof(int)); if(!R1) perror("error:malloc"); while(i<=mid && j<=high) //对比两个分组,将较小的先放入R1 { R1[p++]=(R[i]<R[j]) ? R[i++] : R[j++]; } while(i<=mid) //将第一组剩余的放入R1 { R1[p++]=R[i++]; } while(j<=high) //将第二组剩余的放入R1 { R1[p++]=R[j++]; } for(i=low,p=0;i<=high;i++,p++) // 将R1复制回R中 { R[i]=R1[p]; } free(R1); } void mergeSort(int *R,int first,int last) { int mid; if(first<last) { mid=(last+first)/2; //二分法 mergeSort(R,first,mid); //R[low..m]递归分治 mergeSort(R,mid+1,last);//R[m+1...hight]递归分治 merge(R,first,mid,last); //归并操作 } } int main() { int R[10]={5,0,9,3,8,2,7,1,6,4}; int i,j,temp,p,n=10; mergeSort(R,0,9); //调用归并算法 for(p=0;p<n;p++) //打印输出结果 { printf("%d",R[p]); } printf("\n"); return 0; }
二叉树
#include<stdio.h> #include<stdlib.h> #include<malloc.h> #define MAX_CNT 5 typedef struct Tree_Struct{ int key; struct Tree_Struct * left; struct Tree_Struct * right; }Tree_Struct; void make_node(int target,Tree_Struct ** ppTree){ Tree_Struct * pTree_m=(Tree_Struct *)malloc(sizeof(Tree_Struct)); if(!pTree_m) perror("malloc error!"); pTree_m->key = target; pTree_m->left = NULL; pTree_m->right = NULL; *ppTree=pTree_m; } void insert_node(Tree_Struct ** ppNode,int target){ Tree_Struct * node = *ppNode; if(node == NULL){ make_node(target,&node); *ppNode = node; return; } if(node->key == target){ return; }else if(node->key > target){ insert_node(&node->left,target); *ppNode = node; return; }else{ insert_node(&node->right,target); *ppNode = node; return; } } int get_high(Tree_Struct ** ppNode){ int left_high=0,right_high=0; Tree_Struct * tree = *ppNode; if(tree == NULL){ return 0; }else{ left_high = get_high(&tree->left); right_high = get_high(&tree->right); return left_high > right_high ? left_high+1 : right_high+1; } } void pre_order(Tree_Struct * root){ if(root != NULL){ printf("%d ",root->key); pre_order(root->left); pre_order(root->right); }else{ printf(" # "); } } void in_order(Tree_Struct * root){ if(root != NULL){ in_order(root->left); printf("%d ",root->key); in_order(root->right); }else{ printf(" # "); } } void post_order(Tree_Struct * root){ if(root != NULL){ post_order(root->left); post_order(root->right); printf("%d ",root->key); }else{ printf(" # "); } } int main(){ int i,high=0,srand_int=0; Tree_Struct * root=NULL; srand((unsigned)time(NULL)); printf("Original number list : "); for(i=0;i<MAX_CNT;i++){ srand_int = rand() % 100; printf("%d ",srand_int); insert_node(&root,srand_int); } //前序 printf("\nPer Order:\n"); pre_order(root); printf("\n"); //中序 printf("In Order:\n"); in_order(root); printf("\n"); //后序 printf("Post Order:\n"); post_order(root); printf("\n"); //层高 printf("Tree level high:"); high = get_high(&root); printf("%d \n",high); return 0; }
单链表等待序
查找:
相关推荐
《数据结构与算法分析》的知识点归纳,完全原创,有助于该课程的复习。
快递选择SELECT等15个经典基础算法,共计31篇文章,包括算法理论的研究与阐述,及其编程的具体实现。很多个算法都后续写了续集,如第二个算法:Dijkstra 算法,便写了4篇文章;sift算法包括其编译及实现,写了5篇...
本调研报告建立在大量阅读论文的基础上,总结了2G,3G,4G的认证与空口加密算法的具体实现和三者的变化和比较。2G主要介绍GSM系统的认证算法COMP128以及A5算法,3G主要介绍f8算法及双向认证模式;4G介绍认证和加密在3G...
本文针对亚马逊国际象棋环境,对比分析了不同算法在效率上的优缺点,主要对蒙特卡洛博弈算法及其并行优化进行介绍和总结,在此基础上,对关于亚马逊棋蒙特卡洛博弈算法并行优化的研究前景进行了展望。 主要内容为...
5.4 总结 12 6 智能卡文件系统 13 6.1 文件类型 14 6.2 文件名 15 6.3 文件选择 15 6.4 EF的结构 16 6.5 文件访问条件 17 6.6 文件管理 17 6.7 原子进程 17 7 加解密算法 17 7.1 前言 17 7.2 对称密码系统 18 7.3 非...
技术方向的基础知识总结,包括语言、程序库、数据结构、算法、系统、网络、链接装载库等知识总结记录...... :folded_hands: 仓库内容如有错误或改进欢迎 issue 或 pr,建议或讨论可在 提出。由于本人水平有限,仓库...
我们的一个计算机软件基础大作业是编写4个程序,分别是约瑟夫斯问题、停车场管理、带权图的最小生成树提取、几种排序算法的比较,最后交一个报告,所以花了很长时间写了这边报告,既完成任务,也是对自己编写程序的...
方向校招求职者、初学者的基础知识总结,包括语言、程序库、数据结构、算法、系统、网络等知识及面试、内推等信息。 :blue_book: Summary 页面是目录收起,:open_book: Details 页面是全文展开,适用于不同场景和...
(原创不易,欢迎点赞),这是 2021 最新最完善的 Java 学习路线! Java学习资源汇总(个人总结) Java基础到Java实战全套学习视频教程,包括多个企业级实战项目:...
基础知识系统总结: 重要知识点详解: (很重要的一个数据结构,用好枚举真的没有那么简单!) 其他: 容器 、 、 并发 面试题总结: 必备知识点: JVM 其他 I/O : Java 8 :、、 Java9~Java14 : Java编程规范: 、...
本开源项目主攻Java相关技术栈,把平时积累的点点滴滴汇聚到这里来,既是总结也是分享。 文章都是原创,手敲不易,您的一个star,是我永远的动力! 文章首发公众号行百里er,欢迎关注。 不断更新的目录 架构师必备 ...
技术方向校招求职者、初学者的基础知识总结,包括语言、程序库、数据结构、算法、系统、网络、链接装载库等知识及面试经验、招聘、内推等信息。 :light_bulb: 侧边目录支持方式:、() :page_facing_up: 保存为 PDF...
基础知识系统总结: 重要知识点详解: (很重要的一个数据结构,用好枚举真的没有那么简单!) 其他: 容器 、 、 并发 面试题总结: 必备知识点: JVM 其他 I/O : Java 8 :、、 Java9~Java14 : Java编程规范: 、...
基础知识系统总结: 重要知识点详解: (很重要的一个数据结构,用好枚举真的没有那么简单!) 其他: 容器 、 、 并发 面试题总结: 必备知识点: JVM 其他 I/O : Java 8 :、、 Java9~Java14 : Java编程规范: 、...
基础知识系统总结: 重要知识点详解: (很重要的一个数据结构,用好枚举真的没有那么简单!) 其他: 容器 、 、 并发 面试题总结: 必备知识点: JVM 其他 I/O : Java 8 :、、 Java9~Java14 : Java编程规范: 、...
基础知识系统总结: 重要知识点详解: (很重要的一个数据结构,用好枚举真的没有那么简单!) 其他: 容器 、 、 并发 面试题总结: 必备知识点: JVM 其他 I/O : Java 8 :、、 Java9~Java14 : Java编程规范: 、...
内容概要:这是我是夜阑的狗微信小程序开发过程的总结,希望能够加深自己的印象,以及帮助到其他的小伙伴。所记录下的源码,并对其中代码进行注释讲解。如果代码中有什么需要改进的地方还请大佬不吝赐教。 适用人群...
内容概要:这是我是夜阑的狗微信小程序开发过程的总结,希望能够加深自己的印象,以及帮助到其他的小伙伴。所记录下的源码,并对其中代码进行注释讲解。如果代码中有什么需要改进的地方还请大佬不吝赐教。 适用人群...
基础知识系统总结: 重要知识点详解: (很重要的一个数据结构,用好枚举真的没有那么简单!) 其他: 容器 、 、 并发 面试题总结: 必备知识点: JVM 其他 I/O : Java 8 :、、 Java编程规范: 、 设计模式 : ...