数据结构十日谈

所需积分/C币:44 2013-12-29 5.92MB PDF
评分

数据结构十日谈,描述数据结构的书,不要分数就可以下载,看看没坏处
如果给定两个集合A和B,它们满足ACB和BCA,则称集合 A和B相等,记为A=B。也就是说两个集合中含有相同的元素(次 序不一定一致)。 例如:C={2,3,1} D={1,2,3 显然,由于集合C中的元素和集合D中的元 素相同,即C=D。 (2)集合之间的运算 (a)集合的并(AUB) 对于集合A、B,定义它们的并集AUB、 交集A∩B和差集A-B如下: A B (1)给定两个集合A、B,由集合A和B 中的所有元素构成的集合称为A和B的并(b)集合的交(A∩B) 集,记为A∪B。图1-2(a)为其文氏图表示。 (2)给定两个集合AB,由同时属于集合 A、B的所有元素构成的集合称为A和B的交 集,记为A∩B。图12(b)为其文氏图表示 (c)集合的差(A-B) (3)给定两个集合A、B,由所有属于集合 A而不属于集合B的那些元素构成的集合称 图1-2集合的运算 为A和B的差集,记为A一B。图1-2(c)为其文氏图表示 例如:A={1,2,3,4}B={1,3,5,7} 则AUB={1,2,3,4,5,7} A∩B={1,3} A-B={2,4} 如果集合A和B满足A∩B=,就称集合A和B是不相交的。 按照交集的定义,这也就是说,集合A和B没有公共的元素。 二、关系 在此我们首先介绍有序对(序偶)的概念。在初等数学中,最常见 最典型的序偶,就是平面直角坐标系中点的坐标(x,y)。例如:点〈1, 2)点(-3,5)等。如果a1,a2是两个元素,按先后顺序将它们排列 在一起,并且作为一个整体来看待则称它为一个序偶,记为a1,a2)。 注意(a1a2)和a2a1)是不同的,因为它们的排列顺序不同。例如,在 平面直角坐标系中〈1,-2)和〈-2,1)是不同的,它们代表两个不同 的点 如果给定两个集合A和B,则定义它们的笛卡尔积如下,记为A B A×B={(a,b〉|a∈A,b∈B 例如:设A={a,b},B={1,2,3},那么A和B的笛卡尔积为 A×B={〈a,1〉,(a,2),(a,3),〈b,1),<b,2),<b,3)} B×A={1,a),〈1,b》,〈2,a),(2,b),3,a),〈3,b) 般地,对于任何两个有限集A和B来讲,如果A有n个元素, B有m个元素,那么,A×B和B×A都有nXm个元素。但是,正如 上例中所表明的,A×B和B×A的元素个数虽然一样,其元素却不 同,它们通常是两个不同的集合,即A×B≠BXA。在AXB中,如果 B和A相等,即B=A,则笛卡尔积自然应为A×A。 集合A×B的每个子集R都称为从A到B的一个关系,或者称 R是AⅩB的一个关系。当A=B时,就称R是定义在A上的一个关 系。如果R是定义在集合A上的一个关系,则〈a,b)∈R时,就称元 素a和b有关系R,记作aRb。此时元素a称为元素b的前缀(或前 驱),元素b称为元素a的后继。 设R是非空集合A上的一个关系,如果对于A中的任何元素 a,都有〈a,a)∈R,则称关系R是自反的。如果对于A中任何元素a, 都没有〈a,a)∈R,则称关系R是反自反的。如果对于A中的任何元 素a和b,当ab)∈R时,必有(b,a)∈R,则称关系R是对称的。如 果<a,b〉∈R且(b,a)∈R时,必有a=b,则称R是反对称的。如果 对于A中的任何元素a、b、c,当(a,b>∈R,并且(bc)∈R,必有(a,c) ∈R时,则称关系R是传递的 例如:整数集Z上的关系“=”是自反的,因为对于任意x∈z, 总有x=x;而整数集Z上的关系“(”是反自反的。因为对于任何x∈ Z,x〈x都不成立。整数集Z上的关系“=”是对称的,而关系“>” ≥”、“<”、“≤”是反对称的。整数集Z上的关系“<”是传递的,因 为对于任何a、b、c∈Z,如果a<b且b<c,则必有a<c。 当集合A上定义的关系R是自反的、对称的和传递的,这时就 称R是一个等价关系。此时,如果a,b>∈R,就称元素a和b是等价 的。例如,整数集Z上的关系“=”是一个等价关系 当集合A上定义了一个等价关系R时,可以根据这个关系将A 中的元素分成若干部分,让它们分别属于A的若干个子集,这些子 集互不相交,并且使同一个子集的任何两个元素都具有关系R,而 任何两个子集中的任何两个元素,都不满足关系R,即这些子集构成 了集合A的-些划分,而这些子集都称为关系R的等价类。 当集合A上定义的关系R是自反的、反对称的和传递的,则称 R是集合A的一个部分序(或偏序)关系。如果在集合A上定义了 个偏序关系R,则称集合A为偏序集,记为(A,R)。显然,对于 个有限偏序集来说,至少有一个元素没有前缀,至少有一个元素没有 后继。例如:自然数集N整数集Z、有理数集Q和实数集R上的关 系“≤”就是个偏序关系。又如:在自然数集N上定义关系“/”如 下:x,y)∈/当且仅当x整除y。不难证明,/是自然数集N上的一个 偏序关系。 如果R是定义在集合A上的偏序关系,即(A,R是一个偏序 集,并且关系R满足下面条件;对于A中的任何元素a、b,(a,b〉∈R 和<b,a)∈R两者至少有一个成立,这时就称R是集合A上的一个 序(或完全序)关系,A在这个序关系下称为有序(或完全序)集,仍记 为(A,R)。例如:自然数集N、整数集Z、有理数集Q和实数集R在 关系“≤”下都是完全序集。而自然数集N在如上定义的关系“/”下 就不是完全序集。 1.2数据结构概念 “数据结构”是一门随着计算机科学的发展而还渐形成的学科, 自1946年美国宾夕法尼亚大学的工程师和科学家发明了第一台电 子计算机以来,计算机科学经历了将近半个世纪的蓬勃发展,其发展 速度远远超出了人们的预料,可谓日新月异。计算机硬件技术,软件 技术不断提高,使计算机价格越来越便宜,功能越来越强大,也就使 得其应用领域越来越广泛。计算机的应用早已不再局限于科学计算, 而更多地用于过程控制、数据处理、信息管理,以及计算机辅助设计 (CAD)和计算机辅助制造(CAM)等非数值数据的处理工作。与此 相应,计算机加工处理的对象——数据也从单纯的数值数据发展到 字符、表格、图像以及声音等各种非数值数据。为了更有效地使用计 算机,设计出高效、可靠的程序,需要对数据的组织数据元素之间的 关系、数据在计算机中的表示(包括数据元素的表示和数据元素之间 关系的表示)以及对数据的操作进行深人研究。这样,就促进“数据 结构”这门学科的形成和发展。 一、什么是数据结构 在介绍数据结构这一概念之前,首先要了解一下数据的概念。,所 谓数据就是指对客观事物的符号表示。在计算机科学中我们把所有 能输人到计算机中,并能被计算机处理的符号总称为数据。换言之, 它就是计算机程序加工的原料。例如,一个代数方程求解程序,它处 理的对象(数据)就是实数;又如:一个文字处理程序(如WPS),其 处理的对象就是字符文字。对于计算机科学而言,数据的含义极其广 泛,图像、声音等都可以通过编码而归之为数据的范畴。数据由数据 元素组成,数据元素是数据的基本单位,通常在计算机程序中作为一 个整体进行考虑和处理。而数据元素之间往往又不是孤立无关的,数 据结构就是相互之间存在一种或多种特定关系的数据元素的集合, 数据元素之间存在的相互关系就叫结构。根据数据元素之间关系的 不同特性,通常有下列四类基本结构 1.集合:结构中的数据元素之间除了“同属于一个集合”的关系 外,别无其它关系 2.线性结构:结构中的数据元素之间存在一个对一个的关系; 3.树形结构:结构中的数据元素之间存在一个对多个的关系; 4.图状结构(网状结构):结构中的数据元素之间存在名个对多 个的关系。 图1-3为上述四类基本结构的关系图。其中,圆圈表示数据元 素,圆圈之间的连线表示数据元素之间的关系。在本书中将主要讨 论线性结构、树形结构和网状结构。“集合”,由于元素之间的关系极 为松散,所以不作讨论。 (a)集合 (b)线性 (c)树 (d)图 图1-3四类基本结构关系图 数据结构的形式定义可以用一个二元组表示: Data-Structure=(D,R) 其中,D为具有相同特性的数据元素的有限集,R是D上数据元素 之间关系的有限集。例如:复数在计算机科学中可作如下定义: Complex-=(C,R) 其中,C={c1,c2z|c1,c2∈实数},R={(c1,c2)c1为实部,c2为虚部}。 又如:今欲编制一个企业管理程序,其中需要管理工厂中各车间的 工人,则首先要为计算机处理的对象—车间工人设计一个数据结 构,设一个车间由一个车间主任,三个班组的小组长以及12个工人 组成,且这些成员之间的关系为:车间主任负责管理三个小组长; 小组长、音理四个工人,则可以如下定义数据结构: Grop=P,R) 其中,P={T,G,G2,G3,W1,W12,,W34} R={R1,R2 R1={<T,G)|1≤i≤3} R2={G1,W;)11≤≤3,1≤j4} 上述数据结构的定义仅是对操作对象的一种数学描述,而没有 对操作对象定义具体的操作,换句话说,即从操作对象抽象出的数学 模型。结构定义中的“关系”描述的是数据元素之间的逻辑关系,又称 逻辑结构。 对数据结构的讨论,最终是为了在计算机中实现对数据元素的 操作。为此我们不仅要讨论数据的逻辑结构及其运算,而且还要讨论 数据结构在计算机中表示—数据的物理结构(又称存储结构),它 包括数据元素的表示和元素之间关系的表示。数据元素之间关系的 表示有两种不同的方法:顺序映象和非顺序映象。由此可得到两种不 同的存储结构:顺序存储结构和链式存储结构(非顺序存储结构)其 中,顺序存储映象是借助元素在存储器中的相对位置来表示数据元 素之间的逻辑关系;非顺序存储映象是借助在一个数据元素(a)中保 存另一数据元素(b)在存储器中的相对位置来表示两个元素(a和b) 之间的逻辑关系。 程序设计语言中,我们可以借助“数据类型”来描述数据的存储 结构。例如:在 PASCAL语言中,可以用“一维数组”描述顺序存储结 构;用“指针”描述链式存储结构。 数据类型在程序设计语言中用以描述(程序)操作对象的特性。 在高级语言中,每个变量都要属于一个确定的数据类型(整型、实型、 字符型、布尔型等),不同的数据类型规定了在程序执行期间不同的 变量的取值范围和允许的操作,所以,数据类型是一个值的集合和定 义在这个值集上的一组操作的总称。例如,在 PASCAL语言中的整 数类型,它定义了其值集为区间[一 maxin… naxin]上的整数( maxin 是依赖于具体计算机的最大整数),并规定了在这个值集上的一组操 作为:十、一、*、DYV、MOD等 与数据类型相关的还有一个概念称为数据对象。数据对象是某 种数据元素的集合,是数据的一个子集。例如 PASCAL语言中,布尔 类型的数据对象是集合{TRUE(真), FALSE(假)},字符的数据对 象为集合{xx∈所有ASCI字符}。 数据结构的发展概况 六十年代初期,国内外的大学中都没有独立的“数据结构”课程 但数据结构的有关内容已散见于操作系统、编译原理和表处理语言 等课程之中。1968年,美国一些大学的计算机科学系的教学计划中 明确规定“数据结构”为…门课程,但没有明确规定该课程的内容范 围。当时,数据结构几乎和图论特别是表和树的理论是同义语。随 后,数据结构这个概念被扩充到包括网络、代数集合论、关系等现在 称之为“离散数学结构”的那些内容,它们同现在的“数据结构”的某 些内容混在一起,总称为“数据结构”由于数据必须在计算机中进行 处理,因此,不能局限于研究数据本身的数学概念,还必须考虑数据 的物理结构。这就进一步扩大了数据结构的内容。自从1968年美国 研究计算机科学的著名教授 D, E. Knuth所著的“计算机程序设计技 巧”( The art of Computer Programming问世以后,才逐渐把数据的 逻辑结构、物理结构以及每种结构所定义的运算作为组成“数据结 构”课程的主要内容近年来,由于数据库系统的不断发展,在数据结 构课程中又增加了文件管理特别是大型文件的组织等方面的内容。 数据结构与数学,计算机硬件、特别是计算机软件有着密切的关 系。它是计算机专业的一门核心课程,是编译原理、操作系统、数据 库、人工智能等课程的基础。同时又广泛用于信息科学、系统工程、应 用数学以及各种工程技术领域。 数据结构在计算机科学中有着十分重要的地位。它有自己的理 论、研究对象和应用范围,而且其研究的内容正在不断扩充和深化 而作为一门课程、一本教材,因受特定的对象和时期的限制,因此不 能全面地反映数据结构的全貌但值得注意的是,数据结构是新兴的 9 学科,正值方兴未艾,蓬勃发展的阶段一方面,面向各专门领域中特 殊问题的数据结构得到研究和发展,如多维图形数据结构等;另一方 面,从抽象数据类型的观点来讨论数据结构,已成为一种新的趋势 越来越被人们所重视。 习题 指出下列集合的元素是什么? (1)我国四大发明的集合。 (2)小于24并且是5的倍数。 (3)B={w|w|<3,w∈Z} (4)方程y2-5y+4=0在实数范围内的解 2.下列每一对集合是否相等? (1){-1,1},〈1,-1} (2){1,2,3},{2,1,4} (3){a,b,c},{b;c,d,e,a} (4){x|x2-4x+3=0,x∈R},{1,3} 3.若集合A一{a,b,C},下面的记法哪些是正确的?哪些是不 正确的? a∈A;bA;{c}∈A;AcA;ΦCA;{c}∈A;Φ∈A 4.已知:A={0,2,4,6,8},B={1,3,5,7,9},C={2,5,6,9} 求 A∩B,A∩C,B∩C,AUB,AUC,BUC,AB,BC,CA 5.设A={2,3,4,6}、B={a,b,c),求AXB和BXA。 6.简述下列术语:数据、数据元素、数据对象、数据结构、存储结 构和数据类型。 7.数据结构研究的主要内容是什么? 10

...展开详情
立即下载 最低0.43元/次 身份认证VIP会员低至7折
举报 举报 收藏 收藏
分享
img
macos55555

关注 私信 TA的资源

上传资源赚积分,得勋章
相关内容推荐