简单的理解协同过滤： 相似兴趣爱好的人喜欢相似的东西，具有相似属性的物品可以推荐给喜欢同类物品的人。比如，user A喜欢武侠片，user B也喜欢武侠片，那么可以把A喜欢而B没看过的武侠片推荐给B，反之亦然，这种模式称为基于用户的协同过滤推荐（User－User Collaborative Filtering Recommendation）；再比如User A买了《java 核心技术卷一》，那么可以推荐给用户《java核心技术卷二》《java编程思想》，这种模式称为基于物品的协同过滤（Item－Item Collaborative Filtering Recommendation）. 下面是亚马逊中查看《java核心技术卷一》这本书的推荐结果：  下面参考《集体智慧编程》一书，实现基于欧几里德距离和基于皮尔逊相关度的用户相似度计算和推荐。 ### 数据集，用户对电影的打分表： | movies | Lady in the Water | Snakes on a Plane | Just My Luck | Superman Returns | You, Me and Dupree | The Night Listener | |-----|-----|-----|-----|-----|-----|-----| | Lisa | 2.5 | 3.5 | 3.0 | 3.5 | 2.5 | 3.0 | | Gene | 3.0 | 3.5 | 1.5 | 5.0 | 3.5 | 3.0 | | Michael | 2.5 | － | 3.0 | 3.5 | － | 4.0 | | Claudia | － | 3.5 | 3.0 | 4.0 | 2.5 | 4.5 | | Mick | | 3.0 | 4.0 | 2.0 | 3.0 | 2.0 | | Jack | 3.0 | 4.0 | － | 5.0 | 3.5 | 3.0 | | Toby | － | 4.5 | － | 4.0 | 1.0 | － | ### 建立数据字典 ~~~ critics={'Lisa': {'Lady in the Water': 2.5, 'Snakes on a Plane': 3.5, 'Just My Luck': 3.0, 'Superman Returns': 3.5, 'You, Me and Dupree': 2.5, 'The Night Listener': 3.0}, 'Gene': {'Lady in the Water': 3.0, 'Snakes on a Plane': 3.5, 'Just My Luck': 1.5, 'Superman Returns': 5.0, 'The Night Listener': 3.0, 'You, Me and Dupree': 3.5}, 'Michael': {'Lady in the Water': 2.5, 'Snakes on a Plane': 3.0, 'Superman Returns': 3.5, 'The Night Listener': 4.0}, 'Claudia': {'Snakes on a Plane': 3.5, 'Just My Luck': 3.0, 'The Night Listener': 4.5, 'Superman Returns': 4.0, 'You, Me and Dupree': 2.5}, 'Mick': {'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0, 'Just My Luck': 2.0, 'Superman Returns': 3.0, 'The Night Listener': 3.0, 'You, Me and Dupree': 2.0}, 'Jack': {'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0, 'The Night Listener': 3.0, 'Superman Returns': 5.0, 'You, Me and Dupree': 3.5}, 'Toby': {'Snakes on a Plane':4.5,'You, Me and Dupree':1.0,'Superman Returns':4.0}} ~~~ ### 欧几里德距离 ~~~ #返回一个有关person1与person2的基于距离的相似度评价 def sim_distance(prefs, person1, person2): #得到shared_item的列表 ci = {} for item in prefs[person1]: if item in prefs[person2]: ci[item] = prefs[person1][item] - prefs[person2][item] if len(ci) == 1: # confuses pearson metric return sim_distance(prefs, person1, person2) sum_of_squares=sum([pow(prefs[person1][item]-prefs[person2][item],2) for item in prefs[person1] if item in prefs[person2]]) return 1/(1 + sqrt(sum_of_squares)) ~~~ 计算Lisa和Gene之间的欧式距离： ~~~ print(sim_distance(critics,'Lisa','Gene')) ~~~ 结果： ~~~ 0.294298055086 ~~~ ### 皮尔逊相关系数 ~~~ #返回一个有关person1与person2的基于皮尔逊相关度评价 def sim_pearson(prefs,p1,p2): # Get the list of mutually rated items si={} for item in prefs[p1]: if item in prefs[p2]: si[item]=1 # if they are no ratings in common, return 0 if len(si)==0: return 0 # Sum calculations n=len(si) # Sums of all the preferences sum1=sum([prefs[p1][it] for it in si]) sum2=sum([prefs[p2][it] for it in si]) # Sums of the squares sum1Sq=sum([pow(prefs[p1][it],2) for it in si]) sum2Sq=sum([pow(prefs[p2][it],2) for it in si]) # Sum of the products pSum=sum([prefs[p1][it]*prefs[p2][it] for it in si]) # Calculate r (Pearson score) num=pSum-(sum1*sum2/n) den=sqrt((sum1Sq-pow(sum1,2)/n)*(sum2Sq-pow(sum2,2)/n)) if den==0: return 0 r=num/den return r ~~~ 计算Lisa和Gene之间的皮尔逊相关系数： ~~~ print(sim_pearson(critics,'Lisa','Gene')) ~~~ 结果： ~~~ 0.396059017191 ~~~ ### 选择Top N ~~~ # 从反应偏好的字典中返回最为匹配者 # 返回结果的个数和相似度函数均为可选参数 def topMatches(prefs, person, n=5, similarity=sim_pearson): scores = [(similarity(prefs, person, other), other) for other in prefs if other != person] scores.sort(reverse=True) return scores[0:n] ~~~ 返回4个和Toby品味最相似的用户： ~~~ print(topMatches(critics,'Toby',n=4)) ~~~ 结果： ~~~ yaopans-MacBook-Pro:ucas01 yaopan$ python recommend.py [(0.9912407071619299, 'Lisa'), (0.9244734516419049, 'Mick'), (0.8934051474415647, 'Claudia'), (0.66284898035987, 'Jack')] ~~~ ### 基于用户推荐 ~~~ def getRecommendations(prefs,person,similarity=sim_pearson): totals={} simSums={} for other in prefs: #和其他人比较，跳过自己 if other==person: continue sim=similarity(prefs,person,other) #忽略评价值为0或小于0的情况 if sim<=0: continue for item in prefs[other]: # 只对自己还未看过到影片进行评价 if item not in prefs[person] or prefs[person][item]==0: # 相似度*评价值 totals.setdefault(item,0) totals[item]+=prefs[other][item]*sim # 相似度之和 simSums.setdefault(item,0) simSums[item]+=sim # 建立一个归一化列表 rankings=[(total/simSums[item],item) for item,total in totals.items()] # 返回经过排序的列表 rankings.sort() rankings.reverse() return rankings ~~~ 给Toby推荐： ~~~ print(getRecommendations(critics,'Toby')) ~~~ 推荐结果 ~~~ yaopans-MacBook-Pro:ucas01 yaopan$ python recommend.py [(3.3477895267131013, 'The Night Listener'), (2.8325499182641614, 'Lady in the Water'), (2.5309807037655645, 'Just My Luck')] ~~~ ### 基于物品推荐 基于物品推荐和基于用户推荐类似，把物品和用户调换。 转换函数： ~~~ def transformPrefs(prefs): result={} for person in prefs: for item in prefs[person]: result.setdefault(item,{}) result[item][person]=prefs[person][item] return result ~~~ 返回和Superman Returns相似的电影： ~~~ movies=transformPrefs(critics) print("和Superman Returns相似的电影：") print(topMatches(movies,'Superman Returns')) ~~~ 结果： ~~~ [(0.6579516949597695, 'You, Me and Dupree'), (0.4879500364742689, 'Lady in the Water'), (0.11180339887498941, 'Snakes on a Plane'), (-0.1798471947990544, 'The Night Listener'), (-0.42289003161103106, 'Just My Luck')] ~~~ 结果为负的是最不相关的。 代码下载地址： [recommend.py](http://download.csdn.net/detail/napoay/9385520)

