浙大 陈越何钦铭老师的数据结构课程学习
数据结构目前并没有一个官方定义，但是数据结构与算法往往是联系在一起的。
我们解决一个实际的问题的效率，与数据的组织方式有关，与空间的利用效率有关，与算法的巧妙程度也有关。（例如递归往往看起来清晰易懂，但是空间占用很高）
数据结构可以解释为数据对象在计算机中的组织方式（逻辑结构与物理存储结构），数据对象的组织形式一定是与一系列加在它身上的操作所相关联的，完成这些操作的方法我们就称为算法。
ADT（抽象数据类型）
数据类型是指数据对象集，数据集合相关联的操作集。
抽象是指描述数据类型的方法与操作并不依赖与具体实现，与机器与实现操作的算法和编程语言均无关。
那什么又是算法呢？
一个有限的指令集，可以接受一些输入（或者无输入），产生输出，并且一定是在有限步骤之后终止，每一条指令都必须有充分明确的目标，不可以有歧义，在计算机的处理范围之内，描述不应该依赖于某一种计算机语言以及十分具体的实现手段（例如规定是数组还是链表呀，或者函数是自定义还是宏，这些不应当是算法所考虑的问题）。
算法的评判标准：
（1）空间复杂度，考察算法写成的程序在执行时占用的存储单元的长度。
（2）时间复杂度，考察算法写成的程序在执行时耗费时间的长短。
针对上面的两个复杂度，一般情况下，我们关注算法的两种复杂度形式，一是最坏情况复杂度，二是平均复杂度。尽量不要出现一个n平方或立方的程序，因为n2或n3会出现指数爆炸增长，时间很恐怖，有生之年系列。
例如一个最大子序和问题就会存在三种解法：（1）暴力解法 n的平方（2）分治算法 nlog（n）（3）动态规划 n。时间差距很大。
分治算法的程序如下：
int Max3( int A, int B, int C )
{ /* 返回3个整数中的最大值 */
return A > B ? A > C ? A : C : B > C ? B : C;
}
int DivideAndConquer( int List[], int left, int right )
{ /* 分治法求List[left]到List[right]的最大子列和 */
int MaxLeftSum, MaxRightSum; /* 存放左右子问题的解 */
int MaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界线的结果*/
int LeftBorderSum, RightBorderSum;
int center, i;
if( left == right ) { /* 递归的终止条件，子列只有1个数字 */
if( List[left] > 0 ) return List[left];
else return 0;
}
/* 下面是"分"的过程 */
center = ( left + right ) / 2; /* 找到中分点 */
/* 递归求得两边子列的最大和 */
MaxLeftSum = DivideAndConquer( List, left, center );
MaxRightSum = DivideAndConquer( List, center+1, right );
/* 下面求跨分界线的最大子列和 */
MaxLeftBorderSum = 0; LeftBorderSum = 0;
for( i=center; i>=left; i-- ) { /* 从中线向左扫描 */
LeftBorderSum += List[i];
if( LeftBorderSum > MaxLeftBorderSum )
MaxLeftBorderSum = LeftBorderSum;
} /* 左边扫描结束 */
MaxRightBorderSum = 0; RightBorderSum = 0;
for( i=center+1; i<=right; i++ ) { /* 从中线向右扫描 */
RightBorderSum += List[i];
if( RightBorderSum > MaxRightBorderSum )
MaxRightBorderSum = RightBorderSum;
} /* 右边扫描结束 */
/* 下面返回"治"的结果 */
return Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );
}
int MaxSubseqSum3( int List[], int N )
{ /* 保持与前2种算法相同的函数接口 */
return DivideAndConquer( List, 0, N-1 );
}
什么是线性表：
它的定义是由同类型的数据元素构成的有序序列的线性结构，表中元素的个数称为其长度，没有元素时为空表，表起始位置称为表头，表的结束位置称为表尾。
（1）顺序存储结构，利用数组的连续存储空间顺序存放线性表的元素。
（2）链表结构，不要求在逻辑上相邻的两个元素在物理上也相邻，通过链建立起了数据元素之间的逻辑关系。插入和删除操作不需要移动数据元素，只需要修改链。
广义表
（1）多重链表
多重链表：链表中的节点可能同时隶属于多个链，多重链表中结点的指针域会有多个，如前面例子包含了Next和SubList两个指针域；但包含两个指针域的链表并不一定是多重链表，比如在双向链表不是多重链表。
多重链表有广泛的用途：基本上如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储。
顺序存储代码如下：
typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last;
};
/* 初始化 */
List MakeEmpty()
{
List L;
L = (List)malloc(sizeof(struct LNode));
L->Last = -1;
return L;
}
/* 查找 */
#define ERROR -1
Position Find( List L, ElementType X )
{
Position i = 0;
while( i <= L->Last && L->Data[i]!= X )
i++;
if ( i > L->Last ) return ERROR; /* 如果没找到，返回错误信息 */
else return i; /* 找到后返回的是存储位置 */
}
/* 插入 */
/*注意:在插入位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是存储下标位置（从0开始），两者差1*/
bool Insert( List L, ElementType X, Position P )
{ /* 在L的指定位置P前插入一个新元素X */
Position i;
if ( L->Last == MAXSIZE-1) {
/* 表空间已满，不能插入 */
printf("表满");
return false;
}
if ( P<0 || P>L->Last+1 ) { /* 检查插入位置的合法性 */
printf("位置不合法");
return false;
}
for( i=L->Last; i>=P; i-- )
L->Data[i+1] = L->Data[i]; /* 将位置P及以后的元素顺序向后移动 */
L->Data[P] = X; /* 新元素插入 */
L->Last++; /* Last仍指向最后元素 */
return true;
}
/* 删除 */
/*注意:在删除位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是存储下标位置（从0开始），两者差1*/
bool Delete( List L, Position P )
{ /* 从L中删除指定位置P的元素 */
Position i;
if( P<0 || P>L->Last ) { /* 检查空表及删除位置的合法性 */
printf("位置%d不存在元素", P );
return false;
}
for( i=P+1; i<=L->Last; i++ )
L->Data[i-1] = L->Data[i]; /* 将位置P+1及以后的元素顺序向前移动 */
L->Last--; /* Last仍指向最后元素 */
return true;
}
链式存储代码如下：
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;//PtrToLNode是指针吧？
/* 查找 */
#define ERROR NULL
Position Find( List L, ElementType X )
{
Position p = L; /* p指向L的第1个结点 */
while ( p && p->Data!=X )
p = p->Next;
/* 下列语句可以用 return p; 替换 */
if ( p )
return p;
else
return ERROR;
}
/* 带头结点的插入 */
/*注意:在插入位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是链表结点指针，在P之前插入新结点 */
bool Insert( List L, ElementType X, Position P )
{ /* 这里默认L有头结点 */
Position tmp, pre;
/* 查找P的前一个结点 */
for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;
if ( pre==NULL ) { /* P所指的结点不在L中 */
printf("插入位置参数错误\n");
return false;
}
else { /* 找到了P的前一个结点pre */
/* 在P前插入新结点 */
tmp = (Position)malloc(sizeof(struct LNode)); /* 申请、填装结点 */
tmp->Data = X;
tmp->Next = P;
pre->Next = tmp;
return true;
}
}
/* 带头结点的删除 */
/*注意:在删除位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是拟删除结点指针 */
bool Delete( List L, Position P )
{ /* 这里默认L有头结点 */
Position tmp, pre;
/* 查找P的前一个结点 */
for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;
if ( pre==NULL || P==NULL) { /* P所指的结点不在L中 */
printf("删除位置参数错误\n");
return false;
}
else { /* 找到了P的前一个结点pre */
/* 将P位置的结点删除 */
pre->Next = P->Next;
free(P);
return true;
}
}
通过对比上述两端代码，我们可以明确发现，链式存储在插入和删除时不需要移动其它的元素，但是需要挨个查找元素，各有千秋。
什么是堆栈？
我们需要某种特定的存储方式，能够实现顺序存储运算数，但是倒序输出。抽象表现形式就是具有一定的操作约束的线性表，只能在一端进行插入删除操作，属于一个后入先出（last in first out）。我们可以采用链表来实现这一数据结构，其实就是一个单链表，然后将表头设置为链栈的尾部。栈在很多方面都有利用：函数的调用以及递归实现、深度优先搜索、回溯算法。
分别尝试利用顺序存储和链式存储实现堆栈。
（1）顺序存储
typedef int Position;
struct SNode {
ElementType *Data; /* 存储元素的数组 */
Position Top; /* 栈顶指针 */
int MaxSize; /* 堆栈最大容量 */
};
typedef struct SNode *Stack;
Stack CreateStack( int MaxSize )
{
Stack S = (Stack)malloc(sizeof(struct SNode));
S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
S->Top = -1;
S->MaxSize = MaxSize;
return S;
}
bool IsFull( Stack S )
{
return (S->Top == S->MaxSize-1);
}
bool Push( Stack S, ElementType X )
{
if ( IsFull(S) ) {
printf("堆栈满");
return false;
}
else {
S->Data[++(S->Top)] = X;
return true;
}
}
bool IsEmpty( Stack S )
{
return (S->Top == -1);
}
ElementType Pop( Stack S )
{
if ( IsEmpty(S) ) {
printf("堆栈空");
return ERROR; /* ERROR是ElementType的特殊值，标志错误 */
}
else
return ( S->Data[(S->Top)--] );
}
（2）链式存储
typedef struct SNode *PtrToSNode;
struct SNode {
ElementType Data;
PtrToSNode Next;
};
typedef PtrToSNode Stack;
Stack CreateStack( )
{ /* 构建一个堆栈的头结点，返回该结点指针 */
Stack S;
S = (Stack)malloc(sizeof(struct SNode));
S->Next = NULL;
return S;
}
bool IsEmpty ( Stack S )
{ /* 判断堆栈S是否为空，若是返回true；否则返回false */
return ( S->Next == NULL );
}
bool Push( Stack S, ElementType X )
{ /* 将元素X压入堆栈S */
PtrToSNode TmpCell;
TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));
TmpCell->Data = X;
TmpCell->Next = S->Next;
S->Next = TmpCell;
return true;
}
ElementType Pop( Stack S )
{ /* 删除并返回堆栈S的栈顶元素 */
PtrToSNode FirstCell;
ElementType TopElem;
if( IsEmpty(S) ) {
printf("堆栈空");
return ERROR;
}
else {
FirstCell = S->Next;
TopElem = FirstCell->Data;
S->Next = FirstCell->Next;
free(FirstCell);
return TopElem;
}
}
什么是队列？
队列和堆栈有点类似，都是具有一定操作约束的线性表，但是也有不同，插入只能在一段插入，而在另一端删除。队列也有顺序存储和链式存储两种方式，不过不同的是，队列需要两个变量，一个记录头元素位置的变量front以及一个记录尾元素位置的变量rear。顺序存储，因为队列的特殊性，所以可以通过程序将物理上不是环形的队列构成逻辑上环形的队列。链式存储，依然还是依靠单链表进行存储。
（1）顺序存储
typedef int Position;
struct QNode {
ElementType *Data; /* 存储元素的数组 */
Position Front, Rear; /* 队列的头、尾指针 */
int MaxSize; /* 队列最大容量 */
};
typedef struct QNode *Queue;
Queue CreateQueue( int MaxSize )
{
Queue Q = (Queue)malloc(sizeof(struct QNode));
Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
Q->Front = Q->Rear = 0;
Q->MaxSize = MaxSize;
return Q;
}
bool IsFull( Queue Q )
{
return ((Q->Rear+1)%Q->MaxSize == Q->Front);
}
bool AddQ( Queue Q, ElementType X )
{
if ( IsFull(Q) ) {
printf("队列满");
return false;
}
else {
Q->Rear = (Q->Rear+1)%Q->MaxSize;//由此可见，留了一个空位。
Q->Data[Q->Rear] = X;
return true;
}
}
bool IsEmpty( Queue Q )
{
return (Q->Front == Q->Rear);
}
ElementType DeleteQ( Queue Q )
{
if ( IsEmpty(Q) ) {
printf("队列空");
return ERROR;
}
else {
Q->Front =(Q->Front+1)%Q->MaxSize;//front指向的是第一个空的位置，这个位置后面跟着第一个元素。。
return Q->Data[Q->Front];
}
}
（2）链式存储
typedef struct Node *PtrToNode;
struct Node { /* 队列中的结点 */
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode Position;
struct QNode {
Position Front, Rear; /* 队列的头、尾指针 */
int MaxSize; /* 队列最大容量 */
};
typedef struct QNode *Queue;
bool IsEmpty( Queue Q )
{
return ( Q->Front == NULL);
}
ElementType DeleteQ( Queue Q )
{
Position FrontCell;
ElementType FrontElem;
if ( IsEmpty(Q) ) {
printf("队列空");
return ERROR;
}
else {
FrontCell = Q->Front;
if ( Q->Front == Q->Rear ) /* 若队列只有一个元素 */
Q->Front = Q->Rear = NULL; /* 删除后队列置为空 */
else
Q->Front = Q->Front->Next;
FrontElem = FrontCell->Data;
free( FrontCell ); /* 释放被删除结点空间 */
return FrontElem;
}
}
int AddQ( Queue Q, ElementType X )
{
Position FrontCell=(Position)malloc(sizeof(struct Node));
FrontCell->Data=X;
FrontCell->Next=NULL;
if(IsEmpty(Q))
{
Q->Front=Q->Rear=FrontCell;
Q->Rear=Q->Rear->Next;
}
else
{
Q->Rear->Next=FrontCell;
Q->Rear=Q->Rear->Next;
}
return 1;
}
int main()
{
int m;
Queue Q=(Queue)malloc(sizeof(struct QNode));
Q->Front = Q->Rear = NULL;
AddQ(Q,45);
m=DeleteQ(Q);
printf("%d ",m);
AddQ(Q,453);
m=DeleteQ(Q);
printf("%d ",m);
AddQ(Q,451);
m=DeleteQ(Q);
printf("%d ",m);
AddQ(Q,425);
m=DeleteQ(Q);
printf("%d ",m);
m=DeleteQ(Q);
printf("%d ",m);
system("pause");
return 0;
}
输出结果如下图所示：