Blog Archive

Sunday, July 31, 2011

How to compute wave file length and sample number

Microsoft WAVE soundfile format


How to compute SampleNumber according to FileSize(byte)
SampleNumber=(FileSize-44)/(NBITS/8)
WaveLength=SampleNumber/SamplingFrequency

NOTE:
NBITS:
the number of bits per sample (NBITS) used to encode the
data in the file, which can be get via MATLAB command: wavread

Speech Coding Using Sub-Bands: sbc1.m - File Exchange - MATLAB Central

Speech Coding Using Sub-Bands: sbc1.m - File Exchange - MATLAB Central

Speech Recognition - MATLAB examples

Speech Recognition - MATLAB examples

Audition on Linux [ AudioMasters Forums - The Home of the Original Cool Edit and Adobe Audition Community ]

Audition on Linux [ AudioMasters Forums - The Home of the Original Cool Edit and Adobe Audition Community ]: "Ardour."

Nuance Acquires SVOX



Combine Speech Technology Portfolios to Drive More Nature


Burlington, Mass. – June 16, 2011
–– Nuance Communications, Inc. (NASDAQ: NUAN) today announced that it has acquired SVOX, a provider of voice solutions for in-car systems and consumer electronics. The combination of Nuance and SVOX’s innovations will advance the proliferation of voice in the automotive market, and accelerate the development of new voice capabilities that enable natural, conversational interactions between consumers and their connected cars, mobile phones, and other consumer devices.
The mobile industry is experiencing increased consumer demand to not only command and control in-car systems and devices through voice, but also to quickly and easily access mobile Web content, find local businesses, get directions, and create and listen to messages. Combined, Nuance and SVOX will further empower the world’s leading car makers, automotive suppliers, device manufacturers and third-party developers to meet these demands head on, while customizing and differentiating their offerings with state-of-the-art voice innovations that result in the best mobile experience the industry has to offer.
“The automotive and consumer electronics markets are experiencing a surge in demand for voice capabilities,” said Michael Thompson, senior vice president and general manager, Nuance Mobile. “By combining portfolios and expertise, we can ignite innovations that enable seamless, natural conversations between man and machine across an amazing portfolio of voices and languages.”
The combined organization will deliver:
  • Advanced Voice Solutions for New and Emerging Markets – Nuance and SVOX’s combined technologies will advance groundbreaking voice capabilities through robust text-to-speech and voice recognition offerings, as well as powerful hybrid cloud-embedded voice platforms. This resulting portfolio will enable incredibly natural and intuitive interactions never before thought possible with connected cars, a wide array of consumer devices and services, and the digital living room.
  • Strong Global Customer and Partner Relationships – The acquisition provides Nuance’s and SVOX’s customers and partners access to the industry’s largest and most experienced mobile voice technology teams, delivering the broadest voice capabilities that enrich the automotive and mobile consumer experience. SVOX’s technical expertise and talent combined with Nuance’s global resources and market strength will enable technology platforms that are state-of-the-art today, while offering the assurance of technological leadership through a robust product and services roadmap.
“Manufacturers, suppliers, developers and consumers are all driving an unprecedented demand for fully voice-enabled experiences that require both embedded and cloud-based technology to work hand-in-hand. By combining our technology and talent with Nuance’s robust voice capabilities and market strength, we’ll be better positioned to meet that demand,” said Martin Reber, CEO, SVOX.
SVOX’s portfolio also supplements Nuance’s advanced signal enhancement technologies, including echo cancellation and beamforming that enable increased voice recognition accuracy in automotive, mobile and digital home environments. Additionally, OEMs and developers will have access to a portfolio of plug-and-play application modules that enable them to fully voice-enable their innovations that feature the best of Nuance and SVOX’s trusted voice recognition and text-to-speech capabilities.
To learn more about SVOX, please visit www.SVOX.com.
About SVOX AG
SVOX, a privately held company with significant shareholdings represented by smac partners/Germany, is a leading supplier of speech solutions, with a reputation for quality and customer focus. SVOX drives adoption of speech user interfaces in the automotive, mobile device and consumer electronics industries. The company offers an application development framework, as well as separate components including Speech Recognition, Speech Output and complete Speech Dialog solutions. For more information, please visit www.SVOX.com.

