opencvHOG算法注释

#include "_cvaux.h"

/****************************************************************************** ***********

struct CV_EXPORTS HOGDescriptor

{

public:

enum { L2Hys=0 };

HOGDescriptor() : winSize(64,128), blockSize(16,16), blockStride(8,8),

cellSize(8,8), nbins(9), derivAperture(1), winSigma(-1),

histogramNormType(L2Hys), L2HysThreshold(0.2), gammaCorrection(true)

{}

HOGDescriptor(Size _winSize, Size _blockSize, Size _blockStride,

Size _cellSize, int _nbins, int _derivAperture=1, double _winSigma=-1,

int _histogramNormType=L2Hys, double _L2HysThreshold=0.2, bool _gammaCorrection=false) : winSize(_winSize), blockSize(_blockSize), blockStride(_blockStride), cellSize(_cellSize), nbins(_nbins), derivAperture(_derivAperture), winSigma(_winSigma), histogramNormType(_histogramNormType), L2HysThreshold(_L2HysThreshold), gammaCorrection(_gammaCorrection)

{}

HOGDescriptor(const String& filename)

{

load(filename);

}

virtual ~HOGDescriptor() {}

size_t getDescriptorSize() const;

bool checkDetectorSize() const;

double getWinSigma() const;

virtual void setSVMDetector(const vector& _svmdetector);

virtual bool load(const String& filename, const String& objname=String());

virtual void save(const String& filename, const String& objname=String()) const;

virtual void compute(const Mat& img,

vector& descriptors,

Size winStride=Size(), Size padding=Size(),

const vector& locations=vector()) const;

virtual void detect(const Mat& img, vector& foundLocations,

double hitThreshold=0, Size winStride=Size(),

Size padding=Size(),

const vector& searchLocations=vector()) const;

virtual void detectMultiScale(const Mat& img, vector& foundLocations,

double hitThreshold=0, Size winStride=Size(),

Size padding=Size(), double scale=1.05,

int groupThreshold=2) const;

//Mat& angleOfs,与后文Mat& qangle不一致，怀疑是笔误，由于qangle与angleOfs有不同含义，尽量改过来

virtual void computeGradient(const Mat& img, Mat& grad, Mat& angleOfs,

Size paddingTL=Size(), Size paddingBR=Size()) const;

static vector getDefaultPeopleDetector();

Size winSize;//窗口大小

Size blockSize;//Block大小

Size blockStride;//block每次移动宽度包括水平和垂直两个方向

Size cellSize;//Cell单元大小

int nbins;//直方图bin数目

int derivAperture;//不知道什么用

double winSigma;//高斯函数的方差

int histogramNormType;//直方图归一化类型，具体见论文

double L2HysThreshold;//L2Hys化中限制最大值为0.2

bool gammaCorrection;//是否Gamma校正

vector svmDetector;//检测算子

};

******************************************************************************* ***/

namespace cv

