算法导论的笔记,其实不算笔记,因为我比较懒,懒的写什么文字的笔记,书上的题目有很多是数学型的,计算型的,基本上都做了下,不过只是在稿纸上算的,懒得打字敲上来了,下面只是那些涉及到的算法,用C实现的代码
------------------------------------------------------------------------------------------------------
// chapt2.cpp : Defines the entry point for the console application.
//
//
/*************************************************************
** CLRS Introduction to Algorithm(2nd) chapter 2
** study notes
** by lzp<bluefeynman@gmail.com>
** 2007-10
**************************************************************/
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include <time.h>
** CLRS Introduction to Algorithm(2nd) chapter 2
** study notes
** by lzp<bluefeynman@gmail.com>
** 2007-10
**************************************************************/
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include <time.h>
/*插入排序，按照升序*/
void InsertionSortAscend(int *array,int len)
{
int i,j;
int key;
for(i=1;i<len;i++)
{
key=array;
j=i-1;
while(j>=0&&array[j]>key)
{
array[j+1]=array[j];
j--;
}
array[j+1]=key;
}
}
void InsertionSortAscend(int *array,int len)
{
int i,j;
int key;
for(i=1;i<len;i++)
{
key=array;
j=i-1;
while(j>=0&&array[j]>key)
{
array[j+1]=array[j];
j--;
}
array[j+1]=key;
}
}
/*插入排序，按照降序*/
void InsertionSortDescend(int * array, int len)
{
int i,j;
int key;
for(i=1;i<len;i++)
{
key=array;
j=i-1;
while(j>=0&&array[j]<key)
{
array[j+1]=array[j];
j--;
}
array[j+1]=key;
}
}
//选择排序，按照升序
void SelectionSortAscend(int *array,int len)
{
int key,i,j,tmp,index;
for(i=0;i<len-1;i++)
{
key=array;
index=i;
for(j=i+1;j<len;j++)
{
if(key>array[j])
{
key=array[j];
index=j;
}
}
tmp=array;
array=key;
array[index]=tmp;
}
}
void InsertionSortDescend(int * array, int len)
{
int i,j;
int key;
for(i=1;i<len;i++)
{
key=array;
j=i-1;
while(j>=0&&array[j]<key)
{
array[j+1]=array[j];
j--;
}
array[j+1]=key;
}
}
//选择排序，按照升序
void SelectionSortAscend(int *array,int len)
{
int key,i,j,tmp,index;
for(i=0;i<len-1;i++)
{
key=array;
index=i;
for(j=i+1;j<len;j++)
{
if(key>array[j])
{
key=array[j];
index=j;
}
}
tmp=array;
array=key;
array[index]=tmp;
}
}
/**********************************
**合并排序，按照升序
**这是一个递归实现，时间复杂度O(nlogn)
**其中Merge(...)是个辅助函数，用来将
**两个已经排好序的数组合并成一个大的排好序
**的数组
**Merge(..)参数含义：
array---待排序的数组，但是其中array[p..q]和
array[q+1..r]是已经排好的两个子数组
************************************/
bool Merge(int *array,int p,int q,int r)
{
int i,j,k;
int len1=q-p+1;
int len2=r-q;
int *left,*right;
if((left=(int*)malloc(sizeof(int)*len1))==NULL)
return false;
if((right=(int *)malloc(sizeof(int)*len2))==NULL)
{
free(left);
return false;
}
for(i=0;i<len1;i++)
{
left=array[p+i];
}
for(j=0;j<len2;j++)
{
right[j]=array[q+1+j];
}
for(i=0,j=0,k=p;i<len1&&j<len2;k++)
{
if(left<right[j])
{
array[k]=left;
i++;
}
else
{
array[k]=right[j];
j++;
}
}
for(;i<len1;i++,k++)
{
array[k]=left;
}
for(;j<len2;j++,k++)
{
array[k]=right[j];
}
free(left);
free(right);
return true;
}
**合并排序，按照升序
**这是一个递归实现，时间复杂度O(nlogn)
**其中Merge(...)是个辅助函数，用来将
**两个已经排好序的数组合并成一个大的排好序
**的数组
**Merge(..)参数含义：
array---待排序的数组，但是其中array[p..q]和
array[q+1..r]是已经排好的两个子数组
************************************/
bool Merge(int *array,int p,int q,int r)
{
int i,j,k;
int len1=q-p+1;
int len2=r-q;
int *left,*right;
if((left=(int*)malloc(sizeof(int)*len1))==NULL)
return false;
if((right=(int *)malloc(sizeof(int)*len2))==NULL)
{
free(left);
return false;
}
for(i=0;i<len1;i++)
{
left=array[p+i];
}
for(j=0;j<len2;j++)
{
right[j]=array[q+1+j];
}
for(i=0,j=0,k=p;i<len1&&j<len2;k++)
{
if(left<right[j])
{
array[k]=left;
i++;
}
else
{
array[k]=right[j];
j++;
}
}
for(;i<len1;i++,k++)
{
array[k]=left;
}
for(;j<len2;j++,k++)
{
array[k]=right[j];
}
free(left);
free(right);
return true;
}
bool MergeSortAscend(int *array, int p,int r)
{
int q;
if(p<r)
{
q=(p+r)/2;
if(!MergeSortAscend(array,p,q))
return false;
if(!MergeSortAscend(array,q+1,r))
return false;
if(!Merge(array,p,q,r))
return false;
}
return true;
}
{
int q;
if(p<r)
{
q=(p+r)/2;
if(!MergeSortAscend(array,p,q))
return false;
if(!MergeSortAscend(array,q+1,r))
return false;
if(!Merge(array,p,q,r))
return false;
}
return true;
}
/******************************************
**
**二分查找
** arguments:
*** array---a sorted array
*** len---the length of array
*** x--- the number we want to search in array
**return:
** -1---x No exist in array
** others--the index(position) of x in array
********************************************/
int BinarySearch(int *array,int len,int x)
{
int pos="len/2";
int left="0";
int right="len-1";
**
**二分查找
** arguments:
*** array---a sorted array
*** len---the length of array
*** x--- the number we want to search in array
**return:
** -1---x No exist in array
** others--the index(position) of x in array
********************************************/
int BinarySearch(int *array,int len,int x)
{
int pos="len/2";
int left="0";
int right="len-1";
while(1)
{
if(x>array[pos])
{
if(pos==left)
return -1;
left=pos;
pos=(pos+right)/2;
}
else if(x<array[pos])
{
if(right==pos)
return -1;
right=pos;
pos=(pos+left)/2;
}
else
return pos;
}
return -1;
}
{
if(x>array[pos])
{
if(pos==left)
return -1;
left=pos;
pos=(pos+right)/2;
}
else if(x<array[pos])
{
if(right==pos)
return -1;
right=pos;
pos=(pos+left)/2;
}
else
return pos;
}
return -1;
}
//递归实现
int BinarySearchIter(int *array,int x,int p, int r)
{
int j;
if((p>=r-1)&&(array[r]!=x)&&(array
int BinarySearchIter(int *array,int x,int p, int r)
{
int j;
if((p>=r-1)&&(array[r]!=x)&&(array
!=x))
return -1;
j=(r+p)/2;
if(x<array[j])
return BinarySearchIter(array,x,p,j);
else if(x>array[j])
return BinarySearchIter(array,x,j,r);
else
return j;
}
/******************************************************************
**2.3-7这个题目:请给出一个运行时间为O(nlgn)的算法,使之能在给定的一个由n个整数构成的
**集合S和另一个整数x时,判断出S中是否存在有两个其和等于x的元素
*******************************************************************/
/******************************************************************
**答案如下
懒,没写具体代码)
懒,没写具体代码)**先用合并排序法把S排序,这个步骤是O(nlgn)的
**再for(i=0;i<n;i++)
** a="x-S";
**对a用二分查找看S中存在与否,这个步骤是lgn的,因为for(i=0;i<n;i++)要循环n次
**所以整个是O(nlgn)的
**这样算法整体上是O(nlgn)的
*******************************************************************/
int main(int argc, char* argv[])
{
//test InsertionSortAscend
int a[100];
int i;
srand( (unsigned)time( NULL ) );
int main(int argc, char* argv[])
{
//test InsertionSortAscend
int a[100];
int i;
srand( (unsigned)time( NULL ) );
for(i=0;i<100;i++)
{
a=rand();
}
printf("before sort, array is:\n");
for(i=0;i<100;i++)
{
printf("%d\t",a);
}
printf("\n");
InsertionSortAscend(a,100);
printf("after InertionSortAscend, array is:\n");
for(i=0;i<100;i++)
{
printf("%d\t",a);
}
printf("\n");
//test InsertionSortDescend
InsertionSortDescend(a,100);
printf("after InertionSortDescend, array is:\n");
for(i=0;i<100;i++)
{
printf("%d\t",a);
}
printf("\n");
//test SelectionSortAscend
SelectionSortAscend(a,100);
printf("after SelectionSortAscend, array is:\n");
for(i=0;i<100;i++)
{
printf("%d\t",a);
}
printf("\n");
{
a=rand();
}
printf("before sort, array is:\n");
for(i=0;i<100;i++)
{
printf("%d\t",a);
}
printf("\n");
InsertionSortAscend(a,100);
printf("after InertionSortAscend, array is:\n");
for(i=0;i<100;i++)
{
printf("%d\t",a);
}
printf("\n");
//test InsertionSortDescend
InsertionSortDescend(a,100);
printf("after InertionSortDescend, array is:\n");
for(i=0;i<100;i++)
{
printf("%d\t",a);
}
printf("\n");
//test SelectionSortAscend
SelectionSortAscend(a,100);
printf("after SelectionSortAscend, array is:\n");
for(i=0;i<100;i++)
{
printf("%d\t",a);
}
printf("\n");
//test MergeSortAscend
srand( (unsigned)time( NULL ) );
srand( (unsigned)time( NULL ) );
for(i=0;i<100;i++)
{
a=rand();
}
printf("before sort, array is:\n");
for(i=0;i<100;i++)
{
printf("%d\t",a);
}
printf("\n");
if(!MergeSortAscend(a,0,99))
{
printf("MergeSortAscend error\n");
return 1;
}
printf("after MergeSortAscend, array is:\n");
for(i=0;i<100;i++)
{
printf("%d\t",a);
}
printf("\n");
//test BinarySearch
int x;
for(x=0;x<10000;x++)
{
i=BinarySearch(a,100,x);
switch(i)
{
case -1:
// printf("%d don't find in array\n",x);
break;
default:
printf("find %d in array's position :%d\n",x,i);
break;
}
}
printf("test BinarySearchIter\n");
for(x=0;x<10000;x++)
{
i=BinarySearchIter(a,x,0,99);
switch(i)
{
case -1:
//printf("%d don't find in array\n",x);
break;
default:
printf("find %d in array's position :%d\n",x,i);
break;
}
}
return 0;
}
{
a=rand();
}
printf("before sort, array is:\n");
for(i=0;i<100;i++)
{
printf("%d\t",a);
}
printf("\n");
if(!MergeSortAscend(a,0,99))
{
printf("MergeSortAscend error\n");
return 1;
}
printf("after MergeSortAscend, array is:\n");
for(i=0;i<100;i++)
{
printf("%d\t",a);
}
printf("\n");
//test BinarySearch
int x;
for(x=0;x<10000;x++)
{
i=BinarySearch(a,100,x);
switch(i)
{
case -1:
// printf("%d don't find in array\n",x);
break;
default:
printf("find %d in array's position :%d\n",x,i);
break;
}
}
printf("test BinarySearchIter\n");
for(x=0;x<10000;x++)
{
i=BinarySearchIter(a,x,0,99);
switch(i)
{
case -1:
//printf("%d don't find in array\n",x);
break;
default:
printf("find %d in array's position :%d\n",x,i);
break;
}
}
return 0;
}
- 上一篇： HD7279 C51程序
- 下一篇： 数据结构第4章习题参考答案
EE直播间
更多
-
提升毫米波信号测试精度 直播时间： 12月18日 14:00 -
EE Talk主题专访系列直播-对话：释放 Wi-Fi 7 在高带宽应用中的技术潜力 直播时间： 12月19日 10:00
关闭
站长推荐
/2 
/2
文章评论（0条评论）
登录后参与讨论