数据结构和数据库

《数据结构和数据库》由会员分享，可在线阅读，更多相关《数据结构和数据库（9页珍藏版）》请在金锄头文库上搜索。

1、1、绪论(1) 数据：数据(Data)是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被程序处理的符 号的总称。数据是计算机程序加工的“原料”。例如，一个利用数值分析方法解代数方程的程序，其处理的数据 是整数和实数；一个编译程序或文字处理器(比如Word)处理的数据是字符串。因此，对计算机科学而言，数据的 含义极为广泛，如图象、声音等都可以通过编码而归之于数据的范畴。(2) 数据元素：相对独立的数据单位。对于一个文件来说，每个记录就是它的数据元素；对于一个字符串来说，每 个字符就是它的数据元素；对于一个数组来说，每一个数值就是它的数据元素。数据对象(Data Object):数

2、据对象(Data Object)是性质相同的数据元素的集合，是数据的一个子集。例如，整 数数据对象的集合可表示为N = 0， 1， 2.，字母字符数据对象的集合可表示为 C=A,B,；Z。(3) 数据结构(Data Structure):是指数据元素之间存在着的一种或多种特定的关系。我们根据数据元素之间关 系的不同特性，将数据结构划分为四种类型： 集合：结构中的数据元素之间除了 “同属于一个集合”的关系外，别无其它关系； 线性结构：结构中的数据元素之间存在一对一的关系，即相邻数据元素之间具有“前驱”和“后继”的关系； 树形结构：结构中数据元素之间存在一对多的关系； 图状结构或网状结构：结构中数

3、据元素间存在多对多的关系。由于“集合”是数据元素之间关系极为松散的一种 结构，因此也可以用其它结构来表示它。(4) 存储结构(Storge Structure):数据结构在计算机中的表示(或称映象)称为数据的存储结构，又称为物 理结构。顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。二、线性表和广义表1、线性表：线性表是具有相同属性的数据元素组成的一个有限序列。线形表的存储结构：有顺序存储结构和链接存储结构两种。(1) 顺序存储结构：采用数组来来存储线性表，为保持线性表的线性

4、关系，在数组中元素连续、顺序地存放。下标 IW 层略用C+类表示的线性表顺序存储结构：struct List ElemType * data; 存放元素的数组int size; 顺序表当前巳存表项的最后位置(线性表的长度) ;(2)线性表的链接存储：线性表用单链表作为存储结构的类型定义：struct LNode ElemType data; /数据域LNode* next; 后继指针；2、广义表：广义表是由n（n=0）个元素组成的有限序列。表的元素或者是某种类型的对象（称为单元素），也 可以是一个广义表（称为表元素）。广义表是一种递归数据结构。表示为：LS = （?0,?1,?2,，？n-1）

5、为了区分单元素和表元素，一般表元素用大写表示，单元素用小写表示。表头：广义表第一个元素的值。可能是单元素也可能是表。表尾：广义表除第一个元素外由其它元素组成的表。广义表结构的特点：有次序性、长度、有深度、可递归、可共享。struct GLNode bool tag; / 标志域unionElcmType data / 数据域GLNode* sublist; /子表的表头指针域;GLNode* next; /指向后继结点的指针域;关于联合变量union:联合变量表示其中的几种变量公用一个内存区域，在不同的时间可以存储不同类型的数据，编 译器在编译时自动生成一个变量，其长度为联合中长度最大的变量。

6、在这里广义列表中某个节点如果是单元素，那么 Union变量就表现为ElcmType，如果是广义表，那么就表现为GLNode。三、稀疏矩阵1、矩阵：（Matrix ）是一个具有m行X n列的数表，共有m X n个数。稀疏矩阵：是矩阵中的一种特殊情况，它的非零元素的个数远远小于零元素的个数。如图3-1就是一个3X5的稀疏矩阵。 01400-50-7000_3600280三元组：对于矩阵中的每个非零元素，可用它的行号、列号以及元素值这个三元组（i,j,a ij ）来表示。稀疏矩阵的三元组表示：把每个非零元素的三元组按照行号为主序（即为主关键字）、列号为辅序（即为次关键字） 进行排列，就构成了一个表示

7、稀疏矩阵的三元组线性表。2、稀疏矩阵的的存储结构：（1）顺序存储：就是对其相应的三元组线形表进行顺序存储。这种存储方式的优点是利用数组存储，操作灵活。但 由于数组自身的问题，存储数据的数组的长度MaxTerms取一个大于非零元素个数的值，可能会浪费部分存储空间， 另外插入和删除非零元素需要移动大量元素。示意图如图3-2。 用于存储每个元素的结构类型（三元组）struct Triple int row,col; / 行、列ElemType val; / 元素值； 用于存储稀疏矩阵的结构类型（三元组顺序存储）struct Smatrix int m,n,t;/稀疏矩阵的行、列和非零元素个数Trip

