2008年4月29日星期二

Lucene 简介

Lucene 简介

Lucene 是一个基于 Java 的全文信息检索工具包,它不是一个完整的搜索应用程序,而是为你的应用程序提供索引和搜索功能。Lucene
目前是 Apache Jakarta 家族中的一个开源项目。也是目前最为流行的基于 Java 开源全文检索工具包。

目前已经有很多应用程序的搜索功能是基于 Lucene 的,比如 Eclipse 的帮助系统的搜索功能。Lucene
能够为文本类型的数据建立索引,所以你只要能把你要索引的数据格式转化的文本的,Lucene 就能对你的文档进行索引和搜索。比如你要对一些
HTML 文档,PDF 文档进行索引的话你就首先需要把 HTML 文档和 PDF 文档转化成文本格式的,然后将转化后的内容交给 Lucene
进行索引,然后把创建好的索引文件保存到磁盘或者内存中,最后根据用户输入的查询条件在索引文件上进行查询。不指定要索引的文档的格式也使
Lucene 能够几乎适用于所有的搜索应用程序。

图 1 表示了搜索应用程序和 Lucene 之间的关系,也反映了利用 Lucene 构建搜索应用程序的流程:


图1. 搜索应用程序和 Lucene 之间的关系


回页首


索引和搜索

索引是现代搜索引擎的核心,建立索引的过程就是把源数据处理成非常方便查询的索引文件的过程。为什么索引这么重要呢,试想你现在要在大量的文档中搜索含有某个关键词的文档,那么如果不建立索引的话你就需要把这些文档顺序的读入内存,然后检查这个文章中是不是含有要查找的关键词,这样的话就会耗费非常多的时间,想想搜索引擎可是在毫秒级的时间内查找出要搜索的结果的。这就是由于建立了索引的原因,你可以把索引想象成这样一种数据结构,他能够使你快速的随机访问存储在索引中的关键词,进而找到该关键词所关联的文档。Lucene
采用的是一种称为反向索引(inverted
index)的机制。反向索引就是说我们维护了一个词/短语表,对于这个表中的每个词/短语,都有一个链表描述了有哪些文档包含了这个词/短语。这样在用户输入查询条件的时候,就能非常快的得到搜索结果。我们将在本系列文章的第二部分详细介绍
Lucene 的索引机制,由于 Lucene 提供了简单易用的
API,所以即使读者刚开始对全文本进行索引的机制并不太了解,也可以非常容易的使用 Lucene 对你的文档实现索引。

对文档建立好索引后,就可以在这些索引上面进行搜索了。搜索引擎首先会对搜索的关键词进行解析,然后再在建立好的索引上面进行查找,最终返回和用户输入的关键词相关联的文档。


回页首


Lucene 软件包分析

Lucene 软件包的发布形式是一个 JAR 文件,下面我们分析一下这个 JAR 文件里面的主要的 JAVA 包,使读者对之有个初步的了解。

Package: org.apache.lucene.document

这个包提供了一些为封装要索引的文档所需要的类,比如 Document, Field。这样,每一个文档最终被封装成了一个 Document 对象。

Package: org.apache.lucene.analysis

这个包主要功能是对文档进行分词,因为文档在建立索引之前必须要进行分词,所以这个包的作用可以看成是为建立索引做准备工作。

Package: org.apache.lucene.index

这个包提供了一些类来协助创建索引以及对创建好的索引进行更新。这里面有两个基础的类:IndexWriter 和 IndexReader,其中
IndexWriter 是用来创建索引并添加文档到索引中的,IndexReader 是用来删除索引中的文档的。

Package: org.apache.lucene.search

这个包提供了对在建立好的索引上进行搜索所需要的类。比如 IndexSearcher 和 Hits, IndexSearcher
定义了在指定的索引上进行搜索的方法,Hits 用来保存搜索得到的结果。


回页首


一个简单的搜索应用程序

假设我们的电脑的目录中含有很多文本文档,我们需要查找哪些文档含有某个关键词。为了实现这种功能,我们首先利用 Lucene
对这个目录中的文档建立索引,然后在建立好的索引中搜索我们所要查找的文档。通过这个例子读者会对如何利用 Lucene
构建自己的搜索应用程序有个比较清楚的认识。


回页首


建立索引

为了对文档进行索引,Lucene 提供了五个基础的类,他们分别是 Document, Field, IndexWriter,
Analyzer, Directory。下面我们分别介绍一下这五个类的用途:

Document

Document 是用来描述文档的,这里的文档可以指一个 HTML 页面,一封电子邮件,或者是一个文本文件。一个 Document
对象由多个 Field 对象组成的。可以把一个 Document 对象想象成数据库中的一个记录,而每个 Field 对象就是记录的一个字段。

Field

Field 对象是用来描述一个文档的某个属性的,比如一封电子邮件的标题和内容可以用两个 Field 对象分别描述。

Analyzer

在一个文档被索引之前,首先需要对文档内容进行分词处理,这部分工作就是由 Analyzer 来做的。Analyzer
类是一个抽象类,它有多个实现。针对不同的语言和应用需要选择适合的 Analyzer。Analyzer 把分词后的内容交给
IndexWriter 来建立索引。

IndexWriter

IndexWriter 是 Lucene 用来创建索引的一个核心的类,他的作用是把一个个的 Document 对象加到索引中来。

Directory

这个类代表了 Lucene 的索引的存储的位置,这是一个抽象类,它目前有两个实现,第一个是
FSDirectory,它表示一个存储在文件系统中的索引的位置。第二个是 RAMDirectory,它表示一个存储在内存当中的索引的位置。

熟悉了建立索引所需要的这些类后,我们就开始对某个目录下面的文本文件建立索引了,清单1给出了对某个目录下的文本文件建立索引的源代码。


清单 1. 对文本文件建立索引
package TestLucene;
import java.io.File;
import java.io.FileReader;
import java.io.Reader;
import java.util.Date;
import org.apache.lucene.analysis.Analyzer;
import org.apache.lucene.analysis.standard.StandardAnalyzer;
import org.apache.lucene.document.Document;
import org.apache.lucene.document.Field;
import org.apache.lucene.index.IndexWriter;
/**
* This class demonstrate the process of creating index with Lucene
* for text files
*/
public class TxtFileIndexer {
public static void main(String[] args) throws Exception{
//indexDir is the directory that hosts Lucene's index files
File indexDir = new File("D:\\luceneIndex");
//dataDir is the directory that hosts the text files that to be indexed
File dataDir = new File("D:\\luceneData");
Analyzer luceneAnalyzer = new StandardAnalyzer();
File[] dataFiles = dataDir.listFiles();
IndexWriter indexWriter = new IndexWriter(indexDir,luceneAnalyzer,true);
long startTime = new Date().getTime();
for(int i = 0; i < dataFiles.length; i++){
if(dataFiles[i].isFile() && dataFiles[i].getName().endsWith(".txt")){
System.out.println("Indexing file " +
dataFiles[i].getCanonicalPath());
Document document = new Document();
Reader txtReader = new FileReader(dataFiles[i]);
document.add(Field.Text("path",dataFiles[i].getCanonicalPath()));
document.add(Field.Text("contents",txtReader));
indexWriter.addDocument(document);
}
}
indexWriter.optimize();
indexWriter.close();
long endTime = new Date().getTime();

System.out.println("It takes " + (endTime - startTime)
+ " milliseconds to create index for the
files in directory "
+ dataDir.getPath());
}
}

