ch1.绪论

1.1 数据结构相关概念

数据元素：组成数据的基本单位。

数据对象：是具有相同性质的数据元素的集合，是数据的一个子集。

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

ADT：Abstract Data Types（抽象数据类型），有以下三个基本属性：

Encapsulation（封装）
Inheritance（继承）
Polymorphism（多态）

主要包含：数据对象、数据关系、基本操作。

Operations:

Precondition：执行前系统所在的状态

Input：输入

Process：加工，具体去做某事【顺序、分支、循环】

Output：输出

Postcondition：执行后对系统状态的改变【后置条件】

数据结构：

是相互之间存在一种或多种特定关系的数据元素的集合。

逻辑（Logical structure）：线性、非线性
存储（表示）：存储映像【物理】、what?【数据元素,Virtual elements,etc】、How【顺序、链式存储、Indexed Sequential、哈希】
操作：Query/search【判空、求长度、Get which element、前/后元素】、Process【值传递、地址传递】（Init()、Destroy()、clear()、Insert()、Delete()、update()等）

AKA（Also know as）、b/t（between）

相关规范：

Comments（函数功能、输入输出参数、关键语句）
Identifier naming（标志符的命名）
Structural control
File/document
Robustness（鲁棒性）：系统的稳定，如Precondition,input,process

1.2 数据结构的三要素

1.2.1 逻辑结构

逻辑结构是对数据元素之间逻辑关系的描述，它与数据在计算机中存储方式无关，根据数据元素之间的不同特性，可以对数据的逻辑结构进行分类，如：

集合：各个元素同属一个集合，别无其他集合。

线性结构：数据元素之间是一对一的关系。除了第一个元素，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继。

树形结构：数据元素之间是一对多的关系。

图结构：数据元素之间是多对多的关系。

1.2.2 数据的运算

针对于某种逻辑结构，结合实际需求，定义基本运算。

1.2.3 物理结构（存储结构）

顺序存储、链式存储、索引存储、散列存储。

1.3 算法效率的度量

算法复杂度的定义公式是：

$T = {\sum\limits_{1}^{M}N_{i}}*\tau_{i}$

其中前者为该种控制结构的总执行次数（Frequency），后者为该控制结构需要花的时间

1.3.1 算法时间复杂度

事前预估算法时间开销T(n)与问题规模n的关系（T表示time）

（1）顺序执行的代码只会影响常数项，可以忽略。

（2）只需挑循环中的一个基本操作分析它的执行次数与n的关系即可。

例：

void loveYou(int flag[],int n)
{
    printf("I am iron man\n");
    for(int i=0;i<n;i++)
    {
        if(flag[i]==n) //即找到该元素n
        {
            printf("I love you %d\n",n);
            break;
        }
    }
}

其中flag数组中乱序存放了1-n这些数，调用该函数。计算上述算法的时间复杂度T(n).

在这个例子中，最好的情况是，元素n在第一个位置，最好时间复杂度T(n)=O(1)；最坏的情况是，元素n在最后一个位置，最坏时间复杂度T(n)=O(n)。而平均情况是：

假设元素n在任意一个位置的概率相同为1/n，循环次数$x = \left( {1 + 2 + 3 + \ldots + n} \right)\frac{1}{n} = \frac{n\left( 1 + n \right)}{2}\frac{1}{n} = \frac{1 + n}{2}$，平均时间复杂度T(n)=O(n).

该例说明：很多算法执行时间与输入的数据有关。

一般只考虑最坏和平均时间复杂度。

复杂度排序：“常对幂指阶”

$O(1)<O(log_{2}n)<O(n)<O(nlog_{2}n)<O(n^{2})<O(n^{3})<O(2^{n})<O(n!)<O(n^{n})$

1.3.2 算法空间复杂度

S(n)用大O表示法。

函数递归调用带来的内存开销：找到递归调用的深度x与问题规模n的关系：x=f(n)

void loveYou(int n)
{
    int flag[n];
    if(n>1)
        loveYou(n-1);
    printf("I love you %d\n",n);
}
int main()
{
    loveYou(5);
}

算法空间复杂度为：

$1 + 2 + 3 + \ldots + n = \frac{n\left( {1 + n} \right)}{2} = \frac{1}{2}n^{2} + \frac{1}{2}n$

$S\left( n \right) = n^{2}$

1.4 C语言相关重点知识回顾

1.4.1 结构体

typedef struct (s-name)
{
    char *name;
    int age;
}stu1,stu2[100],*stu3;

stu1 s1;//stu1为类型标识符

stu2 s2;

stu3 s3;等价于stu1 *s3，引用结构体变量s3.name等价于(*s3).name等价于s3->name.

1.4.2 值回传方法

（1）传指针——参数传递；

（2）全局静态变量——两个函数耦合，关系过于密切；

（3）return——只能回传一个。

能不用if就不用if（改为求表达式的值a>b?a:b)。

exit 结束程序状态

ch2.线性表

线性结构要求具有直接前驱（predecessor）和后继（successor）。

2.1 线性表的定义与ADT

2.1.1 线性表的定义

线性表是具有相同数据类型（每个数据元素所占空间一样大）的n(n>=0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则一般表示为L=(a1,a2,…,ai,ai+1,…，an)。

Q：何时传入参数的引用”&“? A:对参数的修改结果需要”带回来“。

线性表的ADT如下：

ADT List {
    Data object: D＝{ai |ai ∈ElemType, i=1,2,...,n, n≥0 }
    Relation:    R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n }
    Operations:
    InitList(&L) 
    DestroyList(&L)
    ListEmpty(L)
    ListLength(L) 
    PriorElem(L,cur_e, &pre_e)
    NextElem(L,cur_e, &next_e)
    GetElem(L,i,&e)
    LocateElem(L,e,compare( ))
    ListTraverse(L,visit( )) 
    ClearList(&L) 
    PutElem(&L,i,e) 
    ListInsert(&L,i,e) 
    ListDelete(&L,i,&e)
} ADT List;