{

size_t HOGDescriptor::getDescriptorSize() const

{

//检测数据的合理性

CV_Assert(blockSize.width % cellSize.width == 0 &&

blockSize.height % cellSize.height == 0);

CV_Assert((winSize.width - blockSize.width) % blockStride.width == 0 &&

(winSize.height - blockSize.height) % blockStride.height == 0 );

//Descriptor的大小

return (size_t)nbins*

(blockSize.width/cellSize.width)*

(blockSize.height/cellSize.height)*

((winSize.width - blockSize.width)/blockStride.width + 1)*

((winSize.height - blockSize.height)/blockStride.height + 1);

//9*(16/8)*(16/8)*((64-16)/8+1)*((128-16)/8+1)=9*2*2*7*15=3780，实际上的检测算子为3781，多的1表示偏置

}

double HOGDescriptor::getWinSigma() const

{

//winSigma默认为-1,然而有下式知，实际上为4；否则自己选择参数

return winSigma >= 0 ? winSigma : (blockSize.width + blockSize.height)/8.;

}

bool HOGDescriptor::checkDetectorSize() const

{

//size_t:unsigned int

size_t detectorSize = svmDetector.size(), descriptorSize = getDescriptorSize();

//三种情况任意一种为true则表达式为true，实际上是最后一种

return detectorSize == 0 ||

detectorSize == descriptorSize ||

detectorSize == descriptorSize + 1;

}

void HOGDescriptor::setSVMDetector(const vector& _svmDetector)

{

svmDetector = _svmDetector;

CV_Assert( checkDetectorSize() );

}

bool HOGDescriptor::load(const String& filename, const String& objname)

{

//XML/YML文件存储

FileStorage fs(filename, FileStorage::READ);

//objname为空，！1=0，选择fs.getFirstTopLevelNode();否则为fs[objname]

//注意到FileStorage中[]重载了：FileNode operator[](const string& nodename)（returns the top-level node by name ）

FileNode obj = !objname.empty() ? fs[objname] : fs.getFirstTopLevelNode();

if( !obj.isMap() )

return false;

FileNodeIterator it = obj["winSize"].begin();

it >> winSize.width >> winSize.height;

it = obj["blockSize"].begin();

it >> blockSize.width >> blockSize.height;

it = obj["blockStride"].begin();

it >> blockStride.width >> blockStride.height;

it = obj["cellSize"].begin();

it >> cellSize.width >> cellSize.height;

obj["nbins"] >> nbins;

obj["derivAperture"] >> derivAperture;

obj["winSigma"] >> winSigma;

obj["histogramNormType"] >> histogramNormType;

obj["L2HysThreshold"] >> L2HysThreshold;

obj["gammaCorrection"] >> gammaCorrection;

FileNode vecNode = obj["SVMDetector"];

if( vecNode.isSeq() )

{

vecNode >> svmDetector;

CV_Assert(checkDetectorSize());

}

return true;

}

void HOGDescriptor::save(const String& filename, const String& objName) const

{

FileStorage fs(filename, FileStorage::WRITE);

//空的对象名则取默认名，输出有一定格式，对象名后紧接{

fs << (!objName.empty() ? objName : FileStorage::getDefaultObjectName(filename)) << "{";

//之后依次为：

fs << "winSize" << winSize

<< "blockSize" << blockSize

<< "blockStride" << blockStride

<< "cellSize" << cellSize

<< "nbins" << nbins

<< "derivAperture" << derivAperture

<< "winSigma" << getWinSigma()

<< "histogramNormType" << histogramNormType

<< "L2HysThreshold" << L2HysThreshold

<< "gammaCorrection" << gammaCorrection;

if( !svmDetector.empty() )

fs << "SVMDetector" << "[:" << svmDetector << "]";

//注意还要输出"}"

fs << "}";

}

//img:原始图像

//grad:记录每个像素所属bin对应的权重的矩阵,为幅值乘以权值

//这个权值是关键，也很复杂：包括高斯权重，三次插值的权重，在本函数中先值考虑幅值和相邻bin间的插值权重

//qangle:记录每个像素角度所属的bin序号的矩阵,均为2通道,为了线性插值

//paddingTL:Top和Left扩充像素数

//paddingBR:类似同上

//功能：计算img经扩张后的图像中每个像素的梯度和角度

void HOGDescriptor::computeGradient(const Mat& img, Mat& grad, Mat& qangle,

Size paddingTL, Size paddingBR) const

{

//先判断是否为单通道的灰度或者3通道的图像

CV_Assert( img.type() == CV_8U || img.type() == CV_8UC3 );

//计算gradient的图的大小,由64*128==》112*160，则会产生5*7=35个窗口（windowstride:8）//每个窗口105个block,105*36=3780维特征向量

//paddingTL.width=16,paddingTL.height=24

Size gradsize(img.cols + paddingTL.width + paddingBR.width,

img.rows + paddingTL.height + paddingBR.height);

//注意grad和qangle是2通道的矩阵，为3D-trilinear插值中的orientation维度，另两维为坐标x与y

grad.create(gradsize, CV_32FC2); //

qangle.create(gradsize, CV_8UC2); // [0..nbins-1] - quantized gradient orientation

//wholeSize为parent matrix大小，不是扩展后gradsize的大小

//roiofs即为img在parent matrix中的偏置

//对于正样本img=parent matrix;但对于负样本img是从parent img中抽取的10个随机位置//至于OpenCv具体是怎么操作，使得img和parent img相联系，不是很了解

//wholeSize与roiofs仅在padding时有用，可以不管，就认为传入的img==parent img，是否是从parent img中取出无所谓

Size wholeSize;

Point roiofs;

img.locateROI(wholeSize, roiofs);

int i, x, y;

int cn = img.channels();

//产生1行256列的向量，lut为列向量头地址

Mat_ _lut(1, 256);

const float* lut = &_lut(0,0);

//gamma校正，作者的编程思路很有意思

//初看不知道这怎么会与图像的gamma校正有关系，压根img都没出现，看到后面大家会豁然开朗的

if( gammaCorrection )

for( i = 0; i < 256; i++ )

_lut(0,i) = std::sqrt((float)i);

else

for( i = 0; i < 256; i++ )

_lut(0,i) = (float)i;

//开辟空间存xmap和ymap，其中各占gradsize.width+2和gradsize.height+2空间

//+2是为了计算dx,dy时用[-1,0,1]算子,即使在扩充图像中，其边缘计算梯度时还是要再额外加一个像素的

//作者很喜欢直接用内存地址及之间的关系，初看是有点头大的

//另外再说说xmap与ymap的作用：其引入是因为img图像需要扩充到gradsize大小

//如果我们计算img中位于（-5，-6）像素时，需要将基于img的(-5,-6)坐标，映射为基于grad和qangle的坐标(xmap,ymap)

AutoBuffer mapbuf(gradsize.width + gradsize.height + 4);

int* xmap = (int*)mapbuf + 1;

int* ymap = xmap + gradsize.width + 2;

// BORDER_REFLECT_101:(左插值)gfedcb|abcdefgh(原始像素)|gfedcba(右插值),一种插值模式 const int borderType = (int)BORDER_REFLECT_101;

//borderInterpolate函数完成两项操作，一是利用插值扩充img，二是返回x-paddingTL.width+roiofs.x映射后的坐标xmap

//例如，ximg=x(取0)-paddingTL.width(取24)+roiofs.x(取0)=-24 ==>xmap[0]=0

//即img中x=-24,映射到grad中xmap=0,并且存在xmap[0]中,至于borderInterpolate的具体操作可以不必细究

for( x = -1; x < gradsize.width + 1; x++ )

xmap[x] = borderInterpolate(x - paddingTL.width + roiofs.x,

wholeSize.width, borderType);

for( y = -1; y < gradsize.height + 1; y++ )

ymap[y] = borderInterpolate(y - paddingTL.height + roiofs.y,

wholeSize.height, borderType);

// x- & y- derivatives for the whole row

// 由于后面的循环是以行为单位，每次循环内存重复使用，所以只要记录一行的信息而不是整个矩阵

int width = gradsize.width;

AutoBuffer _dbuf(width*4);

float* dbuf = _dbuf;

//注意到内存的连续性方便之后的编程

Mat Dx(1, width, CV_32F, dbuf);

Mat Dy(1, width, CV_32F, dbuf + width);

Mat Mag(1, width, CV_32F, dbuf + width*2);

Mat Angle(1, width, CV_32F, dbuf + width*3);

int _nbins = nbins;

float angleScale = (float)(_nbins/CV_PI);//9/pi

for( y = 0; y < gradsize.height; y++ )

{

//指向每行的第一个元素,img.data为矩阵的第一个元素地址

const uchar* imgPtr = img.data + img.step*ymap[y];

const uchar* prevPtr = img.data + img.step*ymap[y-1];

const uchar* nextPtr = img.data + img.step*ymap[y+1];

float* gradPtr = (float*)grad.ptr(y);

uchar* qanglePtr = (uchar*)qangle.ptr(y);

//1通道

if( cn == 1 )

{

for( x = 0; x < width; x++ )

{

int x1 = xmap[x];

//imgPtr指向img第y行首元素，imgPtr[x]即表示第(x,y)像素，其亮度值位于0~255，对应lut[0]~lut[255]

//即若像素亮度为120，则对应lut[120]，若有gamma校正，lut[120]=sqrt(120)

//由于补充了虚拟像素，即在imgPtr[-1]无法表示gradsize中-1位置元素，而需要有个转换//imgPtr[-1-paddingTL.width+roiofs.x],即imgPtr[xmap[-1]]，即gradsize中-1位置元素为img 中xmap[-1]位置的元素

dbuf[x] = (float)(lut[imgPtr[xmap[x+1]]] - lut[imgPtr[xmap[x-1]]]);

//由于内存的连续性，隔width,即存Dy

dbuf[width + x] = (float)(lut[nextPtr[x1]] - lut[prevPtr[x1]]);

}

}

else

//3通道,3通道中取最大值

{

for( x = 0; x < width; x++ )

{

int x1 = xmap[x]*3;

const uchar* p2 = imgPtr + xmap[x+1]*3;

const uchar* p0 = imgPtr + xmap[x-1]*3;

float dx0, dy0, dx, dy, mag0, mag;

dx0 = lut[p2[2]] - lut[p0[2]];

dy0 = lut[nextPtr[x1+2]] - lut[prevPtr[x1+2]];

mag0 = dx0*dx0 + dy0*dy0;

dx = lut[p2[1]] - lut[p0[1]];

dy = lut[nextPtr[x1+1]] - lut[prevPtr[x1+1]];

mag = dx*dx + dy*dy;

if( mag0 < mag )

{

dx0 = dx;

dy0 = dy;

mag0 = mag;

}

dx = lut[p2[0]] - lut[p0[0]];

dy = lut[nextPtr[x1]] - lut[prevPtr[x1]];

mag = dx*dx + dy*dy;

if( mag0 < mag )

{

dx0 = dx;

dy0 = dy;

mag0 = mag;

}

dbuf[x] = dx0;

dbuf[x+width] = dy0;

}

}

//函数cvCartToPolar 计算二维向量(x(I),y(I))的长度，角度:

//magnitude(I) = sqrt(x(I)2 + y(I)2),angle(I) = atan(y(I) / x(I)),注意属于-pi/2~pi/2 cartToPolar( Dx, Dy, Mag, Angle, false );

for( x = 0; x < width; x++ )

{

float mag = dbuf[x+width*2];

float angle = dbuf[x+width*3]*angleScale - 0.5f;//-5<=angle<=4

//判断angle属于哪个bin

int hidx = cvFloor(angle);

angle -= hidx;

//hidx=-5~-1===>4~8

if( hidx < 0 )

hidx += _nbins;

else if( hidx >= _nbins )

hidx -= _nbins;

//检测是否<9

assert( (unsigned)hidx < (unsigned)_nbins );

qanglePtr[x*2] = (uchar)hidx;

hidx++;

//hidx = hidx & 1111 1111 当hidx

//hidx = hidx & 0000 0000 当hidx>=nbins,即hidx=0

//注意到nbins=9时，hidx最大值只为8

hidx &= hidx < _nbins ? -1 : 0;

//qangle两通道分别存放相邻的两个bin

qanglePtr[x*2+1] = (uchar)hidx;

//幅度,注意此时的0

gradPtr[x*2] = mag*(1.f - angle);

gradPtr[x*2+1] = mag*angle;

}

}

}

//HOG存储结构，每个window包含105block,每个block包含36bin

struct HOGCache

{

struct BlockData

{

BlockData() : histOfs(0), imgOffset() {}

//以block为单位，譬如block[0]中的36个bin在内存中位于最前面

//而block[1]中的36个bin存储位置在连续内存中则有一个距离起点的偏置，即为histOfs:hist offset

int histOfs;

//imgOffset表示该block在检测窗口window中的位置

Point imgOffset;

};

//PixData是作者程序中比较晦涩的部分，具体见后面程序分析

//gradOfs:该pixel的grad在Mat grad中的位置，是一个数：(grad.cols*i+j)*2,2表示2通道//qangleOfs:pixel的angle在Mat qangle中的位置，是一个数：(qangle.cols*i+j)*2，2表示2

通道

//histOfs[4]:在后面程序中，作者把一个block中的像素分为四个区域，每个区域的像素最多对四个不同Cell中的hist有贡献

//即一个区域中进行直方图统计，则最多包含四个Cell的不同直方图，histOfs[i]表示每个区域中的第i个直方图

//在整个block直方图存储空间中的距离原始位置的偏置

//显然第一个Cell的hist其对应的histOfs[0]=0,依次类推有：histOfs[1]=9,histOfs[2]=18,histOfs[3]=27

//|_1_|_2_|_3_|_4_|一个block四个cell，这里把每个cell又分四分，1,2,5,6中像素统计属于hist[0],3,4,7,8在hist[1]...

//|_5_|_6_|_7_|_8_|作者将一个block分为了四块区域为：A：1,4,13,16/B：2,3,14,15/C：5,9,8,12/D：6,7,10,11

//|_9_|_10|_11|_12|作者认为A区域中的像素只对其所属的Cell中的hist有贡献，即此区域的像素只会产生一个hist

//|_13|_14|_15|_16|而B区域2,3的像素会对Cell0与Cell1中的hist有贡献，相应的会产生hist[0]与hist[1],14,15类似

//C区域与B区域类似，会对上下两个Cell的hist产生影响，而D区域会对相邻四个Cell 的hist产生影响

//histWeights：每个像素对不同cell的hist贡献大小，由像素在block中的位置决定

//个人觉得这是论文中trilinear插值中对于position中x和y两个维度的插值

//其中像素的角度对于相邻两个bin的权重在HOGDescriptor::computerGradient中已有体现，至此trilinear完成

//其实作者认为每个像素对于其他cell的hist的影响，其大小与该像素距各个cell中心的距离决定

//譬如处于中心的像素（8,8）可以认为对每个cell的hist贡献一样，后面程序中权重的分配也可以看出

//gradWeight：为幅值与高斯权重的乘积

//其中高斯权重选择exp^(-(dx^2+dy^2)/（2*sigma^2）),sigma在HOGDescriptor中决定,以block 中(8,8)为中心

//区别gradWeight和histWeight，gradWeight认为在同一个Cell中不同元素对hist的贡献是不一样的，由二维高斯分布决定

//而histweight说的是一个元素对不同cell中的hist的贡献不同，其贡献由其坐标距离各个cell的距离决定

struct PixData

{

size_t gradOfs, qangleOfs;

int histOfs[4];

float histWeights[4];

float gradWeight;

};

HOGCache();

HOGCache(const HOGDescriptor* descriptor,

const Mat& img, Size paddingTL, Size paddingBR,

bool useCache, Size cacheStride);

virtual ~HOGCache() {};

virtual void init(const HOGDescriptor* descriptor,

const Mat& img, Size paddingTL, Size paddingBR,

bool useCache, Size cacheStride);

//windowsInImage返回Image中横竖可产生多少个windows

Size windowsInImage(Size imageSize, Size winStride) const;

//依据img大小，窗口移动步伐，即窗口序号得到窗口在img中的位置

Rect getWindow(Size imageSize, Size winStride, int idx) const;

//buf为存储blockdata的内存空间，pt为block在parent img中的位置

const float* getBlock(Point pt, float* buf);

virtual void normalizeBlockHistogram(float* histogram) const;

vector pixData;

vector blockData;

//以下的参数是为了充分利用重叠的block信息，避免重叠的block信息重复计算采用的一种缓存思想具体见后面代码

bool useCache;//是否存储已经计算的block信息

vector ymaxCached;//见后文

Size winSize, cacheStride;//cacheStride认为等于blockStride,降低代码的复杂性

Size nblocks, ncells;

int blockHistogramSize;

int count1, count2, count4;

Point imgoffset;//img在扩展后图像中img原点关于扩展后原点偏置

Mat_ blockCache;//待检测图像中以检测窗口进行横向扫描,所扫描的block信息存储在blockCache中

Mat_ blockCacheFlags;

//判断当前block的信息blockCache中是否有存储,1：存储,于是直接调用；0：未存储,需要把信息存储到blockCache中

Mat grad, qangle;

const HOGDescriptor* descriptor;

};

HOGCache::HOGCache()

{

useCache = false;

blockHistogramSize = count1 = count2 = count4 = 0;

descriptor = 0;

}

HOGCache::HOGCache(const HOGDescriptor* _descriptor,

const Mat& _img, Size _paddingTL, Size _paddingBR,

bool _useCache, Size _cacheStride)

{

init(_descriptor, _img, _paddingTL, _paddingBR, _useCache, _cacheStride);

}

//初始化主要包括：1、block中各像素对block四个bin的贡献权重，以及在存储空间中的位置记录

//2、block的初始化，以及每个block在存储空间中的偏置及在检测窗口中的位置记录

//3、其他参数的赋值

//并没有实际计算HOG

void HOGCache::init(const HOGDescriptor* _descriptor,

const Mat& _img, Size _paddingTL, Size _paddingBR,

bool _useCache, Size _cacheStride)

{

descriptor = _descriptor;

cacheStride = _cacheStride;

useCache = _useCache;

descriptor->computeGradient(_img, grad, qangle, _paddingTL, _paddingBR);

imgoffset = _paddingTL;//16,24

winSize = descriptor->winSize;//64*128

Size blockSize = descriptor->blockSize;//16*16

Size blockStride = descriptor->blockStride;//8*8

Size cellSize = descriptor->cellSize;//8*8

Size winSize = descriptor->winSize;//64*128

int i, j, nbins = descriptor->nbins;//9

int rawBlockSize = blockSize.width*blockSize.height;//16*16=256

nblocks = Size((winSize.width - blockSize.width)/blockStride.width + 1,

(winSize.height - blockSize.height)/blockStride.height + 1);//7*15=105

ncells = Size(blockSize.width/cellSize.width, blockSize.height/cellSize.height);//2*2=4 blockHistogramSize = ncells.width*ncells.height*nbins;//9*2*2=36

//对于训练时,该段代码不起作用；对于检测时,该段代码可以提高运行速度。

//在训练时,由于样本大小即等于检测窗口大小,因而不需要额外存储

//但是在检测时由于待检测图像大于检测窗口,因而当检测窗口移动时,检测相邻检测窗口具有大量共同的block信息

//为了节省时间,对于之前计算过大block信息,这里只需要调用,而对于未计算过的block信息,则重新计算并存储

//其具体思路如下：假设待检测图像640*480,检测窗口为144*144

//待检测图像水平方向有79个block,检测窗口垂直方向有17个block

//于是由以下代码知道：blockCache为18*（79*36）=18*2844,blockCacheFlags为17*79,ymxcCached为17

//以左上角代表检测窗口位置,当位于（0,0）时,第一次计算block信息,blockCache中是没有保存任何信息的。

//当位于（0,0）时须计算（也以block左上角代表block位置）：

//(0,0)---->(128,0) 信息均存储到blockCache中,分别为blockCache[0][0]--->blockCache[0][17*36],相应blockCacheFlags置1

//(0,128)-->(128,128) blockCache[17][0]-->blockCache[17][17*36]

//当检测窗口移动到（8,0）时,可以发现两个窗口中有大量信息是重复的,于是可以直接调用blockCache中相关block信息

//并把（136,0）-->(136,128)新增列的block信息加到blockCache中,同时跟新blockCacheFlags //一直到窗口移到(624,0)进入到下一行(0,8),上述过程持续,于是blockCache中前17行存储了待检测图像中前17*79个block信息

//当检测窗口移动到(624,0)时此时blockCache已经存储满了

//当检测窗口移动到(0,8)时,第18行的信息怎么处理呢？

//此时大家要留意的是第1行的block信息已经没有用啦,于是可以将第18行的信息替代第1行的信息。

//当检测窗口不断横向扫描时,最新一行的信息总是会替代最旧一行的信息,如此反复,达到提高运行速度的目的

//另外需要提到一点的是当block在pt=(x,y)=(0,0)-->(624,0)--->(0,128)---->(624.128)

//可以用x/cacheStride=blockStride--->Canche_X,y/blockStride--->Cache_Y

//从而从blockCache中取出对应的blockCache[Cache_Y][Cache_X*36]

//当pt中y>128时,对应的第18行信息存储在第blockCache中的第0行

//于是我们可以用取余的办法,y/blockStride%18--->Cache_Y,而Cache_X的计算不变

//getblock函数中代码正是按该方法进行操作的

if( useCache )

{

//HOGCache的grad，qangle由discriptor->computerGradient得到

//grad.cols=img.cols + paddingTL.width + paddingBR.width

Size cacheSize((grad.cols - blockSize.width)/cacheStride.width+1,

(winSize.height/cacheStride.height)+1);

blockCache.create(cacheSize.height, cacheSize.width*blockHistogramSize); blockCacheFlags.create(cacheSize);

size_t i, cacheRows = blockCache.rows;

ymaxCached.resize(cacheRows);

for( i = 0; i < cacheRows; i++ )

ymaxCached[i] = -1;

}

Mat_ weights(blockSize);

//sigma默认值为4

float sigma = (float)descriptor->getWinSigma();

float scale = 1.f/(sigma*sigma*2);

//权重的二维高斯分布

for(i = 0; i < blockSize.height; i++)

for(j = 0; j < blockSize.width; j++)

{

float di = i - blockSize.height*0.5f;

float dj = j - blockSize.width*0.5f;

weights(i,j) = std::exp(-(di*di + dj*dj)*scale);

}

blockData.resize(nblocks.width*nblocks.height);//105个block

pixData.resize(rawBlockSize*3);//256*3(通道数)

// Initialize 2 lookup tables, pixData & blockData.

// Here is why:

//

// The detection algorithm runs in 4 nested loops (at each pyramid layer):

// loop over the windows within the input image

// loop over the blocks within each window

// loop over the cells within each block

// loop over the pixels in each cell

//

// As each of the loops runs over a 2-dimensional array,

// we could get 8(!) nested loops in total, which is very-very slow.

//

// To speed the things up, we do the following:

// 1. loop over windows is unrolled in the HOGDescriptor::{compute|detect} methods;

// inside we compute the current search window using getWindow() method.

// Yes, it involves some overhead (function call + couple of divisions),

// but it's tiny in fact.

// 2. loop over the blocks is also unrolled. Inside we use pre-computed blockData[j]

// to set up gradient and histogram pointers.

// 3. loops over cells and pixels in each cell are merged

// (since there is no overlap between cells, each pixel in the block is processed once)

// and also unrolled. Inside we use PixData[k] to access the gradient values and

// update the histogram

//作者用查找表的方法来计算。具体实现时是先执行HoGCache的初始化函数Init() //构造查找表，然后用getWindow()和getBlock()两个函数实现的表的查找

count1 = count2 = count4 = 0;

//blockSize.width=16

for( j = 0; j < blockSize.width; j++ )

for( i = 0; i < blockSize.height; i++ )

{

PixData* data = 0;

//确定cell在block中的位置

float cellX = (j+0.5f)/cellSize.width - 0.5f;

float cellY = (i+0.5f)/cellSize.height - 0.5f;

int icellX0 = cvFloor(cellX);

int icellY0 = cvFloor(cellY);

int icellX1 = icellX0 + 1, icellY1 = icellY0 + 1;

cellX -= icellX0;

cellY -= icellY0;

//注意到unsigned，当icellX0=-1时，（unsigned）icellX0>2

//(0~3,0~3)+(0~3,12~15)+(12~15,0~3)+(12~15,12~15)

//(icellX0,icellY0,icellX1,icellY1)=(-1,-1,0,0),(-1,1,0,2),(1,-1,0,2),(1,1,2,2)===》条件4

//(4~11,4~11)==》（0,0,1,1）==》条件1

//(0~3,4~11)+(12~15,4~11)==》(-1,0,0,1)==》条件3

//(4~11,0~3)+(4~11,12~15)==》(0,-1,1,0)==》条件2

//情况2,3中元素对两个cell中的hist有贡献

//(0~3,4~11):histofs=(0,9,0,0);(12~15,4~11):histofs=(18,27,0,0)

//(4~11,0~3):histofs=(0,18,0,0);(4~11,12~15):hisofs=(9,27,0,0)

//情况1中，元素对4个cell的hist有贡献,则会有4个hist及histofs,并且为(0,9,18,27) //情况4中，元素属于一个cell,则只有一个hist，对应的只有一个histofs:hist offset

//分别应为：(0,0,0,0),(9,0,0,0),(18,0,0,0),(27,0,0,0)

//对于权重的理解看后面的注释，选择第二种情况，其他可类推

if( (unsigned)icellX0 < (unsigned)ncells.width &&

(unsigned)icellX1 < (unsigned)ncells.width )

{

if( (unsigned)icellY0 < (unsigned)ncells.height &&

(unsigned)icellY1 < (unsigned)ncells.height )

{

data = &pixData[rawBlockSize*2 + (count4++)];

data->histOfs[0] = (icellX0*ncells.height + icellY0)*nbins;

data->histWeights[0] = (1.f - cellX)*(1.f - cellY);

data->histOfs[1] = (icellX1*ncells.height + icellY0)*nbins;

data->histWeights[1] = cellX*(1.f - cellY);

data->histOfs[2] = (icellX0*ncells.height + icellY1)*nbins;

data->histWeights[2] = (1.f - cellX)*cellY;

data->histOfs[3] = (icellX1*ncells.height + icellY1)*nbins;

data->histWeights[3] = cellX*cellY;

}

else

{

data = &pixData[rawBlockSize + (count2++)];

if( (unsigned)icellY0 < (unsigned)ncells.height )

{

icellY1 = icellY0;

cellY = 1.f - cellY;

}

//|_1_|_2_|_3_|_4_|第二中情况是位于(2,3),(14,15)。感性上可以认为(2,3)中的像素对cell0与cell1的贡献中

//|_5_|_6_|_7_|_8_|其中y分量的贡献都是相同的，由于距离各cell的中心距离相同，而x分量的影响是不同的

//|_9_|_10|_11|_12|所以权重的分配为(1-cellx)*celly和cellx*celly

//|_13|_14|_15|_16|

//挑了中简单的情况，情况1中可以类似分析

data->histOfs[0] = (icellX0*ncells.height + icellY1)*nbins;

data->histWeights[0] = (1.f - cellX)*cellY;

data->histOfs[1] = (icellX1*ncells.height + icellY1)*nbins;

data->histWeights[1] = cellX*cellY;

data->histOfs[2] = data->histOfs[3] = 0;

data->histWeights[2] = data->histWeights[3] = 0;

}

}

else

{

if( (unsigned)icellX0 < (unsigned)ncells.width )

{

icellX1 = icellX0;

cellX = 1.f - cellX;

}

if( (unsigned)icellY0 < (unsigned)ncells.height &&

(unsigned)icellY1 < (unsigned)ncells.height )

{

data = &pixData[rawBlockSize + (count2++)];

data->histOfs[0] = (icellX1*ncells.height + icellY0)*nbins;

data->histWeights[0] = cellX*(1.f - cellY);

data->histOfs[1] = (icellX1*ncells.height + icellY1)*nbins;

data->histWeights[1] = cellX*cellY;

data->histOfs[2] = data->histOfs[3] = 0;

data->histWeights[2] = data->histWeights[3] = 0;

}

else

{

data = &pixData[count1++];

if( (unsigned)icellY0 < (unsigned)ncells.height )

icellY1 = icellY0;

cellY = 1.f - cellY;

}

data->histOfs[0] = (icellX1*ncells.height + icellY1)*nbins;

data->histWeights[0] = cellX*cellY;

data->histOfs[1] = data->histOfs[2] = data->histOfs[3] = 0;

data->histWeights[1] = data->histWeights[2] = data->histWeights[3] = 0;

}

}

data->gradOfs = (grad.cols*i + j)*2;

data->qangleOfs = (qangle.cols*i + j)*2;

data->gradWeight = weights(i,j);

}

assert( count1 + count2 + count4 == rawBlockSize );//rawBlockSize=105*36=3780

// defragment pixData,重新整理数据使其连贯存储

//由图1表示，内存中存储顺序为：1,4,13,16/2,3,5,8,9,12,14,15/6,7,10,11区域像素的信息for( j = 0; j < count2; j++ )

pixData[j + count1] = pixData[j + rawBlockSize];

for( j = 0; j < count4; j++ )

pixData[j + count1 + count2] = pixData[j + rawBlockSize*2];

count2 += count1;

count4 += count2;

// 初始化blockData

for( j = 0; j < nblocks.width; j++ )

for( i = 0; i < nblocks.height; i++ )

{

BlockData& data = blockData[j*nblocks.height + i];

//histofs:hist off set，直方图信息在blockData中的偏置

data.histOfs = (j*nblocks.height + i)*blockHistogramSize;

data.imgOffset = Point(j*blockStride.width,i*blockStride.height);

}

}

