当前位置：文档之家 › 数据结构

数据结构

  • 格式：doc
  • 大小：78.00 KB
  • 文档页数：5

数据结构和算法到底有什么用？
数据结构是对在计算机内存中（有时在磁盘中）的数据的一种安排。数据结构包
括数组、链表、栈、二叉树、哈希表等等。算法对这些结构中的数据进行各种处
理。例如，查找一条特殊的数据项或对数据进行排序。

掌握这些知识以后可以解决哪些问题呢？
现实世界数据存储
程序员的工具
建模
数据结构的特性：
数组：优点是插入快，如果知道下标，可以非常快地存取。缺点是查找慢，删除
慢，大小固定。

有序数组：优点是比无序的数据查找快。缺点是删除和插入慢，大小固定。
哈希表：优点是如果关键字已知则存取极快。插入快。缺点是删除慢，如果不知
道关键字则存取很慢，对存储空间使用不充分。

链表：优点是插入快，删除快。缺点是查找慢。
堆：优点是插入、删除快，对最大数据项的存取很快。缺点是对其他数据项存取
慢。

栈：优点是提供后进先出方式的存取。缺点是存取其他项很慢。
队列：提供先进先出方式的存取。缺点是存取其他项很慢。
二叉树：优点是查找、插入、删除都快（如果树保持平衡）。缺点是删除算法复
杂。

红－黑树：查找、插入、删除都快。树总是平衡的。缺点是算法复杂。
2-3-4树：优点是查找、插入、删除都快。树总是平衡的。类似的树对磁盘存储
有用。缺点是算法复杂。

图：优点是对现实世界建模。缺点是有些算法且复杂。
对于大多数数据结构来说，都需要知道如何插入一条新的数据项，如何寻找某一
特定的数据项，如何删除某一特定的数据项，还需要知道如何迭代地访问某一数
据结构中的各数据项，以便进行显示或其他操作。另一种重要的算法范畴是排序。

一、通用数据结构：数组，链表，树，哈希表
它们被称之为通用的数据结构是因为它们通过关键字的值来存储并查找数据，这
一点在通用数据库程序中常见到（栈等特殊结构正好相反，它们只允许存取一定
的数据项）。

通用数据结构可以完全按照速度的快慢来分类：
数组和链表是最慢的，树相对较快，哈希表是最快的。
但并不是使用最快的结构永远是最好的方案。这些最快的结构也有缺陷，首先，
它们的程序在不同程度上比数组和链表的复杂;其次，哈希表要求预先知道要 存
储多少数据，数据对存储空间的利用率也不是非常高。普通的二叉树对顺序的数
据来说，会变成缓慢的O(N)级操作;而平衡树虽然避免了上述的问题，但是它 的
程序编制起来却比较困难。
数组在下列情况下很有用：
数据量较小
数据量的大小事先可预测
如果存储空间足够大的话，可以放松第二条，创建一个足够大的数组来应付所有
可以预见的数据输入。

如果插入速度很重要的话，使用无序数组。如果查找速度很重要的话，使用有序
数组，并用二分查找。数组元素的删除总是很慢，这是由于为了填充空出来的单
元，平均半数以上的数组元素要被移动。在有序数组中的遍历是很快的，而在无
序的数组不支持这种功能。
向量（如Java中的向量类）是一种当数据太满时可以自己扩充空间的数组。向
量可以应用于数据量不可预知的情况下。然而，在向量扩充时，要将旧的数据拷
入一个新的空间中，这一过程会造成程序明显的周期性暂停。

如果需要存储的数据量不能预知或者需要频繁地插入删除数据元素时，考虑使用
链表。当有新的元素加入时，链表就开辟新的所需要的空间，所以它甚至可以占
满全部可用内存;在删除过程中没有必要像数组那样添补“空洞”。

二、专用数据结构：栈，队列，优先级队列
三、排序：插入排序，希尔排序，快速排序，归并排序，堆排序
四、图：邻接矩阵，邻接表
五、外部存储：顺序存储，索引文件，B-树，哈希方法

在程序中，存放指定的数据最常用的数据结构有两种：数组和链表。
数组和链表的区别：
1、数组是将元素在内存中连续存放。
链表中的元素在内存中不是顺序存储的，而是通过存在
元素中的指针联系到一起。

2、数组必须事先定义固定的长度，不能适应数据动态地增减的情况。
当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。

链表动态地进行存储分配，可以适应数据动态地增减的
情况。