在清单1中,我们注意到类 IndexWriter 的构造函数需要三个参数,第一个参数指定了所创建的索引要存放的位置,他可以是一个 File
对象,也可以是一个 FSDirectory 对象或者 RAMDirectory 对象。第二个参数指定了 Analyzer
类的一个实现,也就是指定这个索引是用哪个分词器对文挡内容进行分词。第三个参数是一个布尔型的变量,如果为 true
的话就代表创建一个新的索引,为 false
的话就代表在原来索引的基础上进行操作。接着程序遍历了目录下面的所有文本文档,并为每一个文本文档创建了一个 Document
对象。然后把文本文档的两个属性:路径和内容加入到了两个 Field 对象中,接着在把这两个 Field 对象加入到 Document
对象中,最后把这个文档用 IndexWriter 类的 add
方法加入到索引中去。这样我们便完成了索引的创建。接下来我们进入在建立好的索引上进行搜索的部分。


回页首


搜索文档

利用Lucene进行搜索就像建立索引一样也是非常方便的。在上面一部分中,我们已经为一个目录下的文本文档建立好了索引,现在我们就要在这个索引上进行搜索以找到包含某个关键词或短语的文档。Lucene提供了几个基础的类来完成这个过程,它们分别是呢IndexSearcher,
Term, Query, TermQuery, Hits. 下面我们分别介绍这几个类的功能。

Query

这是一个抽象类,他有多个实现,比如TermQuery, BooleanQuery, PrefixQuery.
这个类的目的是把用户输入的查询字符串封装成Lucene能够识别的Query。

Term

Term是搜索的基本单位,一个Term对象有两个String类型的域组成。生成一个Term对象可以有如下一条语句来完成:Term term
= new Term("fieldName","queryWord");
其中第一个参数代表了要在文档的哪一个Field上进行查找,第二个参数代表了要查询的关键词。

TermQuery

TermQuery是抽象类Query的一个子类,它同时也是Lucene支持的最为基本的一个查询类。生成一个TermQuery对象由如下语句完成:
TermQuery termQuery = new TermQuery(new
Term("fieldName","queryWord")); 它的构造函数只接受一个参数,那就是一个Term对象。

IndexSearcher

IndexSearcher是用来在建立好的索引上进行搜索的。它只能以只读的方式打开一个索引,所以可以有多个IndexSearcher的实例在一个索引上进行操作。

Hits

Hits是用来保存搜索的结果的。

介绍完这些搜索所必须的类之后,我们就开始在之前所建立的索引上进行搜索了,清单2给出了完成搜索功能所需要的代码。


清单2 :在建立好的索引上进行搜索
package TestLucene;
import java.io.File;
import org.apache.lucene.document.Document;
import org.apache.lucene.index.Term;
import org.apache.lucene.search.Hits;
import org.apache.lucene.search.IndexSearcher;
import org.apache.lucene.search.TermQuery;
import org.apache.lucene.store.FSDirectory;
/**
* This class is used to demonstrate the
* process of searching on an existing
* Lucene index
*
*/
public class TxtFileSearcher {
public static void main(String[] args) throws Exception{
String queryStr = "lucene";
//This is the directory that hosts the Lucene index
File indexDir = new File("D:\\luceneIndex");
FSDirectory directory = FSDirectory.getDirectory(indexDir,false);
IndexSearcher searcher = new IndexSearcher(directory);
if(!indexDir.exists()){
System.out.println("The Lucene index is not exist");
return;
}
Term term = new Term("contents",queryStr.toLowerCase());
TermQuery luceneQuery = new TermQuery(term);
Hits hits = searcher.search(luceneQuery);
for(int i = 0; i < hits.length(); i++){
Document document = hits.doc(i);
System.out.println("File: " + document.get("path"));
}
}
}

在清单2中,类IndexSearcher的构造函数接受一个类型为Directory的对象,Directory是一个抽象类,它目前有两个子类:FSDirctory和RAMDirectory.
我们的程序中传入了一个FSDirctory对象作为其参数,代表了一个存储在磁盘上的索引的位置。构造函数执行完成后,代表了这个IndexSearcher以只读的方式打开了一个索引。然后我们程序构造了一个Term对象,通过这个Term对象,我们指定了要在文档的内容中搜索包含关键词"lucene"的文档。接着利用这个Term对象构造出TermQuery对象并把这个TermQuery对象传入到IndexSearcher的search方法中进行查询,返回的结果保存在Hits对象中。最后我们用了一个循环语句把搜索到的文档的路径都打印了出来。好了,我们的搜索应用程序已经开发完毕,怎么样,利用Lucene开发搜索应用程序是不是很简单。

Solr

Solr 是一个可供企业使用的、基于 Lucene 的开箱即用的搜索服务器。对Lucene不熟?那么建议先看看下面两篇文档:

  实战Lucene,第 1 部分: 初识
Lucene:http://www.ibm.com/developerworks/cn/java/j-lo-lucene1/

  用Lucene加速Web搜索应用程序的开发:http://www.ibm.com/developerworks/cn/web/wa-lucene2/

  一、 solr介绍

  solr是基于Lucene
Java搜索库的企业级全文搜索引擎,目前是apache的一个项目。它的官方网址在http://lucene.apache.org/solr/
.solr需要运行在一个servlet 容器里,例如tomcat5.5.solr在lucene的上层提供了一个基于HTTP/XML的Web
Services,我们的应用需要通过这个服务与solr进行交互。

  二、 solr安装和配置

  关于solr的安装和配置,这里也有两篇非常好的文档,作者同时也是 Lucene Java 项目的提交人和发言人:

  使用Apache Solr实现更加灵巧的搜索:http://www.ibm.com/developerworks/cn/java/j-solr1/index.html

  http://www.ibm.com/developerworks/cn/java/j-solr2/index.html

  下面主要说说需要注意的地方。

  Solr的安装非常简单,下载solr的zip包后解压缩将dist目录下的war文件改名为solr.war直接复制到tomcat5.5的webapps目录即可。注意一定要设置solr的主位置。有三种方法。我采用的是在tomcat里配置java:comp/env/solr/home的一个JNDI指向solr的主目录(example目录下),建立/tomcat55/conf/Catalina/localhost/solr.xml文件。

value="D:/solr/solr" override="true" />

  观察这个指定的solr主位置,里面存在两个文件夹:conf和data.其中conf里存放了对solr而言最为重要的两个配置文件schema.xml和solrconfig.xml.data则用于存放索引文件。

  schema.xml主要包括types、fields和其他的一些缺省设置。

  solrconfig.xml用来配置Solr的一些系统属性,例如与索引和查询处理有关的一些常见的配置选项,以及缓存、扩展等等。

  上面的文档对这两个文件有比较详细的说明,非常容易上手。注意到schema.xml里有一个

url

  的配置,这里将url字段作为索引文档的唯一标识符,非常重要。

  三、 加入中文分词

  对全文检索而言,中文分词非常的重要,这里采用了qieqie庖丁分词(非常不错:))。集成非常的容易,我下载的是2.0.4-alpha2版本,其中它支持最多切分和按最大切分。创建自己的一个中文TokenizerFactory继承自solr的BaseTokenizerFactory.

/**

* Created by IntelliJ IDEA.

* User: ronghao

* Date: 2007-11-3

* Time: 14:40:59

* 中文切词 对庖丁切词的封装

*/