//buf:存储空间

//pt:block在parent img中的坐标，或偏置（左上角）

//只获取一个block中的信息：将256个像素的grad和angle信息变为36个bin的信息并保存

const float* HOGCache::getBlock(Point pt, float* buf)

{

float* blockHist = buf;

assert(descriptor != 0);

Size blockSize = descriptor->blockSize;

//imgoffset = _paddingTL;16,24,从parent img==>grad img的坐标

pt += imgoffset;

CV_Assert( (unsigned)pt.x <= (unsigned)(grad.cols - blockSize.width) && (unsigned)pt.y <= (unsigned)(grad.rows - blockSize.height) );

//相关解释见init函数注释

if( useCache )

{

CV_Assert( pt.x % cacheStride.width == 0 &&

pt.y % cacheStride.height == 0 );

Point cacheIdx(pt.x/cacheStride.width,

(pt.y/cacheStride.height) % blockCache.rows);

if( pt.y != ymaxCached[cacheIdx.y] )

{

Mat_ cacheRow = blockCacheFlags.row(cacheIdx.y);

cacheRow = (uchar)0;

ymaxCached[cacheIdx.y] = pt.y;

}

blockHist = &blockCache[cacheIdx.y][cacheIdx.x*blockHistogramSize];

uchar& computedFlag = blockCacheFlags(cacheIdx.y, cacheIdx.x);

if( computedFlag != 0 )

return blockHist;

computedFlag = (uchar)1; // set it at once, before actual computing

}

int k, C1 = count1, C2 = count2, C4 = count4;

//pt.x*2由于是2通道，记录block左上角对应在grad.data和qangle.data中的位置const float* gradPtr = (const float*)(grad.data + grad.step*pt.y) + pt.x*2;

const uchar* qanglePtr = qangle.data + qangle.step*pt.y + pt.x*2;

CV_Assert( blockHist != 0 );

//blockHistogramSize=36

for( k = 0; k < blockHistogramSize; k++ )

blockHist[k] = 0.f;

//pixData包含256个元素，blockData包含105个block

const PixData* _pixData = &pixData[0];

//遍历一个block中所有像素256个，以像素为单位取

//一个像素包含：gradofs,qangleofs,gradweight,histofs[4],histweight[4]

for( k = 0; k < C1; k++ )

{

const PixData& pk = _pixData[k];

const float* a = gradPtr + pk.gradOfs;//gradPtr起始地址，由不同输入Point pt而变化，pk.gradOfs偏置

float w = pk.gradWeight*pk.histWeights[0];

const uchar* h = qanglePtr + pk.qangleOfs;

int h0 = h[0], h1 = h[1];//h[0]为angle所在bin的位置0~8，hist[h0]表示第h0个bin其中存储的是相应的幅度与权重

float* hist = blockHist + pk.histOfs[0];//blockHist为buff的地址，histOfs即为偏置

float t0 = hist[h0] + a[0]*w;

float t1 = hist[h1] + a[1]*w;

hist[h0] = t0; hist[h1] = t1;

}

//两个

for( ; k < C2; k++ )

{

const PixData& pk = _pixData[k];

const float* a = gradPtr + pk.gradOfs;

float w, t0, t1, a0 = a[0], a1 = a[1];

const uchar* h = qanglePtr + pk.qangleOfs;

int h0 = h[0], h1 = h[1];

float* hist = blockHist + pk.histOfs[0];

w = pk.gradWeight*pk.histWeights[0];

t0 = hist[h0] + a0*w;

t1 = hist[h1] + a1*w;

hist[h0] = t0; hist[h1] = t1;

hist = blockHist + pk.histOfs[1];

w = pk.gradWeight*pk.histWeights[1];

t0 = hist[h0] + a0*w;

t1 = hist[h1] + a1*w;

hist[h0] = t0; hist[h1] = t1;

}

//四个

for( ; k < C4; k++ )

{

const PixData& pk = _pixData[k];

const float* a = gradPtr + pk.gradOfs;

float w, t0, t1, a0 = a[0], a1 = a[1];

const uchar* h = qanglePtr + pk.qangleOfs;

int h0 = h[0], h1 = h[1];

float* hist = blockHist + pk.histOfs[0];

w = pk.gradWeight*pk.histWeights[0];

t0 = hist[h0] + a0*w;

t1 = hist[h1] + a1*w;

hist[h0] = t0; hist[h1] = t1;

hist = blockHist + pk.histOfs[1];

w = pk.gradWeight*pk.histWeights[1];

t0 = hist[h0] + a0*w;

t1 = hist[h1] + a1*w;

hist[h0] = t0; hist[h1] = t1;

hist = blockHist + pk.histOfs[2];

w = pk.gradWeight*pk.histWeights[2];

t0 = hist[h0] + a0*w;

t1 = hist[h1] + a1*w;

hist[h0] = t0; hist[h1] = t1;

hist = blockHist + pk.histOfs[3];

w = pk.gradWeight*pk.histWeights[3];

t0 = hist[h0] + a0*w;

t1 = hist[h1] + a1*w;

hist[h0] = t0; hist[h1] = t1;

}

normalizeBlockHistogram(blockHist);

return blockHist;

}