背包问题： > 背包问题： 已知背包的容量为M和n件物品。第i件物品的重量为wi,价值为pi，将物品i的一部分xi放进背包即可获得价值pi*xi的价值。问题： 怎样装包使所获得的价值最大？ 贪心法核心思想： > 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。 求解背包问题的贪心原则可能是以下几个： 1. 每次选价值最大的物品装进背包 1. 每次都选提及最小的物品装进背包 1. 每次选单位价值最大的装. 准则1每次装的价值大，但是同时也可能占据了较大的空间；准则2能装的物品多，总价值未必高，按第三种准则装可以实现背包总价值最大.因此将每个物品按单位价值递减排序，先装单位价值高的，最好空间有剩余，装物品的一部分即可。 C++程序实现： ~~~ include <iostream> using namespace std; //数组按pi/wi由大到小不递增排列 int greedypackage(int p[],int w[],int M,double X[],int n){ int i; int rc=M;//剩余背包容量，初始化为M; for (i = 0; i < n; ++i) { if(w[i]<=rc){ X[i]=1; rc=rc-w[i]; } else{ break; } } if(i<=n){ X[i]=(double)rc/w[i]; } for (i = 0; i < n; ++i) { cout<<X[i]<<"\t"; } return 0; } int main(){ int p[3]={24,15,25}; int w[3]={15,10,18};//数组w是按wi/pi递减排列的,这一步可以用快速排序实现 int M=20; double A[3]={0,0,0}; greedypackage(p,w,M,A,3); return 0; } ~~~ 输出解： ~~~ 1 0.5 0 ~~~