8、le smMaxTerms+1;/存储三元组的数组，MaxTerms大于等于非零元素个数（2）带行指针向量的链接存储：在这种连接存储中，需要把具有相同行号的三元组节点按照列号从小到大的顺序连 接成一个单链表。这种存储方式可以节约存储空间，对于非零元素的增加和删除都很方便，缺点是不利于按列操作。struct TripleNode int row,col;ElemType val;TripleNode* next; /指向下一个非0元素;struct LMatrix int m,n,t; /原始矩阵的行数、列数、非0元素个数TripleNode* vectorMaxRows+1; / 存储每一行的

9、表头指针，MaxRows 的值大于/等于所存储矩阵的行数;（3）十字链接存储：就是既带行指针向量又带列指针向量的链接存储。在这种链接存储中，每个三元组结点既处于同一行的单链表中，又处于同一列的单链表中，即处于所在的行单链表和列单链表的交点 处。ElemType val; /非零元素的元素值CrossNode* down,*right; /指向同一列或同一行下一个结点的指针 ;struct CLMatrix /稀疏矩阵的行数、列数和元素个数CrossNode*rvMaxRows+1; / 行指针向量CrossNode*cvMaxColumns+1; / 列指针向量 ；四、栈和队列1、栈：栈是只允

10、许在表的一端进行插入和删除的线性表。（1）栈的顺序存储结构：const StackMaxSize 50 ;/根据需要事先定义栈的大小Struct StackElemType stackStackMaxSize ; / 数据域int top ; /栈顶指针;栈满和栈空是栈操作时需要特别考虑的情况，编程时需要做特别处理。栈满：top = StackMaxSize-1（2）栈的链接存储结构Struct LNode ElemType data ; / 数据域struct LNode *next ; / 指针域；2、队列队列：只允许在一端插入，在另一端删除的线性表。（1）队列的顺序存储结构：struct

11、 Queue ElemType queue QueueMaxSize ;int front , rear ;front指向队首元素，rear指向队尾元素。插入时rear向后移动一个位置，把元素存储到rear指向的存储位置; 删除时把front指向存储位置的元素取出，然后指针向后移动一定的位置。（2）队列的链接存储结构：队列的链接存储也是由单链表实现的，此时只允许在单链表的表头进行删除和在单链表的表尾进行插入，为了操作的 方便队列需要设置两个指针：队首指针front和队尾指针rear。用front指针指向队首（即表头）结点的存储位 置，用rear指向队尾（表尾）结点的存储位置。struct LN

12、ode ElemType data;LNode * next;；struct LinkQueue LNode * front;LNode * rear;五、树、二叉树1、树树是一种递归定义的数据结构。树(Tree )是树结构的简称，它是一种重要的非线性数据结构。树或者是一个空树， 即不含有任何的结点(元素)，或者是一个非空树，即至少含有一个结点。主要用于存储目录、索引、家族族谱等具 有层次关系的数据。树的递归定义：树(Tree)是n(nQ)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：(1) 有且仅有一个特定的称为根(Root)的结点；(2) 其余的结点可分为m(mNQ)个互不相

13、交的子集Tl，T2，Tm，其中每个子集本身又是一棵树，并称其 为根的子树(Subree)。注意：树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。 树的表示：树形图表示是树结构的主要表示方法。其他还有广义表、集合图、凹入图三种表示形式。线性结构和树型结构之间的区别：线性结构树型结构第一个数据元素(无前驱) 最后一个数据元素(无后继) 其它数据元素(一个前驱、一个后继)根结点(无前驱)多个叶子结点(无后继)其它数据元素(一个前驱、多个后继)2、二叉树二叉树是指树的度为2的有序树。是最简单的一种树结构，在计算机领域有着广泛的应用。二叉树的递归定义：二

14、叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的分别称根的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。(1)二叉树的存储结构：顺序存储结构#define MAX_TREE_SIZE 100 / 二叉数的最大结点数Typedef ElemType SqBiTreeMAX_TREE_SIZE ;/0 号单元存储根结点A25（i-。14进而通过顺序存储方式来存储二叉树。三个域：值域、左指针域和右指针域，其结点结构如8H4|i3I9I们可以通过添加虚节点来虚构一个完全二叉树，二叉链表采用独立结点， 下图所示：111215对于非完全二叉树储结构结点结构,leftdata right结点类型描述如下：Struct BTreeNodeElemType data;BTreeNode * left;BTreeNode * right;；（2）二叉树的遍历二叉树的遍历是二叉树最重要的算法，根据顺序分为下面几种：前序遍历所谓前序遍历，就是根结点最先遍历，其次左子树，最后右子树。上述的图形遍历的结果就是：A B D C E F中序遍历所谓中序遍历，就是左子树最先遍历，其次根结点，最后右子树。上述的图形遍历的结果就是：DBAECF后序遍历所谓后序遍历，就是右子树最先遍历，其次根结点，最后左