算法导论复习:第八章和第九章 原

fzyz_sb

1. 计数排序

``````#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define SIZE 100

void countingSort( int *A, int *B, int k, int len );

int main( void )
{
int		A[ SIZE ];
int		B[ SIZE ];
int		k = 0;
int		i = 0;
memset( B, 0, sizeof( int ) * SIZE );
k = SIZE - 5;
srand( ( unsigned int )time( NULL ) );
for ( i = 0; i < SIZE; i++ ){
A[ i ] = rand() % k;
}

printf("the array is:\n");
for ( i = 0; i < SIZE; i++ ){
printf("%d ", A[ i ] );
if ( 0 == ( i + 1 ) % 10 ){
printf("\n");
}
}

countingSort( A, B, k, SIZE );

printf("\nafter sort,the array is:\n");
for ( i = 0; i < SIZE; i++ ){
printf("%d ", B[ i ] );
if ( 0 == ( i + 1 ) % 10 ){
printf("\n");
}
}
printf("\n");

return 0;
}

void countingSort( int *A, int *B, int k, int len )
{
int		*C = ( int * )malloc( sizeof( int ) * k );
int		i = 0;
memset( C, 0, sizeof( int ) * k );

for ( i = 0; i < len; i++ ){
C[ A[ i ] ] += 1;
}
for ( i = 1; i < k; i++ ){
C[ i ] += C[ i - 1 ];
}
for ( i = 0; i < k; i++ ){
C[ i ] -= 1;		//下标从0开始,否则B会存在下标越界情况
}

for ( i = len - 1; i >= 0; i-- ){
B[ C[ A[ i ] ] ] = A[ i ];
C[ A[ i ] ] -= 1;
}
free( C );
}``````

2. 基数排序

``````#include <stdio.h>

void radixSort( char *A[], int len, int keyLen );
int main( void )
{
int		i = 0;
char		*A[] = { "COW", "DOG", "SEA", "RUG", "ROW", "MOB", "BOX", "TAB", "BAR", "EAR", "TAR", "DIG", "BIG", "TEA", "NOW", "FOX" };
int		len = sizeof( A ) / sizeof( *A );
int		keyLen = 3;		//每个单词的长度,这里不考虑长度不同的情况,只是为了更好的说明基数排序

for ( i = 0; i < len; i++ ){
printf("%s ", A[ i ] );
if ( 0 == ( i + 1 ) % 5 ){
printf("\n");
}
}
printf("\n");

return 0;
}

void radixSort( char *A[], int len, int keyLen )
{
int		i = 0;
int		j = 0;
int		k = 0;
for ( i = keyLen - 1; i >= 0; i-- ){
//插入排序
for ( j = 1; j < len; j++ ){
char		keyValue = A[ j ][ i ];
char		*key = A[ j ];
k = j - 1;
while ( k >= 0 && A[ k ][ i ] > keyValue ){
A[ k + 1 ] = A[ k ];
k -= 1;
}
A[ k + 1 ] = key;
}
}
}``````

3. 桶排序

``````#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <limits.h>

#define SIZE 100
#define LENBUCKET		10

typedef struct NODE{
int						data;
}Node;

void bucketSort( int *A, int len );
void insertNode( Node *node, int value );

int main( void )
{
int		A[ SIZE ];
int		i = 0;
srand( ( unsigned int )time( NULL ) );
for ( i = 0; i < SIZE; i++ ){
A[ i ] = rand() % SIZE;
}

printf("the array is:\n");
for ( i = 0; i < SIZE; i++ ){
printf("%3d ", A[ i ] );
if ( 0 == ( i + 1 ) % 10 ){
printf("\n");
}
}

bucketSort( A, SIZE );

printf("after sort, the array is:\n");
for ( i = 0; i < SIZE; i++ ){
printf("%3d ", A[ i ] );
if ( 0 == ( i + 1 ) % 10 ){
printf("\n");
}
}
printf("\n");

return 0;
}

void bucketSort( int *A, int len )
{
Node		*B[ LENBUCKET ];
int			i = 0;
int			j = 0;
for ( i = 0; i < LENBUCKET; i++ ){
Node *node = ( Node * )malloc( sizeof( Node ) );
node->data = INT_MIN;
B[ i ] = node;
}
for ( i = 0; i < len; i++ ){
int			index = A[ i ] / ( SIZE / LENBUCKET );
insertNode( B[ index ], A[ i ] );
}

for ( i = 0, j = 0; j < LENBUCKET; j++ ){
Node *node = ( Node * )malloc( sizeof( Node ) );
while ( NULL != node ){
A[ i++ ] = node->data;
}
}
}