概率算法也叫随机化算法。分治算法、贪心算法、动态规划算法、回溯法、分治界限算法这些算法的每一计算步骤都是确定的，概率算法则允许算法在执行过程中随机地选择下一个计算步骤。在很多情况下，算法在执行过程中面临选择时，随机性选择比最优选择省时，因此概率算法可以在很大程度上降低算法的复杂度。 大致可分4类： 1. 数值随机化算法 1. 蒙特卡罗(Monte Carlo)算法 1. 拉斯维加斯(Las Vegas)算法 1. 舍伍德(Sherwood)算法 各算法特点对比： ###1.数值随机化算法 > 用于数值计算，求得的往往是近似解，比如通过概率投点的思想计算圆周率、计算定积分.  如图，向边长为1的正方形内随机投n个点，记落入圆内的点的个数为k，根据几何概型，k／n近似等于圆的面积除以正方形对面积。只计算第一象限，1／4＊pi＊1＊1除以1＊1近似等于k／n，pi＝4＊k/n 程序验证： ~~~ #include <iostream> #include <ctime> #include <math.h> using namespace std; int main(){ srand((unsigned)time(0)); double x,y; int k=0,n=1000000; for(int i=0;i<n;i++){ x=rand()/(double)(RAND_MAX); //随机数x y=rand()/(double)(RAND_MAX); //随机数y x、y在0到1之间 if((pow(x,2)+pow(y,2))<=1) k++; } cout<<(double)4*k/n<<endl; } ~~~ n等于100：  n等于1000：  n等于100000000  可以看到，n约大pi的值越精确.当n等于1亿的时候，可以稳定到3.141 可以用相同的方法计算定积分. ###2.蒙特卡罗(Monte Carlo)算法 > 能求得问题的一个解，但是这个解未必正确 ###3.拉斯维加斯(Las Vegas)算法 > 要么找到的解是正确的，要么找不到解 ###4.舍伍德(Sherwood)算法 > 一定能找到解，而且是正确解 后面三种算法的实例等到有时间再补充。

###问题 > 给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整均为负数时定义子段和为0，依此定义，所求的最优值为： Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 例如，当（a[1],a[2],a[3],a[4],a[5],a[6]）=(-2,11,-4,13,-5,-2)时，最大子段和为20。 ###思路 从第一个元素开始，计算1－2的和、1－3的和、直到1－n的和，sum来记录最大的和，在循环过程中如果有和比sum大，把当前最大和替换掉，记录besti和bestj；然后计算2－3的和、2－4的和、直到2－n的和。需要2次for循环，时间复杂度O(n^2). ###代码 ~~~ #include <iostream> using namespace std; //求a中的最大子段和 int maxSum(int a[],int n){ int i,j,sum=0,besti,bestj; for(i=0;i<4;i++){ int newsum=0; for ( j= i; j <n; ++j) { newsum+=a[j]; if(newsum>sum){ sum=newsum; besti=i; bestj=j; } } } cout<<"开始位置："<<a[besti]<<endl; cout<<"开始位置："<<a[bestj]<<endl; return 0; } int main(){ int a[6]={-2,11,-4,13,-5,-2}; maxSum(a,6); int b[10]={1,-5,6,-2,11,-7,23,-13,15,-3}; maxSum(b,10); } ~~~ ###输出 ~~~ 开始位置：11 开始位置：13 开始位置：6 开始位置：15 ~~~ ###时间复杂度 O(n^2)

~~~ #include <iostream> #include <stdlib.h> using namespace std; template<class T>void mergeSort(T a[],int left,int right); void printArray(int a[],int n){ for(int i=0;i<n;i++){ cout<<a[i]<<"\t"; } } void Merge(int c[],int d[],int l,int m,int r){ int i=1; int j=m+1; int k=1; while((i<=m)&&(j<=r)){ if(c[i]<=c[j]){ d[k++]=c[i++]; }else{ d[k++]=c[j++]; } } if(i>m){ for(int q=j;q<=r;q++){ d[k++]=c[q]; } }else{ for(int q=i;q<=m;q++){ d[k++]=c[q]; } } } void Copy(int a[],int b[],int left,int right){ for (int i = left; i < right; ++i) { a[i]=b[i]; } } void mergeSort(int a[],int left,int right){ if(left<right){ int i=(left+right)/2; int *b=new int[100]; mergeSort(a,left,i); mergeSort(a,i+1,right); Merge(a,b,left,i,right); Copy(a,b,left,right); } } int main(){ int a[10]={10,3,90,22,8,1,20,100,33,106}; cout<<"排序前：\n"; printArray(a,10); mergeSort(a,0,9); cout<<"排序后：\n"; printArray(a,10); } ~~~

快速排序是分治算法的典型应用，基本策略： > 将数组A[1..n]分成两个子数组B[1..p]和B[p+1..n],使得B[1..p]中的元素均不大于B[p+1..n]中的元素，然后分别对这两个数组进行排序，最后把两个数组连接起来。 ### 代码 ~~~ #include <iostream> using namespace std; void printArray(int a[],int n){ for(int i=0;i<n;i++){ cout<<a[i]<<"\t"; } } inline void Swap(int &s,int &t){ int temp=s; s=t; t=temp; } int Partition(int a[],int p,int r){ int i=p,j=r+1; int x=a[p]; while(true){ while(a[++i]<x); while(a[--j]>x); if(i>=j){break;} Swap(a[i],a[j]); } a[p]=a[j]; a[j]=x; return j; } void QuickSort(int a[],int p,int r){ if (p<r) { int q=Partition(a,p,r); QuickSort(a,p,q-1); QuickSort(a,q+1,r); } } int main(){ int a[10]={10,3,90,22,8,1,20,100,33,106}; cout<<"排序前：\n"; printArray(a,10); QuickSort(a,0,9); cout<<"排序后：\n"; printArray(a,10); } ~~~ ### 运行结果 ~~~ 排序前： 10 3 90 22 8 1 20 100 33 106 排序后： 1 3 8 10 20 22 33 90 100 106 ~~~