2.1.2 集合的并运算与元素剔除

集合的并运算代码如下：把B中不与A重复的并到A里面

void union(List &La, List Lb) {
    La_len = ListLength(La);
    Lb_len =ListLength(Lb); // length
    for (i = 1; i <= Lb_len; i++) {
      GetElem(Lb, i, e);// e is the ith element
      if(!LocateElem(La, e, Equal()) 
        ListInsert(La, ++La_len, e);//}
} // union

剔除（Purge）两线性表的重复元素：

法1：利用集合的并，先创建一个空表$A$，$LA=\varnothing$，再用Union操作。

法2：每次比较后面的数与当前的数是否相同，通过从当前后面一个数到末尾 while 循环，把后面所有重复的元素剔除。

注：

若是剔除当前元素，则不仅麻烦，而且会破坏顺序；

要注意 $LB$ 的长度会因为剔除而变短，故第八行应为while (j<listLength(LB))而不是LB_len。

代码如下：

void Purge(LB)
{
	int i = 1, j, x, y;
	while (i < ListLength(LB))
	{
		Getelem(L, i, x);
		j = i + 1;
		while (j < listLength(LB))
		{
			Getelem(LB, j, y);
			if (x == y)
				ListDelete(LB, j);
			else
				j++;
		}
		i++;
	}
}

2.1.3 合并(Merge)有序序列

合并有序序列，按大小顺序合并，其中A和B各自都有顺序。

 void MergeList(List La, List Lb, List &Lc)
 {
    La_len = ListLength(La);   
    Lb_len = ListLength(Lb);
    Lc_len =0;		//创建一个空表，这样可以一个个比较后放入C中
    i = j = 1;
    while (i<= La_len) && (j<= Lb_len) 	// A/B都没放完;循环截止到其中一个放完为止
    { 
      	GetElem(La, i, &x);
        GetElem(Lb, j, &y);
      	if (x<=y)
        {  
            ListInsert(Lc, ++Lc_len, x); 
            ++i; 
        }
      	else{
            ListInsert(Lc, ++Lc_len, y);
            ++j; 
        }
    }
    while(i<= La_len) 		//A没放完,B放完了
    {
      	GetElem(La, i, &x);
      	ListInsert(Lc, ++Lc_len, x);
        i++;
    }
    while(j<= Lb_len)		//B没放完,A放完了
    {
      	GetElem(Lb, j, &x);
      	ListInsert(Lc, ++Lc_len, x);
        j++;
    }
} //merge_list

2.2 顺序表

顺序表即用顺序存储的方式实现线性表。知道一个数据元素的大小，用sizeof(ElemType)。需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源。

顺序表的特点：

随机访问，即可以在O(1)时间内找到第i个元素；

存储密度高，每个节点只存储数据元素；

拓展容量和插入、删除操作不方便。

2.2.1 静态分配

#define MaxSize 10
typedef struct
{
    ElemType data[MaxSize];
    int length;   //顺序表的当前长度
}SqList;
//初始化一个顺序表
void InitList(SqList &L)
{
    for(int i=0;i<MaxSize;i++)
        L.data[i]=0;
    L.length=0;
}
int main()
{
    SqList L; //声明一个顺序表
    InitList(L); //初始化顺序表
    //...
    return 0;
}

==【应用】==

在实际应用中，$x[0]$可作哨兵元素，也可作暂存元素；在后面的排序算法中，若一个序列已经差不多有序，或元素少，可以选择插入排序。

2.2.2 动态分配

#define InitSize 10  //顺序表的初始长度
typedef struct
{
    ElemType *data;  //指示动态分配数组的指针
    int MaxSize;
    int length;
}SeqList;

动态申请和释放内存空间：

malloc、free函数：malloc函数的参数指明要分配多大的==连续==内存空间。

L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);

#include<stdlib.h> //malloc、free函数的头文件
#include<stdio.h>
#define InitSize 10
typedef struct
{
	int *data; //指示动态分配数组的指针
	int MaxSize;
	int length;
}SeqList;
void InitList(SeqList &L)
{
	//用malloc函数申请一片连续的内存空间
	L.data = (int *)malloc(InitSize * sizeof(int));
	L.length = 0;
	L.MaxSize = InitSize;
}
void IncreaseSize(SeqList &L, int len) //增加动态数组的长度
{
	int *p = L.data;
	L.data = (int *)malloc((L.MaxSize + len) * sizeof(int));
	for (int i = 0;i < L.length;i++)
	{
		L.data[i] = p[i];  //将数据复制到新区域
	}
	L.MaxSize += len; //顺序表最大长度增加len
	free(p);
}
int main()
{
	SeqList L;  //声明一个顺序表
	InitList(L);  //初始化顺序表
	//往顺序表中随便插入几个元素
	IncreaseSize(L, 5);
	return 0;
}

2.2.3 基本操作

主要包含创建、销毁、增加、删除、更改、查找等操作。对于销毁操作，静态分配的静态数组是由系统自动回收空间，对于动态分配（链表），需要依次删除各个结点(free操作)。

==插入==

#include<stdlib.h> //malloc、free函数的头文件
#include<stdio.h>
#define MaxSize 10
typedef struct
{
	int data[MaxSize];
	int length;
}SqList;
void ListInsert(SqList &L, int i, int e)
{
	for (int j = L.length;j >= i;j--)
		L.data[j] = L.data[j - 1];  //将第i个元素及以后的元素右移
	L.data[i - 1] = e;
	L.length++;
}
int main()
{
	SeqList L;  //声明一个顺序表
	InitList(L);  //初始化顺序表
	//插入元素
	IncreaseSize(L, 5);
	return 0;
}

在ListInsert函数中，还应判断i的范围是否有效（将函数类型定义为Bool类型），即：

if(i<1||i>L.length+1) return false;if(L.length>=MaxSize) return false;

问题规模n=L.length，最好情况是新元素插入到表尾，不需要移动元素，最好时间复杂度O(1)，最坏为O(n)。平均情况：

假设新元素插入到任何一个位置的概率相同，即i=1,2,3,…,length+1的概率都是p=1/(n+1);

当i=1,循环n次；i=2,循环n-1次；i=3，循环n-2次；…；i=n+1，循环0次。

则平均循环次数=np+(n-1)p+…+1*p=(n(n+1)/2)*(1/n+1)=n/2，故平均时间复杂度为O(n)。

==删除==

bool ListDelete(SqList &L, int i, int &e)
{
	if (i<1 || i>L.length) return false;
	e = L.data[i - 1];
	for (int j = i;j < L.length;j++)  //将第i个位置后的元素前移
		L.data[j - 1] = L.data[j];
	L.length--;  //线性表长度减1
	return true;
}
int main()
{
	SeqList L;  //声明一个顺序表
	InitList(L);  //初始化顺序表
	int e = -1;
	if (ListDelete(L, 3, e))
		printf("已删除第三个元素，删除的元素值=%d\n", e);
	else printf("位序i不合法，删除失败\n");
	return 0;
}

时间复杂度为$O(n)$。

==查找==

按位查找

GetElem(L,i): 获取表L中第i个位置的元素的值，其时间复杂度为$O(1)$

按值查找

LocateElem(L,e):在表L中查找具有给定关键值的元素，其时间复杂度为$O(n)$

若表内元素有序，可在O(log2n)的时间内找到。

2.3 单链表

2.3.1 单链表的定义

typedef struct LNode
{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个结点：LNode *L或LinkList L。（声明一个指针指向单链表第一个结点）

==一般来说，若强调这是一个单链表，使用LinkList；若强调这是一个结点，使用LNode。==

2.3.2 头结点的使用与单链表初始化

2.3.2.1 头结点的使用

在第一个结点之前附设头结点(Header Node)：

头结点的数据域：

存放线性表长度等附加信息
可以不存储任何信息

头结点的指针域：存储指向首元结点（即存储首元位置）的指针

此时，头指针指向头结点：

注：

头指针无论头指针是否存在，头指针均存在。

头指针的意义有：

统一空表和非空表操作
使每一结点均含有直接前驱

2.3.2.2 初始化空表

下面是带头结点的单链表和不带头结点的单链表初始化空表操作的代码：

不带头结点的单链表

bool InitList(LinkList &L)
{
	L = NULL;  //空表，防止脏数据
	return true;
}

带头结点的单链表：初始空链表后，需执行L->next=NULL。

bool InitList(LinkList &L)
{
	L = (LNode *)malloc(sizeof(LNode)); //分配一个头结点
	if (L == NULL)
		return false;  //内存不足，分配失败
	L->next = NULL;
	return true;
}

2.3.2.3 初始化带有元素的表

在这里，使用头结点初始化带有元素的表。

头插法建立单链表：

void CreateList_L(LinkList &L, int n)
{
    L = (LinkList) malloc (sizeof (LNode));
    L->next = NULL;  // establishs a header node 
    for (i = n; i > 0; --i) 
    {
      p = (LinkList) malloc (sizeof (LNode)); 
       // Generate the fresh node 
      scanf(&p->data); //'s input element value 
      p->next = L->next; L->next = p; //
    }
} // CreateList_L

其算法时间复杂度为O(ListLength(L))。

尾插法建立单链表：

这里用到了指针r来记录每次链表的最后一个元素；还可以设置变量length记录链表长度。

LinkList Create() 
{
    head=(LinkList) malloc (sizeof(LNode));
    head->next = NULL; 
    r=head;
    ch=getchar();
    while(ch<>'$')
    {
        s=(LinkList)malloc(sizeof(LNode));
        s->data=ch;
        r->next=s;
        r=s;				//每次更新r,让r指向最后一个结点
        ch=getchar();		//吞回车
    }
    r->next=NULL;			// is as to the non-empty list 
    return head;
}

2.3.3 插入操作

2.3.3.1 按位序插入和后插操作

头结点可以看作”第0个结点“：

//不带头结点
bool ListInsert(LinkList &L, int i, ElemType e)
{
	if (i < 1)
		return false;
	LNode *p;
	int j = 0;  //当前p指向的是第几个结点
	p = L;		//L指向头结点，头结点是第0个结点（不存数据）
	while (p != NULL && j < i - 1)  //循环找到第i-1个结点
	{
		p = p->next;
		j++;
	}
    //后插操作
	if (p == NULL)    //i值不合法
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;     //将结点s连到p之后
	return true;
}

注：

如果不带头结点，则插入、删除第1个元素时，需更改头指针L；

若不考虑指定位置处插入元素，一般使用带头结点的单链表，并进行头插。

2.3.3.2 前插操作

基本思想：

法1：先找前驱，再后插

法2：先后插，再交换数据域（常用）

bool InsertPriorNode(LNode *p, ElemType e)
{
	if (p == NULL) return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if (s == NULL)
		return false;
	s->next = p->next;
	p->next = s;		//新结点s连到p之后
	s->data = p->data;	//将p中的元素复制到s中
	p->data = e;		//p中元素覆盖为e
	return true;
}

2.3.4 删除操作

按位序删除

bool ListDelete(LinkList &L, int i, ElemType &e)
{
	if (i < 1) return false;
	LNode *p;
	int j = 0;
	p = L;
	while (p != NULL && j < n - 1)  //循环找到第n-1个结点
	{
		p = p->next;
		j++;
	}
	if (p == NULL) 
		return false;
	if (p->next == NULL)  //第i-1个结点之后已无其他结点
		return false;
	LNode *q = p->next;   //令q指向被删除的结点
	e = q->data;		  //用e返回元素的值
	p->next = q->next;	  //将*q结点从链中断开
	free(q);
	return true;
}

指定结点的删除

bool DeleteNode(LNode *p)
{
	if (p == NULL) return false;
	LNode *q = p->next;   //令q指向*p的后继结点
	p->data = p->next->data;
	p->next = q->next;
	free(q);
	return true;
}

注：

如果p是最后一个结点，则只能从表头开始找到p的前驱，时间复杂度是O(n)。

单链表的局限性：无法逆向检索，有时候不太方便。

2.4 双向链表

对于双向链表，有：p == p->prior->next == p->next->prior 。

2.4.1 初始化

typedef struct DNode
{
	ElemType data;
	struct DNode *prior, *next;
}DNode,*DLinklist;
bool InitDLinkList(DLinkList &L)
{
	L = (DNode *)malloc(sizeof(DNode)); //分配一个头结点
	if (L == NULL)
		return false;
	L->prior = NULL;	//头结点的prior永远指向NULL
	L->next = NULL;		//头结点之后暂时还没有结点
	return true;
}

2.4.2 插入操作

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s)
{
    if(p==NULL||s==NULL)
        return false;
    if(p->next!=NULL) 		 //如果p结点有后继结点
        p->next->prior=s;
    s->prior=p;
    p->next=s;
    return true;
}

2.4.3 删除操作

bool DeleteNextDNode(DNode *p)
{
    if(p==NULL) return false;
    DNode *q=p->next;		   //找到p的后继结点q
    if(q==NULL) return false;  //p没有后继
    p->next=q->next;
    if(q->next!=NULL) q->next->prior=p;
    free(q);
    return true;
}

2.4.4 遍历

前向遍历/后向遍历，时间复杂度为O(n)。

2.5 循环链表

单链表表尾结点的next指针指向NULL,而循环单链表表尾结点的next指针指向头结点。

循环单/双链表从一个结点出发，可以找到其他任何一个结点。

2.6 静态链表

data表示数据元素，next表示游标

适用场景：不支持指针的语言；数据元素数量固定不变的场景（即问题规模已知，如操作系统的文件分配表FAT）

2.6.1 定义静态链表

#define MaxSize 10
struct Node
{
    ElemType data;
    int next;      //下一个元素的数组下标
}

main函数中struct Node a[MaxSize];，用数组a作为静态链表。

定义的另一种方式：

#define MaxSize 10    //静态链表的最大长度
typedef struct
{
    ElemType data;
    int next;
}SLinkList[MaxSize];

这种定义方式等价于：

#define MaxSize 10    //静态链表的最大长度
struct Node
{
    ElemType data;
    int next;
};
typedef struct Node SLinkList[MaxSize];

即，可用SLinkList定义”一个长度为MaxSize的Node型数组。

在主函数中，声明一个静态链表可用SLinkList a;语句。

2.6.2 基本操作

初始化静态链表：把a[0]的next设为-1。

查找：从头结点出发挨个往后遍历结点。

插入位序为i的结点：

【1】找到一个空的结点，存入数据元素；

注：判断结点是否为空，可在初始化过程中把空闲元素赋某个值；之后查找，若某结点的数值为该值，说明该结点时空闲的。

【2】从头结点出发找到位序为i-1的结点；

【3】修改新结点的next；

【4】修改i-1号结点的next。

ch3.栈和队列

3.1 栈

只允许在一端进行插入或删除操作的线性表。

特点：后进先出 Last In First Out

n个不同元素进栈，出栈元素不同排列的个数为$\frac{1}{n + 1}C_{2n}^{n}$（卡特兰数）。

3.1.1 顺序栈的定义和基本操作

定义

#define MaxSize 10
typedef struct
{
    ElemType data[MaxSize];  //静态数组存放栈中元素
    int top;
}SqStack;

初始化栈时，将初始化栈顶指针赋为-1。

进栈

bool Push(SqStack &S,ElemType x)
{
    if(S.top==MaxSize-1)   //栈满，报错
        return false;
    S.top=S.top+1;
    S.data[S.top]=x; 	   //新元素入栈
    return true;
}

出栈

bool Pop(SqStack &S,ElemType &x)
{
    if(S.top==-1)      //栈空，报错
        return false;
    x=S.data[S.top];   //栈顶元素先出栈
    S.top=S.top-1;     //指针再-1
}

3.1.2 共享栈

定义及存储结构：两个栈共享同一片空间。

#define MaxSize 10
typedef struct
{
    ElemType data[MaxSize];
    int top0;		//0号栈栈顶指针
    int top1;		//1号栈栈顶指针
}ShStack;

初始化栈操作

void InitStack(ShStack &s)
{
    S.top0=-1;
    S.top1=MaxSize;
}

栈满的条件：top0+1==top1。

3.1.3 栈的链式存储结构

栈的链式存储结构中，将栈顶设置在头部，可以免去栈顶指针的设置问题（因为单链表有头指针）。

typedef struct StackNode
{
    ElemType data;
    struct StackNode *next;
}StackNode,*LinkStackPtr;

typedef struct
{
    LinkStackPtr top;
    int count;
}LinkStack;

/* 构造一个空栈S */
Status InitStack(LinkStack *S)
{ 
        S->top = (LinkStackPtr)malloc(sizeof(StackNode));
        if(!S->top)
                return ERROR;
        S->top=NULL;
        S->count=0;
        return OK;
}

/* 插入元素e为新的栈顶元素 */
Status Push(LinkStack *S,SElemType e)
{
        LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode)); 
        s->data=e; 
        s->next=S->top;	  /* 把当前的栈顶元素赋值给新结点的直接后继，见图中① */
        S->top=s;         /* 将新的结点s赋值给栈顶指针，见图中② */
        S->count++;
        return OK;
}

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(LinkStack *S,SElemType *e)
{ 
        LinkStackPtr p;
        if(StackEmpty(*S))
                return ERROR;
        *e=S->top->data;
        p=S->top;					/* 将栈顶结点赋值给p，见图中③ */
        S->top=S->top->next;    /* 使得栈顶指针下移一位，指向后一结点，见图中④ */
        free(p);                    /* 释放结点p */        
        S->count--;
        return OK;
}