Nuance is a leading provider of voice and language solutions for businesses and consumers around the world. Its technologies, applications and services make the user experience more compelling by transforming the way people interact with information and how they create, share and use documents. Every day, millions of users and thousands of businesses experience Nuance’s proven applications and professional services. For more information, please visit: nuance.com.

Nuance, and the Nuance logo are trademarks or registered trademarks of Nuance Communications, Inc. or its subsidiaries in the United States of America and/or other countries. All other company names or product names may be the trademarks of their respective owners.
Statements in this press release regarding the proliferation of voice in the automotive market, increased customer demand in the mobile market, future product offerings by the combined company, and any other statements about Nuance managements’ future expectations, beliefs, goals, plans or prospects constitute forward looking statements within the meaning of the Private Securities Litigation Reform Act of 1995. Any statements that are not statements of historical fact (including statements containing the words "believes," "plans," "anticipates," "expects," estimates and similar expressions) should also be considered to be forward looking statements. There are a number of important factors that could cause actual results or events to differ materially from those indicated by such forward looking statements, including the ability of Nuance to integrate the product offerings of the combined companies and other the factors described in Nuance's Annual Report on Form 10 K for the fiscal year ended September 30, 2010 and other filings with the U.S. Securities and Exchange Commission. Nuance disclaims any intention or obligation to update any forward looking statements as a result of developments occurring after the date of this press release.

Friday, July 29, 2011

Homepage of Dr Tomi Kinnunen

Homepage of Dr Tomi Kinnunen


What Else is New Than the HammingWindow?
Robust MFCCs for Speaker Recognition via Multitapering

Multitaper Estimation of Frequency-Warped Cepstra
With Application to Speaker Verification

Thursday, July 28, 2011

Registered与Unbuffered内存的区别 - 服务器及硬件技术 - ChinaUnix.net

Registered与Unbuffered内存的区别 - 服务器及硬件技术 - ChinaUnix.net


目前市面上有两种内存条,registered 和 unbuffered。它们是不能混插在同一服务器中的。所有的低端X系列服务器现在都使用registered SDRAM 内存。

安装unbuffered同存条,内存控制器直接与DRAMs(动态随机存储控制器)通讯,比registered内存具有轻微的性能优势。Unbuffered内存的劣势是它们具有有限的驱动容量,这意味着大量的内存条连接在同一总线上仍具有较小的容量,因为电子负荷。

Registered内存的不同点是,使用registers(寄存器)将内存控制器与DRAMs(动态随机存储控制器)隔离开。这带来了更轻的电子负荷,因此这使得更多的内存条可以相连接,实现了更大的内存容量。register(寄存器)一般会增加时钟或延迟,意味着registered内存相比于unbuffered内存条需要更长的访问时间。

这些不同意味着通常在设计时,系统所支持的unbuffered内存条比registered要少,这对于台式机来讲不是问题,服务器经常需要大容量的同存所以一般选用registered内存条。

Thursday, July 21, 2011

NIST SPHERE Header

SPHERE Header Example:

    NIST_1A
    1024
    database_id -s3 RM1
    database_version -s3 1.0
    utterance_id -s11 aks0_st0783
    channel_count -i 1
    sample_count -i 50074
    sample_rate -i 16000
    sample_min -i -2032
    sample_max -i 2708
    sample_n_bytes -i 2
    sample_byte_format -s2 01
    sample_sig_bits -i 16
    end_head

    (binary audio data follows)
Explanation:

    (type of header)
    (size of header)
    (databse type)
    (database version)
    (utterance identifier)
    (number of channels)
    (number of samples)
    (sample rate)
    (minimum amplitude)
    (maximum amplitude)
    (number of bytes per sample)
    (byte format:01: little endian; 10: big endian)
    (number of bits per sample)
    (ends the header)

    (signed short integer-valued data)

Ref:
http://www.isip.piconepress.com/projects/speech/software/tutorials/production/fundamentals/v1.0/section_02/s02_01_p04.html

http://www.ldc.upenn.edu/Catalog/readme_files/atis3/wav_spec.html


File: wav_spec.doc, updated 07/22/94

