数据结构笔记

数据结构

1、数据结构的概念

有许多编程问题是无法用数学的公式或方程来描述，是一些“非数值计算”的程序设计问题。

描述非数值计算问题的数学模型不是数学方程，而是诸如表、树和图之类的具有逻辑关系的数据。

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

数据的基本单位是数据元素

构成数据的元素的不可分割的最小单位是数据项

数据对象是性质相同的数据元素的集合

名称	定义	与数据的关系
数据元素	组成数据的基本单位	是集合的个体
数据对象	性质相同的数据元素的集合	集合的子集

数据元素不是孤立存在的，它们之间存在着某种关系、数据元素相互之间的关系称为结构
是指相互之间存在着一种或多种特定关系的数据元素集合
或者说，数据结构就是带结构的数据元素的集合

1. 数据结构包括以下三个方面的内容：

数据元素之间的逻辑关系，也称为逻辑结构。
数据元素及其关系在计算机内存中的表示（也称为映像），称为数据的物理结构或数据的存储结构。
数据的运算和实现，即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现。

2. 数据结构的两个层次

1. 逻辑结构

描述数据元素之间的逻辑关系
与数据的存储无关，独立于计算机
是从具体问题抽象出来的数学模型

2. 物理结构（存储结构）

数据元素及其关系在计算机存储器中的结构（存储方式）
是数据结构在计算机中的表示

3.逻辑结构与存储结构的关系：

存储结构是逻辑关系的映像与元素本身的映像
逻辑结构是数据结构的抽象，存储结构是数据结构的实现
两者综合起来建立了数据元素之间的结构关系。

2、逻辑结构的种类

划分方法一

线性结构

有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。

例如：线性表、栈、队列、串

非线性结构

一个结点可能有多个直接前趋后直接后继。

例如：树、图

划分方法二——四种基本逻辑结构

集合结构：结构中的数据元素除了同属于一个集合的关系外，无任何其它关系。
线性结构：结构中的数据元素之间存在着一对一的线性关系。
树形结构：结构中的数据元素之间存在着一对多的层次关系。
图状结构或网状结构：结构中的数据元素存在着多对多的任意关系。

3、存储结构的种类——四种基本的存储结构

顺序存储结构：

用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。
C语言中用数组来实现顺序存储结构

链接存储结构：

用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。
C语言中用指针来实现链式存储结构

索引存储结构：

在存储结点信息的同时，还建立附加的索引表。
索引表中的每一项称为一个索引项。
索引项的一般形式是：（关键字，地址）
关键字是能唯一标识一个结点的那些数据项。
若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引。若一组结点在索引表中只对应一个索引项，则该索引称之为稀疏索引。

散列存储结构：

根据结点的关键字直接计算出该结点的存储地址。

4、数据类型和抽象数据类型

数据类型

定义：数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。

抽象数据类型

定义：是指一个数学模型以及定义在此数学模型上的一组操作。
- 由用户定义，从问题抽象出数据模型（逻辑结构）
- 还包括定义在数据模型上的一组抽象运算（相关操作）
- 不考虑计算机内的具体存储结构与运算的具体实现算法

抽象数据类型的形式定义

抽象数据类型可以用（D，S，P）三元组表示。

其中：

D是数据对象
S是D上的关系集
P是对D的基本操作集

算法和算法分析

1、算法与程序

算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。
程序是用某种程序设计语言对算法的具体实现。

2、算法特性：一个算法必须具备以下五个重要特性

有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
确定性：算法中的每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即相对于相同的输入只能得到相同的输出。
可行性：算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
输入：一个算法有零个或多个输入。
输出：一个算法有一个或多个输出。

3、评判优劣算法

一个好的算法首先要具备正确性，然后是健壮性，可读性，在几个方面都满足的情况下，主要考虑算法的效率，通过算法的效率高地来评判不同算法的优劣程度
算法效率以下两个方面来考虑：
- 时间效率：指的是算法所消耗的时间；
- 空间效率：指的是算法执行过程中所耗费的存储空间。
  
  时间效率和空间效率有时候是矛盾的。

线性表

1、线性表存储结构

在计算机内，线性表有两种基本的存储结构：顺序存储结构和链式存储结构

线性表的顺序表示又称为顺序存储结构或顺序映像。

顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

链表的各节点由两个域组成

数据域：存储元素数值数据

指针域：存储直接后继结点的存储位置