### 1.问题描述 > 双机调度问题,又称独立任务最优调度：用两台处理机A和B处理n个作业。设第i个作业交给机器A处理时所需要的时间是a[i]，若由机器B来处理，则所需要的时间是b[i]。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这n个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。研究一个实例：n=6, a = {2, 5, 7, 10, 5, 2}, b = {3, 8, 4, 11, 3, 4}. ### 2.代码 ~~~ #include <iostream> #include <stdlib.h> using namespace std; int max(int a,int b){ return a>b?a:b; } int min(int a,int b){ return a<b?a:b; } int main(){ int a[6]={2,5,7,10,5,2}; int b[6]={3,8,4,11,3,4}; int sum_a=0,sum_b=0,T=0,n=6; for (int i = 1; i <=n; i++) { T=max(T,min(sum_a+a[i-1],sum_b+b[i-1])); if(sum_a+a[i-1]>sum_b+b[i-1]){ sum_b+=b[i-1]; cout<<"任务"<<i<<"分配给B做"<<endl; }else{ sum_a+=a[i-1]; cout<<"任务"<<i<<"分配给A做"<<endl; } } cout<<"总时间是："<<T<<endl; } ~~~ ### 3.结果 ~~~ yaopans-MacBook-Pro:algorithm yaopan$ g++ exercise5-2.cpp yaopans-MacBook-Pro:algorithm yaopan$ ./a.out 任务1分配给A做 任务2分配给A做 任务3分配给B做 任务4分配给B做 任务5分配给A做 任务6分配给A做 总时间是：15 ~~~

二分插入排序是对二分查找和插入排序的一个结合，插入操作时通过二分查找找到要插入的位置. ~~~ #include <stdio.h> // 打印数组a void printArr(int a[],int n){ for (int i = 0; i < n; ++i) { printf("%d\t",a[i]); } printf("\n"); } void ModInsertSort(int a[],int n){ int i,j,temp,left,right,mid; for ( i = 1; i < n; ++i) { left=0; temp=a[i]; right=i-1; while(left<=right){ mid=(left+right)/2; if(a[mid]>temp){ right=mid-1; }else{ left=mid+1; } } for ( j = i-1; j >right;j--) a[j+1]=a[j]; a[right+1]=temp; } } int main(){ int a1[]={10,111,22,31,14,57,46,89,39}; ModInsertSort(a1,9); printArr(a1,9); } 输出结果： yaopans-MacBook-Pro:algorithm yaopan$ ./a.out 10 14 22 31 39 46 57 89 111 ~~~ ### JAVA描述 ~~~ public class BinInserSort { //二分插入排序 public static void ModInsertSort(int a[]){ int i,j,right,left,mid,temp; for (i =1; i < a.length; ++i) { temp=a[i]; left=0; right=i-1; while(left<=right){ mid=(left+right)/2; if(a[mid]>temp){ right=mid-1; }else{ left=mid+1; } } for(j=i-1;j>right;j--){ a[j+1]=a[j]; } a[right+1]=temp; } } public static void printArry(int[] a){ for (int i = 0; i < a.length; i++) { System.out.print(a[i]+"\t"); } System.out.println("\n"); } public static void main(String[] args) { int a[]={1,2,34,24,5,6,7,8,77,90,37,19,20}; System.out.println("排序前:"); printArry(a); ModInsertSort(a); System.out.println("排序后:"); printArry(a); } } 排序前: 1 2 34 24 5 6 7 8 77 90 37 19 20 排序后: 1 2 5 6 7 8 19 20 24 34 37 77 90 ~~~

###JAVA版 ~~~ public class Merge { //合并有序数组 public static void mergeSort(int a[], int b[], int c[]) { int n = a.length, m = b.length; int i, j, k; i = j = k = 0; while (i < n && j < m) { if (a[i] < b[j]) { c[k++] = a[i++]; } else { c[k++] = b[j++]; } } while (i < n) c[k++] = a[i++]; while (j < m) c[k++] = b[j++]; } //打印数组中的元素 public static void printArr(int a[]) { for (int i = 0; i < a.length; i++) { System.out.print(a[i] + "\t"); } } public static void main(String[] args) { System.out.println("Hello World!"); int[] a = new int[] { 1, 2, 5, 6 }; int[] b = new int[] { 3, 8, 9, 10 }; int c[] = new int[8]; mergeSort(a, b, c); printArr(c); } } 输出结果： 1 2 3 5 6 8 9 10 ~~~ ###C语言版 ~~~ #include <stdio.h> // 打印数组a void printArr(int a[],int n){ for (int i = 0; i < n; ++i) { printf("%d\t",a[i]); } printf("\n"); } //合并有序数组 void mergeArray(int a[],int n,int b[],int m,int c[]){ int i, j, k; i = j = k = 0; while (i <n && j<m) { if (a[i] < b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; } while (i < n) c[k++] = a[i++]; while (j < m) c[k++] = b[j++]; } int main(){ int a[3]={2,3,6}; int b[2]={1,5}; int c[5]={}; mergeArray(a,3,b,2,c); printArr(c,5); } 输出结果： yaopans-MacBook-Pro:algorithm yaopan$ ./a.out 1 2 3 5 6 ~~~