(Note: the waveform files in this distribution have been compressed using embedded Shorten compression. The header information below does not reflect the compression. Please look at the headers of one of the actual waveform files on Disc 17-2.1 or 17-3.1 for a sample header.)

MADCOW ATIS3 Speech Waveform (.wav) File Type Specifications

MADCOW ATIS speech waveform files are to be formatted using the NIST SPHERE header structure.
The NIST SPHERE header is an object-oriented, 1024-byte blocked, ASCII structure which is prepended to the waveform data. The header is composed of a fixed-format portion followed by an object-oriented variable portion. The fixed portion is as follows:
NIST_1A<new-line>
   1024<new-line>
The first line specifies the header type and the second line specifies the header length. Each of these lines are 8 bytes long (including new-line) and are structured to identify the header as well as allow those who do not wish to read the subsequent header information to programmatically skip over it.The remaining object-oriented variable portion is composed of object-type-value "triple" lines which have the following format:
<LINE> ::= <TRIPLE><new-line> |
           <COMMENT><new-line> | 
           <TRIPLE><COMMENT><new-line> | 

  <TRIPLE> ::= <OBJECT><space><TYPE><space><VALUE><OPT-SPACES>

    <OBJECT> ::= <PRIMARY-SUBOBJECT> | 
                 <PRIMARY-SUBOBJECT><SECONDARY-SUBOBJECT>

    <PRIMARY-SUBOBJECT> ::= <ALPHA> | <ALPHA><ALPHA-NUM-STRING>
    <SECONDARY-SUBOBJECT> ::= _<ALPHA-NUM-STRING> | 
                              _<ALPHA-NUM-STRING><SECONDARY-SUBOBJECT>

    <TYPE> ::= -<INTEGER-FLAG> | -<REAL-FLAG> | -<STRING-FLAG>

      <INTEGER-FLAG> ::= i
      <REAL-FLAG> ::= r
      <STRING-FLAG> ::= s<DIGIT-STRING>
      
    <VALUE> ::= <INTEGER> | <REAL> | <STRING>  (depending on object type)

      <INTEGER> ::= <SIGN><DIGIT-STRING>
      <REAL> ::= <SIGN><DIGIT-STRING>.<DIGIT-STRING> 

    <OPT-SPACES> ::= <SPACES> | NULL

  <COMMENT> ::= ;<STRING>  (excluding embedded new-lines)

<ALPHA-NUM-STRING> ::= <ALPHA-NUM> | <ALPHA-NUM><ALPHA-NUM-STRING>
<ALPHA-NUM> ::= <DIGIT> | <ALPHA>
<ALPHA> ::= a | ... | z | A | ... | Z
<DIGIT-STRING> ::= <DIGIT> | <DIGIT><DIGIT-STRING>
<DIGIT> ::= 0 | ... | 9
<SIGN> ::= + | - | NULL
<SPACES> ::= <space> | <SPACES><space>
<STRING> ::=  <CHARACTER> | <CHARACTER><STRING>
<CHARACTER> ::= char(0) | char(1) | ... | char(255)
Note: The grammar does not impose any limit on the number or order of objects.The single object "end_head" marks the end of the active header and the remaining unused header space is undefined.
The MADCOW headers must include the following fields:
Field                    Type     Description - Probable defaults marked in ()
-----------------------  -------  ---------------------------------------------
speaker_id               string   3-char. speaker ID from filename
speaking_mode            string   speaking mode ("spontaneous" or "read")
recording_date           string   beginning of recording date stamp of the
                                  form DD-MMM-YYYY.  Should contain the string
                                  "unknown" if this info is not available.
recording_time -s11      string   beginning of recording time stamp of the
                                  form HH:MM:SS.HH.  Should contain the string
                                  "unknown" if this info is not available.
microphone               string   microphone description ("Sennheiser HMD-410"
                                  or "Crown PCC-160")
utterance_id             string   utterance ID from filename of the form
                                  XXXUUSMP as described in the filenames 
                                  specification document.