2、线性表的一些基本操作

InistList(&L) (Initialization List)
- 操作结果：构造一个空的线性表L
DestroyList(&L)
- 初始条件：线性表L已经存在。
- 操作结果：销毁线性表L。
ClearList(&L)
- 初始条件：线性表L已经存在
- 操作结果：将线性表L重置为空表。
ListEmpty(L)
- 初始条件：线性表L已经存在。
- 操作结果：若线性表L为空表，则返回TRUE；否则返回FALSE。
ListLength(L)
- 初始条件：线性表L已经存在。
- 操作结果：返回线性表L中的数据元素个数。
GetElem(L , i, &e)
- 初始条件：线性表L已经存在，1 <= i <= ListLength(L)。
- 操作结果：用e返回线性表L中第i个数据元素的值。
LocateElem(L, e, compare())
- 初始条件：线性表L已经存在，compare()是数据元素判定函数。
- 操作结果：返回L中第一个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值0
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无意义。
ListInsert(&L, i, e)
- 初始条件：线性表L已经存在，1 <= i <= ListLength(L) + 1.
- 操作结果：在L的第i个位置之前插入新的数据元素e, L的长度加一。
ListDelete(&L, &e)
- 初始条件：线性表L已经存在，1 <= i <= ListLength(L)。
- 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减一。
  - 删除钱（长度为n）：
    
    （a1、a2、 …、a~~i-1~~、ai、a~~i+1~~、…、an）
  - 删除后（长度为n - 1）：
    
    （a1、a2、…、a~~i-1~~、a~~i+1~~、…、an）
ListTraverse(&L, visited())
- 初始条件：线性表L已经存在。
- 操作结果：依次对线性表中每个元素调用visited()。

3、顺序线性表的相关代码实现

1. 顺序表的结构体定义

#define MAX_SIZE 100 //定义最大长度

typedef int ElemType;   //ElemType的类型根据实际情况而定，这里假定为int
typedef struct{
	ElemType *elems; // 顺序表的基地址  用动态分配的一维数组表示。
	int length; // 顺序表的长度
	int size; // 顺序表的空间
}SqList;

2. 顺序表初始化

bool InitList(SqList &L) {
    L.elems=new int[MAX_SIZE];  //为顺序表分配 Maxsize 个空间
    if(!L.elems) return false; //存储分配失败
    L.length=0; //空表长度为 0
    L.size = MAX_SIZE;
    return true;
}

3. 顺序表销毁

void DestroyList(SqList &L) {
    if(L.elems) delete []L.elems;  //释放存储空间
    L.length = 0;
    L.size = 0;
}

4. 顺序表清空

void ClearList(SqlList &L){
    L.length = 0;
}

5. 顺序表求长

int GetLength(SqlList L){
    return (L.length);
}

6. 顺序表判断是否为空

int IsEmpty(SqlList L){
    if(L.length == 0) return 0;
    else return 0;
}

7. 顺序表取值

bool GetElem(SqList L, int i, int &e) {	//根据位置i获取相应位置数据元素的内容
    if(L.length == 0 || i<0 || i>L.length-1) {
        return false;
    }
    e = L.elems[i];
    return true;
}

8. 顺序表查找

在线性表L中查找与指定值e相同的数据元素的位置
从表的一端开始，逐个进行记录的关键字和给定值的比较。找到，返回该元素的位置序号，未找到，返回0。

int LocateElem(SqList L, int i, int &e) {
    for(int i=0; i<L.length; i++) {
        if(L.elems[i] == e)	return i+1;		//查找成功，返回序号
        return 0;	//查找失败，返回0
    }
}

算法分析
平均查找长度： ASL = P1 + 2P2 + … + (n - 1)P~~n-1~~ + nPn
若每个记录查找的概率相等：Pi = 1 / n
则可以推导为以下公式

ASL_{ss} = \sum_{i = 1}^{n}P_iC_i = \frac{1}{n}\sum_{i=1}^{n}i = \frac{n+1}{2}

9. 顺序表插入

bool ListInsert(SqList &L,int i, int e) {
    if(i<0 || i>L.length) return false; //i 值不合法
    if(L.length == MAX_SIZE) return false; //存储空间已满
    for(int j = L.length-1; j>=i-1; j--) {
    L.elems[j+1] = L.elems[j]; //从最后一个元素开始后移，直到第 i 个元素后移
    }
    L.elems[i-1] = e; //将新元素 e 放入第 i 个位置
    L.length++; //表长增 1
    return true;
}