void insertNode( Node *node, int value )
{
Node *tempNode = ( Node * )malloc( sizeof( Node ) );
tempNode->data = value;
//为空结点
if ( NULL == node->link ){
}
else{
//插入头部
if ( value <= node->link->data ){
}
else{
Node *prevNode = ( Node * )malloc( sizeof( Node ) );
while ( NULL != node && value > node->data ){
prevNode = node;
}
}
}
}``````

2. 对于链表的插入,初始化一个头节点专门用来标识这个链表是良好的设计方法,毕竟C语言只支持传值不支持传址(没有C++中引用).

4. 同时查找最小值和最大值

``````#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE	100

void searchMinMax( int *A, int *minValue, int *maxValue, int len );

int main( void )
{
int		A[ SIZE ];
int		i = 0;
int		minValue = 0;
int		maxValue = 0;
srand( ( unsigned int )time( NULL ) );
for ( i = 0; i < SIZE; i++ ){
A[ i ] = rand() % SIZE;
}

searchMinMax( A, &minValue, &maxValue, SIZE );

printf("the array is:\n");
for ( i = 0; i < SIZE; i++ ){
printf("%3d ", A[ i ] );
if ( 0 == ( i + 1 ) % 10 ){
printf("\n");
}
}

printf("\nthe min value is: %3d\nthe max value is:%3d\n", minValue, maxValue );

return 0;
}

void searchMinMax( int *A, int *minValue, int *maxValue, int len )
{
int		i = 0;
if ( 0 == len % 2 ){
*minValue = A[ 0 ] < A[ 1 ] ? A[ 0 ] : A[ 1 ];
*maxValue = A[ 0 ] > A[ 1 ] ? A[ 0 ] : A[ 1 ];
}
else{
*minValue = *maxValue = A[ 0 ];
}

for ( i = 2; i < len; i += 2 ){
if ( A[ i ] < A[ i + 1 ] ){
if ( *minValue > A[ i ] ){
*minValue = A[ i ];
}
if ( *maxValue < A[ i + 1 ] ){
*maxValue = A[ i + 1 ];
}
}
else{
if ( *minValue > A[ i + 1 ] ){
*minValue = A[ i + 1 ];
}
if ( *maxValue < A[ i ] ){
*maxValue = A[ i ];
}
}
}
}``````

fzyz_sb

Kali Linux 秘籍 原书：Kali Linux Cookbook 译者：飞龙 在线阅读 PDF格式 EPUB格式 MOBI格式 Github Git@OSC 目录： 第一章 安装和启动Kali 第二章 定制 Kali Linux 第三章 高级测试环境 第...

wizardforcel0
07/02
0
0
javascript入门经典【推荐】—新手必备、零基础学习

a125138
2012/08/01
0
0
MyBatis3.2.x从入门到精通系列

Java框架篇---Mybatis 入门 MyBatis3.2.x从入门到精通之第一章 MyBatis3.2.x从入门到精通之第二章 MyBatis3.2.x从入门到精通之第三章 MyBatis3.2.x从入门到精通之第四章 MyBatis3.2.x从入门到...

HenrySun
2016/10/07
54
0
13篇文章，教你学会ES6知识点

ES6 深入理解ES6》学习笔记 本文用于汇总链接到各个子章节的内容，github 欢迎大家题issues和PR，如果对你有帮助，也可以给 star 支持 :) 目录 第一章 块级绑定 第二章 字符串和正则表达式 ...

05/08
0
0
【原创】《深入剖析Tomcat》读书笔记

pandudu
2015/12/22
46
0

Spring详解

Spring详解（一）------概述 目录 1、什么是 Spring ? 2、Spring 起源 3、Spring 特点 4、Spring 框架结构 5、Spring 框架特征 6、Spring 优点 　　本系列教程我们将对 Spring 进行详解的介绍...

DemonsI
25分钟前
0
0
CentOS7系统Nginx安装

m_lm
28分钟前
0
0

1：treeNode.checked用于判断是勾选还是取消勾选。（treeNode指的是节点） 2：treeObj.transformToArray(nodes)用于查询nodes节点下的所有子节点，json格式。（treeObj为数的id）...

uug
29分钟前
0
0
export, import 和 export default的区别

ES6的两个功能： export 和 import export 对外输出模块 import 引入（加载）进来一个模块 一、export => import 单个变量 export var name = "lishi" 在其他文件里引用 import {name} f...

Js_Mei
33分钟前
1
0

WelliJohn
42分钟前
1
1