database_id              string   database (corpus) identifier ("atis3")
database_version         string   database (corpus) revision ("1.0")
channel_count            integer  number of channels in waveform ("1")
speaker_session_number   string   1-char. scenario-session ID from filename
sample_count             integer  number of samples in waveform
sample_max               integer  maximum sample value in waveform
sample_min               integer  minimum sample value in waveform
sample_rate              integer  waveform sampling rate ("16000")
sample_n_bytes           integer  number of bytes per sample ("2")
sample_byte_format       string   byte order (MSB/LSB -> "10" or 
                                  LSB/MSB -> "01")
sample_sig_bits          integer  number of significant bits in each sample
                                  ("16")
session_utterance_number integer  base-10 version of "speaker_sentence_number"
speaker_sentence_number  string   2-character query within scenario-session
                                  (base 36) from filename
end_head                 none     end of header identifier 
Note: Although these fields are mandatory, you may include additional local fields if you wish. If you do add fields, please email us the field names and types so that we can add them to our library.Hypothetical ATIS3 header:
NIST_1A
   1024
speaker_id -s3 z01                     (speaker ID "z01")
speaking_mode -s11 spontaneous         (spontaneous speaking mode)
recording_date -s11 17-APR-1993        (date of beginning of recording)
recording_time -s11 10:23:39.79        (time of beginning of recording)
microphone -s18 Sennheiser HMD-410     (microphone description)
utterance_id -s8 z010b1ss              (utterance ID from filename)
database_id -s5 atis3                  (corpus ID "atis3")
database_version -s3 1.0               (utterance release "1.0")
channel_count -i 1                     (single-channel waveform)
speaker_session_number -s1 1           (scenario-session 1 for speaker)
sample_count -i 215040                 (number of samples in waveform)
sample_max -i 1115                     (maximum sample value)
sample_min -i -1479                    (minimum sample value)
sample_rate -i 16000                   (16 kHz. sampling rate)
sample_n_bytes -i 2                    (2-bytes per sample)
sample_byte_format -s2 10              (MSB/LSB byte order)
sample_sig_bits -i 16                  (16 significant bits per sample)
session_utterance_number -i 11         (scenario-session query 11, base 10)
speaker_sentence_number -s3 0b         (scenario-session query 0b, base 36)
end_head
The speech waveform data follows the header and should contain single-channel 16-bit linear quantized samples at 16kHz. sample rate. There should be no "gain normalization" or post-processing of the the waveform data.

ElectricityTexas: Electricity Offers

ElectricityTexas: Electricity Offers

酷壳 – CoolShell.cn

酷壳 – CoolShell.cn

Good blog for learning programming


recommended by my friend

Wednesday, July 20, 2011

Speech Lab. Speech

Speech Lab. Speech: " Spoken Language Processing Lab."

Spoken Language Processing Lab.

scrunch

scrunch

vt. 碾碎, 压碎
Coldness, dread, worrying my thesis, all inundated me, making my whole body scrunch more and more closely, then finally became a reverse big question mark.
冷漠,恐惧,担心着我的论文,我被它淹没了,使我全身碾碎,然后变成了大问号

Monday, July 18, 2011

__FILE__, __LINE_, __FUNCTION__, __DATE__, __TIME__,__TIMESTAMP__

Q: What are '__FILE__' and '__LINE__'?

A: '__FILE__' and '__LINE__' are predefined macros and part of the C/C++ standard. During preprocessing, they are replaced respectively by a constant string holding the current file name and by a integer representing the current line number.

There are other preprocessor variables including:
  • '__DATE__' -> a string literal of the form "Mmm dd yyyy"
  • '__TIME__' -> a string literal of the form "hh:mm:ss"
  • '__TIMESTAMP__' -> a string literal of the form "Mmm dd yyyy hh:mm:ss"
  • '__FUNCTION__' -> a string literal which contains the function name (this is part of C99, the new C standard and not all C++ compilers support it)

Linux软件下载源码编程文章资料周立发

关键词跟踪    调试    _FILE_    _LINE_                                          