void HOGCache::normalizeBlockHistogram(float* _hist) const {

float* hist = &_hist[0];

size_t i, sz = blockHistogramSize;

float sum = 0;

for( i = 0; i < sz; i++ )

sum += hist[i]*hist[i];

堆 排 序 算 法

堆排序——C#实现 一算法描述 堆排序（Heap Sort）是利用一种被称作二叉堆的数据结构进行排序的排序算法。 二叉堆在内部维护一个数组，可被看成一棵近似的完全二叉树，树上每个节点对应数组中的一个元素。除最底层外，该树是满的。 二叉堆中，有两个与所维护数组相关的属性。Length表示数组的元素个数，而HeapSize则表示二叉堆中所维护的数组中的元素的个数（并不是数组中的所有元素都一定是二叉堆的有效元素）。因此，根据上述定义有： 0 = HeapSize = Length。 二叉堆可分为最大堆和最小堆两种类型。在最大堆中，二叉树上所有的节点都不大于其父节点，即 A[Parent(i)] = A[i]。最小堆正好相反：A[Parent(i)] = A[i]。 为维护一个二叉堆是最大（小）堆，我们调用一个叫做MaxHeapify （MinHeapify）的过程。以MaxHeapify，在调用MaxHeapify时，先假定根节点为Left(i)和Right(i)的二叉树都是最大堆，如果A[i]小于其子节点中元素，则交换A[i]和其子节点中的较大的元素。但这样一来，以被交换的子节点为根元素的二叉堆有可能又不满足最大堆性质，此时则递归调用MaxHeapify方法，直到所有的子级二叉堆都满足最大堆性质。如下图所示： 因为在调用MaxHeapify（MinHeapify）方法使根节点为A[i]的

二叉堆满足最大（小）堆性质时我们有其左右子堆均已满足最大（小）堆性质这个假设，所以如果我们在将一个待排序的数组构造成最大（小）堆时，需要自底向上地调用 MaxHeapify（MinHeapify）方法。 在利用最大堆进行排序时，我们先将待排序数组构造成一个最大堆，此时A[0]（根节点）则为数组中的最大元素，将A[0]与A[n - 1]交换，则把A[0]放到了最终正确的排序位置。然后通过将HeapSize 减去1，将（交换后的）最后一个元素从堆中去掉。然后通过MaxHeapify方法将余下的堆改造成最大堆，然后重复以上的交换。重复这一动作，直到堆中元素只有2个。则最终得到的数组为按照升序排列的数组。 二算法实现 1 注意到在C#中数组的起始下标为0，因此，计算一个给定下标的节点的父节点和左右子节点时应该特别小心。 private static int Parrent(int i) return (i - 1) - 2; private static int Left(int i) return 2 * i + 1; private static int Right(int i) return 2 * i + 2; 2 算法的核心部分是MaxHeapify（MinHeapify）方法，根据算法描述中的说明，一下代码分别实现了对整数数组的最大堆化和最小堆化方法，以及一个泛型版本。

内部堆排序算法的实现课程设计说明书

数据结构课程设计设计说明书 内部堆排序算法的实现 学生姓名金少伟 学号1121024029 班级信管1101 成绩 指导教师曹阳 数学与计算机科学学院 2013年3月15日

课程设计任务书 2012—2013学年第二学期 课程设计名称：数据结构课程设计 课程设计题目：内部堆排序算法的实现 完成期限：自2013年3 月4日至2013年3 月15 日共 2 周 设计内容： 堆排序（heap sort）是直接选择排序法的改进，排序时，需要一个记录大小的辅助空间。n个关键字序列K1，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。（即如果按照线性存储该树，可得到一个不下降序列或不上升序列）。 本课程设计中主要完成以下内容： 1.设计堆排序算法并实现该算法。 2.对堆排序的时间复杂度及空间复杂度进行计算与探讨。 3.寻找改进堆排序的方法。 基本要求如下： 1.程序设计界面友好； 2.设计思想阐述清晰； 3.算法流程图正确； 4.软件测试方案合理、有效。指导教师：曹阳教研室负责人：申静 课程设计评阅

摘要 堆排序是直接选择排序法的改进。本课设以VC++6.0作为开发环境，C语言作为编程语言，编程实现了堆排序算法。程序运行正确，操作简单，易于为用户接受。 关键词：堆排序；C语言；时间复杂度

堆排序算法的基本思想及算法实现示例

堆排序算法的基本思想及算法实现示例 堆排序 1、堆排序定义 n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)： (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ ) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。 2、大根堆和小根堆 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。 注意： ①堆中任一子树亦是堆。 ②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。 3、堆排序特点 堆排序(HeapSort)是一树形选择排序。 堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】，在当前无序区中选择关键字最大(或最小)的记录。 4、堆排序与直接插入排序的区别 直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。 堆排序可通过树形结构保存部分比较结果，可减少比较次数。5、堆排序 堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。 （1）用大根堆排序的基本思想