3、(静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度
小。

链表从堆中分配空间, 自由度大但是申请管理比较麻烦。
数组和链表在存储数据方面到底孰优孰劣呢？根据数组和链表的特性，分两
类情况讨论。
一、当进行数据查询时，数组可以直接通过下标迅速访问数组中的元素。而
链表则需要从第一个元素开始一直找到需要的元素位置，显然，数组的查询效率
会比链表的高。

二、当进行增加或删除元素时，在数组中增加一个元素，需要移动大量元 素，
在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样，如果想删
除一个元素，需要移动大量元素去填掉被移动的元素。而链表只需改动元素中的
指针即可实现增加或删除元素。

那么，我们开始思考：有什么方式既能够具备数组的快速查询的优点又能融
合链表方便快捷的增加删除元素的优势？HASH呼之欲出。

所谓的hash，简单的说就是散列，即将输入的数据通过hash函数得到一个
key值，输入的数据存储到数组中下标为key值的数组单元中去。

我们发现，不相同的数据通过hash函数得到相同的key值。这时候，就产
生了hash冲 突。解决hash冲突的方式有两种。一种是挂链式，也叫拉链法。
挂链式的思想在产生冲突的hash地址指向一个链表，将具有相同的key值的数
据存放到链 表中。另一种是建立一个公共溢出区。将所有产生冲突的数据都存
放到公共溢出区，也可以使问题解决。

如何实现hash的动态增加空间的效果？这和装在因子密切相关。装填因子
= 填入表中的元素个数 / 散列表的长度。当装填因子达到一定值a时，我们就
让数组增加一定的内存空间，同时rehash。

下面用两个示例来加深理解。
示例一：用链表实现队列
节点类

合集下载

数据结构答案(清华大学出版)

数据结构答案(清华大学出版)

10
若是N维数组，其中任一元素的地址该如何计算？ 若是 维数组，其中任一元素的地址该如何计算？ 维数组 低维优先的地址计算公式，该式称为n维数组的映像函数： 低维优先的地址计算公式，该式称为n维数组的映像函数： 优先的地址计算公式
n
0)＋ Loc(j1,j2,…jn)=LOC(0,0, 0)＋i =1 j )=LOC(0,0,…0)
a11 a12 … a1n ^
… …
am1 am2 … amn ^
^ 注：数组的运算参见下一节实例（稀疏矩阵的转置） 数组的运算参见下一节实例（稀疏矩阵的转置）
13
5.3 矩阵的压缩存储
讨论： 讨论： 1. 什么是压缩存储？ 什么是压缩存储？ 若多个数据元素的值都相同 则只分配一个元素值的存储空间， 值都相同， 若多个数据元素的值都相同，则只分配一个元素值的存储空间， 且零元素不占存储空间。 且零元素不占存储空间。 2. 所有二维数组（矩阵）都能压缩吗？ 所有二维数组（矩阵）都能压缩吗？ 未必，要看矩阵是否具备以上压缩条件。 未必，要看矩阵是否具备以上压缩条件。 3. 什么样的矩阵具备以上压缩条件？ 什么样的矩阵具备以上压缩条件？ 一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩 一些特殊矩阵， 对称矩阵，对角矩阵，三角矩阵， 阵等。 阵等。 4. 什么叫稀疏矩阵？ 什么叫稀疏矩阵 稀疏矩阵？ 矩阵中非零元素的个数较少（一般小于5% 5%） 矩阵中非零元素的个数较少（一般小于5%） 重点介绍稀疏矩阵的压缩和相应的操作。 重点介绍稀疏矩阵的压缩和相应的操作。
8
无论规定行优先或列优先， 无论规定行优先或列优先，只要知道以下三要素便可随时求出 任一元素的地址（这样数组中的任一元素便可以随机存取！ 任一元素的地址（这样数组中的任一元素便可以随机存取！）： ①开始结点的存放地址（即基地址） 开始结点的存放地址（即基地址） 维数和每维的上、下界； ②维数和每维的上、下界； ac1,c2 … ac1,d2 ③每个数组元素所占用的单元数 Amn= … aij … ad1,c2 … ad1,d2 则行优先存储时的地址公式为： 行优先存储时的地址公式为： 存储时的地址公式为 LOC(aij)=LOC(ac1，c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L ， aij之前的 数组基址 a 本行前面的
数据结构——精选推荐

数据结构——精选推荐

数据结构1、简要回答术语：数据，数据元素，数据结构，数据类型。

A、数据(Data) ：是客观事物的符号表⽰。

在计算机科学中指的是所有能输⼊到计算机中并被计算机程序处理的符号的总称。

B、数据元素(Data Element) ：是数据的基本单位，在程序中通常作为⼀个整体来进⾏考虑和处理。

C、数据结构(Data Structure)：是指相互之间具有⼀定联系(关系)的数据元素的集合。

D、数据类型(Data Type)：是⼀个值的集合和定义在这个值集上的⼀组操作的总称。

2、数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是什么？A、元素之间的相互联系(关系)称为逻辑结构。

四种基本类型：集合、线性结构、树型结构、图状结构或⽹状结构B、数据结构在计算机中的表⽰（⼜称映像）称为数据的物理结构，⼜称存储结构。

3、算法分析的⽬的是什么？算法分析的主要⽅⾯是什么？4、分析以下程序段的时间复杂度，请说明分析的理由或原因。

⑴Sum1( int n ){ int p=1, sum=0, m ;for (m=1; m<=n; m++){ p*=m ; sum+=p ; }return (sum) ;}⑵Sum2( int n ){ int sum=0, m, t ;for (m=1; m<=n; m++){ p=1 ;for (t=1; t<=m; t++) p*=t ;sum+=p ;}return (sum) ;}⑶递归函数fact( int n ){ if (n<=1) return(1) ;else return( n*fact(n-1)) ;}1、简述下列术语：线性表，顺序表，链表。

A、线性表(Linear List)：是由n(n≧0)个数据元素(结点)a1，a2，…an组成的有限序列。

B、线性表的顺序表⽰指的是⽤⼀组地址连续的存储单元依次存储线性表的数据元素。

C、链式存储：⽤⼀组任意的存储单元存储线性表中的数据元素。

计算机最基本数据结构

计算机最基本数据结构

计算机最基本数据结构
计算机最基本的数据结构有四种：数组、链表、栈和队列。

这些数据结构是计算机科学中最重要的概念之一，也是任何计算机程序员必须掌握的基础知识。

一、数组
数组是一种线性数据结构，它由相同类型的元素组成，这些元素按照一定的顺序排列。

每个元素都可以通过索引访问，索引通常从零开始。

数组在计算机科学中非常有用，因为它们可以快速访问和修改元素，而且它们的空间效率很高。

二、链表
链表也是一种线性数据结构，但与数组不同的是，链表中的元素不必按照顺序存储。

链表中的每个元素都包含一个指向下一个元素的指针。

这些指针将所有元素连接在一起，形成了一个链表。

链表在插入和删除元素时非常高效，但是访问元素时需要遍历整个链表，效率较低。

三、栈
栈是一种后进先出（LIFO）的数据结构，它只允许在栈顶插入和删除元素。

当你将一个元素压入栈中时，它就成了栈顶元素，当你从
栈中弹出一个元素时，它就不再是栈顶元素。

栈在计算机科学中有很多应用，例如函数调用和表达式求值。

四、队列
队列是一种先进先出（FIFO）的数据结构，它允许在队列的末尾插入元素，并从队列的前面删除元素。

队列在计算机科学中也有很多应用，例如进程调度和消息传递。

总结
数组、链表、栈和队列是计算机科学中最基本的数据结构之一。

它们在计算机程序中有广泛的应用，任何计算机程序员都必须掌握它们。

了解这些数据结构的优缺点，可以帮助你更好地设计和实现计算机程序，提高程序的效率和可靠性。

常见的数据结构模型

常见的数据结构模型

常见的数据结构模型数据结构是计算机科学中重要的基础知识，用于组织和存储数据以便有效地操作和访问。

常见的数据结构模型包括线性结构、树状结构、图状结构和哈希结构。

1.线性结构：线性结构是最简单、最常见的数据结构模型之一，它是一组数据元素按照特定次序排列而成的数据结构。

其中最基本的线性结构是数组和链表。

-数组：数组是一种连续存储的线性结构，所有元素在内存中占用一段连续的地址空间，通过索引值可以快速访问元素。

数组的大小固定，并且插入、删除元素较为复杂。

-链表：链表由节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

链表可以分为单向链表、双向链表和循环链表等多种形式。

链表的大小可变，插入、删除元素操作较为简单，但访问元素需要遍历链表。

2.树状结构：树状结构是一种非线性的数据结构，它由节点和边组成，每个节点可以有多个子节点。

树状结构常用来表示层次关系，常见的树状结构包括二叉树、堆、平衡二叉树和B树。

-二叉树：二叉树是一种特殊的树结构，每个节点最多有两个子节点。

二叉树可以分为普通二叉树、满二叉树和完全二叉树等多种形式。

-堆：堆是一种特殊的二叉树，对于任意节点N，N的父节点的值大于等于（或小于等于）N的左右子节点的值。

堆常用于实现优先队列等数据结构。

-平衡二叉树：平衡二叉树是一种特殊的二叉树，它的左右子树的高度差不超过1、平衡二叉树常用于提高查找、插入和删除操作的效率，例如AVL树和红黑树等。

-B树：B树是一种多路树，每个节点可以有多个子节点。

B树常用于存储大量数据的数据库和文件系统等场景，可以有效地减少磁盘I/O次数。

3.图状结构：图状结构是一种由节点和边组成的非线性数据结构，节点之间可以有多个关系。

图状结构常用于表示网络、社交关系等复杂的实际问题。

-有向图：有向图中每条边都有一个方向，表示从一个节点到另一个节点的有向关系。

-无向图：无向图中每条边没有方向，表示节点之间的无向关系。

-加权图：加权图中每条边都有一个权值，表示节点之间的带权关系。