数据结构1-3，5-6章 复习笔记

数据结构1-3，5-6章复习

第一章 绪 论

数据结构的概念与类型

• 集合
• 线性结构
• 树状结构
• 网状结构 图

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象，以及它们之间的关系和操作等的学科

数据 被计算机加工处理的对象。

数据元素（记录、表目） 数据的基本单位，是数据集合中的一个个体。

一个数据元素可由若干个数据项组成

数据类型 在一种程序设计语言中，变量所具有的数据种类。

数据对象 是性质相同的数据元素的集合，是数据的一个子集。（某种数据类型元素的集合。 ）
数据对象可以是有限的，也可以是无限的

数据结构 具有结构的数据元素的集合。它包括数据元素的逻辑结构、存储结构和相适应的运算（重要的是描述了数据对象各元素的关系！）

数据存储方式的四种常用结构

• 顺序存储 数据元素依次放在连续的存储单元中
• 链式存储 在存储结点中增加若干指针域，记录后继或者相关结点的地址（指针）
• 索引存储 将数据元素分为若干子表，子表的开始位置存放在索引表中
• 散列存储 根据数据元素的关键字值，由散列函数计算出存储地址。LOC(ai)=H(key)（哈希）

算法：是对特定问题求解步骤的一种描述

算法是指令的有限序列，其中每一条指令表示一个或多个操作。

算法具有以下五个特性：

• 有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

• 确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。

• 可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。

• 输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合

• 输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量

以下六种计算算法时间的多项式是最常用的。其关系为

$$O(1)<O(logn)<O(n)<O(nlogn) <O(n^2)<O(n^3)$$

指数时间的关系为

$$O(2^n)<O(n!)<O(n^n)$$

---

第二章 线性表

线性结构是一个数据元素的有序（次序）集合

线性结构的特征

• 集合中必存在唯一的一个"第一元素“
• 集合中必存在唯一的一个"最后元素“
• 除最后元素之外，其它数据元素均有唯一的"后继“
• 除第一元素之外，其它数据元素均有唯一的"前驱"

线性表的定义

是具有相同数据类型的n(n>=0)个数据元素的有限序列，通常记为：

$$(a_1，a_2，… a_{i-1}，a_i，a_{i+1}，…a_n)$$

其中n为表长， n＝0 时称为空表。

抽象类型线性表的定义

ADT List {
数据对象： 
D＝{ai | ai ∈ ElemSet, i=1,2,...,n, n≥0 }
数据关系：
R1＝{ < ai－1 , ai >| ai ∈D, i=2,...,n } 
序偶，即有序对，可以看作是具有两个元素的集合。但它与一般集合不同的是序偶具有确定的次序。 
基本操作
}ADT List

把基本操作放在这下面了：

可分为四类

• 结构初始化

  InitList(*L)

  
  

• 销毁结构

  DestroyList(*L)

  初始条件：线性表 L 已存在

  
  

• 引用型操作*

  ListEmpty( L )
  初始条件：线性表L已存在
  操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE

  
  

  ListLength( L )
  初始条件：线性表 L 已存在
  操作结果：返回 L 中元素个数

  
  

  PriorElem( L, cur_e, *pre_e )
  初始条件：线性表 L 已存在
  操作结果：若 cur_e 是 L 中的数据元素，则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义

  
  

  NextElem( L, cur_e, *next_e )
  初始条件：线性表 L 已存在
  操作结果：若 cur_e 是 L 中的数据元素，则用 next_e 返回它的后继，否则操作失败，next_e 无定义

  
  

  GetElem( L, i, *e )　　　
  初始条件：线性表 L 已存在$1≤i≤LengthList(L)$。
  操作结果：用 e 返回 L 中第 i 个元素的值

  
  

  LocateElem( L, e)
  初始条件：线性表 L 已存在。
  操作结果：返回 L 中与 e 相等的元素的序号。若这样的元素不存在，则返回值为0

• 加工型操作

  ClearList( *L )

  初始条件：线性表 L 已存在。

  操作结果：将 L 重置为空表

线性表的顺序存储表示和实现

顺序表,是用一组地址连续的存储单元依次存放线性表中的数据元素，

即以“存储位置相邻”表示“位序相继的两个数据元素之间的前驱和后继的关系

例如有序对$< a_{i－1},a_i>$

并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的基地址

$LOC(a_i ) = LOC(a_{i-1} ) + C$
其中，C是一个数据元素所占存储量

$LOC(a_i ) = LOC(a_1 ) + (i-1)×C$

线性表顺序存储结构的特点

• 逻辑上相邻的元素，其物理位置也相邻；