### 1. 折半搜索 折半搜索是分治算法思想的一典型例子，要解决输入规模很大的问题时可以将该问题分解，得到k个不同的可独立求解的子问题，求出字问题的解之后再用合适的方法合并求出整个问题的解。将整个问题分解成若干小问题来处理的方法称为分治法.比如：找一个学校里身高最高的同学，可以现在每个班找出最高的，把每个班里最高的汇合在一起，找出全校最高的。 二分查找也叫折半搜索，在数组a[1…n]中搜索x,数组a中的元素不递减.如果找到x，则返回x所在的位置下标，否则返回-1.解决思想就是先讲x与数组中中间位置的元素相比较，x比中间元素值大，说明x取值在数组右半部分范围内，否则在左半部分，如此不断分割求解将x的范围不断缩小最后就可求出x的位置. ~~~ #include <stdio.h> #include <stdlib.h> #include <math.h> //二分查找 int bin_search(int a[],int n,int key){ int left=1,right=n,middle; while(left<right){ middle=(left+right)/2; if (key==a[middle]) { return a[middle]; }else if(key>a[middle]){ left=middle+1; }else{ right=middle-1; } } return -1; } int main(){ int a[11]={0,1,2,3,4,5,6,7,8,9,10}; printf("%d\n",bin_search(a,11,7) ); printf("%d\n",bin_search(a,11,11) ); } ~~~ 归并排序是在插入排序的基础上应用分治的思想而来的，先看插入排序. ### 2.冒泡排序 ~~~ #include <stdio.h> // 打印数组a void printArr(int a[],int n){ for (int i = 0; i < n; ++i) { printf("%d\t",a[i]); } printf("\n"); } //冒泡排序 int bubble_sort(int a[],int n){ int i,j; for (int i = 0; i < n-1; ++i) { for (j= i+1; j<n; ++j) { if (a[i]>a[j]) { int temp=a[i]; a[i]=a[j]; a[j]=temp; } } } return 1; } int main(){ int a1[]={1,4,2,15,6,37,28}; printf("排序前："); printArr(a1,7); bubble_sort(a1,7); printf("排序后："); printArr(a1,7); } 输出结果： yaopans-MacBook-Pro:algorithm yaopan$ gcc bubble_sort.c yaopans-MacBook-Pro:algorithm yaopan$ ./a.out 排序前：1 4 2 15 6 37 28 排序后：1 2 4 6 15 28 37 ~~~ 折半搜索和插入排序都是在非递减数组中进行的，对于无序数组可以先冒泡排序. ### 3.插入排序 向有序数组中插入元素 ~~~ //向有序数组中插入元素 void insertArr(int a[],int n,int e){ int i; for (i = n-1; i>0; --i) { if (a[i]>e){ a[i+1]=a[i]; }else{ break; } } a[i+1]=e; } ~~~ 插入排序就是利用向有序数组中插入元素的思想进行排序，数组中第一个元素a[0]放在最开始，a[1]比a[0]小，则交换a[0]和a[1]的位置，否则a[1] 插在a[0] 的后面.这样第一次插入a[0]和a[1] 已经排列好了，再来第三个元素插入到前两个元素中去，以此类推.下面是插入排序的代码： ~~~ #include <stdio.h> // 打印数组a void printArr(int a[],int n){ for (int i = 0; i < n; ++i) { printf("%d\t",a[i]); } printf("\n"); } //插入排序，参数为数组a和数组长度n void insertSort(int a[],int n){ int i,e,j; for (i = 1; i < n; ++i) { e=a[i]; for (j=i-1;j>=0;--j) { if (e<a[j]) { a[j+1]=a[j]; }else{ break; } } a[j+1]=e; } } int main(){ int a1[]={556,90,6,89,1,4,2,15,6,37,28}; printf("排序前："); printArr(a1,11); insertSort(a1,11); printf("排序后："); printArr(a1,11); } yaopans-MacBook-Pro:algorithm yaopan$ ./a.out 排序前：556 90 6 89 1 4 2 15 6 37 28 排序后：1 2 4 6 6 15 28 37 89 90 556 ~~~ ### 4.归并排序 ~~~ #include <stdio.h> #include <stdlib.h> //将有二个有序数列a[first...mid]和a[mid...last]合并。 void mergearray(int a[], int first, int mid, int last, int temp[]) { int i = first, j = mid + 1; int m = mid, n = last; int k = 0; while (i <= m && j <= n) { if (a[i] <= a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; } while (i <= m) temp[k++] = a[i++]; while (j <= n) temp[k++] = a[j++]; for (i = 0; i < k; i++) a[first + i] = temp[i]; } void mergesort(int a[], int first, int last, int temp[]) { if (first < last) { int mid = (first + last) / 2; mergesort(a, first, mid, temp); //左边有序 mergesort(a, mid + 1, last, temp); //右边有序 mergearray(a, first, mid, last, temp); //再将二个有序数列合并 } } bool MergeSort(int a[], int n) { int *p= new int[n]; if (p == NULL) return false; mergesort(a, 0, n - 1, p); delete[] p; return true; } //打印数组 void printArr(int a[],int n){ for (int i = 0; i < n; ++i) { printf("%d\t",a[i]); } printf("\n"); } int main(){ int a[]={1,4,5,7,3,10,56,23,54}; int c[]={}; MergeSort(a,9); printArr(a,9); } ~~~