ppt注释的使用方法

ppt注释的使用方法 演讲PPT之前不用硬背，演讲时心里不打鼓！轻轻松松看这电脑念，下面的人却看不到，特别有面子！！！设置ppt双屏显示，使讲演者看到备注，而观众看不到，嘿嘿，演讲的时候可以作弊咯！！！ 还是自己备一份，不然找起来太费劲了。。 前言：大家在看此篇文章之前心中是不是一直存有一个疑问，那就是office组件中的powerpoint（PPT）制作中的“备注”到底有何作用？ 在工作中经常用PPT放映演示给客户进行讲演，也见识过专业讲师和IT销售给我介绍产品，使用的也是 PPT。但是几乎所有人的PPT使用方式还是停留在投影机上放什么，演讲者的laptop上也显示什么，演讲者要么看自己的laptop的屏幕，要么看墙上的投影。“备注”就彻底失去了作用，因为根本看不见。 出于纳闷，我就询问了几个号称是office高手这个问题，“备注”写了是给谁看的，有什么作用？ 高手给出的答案竟然是“备注”用来给演讲者回忆讲演思路，或者此PPT给别人的时候别人讲演前可以先了解一下制作此PPT的作者的思路意图。 这些都是PPT的常规用法，或者说并不怎么正确的用法，下面我给大家介绍如何高效的使用PPT进行演讲，并且充分利用“备注”的作用，以期为受众作出最出色的讲解。 下面我就开始了。下面做演示用的PPT涉及某安全厂商，原因是我手头做的比较好的PPT 而且备注写的比较详细的也就这份了，我并没有用于商业用途，我也不是该厂商员工，特别声明。

第一步，在你的laptop的显示属性中进行设置。 如图所示，在连接了外部显示器或者投影仪的情况下，点击“2”号屏幕，并按照图中高亮标注处选中“将windows桌面扩展到该显示器”同时设置适当的分辨率。 单击“应用”，就可以看到如下的效果。

堆排序算法分析(C语言版)

堆排序 堆排序是利用堆的性质进行的一种选择排序，下面先讨论一下堆。 1.堆 堆实际上是一棵完全二叉树，其任何一非叶节点满足性质： Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2] 即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。 堆分为大顶堆和小顶堆，满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆，满足Key[i]<= key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。 2.堆排序的思想 利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。 其基本思想为(大顶堆)： 1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区； 2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n]; 3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。 操作过程如下： 1)初始化堆：将R[1..n]构造为堆； 2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。 因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。 下面举例说明： 给定一个整形数组a[]={16,7,3,20,17,8}，对其进行堆排序。 首先根据该数组元素构建一个完全二叉树，得到