作为一个Linux系统下的C程序员,你可能发现调试程序是个比较麻烦的工作,虽然已经有gdb,kgdb等专业的调试软件,但如果对这些软件运用不熟练是根本达不到调试程序找出bug的目的的。又或者你对gdb已经很熟了,但运行gdb开始调试后在哪里设置断点成了你头痛的问题?当然,你可以从程序开始就以单步运行step by step来调试程序,但这会耗去你很多时间。
如果你能很好地跟踪并记录程序的运行情况,那么一切将变得简单。下面我以一个实例说明我是如何操作的:
首先我有一个程序主体main,其代码如下:
//////////////////////////////trace.c 开始///////////////////////////////////////////
/*********************************************************************
*filename: trace.c
*purpose: demonstrate how to trace program easily. We'll
*         get every source filename, function-name, and the
*         current line number wrote into a stream. The stream
*         can be a file descriptor or stdout
*wrote by: zhoulifa(zhoulifa@163.com) 周立发(http://zhoulifa.bokee.com)
*date time:2005-11-30 00:30
*Note: 任何人可以任意复制代码并运用这些代码,当然包括你的商业用途
*                         但请遵循GPL      
*********************************************************************/

#include "global.h"
#include "MyFuncOne.h"
#include "MyFuncTwo.h"

int x;

int main(int argc, char ** argv)
{
    x = 5;
    dump(stdout, "now: x=%d", x);
    MyFuncOne();
    MyFuncTwo();
    dump(stdout, "now: x=%d", x);
    return 0;
}
//////////////////////////////trace.c 结束///////////////////////////////////////////

这个main里面引用了global.h,MyFuncOne.h,MyFuncTwo.h等,global.h里面是一个宏定义,定义了dump宏,其内容如下:
//////////////////////////////global.h 开始///////////////////////////////////////////
#ifndef GLOBAL_H
    #define GLOBAL_H
    #include "dump.h"

/*********************************************************************
*filename: global.h
*purpose: dump function declare
*wrote by: zhoulifa(zhoulifa@163.com) 周立发(http://zhoulifa.bokee.com)
*date time:2005-11-30 00:30
*Note: 任何人可以任意复制代码并运用这些代码,当然包括你的商业用途
*                         但请遵循GPL      
*********************************************************************/
    #ifdef DEBUG
        #define dump(fp, x...)  debug_print(fp, __FILE__, __LINE__, __FUNCTION__, ##x);
    #else
        #define dump(fp, x...)
    #endif

#endif
//////////////////////////////global.h 结束///////////////////////////////////////////
global.h这里又引用了dump.h,其内容稍后再贴出来。
MyFuncOne.h和MyFuncTwo.h分别定义了两个函数MyFuncOne和MyFuncTwo,其内容如下:
//////////////////////////////MyFuncOne.h 开始///////////////////////////////////////////
#ifndef MYFUNC_ONE_H
    #define MYFUNC_ONE_H
    #include "global.h"
/*********************************************************************
*filename: MyFuncOne.h
*purpose: MyFuncOne function declare
*wrote by: zhoulifa(zhoulifa@163.com) 周立发(http://zhoulifa.bokee.com)
*date time:2005-11-30 00:30
*Note: 任何人可以任意复制代码并运用这些代码,当然包括你的商业用途
*                         但请遵循GPL      
*********************************************************************/
    void MyFuncOne();
#endif
//////////////////////////////MyFuncOne.h 结束///////////////////////////////////////////

//////////////////////////////MyFuncTwo.h 开始///////////////////////////////////////////
#ifndef MYFUNC_TWO_H
    #define MYFUNC_TWO_H
    #include "global.h"
/*********************************************************************
*filename: MyFuncTwo.h
*purpose: MyFuncTwo function declare
*wrote by: zhoulifa(zhoulifa@163.com) 周立发(http://zhoulifa.bokee.com)
*Note: 任何人可以任意复制代码并运用这些代码,当然包括你的商业用途
*                         但请遵循GPL      
*********************************************************************/
    void MyFuncTwo();
#endif
//////////////////////////////MyFuncTwo.h 结束///////////////////////////////////////////

//////////////////////////////MyFuncOne.c 开始///////////////////////////////////////////
#include "MyFuncOne.h"

