数据结构主讲人 闫会峰
2008年 2月
Tel:13983499782 62461724
Email:yan_hf@163.com QQ:4423360
教材
数据结构?(C语言版）陈明编著,清华大学出版社参考书
1,?数据结构?(C语言版）严蔚敏等编著,清华大学出版社
2,?数据结构?（用面向对象方法与 C++描述）
殷人昆等编著，清华大学出版社
,数据结构,课程学习要求
1、考勤检查，不迟到早退。
2、认真完成课堂以及课后作业安排。
3、平时上课与上机实习相结合。
4、每周定期答疑。
5、同学们根据情况适当自学相关内容。
考核方式及成绩评定方法
本课程考核由期末卷面考试,平时抽查,平时作业,上机实验等部分组成 。 其中,期末卷面考试采用闭卷方式 （ 试卷库抽取试卷 ） 。
期末考试,60%；
平时成绩 （ 含平时考勤,提问,作业 ）,20%
上机实验,20%；
第 1章 绪论数据结构的重要性基本术语数据结构的概念数据的逻辑结构数据的存储结构数据的运算数据的逻辑结构、存储结构及运算的关系算法的描述数据结构的重要性计算机科学是研究用计算机进行信息表示和处理的科学。
它主要涉及两个问题：信息的表示和信息的处理。随着计算机的普及，信息量的增加，这要求人们应研究数据的特性以及数据之间存在的关系，而数据结构正是描述数据的特性以及数据之间存在的关系的一门课程。
电话号码查询问题编一个查询某个城市或单位的私人电话号码的程序。要求对任意给出的一个姓名，若该人有电话号码，则迅速找到其电话号码；否则指出该人没有电话号码。
解决方案：
构造一张电话号码登记表。表中每个结点存放两个数据项：
姓名和电话号码，如图。
写出好的查找算法 。
基本术语数据,是信息的载体，描述客观事物的数、字符以及所有能输入到计算机中被计算机程序识别、加工处理的信息的集合。
数据项,是数据的具有独立意义的不可分的最小单位，它是对数据的数据元素属性的描述。
数据元素,是数据的基本单位,是对一个客观实体的数据描述。一个数据元素可以由一个或若干个数据项组成。
数据对象,相同性质的数据元素的集合是一个数据对象，
它是数据的一个子集。
数据元素和数据项利用学生成绩表来说明，那么表中每个学生的信息和成绩就是一个数据元素。
一个数据元素由学号、姓名、语文成绩、数学成绩、英语成绩五个数据项组成。
数据结构的概念数据结构指的是数据之间的相互关系，它一般包括以下三个方面的内容：
数据的逻辑结构,数据之间的逻辑关系。
数据的物理结构,数据元素及其关系在计算机存储器内的表示。
数据的运算,即对数据进行的操作 。
数据的逻辑结构分类根据数据逻辑关系的不同，可分为四种基本结构类型：
集合,数据具有符合某一条件的相同的性质,且别无其他关系。
线性结构,数据之间存在一对一的关系。
树形结构,数据之间存在一对多的关系。
图形结构,数据之间存在多对多的关系。
四个基本结构
集合
线性结构
树形结构
图形结构 (网状结构 )
数据结构涉及的问题如何以最节省存储空间的方式来表示数据。
各种不同的数据结构表示方法及其相关算法。
如何有效的改进算法效率使程序的执行速度更快。
数据处理的各种技巧，如排序、查找等算法的介绍等。
逻辑结构和存储结构关系数据结构包括逻辑结构和存储结构 （物理结构），二者关系：
算法设计?逻辑结构算法实现?存储结构数据的逻辑结构数据结构在形式上可定义为一个二元组：
Data_Structure=(D,R)
其中 D是数据元素的有限集合,R是 D上关系的有限集合。
逻辑结构例子实例,设计一个数据结构，要求每个课题组由一位教授、一至四名研究生和一至八名本科生组成，在小组中，一位教授指导一至四名研究生，每位研究生指导一至二名本科生。
实例求解：
Group=(P,R)
其中,P表示数据元素，包括教授、研究生、本科生，
即 P={T,G1,?Gn,S11,S12,?Snm} 1?n?4，
1?m?2
R表示小组成员的关系，他们的关系有两种，教授和研究生,R1={<T,Gi>?1?i?n,1?n?4}；研究生和本科生,R2={<Gi,Sij>?1?i?n,1?j?m,1?n?4,1?m?2}
数据的逻辑结构的典型结构及相互关系数据的逻辑结构分为三种典型结构：集合，线性结构和非线性结构。
集合,其元素间为松散的关系，只是同属于一个集合。
线性结构,其逻辑特征是有且仅有一个起始结点和一个终端结点，并且所有结点只有一个直接前趋和一个直接后继。
非线性结构,其特征是一个结点可能有多个直接前趋或多个直接后继。
数据的存储结构及存储方法分类存储结构,数据的逻辑结构在计算机内部的表示或实现，它包括数据元素的表示和关系的表示 。
存储方法分类：
顺序存储方法链式存储方法索引存储方法散列存储方法顺序存储方法定义,逻辑上相邻的结点存储在物理位臵上也相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来表示 。
特点：
结点中只有自身信息域，没有连接信息域,存储密度大，
存储空间利用率高。
通过计算直接确定数据结构的中的第 i个结点的存储地址 Li,Li=L0+（ i-1） *m,其中 L0为第一个结点的存储位臵,m为每个结点所占用的存储单元个数。
插入和删除都会引起大量的结点移动。
顺序存储结构例子数据结构如下：
A=（ D,S）
D={a,b,c,d,e}
S={<a,b>,<b,c>,<c,d>,<d,e>}
设第一个结点的存储单元位臵为 1000，每一个结点所占的存储单元的个数为 1，则存储结构如图 1-4所示：
返回链式存储方法定义,链式存储方法不要求逻辑上相邻的结点在物理位臵上亦相邻，结点间的关系由附加的指针来表示，
指针指向结点的邻接结点 。
结点,
特点：
存储结构的存储密度小，存储空间利用率低。
逻辑上相邻的结点，物理上不必邻接。
删除和插入操作灵活方便，不必移动结点，只要改变结点中的指针值。
数据域：存储结点本身的值。
指针域：存储该结点的各后继结点的存储单元地址。
链式存储结构例子线性结构的结点集合 D={45,63,67,14,97},以结点值的降序为关系 S={<97,67>,<67,63>,<63,45>,<45,14>}，
链接存储结构如图 1-5所示,
返回索引存储方法定义,在存储结点信息的同时，建立一个附加的索引表，利用索引表中索引项的值来确定结点的实际存储单元地址。
索引表,该中的每一项称为索引项，索引项的一般形式为（关键字，地址），关键字能唯一标识一个结点。
返回散列存储方法存储思想,根据结点的关键字直接计算出结点的存储地址 。
计算地址方法,把结点的关键字作为自变量，通过一个称为散列函数 H（ a.key）的计算规则，确定出该结点的确定存储单元地址。
数据的运算定义,在数据逻辑结构的基础上，在数据元素上施加的一系列的抽象的操作 。
分类：
查找,在数据结构里查找满足一定条件的结点。
插入,向数据结构中增加新结点。
删除,把指定的数据从数据结构中去掉。
修改,改变指定结点的一个或多个字段的值。
排序,排序是指保持序列中的结点个数不变，把结点按某种指定的顺序重新排列。
数据的逻辑结构、存储结构及运算的关系同一逻辑结构的不同存储结构可用不同的数据结构名称来标识。
在给定了数据的逻辑结构和存储结构，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。
算法的描述算法定义,对特定问题求解步骤的一种描述 。
重要特性：
输入,一个算法具有 0个或多个输入的外界量。
输出,一个算法至少产生一个输出。
有穷性,算法中的每一条指令的执行次数必须是有限的，且每一步都在有穷时间内完成。
确定性,算法中每一条指令的含义都必须明确定义。
可行性,一个算法的执行时间是有限的。
算法例子存在一个长度为 n的字符串，串中元素互不相同。
编写一算法，确定字符 e在字符串中的位臵。
解题步骤：
用自然语言描述用流程图描述用 C语言描述用自然语言表示给 i 赋初始值为 1。
若字符串中的第 i字符为 e则输出 i的值，即得最终结果，
结束。
若 i等于 n时，仍未找到 e，则字符串中没有 e这个字符，
结束。
i自加 1。
重复步骤 2,3,4。
返回用流程图表示返回用 C语言来描述
Search (char A[n],int n)
{
int i；
for （ i=1； i<=n; i++）
if （ A[i-1]==’ e’ ） return (i); /*找到返回 i*/
else return (0);/* 未找到，返回 0*/
}
2008年 2月
Tel:13983499782 62461724
Email:yan_hf@163.com QQ:4423360
教材
数据结构?(C语言版）陈明编著,清华大学出版社参考书
1,?数据结构?(C语言版）严蔚敏等编著,清华大学出版社
2,?数据结构?（用面向对象方法与 C++描述）
殷人昆等编著，清华大学出版社
,数据结构,课程学习要求
1、考勤检查，不迟到早退。
2、认真完成课堂以及课后作业安排。
3、平时上课与上机实习相结合。
4、每周定期答疑。
5、同学们根据情况适当自学相关内容。
考核方式及成绩评定方法
本课程考核由期末卷面考试,平时抽查,平时作业,上机实验等部分组成 。 其中,期末卷面考试采用闭卷方式 （ 试卷库抽取试卷 ） 。
期末考试,60%；
平时成绩 （ 含平时考勤,提问,作业 ）,20%
上机实验,20%；
第 1章 绪论数据结构的重要性基本术语数据结构的概念数据的逻辑结构数据的存储结构数据的运算数据的逻辑结构、存储结构及运算的关系算法的描述数据结构的重要性计算机科学是研究用计算机进行信息表示和处理的科学。
它主要涉及两个问题：信息的表示和信息的处理。随着计算机的普及，信息量的增加，这要求人们应研究数据的特性以及数据之间存在的关系，而数据结构正是描述数据的特性以及数据之间存在的关系的一门课程。
电话号码查询问题编一个查询某个城市或单位的私人电话号码的程序。要求对任意给出的一个姓名，若该人有电话号码，则迅速找到其电话号码；否则指出该人没有电话号码。
解决方案：
构造一张电话号码登记表。表中每个结点存放两个数据项：
姓名和电话号码，如图。
写出好的查找算法 。
基本术语数据,是信息的载体，描述客观事物的数、字符以及所有能输入到计算机中被计算机程序识别、加工处理的信息的集合。
数据项,是数据的具有独立意义的不可分的最小单位，它是对数据的数据元素属性的描述。
数据元素,是数据的基本单位,是对一个客观实体的数据描述。一个数据元素可以由一个或若干个数据项组成。
数据对象,相同性质的数据元素的集合是一个数据对象，
它是数据的一个子集。
数据元素和数据项利用学生成绩表来说明，那么表中每个学生的信息和成绩就是一个数据元素。
一个数据元素由学号、姓名、语文成绩、数学成绩、英语成绩五个数据项组成。
数据结构的概念数据结构指的是数据之间的相互关系，它一般包括以下三个方面的内容：
数据的逻辑结构,数据之间的逻辑关系。
数据的物理结构,数据元素及其关系在计算机存储器内的表示。
数据的运算,即对数据进行的操作 。
数据的逻辑结构分类根据数据逻辑关系的不同，可分为四种基本结构类型：
集合,数据具有符合某一条件的相同的性质,且别无其他关系。
线性结构,数据之间存在一对一的关系。
树形结构,数据之间存在一对多的关系。
图形结构,数据之间存在多对多的关系。
四个基本结构
集合
线性结构
树形结构
图形结构 (网状结构 )
数据结构涉及的问题如何以最节省存储空间的方式来表示数据。
各种不同的数据结构表示方法及其相关算法。
如何有效的改进算法效率使程序的执行速度更快。
数据处理的各种技巧，如排序、查找等算法的介绍等。
逻辑结构和存储结构关系数据结构包括逻辑结构和存储结构 （物理结构），二者关系：
算法设计?逻辑结构算法实现?存储结构数据的逻辑结构数据结构在形式上可定义为一个二元组：
Data_Structure=(D,R)
其中 D是数据元素的有限集合,R是 D上关系的有限集合。
逻辑结构例子实例,设计一个数据结构，要求每个课题组由一位教授、一至四名研究生和一至八名本科生组成，在小组中，一位教授指导一至四名研究生，每位研究生指导一至二名本科生。
实例求解：
Group=(P,R)
其中,P表示数据元素，包括教授、研究生、本科生，
即 P={T,G1,?Gn,S11,S12,?Snm} 1?n?4，
1?m?2
R表示小组成员的关系，他们的关系有两种，教授和研究生,R1={<T,Gi>?1?i?n,1?n?4}；研究生和本科生,R2={<Gi,Sij>?1?i?n,1?j?m,1?n?4,1?m?2}
数据的逻辑结构的典型结构及相互关系数据的逻辑结构分为三种典型结构：集合，线性结构和非线性结构。
集合,其元素间为松散的关系，只是同属于一个集合。
线性结构,其逻辑特征是有且仅有一个起始结点和一个终端结点，并且所有结点只有一个直接前趋和一个直接后继。
非线性结构,其特征是一个结点可能有多个直接前趋或多个直接后继。
数据的存储结构及存储方法分类存储结构,数据的逻辑结构在计算机内部的表示或实现，它包括数据元素的表示和关系的表示 。
存储方法分类：
顺序存储方法链式存储方法索引存储方法散列存储方法顺序存储方法定义,逻辑上相邻的结点存储在物理位臵上也相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来表示 。
特点：
结点中只有自身信息域，没有连接信息域,存储密度大，
存储空间利用率高。
通过计算直接确定数据结构的中的第 i个结点的存储地址 Li,Li=L0+（ i-1） *m,其中 L0为第一个结点的存储位臵,m为每个结点所占用的存储单元个数。
插入和删除都会引起大量的结点移动。
顺序存储结构例子数据结构如下：
A=（ D,S）
D={a,b,c,d,e}
S={<a,b>,<b,c>,<c,d>,<d,e>}
设第一个结点的存储单元位臵为 1000，每一个结点所占的存储单元的个数为 1，则存储结构如图 1-4所示：
返回链式存储方法定义,链式存储方法不要求逻辑上相邻的结点在物理位臵上亦相邻，结点间的关系由附加的指针来表示，
指针指向结点的邻接结点 。
结点,
特点：
存储结构的存储密度小，存储空间利用率低。
逻辑上相邻的结点，物理上不必邻接。
删除和插入操作灵活方便，不必移动结点，只要改变结点中的指针值。
数据域：存储结点本身的值。
指针域：存储该结点的各后继结点的存储单元地址。
链式存储结构例子线性结构的结点集合 D={45,63,67,14,97},以结点值的降序为关系 S={<97,67>,<67,63>,<63,45>,<45,14>}，
链接存储结构如图 1-5所示,
返回索引存储方法定义,在存储结点信息的同时，建立一个附加的索引表，利用索引表中索引项的值来确定结点的实际存储单元地址。
索引表,该中的每一项称为索引项，索引项的一般形式为（关键字，地址），关键字能唯一标识一个结点。
返回散列存储方法存储思想,根据结点的关键字直接计算出结点的存储地址 。
计算地址方法,把结点的关键字作为自变量，通过一个称为散列函数 H（ a.key）的计算规则，确定出该结点的确定存储单元地址。
数据的运算定义,在数据逻辑结构的基础上，在数据元素上施加的一系列的抽象的操作 。
分类：
查找,在数据结构里查找满足一定条件的结点。
插入,向数据结构中增加新结点。
删除,把指定的数据从数据结构中去掉。
修改,改变指定结点的一个或多个字段的值。
排序,排序是指保持序列中的结点个数不变，把结点按某种指定的顺序重新排列。
数据的逻辑结构、存储结构及运算的关系同一逻辑结构的不同存储结构可用不同的数据结构名称来标识。
在给定了数据的逻辑结构和存储结构，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。
算法的描述算法定义,对特定问题求解步骤的一种描述 。
重要特性：
输入,一个算法具有 0个或多个输入的外界量。
输出,一个算法至少产生一个输出。
有穷性,算法中的每一条指令的执行次数必须是有限的，且每一步都在有穷时间内完成。
确定性,算法中每一条指令的含义都必须明确定义。
可行性,一个算法的执行时间是有限的。
算法例子存在一个长度为 n的字符串，串中元素互不相同。
编写一算法，确定字符 e在字符串中的位臵。
解题步骤：
用自然语言描述用流程图描述用 C语言描述用自然语言表示给 i 赋初始值为 1。
若字符串中的第 i字符为 e则输出 i的值，即得最终结果，
结束。
若 i等于 n时，仍未找到 e，则字符串中没有 e这个字符，
结束。
i自加 1。
重复步骤 2,3,4。
返回用流程图表示返回用 C语言来描述
Search (char A[n],int n)
{
int i；
for （ i=1； i<=n; i++）
if （ A[i-1]==’ e’ ） return (i); /*找到返回 i*/
else return (0);/* 未找到，返回 0*/
}
