数据结构期末复习讲解

计算机1405杨程皓。

附录是最小生成树和拓扑排序的**及讲解，还有一些主要算法的演示。

一、基本概念及基本结构。

1、数据结构及其逻辑结构、存储（物理）结构的基本概念。

答：数据结构是相互之间存在一种或多种特定关系的数据元素的集合，在任何问题中，数据元素都不是孤立存在的，而是在他们之间存在着某种关系，这种数据元素相互之间的关系称为结构。根据数据元素之间关系的不同特性，通常分为下列4类(1)集合(2)线性结构(3)树形结构(4)图状结构或网状结构。

数据结构在计算机中的表示(又称映像)称为数据的物理结构，又称存储结构。数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：

顺序存储结构和链式存储结构。顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像的特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

2、动态存储顺序表的基本概念。（不准确）

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构是一种随机存取的存储结构。

3、单链表、循环单链表、双链表的基本概念。

线性表的链式存储结构的特点使用一组任意的存储单元存储线性表的数据元素，为了表示每个数据元素a(i)与其直接后继数据元素a(i+1)之间的逻辑关系，对数据元素a(i)来说，除了存储其本身的信息之外，还需储存一个指示其直接后继的信息。这两部分信息组成数据元素a(i)的存储映像，称为结点。它包括两个域：

其中存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域。n个结点链接成一个链表，即为线性表的链式存储结构。

由于此链表的每个节点中只包含一个指针域，故又称线性链表或单链表。

循环链表是另一种形式的链式存储结构，它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。每个节点只包含一个指针域则为循环单链表。

双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。

4、顺序栈的基本概念。

顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。

5、循环队列、链队列的基本概念。

队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针的队列叫循环队列。

（这里需要掌握循环队列的判空的三种方法）。

用链表表示的队列简称为链队列。

6、字符串的概念、存储结构、传统模式匹配算法思想。

串是由零个或多个字符组成的有限队列。

串的顺序存储结构简称为顺序串，与顺序表类似，顺序串是用一组地址连续的存储单元来存储串中的字符序列的。其描述如下：

#define maxstrlen 255

typedef unsigned char sstring[maxstrlen+1];

串的堆分配存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但他们的存储空间是在程序执行过程中动态分配得到。描述如下：

typedef struct

rtag=以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树称之为线索二叉树。

存储表示：typedef enum pointertag; /link==0:指针，thread==1,线索。

typedef struct bithrnodebithrnode,*bithrtree;

11、树的孩子兄弟链表的基本概念及存储结构。

3种常用的链表结构。

1.双亲表示法。

2.孩子表示法。

这两种表示法可以看书p135~p136

3.孩子兄弟表示法

孩子兄弟表示法又称二叉树表示法，即以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild域和nextsibling域。

typedef struct csnode{

elemtype data;

struct csnode *firstchild,*nextsibling;

csnode,*cstree;