extern int x;
/*********************************************************************
*filename: MyFuncOne.c
*purpose: MyFuncOne function instance
*wrote by: zhoulifa(zhoulifa@163.com) 周立发(http://zhoulifa.bokee.com)
*date time:2005-11-30 00:30
*Note: 任何人可以任意复制代码并运用这些代码,当然包括你的商业用途
*                         但请遵循GPL      
*********************************************************************/
void MyFuncOne()
{
    x *= -2;
    dump(stdout, "MyFuncOne, now: x=%d", x);
}
//////////////////////////////MyFuncOne.c 结束///////////////////////////////////////////

//////////////////////////////MyFuncTwo.c 开始///////////////////////////////////////////
#include "MyFuncTwo.h"

extern int x;
/*********************************************************************
*filename: MyFuncTwo.h
*purpose: MyFuncOne function declare
*wrote by: zhoulifa(zhoulifa@163.com) 周立发(http://zhoulifa.bokee.com)
*date time:2005-11-30 00:30
*Note: 任何人可以任意复制代码并运用这些代码,当然包括你的商业用途
*                         但请遵循GPL      
*********************************************************************/
void MyFuncTwo()
{
    x++;
    dump(stdout, "MyFuncTwo, now: x=%d", x);
}
//////////////////////////////MyFuncTwo.c 结束///////////////////////////////////////////

现在该是时候说dump了,先看看其实现:
//////////////////////////////dump.h 开始///////////////////////////////////////////
#ifndef DUMP_H
    #define DUMP_H
    #include <sys/param.h>
    #include <stdio.h>
    #include <stdarg.h>
    #include <time.h>
/*********************************************************************
*filename: dump.h
*purpose: debug_print function declare
*wrote by: zhoulifa(zhoulifa@163.com) 周立发(http://zhoulifa.bokee.com)
*date time:2005-11-30 00:30
*Note: 任何人可以任意复制代码并运用这些代码,当然包括你的商业用途
*                         但请遵循GPL      
*********************************************************************/
    void debug_print(FILE * fp, const char * filename, const int line, const char * funcname, char *fmt, ...);
#endif
//////////////////////////////dump.h 结束///////////////////////////////////////////

//////////////////////////////dump.c 开始///////////////////////////////////////////
#include "dump.h"

/*********************************************************************
*filename: dump.c
*purpose: debug_print function instance
*wrote by: zhoulifa(zhoulifa@163.com) 周立发(http://zhoulifa.bokee.com)
*date time:2005-11-30 00:30
*Note: 任何人可以任意复制代码并运用这些代码,当然包括你的商业用途
*                         但请遵循GPL      
*********************************************************************/
void debug_print(FILE * fp, const char * filename, const int line, const char * funcname, char *fmt, ...)
{
    char buf[1024];
    time_t t;
    struct tm * now;
    va_list ap;

    time(&t);
    now = localtime(&t);
    va_start(ap, fmt);
    fprintf(fp, "%04d-%02d-%02d %02d:%02d:%02d -- %s(%d):%s DEBUG:@\"", now -> tm_year + 1900, now -> tm_mon + 1, now -> tm_mday, now -> tm_hour, now -> tm_min, now -> tm_sec, filename, line, funcname);
    vsprintf(buf, fmt, ap);
    fprintf(fp, "%s\"@\n", buf);
    va_end(ap);
}
//////////////////////////////dump.c 结束///////////////////////////////////////////

大家一定注意到:这个程序和大家一般写的程序并无大的区别,除了__FILE__, __LINE__, __FUNCTION__等几个宏和dump宏,__FILE__, __LINE__, __FUNCTION__是编译的时候已经内置了的几个宏,用来表明当前程序运行到了哪个源文件的哪一行,同时表明当前在哪个函数里面。而我们定义一个dump宏就是用来把这些信息送到一个文件句柄去。比如你的日志文件。这样,在任何程序需要的地方都可以加上一句dump来把需要的调试信息记录下来。
比如编译上述程序:
gcc -DDEBUG trace.c dump.c MyFuncOne.c MyFuncTwo.c -o trace
然后运行程序可以得到如下结果:
2005-11-30 00:40:38 -- trace.c(22):main DEBUG:@"now: x=5"@
2005-11-30 00:40:38 -- MyFuncOne.c(15):MyFuncOne DEBUG:@"MyFuncOne, now: x=-10"@
2005-11-30 00:40:38 -- MyFuncTwo.c(15):MyFuncTwo DEBUG:@"MyFuncTwo, now: x=-9"@
2005-11-30 00:40:38 -- trace.c(25):main DEBUG:@"now: x=-9"@
第一行:显示在trace.c源文件的第22行处,即main函数内打印出:now: x=5;
第二行:显示在MyFuncOne.c源文件的第15行处,即MyFuncOne函数内打印出:MyFuncOne, now: x=-10;
第三行:显示在MyFuncTwo.c源文件的第15行处,即MyFuncTwo函数内打印出:MyFuncTwo, now: x=-9;
第四行:显示在trace.c源文件的第25行处,即main函数内打印出:now: x=-9;