栈是先进后出，队列则是先进先出.下面贴一下队列的基本操作. ### 1.队列的顺序表示. #### 1.1队列的结构体定义 ~~~ #include <stdio.h> #include <stdlib.h> typedef int DataType; #define MAXNUM 20 /*队列中元素的最大个数*/ struct Seqqueue /*顺序队列类型定义*/ { int f,r; DataType q[MAXNUM]; }; typedef struct Seqqueue Seqqueue,*PSeqqueue; /*创建一个空队列*/ PSeqqueue createEmptyqueue(void); /*判断队列是否为空*/ int isEmptyqueue_seq(PSeqqueue paqu); /*在队列中插入一个元素*/ void enqueue_seq(PSeqqueue paqu,DataType x); /*删除队头元素*/ void dequeue_seq(PSeqqueue paqu); /*对非空队列求队头元素*/ DataType frontqueue_seq(PSeqqueue paqu); ~~~ #### 1.2创建队列 ~~~ PSeqqueue createEmptyqueue(){ PSeqqueue paqu=(PSeqqueue)malloc(sizeof(struct Seqqueue)); if (paqu==NULL) { printf("Out of space.\n"); }else{ paqu->r=paqu->f=0; } return paqu; } ~~~ #### 1.3队列中插入元素 ~~~ void enqueue_seq(PSeqqueue paqu,DataType x){ if ((paqu->r+1)%MAXNUM==paqu->f) { printf("Full queue.\n"); }else{ paqu->q[paqu->r]=x; paqu->r=(paqu->r+1)%MAXNUM; } } ~~~ #### 1.4删除对头元素 ~~~ void dequeue_seq(PSeqqueue paqu){ if (isEmptyqueue_seq(paqu)) { printf("Empty queue\n"); }else{ paqu->f=(paqu->f+1)%MAXNUM; } } ~~~ #### 1.5返回对头元素 ~~~ DataType frontqueue_seq(PSeqqueue paqu){ return paqu->q[paqu->f]; } ~~~ #### 1.6判断队列是否为空. ~~~ int isEmptyqueue_seq(PSeqqueue paqu){ return paqu->f=paqu->r; } ~~~ #### 1.7测试 ~~~ int main(){ PSeqqueue queue=createEmptyqueue(); enqueue_seq(queue,2); enqueue_seq(queue,3); enqueue_seq(queue,4); printf("%d\n",frontqueue_seq(queue)); return 0; } ~~~ ###2.队列的链式表示 #### 2.1结构体定义和函数声明 ~~~ #include <stdio.h> #include <stdlib.h> typedef int Datatype; struct Node; typedef struct Node *PNode; struct Node { Datatype info; PNode link; }; struct LinkQueue { PNode f; PNode r; }; typedef struct LinkQueue *PLinkQueue; //创建一个空队列 PLinkQueue createEmptyQueue_link(); //判断队列是否为空 int isEmptyQueue_link(PLinkQueue plqu); //进队列 void enQueue_link(PLinkQueue plqu,Datatype x); //出对列 void deQueue_link(PLinkQueue plqu); //在非空队列中求对头元素 Datatype frontqueue_link(PLinkQueue plqu); ~~~ #### 2.2创建队列 ~~~ PLinkQueue createEmptyQueue_link(){ PLinkQueue plqu=(PLinkQueue)malloc(sizeof(struct LinkQueue)); if (plqu==NULL) { printf("Out of space.\n"); }else{ // PNode pnode=(PNode)malloc(sizeof(struct Node)); plqu->f=plqu->r=NULL; } return plqu; } ~~~ #### 2.3入队列 ~~~ void enQueue_link(PLinkQueue plqu,Datatype x){ PNode pnode=(PNode)malloc(sizeof(struct Node)); if(pnode==NULL){ printf("Out of space.\n"); }else{ pnode->info=x; pnode->link=NULL; if (plqu->f==NULL) { plqu->f=pnode; }else{ plqu->r->link=pnode; } plqu->r=pnode; } } ~~~ #### 2.4删除队尾元素 ~~~ void deQueue_link(PLinkQueue plqu){ PNode pnode; if (plqu->f==NULL) { printf("Empty Queue\n"); }else{ pnode=plqu->f; plqu->f=plqu->f->link; free(pnode); } } ~~~ #### 2.5返回对头元素 ~~~ Datatype frontqueue_link(PLinkQueue plqu){ printf("%d\n",plqu->f->info); return(plqu->f->info); } ~~~ #### 2.6队列是否为空 ~~~ int isEmptyQueue_link(PLinkQueue plqu){ return (plqu->f==NULL); } ~~~ #### 2.7测试 ~~~ int main(){ PLinkQueue p=createEmptyQueue_link(); enQueue_link(p,5); enQueue_link(p,15); enQueue_link(p,35); frontqueue_link(p); deQueue_link(p); frontqueue_link(p); return 0; } ~~~