注释要求

一、注释体例及标注位置 文献引证方式采用注释体例。 注释放置于当页下（脚注）。注释序号用①，②，③……标识，每页单独排序。正文中的注释序号统一置于包含引文的句子(有时候也可能是词或词组)或段落标点符号之后。 二、注释的标注格式 （一）非连续出版物 1．著作 标注顺序:责任者与责任方式/文献题名/出版地点/出版者/出版时间/页码。 责任方式为著时，“著”可省略，其他责任方式不可省略。 引用翻译著作时，将译者作为第二责任者置于文献题名之后。 引用《马克思恩格斯全集》、《列宁全集》等经典著作应使用最新版本。 示例： 赵景深：《文坛忆旧》，北新书局，1948，第43页。 谢兴尧整理《荣庆日记》,西北大学出版社，1986，第175页。 蒋大兴：《公司法的展开与评判——方法·判例·制度》，法律出版社，2001，第3页。 任继愈主编《中国哲学发展史(先秦卷)》,人民出版社,1983,第25页。 实藤惠秀：《中国人留学日本史》，谭汝谦、林启彦译，香港中文大学出版社，1982，第11-12页。 金冲及主编《周恩来传》，人民出版社、中央文献出版社，1989，第9页。 佚名：《晚清洋务运动事类汇钞五十七种》上册，全国图书馆文献缩微复制中心，1998，第56页。 狄葆贤：《平等阁笔记》，有正书局，出版时间不详，第8页。 《马克思恩格斯全集》第31卷，人民出版社，1998，第46页。 2．析出文献

标注顺序:责任者/析出文献题名/文集责任者与责任方式/文集题名/出版地点/出版者/出版时间/页码。 文集责任者与析出文献责任者相同时，可省去文集责任者。 示例： 杜威·佛克马:《走向新世界主义》,王宁、薛晓源编《全球化与后殖民批评》,中央编译出版社,1999,第247-266页。 鲁迅：《中国小说的历史的变迁》，《鲁迅全集》第9册，人民文学出版社，1981，第325页。 唐振常：《师承与变法》，《识史集》，上海古籍出版社，1997，第65页。 3.著作、文集的序言、引论、前言、后记 （1）序言、前言作者与著作、文集责任者相同。 示例： 李鹏程：《当代文化哲学沉思》，人民出版社，1994，“序言”，第1页。 （2）序言有单独的标题，可作为析出文献来标注。 示例： 楼适夷：《读家书，想傅雷（代序）》，傅敏编《傅雷家书（增补本）》，三联书店，1988，第2页。 黄仁宇：《为什么称为“中国大历史”？——中文版自序》，《中国大历史》，三联书店，1997，第2页。 （3）责任者层次关系复杂时，可以通过叙述表明对序言的引证。为了表述紧凑和语气连贯，责任者与文献题名之间的冒号可省去，出版信息可括注起来。 示例： 见戴逸为北京市宣武区档案馆编、王灿炽纂《北京安徽会馆志稿》（北京燕山出版社，2001）所作的序，第2页。 4.古籍 （1）刻本 标注顺序：责任者与责任方式／文献题名（卷次、篇名、部类）（选项）／版本、页码。 部类名及篇名用书名号表示，其中不同层次可用中圆点隔开，原序号仍用汉字数字，下同。页码应注明a、b面。

堆排序