• 可**随机存取(也叫做直接取到）**表中任一元素；

• 必须按最大可能长度预分存储空间，存储空间利用率低，表的容量难以扩充，是一种静态存储结构；

• 插入删除时，需移动大量元素，平均移动元素为n/2

线性表的链式存储表示和实现

线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。
为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，数据元素ai除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）

线性表的链式存储表示：由分别表示 a1, a2 ,…, aN 的N 个结点依次相链构成的链表。

单链表：每个结点中只包含一个指针域。

头指针：第一个数据元素的存储地址为链表的基地址

• 链表中结点在内存中存放的位置可以是不连续的，甚至是零散分布的

• 存取元素操作为取第 i 元素，首先必须先找到第 i-1 个元素。因此不论 i 值为多少，都必须从头结点开始起“点数”，直数到第 i 个为止,也就是需要顺序存取。

单链表的优势

• 能有效利用存储空间；逻辑上相邻的元素，物理位置不一定需要相邻； 元素之间的邻接关系由指针域指示。链表是一种动态存储结构；
  链表的结点可调用malloc()申请和free()释放。
• 用“指针”指示数据元素之间的后继关系，便于进行“插入”、“删除”等操作

单链表的劣势

• 不能随机存取数据元素
• 线性表的“表长”和数据元素在线性表中的“位序”，在单链表中都看不见了。
• 不便于在表尾插入元素，需遍历整个表才能找到插入的位置。

第三章 栈与队列

栈

栈 是一种特殊的线性表，限定插入和删除操作只能在表尾进行。具有后进先出(LIFO—Last In First Out )的特点

**问：**有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个 ？

**分析：**我们从题目中就知道了出栈队列必为CDxxx

**答：**从题中可知,要使C第一个且D第二个出栈,应是A入栈,B入栈,C入栈,C出栈,D入栈,D出栈。

之后可以有以下几种情况:

• B出栈,A出栈,E入栈,E出栈,输出序列为CDBAE
• B出栈,E入栈,E出栈,A出栈,输出序列为CDBEA
• E入栈,E出栈,B出栈,A出栈,输出序列为CDEBA
• 所以可能的次序有:CDBAE,CDBEA,CDEBA

栈的顺序存储结构以及操作的实现

一个栈独占一组地址连续的存储单元

顺序栈=数组(栈空间)+栈顶指示

栈中的数据元素是用一组连续的存储空间来存放的。

栈底位置可以设置在存储空间的一个端点，而栈顶是随着插入和删除而变化的，用一个top指针来指示当前栈顶位置

CONST   arrmax=100 {栈的最大允许容量}；
typedef  struct  {
   Elemtype    * top;
   Elemtype    * base;
   int    stacksize;
  }  SqStack

SqStack S；
栈空条件 S.top=S.base (此时退栈则下溢)
栈满条件 S.top=S.base+arrmax (此时进栈则上溢)

栈的链式存储结构以及操作的实现

typedef  struct node  { 
    Elemtype     data;
    struct node  *next;
}  LinkStack;

LinkStack  * top;

此时只需要对顺序栈的基本操作接口作两处改动，便可作为链栈的基本操作接口。

其一是，初始化时不需要“maxsize”的参数，因为它不需要事先分配空间；

其二是，在进行入栈操作时不需要顾忌栈的空间是否已经被填满，但是在出栈时要及时free掉出栈的节点。

链栈的定义更简单，结点结构和单链表中的结点结构相同，无须重复定义。由于栈只在栈顶作插入和删除操作，因此链栈中不需要头结点，但要注意链栈中指针的方向是从栈顶指向栈底的，这正好和单链表是相反的。

能否将链栈中的指针方向反过来，从栈底到栈顶？

不行，如果反过来的话，删除栈顶元素时，为修改其前驱指针，需要从栈底一直找到栈顶,效率低！

前缀、中缀、后缀表达式

若$exp＝a×b+(c-d/e)×f$则它的

前缀式为：$ +×ab×－c/def $

中缀式为：$a×b＋c－d/e×f $

后缀式为：$ab×cde/－f×＋ $

综合比较它们之间的关系可得下列结论：

1．三式中的 “操作数之间的相对次序相同”；

2．三式中的 “运算符之间的的相对次序不同”；

3．中缀式丢失了括弧信息，致使运算的次序不确定；

4．前缀式的运算规则为：连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式；

5．后缀式的运算规则为：

• 运算符在式中出现的顺序恰为表达式的运算顺序；

• 每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式；

如何按后缀式进行运算？

可以用两句话来归纳它的求值规则：“先找运算符，后找操作数。”

说的更深一点，是先乘除后加减

从这个例子的运算过程可见，运算过程为：对后缀式从左向右"扫描"，遇见操作数则暂时保存，遇见运算符即可进行运算；此时参加运算的两个操作数应该是在它之前刚刚碰到的两个操作数，并且先出现的是第一操作数，后出现的是第二操作数。由此可见，在运算过程中保存操作数的结构应该是个栈

栈的递归问题

汉诺塔

void  hanoi (int n, char x,  char y, char z )
{   
         if (n==1) 
             move (x, 1, z);  //出口条件:将编号1的圆盘从x移到z 
         else{
                hanoi(n-1, x, z, y); //将n-1个圆盘从x移到y上，z为辅助塔座
			   move (x，n，z);   //将编号n的圆盘从x移到z
			   hanoi (n-1,  y, x, z); //将n-1个圆盘从y移到z上，x为辅助塔座
          	  }
}//hanoi

利用栈，栈中每个元素称为工作记录，分成三个部分：
返回地址 参数表(变参和值参) 局部变量

• 发生调用时，保护现场，将被调用函数的工作记录入栈，然后
  转入被调用的函数
• 一个调用结束时，恢复现场，即若栈不空，则退栈，从
  退出的返回地址处继续执行下去

队列

队列是一种特殊的线性表，限定插入和删除操作分别在表的两端进行。具有先进先出(FIFO—First In First Out)的特点

把允许插入的一端叫队尾(rear) ，把允许删除的一端叫队头(front)。没有元素时称为空队列，队列是尾进头出的

队列的链式存储结构以及操作的实现

[类型定义] 队头指针 + 队尾指针

typedef  struct node  { 
    Elemtype     data;
    struct node  *next;
}  QNode ;

QNode   * front,  * rear;

重点看出入队列的语句，牢记是队尾rear进，队头front出！

Status  EnQueue ( LinkQueue  *Q, Elemtype e )    //入队列，链表尾加元素   
{ 
         s = (Qnode *) malloc ( sizeof ( QNode ) );
         s->data = e; 
         s->next = NULL;
         Q->rear->next = s;
         Q->rear = s;
         return OK;
}

Status   DeQueue ( LinkQueue  *Q,  Elemtype  *e )	//出队列，链表头删元素
{    	// 链队不带头结点
     	if  ( Q->front = = NULL )   return ERROR;
		*e = Q->front->data;
 		p = Q->front;
 		Q->front = Q->front->next;					
 		if (Q->front = = NULL)  Q->rear = NULL;
 		free (p);
 		return  OK;
}

循环队列的顺序存储结构以及操作的实现

Elemtype   A[100]; 

int    rear,  front;

一般用法的顺序存储结构的缺陷在于出队列操作后，会大量移动数据（特别是数组起点），可能会存在“假上溢”现象。
解决假溢出的方法之一是将队列的数据区看成头尾相接的循环结构。只要队列元素个数小于总的可用空间，插入删除就可以一直进行下去。

如上图，队列最大长度为10
if(i+1 == 10){
    i=0;
}
          
else{
    i++;    
}

队尾插入一个元素时：
rear = (rear + 1) %10
队头删除一个元素时：
front = (front + 1) %10

为了分清队列的空与满，我们可以规定一个计数器用于计算队列中的元素的个数，或者可以采取空出一个元素的空间，以便于分出两个不同的条件，分别用来区分队列的空与满。

//默认队尾不存元素，指向一个空的空间
    
队指针初值：f = r = 1
队空条件： f = r
队满条件： f = (r mod m) + 1
指针后移时的取值：i = (i mod m) + 1

---

第五章 数组，广义表与算法

数组

任何数组都可以看作一个线性表，对n维数组而言，表中每一个元素是一个(n-1)维数组

数组元素的地址计算

对一维数组，

$$\begin{aligned} LOC[i] &=LOC[0]+i×L\\ &=b+ i × L\\ &=c0+c1× i,\\ ~\\ c1 &= L,\\ c0 &= b=LOC[0] \end{aligned}$$

对二维数组，

$$\begin{aligned} LOC[i,j]&=LOC[0,0]+(i×n+j)×L \\&=c0+c1×i+c2×j ~\\ \\c2 &=L \\c1 &=n×c2\\&=b2×c2 \\c0 &=b=LOC[0,0] \end {aligned}$$

推广到n维数组，

$$\begin{aligned} LOC[j_1,j_2,...,j_n]&=c_0+c_1×j_1 +c_2×j_2 +...+c_n×j_n \\ &=c_0+\sum^n_{i=1}c_i×j_i\\ ~\\ j_i&:所求的元素在i维的位置\\ c_n&=L：占用L个单元空间\\ c_{i-1}&=c_i×b_i (1<i\le n)：b_i=第i维占用的总行数\\ c0=b &=LOC[0,0,...,0]，起始地址\\ \end{aligned}$$

例 ElemType $A[3…7, 0…9, 1…6, 5…12] $
设每数组元素占用8个存储单元，起始地址为1000,求按低下标优先（类似行优先）顺序存储时，
LOC[6, 1, 4, 7]=？

答 $LOC[6, 1, 4, 7]=\\1000+(7-5)* 8\\+8* (4-1)* 8\\+8* 6*(1-0)*8\\+8* 6* 10* (6-3)* 8\\=13112$

---

用数组进行矩阵的压缩

对称矩阵

[特点] 在n8n的矩阵a中，满足如下性质：

$a_{ij}=a_{ji} (1 \le i, j \le n)$

[存储方法] 只存储下(或者上)三角(包括主对角线)的数据元素。共占用n(n+1)/2个元素空间:

$$\begin{equation} k=\left \{ \begin{array}{lr} \frac{i(i-1)}{2}+j-1 &,当 i \ge j\\ \frac{j(j-1)}{2}+i-1 &,当 i < j \\ \end{array} \right. \end{equation}$$

三角矩阵

随机稀疏矩阵

[特点] 大多数元素为零

[常用存储方法] 记录每一非零元素$(i,j,a_{ij})$
能节省空间，但丧失随机存取功能
顺序存储 三元组表
链式存储 十字(正交)链表

在行、列两个方向上，将非零元素链接在一起。克服三元组表在矩阵的非零元素位置或个数经常变动时的使用不便

行逻辑链接的表

散列表，实质就是一个数组内存放着其他链表/数组的链表/数组头

---

广义表

广义表是由零个或多个原子或者子表组成的有限序列。可以记作：LS=(d1, d2, … , dn )

• 原子：逻辑上不能再分解的元素。
• 子表：作为广义表中元素的广义表。

与线性表的关系
广义表中的元素全部为原子时即为线性表。线性表是广义表的特例，广义表是线性表的推广。

广义表的表示方法

表达式	表长	表深	表头	表尾
A=( )	0	1	无	无
B=(a, A)=(a, ( ))	2	2	a	(())
C=((a,b), c, d)	3	2	(a,b)	(c,d)
D=(a, D)=(a, (a, (a, …)))	2	$\infin$	a	(D)

表的长度 表中的元素（第一层）个数
表的深度 表中元素的最深嵌套层数

也就是括号的最多嵌套数

表头 表中的第一个元素
表尾 除第一个元素外，剩余元素构成的广义表

记得加一层括号！

Head():求广义表头

Tail():求广义表表尾：还是广义表，记得加括号！！！！！

非空广义表的表尾必定仍为广义表

一般用●表示表，用■表示原子

广义表的存储结构

第一种 头尾链表形式

表结点

tag=1	hp	tp
标志域：注明为表结点	指示表头的指针	指示表尾的指针

原子结点

tag=0	atom
标志域：注明为原子结点	值域

第二种 扩展的线性链表形式

表结点

tag=1	hp	tp
标志域：注明为表结点	指示表头的指针	指向同一层的下一个结点

原子结点

tag=0	atom	tp
标志域：注明为原子结点	值域	指向同一层的下一个结点

广义表结构的分类

• 纯表：与树型结构对应的广义表。

• 再入表：允许结点共享的广义表。

• 递归表：允许递归的广义表。

$$递归表\supset 再入表\supset纯表\supset线性表$$

广义表的递归算法

广义表的特点 定义是递归的

求广义表的深度

int GListDepth(GList1 L)	//分析表中各元素（子表）
{        if  (!L) return 1;   //空表
          if  (L->tag==ATOM) return 0;  //单原子
          for (max=0, pp=L; pp; pp=pp->ptr.tp) {
                  dep=GListDepth (pp->ptr.hp);
                  if (dep>max) max=dep;
           }
           return  max+1;
 }//GListDepth

或者

int GListDepth(GList1 L)	//分析表头和表尾
{        if  (!L) return 1;   //空表
          if  (L->tag==ATOM) return 0;  //单原子
          dep1=GListDepth (L->ptr.hp)+1;
          dep2=GListDepth (L->ptr.tp);
          if  (dep1>dep2)  return dep1;
          else   return  dep2;
 }//GListDepth

复制广义表

基本项：InitGList(NEWLS)
当LS为空表时；

​ 复制单原子结点
​ 当LS为原子时；
归纳项：建表结点；
​ 复制表头；
​ 复制表尾；

Status CopyGList(GList1 &T, GList1 L)
{        if  (!L) T=NULL;   //复制空表
         else {
            T=(GList1)malloc(sizeof(GLNode));
            if (!T) exit(OVERFLOW);
            T->tag=L->tag;
            if (L->tag==ATOM) T->atom=L->atom; //复制单原子
            else {
                 CopyGList(T->ptr.hp, L->ptr.hp);
                 CopyGList(T->ptr.tp, L->ptr.tp);
            }
         }
         return  OK;
}//CopyGList

---

我树呢？