### 顺序栈 #### 1.1顺序栈的定义 ~~~ /* 顺序栈基本操作 */ #include <stdio.h> #include <stdlib.h> //定义栈中最大元素的个数. #define MAXNUM 20 typedef int DataType; typedef struct SeqStack{ int t; //栈顶位置指示 DataType s[MAXNUM]; }SeqStack,*PSeqStack; //创建一个空栈;为栈结构申请空间.并将栈顶元素变量赋值为－1 PSeqStack createEmptyStack(void); //判断pastack所指的栈是否为空，当pastack所指的栈为空时返回1;否者为0. int isEmptyStack(PSeqStack pastack); //压栈操作 void push_seq(PSeqStack pastack,DataType e); //出栈操作 void pop_seq(PSeqStack pastack); //pastack不为空栈时，求栈顶元素 DataType getTop_seq(PSeqStack pastack); ~~~ #### 1.2 初始化栈 ~~~ PSeqStack createEmptyStack(){ PSeqStack pastack=(PSeqStack)malloc(sizeof(struct SeqStack)); if (pastack==NULL) { printf("Error:out of space\n"); }else{ pastack->t=-1; } return pastack; } ~~~ #### 1.3判断栈是否为空 ~~~ int isEmptyStack(PSeqStack pastack){ return pastack->t==-1; } ~~~ #### 1.4入栈操作 ~~~ void push_seq(PSeqStack pastack,DataType e){ if(pastack->t>=MAXNUM-1){ printf("Stack Overflow!\n"); }else{ pastack->t++; pastack->s[pastack->t]=e; } } ~~~ #### 1.5出栈操作 ~~~ void pop_seq(PSeqStack pastack){ if (pastack->t==-1) { printf("UnderFlow!\n"); }else{ printf("Pop:%d\n",pastack->s[pastack->t]); pastack->t--; } } ~~~ #### 1.6返回栈顶元素 ~~~ DataType getTop_seq(PSeqStack pastack){ return pastack->s[pastack->t]; } ~~~ #### 1.7测试 ~~~ int main(){ PSeqStack stack1=createEmptyStack(); push_seq(stack1,1); push_seq(stack1,2); push_seq(stack1,3); printf("%d\n",getTop_seq(stack1)); pop_seq(stack1); pop_seq(stack1); pop_seq(stack1); return 0; } ~~~ ### 链栈 #### 2.1链栈定义 ~~~ #include <stdio.h> #include <stdlib.h> typedef int DataType; struct Node; typedef struct Node *PNode; struct Node { DataType info; PNode link; }; struct LinkStack { PNode top; }; typedef struct LinkStack *PLinkStack; // 申请链栈结构空间，创建一个空链栈,返回指向空链接的指针. PLinkStack createEmptyStack_link(void); // 链式栈是否为空栈 int isEmptyStack_link(PLinkStack plstack); //入栈 void push(PLinkStack plstack, DataType e); //出栈 void pop(PLinkStack plstack); //对非空栈求栈顶元素 ~~~ #### 2.2初始化栈 ~~~ PLinkStack createEmptyStack_link(){ PLinkStack plstack=(PLinkStack)malloc(sizeof(struct LinkStack)); if (plstack==NULL) { printf("Out of space\n"); }else{ plstack->top=NULL; } return plstack; } ~~~ #### 2.3判断栈是否为空 ~~~ int isEmptyStack_link(PLinkStack plstack){ return plstack->top==NULL; } ~~~ #### 2.4入栈操作 ~~~ void push(PLinkStack plstack,DataType e){ PNode newnode=(PNode)malloc(sizeof(struct Node)); if(newnode==NULL){ printf("Out of space.\n"); }else{ newnode->info=e; newnode->link=plstack->top; plstack->top=newnode; } } ~~~ #### 2.5出栈操作 ~~~ void pop(PLinkStack plstack){ if (isEmptyStack_link(plstack)) { printf("Empty Stack pop.\n"); }else{ PNode p=plstack->top; printf("%d\n",p->info); plstack->top=plstack->top->link; free(p); } } ~~~ #### 2.6测试代码 ~~~ int main(){ PLinkStack plstack1=createEmptyStack_link(); push(plstack1,1); push(plstack1,3); push(plstack1,5); pop(plstack1); pop(plstack1); pop(plstack1); pop(plstack1); } ~~~

