数据结构论文总结

基于安卓的音乐播放器论文中用到了哪些数据结构同学你好，毕设，俺给你发现成的

人们把客观存在的事物以数据的形式存储到计算机中，经历了对现实生活中事物特性的认识、概念化到计算机数据库里的具体表示的逐级抽象过程，即现实世界－概念世界－机器世界三个领域。有时也将概念世界称为信息世界；将机器世界称为存储或数据世界。 一、三个世界 1、现实世界 人们管理的对象存于现实世界中。现实世界的事物及事物之间存在着联系，这种联系是客观存在的，是由事物本身的性质决定的。例如学校的教学系统中有教师、学生、课程，教师为学生授课，学生选修课程并取得成绩。 2、概念世界 概念世界是现实世界在人们头脑中的反映，是对客观事物及其联系的一种抽象描述，从而产生概念模型。概念模型是现实世界到机器世界必然经过的中间层次。涉及到下面几个术语： 实体：我们把客观存在并且可以相互区别的事物称为实体。实体可以是实际事物，也可以是抽象事件。如一个职工、一场比赛等。 实体集：同一类实体的集合称为实体集。如全体职工。注意区分"型"与"值"的概念。如每个职工是职工实体"型"的一个具体"值"。 属性：描述实体的特性称为属性。如职工的职工号，姓名，性别，出生日期，职称等。 关键字：如果某个属性或属性组合的值能唯一地标识出实体集中的每一个实体，可以选作关键字。用作标识的关键字，也称为码。如"职工号"就可作为关键字。 联系：实体集之间的对应关系称为联系，它反映现实世界事物之间的相互关联。联系分为两种，一种是实体内部各属性之间的联系。另一种是实体之间的联系。 3、机器世界 存入计算机系统里的数据是将概念世界中的事物数据化的结果。为了准确地反映事物本身及事物之间的各种联系，数据库中的数据必须有一定的结构，这种结构用数据模型来表示。数据模型将概念世界中的实体，及实体间的联系进一步抽象成便于计算机处理的方式。 数据模型应满足三方面要求：一是能比较真实地模拟现实世界；二是容易为人所理解；三是便于在计算机上实现。数据结构、数据操作和完整性约束是构成数据模型的三要素。数据模型主要包括网状模型、层次模型、关系模型等，它是按计算机系统的观点对数据建模，用于DBMS的实现。 关系数据库采用关系模型作为数据的组织方式。 关系数据库因其严格的数学理论、使用简单灵活、数据独立性强等特点，而被公认为最有前途的一种数据库管理系统。它的发展十分迅速，目前已成为占据主导地位的数据库管理系统。自20世纪80年代以来，作为商品推出的数据库管理系统几乎都是关系型的，例如，Oracle，Sybase，Informix，Visual FoxPro等。 网络数据库也叫Web数据库。促进Internet发展的因素之一就是Web技术。由静态网页技术的HTML到动态网页技术的CGI、ASP、PHP、JSP等，Web技术经历了一个重要的变革过程。Web已经不再局限于仅仅由静态网页提供信息服务，而改变为动态的网页，可提供交互式的信息查询服务，使信息数据库服务成为了可能。Web数据库就是将数据库技术与Web技术融合在一起，使数据库系统成为Web的重要有机组成部分，从而实现数据库与网络技术的无缝结合。这一结合不仅把Web与数据库的所有优势集合在了一起，而且充分利用了大量已有数据库的信息资源。图1-1是Web数据库的基本结构图，它由数据库服务器（Database Server）、中间件（Middle Ware）、Web服务器（Web Server）、浏览器（Browser）4部分组成。 Web数据库的基本结构它的工作过程可简单地描述成：用户通过浏览器端的操作界面以交互的方式经由Web服务器来访问数据库。用户向数据库提交的信息以及数据库返回给用户的信息都是以网页的形式显示。1 Internet技术与相关协议Internet技术在Web数据库技术中扮演着重要的角色。Internet（因特网）专指全球最大的、开放的、由众多网络相互连接而成的计算机网络，并通过各种协议在计算机网络中传递信息。TCP/IP协议是Internet上使用的两个最基本的协议。因此也可以说Internet是全球范围的基于分组交换原理和TCP/IP协议的计算机网络。它将信息进行分组后，以数据包为单位进行传输。Internet在进行信息传输时，主要完成两项任务。（1）正确地将源信息文件分割成一个个数据包，并能在目的地将源信息文件的数据包再准确地重组起来。（2）将数据包准确地送往目的地。TCP/IP协议的作用就是为了完成上述两项任务，规范了网络上所有计算机之间数据传递的方式与数据格式，提供了数据打包和寻址的标准方法。1．TCP/IP协议TCP协议（Transmission Control Protocol，传输控制协议）规定了分割数据和重组数据所要遵循的规则和要进行的操作。TCP协议能保证数据发送的正确性，如果发现数据有损失，TCP将重新发送数据。2．IP协议在Internet上传送数据往往都是远距离的，因此在传输过程中要通过路由器一站一站的转接来实现。路由器是一种特殊的计算机，它会检测数据包的目的地主机地址，然后决定将该数据包送往何处。IP协议（Internet Protocol，网际协议）给Internet中的每一台计算机规定了一个地址，称为IP地址。IP地址的标准是由4部分组成（例如11），其中前两部分规定了当前使用网络的管理机构，第3部分规定了当前使用的网络地址，第4部分规定了当前使用的计算机地址。Internet上提供的主要服务有E-mail、FTP、BBS、Telnet、WWW等。其中WWW（World Wide Web，万维网）由于其丰富的信息资源而成为Internet最为重要的服务。3．HTTP协议HTTP协议（Hypertext Transfer Protocol，超文本传输协议）应用在WWW上，其作用是完成客户端浏览器与Web服务器端之间的HTML数据传输。2 Web的工作原理与工作步骤万维网简称为Web。Web可以描述为在Internet上运行的、全球的、交互的、动态的、跨平台的、分布式的、图形化的超文本信息系统。1．Web的工作原理Web是伴随着Internet技术而产生的。在计算机网络中，对于提供Web服务的计算机称为Web服务器。Web采用浏览器/服务器的工作方式。每个Web服务器上都放置着大量的Web信息。Web信息的基本单位是Web页（网页），多个网页组成了一个Web节点。每个Web节点的起始页称为“主页”，且拥有一个URL地址（统一资源定位地址）。Web节点之间及网页之间都是以超文本结构（非线性的网状结构）来进行组织的。2．Web的工作步骤Web的工作步骤如下。（1）用户打开客户端计算机中的浏览器软件（例如Internet Explorer）。（2）用户输入要启动的Web主页的URL地址，浏览器将生成一个HTTP请求。（3）浏览器连接到指定的Web服务器，并发送HTTP请求。（4）Web服务器接到HTTP请求，根据请求的内容不同作相应的处理，再将网页以HTML文件格式发回给浏览器。（5）浏览器将网页显示到屏幕上 图1-2 Web的工作步骤3 WWW世界中的标记语言1．HTML语言HTML（Hypertext Markup Language，超文本标记语言）是创建网页的计算机语言。所谓网页实际上就是一个HTML文档。文档内容由文本和HTML标记组成。HTML文档的扩展名就是html或htm。浏览器负责解释HTML文档中的标记，并将HTML文档显示成网页。（1）HTML标记HTML标记的作用是告诉浏览器网页的结构和格式。每一个标记用尖括号<>括起来。大多数标记都有一个开始标记和一个结束标记。标记不分大小写。多数标记都带有自己的属性。例如字体标记有FACE、COLOR、SIZE等属性：FACE定义字体；COLOR定义字体的颜色；SIZE定义字体的大小。使用格式： BEIJING 。网页中有很多文本链接和图片链接。链接，又被称为超链接，用于链接到WWW万维网中的其他网页上。在HTML文档中表示超链接的标记是，通过属性HREF指出链接的网页地址URL。使用格式： BEIJING 。（2）HTML程序HTML程序必须以标记开始，以标记结束。在和标记之间主要由两部分组成：文件头和文件体。文件头用标记 来标识，文件体用标记来标识。在文件的头部通常包含整个网页的一些信息。例如标记是用来说明网页的名称；标记是用来说明网页的其他信息，如设计者姓名和版权信息等。所有在浏览器中要显示的内容称为网页的主体，必须放在标记中。下面给出的是一个空网页的HTML程序。 (在此标记中写网页的内容) （3）HTML规范HTML规范又称为HTML标准，它总在不断地发展。每一新版本的出现，HTML都会增加新的特性和内容。有关HTML版本的详细信息请访问网站。在不同的浏览器中，网页的显示效果可能会有所不同。每一个浏览器都使用自己独特的方式解释HTML文档中的标记，并且多数浏览器不完全支持HTML的所有特性。因为，像Microsoft和Netscape公司在HTML标准上又开发了一些特有的HTML标记和属性，称之为HTML的扩展。这些标记和属性只被他们自己的浏览器所识别，不可能被其他公司的浏览器识别。如果浏览器不能识别HTML文档中的标记，则会忽略这个标记。（4）HTML程序的编辑环境与运行环境HTML文档是一个普通的文本文件（ASCII），不包含任何与平台、程序有关的信息。因此HTML文档可以利用任何文本编辑器来方便地生成。要注意的是HTML文档的扩展名必须是html或htm。运行HTML文档可以在任何浏览器下进行，并可在浏览器上查看网页的HTML源代码。关于HTML语言中标记的种类与使用方法将会在第5章中更详细地进行介绍。2．可扩展标记语言（XML）HTML是Web上的通用语言，随着Internet的深入人心，WWW上的Web文件日益复杂化、多样化，人们开始感到了HTML这种固定格式的标记语言的不足。1996年W3C开始对HTML的后续语言进行研究，并于1998年正式推出了XML（Extensible Markup Language，可扩展标记语言）。在设计网页时，XML提供了比HTML更灵活的方法。（1）XML语言的特点XML是国际组织W3C为适应WWW的应用，将SGML （Standard Generalized Markup Language）标准进行简化形成的元标记语言。简单地说，XML是使用标记来描述内容或与内容相关的形式信息的通用语言。一个XML文档由标记和字符数据组成。而作为元标记语言，XML不再使标记固定，允许网页的设计者定义数量不限的标记来描述内容，同时还允许设计者创建自己的使用规则。（2）XML的DTDDTD（Document Type Definition,文档类型定义）是一组应用在XML文档中的自定义标记语言的技术规范。DTD中定义了标记的含义及关于标记的语法规则。语法规则中确定了在XML文档中使用哪些标记符，它们应该按什么次序出现，标记符之间如何 嵌套，哪些标记符有属性等等。DTD可以包含在它所描述的XML文档中，但通常它是一份单独的文档或者一系列文档。作为外部文件可通过URL链接，被不同的XML文档 共享。XML把DTD的定义权开放，不同行业可以根据自己的实际需求定义描述内容的DTD，以适应本行业内部的信息交流和存档需要。因此，适合于不同行业、不同平台的标记语言大批涌现。（3）XML的CSS与XSL强调内容描述与形式描述的分离，一方面可以使XML文件的编写者更集中精力于数据本身，而不受显示方式的细节影响；另一方面允许为相同的数据定义不同的显示方式，从而适合于不同应用、不同媒体，使XML数据得到最大程度的重用。XML文档数据的显示形式是通过样式单定义的。CSS（Cascading Style Sheets）是XML使用的一种标准的级联样式单，XSL（Extensible Style Language）则是可扩展的样式语言。由于XML允许用户创建任何所需的标记，而通用浏览器却既无法预期用户标记的意义，又无法为显示这些标记而提供规则，因此用户必须为自己创建的XML文档编写样式单，样式单可以实现共享。浏览器对一个XML文档的处理过程是，首先去关联它所指定的样式单文件，如果该样式单是一个XSL文件，则按照规定对XML数据进行转换然后再显示，XSL本身也是基于XML语言的，可以将XML转化为HTML后再显示。如果该样式单是一个CSS文件，浏览器就会按照样式单的规定给每个标记赋予一组样式后再显示。2 Web数据库访问技术Web数据库访问技术通常是通过三层结构来实现的，如图1-3所示。目前建立与Web数据库连接访问的技术方法可归纳为CGI技术，ODBC技术和ASP、JSP、PHP 技术。 Web数据库访问的三层结构1 CGI技术CGI（Common Cateway Interface，通用网关界面）是一种Web服务器上运行的基于Web浏览器输入程序的方法，是最早的访问数据库的解决方案。CGI程序可以建立网页与数据库之间的连接，将用户的查询要求转换成数据库的查询命令，然后将查询结果通过网页返回给用户。一个CGI工作的基本原理如图1-4所示。CGI程序需要通过一个接口才能访问数据库。这种接口多种多样，数据库系统对CGI程序提供了各种数据库接口如Perl、C/C++、VB等。为了使用各种数据库系统，CGI程序支持ODBC方式，通过ODBC接口访问数据库。 CGI工作流程2 ODBC技术ODBC（Open Database Connectivity，开放数据库互接）是一种使用SQL的应用程序接口（API）。ODBC最显著的优点就是它生成的程序与数据库系统无关，为程序员方便地编写访问各种DBMS的数据库应用程序提供了一个统一接口，使应用程序和数据库源之间完成数据交换。ODBC的内部结构为4层：应用程序层、驱动程序管理器层、驱动程序层、数据源层。它们之间的关系如图1-5所示。由于ODBC适用于不同的数据库产品，因此许多服务器扩展程序都使用了包含ODBC层的系统结构。 ODBC的内部结构Web服务器通过ODBC数据库驱动程序向数据库系统发出SQL请求，数据库系统接收到的是标准SQL查询语句，并将执行后的查询结果再通过ODBC传回Web服务器，Web服务器将结果以HTML网页传给Web浏览器，工作原理如图1-6所示。 Web服务器通过ODBC访问数据库由于Java语言所显示出来的编程优势赢得了众多数据库厂商的支持。在数据库处理方面，Java提供的JDBC为数据库开发应用提供了标准的应用程序编程接口。与ODBC类似，JDBC也是一种特殊的API，是用于执行SQL语句的Java应用程序接口。它规定了Java如何与数据库之间交换数据的方法。采用Java和JDBC编写的数据库应用程序具有与平台无关的特性。3 ASP、JSP、PHP技术ASP是Microsoft开发的动态网页技术，主要应用于Windows NT+IIS或 Windows 9x+PWS平台。确切地说ASP不是一种语言，而是Web服务器端的开发环境。利用ASP可以产生和运行动态的、交互的、高性能的Web服务应用程序。ASP支持多种脚本语言，除了VBScript和Pscript，也支持Perl语言，并且可以在同一ASP文件中使用多种脚本语言以发挥各种脚本语言的最大优势。但ASP默认只支持VBScript和Pscript，若要使用其他脚本语言，必须安装相应的脚本引擎。ASP支持在服务器端调用ActiveX组件ADO对象实现对数据库的操作。在具体的应用中，若脚本语言中有访问数据库的请求，可通过ODBC与后台数据库相连，并通过ADO执行访问库的操作。关于ASP的编程技术将会在第7章中详细介绍。JSP是Sun公司推出的新一代Web开发技术。作为Java家族的一员，几乎可以运行在所有的操作系统平台和Web服务器上，因此JSP的运行平台更为广泛。目前JSP支持的脚本语言只有Java。JSP使用JDBC实现对数据库的访问。目标数据库必须有一个JDBC的驱动程序，即一个从数据库到Java的接口，该接口提供了标准的方法使Java应用程序能够连接到数据库并执行对数据库的操作。JDBC不需要在服务器上创建数据源，通过JDBC、JSP就可以实现SQL语句的执行。PHP是Rasmus Lerdorf推出的一种跨平台的嵌入式脚本语言，可以在Windows、UNIX、Linux等流行的操作系统和IIS、Apache、Netscape等Web服务器上运行，用户更换平台时，无需变换PHP代码。PHP是通过Internet合作开发的开放源代码软件，它借用了C、Java、Perl语言的语法并结合PHP自身的特性，能够快速写出动态生成页面。PHP可以通过ODBC访问各种数据库，但主要通过函数直接访问数据库。PHP支持目前绝大多数的数据库，提供许多与各类数据库直接互连的函数，包括Sybase、Oracle、SQL Server等，其中与SQL Server数据库互连是最佳组合。3 网络数据库应用系统的层次体系当前，Internet/Intranet技术发展异常迅速，越来越多的数据库应用软件运行在Internet/Intranet环境下。在此之前，数据库应用系统的发展经历了单机结构、集中式结构、客户机/服务器（C/S）结构之后，随着Internet的普及，又出现了浏览器/服务器（B/S）结构与多层结构。在构造一个应用系统时，首先考虑的是系统的体系结构，采用哪种结构取决于系统的网络环境、应用需求等因素。1 客户机/服务器结构1．二层C/S结构二层C/S结构是当前非常流行的数据库系统结构，在这种结构中，客户机提出请求，服务器对客户机的服务请求做出回答。它把界面和数据处理操作分开在前端（客户端）和后端（服务器端），这个主要特点使得C/S系统的工作速度主要取决于进行大量数据操作的服务器，而不是前端的硬件设备；同时也大大降低了对网络传输速度的要求，因为只须客户端把服务请求发送给数据库服务器，数据库服务器只把服务结果传回前端，如图1-7所示。在设计时，对数据可能有如下不同的处理形式。（1）在处理时，客户机先向服务器索取数据，然后释放数据库，即客户机发出的是文件请求，在客户机端处理数据，最后将结果送回服务器。这种处理方式的缺点很明显：所有的应用处理都在客户端完成，这就要求客户端的计算机必须有足够的能力，以便执行需要的任何程序。更为糟糕的是，由于所有的处理均在客户端完成，每次运行时都要将文件整体传送到客户端，然后才能执行。如：Student表中有30 000条记录，客户端发出命令：Select * From Student Where Sno='200101'这条命令将要求服务器将Student表中的所有记录传送到客户端，然后在客户端执行查询，结果只用到一条记录；如果查询的记录不存在，网络传输的数据实际上是无 用的。如此大的数据传输量是不可想象的。因此，人们提出了在服务器中能够执行部分代码的客户机/服务器结构。（2）在处理时，客户机接受用户要求，并发给服务器；在服务器端处理用户要求，最后将结果传回客户机显示或打印。这种处理方式网络通信量较小。客户机向服务器发出的是处理请求，而不是文件请求，处理请求中的代码在服务器端执行后向客户机传送处理后的结果。这样，为了特定任务，客户机上的程序和服务器上的程序协同工作：客户机端的代码用于完成用户的输入输出及数据的检查，而服务器端的代码完成对数据库的操作。客户机/服务器结构的另一个主要特点在于软件、硬件平台的无关性。数据库服务器上的数据库管理系统集中负责管理数据，它向客户端提供一个开放的使用环境，客户端通过数据库接口，如ODBC（开放数据库连接）和SQL语言访问数据库，也就是说，不管客户端采用什么样的硬件和软件，它只要能够通过网络和数据库接口程序连接到服务器，就可对数据库进行访问。在客户机/服务器结构中，常把客户机称为前台，而把服务器端称为后台。前台应用程序的功能包括用户界面、接收用户数据、处理应用逻辑、向后台发出请求、同时接收后台返回的结果，最后再将返回的结果按一定的格式或方式显示给用户。而后台服务器则负责共享外部设备、存取共享数据、响应前台客户端的请求并回送结果等工作。前台的应用程序和数据一般是用户专用的，而后台的数据和代码是所有用户可以共享的。由于数据库服务器不仅要管理共享数据，保证数据的完整性，还要执行一部分代码，完成客户端的一些处理请求，所以对用于服务器的计算机提出较高的要求。最好要采用一台专用的服务器，有较快的处理速度，有大容量的硬盘和内存，支持磁带等大容量的存储设备。上面讲的客户机/服务器结构将应用分在了客户机、服务器两级，称其为两层客户机/ 服务器结构。总之，两层C/S结构的基本工作方式是客户程序向数据库服务器发送SQL请求，服务器返回数据或结果。这种C/S结构有两种实现方式，一种是客户来完成表示部分和应用逻辑部分，而服务器完成数据访问部分，这种情况是以客户为中心的，适用于应用相对简单、数据访问量不是很大的情况。另一种是以服务器为中心的，把一些重要的应用逻辑部分放到服务器上，这样可充分利用服务器的计算能力，减少网络上需要传送的数据。通常以存储过程和触发器的形式出现，但存储过程都依赖于特定数据库，不同数据库之间很难移植，而三层C/S结构可以很好地解决这个问题。注意：触发器（trigger）是数据库系统中，一个在插入、删除、修改操作之后运行的记录级事件代码。不同的事件可以对应不同的动作。通常有3种类型的触发器：INSERT触发器、DELETE触发器和UPDATE触发器。2．三层C/S结构由于两层结构的客户机/服务器系统本身固有的缺陷，使得它不能应用于一些大型、结构较为复杂的系统中，故出现了3层结构的客户机/服务器系统，将两层结构中服务器部分和客户端部分的应用单独划分出来，即采用“客户机—应用服务器—数据库服务器”结构（如图1-8所示）。典型的数据库应用可分为三部分：表示部分、应用逻辑（商业逻辑）部分和数据访问部分，三层结构便是对应于这三部分。 图1-8 三层C/S结构其中，应用服务器和数据库服务器可位于同一主机，也可位于不同主机。客户机是应用的用户接口部分，负责用户与应用程序的交互，运行在客户机端的软件也称为表示层软件。应用服务器存放业务逻辑层（也称为功能层）软件，是应用逻辑处理的核心，实现具体业务。它能响应客户机请求，完成业务处理或复杂计算。若有数据库访问任务时，应用服务器层可根据客户机的要求向数据库服务器发送SQL指令。应用逻辑变得复杂或增加新的应用时，可增加新的应用服务器。数据库服务器便是用来执行功能层送来的SQL指令，完成数据的存储、访问和完整性约束等。操作完成后再通过应用服务器向客户机返回操作结果。2 浏览器/服务器结构随着Internet技术和Web技术的广泛应用，C/S结构已无法满足人们的需要。因为在典型C/S体系中，通常为客户安装前端应用程序的做法已不再现实，并且限制客户端工作环境只能基于Windows、Macintosh或UNIX等操作系统也不切实际。于是基于浏览器/服务器结构（Browser/Server）的系统应运而生。采用B/S结构后，在客户端只需安装一个通用的浏览器即可，不再受具体操作系统和硬件的制约，实现了跨平台的应用。基于B/S结构的典型应用通常采用三层结构：“浏览器—Web服务器—数据库服务器”，B/S模式的工作原理是：通过浏览器以超文本的形式向Web服务器提出访问数据库的请求，Web服务器接受客户请求后，激活对应的CGI程序将超文本HTML语言转化为SQL语法，将这个请求交给数据库，数据库服务器得到请求后，进行数据处理，然后将处理结果集返回给CGI程序。CGI再将结果转化为HTML，并由Web服务器转发给请求方的浏览器，如图1-9所示。 图1-9 B/S工作原理在B/S模式中，客户端的标准配置是浏览器，如IE；业务功能处理由独立的应用服务器处理，Web服务器成为应用处理的标准配置；数据处理仍然由数据库服务器处理。从本质上讲，B/S结构与传统的C/S结构都是以同一种请求和应答方式来执行应用的，区别主要在于：C/S是一种两层或三层结构模式，其客户端集中了大量应用软件，而B/S是一种基于超链接（HyperLink）、HTML、Java的三级或多级C/S结构，客户端仅需单一的浏览器软件，是一种全新的体系结构，解决了跨平台问题。到目前，这两种结构在不同方面都有着广泛的应用。虽然C/S结构在Internet环境下明显不如B/S结构具有优势，但它在局域网环境下仍具有优势。3 Internet/Intranet信息系统的多层体系结构多层结构应用软件与传统的两层结构应用软件相比，有可伸缩性好、可管理性强、安全性高、软件重用性好等诸多优点，如何在Internet/Intranet环境下构建应用软件体系结构就成为一个非常重要的问题，也是现今软件体系研究的一个新热点。目前各种技术层出不穷，如最初的静态HTML页面、简单的CGI网关程序、Java Applet程序，现在的ASP等Web数据库技术，还有动态的Java在线游戏及PHP技术等。实际上，多层的概念是由Sun公司提出来的。Sun公司提出的多层应用体系包括4层：客户层、顶端Web服务层、应用服务层和数据库层。其中顶端Web服务层是Sun公司多层体系结构中非常重要的一层，它主要起代理和缓存的作用。顶端Web服务器的作用是缓存本地各客户机经常使用的Java Applet程序和静态数据，通常被放置在客户机所在的局域网内，起到一个Java Applet主机（向Web浏览器传送Java Applet程序的计算机）和访问其他服务的代理作用。与普通代理服务器的作用相同。构建多层结构应用软件时，选用Java平台是一个很好的选择，因为它跨越各应用平台。总之，在Java平台上构建多层应用软件体系代表着今后Internet/Intranet应用的趋势。