可逆概要数据结构
ISSN 100020054CN 1122223 N
清华大学学报(自然科学版)J T singhua U niv (Sci &Tech ),2008年第48卷第10期
2008,V o l .48,N o .1023 40
162521628
可逆概要数据结构
冯文峰1,2
, 黄永峰1
, 李 星
1
(1.清华大学电子工程系,北京100084;2.河南理工大学,焦作454000)
收稿日期:2007207227
基金项目:国家自然科学基金资助项目(60703053);
国家“九七三”基础研究基金项目(2007CB 310806)
作者简介:冯文峰(1975—),男(汉),河南,博士后。
通讯联系人:黄永峰,副教授,E 2m ail :yfhuang @tsinghua .edu .cn
摘 要:由于随机哈希函数不可逆,目前的概要数据结构不得不遍历关键字地址空间以查找和估计频繁项集。该文基于多项式域上的中国剩余定理,设计可逆H ash 函数族,进而实现了一类可逆概要数据结构。它遍历哈希地址空间查找和估计频繁项集,并利用随机哈希函数的可逆性反推出频繁项对应的关键字。实验结果表明,与目前具有代表性的Coun t 2
M in 概要数据结构相比,可逆概要数据结构以相同的存储空
间和估计精度,将查找速度提高了约4个量级。
关键词:数据结构;随机映射;多项式域;中国剩余定理;
频繁项集
中图分类号:T P 301.6;T P 311.12
文献标识码:A
文章编号:100020054(2008)1021625204
Reversible sketch da ta structure
FENG W enfe ng 1,2,HUANG Yongfe ng 1,L I Xing 1
(1.D epart men t of Electron ic Eng i neer i ng ,Tsi nghua Un iversity ,Be ij i ng 100084,Ch i na ;
2.D epart men t of Co mputer Sc ience ,Henan Polytechn ic Un iversity ,
J i aozuo 454000,Chi na )Abstract :D ue to the irreversibility of random hash m app ing,current sketch data structures have to traverse the key address space to find frequent item s .
T he Ch inese rem ainder theo rem fo r a
po lynom ial field w as used to design a fam ily of reversible H ash functi ons on the po lynom ial field,w ith a reversible sketch data structure,w hich only needs to traverse the hash address space to find and evaluate frequent item s and then computes the responsible keys by reverse hash m app ing .Experi m ental results show that the reversible sketch i m p roves the finding speed by about four m agnitudes over the Count 2M in sketch w ith al mo st the sam e sto rage space and accuracy .
Key words :data structure;random p ro jecti on;po lynom ial field;
Chinese rem ainder theo rem;frequent item s
在大规模高速网络环境中,实时地查找和估计网络中的“重击”流量是网络流量分析中的一个基本问题,是网络异常监测、流量工程等技术的基本组件。近几年,互联网的带宽越来越大,应用规模越来越大,不断实时的产生着海量的流量数据。对海量流
量数据的实时分析是网络安全和流量工程等的前提
之一,而查找和估计网络中的“重击”流量或者“热”流量更是其中的基本组件。
数据概要技术通过设计概要数据结构将大规模数据集合映射到亚线性的概要数据空间中,并根据概要数据空间的值来估计大规模数据集合的值,特别适用于大规模高速网络流量的实时分析。评估其性能的指标主要有更新速度、存储空间、查找速度、以及查找和估计精度。其中,实时的查找速度对于网络异常监测和流量工程等实时应用是关键的。
Coun t 2M in 概要数据结构[1]
是具有代表性的和
高效的数据概要技术。设[U ]表示集合{0,1,…,U -1},[W ]表示集合{0,1,…,W -1},指定一个质数P >U >W ,那么H ={h (x )=((ax +b )m od P )m od W x ∈[U ],a ,b ∈[P ]}是一族实现从[U ]到[W ]映射的两两相互独立的H ash 函数族[2]
。通过在H ash 函数族H 中均匀随机选取d 个H ash 函数h 1,
…,h d 实现从集合[U ]到集合[W ]的随机映射。
Coun t 2M in 概要数据结构在内存中维护一个二维计数数组C [d ][W ]。当数据流元组(x ,v ),其中x ∈[U ],v ∈Z 到达时,执行更新程序{fo r i =1to d ,C [i ][h i (x )]+=v ;},并且在任何时候以m in i (C [i ][h i (x )])来估计关键字x 的当前属性值。
然而,由于随机H ash 函数的不可逆,Coun t 2M in 等目前的概要数据结构必须遍历大规模数据的地址空间以查找频繁项集。基于此,本文提出了可逆概要数据结构,只需遍历概要数据空间即可查找频繁项集,极大提高了查找速度。
1 可逆概要数据结构的设计和实现
1.1 多项式域上的Ha sh函数族
设Z
2
={0,1},Z2[t]是Z2上的多项式集合, p(t)是Z2[t]中的一个n次不可约多项式。令Z2[t]p(t)表示Z2[t]中所有次数 Z2[t]p(t)= {a0+a1t+a2t2+…+a n-1t n-1 a0,a1,a2,…,a n-1∈Z2}. 设a(t),b(t)∈Z2[t]p(t),它们的和与积分别定义如下。 和:a(t) (t)=(a(t)+b(t))m od p(t)= a(t)+b(t); 积:a(t)⊙b(t)=(a(t) b(t))m od p(t). 这种Z 2 [t]p(t)中的加法和乘法分别被叫做模p(t)的加法和模p(t)的乘法。可以验证Z2[t]p(t)对于如上规定的加法运算和乘法运算是域[3]。 本文下面用Z n 2来代表Z2[t]p(t)并不会引起混淆。 设关键字x=(x ,x1,x2,…,x u-1)∈{0,1}u,当u≤n时,可以将x看作域Z n2上的元素x(t)。Z n2上的一一映射定义如下: f(x)=a(t)⊙x(t) b(t)= (a(t) x(t)+b(t))m od p(t).(1)其中:a(t)、b(t)是从Z n2中均匀随机选取的元素, p(t)是均匀随机选取的n次不可约多项式。 很明显,f(x)的逆函数为 x=f-1(f(x))= (a-1(t) f(x)-b(t))m od p(t).(2)其中:a-1(t)是元素a(t)在域Z n2中的逆元素, -b(t)是元素b(t)在域Z n2中的负元素。 从{0,1}u到{0,1}m的H ash函数定义如下: h(x)=f(x)m od p m(t)= ((a(t) x(t)+b(t))m od p(t))m od p m(t).(3)其中p m(t)是Z2[t]中的一个m次不可约多项式。 该H ash函数族定义如下: H={h(x)=f(x)m od p m(t) p m(t)是m次不可约多项式}. 从H中均匀随机选取H ash函数可以通过均匀随机选取m次不可约多项式p m(t)实现。如果以h∈R H表示从H中均匀随机选取h,那么: h∈R HΖp m(t)∈R{所有m次不可约多项式}. 设h i (x)=f(x)m od p i m(t)(i=1,2,…,d)表示从H中均匀随机选取的第i个H ash函数,其中p m i(t)表示均匀随机选取的第i个m次不可约多项 式。根据un iversal H ash[3]的定义,可以验证:Πx,y∈{0,1}u∧x≠y,Πi∈[1,d], P r h∈ R H [h i(x)=h i(y)]=1 2m. 即函数族H是un iversal H ash函数族。 定理1[中国剩余定理] 设f 1 (t),f 2 (t),…, f d(t)是Z2[t]中d个两两互素的次数≥1的多项式, 令f(t)=f 1 (t)f 2 (t)…f d (t),那么任给g i (t)∈ Z2[t]f i (t),i=1,2,…,d,都有唯一的一个g(t)∈Z2[t]f(t)使后面的d个同余式:g(t)≡g i(t)m od f i(t),i=1,2,…,d,同时成立。如果令f^i(t)= f(t) f i(t),那么对任一i=1,2,…,d,f^i(t)与f i(t)都互素,因而有d对多项式a i(t)和b i(t)(i=1, 2,…,d)存在,使得1=a i(t)f^i(t)+b i(t)f i(t)(i=1, 2,…,d)成立。如果令e i(t)=(a i(t)f^i(t))m od f(t) (i=1,2,…,d),那么 g(t)=(e1(t)g1(t)+e2(t)g2(t)+…+ e d(t)g d(t))m od f(t).(4) 显然,H ash函数族H中均匀随机选取的d个 不可约多项式p m 1 (t),…,p m d(t)之间两两互素,从而符合中国剩余定理的条件。根据中国剩余定理,如果令p m(t)=p m1(t)p m2(t)…p m d(t),p^m i(t)=p m(t) p m i(t) (i=1,2,…,d),利用辗转相除法求得满足1=a i(t)p^m i(t)+b i(t)p m i(t)的a i(t),并令e i(t)= a i(t)p^m i(t)m od p m(t),那么有 f(x)=(e1(t)h1(x)+e2(t)h2(x)+…+ e d(t)h d(x))m od p m(t),(5)进而有 x=h-1(h1,…,h d)= (a-1(t) ((e1(t)h1(x)+e2(t)h2(x)+…+ e d(t)h d(x))m od p m(t))-b(t))m od p(t).(6) 图1给出了当关键字地址空间位数u=16,多项式域次数n=16,H ash地址空间位数m=8,随机H ash函数个数d=2时,如上所述的可逆H ash函数的示意图。 2.2 可逆概要数据结构 可逆概要数据结构通过从函数族H中随机选 取d个哈希函数h 1 ,…,h d来实现从关键字地址空间U={0,1}u到哈希地址空间W={0,1}m的随机映 6261清华大学学报(自然科学版)2008,48(10) 实线箭头所示是随机哈希函数h i (x)(i=1,2,…,d),虚 线所示是其逆函数h-1(h1,…,h d)。 图1 可逆哈希函数示意图 (u=16,n=20,m=10,d=2时) 射。可逆概要数据结构在内存中维护d个哈希表,每个哈希表的大小是W=2m,即维护一个二维数组C [d][W]。当数据流元组(x,v),其中x∈U到达时, 执行更新程序{fo r i=1to d do C[i][h i (x)]+= v;},并且在任何时候遍历C[d][W]以查找和估计频繁项集。 可逆概要数据结构的实现中,需要从Z n 2中均匀随机选取a(t)、b(t),和均匀随机选取n次不可约多项式p(t),以及均匀随机选取d个m次不可约多项 式{p m 1(t),…,p m d (t)}。本文选用RAN RO T算法[4]作 为均匀随机选取a(t)、b(t)的算法,选用文[5]所描述算法实现不可约多项式p(t)和{p m1(t),…,p m d(t)}的均匀随机选取。 算法1 频繁项集查找和估计算法。 1)遍历d个H ash表C[d][W],获得d组大于阈值5的元素值F i ={(j i,C[i][j i]) C[i][j]>5}。 2)求D escarte积:F=F1…F d={(j1,…,j d, m in 1≤i≤d (C[i][j i ]))}。 3)根据式(6)求关键字x=h-1(j1,…,j d)。 4)如果x∈{0,1}u,则输出;否则抛弃x。 从算法1可以看出,当n-u=0时,算法的效率 很高;随着n-u的逐渐增大,算法效率逐渐降低,这是下一步需要解决的问题。 3 实验结果和分析 在一台1.7GH z主频、512M B内存的笔记本电脑上安装W indow s2000P rofessi onal操作系统,用软件Cyg W in模拟一个L inux环境。考虑到实时网络流量分析对程序性能的要求很高,所以采用C语言来实现程序。 实验数据的获取:第一类是人工生成数据。实现一个人工数据生成程序,根据偏度参数生成在数据域U=224上的数据集,该类数据称为SYN数据;第二类是实测的由IP数据包头组成的网络流量数据。数据来源是美国应用网络研究国家实验室(NLAN R)的被动测量和分析工作组(PM A)。本文使用由其W AND研究组在A uck land大学用DA G3测量系统测量到的2001年2月25日的IP数据包包头数据[6]。这个网络流量数据包括3500多万个IP数据包包头,数据格式是DA G3,每个DA G记录存储40B的IP包头数据,包括了IP数据包包头的几乎全部内容。编写程序对DA G格式数据进行解析,分别抽取出其中的源IP地址、目的IP地址字段,称为SRC IP数据和D ST IP数据。因为W AND研究组为了保密将所有源IP地址和目的IP地址的第一个字节替换为10,所以将第一个字节舍弃,从而得到24b 的源和目的IP地址,即U=224。 性能指标如下。第一,算法和结构对时间和空间资源的需求,包括:存储空间大小、更新时间、查找和估计频繁项集时间。第二,查找和估计频繁项集的精度,包括:①召回率,即是不是能够查找到所有的频繁项。从上一节可逆概要数据结构的实现可知,查找和估计频繁项集算法的召回率为100%。②查找准确率,即真正的频繁项在查找到的频繁项中所占的比率。查找到的频繁项中有一些实际上并不是频繁项,这是算法的误差;③估计误差率,即估计的频繁项的频值和该频繁项的实际频值的相对误差E x=(z^x-z x) z x,以整个频繁项集的相对误差的均值A vg(E x )和最大值M ax(E x )来表示。相对误差的均值反映了算法的平均误差,相对误差的最大值反映了算法的最大误差。 选择n=u=24,m=12,d=2,阈值5=0.003,那么W=212=4096。给C M、R EV2种概要数据结构相同的参数。表1给出了C M、R EV这2种概要数据结构的存储空间、更新时间和查找频繁项集时间。其中,C M结构和R EV结构占用几乎相同的内存空间,R EV结构的更新速度是C M结构的1 2左右。C M结构查找和估计频繁项集的时间很长,因为它要遍历U=224的源关键字地址空间,而R EV结构只需要遍历2×212大小的H ash地址空间,从而查找和估计频繁项集的时间比C M结构提高了约4个量级。可以看出:R EV结构以和C M结构几乎相同的存储空间和1 2左右的更新时间获得了查找频繁项集速度的极大提升。并且,与基于质数模运 7261 冯文峰,等: 可逆概要数据结构 算的C M 结构不同,R EV 结构基于GF (2)的异或运算和与运算,非常适合用硬件实现。在高速骨干网络中,很多的算法需要用硬件或者固件实现,此时,R EV 概要数据结构比C M 概要数据结构更有实用价值。 表1 C M REV 结构的存储空间、 更新时间和查找频繁项集时间概要数据结构名称 存储空间kB 更新时间 n s 查找和估计频繁项集时间 m s C M 65.632012500R EV 65.8 600 1.2 在相同的参数设置下,比较C M 和R EV 概要数 据结构的查找和估计精度,包括3个指标:查找准确率、平均相对误差率和最大相对误差率。图2—4分别显示和比较了以SRC IP 数据为实验数据时,C M 和R EV 两种概要数据结构的查找准确率、平均相对误差和最大相对误差3个指标。从图中可以看出,R EV 概要数据结构的查找和估计精度不低于C M 概要数据结构,甚至比 C M 结构有少许提高。用理论工具, 给出R EV 概要数据结构和C M 概要数据结构在查找和估计精度方面的差别是下一步研究的目标。 图2 SRC IP 数据的查找准确率 图3 SRC IP 数据的平均误差率 图4 SRC IP 数据的最大误差率 4 结 论 本文以提高概要数据结构中查找和估计频繁项 集的速度为目标,通过设计多项式域上可逆的H ash 函数族,实现了一类可逆概要数据结构。与目前具有代表性的Coun t 2M in 概要数据结构相比,该可逆概要数据结构以相同的存储空间和估计精度,以及1 2左右的更新速度,将查找速度提高了约4个量 级。但是该可逆概要数据结构还存在n -u 必须较小以保证查找速度的缺点,怎样解决该问题是下一步的研究目标。 参考文献 (References ) [1] Co rmode G,M uthukrishnan S .A n i m p roved data stream summ ary:T he count 2m in sketch and its app licati ons [J ].J ou rna l of A lg orithm s ,2005,55(1):58-75.[2] Carter J L ,W egm an M N. U niversal classes of hash functi ons [J ].J ou rna l of C o m p u ter and S y ste m S ciences (J CS S ),1979,18(2):143-154.[3] 万哲先.代数导引[M ].北京:科学出版社,2004:41-60. WAN Zhexian.A lgebra Introducti on [M ].Beijing:Science P ress,2004:41-60.(in Chinese ) [4]A gner Fog .P seudo random num ber generato rs [EB OL ]. (2005).h ttp: www.agner .o rg random .[5] R abin M O.F ingerp rinting by random po lynom ials,R epo rt TR 215281 [R ]. Center fo r R esearch in Computing T echno logy,H arvard U niversity,1981. [6]NLAN R.N etw o rk traffic packet header traces [EB OL ]. (2002).h ttp: pm a .nlanr .net T races . 8 261清华大学学报(自然科学版)2008,48(10) 复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i 教材：《数据结构》严蔚敏吴伟民清华大学出版社 《数据结构算法实现及解析》高一凡西安电子科技大学出版社 第一部分数据结构概述 一、定义（研究是数据结构的存储和数据的操作的） 如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫做算法。 数据结构= 个体的存储（从某个角度而言，可忽略）+ 个体与个体之间关系的存储（核心） 算法= 对存储数据的操作 二、算法 解题的方法和步骤 衡量算法的标准 1.时间复杂度 大概程序要执行的次数，而非执行的时间 2.空间复杂度 算法执行过程中大概所占用的最大内存 3.难易程度（即可读性） 4.健壮性 三、数据结构的地位 数据结构是软件中最核心的内容 程序= 数据的存储+ 数据的操作+ 可以被计算机执行的语言 第二部分预备知识 一、指针 指针的重要性：指针是C语言的灵魂 定义 地址：内存单元的编号 从零开始的非负整数 范围：0--FFFFFFFF（即0--4G-1） 指针： 指针就是地址，地址就是指针 指针变量是存放内存单元地址的变量 指针的本质是一个操作受限的非负整数（只能进行减运算）分类： 1.基本类型的指针 2.指针和一维数组的关系 二、结构体 为什么会出现结构体 为了表示一些复杂的数据，而普通的基本类型变量无法满足要求什么叫结构体 结构体是用户根据实际需要自己定义的数据类型 如何使用结构体 两种方式： struct Student st = {1000, "zhangsan", 20} struct Student * pst = &st; 1.st.sid 2.pst->sid pst所指向的结构体变量中的sid这个成员 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（） A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（）。 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（） A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 空间数据库概论答案 【篇一：数据库系统概论试题及答案整理版】 >第一章绪论 一、选择题 1. 在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。在这几个 阶段中，数据独立性最高的是a阶段。 a．数据库系 2. 数据库的概念模型独立于a。 a．具体的机器和dbms 3. 数据库的基本特点是b。 a.(1)数据结构化 (2)数据独立性 (3)数据共享性高，冗余大，易移植 b.(1)数据结构化 (2)数据独立性 (3)数据共享性高，冗余小，易扩充 c.(1)数据结构化 (2)数据互换性 (3)数据共享性高，冗余小，易扩充 (4)统一管理和控制(4)统一管理和控制(4)统一管理和控制 b．e-r图 c．信息世界 d．现实世界 b．文件系统 c．人工管理 d．数据项管理 d.(1)数据非结构化 (2)数据独立性 (3)数据共享性高，冗余小，易扩充(4)统一管理和控制 4. b是存储在计算机内有结构的数据的集合。 a．数据库系统 5. 数据库中存储的是c。 a. 数据 6. 数据库中，数据的物理独立性是指c。 a．数据库与数据库管理系统的相互独立 b．用户程序与dbms的相互独立 c．用户的应用程序与存储在磁盘上数据库中的数据是相互独立的d．应用程序与数据库中数据的逻辑结构相互独立 7. 数据库的特点之一是数据的共享，严格地讲，这里的数据共享是指d。 a．同一个应用中的多个程序共享一个数据集合 b．多个用户、同一种语言共享数据 c．多个用户共享一个数据文件 d．多种应用、多种语言、多个用户相互覆盖地使用数据集合 b. 数据模型 c. 数据及数据间的联系 d. 信息 b．数据库 c．数据库管理系统 d．数据结构 8. 数据库系统的核心是b。 a．数据库 9. 下述关于数据库系统的正确叙述是 a 。 a．数据库系统减少了数据冗余b．数据库系统避免了一切冗余 c．数据库系统中数据的一致性是指数据类型一致 d．数据库系统比文件系统能管理更多的数据 10. 数将数据库的结构划分成多个层次，是为了提高数据库的 b ①和 b ②。①a．数据独立性 ②a. 数据独立性 11. 数据库(db)、数据库系统(dbs)和数据库管理系统(dbms)三者之间的关系是 a 。 a．dbs包括db和dbmsc．db包括dbs和dbms 12. 在数据库中，产生数据不一致的根本原因是d。 a．数据存储量太大 b．没有严格保护数据 d．数据冗余 b．ddms包括db和dbs d．dbs就是db，也就是dbms b．逻辑独立性 b．物理独立性 c．管理规范性 c．逻辑独立性 d．数据的共享 b．数据库管理系统 c．数据模型 d．软件工具 d．管理规范性 c．未对数据进行完整性控制 13. 数据库管理系统(dbms)是d。 a．数学软件 第一章概论习题 一、选择题 1．数据结构是具有【B 】的数据元素的集合。 A．相同性质B．相互关系C．相同运算D．数据项2．在计算机的存储结构中，逻辑上相邻的结点存储在物理位置上也相邻的连续存储单元里，称之为【 B 】。 A．逻辑结构B．顺序存储结构C．链式存储结构D．散列存储结构3．语句for(i=1;i<=n;i++) x++;的时间复杂度为【B 】。 A．O(1) B．O(n) C．O(n2) D．O(n3) 4．下面不属于数据的存储结构的是【D 】。 A．散列存储B．链式存储C．索引存储D．压缩存储5．数据结构研究的是数据的【 A 】及它们之间的相互关系。 A．存储结构和逻辑结构B．存储和抽象C．理想与抽象D．理想与逻辑6．下面程序段的时间复杂度是【D 】。 for(i=0;i<2*n;i++) for(j=1;j<3*n;j++) A[i][j]=0; A．O(n) B．O(5n) C．O(6n2) D．O(n2) 7．数据的逻辑结构有两大类，分别是【 B 】。 A．顺序存储结构和链式存储结构B．线性结构和非线性结构 C．压缩结构和非压缩结构D．有序结构和无序结构 8．以下与数据的存储结构无关的术语是【D 】。 A．循环队列B．链表C．哈希表D．栈 9．算法分析的两个主要方面是【A 】。 A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 10．下面程序段的时间复杂度是【D 】。 S=0; for(i=0;i 空间数据挖掘 一、空间数据库概述 空间数据库指的是地理信息系统在计算机物理存储介质上存储的与应用相关的地理空间数据的总和，一般是以一系列特定结构的文件的形式组织在存储介质之上的。空间数据库的研究始于20世纪70年代的地图制图与遥感图像处理领域，其目的是为了有效地利用卫星遥感资源迅速绘制出各种经济专题地图。由于传统的关系数据库在空间数据的表示、存储、管理、检索上存在许多缺陷，从而形成了空间数据库这一数据库研究领域。而传统数据库系统只针对简单对象，无法有效的支持复杂对象（如图形、图像）。 空间数据挖掘是指从空间数据库中抽取没有清楚表现出来的隐含的知识和空间关系，并发现其中有用的特征和模式的理论、方法和技术。空间数据挖掘和知识发现的过程大致可分为以下多个步骤：数据准备、数据选择、数据预处理、数据缩减或者数据变换、确定数据挖掘目标、确定知识发现算法、数据挖掘、模式解释、知识评价等，而数据挖掘只是其中的一个关键步骤。但是为了简便，人们常常用空间数据挖掘来代替空间数据挖掘和知识发现。 空间数据挖掘与传统数据挖掘的不同表现在以下三个方面： 传统数据挖掘处理的是数字和类，而空间数据则是一些更为复杂的数据类型；传统数据挖掘通常具有显式的输入，而空间数据挖掘的输入则常常是隐式的；在传统数据挖掘中，有一个至关重要的前提假设：数据样品是独立生成的。而这一假设在空间数据分析中是不成立的。事实上，空间数据之间是高度自关联的。 二、空间数据挖掘的技术特点 (一)数据挖掘算法具有高效、可测的特点 数据库一般有数千个表和属性以及上百万个元组。数据库中千兆级别的数据已不再罕见，因为万亿级别的数量数据库已经腾空出世，取代了千兆级别的数据库。高维空间的海量数据库不但使搜索的空间变大，而且更容易发现模式存在的错误，所以充分利用相关知识去改变维数，降低维数，删除多余的数据，使数据挖掘的算法更具高效性。海量空间数据提供知识的算法要有可测性、高效性。多项式算法和指数算法没有实际的使用价值，但是若把算法换成以有限的数据做成特定的模型来获取合适的参数，实现的价值将会相当可观。 (二)所挖掘的信息来源于各种数据 用因特网、广域网、局域网与其他数据源组成一个结构复杂、空间庞大的数据库。数据进行挖掘主要是在各种语义的非格式化和格式化的数据中挖掘数据知识，这种数据挖掘可以弥补庞大、复杂的数据库所不能查询的数据知识。数据库本身已拥有分布广、规模大、数据挖掘方法复杂等特性，该特性的要求是要构建一种分布平行的数据挖掘技术。 第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2. 数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 (补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 ) 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。(有时候也 叫做属性。) 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1. 集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2. 线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3. 树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素 (根)之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4. 图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1. 顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2. 链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5. 时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n 无关系T(n)=O(1) 2. 线性阶：算法的时间复杂度与问题规模 n 成线性关系T(n)=O(n) 3. 平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 数据结构基础知识 标准化文件发布号：（9312-EUATWW-MWUB-WUNN-INNUL-DQQTY- 复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i 1 概述 一、选择题： 1、下列算法的时间复杂度是（） for(i=0;i 数据结构概论考核题 C. 0 1 3 2 D.0 3 1 2 （第9题配图：数组的下标为0,1,2,3） 10.对于哈希函数H(key)=key%13,被称为同义词的关键字是( D ) A.35和41 B.23和39 C.15和44 D.25和51 11.图的深度优先遍历类似于二叉树的( A ) A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 12.下述几种排序方法中，稳定的排序算法是( A ) A.直接插入排序 B.快速排序 C.堆排序 D.希尔排序 13.依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位 置上的方法，称为( C ) A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序 14.二叉树是非线性数据结构，所以 ( A ) A.它不能用顺序存储结构存储 B.它不能用链式存储结构存储 C.顺序存储结构和链式存储结构都能存储 D.顺序存储结构和链式存储结构都不能使用 15.有8个结点的无向图最多有( B )条边。 A.14 B.28 C.56 D.112 二、填空题（每小题1分，共15分） 1 当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的__时间复杂度______。 2 设数组a[M](M为最大空间个数)作为循环队列Q的存储空间，front为队头指针(指向第一个存 （3）重复（2），直到U=V为止。 此时，TE中必含有n-1条边，则T=（V，{TE}）为N的最小生成树。 2. 假设通信电文使用的字符集为{a,b,c,d,e,f,g}，若这些字符在电文中出现的频度分别为：3， 35，13，15，20，5和9，分别求出这些字符的等长编码以及哈夫曼编码，并比较他们的编码长度。 8576 顺序线性表的基本操作 时间限制:1000MS 内存限制:1000K 提交次数:1714 通过次数:300 题型: 编程题语言: 无限制 Description 编写算法，创建初始化容量为LIST_INIT_SIZE的顺序表T，并实现插入、删除、遍历操作。本题目给出部分代码，请补全内容。 #include for(_________________________) printf("%d ",_________________________); // 请填空 } printf("\n"); return OK; } intListInsert_Sq(SqList&L,inti,int e) { // 算法2.4，在顺序线性表L中第i个位置之前插入新的元素e // i的合法值为1≤i≤L.length +1 // 请补全代码 } intListDelete_Sq(SqList&L,inti, int&e) { // 算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值 // i的合法值为1≤i≤L.length // 请补全代码 } int main() { SqList T; int a, i; ElemType e, x; if(_________________________) // 判断顺序表是否创建成功 { printf("A Sequence List Has Created.\n"); } while(1) { printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n"); scanf("%d",&a); switch(a) { case 1: scanf("%d%d",&i,&x); if(_________________________) printf("Insert Error!\n"); // 判断i值是否合法，请填空 elseprintf("The Element %d is Successfully Inserted!\n", x); 第一章绪论 1、简述下列术语：数据、数据元素、数据对象、数据结构、数据存储、存储结构、数据类型和抽象数据类型。 2、数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？ 3、什么是算法? 算法的5个特性是什么? 试根据这些特性解释算法与程序的区别。 4、什么叫算法的时间复杂度？怎样表示算法的时间复杂度？ 5、两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不一样，它们是否可以认作是同一个数据结构？为什么？ 6、试画出与下列程序段等价的框图 (1)product = 1; i = 1; while(i <= n){ product * = i ; i++; } (2)i = 0; do{ i++; }while ((i!=n)&&(a[i])!=x); 7、已知如下程序段 for(i=n;n>=1;n--) {语句1} { x++； {语句2} for(j=n;j<=i;j--)FOR j:=n {语句3} y++; {语句4} }； 求语句１到语句４的频度。 8、按增长率从小到大的顺序排列下列各组函数： 2100，（3/2）n，（2/3）n，（4/3）n，n，n3/2，n2/3，n!，n n，log2n，n/log2n，log2(log2n)，n log2n 9、试写一算法，自大至小依次顺序读入的三个整数X,Y,Z的值。 10、假设有A,B,C,D,E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每行的形式为： 项目名称性别校名成绩得分 编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。 11、设求解同一个问题有三种算法，三种算法各自的时间复杂度分别为O(n2)，O(2n)和O(nlg n)，哪种算法最可取？为什么？ 12、设n为已在算法前边定义的整数类型，并已知n为正整数，分析下列各算法中语句的执行次数，并给出各算法的时间复杂度T(n)。 (1) int i = 1, k = 0; while (i < n-1) { k = k + 10 * i; i = i + 1; } (2) int i = 1, k = 0; do { k = k + 10 * i; i = i + 1; }while (i != n); (3) int i = 1, j = 1; while (i <= n && j <= n) { i = i + 1; j = j + 1; } (4) int x = n; /* n > 1 */ int y = 0; while(x >= (y+1)*(y+1)) y++; 第一章概述习题 一、单选题 1、研究数据结构就是研究( D )。 A、数据的逻辑结构 B、数据的存储结构 C、数据的逻辑结构和存储结构 D、数据的逻辑结构、存储结构及其数据在运算上的实现 2、以下说法正确的是(C )。 A、数据元素是数据的最小单位 B、数据项是数据的基本单位 C、数据结构是带有结构的各数据项的集合 D、一些表面上很不相同的数据可以有相同的逻辑结构. 3、在数据结构中，数据的逻辑结构可以分成（C ）。 A. 内部结构和外部结构 B. 紧凑结构和非紧揍结构 C. 线性结构和非线性结构 D. 动态结构和静态结构 4、数据元素及其关系在计算机存储器内的表示，称为数据的（D ）。 A. 线性结构 B. 非线性结构 C. 逻辑结构 D. 存储结构 5、计算机算法必须具备输入、输出、（ B ）等5个特性。 A 可行性、可移植性和可扩展性 B 可行性、确定性和有穷性 C 确定性、有穷性和稳定性 D 易读性、安全性和稳定性 6、下面关于算法的叙述中错误的是（ A ）。 A. 一个算法应有一个或多个输入。 B. 算法最终必须由计算机程序实现 C. 为解决某问题的算法同为该问题编写的程序含义是相同的 D. 算法中的每条指令都必须有明确的含义 7、若一个算法的时间复杂度用T(n)表示，其中n的含义是（C ）。 A. 循环层数 B. 语句条数 C. 问题规模 D. 函数数量 8、下面说法正确的是（A）。 A. 健壮的算法不会因非法的数据输入而出现莫名其妙的状态 B. 程序一定是算法 C. 算法的时间复杂度只依赖于问题的规模 D. 算法的优劣与算法描述语言无关，但与所用计算机有关 9、下面程序段的时间复杂性的数量级为（C ） for (i=1;i<=n;i++) 1.1 程序设计的实质是数据表示和数据处理。 1.2数据要能被计算机加工处理，首先必须能够存储在机器中，成为能被机器直接操作的对象。数据在计算机存储器中的这种存在形式称为机内表示。将数据从机外表示转化为机内表示，这项任务称为数据表示。 1.3用适当的可执行语句编制程序，以便让计算机去执行对数据机内表示的各种操作，从而实现处理要求，即得到所需的结果，这项工作称为数据处理。 1.4 软件工程学认为：软件系统的生存期可分为软件计划、需求分析、软件设计、软件编码、软件测试和软件维护等六个阶段。程序设计包括前五个阶段（程序设计包括数据表示和数据处理两个方面）。 1.5数据结构课程集中讨论以设计阶段为核心、同时涉及编码阶段和分析阶段的一个小范围内的若干基本问题。概括的说，其主要内容包括：数据的逻辑结构、定义在逻辑结构上的基本运算、数据的存储结构和运算的实现。其中，数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式。由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立、选择和实现是数据结构的核心问题。 1.6 数据表示任务是逐步完成的，即数据表示形式的变化过程是：机外表示——》逻辑结构——》存储结构。 数据处理任务也是逐步完成的，即有转化过程：处理需求——》基本运算和运算——》算法。 数据表示与数据处理是密切相关的，数据处理方式总是与数据的相应的表示形式相联系，反之亦然。 2.1从数据结构的观点看，数据就分成三个不同的层次，即数据、数据元素和数据项。凡能被计算机存储、加工的对象通称为数据；数据元素是数据的基本单位，在程序中作为一个整体而加以考虑和处理，即数据元素被当作运算的基本单位，并且通常具有完整确定的实际意义，又被称为元素、结点、顶点或记录；数据元素又是数据项组成的，但数据项通常不具有完整确定的实际意义，或不当作一个整体对待，又称为字段或域，它是数据的不可分割的最小标识单位。 2.2从数据结构的观点看，重要的是数据元素之间的逻辑关系。所谓逻辑关系是指数据元素之间的关联方式或称“邻接关系”。数据元素之间逻辑关系的整体称为逻辑结构。数据的逻辑结构就是数据的组织形式。四类基本逻辑结构：集合、线性结构、树形结构和图状结构。1）逻辑结构与数据元素本身的形式、内容无关 2）逻辑结构与数据元素的相对的相对位置无关 3）逻辑结构与所含结点个数无关 2.3运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。这种加工以一个或多个逻辑结构及其他有关参数为对象，以经过修改的逻辑结构或从原逻辑结构中提取的有关信息为结果。根据操作的效果将运算分成两种基本类型： 1）加工型运算，其操作改变了原逻辑结构的“值” 2）引用型运算，其操作不改变原逻辑结构，只从中提取某些信息作为运算的结果 2.4假如A是S上的一些运算的集合，B是A的一个子集，使得A中每一运算都可以“归约”为B中一个或多个运算，而B中任一运算不可归约为别的运算，则称B中运算为（相对于A的）基本运算。 2.5对某些逻辑结构S和在S上的基本运算集B，由S和B构成的整体（S，B）往往在大量不同种类的实际问题的求解中反复出现，在此将这样的整体称为一个“数据结构”；线性表、队列、栈等都是数据结构，这三个数据结构有相同的逻辑结构但有不同的基本运算集。 3.1存储实现的基本目标是建立数据的机内表示，存储实现建立的机内表示应遵循选定的逻 第一章概论自测题答案 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11. 一个算法的效率可分为时间效率和空间效率。 二、单项选择题 （B）1. 非线性结构是数据元素之间存在一种： A）一对多关系B）多对多关系C）多对一关系D）一对一关系 （ C ）2. 数据结构中，与所使用的计算机无关的是数据的结构； A) 存储B) 物理C) 逻辑D) 物理和存储 （C）3. 算法分析的目的是： A) 找出数据结构的合理性B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性 （A）4. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性B) 正确性和简明性 C) 可读性和文档性D) 数据复杂性和程序复杂性 （ C ）5. 计算机算法指的是： A) 计算方法B) 排序方法C) 解决问题的有限运算序列D) 调度方法 （B）6. 计算机算法必须具备输入、输出和等5个特性。 A) 可行性、可移植性和可扩充性B) 可行性、确定性和有穷性 第1章习题解答 1.1什么是数据结构？一个数据结构结构的二元组定义形式是什么样的？举例解释其含义。 [解答] 概括地说，数据结构是互相有关联的数据元素的集合。也就是说，数据结构是由某个数据元素的集合和该集合中的数据元素之间的关系组成的，因此数据结构可以用一个二元组来表示。例如，B=（D，R），其中D是某一数据元素的集合，R是D上的关系的有限集。R所表示的是集合D的数据元素之间的逻辑关系，它表示的可能是数据元素之间客观存在的某种联系，也可能是为了处理问题的需要而人为组织的数据元素之间的某种关系，因此，称之为数据的逻辑结构。例如，一个农历节气表，就构成了一个数据结构，其数据元素是一年的农历二十四节气，数据元素之间的关系是节气的时间先后关系。又如，一个某年级学生的成绩排序表，也是一个数据结构，其数据元素是包含成绩项的该年级的学生记录，数据元素之间的关系是学生之间的成绩高低关系。为了在计算机中进行数据处理，必须把从实际问题中抽象出来的数据的逻辑结构映象到计算机的存储器中，即要把抽象出来的数据元素集合D 和数据元素之间的关系存储到计算机的存储器中，称之为数据的物理结构或存储结构，它是数据的逻辑结构在计算机中的表示。 1.2假设R是集合M上的一个关系，R的定义是什么？对实际问题而言，其含义是什么？ [解答] 如果R是对集合M自身的笛卡尔积所取的一个子集，那么我们就说“R是集合M上的一个关系”。对实际问题而言，它表示的是集合M中元素的某种相关性。例如，对于参加一个羽毛球比赛的运动员集合，可以用一个二元关系表示出各场比赛的胜负关系。对于一组课程的集合，可以用一个二元关系表示出各门课程之间的先修和后续关系等等。 1.3设有集合M={d1,d2,d3,d4,d5}上的一个关 R={(d1,d2),(d2,d4),(d4,d5),(d2,d5),(d1,d4),(d1,d5),(d3,d5),(d1,d3)}，试说明关系R具有什么样的性质。 [解答] 从二元关系的基本性质容易验证，该关系R是反自反的、反对称的、传递的关系。 因为关系R中没有(d i,d i)这样的元素，所以它是反自反的。 因为关系R中没有(元素d i,d j)和(d j,d i)同时存在的情况，所以它是反对称的。 关系R 的传递性表现在： 有元素(d1,d2),(d2,d4)，同时有元素(d1,d4), 有元素(d1,d2),(d2,d5)，同时有元素(d1,d5), 有元素(d1,d3),(d3,d5)，同时有元素(d1,d5)， 有元素(d1,d4),(d4,d5)，同时有元素(d1,d5)， 有元素(d2,d4),(d4,d5)，同时有元素(d2,d5)。 1.4什么是线性结构？什么是非线性结构？举例说明。 [解答] 第1章概述 第1章概述 本章学习要点 ◆了解数据结构的相关概念。 ◆了解并掌握数据的4种基本逻辑结构的特点。 ◆了解数据的各种基本存储结构。 ◆了解算法的相关概念，并能分析各种算法的时间复杂度和空间负责度。 数据结构（Data Structures）是随着计算机科学的发展而逐步形成的一门学科，目前已成为高等院校中计算机类各专业的核心课之一，同时也是统计类、经济类和工程软件设计类各专业的必修课程。本章的主要内容是对数据结构的基本概念和基本内容作一概要介绍，为此，简单回顾一下数据结构的发展与形成过程对于理解数据结构的内容和重要性是很有必要的。 1.1 数据结构的发展概况 众所周知，在40年代计算机刚诞生时，计算机所能处理的数据只能是由0或1组成的二进制数，此时还谈不上什么结构。后来虽然计算机可以处理十进制整数和十进制实数，也不过是由0到9这十个数字组成的序列，或再加上小数点，其数据的结构非常简单没有研究它的必要。 由于计算机技术的飞速发展和数据处理能力的不断提高，到60年代中期，各种高级程序设计语言相继出现，所能描述的数据类型逐渐丰富。例如，在FORTRAN语言中允许使用复数类型和数组类型数据。其中，复数是两个实数的有序对，而数组是同类型数据的一个有限序列，这自然是一种“结构”。在COBOL语言和PL/1语言中允许使用字符类型和记录类型数据，将计算机的应用领域由数值计算进一步扩充到非数值计算。其中，记录就是一种“结构”类型的数据，它把一组相互关联的不同类型的数据看作一个整体构成一种新的“结构类型”数据。有了“结构类型”的概念之后，各个数据之间不再孤立，这样便于表示和储存，也便于处理。后来，在LISP语言中又定义了一种带有层次性的表结构，并定义了许多相应的运算。这种层次结构是一种非线性的树型结构，也是本书中将要着重讨论的内容之一。 数据结构作为一门课程的形成和发展主要是在60年代后期。首先，在1968年由美国计算机协会（ACM）颁发了建议性的计算机教学计划，其中规定数据结构作为一门独立的课程，这在世界上是第一次。同一年，美国的计算机科学家D.E.Knuth教授在他的巨著《计算机程序设计的技巧》详细论述了数据的逻辑结构和数据的存储结构，并对各种结构给出了典型算法，为数据结构作为一门课程奠定了理论基础。 70年代初，随着大型程序以及大规模文件系统的出现，结构程序设计成为程序设计方法学的主要内容。在程序设计中，数据结构受到了极大的重视。认为程序设计的实质就是对要处理的问题选择一种最为适合的数据结构，同时在此结构上施加一种好的算法。1976年瑞士著名计算机科学家N.Wirth编著的《算法+数据结构=程序》一书正是这种程序设计思想的具体体现。 70年代中后期，由于数据库系统和数据检索系统的不断发展，在数据结构中进一步增加了文件管理的内容以及B-树和B+树的知识，使数据结构的内容得以丰富和进一步完善。从80年代开始，在我国高等院校的教学计划中已经将数据结构课程列为计算机类各专业的核心课程之一，在许多非计算机专业也把数据结构作为必修课或选修课程。数据结构是一门介于数学、计算机硬件和计算机软件三者之间的计算机专业基础课，是程序设计方法学、数据库 数据结构 逻辑结构（关系）： （1）集合：集合中任何两个结点之间都没有逻辑关系，组织形式松散。 （2）线性结构：元素之间存在着一对一的关系。依次排列形成一条“锁链”。 （3）树形结构：数据元素之间存在着一对多的关系，具有分支、层次特性。 （4）图状结构：数据元素之间存在多对多的关系，元素之间互相缠绕，具有网络特性。 存储结构：逻辑结构及数据元素在计算机中的表示。 （1）顺序存储方式（向量存储）、 （2）链式存储方式 （3）索引存储方式 （4）散列存储方式 抽象数据类型：一个数学模型和定义在这个数学模型的一组操作。 抽象的含义： ★．范围广包括已存在的数据类型和用户自定义数据类型 ★★．实现方法不同，但数学特性相同—数学抽象特性 ADT抽象数据类型名 { 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作：<基本操作的定义> }ADT抽象数据类型名 数据结构 数据结构就是要研究数据之间的结构关系。具体来说，它包括数据的逻辑结构和物理结构，以及在这些结构上定义的相应的运算。 按照某种逻辑结构组织的一组数据，按一定的存储方式将它们映射到计算机的存储器中，并且在这些数据上定义了一个运算的集合运算的结果保持原来的结构。 结构 结构是指同一数据对象中各数据元素之间存在的关系。 数据结构课程研究的主要内容 【1】研究数据元素之间的客观联系。（逻辑结构） 【2】研究具有某种逻辑关系的数据在计算机存储器内的存储方式。（存储结构） 【3】研究如何在数据的各种结构。（逻辑的和物理的）的基础上对数据实施一系列有效的基本操作。 数据结构举例 例1：一系列整数，我们可以用算术运算“+、—、*、/”等进行运算，此时数据对象是整数集合，那么，数据对象整数再加上“+、—、*、/”等符号的运算就构成了一个数据结构的定义。 数据结构课程研究的主要内容数据结构复习提纲(整理)
数据结构概述
数据结构第1章作业
空间数据库概论答案
第一章数据结构概论习题
空间数据库报告分析
数据结构复习要点(整理版).docx
数据结构基础知识
数据结构习题集
(完整版)数据结构概论
数据结构第一章
数据结构第一章 概述习题↓
数据结构 第一章 概述习题
数据结构第一章
第1章数据结构概论自测题及答案
数据结构第1章习题解答..
数据结构《第1章 概述》习题解答
数据结构第一章重点总结