3.2 队列

只允许在一端进行插入，在另一端删除的线性表。

队列的特点：先进先出（FIFO）

重要术语：队头、队尾、空队列

3.2.1 顺序存储结构

分析思路：分析front、rear指针的指向；确定判空、判满的方法。

初始化

#define MaxSize 10		//定义队列中元素的最大个数
typedef struct
{
    ElemType data[MaxSize];
    int front,rear;	    //队头指针和队尾指针
}SqQueue;  //sequence顺序

初始化时，可将front指向队头元素，rear指向队尾元素的后一个位置（下一个应该插入的位置）。

void InitQueue(SqQueue &Q)
{
    //初始时，队头、队尾指针指向0
    Q.rear=Q.front=0;
}

判断队列是否为空，可用Q.rear==Q.front来判断。

入队

只能从队尾入队（插入）。（循环队列）

bool EnQueue(SqQueue &Q,ElemType x)
{
    if(Q.size == MaxSize)		//队列已满
        return false;
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;	//队尾指针＋1取模
    return true;
}

出队

//删除一个队头元素，并用x返回
bool DeQueue(SqQueue &Q,ElemType &x)
{
    if(Q.rear==Q.front)		//判断队空
        return false;
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

获得队头元素的值的操作：

//获得队头元素的值，用x返回
bool GetHead(SqQueue &Q,ElemType &x)
{
    if(Q.rear == Q.front)
		return false;    //队空则报错
    x = Q.data[Q.front];
    return true;
}

队列已满的条件：队尾指针的再下一个位置是队头，即(Q.rear+1)%MaxSize==Q.front。

队列的元素个数=(rear-front+MaxSize)%MaxSize。

对于判空、判满的方法，另有下列2个方案：

方案2：引入一个变量int size作为保存队列的当前长度，当size==MaxSize时，队列满。

方案3：判断队列已满/已空

每次删除操作成功时，都令tag=0；每次插入操作成功时，都令tag=1。

逻辑：只有删除操作，才可能导致队空；只有插入操作，才可能导致队满。

队空条件：front==rear&&tag==0；

队满条件：front==rear&&tag==1。

3.2.2 链式存储结构

typedef struct LinkNode
{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct
{
    LinkNode *front,*rear;		//队列的队头和队尾指针
}LinkQueue;

入队

新元素连接到的是队列尾部。

带头结点：

void EnQueue(LinkQueue &Q,ElemType x)
{
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s;		//新结点插入到rear之后
    Q.rear=s;			//修改表尾指针
}

不带头结点：

void EnQueue(LinkQueue &Q,ElemType x)
{
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    if(Q.front==NULL)	//修改front和rear的指向
    {
        Q.front=s;
        Q.rear=s;
    }
    else
    {
        Q.rear->next=s;
        Q.rear=s;
    }
}

出队

带头结点：

bool DeQueue(LinkQueue &Q, ElemType &x)
{
	if (Q.front == Q.rear)
		return false;
	LinkNode *p = Q.front->next;	//用变量x返回队头元素
	x = p->data;
	Q.front->next = p->next;		//修改头结点的next指针
	if (Q.rear == p)				//本次是最后一个结点出队
		Q.rear = Q.front;
	free(p);
	return true;
}

不带头结点：则LinkNode *p=Q.front;，即p是队列的队头。

3.3 栈的应用

3.3.1 栈在括号匹配中的应用

原则

遇到左括号就入栈；遇到右括号，就“消耗”一个左括号。当发现当前扫描到的右括号与栈顶左括号不匹配，则本次扫描失败。

算法实现

需要用到的函数如下：

//初始化栈
void InitStack(SqStack &S);
//判断栈是否为空
bool StackEmpty(SqStack S);
//新元素入栈
bool Push(SqStack &S, char x);
//栈顶元素出栈，用x返回
bool Pop(SqStack &S, char &x);

代码如下：

#define MaxSize 10
typedef struct
{
	char data[MaxSize];
	int top;
}SqStack;
bool bracketCheck(char str[], int length)
{
	SqStack S;
	InitStack(S);		//初始化一个栈
	for (int i = 0;i < length;i++)
	{
		if (str[i] == '(' || str[i] == '[' || str[i] == '{')
			Push(S, str[i]);	//扫描到左括号，入栈
		else
		{
			if (StackEmpty(S))	//扫描到右括号，且当前栈空
				return false;
			char topElem;
			Pop(S, topElem);	//栈顶元素出栈
			if (str[i] == ')' && topElem != '(')
				return false;
			if (str[i] == ']' && topElem != '[')
				return false;
			if (str[i] == '}' && topElem != '{')
				return false;
		}
	}
	return StackEmpty(S);	//检索完全部括号后，栈空则说明匹配成功
}

3.3.2 栈在表达式求值中的应用

3.3.2.1 相关表达式的定义

波兰表达式（前缀表达式）、逆波兰表达式（后缀表达式）。

前缀表达式：运算符在两个操作数前面，如+ab,-+abc,-+ab*cd；

中缀表达式：运算符在两个操作数之间，如a+b,a+b-c,a+b-c*d；

后缀表达式：运算符在两个操作数后面，如ab+,ab+c-(或abc-+),ab+cd*-。

3.3.2.2 中缀表达式转后缀表达式

手算

（1）确定中缀表达式中各个运算符的运算顺序；

（2）选择下一个运算符，按照【左操作数右操作数运算符】的方式组合成一个新的操作数；

（3）如果还有运算符没被处理，就继续步骤2。

【注】”左优先”原则：只要左边的运算符能先计算，就优先算左边的。（可保证运算顺序唯一）

机算

从左到右处理各个元素，直到末尾。可能遇到以下三种情况：

（1）遇到操作数：直接加入后缀表达式。

（2）遇到界限符：遇到”(“直接入栈；遇到”)”则依次弹出栈内运算符并加入后缀表达式，直到弹出”(“为止。（注：”(“不加入后缀表达式）

（3）遇到运算符：依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到”(“或栈空则停止。之后再把当前运算符入栈。

3.3.2.3 用栈实现表达式的计算

后缀表达式的计算

（1）从左到右扫描下一个元素，直到处理完所有元素；

（2）若扫描到操作数则压入栈，并回到（1），否则执行（3）；

（3）若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到（1）。

中缀表达式的计算

初始化两个栈，操作数栈和运算符栈。

若扫描到操作数，压入操作数栈；

若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）。

3.3.3 栈在递归中的应用

函数调用时，需要用一个栈存储调用返回地址、实参、局部变量。

3.4 队列的应用

树的层次遍历、图的广度优先遍历、队伍在操作系统中的应用。

队伍在操作系统中的应用：

多个进程争抢着使用有限的系统资源时，FCFS（First Come First Service，先来先服务）是一种常用的策略。

例：CPU资源的分配，一台打印机打印论文（使用缓冲区，可用“队列”组织打印数据，可缓解主机与打印机速度不匹配的问题）。

ch4.字符串

4.1 字符串的定义与基本操作

4.1.1 字符串的定义

字符串，即是由零个或多个字符组成的有限序列，一般记为S='a1a2…an'(n>=0)。

其中，S是串名，单引号括起来的字符序列是串的值，ai可以是字母、数字或其他字符；串中字符的个数n称为串的长度，n=0时的串称为空串。

例：S="HelloWorld!"(Java、C为双引号) T='iPhone 11 pro max?'(Python为单引号)

子串：串中任意个连续的字符组成的子序列。主串：包含子串的串。

字符在主串中的位置：字符在串中的序号。

4.1.2 字符串的基本操作

在对字符串的基本操作中，通常以“串的整体”作为操作对象。如在字符串中查找某一子串、在串的某个位置上插入一个子串及删除一个子串等。

比较操作StrCompare(S,T)：从最左开始一个一个比较ASCII的值，一旦某字符比出大小，就停止。

长串的前缀与短串相同时，长串更大。

//比较操作。若S>T,则返回值>0;若S=T,则返回值=0；若S<T,则返回值<0
int StrCompare(SString S,SString T)
{
    for(int i=1;i<=S.length && i<=T.length;i++)
    {
        if(S.ch[i]!=T.ch[i])
            return S.ch[i]-T.ch[i];
    }
    //扫描过的所有字符都相同，则长度长的串更大
    return S.length-T.length;
}

定位操作Index(S,T)：在主串S的第pos个字符后找到与T相等的子串，并返回该子串第一个字符在S中的位置。

int Index(String S, String T, int pos) {
    if (pos > 0){
        n = StrLength(S);
        m = StrLength(T);
        i = pos;
        while (i <= n-m+1){
          SubString(&sub, S, i, m);
          if (StrCompare(sub,T) != 0)
              ++i ;
          else
              return i;
        } 
    }
    return 0;
}

4.2 字符串的存储结构

4.2.1 顺序存储

4.2.1.1 定长存储

#define MAXSTRING 255
    typedef unsigned char SString[MAXSTRLEN +1];		//0号单元存放字符串的长度 
SString s;
S[0] = 0;

4.2.1.2 堆分配存储表示

仍以一组地址连续的存储单元存放串值字符序列，但存储空间是动态分配的；存储成功，则返回一个指向起始地址的指针。

typedef struct{
    char *ch;
    int length;		//串长,无需像第一种方式需在0号单元存长度
}HString;

void StrAssign(HString *str, char *chars) {
	char *p = chars;
	int	 length, i;
	if(str->ch)
	{
        /* free space */
		free(str->ch);
		str->ch = NULL;
		str->length = 0;
	}
	/* compute length */
	while(*p++);
	length = p - chars - 1;
	if(length == 0)
		str->length = 0;
	else{
        /* apply for space */
		str->length = length;
		str->ch = (char *)malloc(sizeof(char)*length);
		assert(str->ch);//ensure 
		for(i=0; i<length; i++)
			str->ch[i] = chars[i];
	}
}

4.2.1.3 索引顺序存储

typedef struct
{ 
   char name[maxsize];
   int length;
   char *staaddr;		//起始指针,还可添加尾指针
}LNode;

4.2.2 链式存储

4.2.2.1 单链存储

typedef struct StringNode
{
    char ch;		//每个结点存1个字符
    string StringNode *next;
}StringNode,*String;

该存储结构存储密度低，每个字符1B，每个指针4B。

注：存储密度=串值所占的存储位/实际分配的存储位。

4.2.2.2 块链存储

#define CHUNKSIZE 80		//块的大小由用户定义
typedef struct Chunk {		//定义块
	char ch[CHUNKSIZE];
    struct Chunk *next;
}Chunk;
typedef struct{
  Chunk *head, *tail;   //串的头尾指针
  int curlen; 			//串的当前长度
}LString;

该存储结构存储密度提高。

4.3 字符串的模式匹配

模式匹配算法问题主要由模式串决定。

4.3.1 朴素模式匹配算法

字符串模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置。

朴素模式匹配算法：将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止。（最多对比n-m+1个子串）（Index定位操作即朴素模式匹配算法）

通过数组下标实现朴素模式匹配算法：

int Index(SString S,SString T)
{
    int i=1,j=1;
    while(i<=S.length && j<=T.length)
    {
        if(S.ch[i]==T.ch[j])
        {
            i++;j++;	//继续比较后继字符
        }
        else
        {
            i=i-j+2;	//指向下一个子串的起始位置
            j=1;		//指针后退重新开始匹配
        }
        if(j>T.length)
            return i-T.length;
        else 
            return 0;
    }
}

设主串长度为n，模式串长度为m，则最坏时间复杂度=O(nm)，最好时间复杂度=O(n)。

最坏时间复杂度：每次均为匹配到模式串最后一个字母时发现匹配失败。

在最坏的情况中，每个子串都要对比m个字符，共n-m+1个子串，复杂度=O((n-m+1)m)=O(nm)。（注：很多时候，n远大于m）

在最好的情况中，每个子串的第一个字符就匹配失败，共n-m+1个子串，复杂度=O(n-m+1)=O(n)。

4.3.2 KMP算法

4.3.2.1 算法分析

算法精髓：利用好已经匹配过的模式串的信息。

Assuming s:

s1, s2…si-j+1…si-k+1, si-k+2…si-1,si,s1+i …sn

Pattern string p:

p1,p2…pj-k,pj-k+1,…,pk-1,pk,…,pj-1,pj,…,pm

Si compare with pk ：

“p1p2,…pk-1”=”si-k+1si-k+2,…si-1”

Si compare with pj，：

“p1p2…pj-k+1…pj-1”=”si-j+1,si-j+2…si-1“

Because k<j：

“pj-k+1pj-k+2…pj-1”=”si-k+1si-k+2,…si-1”

So ：“p1p2,…pk-1”=“pj-k+1pj-k+2…pj-1”

int Index_KMP((SString S,SString T,int next[]))
{
    int i=1,j=1;
    while(i <= S.length && j <= T.length)
    {
        if(j == 0 || S.ch[i] == T.ch[j])
        {
            i++;j++;		    //继续比较后继字符
        }
        else
            j = next[j];		//模式串向右移动,i保持不变
        if(j > T.length)
            return i - T.length;
        else
            return 0;
    }
}

KMP算法的最坏时间复杂度为O(m+n)，其中，求next数组时间复杂度O(m)，模式匹配过程最坏时间复杂度O(n)。

4.3.2.2 求next数组

next数组的作用：当模式串的第j个字符失配时，从模式串的第next[j]个继续往后匹配。

next[1]、next[2]在任何情况下均分别为0、1。对于其他的next，在不匹配的位置前，划一条分界线。模式串一步一步往后退，直到分界线之前“能对上”，或模式串完全跨过分界线为止。此时j指向哪，next数组值就是多少。

另一种方法是，当此集合不空，且j不等于1时，next[j]即第j个元素前j-1个元素首尾重合部分个数再加一。

代码逻辑：

如果$P_{j} \neq P_{\text {next }[j]} $，那么$next[j+1]$可能的次大值为$next[next[j]]+1$ ，以此类推即可高效求出$next [j+1]$。

//通过计算返回子串T的next数组
void get_next(SString T,int *next)
{
    int i,k;
    i=1,k=0;
    next[1]=0;
    while(i<T[0])
    {
        if(k==0||T[i]==T[k])
        {
            i++;
            k++;
            next[i]=k;
        }
        else
            k=next[k];		//r
    }
}

4.3.2.3 求nextval数组

例如： ‘aaaab’，有 $next[j]= 01234, nextval[j]=00004$。

void get_nextval(SString &P, int &nextval[])
 {
i = 1; j = 0;
 nextval[1] = 0;
 while (i < P[0]) 
{
    if (j == 0 || P[i] == P[j])
    {
       ++i; ++j;
       if (P[i] != P[j]) 
           nextval[i] = j;
      else nextval[i] = nextval[j];
     }
  else j = nextval[j];
}//while
} // get_nextval

ch5.广义表、数组和矩阵

5.1 广义表

5.1.1 逻辑结构

广义表即”表中有表“，记作$LS=(\alpha_{1},\alpha_{2},…,\alpha_{n})$，n为其长度，$\alpha_{i}$可以为单个元素，也可以为广义表，分别称广义表LS的原子和子表。当广义表非空时，称第一个元素$\alpha_{1}$为LS的表头（Head），其余元素组成的表$(\alpha_{2},\alpha_{3},…,\alpha_{n})$是LS的表尾（Tail）。

注意：

每次取表尾就是构建广义表的过程，如D=(A,B,C),GetTail(D)=(B,C),GetTail((B,C))=(C).

广义表的长度为表中最上层元素的个数，而广义表的深度为表中括号的最大层数。求深度时，可将子表展开，如某广义表可以展开为$((d,e),(b,(c,d)))$，则深度为3。

5.1.2 存储结构

广义表中的数据元素可以为原子或列表，表结点由三个域构成：标志域（tag=1）、指示表头的指针域和指示表尾的指针域，原子结点由三个域构成：标志域（tag=0）、值域。

5.2 数组的表示

对数组：

a11	a12	……	a1n
a21	a22	……	a2n
……	……	……	……
am1	am2	……	amn

以行为主序：$Loc(a_{ij})=Loc(a_{11})+[(i-1)n+(j-1)]*l$（l为每个单元的字节数)；

以列为主序：$Loc(a_{ij})=Loc(a_{11})+[(j-1)m+(i-1)]*l$（l为每个单元的字节数）。

5.3 结构化稀疏矩阵的存储

5.3.1 下三角矩阵

5.3.2 对称矩阵

5.4 稀疏矩阵的存储表示

5.4.1 三元组表

稀疏矩阵由非零元的三元组及其行列数唯一确定。其中，行列数可以单独设置变量，也可以直接用零号单元进行存储（转置运算例子采用零号单元存储）。

//稀疏矩阵的三元组顺序表存储表示
typedef struct{
    int i,j;		//非零元的行下标和列下标
    ElemType e;
}Triple;
typedef struct{
    Triple data[MaxSize+1];
    int mu,nu,tu;	//矩阵的行数、列数和非零元个数，也可以直接存在data[0]中
}TSMatrix;

5.4.2 重要实例：稀疏矩阵的转置运算

方法1：将矩阵的行列值相互交换，然后排序。其时间复杂度为$O(n^{2}+nlogn)$。

方法2：遍历三元组表，找到$j_{min}$（列优先），互换后得到三元组表。每次遍历的时候，从$column=1$开始（$column=1,2,…,n$），将符合条件的进入新三元组表中。其时间复杂度为$O(N_{u}*t_{u})$（$N_{u}$为列数，$t_{u}$为非零元个数）。这个方法的缺点在于反复搜索。

方法3：实现：设两个数组

$num[col]$：表示矩阵$M$中第$col$列中非零元个数

$cpot[col]$：指示$M$中第$col$列第一个非零元在$mb$中位置

显然有：

$cpot[1]=1;$
$cpot[col]=cpot[col-1]+num[col-1]; (2\leq col \leq ma[0].cols)$

每次保存到新三元组表中后，将$cpot[col]$进行自增。其算法的时间复杂度为$O(N_{u}+t_{u})$（$N_{u}$为列数，$t_{u}$为非零元个数）。该算法以空间换时间。

5.4.3 行/列逻辑链表

5.4.3.1 单向链表表示

5.4.3.2 带行指针向量的单向链表

每行的非零元用一个单链表存放；

设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空。需存储单元个数为3t+m（t为非零元素个数，m为行数）。

typedef    struct node
{    int  col;
      int  val;
      struct node  *link;
}RNode;
typedef  struct  node   *TD;

5.4.4 十字链表

设行指针数组和列指针数组，分别指向每行、列第一个非零元。结点定义如下：

typedef  struct Node
{     
    int  row,col,val;
    struct Node *down, *right;
}OLNode;

ShiQuLiZhi

https://www.qqzzss.top/2022/08/23/ds-algorithm/shu-ju-jie-gou-01-shu-ju-jie-gou-1/

本博客所有文章除特别声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 ShiQuLiZhi !

算法数据结构

数据结构2:树与图

2022-08-23 数据结构与算法课程

算法数据结构

Python数据处理:数据分析处理库Pandas

2022-08-16 Python与数据处理

程序设计 Python 数据处理

数据结构1:线性表,栈,队列,字符串,广义表,数组

ch1.绪论

1.1 数据结构相关概念

1.2 数据结构的三要素

1.2.1 逻辑结构

1.2.2 数据的运算

1.2.3 物理结构（存储结构）

1.3 算法效率的度量

1.3.1 算法时间复杂度

1.3.2 算法空间复杂度

1.4 C语言相关重点知识回顾

1.4.1 结构体

1.4.2 值回传方法

ch2.线性表

2.1 线性表的定义与ADT

2.1.1 线性表的定义

2.1.2 集合的并运算与元素剔除

2.1.3 合并(Merge)有序序列

2.2 顺序表

2.2.1 静态分配

2.2.2 动态分配

2.2.3 基本操作

2.3 单链表

2.3.1 单链表的定义

2.3.2 头结点的使用与单链表初始化

2.3.2.1 头结点的使用

2.3.2.2 初始化空表

2.3.2.3 初始化带有元素的表

2.3.3 插入操作

2.3.3.1 按位序插入和后插操作

2.3.3.2 前插操作

2.3.4 删除操作

2.4 双向链表

2.4.1 初始化

2.4.2 插入操作

2.4.3 删除操作

2.4.4 遍历

2.5 循环链表

2.6 静态链表

2.6.1 定义静态链表

2.6.2 基本操作

ch3.栈和队列

3.1 栈

3.1.1 顺序栈的定义和基本操作

3.1.2 共享栈

3.1.3 栈的链式存储结构

3.2 队列

3.2.1 顺序存储结构

3.2.2 链式存储结构

3.3 栈的应用

3.3.1 栈在括号匹配中的应用

3.3.2 栈在表达式求值中的应用

3.3.2.1 相关表达式的定义

3.3.2.2 中缀表达式转后缀表达式

3.3.2.3 用栈实现表达式的计算

3.3.3 栈在递归中的应用

3.4 队列的应用

ch4.字符串

4.1 字符串的定义与基本操作

4.1.1 字符串的定义

4.1.2 字符串的基本操作

4.2 字符串的存储结构

4.2.1 顺序存储

4.2.1.1 定长存储

4.2.1.2 堆分配存储表示

4.2.1.3 索引顺序存储

4.2.2 链式存储

4.2.2.1 单链存储

4.2.2.2 块链存储

4.3 字符串的模式匹配

4.3.1 朴素模式匹配算法

4.3.2 KMP算法

4.3.2.1 算法分析

4.3.2.2 求next数组

4.3.2.3 求nextval数组

ch5.广义表、数组和矩阵

5.1 广义表

5.1.1 逻辑结构

5.1.2 存储结构

5.2 数组的表示