###1.数据在内存中的存储方式 数据在计算机程序中都是存储在内存空间中的. 1. 连续内存空间，比如申请一个数组，申请内存的大小事先知道。【数组】 1. 非连续内存空间，特点是申请次数无限制，每次固定大小。【链表】 ###2.时间复杂度和空间复杂度 - 时间复杂度：同一问题可用不同的算法解决，一个算法的质量优劣将影响算法乃至程序的效率。算法的时间复杂度是一个函数，定量描述算法的运行时间，通常用O表示. - 空间复杂度：一个算法在运行过程中占用存储空间大小的度量，包括算法本身所占的存储空间、数据输出数据所占用的存储空间的大学、运行过程中临时占用的存储空间的大小这三个方面。 ###3.衡量一个算法的优劣的标准 - **正确性**. 所写算法能满足具体问题的要求，对于任何合法的输入可以得出正确的结果。 - **可读性.** 晦涩难懂的算法不易于交流、推广、修改、拓展、维护，在写算法的时候，要尽量写的简明易懂。 - **健壮性.** 输入数据非法时，算法也会做出相应的判断，不会因为输入的错误造成程序瘫痪。 - **时间复杂度和空间复杂度.** 理想的算法应该是时间复杂度和空间复杂度都最佳。对于一个算法，时间复杂度和空间复杂度往往相互影响。 ###4.链表基本操作 ##### 4.1链表结构体定义 ~~~ #include <stdio.h> #include <stdlib.h> #include <MATH.h> typedef struct linklist { int data; struct linklist *next; //单链表 }linknode,*linklistp; ~~~ ##### 4.2.头部插入新节点 ~~~ //返回头部 linklistp insert_head(linklistp head,linklistp newnode){ newnode->next=head; head=newnode; return head; } ~~~ ##### 4.3. 尾部插入新节点 ~~~ linklistp insert_tail(linklistp head,linklistp newnode){ if(head==NULL){ head=newnode; }else{ linklistp temp=head; while(temp->next!=NULL){ temp=temp->next; } newnode->next=temp->next; temp->next=newnode; } return head; } ~~~ ##### 4.4 删除子节点 ~~~ //删除节点 linklistp list_delete(linklistp head,int a){ linklistp temp=head; //1.temp为空，返回NULL if(temp==NULL){ printf("链表为空\n"); return NULL; } //2.正好是首节点 if(temp->data==a){ head=head->next; free(temp); return head; } //3.不在首节点 linklistp prev=head; temp=head->next; while(temp!=NULL&&temp->data!=a){ prev=temp; temp=temp->next; } //3.1 没找到 if(temp==NULL){ printf("不存在\n"); return NULL; } prev->next=temp->next; return head; } ~~~ ##### 4.5查找节点 ~~~ //查找第i个元素 int getElem(linklistp head,int i,int a){ if (head->next==NULL) { printf("link list is NULL"); return 0; } linklistp temp=head; int j=0; while(temp->next&&j<i){ temp=temp->next; ++j; } if(!temp||j>i){ printf(" 不存在第i个元素\n"); } a=temp->data; return a; } ~~~ ##### 4.6 判断链表是否为空 ~~~ //判断链表是否为空 _Bool isEmpty(linklistp head){ if (head->next==NULL) { printf("链表为空\n"); return 1; } return 0; } ~~~ #####4.7遍历链表 ~~~ void output(linklistp head){ linklistp temp=head; while(temp){ printf("%d\t", temp->data); temp=temp->next; } printf("\n"); } ~~~ ##### 4.8 测试代码 ~~~ int main(){ linklistp head=NULL; for (int i = 0; i < 10; ++i) { /* code */ linklistp newnode=(linklistp)malloc(sizeof(linknode)); newnode->data=i*10+2; newnode->next=NULL; head=insert_head(head,newnode); } output(head); printf("*********删除节点*******\n"); int data=0; printf("请输入要删除的数据：\n"); scanf("%d",&data); linklistp temp=list_delete(head,data); if (temp==NULL) { printf("def failture or not has this node"); }else{ head=temp; output(head); } printf("**************************\n"); printf("enter the num you want to find:\n"); printf("%d\n",getElem(head,2,data)); return 0; } ~~~ 

> 原文出处：[数据结构与算法](http://blog.csdn.net/column/details/algorithmpp.html) 作者：[napoay](http://blog.csdn.net/napoay) **本系列文章经作者授权在看云整理发布，未经作者允许，请勿转载！** # 数据结构与算法 > 本专栏主要发布与数据结构、算法相关的博客。