算法分析
若要考虑在各种位置插入（共n+1种可能）的平均移动次数，该如何计算
插入到各个位置的概率为 $\frac{1}{n+1}$
插入所需移动次数为 $n+1-i$
公式如下

\frac{1}{n+1}\sum_{i=1}^{n+1}(n-i+1)=(n+ ... +1+0) =\frac{1}{n+1}(n+...+1+0)

= \frac{1}{n+1}\frac{n(n+1)}{2} = \frac{n}{2}

所以平均时间复杂度为** $O(n)$ **

10. 顺序表删除

bool ListDelete(SqList &L,int i,int &e) {
    if(i<0 || i>=L.length) return false; //不合法
    if(L.length == 0)	return false;   //线性表为空
    e = L.elems[i];  //返回被删除元素   
    for(int j=i; j<=L.length-1; j++) {
        L.elems[j-1] = L.elems[j]; //被删除元素之后的元素前移
    }
    L.length--;
    return true;
}

算法分析
若要考虑在各种位置删除（共n种可能）的平均移动次数，该如何计算
在各个位置删除的概率为 $\frac{1}{n}$
所需要的移动次数为 $n-i$

\frac{1}{n}\sum_{i=1}^{n}{n-i} = \frac{1}{n}\frac{n(n-1)}{2} = \frac{n-1}{2}

4.、顺序表的操作算法分析

时间复杂度
- 查找、插入、删除算法的平均时间复杂度为 $O(n)$
空间复杂度
- 顺序表操作算法的空间复杂度 $S(n)=O(1)$ 不占用辅助空间
优点：
- 存储密度大（节点本身所占存储量/结点结构所占存储量
- 可以随机存取表中任一元素
缺点：（用链表解决）
- 在插入、删除某一元素时，需要移动大量元素
- 浪费存储空间
- 属于静态存储形式，数据元素的个数不能自由扩充

5、与链式存储有关的术语

结点：数据元素的存储映像。由数据域和指针域两部分组成
链表：n个结点由指针链组成一个链表

6、线性表的链式表示和实现

有单链表、双链表、循环链表

单链表：结点只有一个指针域的链表，称为单链表或线性链表
双链表：结点有两个指针域的链表，称为双链表
循环链表：收尾相接的链表

1. 单链表的定义和表示

单链表的存储结构

typedef int ElemType;	//假设数据元素类型为int

typedef struct Lnode {
	ElemType data;	//结点的数据域
	struct Lnode *next;		//结点的指针域
}Lnode, *LinkList;

//定义链表L:
LinkList L;
//定义结点指针P:  以下两种方式都可以
LNode *p;
LinkList p;

2. 单链表基本操作的实现

1. 单链表初始化

//构造一个空的单链表 L
bool InitList(LinkList* &L) {
    L=new LinkNode; //生成新结点作为头结点，用头指针 L 指向头结点
    if(!L)return false; //生成结点失败
    L->next=NULL; //头结点的指针域置空
    return true;
}

2. 判断链表是否为空

bool ListEmpyt(LinkList L){
    if(L->next)	//非空
        return true;
    else
        return false;
}

3.销毁单链表

bool DestroyList_L(LinkList &L){
	Lnode *p;
    while(L){
        p = L;
        L = L->next;
        delete p;
    }
    return true;
}

清空单链表

bool ClearList(LinkList &L){		//将L重置为空表
    Lnode *p, *q;		//或者LinkList p，q；
    p = L->next;
    while(p){		//没到表尾
        q = p->next;
        delete p;
        p = q;
    }
    L->next = NULL;		//头结点指针域为空
    return true;
}

求单链表L的表长

int ListLength_L(LinkList L){
    LinkList p;
    p = L->next;
    i = 0;
    while(p){
        i++;
        p = p->next;
    }
    return i;
}

取值，取单链表中第i个元素的内容

Status GetElem_L(LinkList L, int i, ElemType &e){
    p = L->next;
    j = 1;
    while(p && j < i){
		p = p->next;
        ++j;
    }
    if(!p || j > i)
    	return ERROR;
    e = p->data;
    return OK;
}//GetElem_L

按值查找—根据指定数据获取该数据所在的位置（地址）