public class ChineseTokenizerFactory extends BaseTokenizerFactory {

/**

* 最多切分 默认模式

*/

public static final String MOST_WORDS_MODE = "most-words".

/**

* 按最大切分

*/

public static final String MAX_WORD_LENGTH_MODE = "max-word-length".

private String mode = null.

public void setMode(String mode) {

if (mode==null||MOST_WORDS_MODE.equalsIgnoreCase(mode)

|| "default".equalsIgnoreCase(mode)) {

this.mode=MOST_WORDS_MODE.

} else if (MAX_WORD_LENGTH_MODE.equalsIgnoreCase(mode)) {

this.mode=MAX_WORD_LENGTH_MODE.

}

else {

throw new IllegalArgumentException("不合法的分析器Mode
参数设置:" mode).

}

}

@Override

public void init(Map args) {

super.init(args).

setMode(args.get("mode")).

}

public TokenStream create(Reader input) {

return new PaodingTokenizer(input, PaodingMaker.make(),

createTokenCollector()).

}

private TokenCollector createTokenCollector() {

if( MOST_WORDS_MODE.equals(mode))

return new MostWordsTokenCollector().

if( MAX_WORD_LENGTH_MODE.equals(mode))

return new MaxWordLengthTokenCollector().

throw new Error("never happened").

}

}

Apache Solr

导言
说起Apache Lucene,可以说无人不知,无人不晓,但是说道Apache Solr,恐怕知道的不多。看看Apache Solr的说明:

Solr是一个基于Lucene java库的企业级搜索服务器,包含XML/HTTP,JSON API, 高亮查询结果,faceted
search(不知道该如何翻译,片段式搜索),缓存,复制还有一个WEB管理界面。Solr运行在Servlet容器中。所以Solr和Lucene的本质区别有以下三点:搜索服务器,企业级和管理。Lucene本质上是搜索库,不是独立的应用程序,而Solr是。Lucene专注于搜索底层的建设,而Solr专注于企业应用。Lucene不负责支撑搜索服务所必须的管理,而Solr负责。所以说,一句话概括Solr:
Solr是Lucene面向企业搜索应用的扩展。

在本篇文章中,我们先看看Solr向我们承诺了什么,或者说Solr宣称的特性们。

无废话Solr
Solr是一个拥有象WebService一样接口的独立运行的搜索服务器。你将能够通过HTTP协议以XML格式将文档放入搜索服务器(这个过程叫做索引),你能够通过HTTP协议的GET来查询搜索服务器并且得到XML格式的结果。Solr的特性包括:

高级的全文搜索功能
专为高通量的网络流量进行的优化
基于开放接口(XML和HTTP)的标准
综合的HTML管理界面
可伸缩性-能够有效地复制到另外一个Solr搜索服务器
使用XML配置达到灵活性和适配性
可扩展的插件体系

Solr使用Lucene并且扩展了它!
一个真正的拥有动态域(Dynamic Field)和唯一键(Unique Key)的数据模式(Data Schema)
对Lucene查询语言的强大扩展!
支持对结果进行动态的分组和过滤
高级的,可配置的文本分析
高度可配置和可扩展的缓存机制
性能优化
支持通过XML进行外部配置
拥有一个管理界面
可监控的日志
支持高速增量式更新(Fast incremental Updates)和快照发布(Snapshot Distribution)
Schema(模式)
定义域类型和文档的域
能够驱动智能处理
声明式的Lucene分析器规范
动态域能够随时增加域
拷贝域功能允许对一个域进行多种方式的索引,或者将多个域联合成一个可搜索的域
显式类型能够减少对域类型的猜测
能够使用外部的基于文件的终止词列表,同义词列表和保护词列表的配置
查询
拥有可配置响应格式(XML/XSLT,JSON,Python,Ruby)的HTTP接口
高亮的上下文搜索结果
基于域值和显式查询的片段式搜索(Faceted Search)
对查询语言增加了排序规范
常量的打分范围(Constant scoring range)和前缀式查询-没有idf,coord,或者lengthNorm因子,对查询匹配的词没有数量限制
函数查询(Function Query)-通过关于一个域的数值或顺序的函数对打分进行影响
性能优化
核心
可插拔的查询句柄(Query Handler)和可扩展的XML数据格式
使用唯一键的域能够增强文档唯一性
能够高效地进行批量更新和删除
用户可配置的文档索引变化触发器(命令)
并发控制的搜索器
能够正确处理数字类型,从而能够进行排序和范围搜索
能够控制缺失排序域的文档
支持搜索结果的动态分组
缓存
可配置的查询结果,过滤器,和文档缓存实例
可插拔的缓存实现
后台缓存热启:当一个新的搜索器被打开时,可配置的搜索将它热启,避免第一个结果慢下来,当热启时,当前搜索器处理目前的请求(???)。
后台自动热启:当前搜索器缓存中最常访问的项目在新的搜索器中再次生成,能够在索引器和搜索器变化的时候高速缓存常查询的结果
快速和小的过滤器实现
支持自动热启的用户级别的缓存
复制
能够将使用rsync传输时改变的索引部分有效的发布
使用拉策略(Pull Strategy)来简化增加搜索器
可配置的发布间隔能够允许对时间线和缓存使用进行权衡选择
管理接口
能够对缓存使用,更新和查询进行综合统计
文本分析调试器,能够显示每个分析器每个阶段的结果
基于WEB的查询和调试输出:解析查询输出,Lucene的explain方法细节,能够解释为何某个文档打分低,被排除在结果中等等

2008年4月28日星期一

非洲为什么这么穷

非洲为什么这么穷? 标签: 非洲 奴隶 贫穷
15世纪末,在哥伦布刚刚到达美洲不久,全世界人口4亿左右,亚洲占一半以上,其余非洲有7000万人,欧洲有6000万人,美洲约4000万。到了18世纪初,美洲印第安人只剩下不到780万。经200年后,美洲印第安人目前人口约3600万。关于美洲印第安人口数量的变化,本人在其他文章里已有介绍,这里不多叙述。
20世纪初,欧洲人口达到4.5亿,亚洲10亿,非洲1亿多。亚非欧三个大洲,在500年间的人口变化,说明了什么?500年间,欧洲人口如果加上往美洲、澳洲的移民,增长8、9倍。亚洲增长5倍,非洲却增长有限,1倍都不到。又过了100年,到了21世纪初,非洲人口猛增到9亿以上,欧洲却增长缓慢,只达到7亿多。但是,非洲有三分之一的人口,处于每天收入一美元以下的绝对贫困。非洲的这个局面是如何造成的?
欧洲人到达美洲以后,首先造成美洲印第安人口的大量减少。为了获得廉价劳动力,欧洲人开始从非洲向美洲贩卖奴隶。这一行为,是造成非洲现在贫困的一个重要原因。据统计,欧洲人从非洲贩买的奴隶总数约2000万人,但是,这个数字是到达美洲奴隶主手中的数字,也就是成交的数字。在这个数字背后,非洲人口损失的数字要大得多。一般认为,在捕猎、集中、运输、贩卖的过程中,到达美洲奴隶主手中的一个奴隶背后,有4个奴隶的死亡。也就是说,400年的奴隶贸易,到达美洲2000万黑奴,共造成非洲的直接人口损失约1亿。
这样一个人口损失对非洲会造成什么影响?首先是生产力大大降低。基本上最好的劳动力都被欧洲人抓去作了奴隶,黑人为自己创造财富的能力消失殆尽;其次,人口繁殖能力下降。繁殖能力最旺盛的年龄段人口,大多被抓走或杀害,所以才会造成500年间非洲人口只增加了1倍不到;第三,文化传承断绝。非洲曾经也有灿烂的历史文化,但是,青壮年的消失,造成年龄断层,文化的延续被迫中断。而且,绝大多数人都在为逃避抓捕而躲藏,文化延续的工作根本无法继续;第四,部落冲突加剧。虽然欧洲人有先进的武器,但是,抓奴隶并非要打死人,欧洲人自己人手又不够,便鼓动各个黑人部落去抓其他部落的黑人,由此造成延续至今的部落血仇冲突。上述几个原因,使得非洲被迫远离世界各地文化、科学发展的重要阶段,人类一切最新的文明成果,几乎都与非洲无关。非洲除了供应奴隶,仿佛已经被世界遗忘。
欧洲废奴运动后,欧洲人追求财富的手段,并没有使得非洲摆脱灾难。废奴运动从理论上说,是因为启蒙思想传播的结果,其实并不完全如此。废奴运动得以实现的根本原因是,奴隶贸易的利润大大降低。原先运往美洲的奴隶,成本已经太高,于是,废奴运动后,欧洲人便开始把奴隶经济转移到非洲本土。加上非洲发现大量的金矿、钻石矿等,让黑人在非洲本土做奴隶,比贩卖到美洲要合算。由此,我们也就能够理解,当今非洲最富裕的国家南非,是全世界范围最后一个废除种族隔离制度的国家。
欧洲国家瓜分世界的野心,在非洲得到最充分的体现。最高峰的时候,非洲只剩下埃塞俄比亚这个唯一独立的国家。即便如此,墨索里尼还是短暂地占领了这块最后属于非洲人自己的土地。而且,墨索里尼的行为,得到了欧洲各国的认可。二次大战之后,伴随着殖民地独立运动,非洲国家也纷纷独立。但是,至今为止,非洲国家的边界,大多是欧洲殖民地当年留下的。欧洲人留下的边界,不顾非洲的历史,不顾非洲的民族,只顾相互之间的利益分配,造成很多民族的分裂,也给今天的非洲留下众多冲突的隐患。
把非洲瓜分完毕后,欧洲将非洲黑人变成各个宗主国自己的廉价劳动力。于是,贩卖奴隶造成的非洲人口数量低下,成为不利因素,欧洲便开始在非洲推动黑人人口增长。然而,人口的增长,目的只是就地变成奴役对象,非洲黑人基本上得不到受教育的机会,最终导致如今非洲人口猛增,教育水平低下,绝对贫困人口占三分之一的灾难性局面。
"钻石恒久远,一颗永流传",这个广告语在世界各地深入人心。很多年轻人结婚时,都要买一颗钻石。世界上最大的钻石产地在非洲,世界上最大的钻石生产、销售商却不属于非洲黑人。非洲钻石所获得的巨大利润,也不属于非洲人自己。因此,我反对购买非洲钻石。我们购买非洲钻石,等于是在帮助欧洲人,继续奴役非洲黑人。去年好莱坞的一部电影《血腥钻石》,则从另外一个角度,描述了钻石的罪恶。
随着殖民地时代的过去,亚洲、拉丁美洲独立国家,有一个鲜明的举动,就是将殖民地宗主国的财产收归国有,本国重要资源也由本国人民掌握。但是,这种情况在非洲却并不普遍,例如,非洲人口最多的国家尼日利亚,也是非洲石油拥有量最多的国家,尼日利亚经济在非洲排名第四,但同时也是非洲最穷的国家,三分之一绝对贫困的非洲人,集中在尼日利亚这一个国家。为什么?因为,尼日利亚的石油企业都属于西方石油公司。为什么?因为欧洲人野蛮殖民手段造成非洲文化的断裂,教育的贫乏,不像亚洲、拉丁美洲那样,至少还保留了一点自己的人才。非洲黑人普遍教育程度低下的状况,是欧洲殖民者直接造成的,至今还在危害着独立以后的非洲国家。
看看世界500年的历史,就会发现,欧洲人如今享受着舒适的生活,有多少是沾满血迹的财富,有多少是践踏别人生命的结果。当中国稍稍富裕一点,真心到非洲投资,帮助非洲人民共同富裕的时候,一些欧洲人居然说,中国人现在到非洲做的事情,同他们当年在非洲的殖民统治是一样的。亏他们说得出口,居然毫不脸红,毫不愧疚。欧洲人、美国人甚至胡说,中国企业在苏丹的投资,是造成达尔富尔地区人道主义灾难的原因,这也成为他们抵制北京奥运会的一个理由。斯皮尔伯格就是这样认为的。
只要我们了解一下非洲的历史,就会对欧美关于达尔富尔的言论感到愤慨。非洲最大的人道主义灾难,全部都是西方人直接或间接造成的,并且延续至今。中国历史上没有奴役过黑人,现在也没有欺负过黑人,而是真心和非洲黑人一起走上共同富裕的道路。欧美某些人针对中国在非洲的言论,正应了一句中国老话:天理何在。非洲大地上,该永远被钉上耻辱柱的,正是西方人自己。他们有过自我反省吗?

Lucene的简介

本文主要面向具体使用,适用于已熟悉java编程的lucene初学者。
1. Lucene的简介

1.1 Lucene 历史


org.apache.lucene包是纯java语言的全文索引检索工具包。
Lucene的作者是资深的全文索引/检索专家,最开始发布在他本人的主页上,2001年10月贡献给APACHE,成为APACHE基金jakarta的一个子项目。
目前,lucene广泛用于全文索引/检索的项目中。
lucene也被翻译成C#版本,目前发展为Lucene.Net(不过最近好象有流产的消息)。


1.2 Lucene 原理


lucene的检索算法属于索引检索,即用空间来换取时间,对需要检索的文件、字符流进行全文索引,在检索的时候对索引进行快速的检索,得到检索位置,这个位置记录检索词出现的文件路径或者某个关键词。
在使用数据库的项目中,不使用数据库进行检索的原因主要是:数据库在非精确查询的时候使用查询语言"like
%keyword%",对数据库进行查询是对所有记录遍历,并对字段进行"%keyword%"匹配,在数据库的数据庞大以及某个字段存储的数据量庞大的时候,这种遍历是致命的,它需要对所有的记录进行匹配查询。因此,lucene主要适用于文档集的全文检索,以及海量数据库的模糊检索,特别是对数据库的xml或者大数据的字符类型。


2.Lucene的下载和配置


2.1 Lucene的下载


lucene在jakarta项目中的发布主页:http://jakarta.apache.org/lucene/docs/index.html。以下主要针对windows用户,其它用户请在上面的地址中查找相关下载。


lucene的.jar包的下载(包括.jar和一个范例demo):
http://apache.oregonstate.edu/jakarta/lucene/binaries/lucene-1.4-final.zip


lucene的源代码下载:
http://www.signal42.com/mirrors/apache/jakarta/lucene/source/lucene-1.4-final-src.zip


lucene的api地址:http://jakarta.apache.org/lucene/docs/api/index.html


本文使用lucene版本:lucene-1.4-final.jar。


2.2 lucene的配置


首先请确定你的机子已经进行了java使用环境的基本配置,即确保在某个平台下能够运行java源代码,否则请查阅相关文档进行配置。
接下来进入lucene的配置:
普通使用者:在环境变量的CLASSPATH中添加lucene的位置。比如:"D:\java
\lucene-1.4-final\lucene-1.4-final.jar;"。
jbuilder使用者:在"Project"--"Project Properties"--"Required Libraries"进行添加。
Jsp使用者:也可以直接将lucene-1.4-final.jar文件放到\WEB-INF\classes下。


3. Lucene 的范例(Demo )


3.1 Demo说明


可以得到的Demo包括:lucene-demos-1.4-final、XMLIndexingDemo,lucene-demos-1.4-final中包括对普通文件和html文件的两种索引,XMLIndexingDemo针对xml文件的索引。他们的区别主要在于:对普通文件进行索引时只要对文件的全文进行索引,而针对html、xml文件时,对标签类型不能进行索引,在实现上:html、xml的索引需要额外的数据流分析器,以分析哪些内容有用哪些无用。因此,在后两者实现上,索引的时间额外开支,甚至超过索引本身时间,而检索时间没有区别。


以上Demo中,lucene-demos-1.4-final自带于lucene-1.4-final.zip中,XMLIndexingDemo的下载地址:
http://cvs.apache.org/viewcvs.cgi/jakarta-lucene-sandbox/contributions/XML-Indexing-Demo/


3.2 Demo的运行


首先将demo.jar的路径添加如环境变量的CLASSPATH中,例如:"D:\java\lucene-1.4-final\lucene-demos-1.4-final.jar;",同时确保已经添加lucene-1.4-final.jar。


然后进行文件的全文索引,在dos控制台中,输入命令"java
org.apache.lucene.demo.IndexFiles
{full-path-to-lucene}/src",后面的路径为所要进行索引的文件夹,例如:"java
org.apache.lucene.demo.IndexFiles c:\test"。


接着对索引进行检索,敲入"java
org.apache.lucene.demo.SearchFiles",在提示"Query:"后输入检索词,程序将进行检索列出检索得到的结果(检索词出现的文件路径)。

其他Demo的运行请参考\docs\demo.html。
在运行Demo后请阅读Demo的源代码以便深入学习。

Strassen矩阵乘法

Strassen矩阵乘法
矩阵乘法是线性代数中最常见的运算之一,它在数值计算中有广泛的应用。若A和B是2个n×n的矩阵,则它们的乘积C=AB同样是一个n×n的矩阵。A和B的乘积矩阵C中的元素C[i,j]定义为:

若依此定义来计算A和B的乘积矩阵C,则每计算C的一个元素C[i,j],需要做n个乘法和n-1次加法。因此,求出矩阵C的n2个元素所需的计算时间为0(n3)。

60年代末,Strassen采用了类似于在大整数乘法中用过的分治技术,将计算2个n阶矩阵乘积所需的计算时间改进到O(nlog7)=O(n2.18)。

首先,我们还是需要假设n是2的幂。将矩阵A,B和C中每一矩阵都分块成为4个大小相等的子矩阵,每个子矩阵都是n/2×n/2的方阵。由此可将方程C=AB重写为:

 (1)

由此可得:

C11=A11B11+A12B21 (2)

C12=A11B12+A12B22 (3)

C21=A21B11+A22B21 (4)

C22=A21B12+A22B22 (5)

如果n=2,则2个2阶方阵的乘积可以直接用(2)-(3)式计算出来,共需8次乘法和4次加法。当子矩阵的阶大于2时,为求2个子矩阵的积,可以继续将子矩阵分块,直到子矩阵的阶降为2。这样,就产生了一个分治降阶的递归算法。依此算法,计算2个n阶方阵的乘积转化为计算8个n/2阶方阵的乘积和4个n/2阶方阵的加法。2个n/2×n/2矩阵的加法显然可以在c*n2/4时间内完成,这里c是一个常数。因此,上述分治法的计算时间耗费T(n)应该满足:

这个递归方程的解仍然是T(n)=O(n3)。因此,该方法并不比用原始定义直接计算更有效。究其原因,乃是由于式(2)-(5)并没有减少矩阵的乘法次数。而矩阵乘法耗费的时间要比矩阵加减法耗费的时间多得多。要想改进矩阵乘法的计算时间复杂性,必须减少子矩阵乘法运算的次数。按照上述分治法的思想可以看出,要想减少乘法运算次数,关键在于计算2个2阶方阵的乘积时,能否用少于8次的乘法运算。Strassen提出了一种新的算法来计算2个2阶方阵的乘积。他的算法只用了7次乘法运算,但增加了加、减法的运算次数。这7次乘法是:

M1=A11(B12-B22)

M2=(A11+A12)B22

M3=(A21+A22)B11

M4=A22(B21-B11)

M5=(A11+A22)(B11+B22)

M6=(A12-A22)(B21+B22)

M7=(A11-A21)(B11+B12)

做了这7次乘法后,再做若干次加、减法就可以得到:

C11=M5+M4-M2+M6

C12=M1+M2

C21=M3+M4

C22=M5+M1-M3-M7

以上计算的正确性很容易验证。例如:

C22=M5+M1-M3-M7

=(A11+A22)(B11+B22)+A11(B12-B22)-(A21+A22)B11-(A11-A21)(B11+B12)

=A11B11+A11B22+A22B11+A22B22+A11B12

-A11B22-A21B11-A22B11-A11B11-A11B12+A21B11+A21B12

=A21B12+A22B22

由(2)式便知其正确性。

至此,我们可以得到完整的Strassen算法如下:

procedure STRASSEN(n,A,B,C);begin if n=2 then MATRIX-MULTIPLY(A,B,C)
else begin 将矩阵A和B依(1)式分块;
STRASSEN(n/2,A11,B12-B22,M1);
STRASSEN(n/2,A11+A12,B22,M2);
STRASSEN(n/2,A21+A22,B11,M3);
STRASSEN(n/2,A22,B21-B11,M4);
STRASSEN(n/2,A11+A22,B11+B22,M5);
STRASSEN(n/2,A12-A22,B21+B22,M6);
STRASSEN(n/2,A11-A21,B11+B12,M7);
;
end;
end;
其中MATRIX-MULTIPLY(A,B,C)是按通常的矩阵乘法计算C=AB的子算法。

Strassen矩阵乘积分治算法中,用了7次对于n/2阶矩阵乘积的递归调用和18次n/2阶矩阵的加减运算。由此可知,该算法的所需的计算时间T(n)满足如下的递归方程:

按照解递归方程的套用公式法,其解为T(n)=O(nlog7)≈O(n2.81)。由此可见,Strassen矩阵乘法的计算时间复杂性比普通矩阵乘法有阶的改进。

有人曾列举了计算2个2阶矩阵乘法的36种不同方法。但所有的方法都要做7次乘法。除非能找到一种计算2阶方阵乘积的算法,使乘法的计算次数少于7次,按上述思路才有可能进一步改进矩阵乘积的计算时间的上界。但是Hopcroft和Kerr(197l)已经证明,计算2个2×2矩阵的乘积,7次乘法是必要的。因此,要想进一步改进矩阵乘法的时间复杂性,就不能再寄希望于计算2×2矩阵的乘法次数的减少。或许应当研究3×3或5×5矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是O(n2.367)。而目前所知道的矩阵乘法的最好下界仍是它的平凡下界Ω(n2)。因此到目前为止还无法确切知道矩阵乘法的时间复杂性。关于这一研究课题还有许多工作可做。

广义表的定义

广义表

教学目的: 广义表的定义及存储结构

教学重点: 广义表的操作及意义

教学难点: 广义表存储结构

授课内容:

一、广义表的定义

广义表是线性表的推广,其表中的元素可以是另一个广义表,或其自身.

广义表的定义:

ADT GList{

数据对象:D={i=1,2,...,n>=0;ei(-AtomSet或ei(-GList,

AtomSet为某个数据对象}

数据关系:R1={<ei-1,ei>|ei-1,ei(-D,2=<i<=n}

基本操作:

InITGlist(&L);

操作结果:创建空的广义表L

CreateGList(&L,S);

初始条件:S是广义表的书写形式串

操作结果:由S创建广义表L

DestroyGlist(&L);

初始条件:广义表L存在

操作结果:销毁广义表L


CopyGlist(&T,L);

初始条件:广义表L存在

操作结果:由广义表L复制得到广义表T


GListLength(L);

初始条件:广义表L存在

操作结果:求广义表L的长度,即元素个数


GListDepth(L);

初始条件:广义表L存在

操作结果:求广义表L的深度


GlistEmpty(L);

初始条件:广义表L存在

操作结果:判断广义表L是否为空


GetHead(L);

初始条件:广义表L存在

操作结果:取广义表L的头


GetTail(L);

初始条件:广义表L存在

操作结果:取广义表L的尾


InsertFirst_GL(&L,e);

初始条件:广义表L存在

操作结果:插入元素e作为广义表L的第一元素


DeleteFirst_GL(&L,&e);

初始条件:广义表L存在

操作结果:删除广义表L的第一元素,并用e返回其值


Traverse_GL(L,VisIT());

初始条件:广义表L存在

操作结果:遍历广义表L,用函数VisIT处理每个元素


}ADT GList

广义表一般记作:LS=(a1,a2,...,an)

其中LS是广义表的名称,n是它的长度,ai可以是单个元素也可是广义表,分别称为原子和子表,当广义表非空时,称第一个元素a1为LS的表头称其余元素组成的广义表为表尾.

二、广义表的存储结构

广义表的头尾链表存储表示

typedef emnu{ATOM,LIST} ElemTag;

typedef struct GLNode{

ElemTag tag;

union{

AtomType atom;

struct{struct GLNode *hp,*tp;}ptr;

}

}

有A、B、C、D、E五个广义表的描述如下:

A=() A是一个空表,它的长度为零

B=(e) 列表B只有一个原子e,B的长度为1.

C=(a,(b,c,d)) 列表C的长度为2,两个元素分别为原子a和子表(b,c,d)

D=(A,B,C) 列表D的长度为3,三个元素都是列表,显然,将子表的值代入后,则有D=((),(e),(a,(b,c,d)))

E=(a,E) 这是一个递归的表,它的长度为2,E相当于一个无限的列表E=(a,(a,(a,...)))

上述五个广义表用以上的存储结构的存储映像如下:

欢迎转载,但请保留出处,本文章转自[华软网] 原文链接:http://www.hur.cn/program/C/c03/200511/5316.html

《数据结构》考试大纲

I 课程性质与设置目的:

  1. 本课程的性质和特点、在本专业中的地位、设置目的与作用

《数据结构》课程是网络教育考试的一门必修的专业基础课。这门课程的主要特点是实践性很强,不仅要学习基本理论知识,更要注重上机实践,通过上机实践验证算法的正确性,掌握和巩固所学理论知识。设立本门课程的目的是通过学习,使学生学会分析研究计算机加工的数据结构的特性,以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法,并初步了解对算法的时间分析和空间分析技术。另一方面,通过对本课程算法设计和上机实践的训练,还应培养学生的数据抽象能力和程序设计的能力,为后续课程,特别是软件课程打下坚实的知识基础。要求学生掌握各种常用数据结构的逻辑结构,存储结构及有关操作的算法。

二、本课程的基本要求

通过本课程的学习,学生应比较系统地从数据结构的逻辑结构、存储结构和运算三个方面去掌握线性表、栈、队列、串、数组、广义表、树、图和文件等常用的数据结构;并且掌握在各种常用的数据结构上实现得排序和查找算法,同时对算法的时间和空间复杂性有一定得分析能力;针对简单的应用问题,应能选择合适得数据结构及设计有效得算法解决之。这对于培养学生运用数据结构解决实际问题能力的培养有着重要的意义



II 课程内容与考核标准:

  1. 绪论

一、学习目的和要求

本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义。

本章要了解数据的抽象类型定义。理解算法在实际问题中的应用。重点掌握各种基本概念和术语、算法描述和分析的方法。

二、课程内容

      1. 什么是数据结构

      2. 基本概念和术语

      3. 抽象数据类型的表示与实现

      4. 算法和算法分析

三、考核知识点

              1. 合适的数据结构在解决实际应用问题中的关键性;以及学习《数据结构》的意义。

              2. 数据、数据元素、数据项、数据结构等基本概念。

              3. 数据结构的四种逻辑结构和两种存储结构表示方法。

              4. 抽象数据类型的表示和实现

              5. 算法的五个特点。

              6. 算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。

              7. 算法描述和算法分析的方法,对于一般算法能分析出时间复杂度。

四、考核要求

                1. 识记

  1. 数据结构的基本概念和术语。

  2. 合适的数据结构在解决实际应用问题中的关键性,以及学习《数据结构》的意义。

  3. 数据结构的四种逻辑结构和两种存储结构表示方法。

                1. 领会

  1. 算法的描述和分析:算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度



  1. 线性表

一、学习目的和要求

本章的目的是介绍线性表的逻辑结构和各种存储表示方法,以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。要求在熟悉这些内容的基础上,能够针对具体应用问题的要求和性质,选择合适的存储结构设计出相应的有效算法,解决与线性表相关的实际问题。

本章重点是熟练掌握顺序表和单链表上实现的各种基本运算及相关的时间性能分析,难点是在循环链表和双向链表存储结构中各种基本运算的实现。

二、课程内容

      1. 线性表的类型定义

      2. 线性表的顺序表示和实现

      3. 线性表的链式表示和实现

三、考核知识点

              1. 线性表的类型定义

              2. 顺序表的含义及特点,顺序表上的插入、删除操作及其平均时间性能分析

              3. 链式表示和实现,单链表、双链表、循环链表链接方式上的区别;

              4. 单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。

              5. 双向链表的定义和相关算法。

              6. 顺序表和链表的比较,以及如何选择其一作为其存储结构才能取得较优的时空性能。

四、考核要求

                1. 识记

  1. 线性表的逻辑结构特征;

  2. 线性表上定义的基本运算,并利用基本运算构造出较复杂的运算。

                1. 领会

  1. 顺序表和链表的比较,各自的优缺点。

  2. 针对线性表上所需要执行的主要操作,知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能。

                1. 综合应用

      1. 顺序表的含义及特点,顺序表上的插入、删除操作及其平均时间性能分析。

      2. 单链表、双链表、循环链表链接方式上的区别;

      3. 单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。

      4. 双链表的定义和相关算法。



  1. 栈和队列

一、学习目的和要求

本章的目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算。要求在掌握栈和队列的特点的基础上,懂得在什么样的情况下使用栈或队列。

本章重点是掌握栈和队列在两种存储结构上实现的基本运算,难点是循环队列中对边界条件的处理

二、课程内容

      1. 栈的应用举例

第四节 队列

三、考核知识点

              1. 栈的抽象数据类型的定义

              2. 栈的表示和实现

              3. 栈的简单应用

              4. 抽象数据类型队列的定义

              5. 队列的链式表示和实现

              6. 队列的顺序表示和实现

四、考核要求

                1. 领会

  1. 栈和队列的特点,栈和队列各自的使用情况。

                1. 综合应用

                  1. 栈的逻辑结构特点,栈与线性表的异同。

                  2. 顺序栈和链栈上实现进栈、退栈等基本算法。

                  3. 利用栈解决简单的实际问题。

                  4. 队列逻辑结构特点,队列与线性表的异同。

                  5. 顺序队列(主要是循环队列)和链队列上实现的入队、出队等基本算法。

                  6. 顺序队列的“假溢出”现象及其采用循环队列进行解决的方法。



一、学习目的和要求

本章的目的是介绍串的逻辑结构、存储结构及其串上的基本运算。本章重点是掌握串的基本概念和三种表示方法,这也是难点。

二、课程内容

      1. 串类型的定义

      2. 串的表示和实现

三、考核知识点

              1. 串的定义、空串、空格串、子串、主串、串相等。

              2. 串的基本操作。

              3. 串的顺序存储结构及在顺序存储结构下基本操作的实现。

              4. 串的堆分配存储表示及其在堆分配存储结构下基本操作的实现。

              5. 串的链式存储表示

四、考核要求

                1. 领会

  1. 串的有关概念及其基本运算

                1. 简单应用

  1. 串的三种存储表示

  2. 使用串解决与串相关的简单的应用问题



  1. 数组和广义表

一、学习目的和要求

本章的目的是介绍多维数组的逻辑结构特征及其存储方式,特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念,要求熟悉这些内容。

本章重点是熟悉多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其表头表尾的运算,难点是稀疏矩阵的压缩存储表示下转置运算。

二、课程内容

      1. 数组的定义

      2. 数组的顺序表示和实现

      3. 矩阵的压缩存储

      4. 广义表的定义

      5. 广义表的存储结构

三、考核知识点

              1. 数组的顺序存储结构。

              2. 二维数组的按行存储及按列存储和计算数组元素的地址计算公式。

              3. 矩阵的压缩存储、特殊矩阵的表示。

              4. 广义表的定义和操作(HEADTAIL)

              5. 广义表的2种存储结构

四、考核要求

                1. 领会

  1. 多维数组的逻辑结构特征

  2. 多维数组的顺序存储结构及其地址计算方式

  3. 特殊矩阵和稀疏矩阵的概念

  4. 稀疏矩阵的压缩存储方式——三元组表

  5. 稀疏矩阵的两种转置运算算法

  6. 广义表的概念、广义表和线性表的联系

  7. 广义表表头和表尾的概念及广义表两个特殊的基本运算,取表头和取表尾。

  8. 广义表的两种存储结构



  1. 树和二叉树

一、学习目的和要求

本章的目的是介绍二叉树的定义、性质、存储结构、遍历、线索化,树的定义、存储结构、遍历、树和森林的转换及赫夫曼树及其赫夫曼编码等内容。本章重点是掌握二叉树及其二叉树的遍历。难点是掌握与树有关的简单应用。

二、课程内容

      1. 树的定义和基本术语

      2. 二叉树

      3. 遍历二叉树和线索二叉树

      4. 树和森林

第六节 赫夫曼树及其应用

三、考核知识点

              1. 树的定义和术语。

              2. 二叉树(完全二叉树、满二叉树)的定义和性质(结论)、二叉树的存储结构——顺序表示法和链表表示法。

              3. 二叉树的三种遍历方法及相应的递归算法。

              4. 二叉树线索化的目的及其实质。

              5. 树的存储表示法——孩子表示法、双亲表示法、孩子兄弟表示法。

              6. 树和森林及二叉树的转换方法。

              7. 树和森林的遍历

              8. 树的路径长度、树的带权路径长度、赫夫曼树(最优二叉树)的构造方法。

              9. 赫夫曼编码方法

四、考核要求

                1. 领会

  1. 树的逻辑结构特征

  2. 树的不同表示方法

  3. 树的常用术语及含义

  4. 二叉树线索化的目的及实质

  5. 在中序线索树中查找给定结点的中序前驱和中序后继的方法

  6. 树和森林与二叉树之间的转换方法

  7. 树的各种存储结构及其特点

  8. 树的遍历方法

                1. 简单应用

  1. 二叉树的定义及树与二叉树的差别

  2. 二叉树的性质,了解相应的证明方法

  3. 二叉树的两种存储结构、特点及适用范围

  4. 最优二叉树和前缀编码的概念及特点

  5. 赫夫曼算法的思想

  6. 根据给定的叶结点及其权值构造出相应的最优二叉树

  7. 根据最优二叉树构造对应的赫夫曼编码

                1. 综合应用

  1. 二叉树的三种遍历算法,理解其执行过程

  2. 根据不同的遍历方法,应能得出其相应的结点访问次序

  3. 以遍历算法为基础,设计有关算法解决简单的应用问题



III 有关说明与实施要求:

一、关于考核目标的说明

为了使考试内容和考试要求标准化,本大纲在列出考试内容的基础上,对各章节规定了考核目标。考核目标包含考核知识点和考核要求两项。辅导教师和学生可以通过对考核目标的阅读,进一步明确考试范围、内容和要求,从而可以更为系统地学习和把握教材。同时,考核目标还能够进一步明确考试命题范围,更正确地安排试题的知识能力层次和把握试题的难易程度。

本大纲在考核目标中,按照识记、领会、简单运用和综合运用等四个层次规定学生通过学习应该达到的能力层次要求。四个能力层次是递进等级关系。各能力层次的含义是:

1、识记:能够了解有关的名词、概念、知识的含义,并能正确认识和表述、选择和判断。

2、领会:在识记的基础上,能够比较全面地把握基本概念、基本事实、基本理论模型、基本方法,能把握有关概念、事实、理论模型、分析方法之间的区别和联系。并能根据考核的不同要求,做出正确的解释、说明和论述。

3、简单运用:在领会的基础上,能够运用本课程中规定的少量的知识点,分析和解释有关的一般的应用问题。例如,简单的算法设计和时间性能分析。

4、综合运用:指在简单运用的基础上,能够综合运用所学习过的多个知识点,分析和解决较复杂的应用问题,例如,设计较复杂的算法。


二、关于教材、参考教材和参考读物(根据课程的实际情况写内容)

1、教材:《数据结构》(C语言版)严蔚敏 吴伟民 编著,清华大学出版社1996年版。

2、参考教材

《数据结构》苑森淼等,吉林科学技术出版社。

《数据结构》黄刘生主编,全国高等教育自学考试指导委员会组编,经济科学出版社。

        1. 参考读物:《数据结构题集》严蔚敏 吴伟民著,清华大学出版社1999年版。


三、关于本门课程考试命题的若干规定

1、本门课程的命题考试,根据本大纲所规定的考试内容和考试目标来确定考试范围和考核要求。考试命题会覆盖各章,并适当突出重点章节,体现本课程的内容重点。

2、本课程在试题中对不同能力层次要求的分数比例一般为:识记占20%,领会占30%,简单应用占30%,综合运用占20%

3、试题合理安排难易度结构。试题难易度可分为:易、较易、较难和难四个等级。每份试卷中,不同难度试题的分数比例为:2332

4、本课程考试的题型,一般有填空、单项选择、简答、应用、算法设计等五种类型。

广义表的实现

实现广义表,具体没有做习题,感觉有些累了。呵呵。不知再往下看,脑细胞是否经得起折腾。先把源文件贴 上来。
//glist.h
//----------------------- 广义表 ---------------------------------------
typedef enum...{ATOM, LIST} ElemTag; //ATOM==0:原子,LIST==1:子表
typedef int AtomType; //原子的数据类型

typedef struct GLNode...{
ElemTag tag; //公共部分,区分原子节点和表节点
union...{ //原子节点和表节点的联合部分
AtomType atom; //原子节点的值
struct GLNode *hp; //表节点的表头指针
};
struct GLNode *tp; //相当于线形链表的next,指向下一个元素
}*GList;

//----------------- 基本操作的算法实现 -------------------------------
Status Sever(HString &str, HString &hstr)...{
//将非空串str分割成两部分:hstr为第一个','之前的自串,str为之后的子串
int n = StrLength(str), i=1, k=0; //k记尚未配对的左括号个数
HString ch;StrInit(ch);StrAssign(ch,"a");
for(i=1, k=0; i<=n&&ch.ch[0]!=','||k!=0;i++)...{ //搜索最外层的第一个','
SubString(ch,str,i,1);
if(ch.ch[0]=='(') ++k;
else if(ch.ch[0]==')')--k;
}
if(i<=n)...{ SubString(hstr,str,1,i-2); SubString(str,str,i,n-i+1); }
else...{StrCopy(hstr,str); ClearString(str);}
return OK;
}

Status CreateGList(GList &L, HString S)...{
//采用头尾链接存储结构,由广义表的书写形式串S创建广义表L
HString emp; StrInit(emp); StrAssign(emp,"()");
GList p,q;
if( !StrCompare(S,emp) ) L=NULL; //创建空表
else...{
if(!(L=(GList)malloc(sizeof(GLNode)))) exit(OVERFLOW); //创建节点
if(StrLength(S)==1) ...{L->tag = ATOM; L->atom = *(S.ch);} //创建原子节点
else...{
L->tag = LIST; p=L;
HString sub,hsub; StrInit(sub); StrInit(hsub);
SubString(sub,S,2,StrLength(S)-2); //脱外层扩号
do...{
Sever(sub,hsub);
CreateGList(p->hp,hsub); q=p;
if(!StrEmpty(sub))...{
if(!(p=(GLNode *) malloc(sizeof(GLNode))))
exit(OVERFLOW);
p->tag = LIST; q->tp = p;
}
}while(!StrEmpty(sub));
q->tp = NULL;
}
}
return OK;
}

Status CopyGList(GList &T, GList L)...{
//L复制给T
if(!L) T=NULL;
else...{
if(!(T=(GList)malloc(sizeof(GLNode)))) exit(OVERFLOW);
T->tag = L->tag;
if(L->tag ==ATOM ) T->atom = L->atom;
else...{
CopyGList(T->hp, L->hp);
CopyGList(T->tp, L->tp);
}
}
return OK;
}

int GListDepth(GList L)...{
//求广义表的深度
if(!L) return 1;
if(L->tag==ATOM) return 0;
int max;
GList pp;
for(max=0,pp=L;pp;pp=pp->tp)...{
int dep = GListDepth(pp->hp);
if(dep>max) max= dep;
}
return max+1;
}

Status PrintGList(GList L)...{
//显示广义表
GList p = L;
if(!L) ...{printf("()"); return OK; }
if(L->tag== ATOM) printf("%c",L->atom);
else...{
printf("(");
while(p!=NULL)...{
PrintGList(p->hp);
p=p->tp;
if(p) ...{ printf(","); }
}
printf(")");
}
return OK;
}
2.

//hstring.h
//----------------- 串的堆分配存储表示 ---------------------------
typedef struct{
char *ch; //若是非空串,则按串长分配存储区,否则ch为NULL
int length; //串长度
}HString;

//----------------- 栈的基本操作的算法实现 --------------------------------
Status StrInit(HString &T){
//初始化串
T.ch=NULL; T.length=0;
return OK;
}

Status StrAssign(HString &T, char *chars){
//生成一个其值等于串常量chars的串T
//if(T.ch) free(T.ch); //释放原有的串空间
int len; char *c;
for(len=0, c=chars;*c;++len,++c); //求chars的长度i;
if(!len) {T.ch=NULL; T.length=0;}
else{
if( !(T.ch = (char *) malloc(len*sizeof(char) ) ))
exit(OVERFLOW);
for(int i=0;i<len;i++) T.ch[i] = chars[i];
T.ch[i]='\0'; //结尾加上\0
T.length = len;
}

return OK;
}

int StrLength(HString s){
//返回串长度
return s.length;
}

void StrPrint(HString s){
//打印串
for(int i=0;i<s.length;i++)
printf("%c",s.ch[i]);
printf("\n");
}

int Index(HString s,HString t, int pos){
//返回子串t在主串s中第pos个字符之后的位置。如不存在,则返回0
int i=pos,j=1;
while(i<=s.length && j<=t.length){
if(s.ch[i-1]==t.ch[j-1]) i++,j++;
else i=i-j+2,j=1;
}
if(j>t.length) return i-t.length;
else return 0;
}

int Next(HString s,int j){
//KMP模式匹配的next函数
if(j==1) return 0;

for(int k=j-1;k>1;k--){
for(int i=1;i<k;i++){
if(s.ch[i-1] != s.ch[j-k+i-1])
break;
}
if(i==k) break;
}
return k;
}

int Index_KMP(HString s,HString t, int pos){
//KMP算法
int i=pos,j=1;
while(i<=s.length && j<=t.length){
if(j==0 || s.ch[i-1]==t.ch[j-1]) i++,j++;
else j=Next(t,j);
}
if(j>t.length) return i-t.length;
else return 0;
}

Status SubString(HString &sub, HString s, int pos, int len){
//用sub返回串S的第pos个字符起长度为len的子串
if(pos<1 || pos>s.length || len<0 )
return ERROR;
if( len>s.length-pos+1 ) len=s.length-pos+1; //如果所取长度超过实际长度,输出实际长度
// if(sub.ch) free(sub.ch);
if(!len){ sub.ch=NULL; sub.length=0; }
else{
if( !(sub.ch = (char *) malloc(len*sizeof(char) ) ))
exit(OVERFLOW);
for(int i=0;i<len;i++) sub.ch[i] = s.ch[pos+i-1];
sub.ch[i]='\0'; //结尾加上\0
sub.length = len;
}
return OK;
}

Status ClearString(HString &s){
//清空s
if(s.ch) {
// realloc(s.ch,0);
s.ch=NULL;
}
s.length =0;
return OK;
}

int StrCompare(HString s,HString t){
//比较s,t
for(int i=0;i<s.length&& i<t.length;i++)
if(s.ch[i]!=t.ch[i]) return s.ch[i]-t.ch[i];
return s.length - t.length;
}

Status Concat(HString &t, HString s1, HString s2){
//用t返回由s1和s2联接而成的新串
//if(t.ch) free(t.ch);
if(!(t.ch=(char *)malloc((s1.length+s2.length)*sizeof(char))))
exit(OVERFLOW);
for(int i=0;i<s1.length;i++) t.ch[i]=s1.ch[i];
for(i=0;i<s2.length;i++) t.ch[i+s1.length]=s2.ch[i];
t.ch[s1.length+s2.length]='\0';
t.length = s1.length+s2.length;
return OK;
}

Status StrCopy(HString &t,HString s){
if(!(t.ch=(char *)malloc( (s.length)*sizeof(char))))
exit(OVERFLOW);
for(int i=0;i<s.length;i++) t.ch[i]=s.ch[i];
t.ch[s.length] = '\0';
t.length = s.length;
return OK;
}

Status StrEmpty(HString s){
return s.length==0;
return OK;
}