摘 要：
“数据结构”是一门专业技术基础课。它的教学要求是：学会分析研究计算机加工
的数据结构的特征，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其
相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，本课程
的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确
易读，符合软件工程的规范。
在学习中，先要学习程序设计课程的目的掌握设计程序的思路，学习会用计算机
语言编写程序，以实现所需要处理的任务。要正确处理算法与语法的关系，算法
是程序的核心、是灵魂，语法是外壳、是工具。不应把学习重. 点放在语法规则
上，语法是重要的，不掌握语法规则就无法编写出正确的程序。一定要把重点放
在解题的思路上，通过思考，和大量的阅读，来构造一个完整的程序。请记住：
重要的是学会编程，而不是背语法。
关键词 ：线性表，栈和队列，二叉树，图，查找，排序，二叉排序树的应用
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多
种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高
的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
一、数据结构的研究内容
在计算机科学中，数据结构是一门研究非数值计算的程序设计问题中计算机
的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这
些运算后所得到的新结构仍然是原来的结构类型。 “数据结构”作为一门独
立的课程在国外是从1968年才开始设立的。 1968年美国唐·欧·克努特教授开创
了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》
是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。“数据结构”
在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬
件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一
般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、
操作系统、数据库系统及其他系统程序的重要基础。 计算机是一门研究用
计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示，信
息的处理 。 而信息的表示和组织又直接关系到处理信息的程序的效率。
随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用
程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分
析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研
究的问题。众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，
这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是
数据结构的内容。数据的结构，直接影响算法的选择和效率。 计算机解决
一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个
适当的数学模型，然后设计一个解此数学模型的算法（Algorithm ），最后编出程
序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中
提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以
描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，
数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相
应的插入、删除和修改的算法 。也就是说，数据结构还需要给出每种结构类型
所定义的各种运算的算法。
二、数据结构的分类
数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构分别
为逻辑结构、存储结构（物理结构）和数据的运算。数据的逻辑结构是对数据
之间关系的描述，有时就把逻辑结构简称为数据结构。逻辑结构形式地定义为
（K ，R ）（或（D ，S ）），其中，K 是数据元素的有限集，R 是K 上的关系的有限集。 数据元素相互之间的关系称为结构。有四类基本结构：集合、线性
结构、树形结构、图状结构（网状结构）。树形结构和图形结构全称为非线性
结构。集合结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构
中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中
元素之间存在多对多关系。在图形结构中每个结点的前驱结点数和后续结点数可
以任意多个。 数据结构在计算机中的表示（映像）称为数据的物理（存储）
结构。它包括数据元素的表示和关系的表示。数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储
结构和链式存储结构。顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此
得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方
法，通常借助于程序设计语言中的数组来实现。链接存储方法：它不要求逻辑上
相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计
语言中的指针类型来实现。索引存储方法：除建立存储结点信息外，还建立附
加的索引表来标识结点的地址。散列存储方法：就是根据结点的关键字直接计
算出该结点的存储地址。 数据结构中，逻辑上（逻辑结构：数据元素之间
的逻辑关系）可以把数据结构分成线性结构和非线性结构。线性结构的顺序存储
结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存取的存
储结构。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不
连续。逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。
三、二叉排序树的应用
1. 主要模块：
1）主函数模块
Main()
{
建立n 个关键字的二叉排序树并输出；
从二叉树排序树T 中删除任意结点, 其关键字为key ；
在二叉树排序树T 中，插入一个结点t, 其关键字为key ；
在二叉排序树T 中递归查找关键字等于 key2 的数据元素；
}
2）创建二叉排序树模块
BiTree CreatBST(int n)
{
建立n 个关键字的二叉排序树；
从键盘输入调建立n 个关键字依次用InsertBST1（插入函数）；
返回根结点T ；
输出过程；
}
3）删除模块
DeleteNode(BiTree &T, int x)
{
从二叉树排序树T 中删除任意结点, 其关键字为x ；
可以实现删除根结点、叶子结点以及其它任意结点的功能；
}
4）插入模块
void InsertBST1(BiTree &T,BiTNode *s)
{
在二叉树排序树T 中，插入一个结点s(递归算法) ；
被CreatBST 函数调用；
}
5）查找模块
BiTree searchBST1(BiTree T,TElemType key)
{
在根指针T 所指二叉排序树中递归查找关键字等于 key 的数据元素；
若成功，返回指向该数据元素结点的指针；
否则返回空指针；
}
2. 部分程序代码：
void inorder_btree(BSTree root)// 中序遍历打印二叉排序树
{
BSTree p=root;
if(p!=NULL){
inorder_btree(p->left );
coutkey
inorder_btree(p->right );
}
}
int searchBST(BSTree t,KeyType key)//查找
{
if(key==t->key)
return 1;
if(t==NULL)
return 0;
if(keykey)
return searchBST(t->left,key);
else
return searchBST(t->right,key);
}
BSTree deleteBST(BSTree tptr,KeyType key)//删除
{
BSTree p,tmp,parent=NULL;
p=tptr;
while(p)
{
if(p->key==key)
break;
parent=p;
p=(key
key)?p->left:p->right;
}
if(!p) return NULL;
tmp=p;
if(!p->right&&!p->left) /*p的左右子树都为空*/
{
if(!parent) //要删根，须修改根指针
tptr=NULL;
else if(p==parent->right)
parent->right=NULL;
else
parent->left=NULL;
free(p);
}
else if(!p->right) //p的右子树为空，则重接p 的左子树
{
p=p->left;
if(!parent) //要删根，须修改根指针
tptr=p;
else if(tmp==parent->left)
parent->left=p;
else
parent->right=p;
free(tmp);
}
else if(!p->left) //的左子树为空，则重接p 的左子树
{
p=p->right;
if(!parent) //要删根，须修改根指针
tptr=p;
else if(tmp==parent->left)
parent->left=p;
else
parent->right=p;
free(tmp);
}
else if(p->right&&p->left) //p有左子树和右子树，用p 的后继覆盖p
然后删去后继
{ //另有方法：用p 的前驱覆盖p 然后删去前驱||
合并p 的左右子树
parent=p; //由于用覆盖法删根，则不必特殊考虑删根
p=p->right;
while(p->left)
{
parent=p;
p=p->left;
}
tmp->key=p->key;
if(p==parent->left)
parent->left=NULL;
else
parent->right=NULL;
free(p);
}
return tptr;
}
int main()
{
KeyType key;
int flag,test;
char cmd;
BSTree root;
do
{
cout
cout
cout
cout
cout
cout
flag=0;
do
{
if(flag!=0)
cout
fflush(stdin);
cin>>cmd;
flag++;
}while(cmd!='c'&&cmd!='C'&&cmd!='a'&&cmd!='A');
if(cmd=='c'||cmd=='C')
{
cout
root=createBST();
do
{
flag=0;
cout
inorder_btree(root);
cout
cout
作:**************"
cout
cout
cout
cout
cout
cout
cout
***"
do{
if(flag!=0)
cout
fflush(stdin);
scanf("%c",&cmd);
flag++;
}
3. 测试用例：
1, 程序运行时菜单显示如下：
当输入的二叉树序列为：{2,6,9,8,4}时，创建二叉排序树，并输出结果如下：
参考文献：《数据结构课程设计》严蔚敏、吴伟民著。清华大学出版社。1997.4
摘 要：
“数据结构”是一门专业技术基础课。它的教学要求是：学会分析研究计算机加工
的数据结构的特征，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其
相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，本课程
的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确
易读，符合软件工程的规范。
在学习中，先要学习程序设计课程的目的掌握设计程序的思路，学习会用计算机
语言编写程序，以实现所需要处理的任务。要正确处理算法与语法的关系，算法
是程序的核心、是灵魂，语法是外壳、是工具。不应把学习重. 点放在语法规则
上，语法是重要的，不掌握语法规则就无法编写出正确的程序。一定要把重点放
在解题的思路上，通过思考，和大量的阅读，来构造一个完整的程序。请记住：
重要的是学会编程，而不是背语法。
关键词 ：线性表，栈和队列，二叉树，图，查找，排序，二叉排序树的应用
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多
种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高
的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
一、数据结构的研究内容
在计算机科学中，数据结构是一门研究非数值计算的程序设计问题中计算机
的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这
些运算后所得到的新结构仍然是原来的结构类型。 “数据结构”作为一门独
立的课程在国外是从1968年才开始设立的。 1968年美国唐·欧·克努特教授开创
了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》
是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。“数据结构”
在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬
件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一
般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、
操作系统、数据库系统及其他系统程序的重要基础。 计算机是一门研究用
计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示，信
息的处理 。 而信息的表示和组织又直接关系到处理信息的程序的效率。
随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用
程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分
析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研
究的问题。众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，
这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是
数据结构的内容。数据的结构，直接影响算法的选择和效率。 计算机解决
一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个
适当的数学模型，然后设计一个解此数学模型的算法（Algorithm ），最后编出程
序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中
提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以
描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，
数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相
应的插入、删除和修改的算法 。也就是说，数据结构还需要给出每种结构类型
所定义的各种运算的算法。
二、数据结构的分类
数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构分别
为逻辑结构、存储结构（物理结构）和数据的运算。数据的逻辑结构是对数据
之间关系的描述，有时就把逻辑结构简称为数据结构。逻辑结构形式地定义为
（K ，R ）（或（D ，S ）），其中，K 是数据元素的有限集，R 是K 上的关系的有限集。 数据元素相互之间的关系称为结构。有四类基本结构：集合、线性
结构、树形结构、图状结构（网状结构）。树形结构和图形结构全称为非线性
结构。集合结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构
中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中
元素之间存在多对多关系。在图形结构中每个结点的前驱结点数和后续结点数可
以任意多个。 数据结构在计算机中的表示（映像）称为数据的物理（存储）
结构。它包括数据元素的表示和关系的表示。数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储
结构和链式存储结构。顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此
得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方
法，通常借助于程序设计语言中的数组来实现。链接存储方法：它不要求逻辑上
相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计
语言中的指针类型来实现。索引存储方法：除建立存储结点信息外，还建立附
加的索引表来标识结点的地址。散列存储方法：就是根据结点的关键字直接计
算出该结点的存储地址。 数据结构中，逻辑上（逻辑结构：数据元素之间
的逻辑关系）可以把数据结构分成线性结构和非线性结构。线性结构的顺序存储
结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存取的存
储结构。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不
连续。逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。
三、二叉排序树的应用
1. 主要模块：
1）主函数模块
Main()
{
建立n 个关键字的二叉排序树并输出；
从二叉树排序树T 中删除任意结点, 其关键字为key ；
在二叉树排序树T 中，插入一个结点t, 其关键字为key ；
在二叉排序树T 中递归查找关键字等于 key2 的数据元素；
}
2）创建二叉排序树模块
BiTree CreatBST(int n)
{
建立n 个关键字的二叉排序树；
从键盘输入调建立n 个关键字依次用InsertBST1（插入函数）；
返回根结点T ；
输出过程；
}
3）删除模块
DeleteNode(BiTree &T, int x)
{
从二叉树排序树T 中删除任意结点, 其关键字为x ；
可以实现删除根结点、叶子结点以及其它任意结点的功能；
}
4）插入模块
void InsertBST1(BiTree &T,BiTNode *s)
{
在二叉树排序树T 中，插入一个结点s(递归算法) ；
被CreatBST 函数调用；
}
5）查找模块
BiTree searchBST1(BiTree T,TElemType key)
{
在根指针T 所指二叉排序树中递归查找关键字等于 key 的数据元素；
若成功，返回指向该数据元素结点的指针；
否则返回空指针；
}
2. 部分程序代码：
void inorder_btree(BSTree root)// 中序遍历打印二叉排序树
{
BSTree p=root;
if(p!=NULL){
inorder_btree(p->left );
coutkey
inorder_btree(p->right );
}
}
int searchBST(BSTree t,KeyType key)//查找
{
if(key==t->key)
return 1;
if(t==NULL)
return 0;
if(keykey)
return searchBST(t->left,key);
else
return searchBST(t->right,key);
}
BSTree deleteBST(BSTree tptr,KeyType key)//删除
{
BSTree p,tmp,parent=NULL;
p=tptr;
while(p)
{
if(p->key==key)
break;
parent=p;
p=(key
key)?p->left:p->right;
}
if(!p) return NULL;
tmp=p;
if(!p->right&&!p->left) /*p的左右子树都为空*/
{
if(!parent) //要删根，须修改根指针
tptr=NULL;
else if(p==parent->right)
parent->right=NULL;
else
parent->left=NULL;
free(p);
}
else if(!p->right) //p的右子树为空，则重接p 的左子树
{
p=p->left;
if(!parent) //要删根，须修改根指针
tptr=p;
else if(tmp==parent->left)
parent->left=p;
else
parent->right=p;
free(tmp);
}
else if(!p->left) //的左子树为空，则重接p 的左子树
{
p=p->right;
if(!parent) //要删根，须修改根指针
tptr=p;
else if(tmp==parent->left)
parent->left=p;
else
parent->right=p;
free(tmp);
}
else if(p->right&&p->left) //p有左子树和右子树，用p 的后继覆盖p
然后删去后继
{ //另有方法：用p 的前驱覆盖p 然后删去前驱||
合并p 的左右子树
parent=p; //由于用覆盖法删根，则不必特殊考虑删根
p=p->right;
while(p->left)
{
parent=p;
p=p->left;
}
tmp->key=p->key;
if(p==parent->left)
parent->left=NULL;
else
parent->right=NULL;
free(p);
}
return tptr;
}
int main()
{
KeyType key;
int flag,test;
char cmd;
BSTree root;
do
{
cout
cout
cout
cout
cout
cout
flag=0;
do
{
if(flag!=0)
cout
fflush(stdin);
cin>>cmd;
flag++;
}while(cmd!='c'&&cmd!='C'&&cmd!='a'&&cmd!='A');
if(cmd=='c'||cmd=='C')
{
cout
root=createBST();
do
{
flag=0;
cout
inorder_btree(root);
cout
cout
作:**************"
cout
cout
cout
cout
cout
cout
cout
***"
do{
if(flag!=0)
cout
fflush(stdin);
scanf("%c",&cmd);
flag++;
}
3. 测试用例：
1, 程序运行时菜单显示如下：
当输入的二叉树序列为：{2,6,9,8,4}时，创建二叉排序树，并输出结果如下：
参考文献：《数据结构课程设计》严蔚敏、吴伟民著。清华大学出版社。1997.4