数据结构_文件及查找

注意事项：在磁盘上创建一个目录，专门用于存储数据结构实验的程序。

因为机房机器有还原卡，请同学们将文件夹建立在最后一个盘中，以学号为文件夹名。

实验八查找和排序一、实验目的掌握运用数据结构两种基本运算查找和排序,并能通过其能解决应用问题。

二、实验要求1．掌握本实验的算法。

2．上机将本算法实现。

三、实验内容为宿舍管理人员编写一个宿舍管理查询软件, 程序采用交互工作方式,其流程如下:建立数据文件，数据结构采用线性表，存储方式任选（建议用顺序存储结构），数据元素是结构类型（学号，姓名，性别，房号），元素的值可从键盘上输入，可以在程序中直接初始化。

数据文件按关键字（学号、姓名、房号）进行排序（排序方法任选一种），打印排序结果。

（注意字符串的比较应该用strcmp(str1,str2)函数）查询菜单: (查找方法任选一种)1. 按学号查询2. 按姓名查询3. 按房号查询打印任一查询结果（可以连续操作）。

参考：typedef struct {char sno[10];char sname[2];int sex; //以0表示女，1表示男int roomno;}ElemType;struct SqList{ElemType *elem;int length;};void init(SqList &L){L.elem=(ElemType *)malloc(MAXSIZE*sizeof(ElemType));L.length=0;}void printlist(SqList L){ int i;cout<<" sno name sex roomno\n";for(i=0;i<L.length;i++)cout<<setw(7)<<L.elem[i].sno<<setw(10)<<L.elem[i].sname<<setw(3)<<L.elem[i].sex<<setw(6) <<L.elem[i].roomno<<endl;}。

实现一个简单的文件系统一个简单的文件系统是指一个用于管理文件和文件夹的系统，可以进行基本的文件和文件夹的创建、删除、重命名、查找、打开、关闭等操作。

以下是一个简单文件系统的实现，主要包括文件和文件夹的数据结构和相关操作。

1.数据结构：- 文件(File)：包含文件名、文件内容、创建时间、修改时间等属性。

- 文件夹(Folder)：包含文件夹名、文件夹路径、创建时间、修改时间等属性，以及包括的文件和文件夹列表。

2.操作：-创建文件夹：可以根据输入的文件夹名和路径，在对应的位置创建一个新的文件夹对象，并将其添加到上级文件夹的文件夹列表中。

-创建文件：可以根据输入的文件名和路径，在对应的位置创建一个新的文件对象，并将其添加到对应的文件夹的文件列表中。

-删除文件夹：可以根据输入的文件夹名和路径，将对应的文件夹对象从上级文件夹的文件夹列表中删除，并删除其包含的所有文件和文件夹。

-删除文件：可以根据输入的文件名和路径，将对应的文件对象从所在文件夹的文件列表中删除。

-重命名文件夹：可以根据输入的原文件夹名和路径以及新文件夹名，将对应的文件夹对象重命名。

-重命名文件：可以根据输入的原文件名和路径以及新文件名，将对应的文件对象重命名。

-查找文件夹/文件：可以根据输入的文件夹名和路径，查找对应的文件夹对象。

-打开文件：可以根据输入的文件名和路径，打开对应的文件对象，并显示其内容。

-关闭文件：可以关闭当前打开的文件。

3.实现：- 定义一个文件夹类(Folder)，包含文件夹名、文件夹路径、创建时间、修改时间等属性，以及一个存储文件夹对象的列表。

- 定义一个文件类(File)，包含文件名、文件内容、创建时间、修改时间等属性。

- 实现创建文件夹的方法(createFolder)，在对应的位置创建一个新的文件夹对象，并将其添加到上级文件夹的文件夹列表中。

- 实现创建文件的方法(createFile)，在对应的位置创建一个新的文件对象，并将其添加到对应的文件夹的文件列表中。

数据结构线性表一、引言数据结构是计算机存储、组织数据的方式，它决定了数据访问的效率和灵活性。

在数据结构中，线性表是一种最基本、最常用的数据结构。

线性表是由零个或多个数据元素组成的有限序列，其中数据元素之间的关系是一对一的关系。

本文将对线性表的概念、分类、基本操作及其应用进行详细阐述。

二、线性表的概念1.数据元素之间具有一对一的关系，即除了第一个和一个数据元素外，其他数据元素都是首尾相连的。

2.线性表具有唯一的第一个元素和一个元素，分别称为表头和表尾。

3.线性表的长度是指表中数据元素的个数，长度为零的线性表称为空表。

三、线性表的分类根据线性表的存储方式，可以将线性表分为顺序存储结构和链式存储结构两大类。

1.顺序存储结构：顺序存储结构是将线性表中的数据元素按照逻辑顺序依次存放在一组地质连续的存储单元中。

顺序存储结构具有随机访问的特点，可以通过下标快速访问表中的任意一个元素。

顺序存储结构的线性表又可以分为静态顺序表和动态顺序表两种。

2.链式存储结构：链式存储结构是通过指针将线性表中的数据元素连接起来，形成一个链表。

链表中的每个节点包含一个数据元素和一个或多个指针，指向下一个或前一个节点。

链式存储结构具有动态性，可以根据需要动态地分配和释放节点空间。

链式存储结构的线性表又可以分为单向链表、双向链表和循环链表等。

四、线性表的基本操作线性表作为一种数据结构，具有一系列基本操作，包括：1.初始化：创建一个空的线性表。

2.插入：在线性表的指定位置插入一个数据元素。

3.删除：删除线性表中指定位置的数据元素。

4.查找：在线性表中查找具有给定关键字的数据元素。

5.更新：更新线性表中指定位置的数据元素。

6.销毁：释放线性表所占用的空间。

7.遍历：遍历线性表中的所有数据元素，进行相应的操作。

8.排序：对线性表中的数据元素进行排序。

9.合并：将两个线性表合并为一个线性表。

五、线性表的应用1.程序语言中的数组：数组是一种典型的顺序存储结构的线性表，常用于存储具有相同类型的数据元素。

数据结构（C语言版）9-12章练习答案清华大学出版社9-12章数据结构作业答案第九章查找选择题1、对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A )A．（n+1）/2 B. n/2 C. n D. [（1+n）*n ]/2 2. 下面关于二分查找的叙述正确的是 ( D )A. 表必须有序，表可以顺序方式存储，也可以链表方式存储B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储3. 二叉查找树的查找效率与二叉树的( （1）C)有关, 在 (（2)C ）时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

4. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）A)个链表。

这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）C) （1） A．17 B. 13 C. 16 D. 任意（2） A．0至17 B. 1至17 C. 0至16 D. 1至16判断题1．Hash表的平均查找长度与处理冲突的方法无关。

(错) 2. 若散列表的负载因子α<1，则可避免碰撞的产生。

（错）3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。

（错）填空题1. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为 4 .算法应用题1. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10解决冲突。

要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

文件系统数据结构文件系统是计算机操作系统中用于管理计算机文件的一种机制，它使用特定的数据结构来组织和存储文件及其相关信息。

文件系统的设计和实现涉及到多种数据结构，包括目录结构、索引结构和文件分配表等。

在本文中，我们将详细介绍文件系统中常用的数据结构及其功能。

一、目录结构目录结构是文件系统中组织文件和文件夹的一种方式。

它使用树状结构来表示文件和文件夹之间的层次关系，使得用户可以方便地浏览和管理文件。

在目录结构中，每个文件夹表示为一个目录项，该目录项包含了文件夹的名称、创建时间、访问权限等信息。

而文件夹中的文件则以文件项的形式存在，文件项包含了文件的名称、大小、创建时间等属性。

目录结构的实现可以使用树结构或者图结构。

其中，树结构是最常见的一种实现方式。

在树结构中，每个目录项都可以作为树的一个节点，根节点代表根目录，每个子节点代表一个子目录或者文件。

通过遍历树的节点，用户可以逐层查找和访问文件。

二、索引结构索引结构是一种基于关键字的数据结构，用于快速定位文件的相关信息。

在文件系统中，文件的内容通常分散存储在磁盘上的不同位置，为了提高文件的访问速度，可以使用索引结构建立文件与存储位置的映射关系。

常见的索引结构包括位图索引、哈希索引和B树索引等。