如果程序加多点dump,则程序运行到了哪里出了问题就会一目了然了。

Saturday, July 16, 2011

二叉树

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

#define MAX_TREE_SIZE  100

typedef struct BiTNode {
            char data;
            struct BiTNode * lchild;
            struct BiTNode * rchild;
}BiTNode, *BiTree;

//函数声明
void Print(BiTree &root);
void Selection(int sel,BiTree &root);
void ReadExPreOrder(BiTree &root);
void PrintExPreOrder(BiTree root);
void PostOrderTraverse(BiTree T);

//主函数
void main()   {
           
            BiTree root=NULL; //初始化根结点
   
            Print(root);
            while (true)   {
                        printf("\nPress enter to continue.........");
                        getchar();
                        system("cls");
                        Print(root);
            }

}


void Print(BiTree &root)    {
  //提示
            int sel;
            printf("使用说明:本程序可实现二叉链表方式存储的二叉树,输入为扩展先序遍历序列.\n");
            printf("---------------------\n");
            printf("1.输入扩展先序遍历序列并建立对应的二叉树.\n");
            printf("2.打印当前的二叉树的扩展先序遍历序列.\n");
            printf("3.后序遍历当前的二叉树并打印遍历序列.\n");
            printf("4.按其它任意键退出.\n");
            printf("---------------------\n");

            printf("请选择你要的操作:");
            scanf("%d", &sel);
            getchar();
            Selection(sel, root);

}

void Selection(int sel, BiTree &root)       {
      //根据用户输入决定下一步骤
            switch (sel) {
                        case 1: ReadExPreOrder(root);
                                        break;
                        case 2: PrintExPreOrder(root);
                                        break;
                        case 3: PostOrderTraverse(root);
                                        break;
                        default: exit(0);
            }

}

void ReadExPreOrder(BiTree &root)       {
 //先序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针
            char ch;
            ch = getchar();
            if (ch == '.')
                        root = NULL;
            else {
                        root = (BiTree)malloc(sizeof(BiTNode));
                        root->data = ch;
                        ReadExPreOrder(root->lchild);
                        ReadExPreOrder(root->rchild);
            }
}

void PrintExPreOrder(BiTree root)           {

            char ch;
            if (root!=NULL)       {
                        ch = root->data;
                        printf("%c", ch);
                        PrintExPreOrder(root->lchild);
                        PrintExPreOrder(root->rchild);
            }
            else
                        printf(".");

}

void PostOrderTraverse(BiTree T) {

            BiTree stack[MAX_TREE_SIZE], p;
            int tag[MAX_TREE_SIZE],top=0;
            p = T;
            while(p || top != 0)    {
                        while(p)        {
                                    top++;
                                    stack[top]=p;
                                    tag[top]=0;
                                    p=p->lchild;//从根开始,左结点依次入栈
                        }
                        if(top> 0)   {
                          if(tag[top]==1){//表示是从该结点的右子树返回,则访问该结//
                                                p=stack[top];
                                                printf("%c", p->data);
                                                top--;
                                                p=NULL;//p指向NULL,则下次进入while循环时,不做左子//树入栈操作
                                    }
                                    else{ //表明是从该结点左子树返回,应继续访问其右子树
                                                p=stack[top];
                                                if(top> 0)  {
                                                            p=p->rchild;
                                                            tag[top]=1;  //表明该结点的右子树已访问
                                                }
                                    } //end of else
                        } //end of if
            }//end of while
}