算法与数据结构程设计报告 一．设计题目： 堆排序的算法 二．运行环境： 1、硬件：计算机 2、软件：Microsoft Visual C++6.0 三．目的和意义： 目的：创建一个大堆，按从大到小顺序输出堆元素，实现堆排序。 意义：利用堆排序，即使在最坏情况下的时间复杂度也是O(nlog2n)，相对于快速排序来说，时间复杂度小，这是堆排序的最大优点，可用于对若干元素进行排序，加快排序速度。 四．算法设计的基本思想： 堆排序算法设计基本思想： 堆排序利用了大根堆堆顶记录的关键字最大这一特征，使得在当前无序区中选取最大关键字的记录变得简单。先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区。再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录r[n]交换，由此得到新的无序区r[1..n-1]和有序区r[n]，且满足r[1..n-1].keys≤r[n].key。由于交换后新的根R[1]可能违反堆性质，故应将当前无序区r[1..n-1]调整为堆。然后再次将r[1..n-1]中关键字最大的记录r[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区r[1..n-2]和有序区r[n-1..n]，且仍满足关系r[1..n-2].keys≤r[n-1..n].keys，同样要将r[1..n-2]调整为堆。直到无序区只有一个元素为止.

. .

流程图3：打印数组函数print()

六．算法设计分析： 性能分析：堆排序的时间主要由建立初始堆和不断重复建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。其中：建立初始堆时，总共需进行的关键字比较次数≤ 4n =O(n) ;排序过程中进行n-1次重建堆所进行的总比较次数不超过下式：2*(└ log2(n-1) ┘+└ log2(n-2) ┘+…+ └ log22 ┘) < 2n └ log2n ┘=O(n log2n)因此堆排序总的时间复杂度是 O(n+ n log2n)= O(n log2n)。堆排序在最坏情况下的时间复杂度也是O(nlog2n)，相对于快速排序来说，这是堆排序的最大优点。另外，堆排序仅需一个记录大小供交换用的辅助空间。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录较少的文件，但对n较大的文件还是很有效的。堆排序是就地排序，辅助空间为O(1)，它是不稳定的排序方法。 堆的描述：堆排序(HeapSort)是一树形选择排序。堆是对基于数组的树的重要应用场合之一。它是节点间具有层次次序关系的完全二叉树。其中，父节点值大于或等于其孩子节点值的，叫“最大堆（maximum heap）”;父节点值小于或等于孩子节点值的，叫“最小堆（minimum heap）”.在最大堆中，根中的元素值最大；在最小堆中，根中的元素值最小。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。 从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。 堆的存储特点：在这里，讨论作为顺序表存储的堆。它是按某种次序将一系列数据以完全二叉树形式存放的一种表。它要求堆中的节点的值都大于或等于其孩子节点的值。 按照这种存储方式，可知第i个元素的左右儿子分别是第2i和第2i+1个元素，而它的父亲节点是第i/2个元素。由于父亲节点和儿子节点具有这样的顺序关系，所以可以方便地由父亲节点找到儿子节点，反之亦然。 可见，这种存储方式大大节省了存储空间，高效快速。 堆的相关操作：作为抽象表结构，堆允许增加和删除表项。插入过程不用假定新表项占有一个特定的位置而只需维持堆顺序。但是删除操作总是删去表中的最大项（根）。堆可以用于那些客户程序想直接访问最大（小）元素的场合。作为表，堆并不提供Find操作，而对表的直接访问是只读的。所有的堆处理算法都有责任更新树和维持堆顺序。 1.建堆：数组具有对应的树表示形式。一般情况下，树并不满足堆的条件。通过重新排列元素，可以建立一棵“堆化”的树。 2.插入一个元素：新元素被加入到表中，随后树被更新以恢复堆次序。例如，下面的步骤将15加入到表中。 3.删除一个元素：删除总是发生在根节点处。用表中的最后一个元素来填补空缺位置，结果树被更新以恢复堆条件。 在堆实现时我们是采用数组来存储堆的完全二叉树表示，并且用一种有效的算法来保证对堆的所有操作不破坏堆的性质。这种表示的主要问题在于数组的大小需要事先确定，这使得对堆的大小有了一个初始的限定。在堆中数据增长到

参考文献与注释的编排方法.doc

参考文献与注释的编排方法 一、注释的标注方法 注释是对论著正文中某一特定内容的进一步解释或补充说明,以及未公开发表的私人通信、内部资料、书稿和仅有中介文献信息的"转引自"等类文献的引用著录，排印在该页地脚(数字加圆圈，如①、②...)。 二、参考文献的标注方法 参考文献是作者写作论著时所引用的已公开发表的文献书目,或有明确收藏地点的善本、档案，按照在正文中引用的顺序，用数字加方括号集中列表于文末。正文中的标注方法是：1.引用文献原文需要在正文中标出序号与页码(如："资本主义生产的内在规律在竞争中是以颠倒的形式表现出来的"[1]251)，文后参考文献中不出现页码项;2.引用参考文献中的观点可以只标出序号或者序号与页码同时标注(如：生产力决定生产关系[3]);3.文中多次引用同一参考文献内容，在文后参考文献表中只出现一次，其中不注页码;在正文中标注首次引用的文献序号，并在序号的角标外著录引文页码;4.参考文献的编排格式见附注。 例文 国内外现有的竞争理论文献，或者忽略了马克思的竞争理论，或者只把它作为竞争理论发展的一个阶段或众多竞争理论中的一个流派，停留在马克思对市场竞争过程的描述上。然而,马克思指出："资本主义生产的内在规律在竞争中是以颠倒的形式表现出来的"[1]251。"只有了解了资本的内在本性，才能对竞争进行科学的分析，正像只有认识了天体的实际的、

但又直接感觉不到的运动的人，才能了解天体的表面运动一样。"[2]352 ...... ......而且可以说明，当时政治经济学没有理解的"关于资本主义竞争的基本规律，即调节一般利润率和由它决定的所谓生产价格的规律，也是建立在商品价值和商品成本价格之间的这种差别之上的，建立在由此引起的商品低于价值出售也能获得利润这样一种可能性之上的"[1]45。 ...... ......随着许多偶然的改进,产品系列趋于增大，零件数量趋于增加，会产生大量的多样化成本。[3] 参考文献： [1] 马克思.资本论(第3卷)[M].北京：人民出版社，1975. [2] 马克思.资本论(第1卷)[M].北京：人民出版社，1975. [3] 安德森·派恩二世.21世纪企业竞争的新前沿——大规模定制模式下的敏捷产品开发[M].北京：机械工业出版社，1999. 附注： 一、参考文献著录项目 1. 主要责任者 (专著作者、论文集主编、学位申报人、专利申请人、报告撰写人、期刊文章作者、析出文章作者)。多个责任者之间以"，"分隔，注意在本项数据中不得出现缩写点"."。主要责任者只列姓名，其后不加"著"、"编"、"主编"、"合编"等责任说明。 2.文献题名; 3.文献类型及载体类型标识;

关于引文注释的规定

关于引文注释的规定 （一）注释体例及标注位置 文献引证方式采用注释体例。 注释放置于当页下（脚注）。注释序号用①，②……标识，每页单独排序。正文中的注释序号统一置于包含引文的句子（有时候也可能是词或词组）或段落标点符号之后。 （二）注释的标注格式 1.非连续出版物 （1）著作 标注顺序：责任者与责任方式/文献题名/出版地点/出版者/出版时间/页码。 责任方式为著时，“著”可省略，其他责任方式不可省略。 引用翻译著作时，将译者作为第二责任者置于文献题名之后。引用《马克思恩格斯全集》、《列宁全集》等经典著作应使用最新版本。 示例： 赵景深：《文坛忆旧》，上海：北新书局，1948 年，第 43 页。 谢兴尧整理：《荣庆日记》，西安：西北大学出版社，1986年，第175 页。 蒋大兴：《公司法的展开与评判——方法·判例·制度》，北京：法律出版社，2001 年，第 3 页。

任继愈主编：《中国哲学发展史（先秦卷）》，北京：人民出版社，1983 年，第 25 页。 实藤惠秀：《中国人留学日本史》，谭汝谦、林启彦译，香港：中文大学出版社，1982年，第11—12页。 金冲及主编：《周恩来传》，北京：人民出版社、中央文献出版社，1989年，第9页。 佚名：《晚清洋务运动事类汇钞五十七种》上册，北京：全国图书馆文献缩微复制中心，1998年，第56页。 狄葆贤：《平等阁笔记》，上海：有正书局，出版时间不详，第8 页。 《马克思恩格斯全集》第31卷，北京：人民出版社，1998年，第46页。 （2）析出文献 标注顺序：责任者/ 析出文献题名/文集责任者与责任方式/文集题名/出版地点/出版者/出版时间/页码。 文集责任者与析出文献责任者相同时，可省去文集责任者。 示例： 杜威·佛克马：《走向新世界主义》，王宁、薛晓源编：《全球化与后殖民批评》，北京：中央编译出版社，1999年，第247—266 页。 鲁迅：《中国小说的历史的变迁》，《鲁迅全集》第9册，北京：人民文学出版社，1981 年，第325页。 唐振常：《师承与变法》，《识史集》，上海：上海古籍出版

注释规范

1.注释规范 1.1.规则 1.1.1.一般情况下，源程序有效注释量必须在30％以上。 说明：注释的原则是有助于对程序的阅读理解，在该加的地方都加了，注释不宜太多也不能太少，注释语言必须准确、易懂、简洁。可以用注释统计工具来统计。 1.1. 2.包的注释：包的注释写入一名为package.html 的HTML格式说明文件放入当前路 径。 说明：方便JavaDoc收集 示例： com/qjkj/msg/relay/comm/package.html 1.1.3.包的注释内容：简述本包的作用、详细描述本包的内容、产品模块名称和版本、公 司版权。 说明：在详细描述中应该说明这个包的作用以及在整个项目中的位置。 格式： 一句话简述。 详细描述。 产品模块名称和版本
公司版权信息 示例：

为 Relay 提供通信类，上层业务使用本包的通信类与SP进行通信。 详细描述。。。。。。。。

MMSC V100R002 Relay
(C) 版权所有 2006-2011 79it有限公司 1.1.4.类和接口的注释：该注释放在package 关键字之后，class 或者interface 关键字 之前。 说明：方便JavaDoc收集。 示例： package https://www.doczj.com/doc/d77528376.html,m; /** * 注释内容 */ public class CommManager 1.1.5.类和接口的注释内容：类的注释主要是一句话功能简述、功能详细描述。 说明：可根据需要列出：版本号、生成日期、作者、内容、功能、与其它类的关系等。如果一个类存在Bug，请如实说明这些Bug。 格式： /** * 〈一句话功能简述〉 * 〈功能详细描述〉 * @author [作者] * @version [版本号, YYYY-MM-DD] * @see [相关类/方法] * @since [产品/模块版本] * @deprecated */ 说明：描述部分说明该类或者接口的功能、作用、使用方法和注意事项，每次修改

java注释规范

设置注释模板的入口： Window->Preference->Java->Code Style->Code Template 然后展开Comments 节点就是所有需设置注释的元素啦。现就每一个元素逐一介绍： 文件(Files)注释标签： /** * @Project: ${project_name} * @Title: ${file_name} * @Package ${package_name} * @Description: ${todo} * @author jeffshaw jeff_chon@https://www.doczj.com/doc/d77528376.html, * @date ${date} ${time} * @Copyright: ${year} https://www.doczj.com/doc/d77528376.html, Inc. All rights reserved. * @version V1.0 */ 类(Types)注释标签（类的注释）： /** * @ClassName: ${type_name} * @Description: ${todo} * @author jeffshaw jeff_chon@https://www.doczj.com/doc/d77528376.html, * @date ${date} ${time} * * ${tags} */ 字段(Fields)注释标签： /** * @Fields ${field} : ${todo} */ 构造函数标签： /** * Title: * Description:

* ${tags} */ 方法(Constructor & Methods)标签： /** * @Title: ${enclosing_method} * @Description: ${todo} * @param ${tags} 设定文件 * @return ${return_type} 返回类型* @throws */ 覆盖方法(Overriding Methods)标签： /* (非 Javadoc) * Title: ${enclosing_method} * Description: * ${tags} * ${see_to_overridden} */ 代表方法(Delegate Methods)标签： /** * ${tags} * ${see_to_target} */ getter方法标签： /** * @return ${bare_field_name} */

堆排序思想

基本思想 堆的定义： n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称堆性质)： (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤FLOOR(n/2)) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小 根堆。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。 用大根堆排序的基本思想： (1) 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区; (2) 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key; (3) 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。 排序过程 假设待排序数组为array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，数组大小为20。 （一）初始建堆 首先执行的初始建堆（在建堆的过程中需要调整堆）。过程如下： 1、求出当前堆中最后一个存在孩子结点的索引 这里，把数组array看做是一棵完全二叉树，这样数组每个索引位置上的元素都对应到二叉树中的结点，如图所示： 其中需要在这棵树中找到最后一个有孩子最大的一个结点的索引： pos = (array.length-1)/2 = (20-1)/2 = 9 也就是索引为9的array[9] = 76，由后至前层次遍历，从array[9]一直到array[0]，对初始堆进行调整。 2、对初始堆进行调整

常见英文注释的写作方法

常见英文注释的写作方法 南京师范大学法学院颜林 一、案例的引用 一项标准的案例注释应包括：案件的名称、可查询到该案例的出版物，并在括号中列明如下一些信息：（1）作出该判决的时间，（2）当所引用的报告及其卷期之名所提供的信息不清楚时，须列明作出判决的法院，如果该案在该法院判决前和判决后还有其他的判决，也应一并予以列明。 如：Jackson v. Metropolitan Edison co., 348 F.Supp.954 (M.D. Pa. 1972),aff’d, 483 F.2d 754 (3d Cir. 1973), aff’d, 419 U.S.345(1974). 二、对美国成文法的引用 众所周知，美国是一个以判例法为主的国家，但事实上，美国社会从未放弃对法典化立法的期盼。第一次真正全国意义上的法典编纂是在1875年开始的，并于1878年进行了正式的法典编纂。经过了几十年的努力，直到1926年，美国法典才完成了第一次比较全面、系统的编纂，至此美国的法典编纂已经形成了一套比较固定的体系和比较规范的程序。 美国现行官方的法典编纂制度分为“美国法典编纂”和“美国联邦行政法典编纂”两个部分。这两个法典分别由两个专设机构负责编纂。负责美国法典编纂的机构是设在美国国会众议院内的法律修订委员会办公室（the Office of the Law Revision Counsel of the House of Representatives）；负责美国联邦行政法典编纂的机构是联邦政府公报室（Bulletin Office of the Federal Government）。此外，各州的议会和政府也设有专门机构根据各自的立法权限进行独立的法律编纂。 （一）《美国法典》的历史、内容及其引用 1、就《美国法典》而言，它的编纂是一个相当大的法律汇编工程。1926年首次将建国二百多年以来国会制定的所有立法（除独立宣言、联邦条例和联邦宪法外）加以整理编纂，把每部单行法都按照条文逐一拆开，再按照事先划分的50个大类进行分门别类，同一类别的条文就编入一个大类中，而不论其来自哪部成文法。这样把全部的法律进行分解、分类，重排，汇编，就形成了50个大类（如劳工、证券、版权、专利、破产、税收、教育、食品与药品、医疗卫生、对外关系、高速公路、外国人及国籍、国内安全、战争国防、货币金融、总统、国旗、农业、印地安人、商业贸易、教育、含酒精类饮料、运输、电报电话等等）组