位图索引用一个位图来表示文件的存储位置，每个位对应一个存储块，通过位图可以迅速定位到文件所在的位置。

哈希索引使用哈希函数将文件的关键字映射到存储位置，从而实现快速定位。

而B树索引是一种多路搜索树，用于支持范围查询和高效的插入和删除操作。

索引结构的选择依赖于文件系统的需求和性能要求。

不同的索引结构具有不同的特点和适用范围，需要根据具体情况进行选择和优化。

三、文件分配表文件分配表是文件系统中用于管理文件存储空间的一种数据结构。

它记录了文件在磁盘上分配的存储块，以及存储块之间的关系。

文件的存储块可以是连续的，也可以是离散的。

文件分配表采用表格的形式来表示文件在磁盘上的分布情况。

第12章文件12.1 复习笔记一、文件的基本概念1．文件概述（1）定义文件是性质相同的记录的集合。

（2）按关键字划分①单关键字文件若文件中的记录只有一个惟一标识记录的主关键字，则称之为单关键字文件；②多关键字文件若文件中的记录除了含有一个主关键字外，还含有若干个次关键字，则称之为多关键字文件。

（3）按是否定长划分①定长文件若文件中各记录含有的信息长度相同，则称这类记录为定长记录，由这种定长记录组成的文件称作定长文件；②不定长文件若文件中各记录含有的信息长度不等，则称作不定长文件。

2．文件的逻辑结构及操作（1）文件的逻辑结构文件中各记录之间存在着逻辑关系，当一个文件的各个记录按照某种次序排列起来时，各记录之间就自然地形成了一种线性关系。

在这种次序下，文件中每个记录最多只有一个直接后继记录和一个直接前驱记录，而文件的第一个记录只有直接后继没有直接前驱，文件的最后一个记录只有直接前驱而没有直接后继。

此时，文件可看成是一种线性结构。

（2）文件操作①检索文件检索就是在文件中查找满足给定条件的记录，它既可以按记录的逻辑号（即记录存入文件时的顺序编号）查找，也可以按关键字查找。

②维护文件维护主要是指对文件进行记录的插入、删除及修改等更新操作。

此外，为提高文件的效率，还要进行再组织操作、文件被破坏后的恢复操作以及文件中数据的安全保护等。

3．文件的存储结构（1）概念文件的存储结构是指文件在外存上的组织方式。

采用不同的组织方式就得到不同的存储结构。

（2）基本的组织方式①顺序组织；②索引组织；③哈希组织；④链组织。

文件组织的各种方式往往是这四种基本方式的结合。

二、顺序文件1．定义顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序跟物理顺序一致的文件。

若顺序文件中的记录按其主关键字有序，则称此顺序文件为顺序有序文件；否则称为顺序无序文件。

2．优点顺序文件的主要优点是连续存取的速度较快，即若文件中第i个记录刚被存取过，而下一个要存取的是第i+1个记录，则这种存取将会很快完成。

文件的索引结构
在计算机科学中，文件索引结构是用于快速检索和访问文件内容的数据结构或技术。

常见的文件索引结构有：线性索引、哈希索引、B树索引以及倒排索引。

1.线性索引：线性索引是最简单的索引结构之一，它将文件中每个记录的关键字按顺序存储在一个索引表中。

通过索引表中的关键字和指向记录的指针，可以快速查找和访问文件中的记录。

2.哈希索引：哈希索引使用哈希函数将文件中的关键字映射到索引表中的桶或槽位，每个槽位存储对应关键字的指针或记录。

哈希索引具有快速的查找速度，但对于范围查询等操作效果较差。

3.B树索引：B树是常用于数据库系统的索引结构，通过将文件内容组织成多层的树结构来进行索引。

B树的每个节点可以包含多个关键字和子节点。

4.倒排索引：倒排索引是用于文本搜索和信息检索的常见索引结构。

它将文档中的每个单词或关键字映射到包含该单词的文档列表中。

倒排索引适合处理自由文本，可以快速定位包含指定关键字的文档。

数据结构的实际应用案例分析数据结构是计算机科学中非常重要的一个概念，它是指数据元素之间的关系，以及数据元素本身的存储结构。

在计算机领域中，数据结构被广泛应用于各种算法和数据处理过程中，能够提高程序的效率和性能。