Lnode *LocateElem_L(LinkList L, Elemtype e){
	p = L->next;
    while(p && p->data != e)
        p = p->next;
    return p;
}

按值查找—根据指定数据获取该数据位置序号

Lnode *LocateElem_L(LinkList L, Elemtype e){
    p = L->next;
    while(p && p->data != e)
        p = p->next;
    return p;
}

插入—在第i个结点前插入为e的新结点

Status ListInsert_L(LinkList &L, int i, ElemType e){
    p = L;
    j = 0;
    while(p && j<i-1){
        p = p->next;
        ++j;
    }
    if(!p || j>i-1)
        return ERROR;
    s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}//ListInsert_L

删除—删除第i个结点

Status ListDelete_L(LinkList &L, int i, ElemType &e){
    p = L;
    j = 0;
    while(p->next && j<i-1){
        p = p->next;
        ++j;
    }
    if(!(p->next) || j>i-1)
        return ERROR;
    q = p->next;
    p->next = q->next;
    e = q->data;
    delete q;
    return OK;
}//ListDelete_L

建立单链表：头插法—元素插入在链表头部，也叫前插法

void CreateList_H(LinkList &L,int n){
    L = new LNode;
    L->next = NULL;
    for(i=n; i>0; --i){
        p = new LNode;
        cin >> p->data;
        p->next = L->next;
        L->next = p;
    }
}

尾插法—元素插入在链表尾部，也叫后插法

void CreateList_R(LinkList &L, int n){
   L = new LNode;
   L->next = NULL;
   r = L;
   for(i=0; i<n; ++i){
   	p = new LNode;
       cin >> p->data;
       p->next = NULL;
       r->next = p;
       r = p;
   }
}//CreateList_R

7、顺序表和链表的比较

链式存储结构的优点

结点空间可以动态申请和释放；
数据元素的逻辑次序靠结点的指针来指示，插入和删除不需要移动数据元素。

链式存储结构的缺点：

==存储密度==小，每个结点的指针域==需额外占用存储空间==。当每个结点的数据域所占字节不多时指针域所占空间的比重显得很大。

存储密度 = \frac{结点数据本身占用的空间}{结点占用的空间总量}

链式存储结构是==非随机存取==结构。对任一结点的操作都要从头指针依指针链查找到该结点，这增加了算法的复杂度。

8、栈的定义和特点

==栈==（stack）是一个特殊的线性表，只限定仅在一端（通常是表尾）进行插入和删除操作的线性表。

又称为==后进后出==（Last In First Out）的线性表，简称LIFO结构

栈的相关概念

==栈==是仅在表尾进行插入、删除操作的线性表。

表尾（即an端）称为==栈顶==Top；表头（即a1端）称为==栈底==Base

插入到元素栈顶（即表尾）的操作，称为==入栈==。

从栈顶（即表尾）删除最后一个元素的操作，称为==出栈==。

定义限定只能在表的一端进行插入和删除运算的线性表(只能在栈顶操作)
逻辑结构与同线性表相同，仍为一对一关系。
存储结构用顺序表或链栈存储均可，但以顺序栈更常见
运算规则只能在栈顶运算，且访问结点时依照后进先出(LIFO)的原则。
实现方式关键是编写入栈和出栈函数，具体实现依顺序栈和链栈的不同而不同

栈与一般线性表有什么不同

栈与线性表的区别：仅在于运算规则的不同

	一般线性表	栈
逻辑结构	一对一	一对一
存储结构	顺序表、链表	顺序栈、链栈
运算规则	随机存取	先进后出【LIFO】

9、队列的定义和特点

==队列==（queue）是一种==先进先出==（First In First Out—FIFO）的线性表。在表的一端插入（表尾），在另一端（表头）删除。

队列的相关概念

定义只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表（头删尾插）
逻辑结构与同线性表相同，仍为一对一关系。
逻辑结构顺序队或链队，以循环顺序队列更常见。
运算规则只在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。
实现方式关键是掌握入队和出队的操作，具体实现依顺序队或链队的不同而不同。

10、顺序栈的表示和实现

使用数组作为顺序栈存储方式的特点：
简单、方便、但易产生溢出（数组大小固定）

上溢(overflow)：栈已经满，又要压入元素
下溢(underflow)：栈已经空，还要弹出元素

[!CAUTION]

上溢是一种错误，使问题的处理无法进行；而下溢一般是一种结束条件，及问题处理结束。