【毕业学位论文】(Word原稿)开发ID3 navigation metadata算法-软件工程

第 - 1 - 页 共 26 页 开发 法 摘要： 我们知道无论是 上的播放器还是 放器，在播放影音文件时都必须首先“告诉“播放器我们要播放的文件存储在什莫地方，然后播放器再根据我们所提供的“地点“去读取文件并进行播放。令我们失望的是这些播放器听不懂我们的话，那末我们是通过什莫方式来让她知道她取文件的地点呢？答案就是文件路径。播放器可以通过我们所提供的文件路径来找到要播放的文件。为了满足用户的不同需求，我们可能要将这些文件按 辑名）、 唱者）、派 ）进行分类。例如 :歌曲一生有你当按专辑分时它属于专辑“一生有你“，按演唱者分它又属于“水木年华“组合。而事实上我们的 行分类的文件，也就是说我们从“水木年华“组合所唱的歌曲中可以找到歌曲一生有你、同样也可以在“一生有你“专辑中看到歌曲一生有你。现在的 通过在以 属性 名 命 名的文件中存储 属性 分类 文件 的。这样的话，同一个 件的路径将在不同 属性 文件中重复存储，而往往在我们的 且这些文件都会被集中存储起来，也就是这些集中存储的文件的路径会有很多地方是相同的，例如： C:件中存在很多 件，那末这些 件的路径中都会包含 C:样将导致文件路径中相同的部分更会被反复存储。如果能将这些相同的部分仅仅只存储一次并被大家“共用“，这样就能节省相当可观的存储空间。而这些存储空间对于容量有限的 说就显得尤为重要。 此文将 介绍 一种 采用 算法来 实现这样的设想 。在电子领域，时间和空间永远都是一对不相容的冤家。这里我们也将采取一定措施来平衡两者。 关键字： 放器 、 法 第 - 2 - 页 共 26 页 D3 we no C we to or we it go to to It is is of So do we it to is by s we to so it is of it is as as to In at In we on by on So of is on MP of In of on a :a of of C: to of If we on it by a of 第 - 3 - 页 共 26 页 目录 前言 第一章背景介绍 1 1、 1 1 1、 念 1 1 2、 件组成 1 2、 简 介现 行 1 2 1、 1 2 2、 现行算法 分析 第二章基本知识 2 1、 键 树 简介 2 2、伪代码 简介 2 3、 C+语言简介 第三章算法开发过程 3 1、 算法简介 3 2、 分析数据 3 3、 算法 实现 伪 代码 实现 3 C+实现 第四章小结 文献参考 致谢 第 - 4 - 页 共 26 页 前言 随着世界数码化进程的加快我们身边精致的数码玩具也在不断更新，从像素不断提升的数码相机到功能不断出新的手机，无不体现了现代科技的精致与完美。其中， 于网上 今以是最流行，普及率也最高的数码产品了。在 上的服务感到了不满，而对视觉、听觉上的全面享受的渴求直接导致了今天 放器 的诞生。 自去年法国爱可视公司推出收款产品以来， 升級 产 品， 現了 “随 身 听 ”到 “随 身看 ”的升級， 将终结 代 。但是数码 市場上 显示 ， 而 颇 得冷清。主因是 市場仍在 “培育期 ”，目前最主要的問題是 价格 仍然很貴，普及起來是有一定 难度 。而且目前 为 影资源下载的网站数量虽然 也已 经 和 但是网站 內容建 设混乱 、影片品 质良莠不齐 、 收费机制 不健全 等直接 影响 到 据业 內人士分析， 随着 微型硬 盘价格 的下跌， 成本 问题将 很快得到解決， 价格瓶颈有望被打破 ，加上 宽带网络 的 进一步普及 、 规范 ， 快大 规模启动 的。 消费者引领企盼的商品 ， 还是未成熟的昙花一现 ？虽然目前 场 中， 算是刚刚起步 的 阶段 ，但是也已 经隐约呈现 百家 争鸣 的情 况 。 至于 在 产 品未 来 的 设计及发展 上，提升液晶 显示屏的 品質、改善使用者介面、延 长电池寿命 等等的方向，目的都是 为 了要 让 消 费 者能夠接受這 种 新 兴的 产 品。事 实 上，如果因 为档案经适当 压缩后 ，消 费 者即可 随时随地享受媲美 的影片，這是一個多 麽 令人 雀跃 的生活改 变 ，我們對 个 商品的未 来保持乐观与期待。 如今 微星 公司也推出了自己 的 并 在大陆各大 但要在风云巨变的数码市场站稳脚跟，就需要不断对产品进行技术改进使其在同类产品中突显一定的优势。 此文即为对 与 第 - 5 - 页 共 26 页 第一章背景介 绍 1 1、 介 观察目前消费性电子（ 展， 身听凭借技术成熟、平民价格（现在 256要 500 元不到）等优势，因此在 场逐渐扩展版图，并且不论是 播、重复播放、词曲同步及录音等多元化方针，或者是 幕、蓝牙（ 设计的集成，都让 身听更加如虎添翼。然而，随着出货量的与日遽增， 利下降等问题，而且只能用于听音乐， 还未将影像部分纳入其中，使得 上型多媒体播放器）概念应运而生。 念 是 放器。 顾名思义， 放器是一个能够播放 件的设备，它可以叫做 人视频播放器）也可以叫做 携式媒体播放器）。现在对 放器的功能没有具体界定，虽然不少厂商都将它定义为多媒体影音播放器，但它除了听看电影的基本功能外还支持音乐播放、浏 览图片，甚至部分产品还可以上网。但为了强调便携的特征，我们在这里所讨论的 将以便携、播放视频为准则，它们可以通过 1394 端口传输文件，很方便地将视频文件下载到设备中进行播放，而且应当自带 幕，以满足随时播放视频的需要。 优点很多，它能够直接播放高品质视频、音频，也可以浏览图片以及作为移动硬盘、数字银行使用；更有产品还具备一些十分新颖、实用的功能，例如爱可视 够录制视频，它可以将来自 视等设备的信号以式保存在硬盘中；中基超威力即将推出的 放器支 持 理以及无线网络功能，可以在无线环境普及后发挥出更多作用。而且现在我们所见的到 多数都带有视频转制等专业的视频功能，并具备非常齐全的视频输入 /输出端口，因此它们携带的视频文件能够在很多场合中播放，尽管这对一些仅在旅行途中使用播放器的用户没有更多的实际意义，但对于一些经常做视频演示的用户则十分有用，因为 放器能够方便地接驳投影机以及电视等输出设备。 件组成 本都具有处理器、液晶显示屏，存储设备三大基本原件。这三件也直接影响了我们对 使用，下面就一一介绍： 处理器 ： 同于 要强大处理器作为 中央处理芯片，不仅要内建视频编 /译码芯片，做为模拟与数字两种信号间转换之用。另外，用来接视频译码器与 总线，以及 示器的驱动电路等等，最主要的是对 解码和播放。市场上主流的 般都是采用德州仪器和英特尔的数字处理芯片，德州仪器在移动娱乐数字芯片上独占鳌头；英特尔则是计算机处理器的领袖，其能力有目共睹 。 第 - 6 - 页 共 26 页 液晶显示屏 ： 液晶显示器主要考虑三个重点因素，分别是色彩表现力和液晶屏尺寸及分辨率。 存储设备 ： 日前， 样，可用微硬盘 (如 闪存卡 (如储影音文件，由于 频文件比 频文件体积要大得多，虽然闪存卡在防震上有优势，但容量有限，即使插上扩展卡也只有 1G，只能放两部 片，这样也使二次投入大大增加，微硬盘式容量动辄几十 G，可存储几十甚至上百部电影，拉开了和 距离；且防震方面也基本达到我们要求，不过一般发热、耗电较大。 1 2、简介现行 运作过程 式 1. 表示紧接在它之后的 有多少个 表示媒体的某一项属性。 示与 应的 该文件中的起始地址。最后一个 个 来隔开。 示对应媒体文件在 的序号。每一组 束后根 2个 。 2. . 0| 0 00 | 0 | 0 | 00 第 - 7 - 页 共 26 页 音频媒体数据项在该文件中的起始地址（如果没有音频数据则该项为 0）。 视频媒体数据项在该文件中的起始地址（如果没有视频数据则该项为 0）。 图片媒体数据项在该文件中的起始地址（如果没有图片数据则该项为 0）。 4 为对应数据项在 的地址。 3. 的意义相同。 0 . ( 0 . . . ( 0 0 . . . . . . . . 第 - 8 - 页 共 26 页 示紧接其后的 长度 (有多少个 2个数据项之间用 0 分开。 没有 ，其对应 替。 1 2 2、 现行算法分析 如上 现行算法中我们是 借助以下九个文件： 通过三级映射才得到我们所要得文件地址即 这个 件 在 这个其实类似于 不过 是按 盘 进行 分区的， 为了便于讲述 ,下面就以 相信大家对上面的 面已经很熟悉了吧！ 通常情况下 我们都习惯于把 文件集中存放在固定的一个或几个文件夹里 ， 这样就会出现如上图示的文件路径中有很多重复的情形。 比如现在在 C:个文件夹中存储了 100 个文件，那末这 100 个 文件的路径中都会出现 占用 12 个字节的字符串 C:共占用 1200 个字节的空间 。 试想一下，假如我们的文件再多一些，那末这些“公共路径“所占用的内存又会是 多少？ 如果通过一种方法将这些 “公共路径“只存储一次 。 这对于资源宝贵的 会是一笔很可观的财富。 在第三章中 将介绍一种通过 键树 来实现这一功能的算法。 第 - 9 - 页 共 26 页 第二章基本知识 2 1、 键树 简介 键树又称数字查找树（ 它是一棵度大于或等于 2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。例如，若关键字是数值，则结点中只包含一个数位；若关键字是单词，则结点中只包含一个字母字符。这种树会给某种类型关键字的表的查找带来方便。 例如：有如下 9 个关键 字的集合 可对此集合作如下的逐层分割。 首先按首字符不同将他们分为三个子集： , 然后对其中关键字个数大于 1 的子集再按第二个字符不同进行再分割 的 集 合 可 进 行 如 下 分 割 ： (, (、 ( 显然，如此集 合、子集和元素之间的层次关系可以用一棵树来表示，这棵树便是键树。例如上述集合及其分割可用下图来描述： $A$树中根结点的三棵子树表示首字符为 C、 Y 和 Z 的三个关键字子集。从根到叶子结点的字符组成的字符串表示一个关键字，叶子结点中的特殊符号 $表示字符串的结束。在叶子结点还含有指向该关键字的指针。 为了查找和插入方便，我们约定键树是有序的，即同一层中兄弟结点之间依 第 - 10 - 页 共 26 页 所含符号 自左至右有序。 通常，键树可有两种存储结构。 (1)以树的孩子兄弟链表来表示键树。树的每个结 点包含三个域： ：存储关键字的一个字符； ：存储指向第一棵子树根的指针； ：存储指向右兄弟的指针。（本课题将采用这种存储方式。） (2)以树的多重链表表示键树，即树的每个结点中应含有 代码 伪代码 (一种算法描述语言。使用为代码的目的是为了使被描述的算法可以容易地以任何一种编程语言 (C, 现。因此，伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言。 下面介绍一种类 伪代码的语法规则 1、 在伪代码中，每一条指令占一行 (外， )，指令后不跟任何符号（ 中语句要以分号结尾）； 2、 书写上的 “ 缩进 ” 表示程序中的分支程序结构。这种缩进风格也适用于缩进取代传统 的 一模块的语 句有相同的缩进量，次一级模块的语句相对与其父级模块的语句缩进； 例如： 而在 嵌套来表示， 在 和 的嵌套来表示， 第 - 11 - 页 共 26 页 3、 在伪代码中，通常用连续的数字或字母来标示同一即 模块中的连续语句，有时也可省略标号。 例如： 1. 2. a. b. 1. 2. c. 3. 4、 符号 后的内容表示注释； 5、 在伪代码中，变量名和保留字 不区分大小写 ，这一点和 同，与+不同； 6、 在伪代码中，变量不需声明，但变量局部于特定过程，不能不加显示的说明 就使用全局变量； 7、 赋值语句用符号 表示， x示将 x，其中 表达式的结果与 多重赋值 ije 是将表达式 e 的值赋给变量 i 和 j，这种表示与 je和 ie 等价。 8、 例如： xy x20*(y+1) xy30 以上语句用 x := y; x := 20*(y+1); x := 30; y := 30; 以上语句用 x = y; x = 20*(y+1); x = y = 30; 第 - 12 - 页 共 26 页 9、 选择语句用 表示，并且这种 以嵌套，与 例如 : 10、 循环语句有三种： ，其语法均与是 用缩进代替 例如： 1. x 0 2. y 0 3. z 0 4. x = 0 ); z = x * y; y /= 2; 11、 数组元素的存取有数组名后跟 “ 下标 ” 表示。例如 Aj指示数组 号 “ ” 用来指示数组中值的范围。 例如： A1j 表示含元素 A1, A2, , Aj 的子数组； 12、 复合数据用对象 (表示，对象由属性 (域 (成。域的存取是由域名后接由方括号括住的对象名表示。 例如： 数组可被看作是一个对象，其属性有 示其中元素的个数，则就表示数组 A 中的元素的个数。在表示数组元素和对象属性时都要用方括号， 一般来说从上下文可以看出其含义。 用于表示一个数组或对象的变量被看作是指向表示数组或对象的数据的一个指针。对于某个对象 f，赋值 yx 就使 fy=fx，更进一步，若有 fx3 ，则不仅有 fx=3，同时有 fy=3，换言之，在赋值 yx 后， x 和 有时，一个指针不指向任何对象，这时我们赋给他 13、 函数和过程语法与 函数值利用 “ 函数返回值 )” 语句来返回，调用方法与 似；过程用 “程名 ” 语句来调用； 例如： 1. x t + 10 2. y x) 3. x,y) 参数用按值传递方式传给一个过程：被调用过程接受参数的一份副本，若他对某个参数赋值，则这种变化对发出调用的过程是不可见的。当传递一个对象时，只是拷贝指向该对象的指针，而不拷贝其各个域。 2 3、 C+语言简介 第 - 14 - 页 共 26 页 C+语言是一种应用较广的面向对象的程序设计语言，使用它可以实现面向对象的程序设计。面向对象的设计与面向过程的设计是有很大区别的，面向对象的程序设计是在面向过程的程序设计的基础上一个质的 飞跃。要学会面向对象的程序设计，首先要学会一种面向对象的语言，即要学会用 要先有 C+的基础，而学习 C+语言首先要认识它面向对象的特性和实现面向对象的方法。 C+是一种面向对象的程序设计语言 当你首次学习 C+时，总会碰到一些在 C 语言从未见过的概念，如：类、对象、抽象、封装、继承、多态性、虚函数等等。这些概念是 C+所具有，下面简单的介绍一下 C+对面向对象程序设计方法的支持和实现。 1、 C+支持数据封装 支持数据封装就是支持数据抽象。在 C+中，类是支持数据封装的工具，对象则是数据封装的实现 。面向过程的程序设计方法与面向对象的程序设计方法在对待数据和函数关系上是不同的，在面向对象的程序设计中，将数据和对该数据进行合法操作的函数封装在一起作为一个类的定义，数据将被隐藏在封装体中，该封装体通过操作接口与外界交换信息。对象被说明具有一个给定类的变量，类类似于 这种结构中包含数据，而不包含函数。 C+中的类是数据和函数的封装体。在 C+中，结构可作为一种特殊的类，它虽然可以包含函数，但是它没有私有或保护的成员。 2、 C+类中包含私有、公有和保护成员 C+类中 可定义三种不同访控制权限的成员。一种是私有 (员，只有在类中说明的函数才能访问该类的私有成员，而在该类外的函数不可以访问私有成员；另一种是公有 (员，类外面也可访问公有成员，成为该类的接口；还有一种是保护 (员，这种成员只有该类的派生类可以访问，其余的在这个类外不能访问。 3、 C+中通过发关消息来处理对象 C+中是通过向对象发关消息来处理对象的，每个对象根据所接收到的消息的性质来决定需要采取的行动，以响应这个消息。响应这些消息是一系列的方法，方法是在类定 义中使用函数来定义的，使用一种类似于函数调用的机制把消息发送到一个对象上。 4、 C+中允许友元破坏封装性 类中的私有成员一般是不允许该类外面的任何函数访问的，但是友元便可打破这条禁令，它可以访问该类的私有成员 (包含数据成员和成员函数 )。友元可以是在类外定义的函数，也可以是在类外定义的整个类，前者称友元函数，后者称为友元类。友元打破了类的封装性，它是 C+另一个面向对象的重要牲。 5、 C+允许函数名和运算符重载 C+支持多态性， C+允许一个相同的标识符或运算符代表多个不同实现的函数，这就称标识符或运算 符的重载，用户可以根据需要定义标识符重载或运算符重载。 6、 C+支持继承性 C+中可以允许单继承和多继承。一个类可以根据需要生成派生类。派生类继承了基类的所有方法，另外派生类自身还可以定义所需要的不包含在父类中的新方法。一个子类的每个对象包含有从父类那里继承来的数据成员以及自己所特有的数据成员。 第 - 15 - 页 共 26 页 7、 C+支持动态联编 C+中可以定义虚函数，通过定义虚函数来支持动态联编。 以上是所讲的是 C+对面向对象程序设计中的一些主要特征的支持。 C+的词法及词法规则 1、 C+的字符集 字符是一些可以区分的最小符号。 C+的字符集由大小写英文字母 (数据字符 (0特殊字符 (空格，！， #， %， ， &， *， _， ， ?， ， ,)组成。 2、 单词及词法规则 单词又称词法记号，它是由若干个字符组成的具有一定意义的最小词法单元。 C+共有 6 种单词，分别是：标识符、关键字、运算符、分隔符、常量、注释符，在编码时要特别注意这些单词的词法规则。要注意的是 C+中的空白符： C+中经常使用空白符，实际上，空白符不是一个字符，它是空格符、换行符和水平制表符的统称。注意，空白符不等于空格 符，只是空白符包含空格符。还有一个空字符，要把它与空白符分开。空字符是指 的那个字符。空字符在 C+中有特殊用途，用它来作为字符串的结束符。存放在内存中的字符串常量都在最后有一个结束符，即用空字符，它用转义序列方法表示为 0 。 C+程序结构的组成 C+程序结构的基本组成部分 1、 预处理命令 ， C+提供了三类预处理命令：宏定义命令、文件包含命令、条件编译命令。 2、 输入输出 ， C+程序中总是少不了输入和输出的语句，实现与程序内部的信息交流。特别是屏幕输出的功能，几乎每个程序都要用到，使 用它把计算机的结果显示在屏幕上。 3、 函数 ， C+的程序是由若干个文件组成的，每个文件又是由若干个函数组成，因此，可以认为 C+的程序就是函数串，即由若干个函数组成，函数与函数之间是相对的，并且是并行的，函数之间可以调用。在组成一个程序的若干个函中，必须有一个 。 4、 语句 ，语句是组成程序的基本单元。函数是由若干条语句组成的。但是，空函数是没有语句的。语句是由单词组成，单词间用空格符分隔， C+程序中的语句又是以以分号结束。语句除了有表达式语句和空语句之外，还有复合语句、分支语句、循环语句和转向语 句等若干类。 5、 变量 ，多数程序都需要说明和使用变量。广义讲，对象包含了变量，即将变量也称为一种对象，狭义讲，将对象看作是类的实例，对象是指某个类的对象。 6、 其他 ，除了以上讲述的 5 个部分以外，还有其他组成部分。例如，符号常量和注释信息也是程序的一部分。 C+中都尽量把常量定义为符号常量，在 C+的程序中出现的是符号常量，该符号常量代表着某个确定的常量值。 C+程序的书写格式 在编程时应该注意 C+的书写格式，基本原则是：一行一般写一条语句。短语句可以一行写多个。长语句可以一条写多行。分行原则是不能将一个 单词分开。用双引号引用的一个字符串也最好不分开，如果一定要分开，有的编译系统要求在行尾加续行符 (“ ” ) 第 - 16 - 页 共 26 页 C+程序的实现 C+源程序的实现与其他高级语言源程序实现的原理是一样的。一般都要经过编辑、编译、运行。其中最要的是编译过程， C+是以编译方式实现的高级语言。 C+程序的实现，必须要使用某种 C+语言的编译器对程序进行编译。