本文将通过几个实际应用案例来分析数据结构在现实生活中的应用。

1. 社交网络中的好友关系图在社交网络中，人们之间的好友关系可以用图这种数据结构来表示。

每个人都是一个节点，而好友关系则是节点之间的边。

通过这种数据结构，社交网络平台可以快速地查找用户的好友、好友的好友，实现推荐好友、推荐兴趣爱好等功能。

同时，还可以通过分析好友关系图，发现用户之间的社交圈子、影响力等信息，为用户提供个性化的服务。

2. 文件系统中的目录结构在计算机的文件系统中，文件和目录之间的关系可以用树这种数据结构来表示。

树的根节点代表根目录，每个目录都是一个节点，而文件则是叶子节点。

通过树这种数据结构，文件系统可以实现文件的组织和管理，快速地查找文件、创建目录、移动文件等操作。

同时，还可以通过树的遍历算法，实现文件系统的备份、恢复等功能。

3. 路由器中的路由表在网络通信中，路由器通过路由表来决定数据包的转发路径。

路由表可以用哈希表、树等数据结构来实现，不同的数据结构对应不同的路由查找算法。

通过合理设计路由表的数据结构和算法，可以提高路由器的转发效率，减少网络延迟，提升网络性能。

4. 搜索引擎中的倒排索引在搜索引擎中，倒排索引是一种常用的数据结构，用于快速地查找包含特定关键词的文档。

倒排索引将关键词与包含该关键词的文档之间的映射关系存储起来，通过这种数据结构可以实现搜索引擎的关键词检索功能。

倒排索引可以通过哈希表、树等数据结构来实现，不同的数据结构对应不同的搜索算法，影响搜索引擎的检索速度和准确性。

5. 数据库系统中的索引结构在数据库系统中，索引是一种用于加快数据检索速度的数据结构。

数据库系统可以通过B树、B+树等数据结构来实现索引，提高数据库的查询效率。

第九章查找一、选择题1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。

A． (n-1)/2 B. n/2 C. (n+1)/2 D. n2. 下面关于二分查找的叙述正确的是 ( )A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储3. 用二分（对半）查找表的元素的速度比用顺序法( )A．必然快 B. 必然慢 C. 相等 D. 不能确定4. 具有12个关键字的有序表，折半查找的平均查找长度（）A. 3.1B. 4C. 2.5D. 55．当采用分块查找时，数据的组织方式为 ( )A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D. 数据分成若干块，每块（除最后一块外）中数据个数需相同6. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

7. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败,它们的平均查找长度是((1)) ,对于查找成功,他们的平均查找长度是((2))供选择的答案:A. 相同的B.不同的9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90）C.（100，60， 80， 90， 120，110，130）D. (100，80， 60， 90， 120，130，110)10. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。

第九章查找一、选择题1。

若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。

A． (n—1)/2 B. n/2 C。

（n+1）/2 D。

n2. 下面关于二分查找的叙述正确的是（ )A。

表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列B。

表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储3. 用二分(对半）查找表的元素的速度比用顺序法（ )A．必然快 B. 必然慢 C. 相等 D. 不能确定4. 具有12个关键字的有序表，折半查找的平均查找长度( ）A. 3。

1 B。

4 C. 2。

5 D. 55．当采用分块查找时,数据的组织方式为 ( ）A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序,但块间必须有序，每块内最大(或最小）的数据组成索引块C。

数据分成若干块，每块内数据有序，每块内最大(或最小）的数据组成索引块D. 数据分成若干块,每块（除最后一块外)中数据个数需相同6。

二叉查找树的查找效率与二叉树的( （1）)有关, 在（（2）)时其查找效率最低（1）: A。

高度 B。

结点的多少 C. 树型 D. 结点的位置(2）: A。

结点太多 B. 完全二叉树 C。

呈单枝树 D. 结点太复杂。

7. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败，它们的平均查找长度是((1）） ,对于查找成功，他们的平均查找长度是（（2））供选择的答案：A。

相同的 B。

不同的9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）A．(100,80， 90， 60， 120，110，130） B。

（100，120，110,130，80， 60, 90) C。

（100，60, 80， 90, 120，110，130） D。