数据结构：简单选择,直接插入,快速排序,冒泡排序希尔排序,堆排序算法比较平台

一、试验内容 内部排序算法效率比较平台的设计与实现 二、试验目的 问题描述：各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较几种主要的基本算法的关键字比较次数和关键字移动次数，以取得直观感受。 三、流程图 冒泡排序 否 是 否 否 开始 J=N-1 I=0 a[i]>a[i+1] a[i]与a[i+1]交换 I++ I=j J=J-1 J=0? 结束

简单选择排序 假 假 真 真 真 假 开 始 i

序 真 真 假 假 真 假 开始 i=2 i<=L.length L.r[i].key

序 假 真 真 真 假 假 真 假 开始 k=0 i<=L.length L.r[i].key0&&L.r[0].k ey

堆排序算法课程设计

数据结构课程设计设计说明书 堆排序的算法的实现 学生姓名 学号 班级 成绩 指导教师 计算机科学与技术系 2011年3月4 日

数据结构课程设计评阅书 注：指导教师成绩60%，答辩成绩40%，总成绩合成后按五级制记入。

课程设计任务书 2010 —2011 学年第二学期 专业：学号：姓名： 课程设计名称：数据结构课程设计 设计题目：堆排序算法的实现 完成期限：自 2011年 2 月 19 日至 2011 年 3 月 4 日共 2 周 设计依据、要求及主要内容（可另加附页）： 堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。如关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆。 大根堆和小根堆：根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。注意：①堆中任一子树亦是堆。②以上讨论的堆实际上是二叉堆(Binary Heap)， 大根堆排序的基本思想： ① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区。 ② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key。 ③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。 要求：（1）给出一个符合堆序列的一组数，能够建立大根堆和小根堆。 （2）界面友好，可操作性强。 （3）能够实现数据个数的变化输入，并建立相应的堆。 指导教师（签字）：教研室主任（签字）： 批准日期：年月日

排序算法实验报告

数据结构实验报告 八种排序算法实验报告 一、实验容 编写关于八种排序算法的C语言程序，要求包含直接插入排序、希尔排序、简单选择排序、堆排序、冒泡排序、快速排序、归并排序和基数排序。 二、实验步骤 各种部排序算法的比较： 1.八种排序算法的复杂度分析（时间与空间）。 2.八种排序算法的C语言编程实现。 3.八种排序算法的比较，包括比较次数、移动次数。 三、稳定性，时间复杂度和空间复杂度分析 比较时间复杂度函数的情况：

时间复杂度函数O(n)的增长情况 所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。 时间复杂度来说： (1)平方阶(O(n2))排序 各类简单排序:直接插入、直接选择和冒泡排序； (2)线性对数阶(O(nlog2n))排序 快速排序、堆排序和归并排序； (3)O(n1+§))排序,§是介于0和1之间的常数。 希尔排序 (4)线性阶(O(n))排序 基数排序，此外还有桶、箱排序。 说明： 当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）； 而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）； 原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。 稳定性： 排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。 稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较； 稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序 不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序

Word脚注格式变化方法

Word脚注、尾注加中括号“【1】”的方法 有很多中文期刊和毕业论文脚注尾注都要求大家用方括号，但w ord自动编号脚注格式里面居然没有方括号的，连这点中国国情都不照顾，还谈什么office中文版？这一难题困扰了我7年，在学校word高手经验交流会上，这一技术难题被xx同志列为学术界3大w ord难题之一。我一直使用他说的变通方法，但今天，终于觉得还是麻烦，难道，勤劳智慧的中国人民，就想不到一个简便易行的方法吗？我今天想到了用替换，但是当我还没有琢磨出究竟的时候，一个网友的帖子进入了我的视线 --有没有更简单的方法改变尾注的编号呢？答案就在强大的w ord替换功能里。大家一般都熟悉常用的查找和替换，但是一些特殊字符的查找和替换恐怕很少有人用过。如怎么批量清除段落之间多余的空行呢？我们只要查找^p^p...,并替换为^p即可。这里的^p就是换行符。再说如何用特殊字符替换功能给尾注编号加方括号。很多杂志和论文要求参考文献编号带有方括号，但是w ord的脚注/尾注中默认格式中唯独没有方括号。如 果用自定义方法加入方括号，当你调整段落顺序后，参考文献的序号不会跟着调整，麻烦更大了。 我们还是用默认的1,2,3插入尾注吧，等你做完了所有工作，再用word的特殊字符将尾注编号替换为带方括号格式的[1],[2],[3]即可,当然 也可以替换为：<>{}《》等格式。 具体操作办法如下：如果用了尾注就查找尾注标记^e，然后全部替换为[^&]即可；如果用了脚注就查找脚注标记^f,再全部替换为[^&]便可以了（注意查找时让“不限定格式”按钮为灰色）。简单吧，一键进入新时代～牛大了！ 看到这个网友写的，我试验了一下，很好用，太高兴了，终于解决了。 ^&估计是通配符，但奇怪的是替换时不能勾选“使用通配符”选项 我写个简单的操作流程： 1、正常插入尾注格式用1、 2、 3、4，全部弄完后 2、在word-编辑-替换里面，“查找”里填 ^e ，“替换”里面填 [^&] 照着做就行了，注意查找时让“不限定格式”按钮为灰色替换时不能勾选“使用通配符”选项 今天终于查到了困扰已久的一个问题的解决方案。 采用宏修改word的尾注格式，加上中括号。 Sub RefineEndNote() Dim n As Integer n = 1 For Each Endnote In ActiveDocument.Endnotes ActiveDocument.Endnotes(n).Reference.InsertBefore (" [") ActiveDocument.Endnotes(n).Reference.InsertAfter ("]") ActiveDocument.Endnotes(n).Range.Select Selection.MoveLeft Unit:=wdCharacter, Count:=3, Extend:=wdMove Selection.TypeText ("[") Selection.MoveRight Unit:=wdCharacter, Count:=1, Extend:=wdExtend Selection.Font.Superscript = False Selection.MoveRight Unit:=wdCharacter, Count:=1, Extend:=wdMove Selection.TypeText ("]")

演讲PPT注释字幕添加方法

演讲PPT再也不用硬背稿子了！设置PPT双屏显示，讲演者看得到备注，而观众看不到！2012-10-08 16:56 前言：大家在看此篇文章之前心中是不是一直存有一个疑问，那就是office组件中的powerpoint（PPT）制作中的“备注”到底有何作用？ 在工作中经常用PPT放映演示给客户进行讲演，也见识过专业讲师和IT销售给我介绍产品，使用的也是PPT。但是几乎所有人的PPT使用方式还是停留在投影机上放什么，演讲者的laptop上也显示什么，演讲者要么看自己的laptop的屏幕，要么看墙上的投影。“备注”就彻底失去了作用，因为根本看不见。 出于纳闷，我就询问了几个号称是office高手这个问题，“备注”写了是给谁看的，有什么作用？ 高手给出的答案竟然是“备注”用来给演讲者回忆讲演思路，或者此PPT给别人的时候别人讲演前可以先了解一下制作此PPT的作者的思路意图。 这些都是PPT的常规用法，或者说并不怎么正确的用法，下面我给大家介绍如何高效的使用PPT进行演讲，并且充分利用“备注”的作用，以期为受众作出最出色的讲解。 下面我就开始了。下面做演示用的PPT涉及某安全厂商，原因是我手头做的比较好的PPT而且备注写的比较详细的也就这份了，我并没有用于商业用途，我也不是该厂商员工，特别声明。

第一步，在你的laptop的显示属性中进行设置。 如图所示，在连接了外部显示器或者投影仪的情况下，点击“2”号屏幕，并按照图中高亮标注处选中“将windows桌面扩展到该显示器”同时设置适当的分辨率。 单击“应用”，就可以看到如下的效果。

由于家里没有投影做演示，就用了一台上了年纪的CRT做示意。从两个屏幕可以看见不同的显示内容，左面的CRT的屏幕正是要给演讲受众看的。这样，下面的观众就不会看见演讲者的笔记本里面装了什么东西，演讲者可以根据自己的意愿把需要给观众看的放映出来，而不是把演讲者的所有操作都放映出来。（这个好处我就不多说了，有过类似经历的朋友想必深有体会） 第二步，打开你需要演讲的PPT进行放映前的准备工作。 选择放映的设置