数据结构讲义

基本概念

• 空间使用
  函数PrintN，使得传入一个正整数为N的参数后，打印从1到N的全部正整数。

// 方法一：循环实现
void PrintN_1(int N)
{
    for (int i=N; i>=0; i--)
    {
        printf("%d\n", i);
    }
    return;
}
// 方法二：递归实现
void PrintN(int N)
{
    if (N)
    {
        PrintN(N - 1);
        printf("%d\n", N);
    }
    return;
}

• 算法效率
  多项式 f(x) = a0 + a1*x^1 +… +an * x^n

// 方法一
double f1(int n, double a[], double x)
{
    int i;
    double p = a[0];
    for (i = 1; i <= n; i++)
    {
        p += (a[i] * pow(x, i));
    }
    return p;
}
// 方法二
double f2(int n, double a[], double x)
{
    int i;
    double p = a[n];
    for (i = n; i > 0; i--){
        p = a[i - 1] + x * p;  // f(x) = a0+ x(a1+x(...(an-1 + x(an))...))
    }
    return p;
}

计时
CLK_TCK 为常数，机器始终每秒所走的打点数 Use CLOCKS_PER_SEC instead of CLK_TCK on mac
include <time.h>

#include <stdio.h>
#include <time.h>
#include <math.h>
#define MAXN 10 // 9阶多项式的最大项数

clock_t start, stop;  //clock()返回的变量类型是 clock_t
double duration;  //秒
double f1(int n, double a[], double x);
double f2(int n, double a[], double x);

int main(int argc, char const *argv[])
{
	int i;
	double a[MAXN];
	for(i=0; i<MAXN; i++) a[i] = (double)i;  // 假定每一项系数就是i

	start = clock();
	f1(MAXN-1, a, 1.1); // 假定 x=1.1
	stop = clock();
	duration = (double)(stop -  start)/CLOCKS_PER_SEC; 
	printf("ticks1 = %f\n", (double)(stop -  start));
	printf("duration1 = %6.2e\n", duration);

	start = clock();
	f2(MAXN-1, a, 1.1); // 假定 x=1.1
	stop = clock();
	duration = (double)(stop -  start)/CLOCKS_PER_SEC;
	printf("ticks2 = %f\n", (double)(stop -  start));
	printf("duration2 = %6.2e\n", duration);  // 要占6位，小数点后2位，以e指数的形式输出

	return 0;
}

double f1(int n, double a[], double x){
    int i;
    double p = a[0];
    for (i = 1; i <= n; i++)
    {
        p += (a[i] * pow(x, i));
    }
    return p;
}

double f2(int n, double a[], double x){
    int i;
    double p = a[n];
    for (i = n; i > 0; i--){
        p = a[i - 1] + x * p;  // f(x) = a0+ x(a1+x(...(an-1 + x(an))...))
    }
    return p;
}

抽象数据类型 Abstract Data Type

数据类型，包含：数据对象集、数据集合相关联操作集。

抽象指，描述数据类型的方法不依赖于具体实现。 与存放数据的机器、物理结、编程语言构等无关。

• 类型名称：矩阵
• 数据对象集：M*N
• 操作集：…

算法

空间复杂度S(n)
时间复杂度T(n)
多项式算法一：
(1+2+3+…+n) = (n^2 + n) /2
T(n) = C1n^2 + c2n
方法二： T(n) = Cn

最坏情况负责度
平均复杂度

复杂度渐进表示
上界：T(n) = O(f(n)), 存在T(n) <= Cf(n)
下界： T(n) = Omega(g(n))， 存在T(n) >= Cg(n)

实例： 最大子列和问题

算法一：

举例{1,2,3,4}
sum = 1
sum = 1 + 2
sum = 1 + 2 + 3
sum = 1 + 2 + 3 + 4
sum = 2
sum = 2 + 3
sum = 2 + 3 + 4
sum = 3
sum = 3 + 4
sum = 4

int MaxSubseqSum1( int A[], int N )
{ 
	int ThisSum, MaxSum = 0;
	int i, j, k;
	for( i = 0; i < N; i++ ) 
    { 
		for( j = i; j < N; j++ ) 
        { 
			ThisSum = 0; 
			for( k = i; k <= j; k++ )
				ThisSum += A[k];
			if( ThisSum > MaxSum ) 
				MaxSum = ThisSum; 
		} 
	} 
	return MaxSum;
}

T(N) = O(N^3)

算法二, 去掉K这个循环

举例{1,2,3,4}
sum = 1
sum = sum_previous + 2
sum = sum_previous + 3
sum = sum_previous + 4
sum = 2
sum = sum_previous + 3
sum = sum_previous + 4
sum = 3
sum = sum_previous + 4
sum = 4

int MaxSubseqSum2( int A[], int N )
{ 
	int ThisSum, MaxSum = 0;
	int i, j;
	for( i = 0; i < N; i++ ) 
    {
		ThisSum = 0; 
		for( j = i; j < N; j++ ) 
		{ 
			ThisSum += A[j];
            if( ThisSum > MaxSum ) 
				MaxSum = ThisSum; 
		} 
	}  
	return MaxSum;
} 

T(N) = O(N^2)

算法三： 分而治之

T(N) = O(NlogN)

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 ) 
        { 
        	// printf("List[left]=%d\n", List[left]);
        	return List[left];
        }
        else return 0;
    }
 
    /* 下面是"分"的过程 */
    // printf("left=%d\n", left);
    // printf("right=%d\n", right);
    center = ( left + right ) / 2; /* 找到中分点 */
    // printf("center=%d\n", center);
    /* 递归求得两边子列的最大和 */
    MaxLeftSum = DivideAndConquer( List, left, center );
    // printf("MaxLeftSum=%d\n", MaxLeftSum);
    MaxRightSum = DivideAndConquer( List, center+1, right );
    // printf("MaxRightSum=%d\n", MaxRightSum);
 
    /* 下面求跨分界线的最大子列和 */
    MaxLeftBorderSum = 0; LeftBorderSum = 0;
    for( i=center; i>=left; i-- ) 
    { /* 从中线向左扫描 */
        LeftBorderSum += List[i];
        // printf("LeftBorderSum=%d\n", LeftBorderSum);
        if( LeftBorderSum > MaxLeftBorderSum )
        {
            MaxLeftBorderSum = LeftBorderSum;
            // printf("MaxLeftBorderSum=%d\n", MaxLeftBorderSum);
        }
    } /* 左边扫描结束 */
 
    MaxRightBorderSum = 0; RightBorderSum = 0;
    for( i=center+1; i<=right; i++ ) 
    { /* 从中线向右扫描 */
        RightBorderSum += List[i];
        // printf("RightBorderSum=%d\n", RightBorderSum);
        if( RightBorderSum > MaxRightBorderSum )
        {
            MaxRightBorderSum = RightBorderSum;
            // printf("MaxRightBorderSum=%d\n", MaxRightBorderSum);
        	
        }
            
    } /* 右边扫描结束 */
 
    /* 下面返回"治"的结果 */
    int Max = Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);
    // printf("Max=%d\n", Max);
    return Max;
}

int MaxSubseqSum3( int List[], int N )
{ /* 保持与前2种算法相同的函数接口 */
    return DivideAndConquer( List, 0, N-1 );
} 

算法四： 在线处理

每一个数据进行即时处理，在任何一个地方输入种植，都给出当前的解。

int MaxSubseqSum4( int A[], int N )
{ 
	int ThisSum, MaxSum;
	int i;
	ThisSum = MaxSum = 0;
	for( i = 0; i < N; i++ ) {
		ThisSum += A[i]; /* 向右累加 */ 
		if( ThisSum > MaxSum )
			MaxSum = ThisSum; /* 发现更大和则更新当前结果 */ 
		else if( ThisSum < 0 ) /* 如果当前子列和为负 */
			ThisSum = 0; /* 则不可能使后面的部分和增大，抛弃之 */ }
	return MaxSum;
}

线性结构

一元多项式

$$f(x) = a_0 + a_1x+…+a_nx$$

方法一：顺序存储结构直接表示
a[i]: 系数

方法二：顺序存储表示非零项
用结构数组表示：系数与指数的二元组

方法三：链表结构存储非零项
coef expon link;

typedef struct PolyNode *polynomial;
truct PolyNode{
   int coef;
   int expon;
   polynomial link;
}

线性表 Linear List

同类型数据元素构成有序序列的线性结构。
数据对象集：n个元素构成的有序序列
操作集：线性表L属于List, 整数表示位置，元素x属于ElementType。操作：

• List MakeEmpty(): 初始化一个空表
• ElementType FindKth(int K, List L); 根据位序K，返回相应元素
• int Find(ElementType x, List L); 在表中查找X第一次出现的位置
• void insert(ElementType X, int i, List L); 插入
• void Delete(int i, List l); 删除
• int length(List L); 返回长度

线性存储序列的实现

typedef struct LNode *List; 
struct LNode{
   ElementType Data[MAXSIZE];
   int Last; 
};
struct LNode L; 
List PtrL;

访问元素：L.Data[i] or PtrL->Data[i]
线性表的长度:L.Last+1 或 PtrL->Last+1 (last代表位置，因为从零开始所以是n-1)

• 初始化

List MakeEmpty( )
{
   List PtrL;
   PtrL = (List )malloc( sizeof(struct LNode) );  
   PtrL->Last = -1; //last若为0 则表示表里有一个元素在0号位置
   return PtrL;
}

• 查找

int Find( ElementType X, List PtrL ) { 
   int i = 0;
   while( i <= PtrL->Last && PtrL->Data[i]!= X ) 
      i++;
   if (i > PtrL->Last) return -1; 
   /* 如果没找到，返回-1(因破坏第一个条件而跳出循环) */
   else return i; /* 找到后返回的是存储位置 */ }
}

平均查找次数(n +1)/2，平均时间性能为 O(n)

• 插入
  第 i (1≤i≤n+1)个位置上插入一个值为X的新元素（其实是插在数组的第i-1个位置，因为数组从0开始标）先移动再插入，n挪到n+1，n-1挪到n, …，i-1挪到i
  在链表L中的第一个位置插入元素X，如下，MAXSIZE代表链表的size

void Insert( ElementType X, int i, List PtrL ) { 
   int j;
   /* 表空间已满，不能插入*/
   if ( PtrL->Last == MAXSIZE-1 )
   { 
      printf("表满");
      return; 
   }
   /*检查插入位置的合法性*/
   if ( i < 1 || i > PtrL->Last+2) 
   { 
      printf("位置不合法"); 
      return;
   }
   /* 开始挪位子，从最后的一位last开始直到i-1 */
   for ( j = PtrL->Last; j >= i-1; j-- )
      PtrL->Data[j+1] = PtrL->Data[j]; 
   
   PtrL->Data[i-1] = X; /*新元素插入*/ 
   PtrL->Last++; /*Last仍指向最后元素*/ 
   return;
}

平均移动次数为 n /2，
/检查插入位置的合法性/ 平均时间性能为 O(n)

• 删除
  删除第i个位置上的元素，i在1到n之间，对应数组下表0到n-1
  删掉下表为i-1的元素，下标i的元素挪到i-1…

void Delete( int i, List PtrL ) 
{ 
   intj;
   /*检查空表及删除位置的合法性*/
   if( i < 1 || i > PtrL->Last+1 ) 
   { 
   printf (“不存在第%d个元素”, i );
   return ; 
   }
   /*将 ai+1~ an顺序向前移动, 从第i位开始，到last */
   for ( j = i; j <= PtrL->Last; j++ ) 
      PtrL->Data[j-1] = PtrL->Data[j];
      
   PtrL->Last--; /*Last仍指向最后元素*/
   return; 
}

平均移动次数为 (n-1) /2
平均时间性能为 O(n)

链式存储的实现

一个线性表用数组存储的时候，相邻的元素不仅逻辑上不仅逻辑上相邻，物理上也是相邻的。而链表通过链连接，建立数据元素的逻辑关系。

typedef struct LNode *List; 
struct LNode
{
   ElementType Data;
   List Next; 
};
struct Lnode L; 
List PtrL;

• 求表长
  用临时指针p指向链表头Ptrl，然后遍历，直到null

int Length ( List PtrL )
{
   List p = PtrL;  /* p指向表的第一个结点*/
   int j=0; 
   while ( p ) 
   {
      p = p->Next; 
      j++;  /* 当前p指向的是第 j 个结点*/
   }
   return j; 
}

• 查找

1. 按序号查找 根据位序K，返回相应元素 FindKth(int K, List L)

List FindKth( int K, List PtrL )
{
   List p = PtrL;
   int i=1;  // i代表第几给元素。因为一开始p指向第一个元素，所以i=1
   while (p !=NULL && i < K )
   {
      p = p->Next;
      i++; 
   }
   if ( i == K ) /* 找到第K个，返回指针 */
      return p;
   else return NULL;  /* 没找到第K个，循环因为 p=NULL 而退出 */
}

2. 按值查找：Find(ElementType x, List L)

List Find( ElementType X, List PtrL )
{
   List p = PtrL;
   while ( p!=NULL && p->Data != X ) // 条件1表不空，条件2没找到X，就继续
      p = p->Next;
   return p; //找到了：返回节点p。没找到返回p = NULL
}

• 插入
  在第 i-1 (1≤i≤n+1) 个结点后插入一个值为X的新结点

1. 先构造一个新结点，用s指向; mallo
2. 再找到链表的第 i-1个结点，用p指向;
3. 然后修改指针，插入结点 ( p之后插入新结点是 s)

s-> next = p -> next;
p -> next = s

实现

List Insert( ElementType X, int i, List PtrL )
{
   List p, s; 
   if ( i == 1 )   /* 新结点插入在表头 */
   {
      s = (List)malloc(sizeof(struct LNode));  /*申请、填装结点s */
      s->Data = X;
      s->Next = PtrL; 
      return s;  // s成为新的head，返回出去
   }
   p = FindKth( i-1, PtrL );  /* 查找第i-1个结点 */
   if ( p == NULL )  
   {
      printf("参数i错");
      return NULL; 
   }
   else 
   {
      s = (List)malloc(sizeof(struct LNode)); /*申请、填装结点*/ 
      s->Data = X;
      s->Next = p->Next; /*新结点插入在第i-1个结点的后面*/ 
      p->Next = s;
      return PtrL;
   }
}

• 删除
  删除链表的第 i (1≤i≤n) 个位置上的节点

1. 先找到链表的第 i-1个结点，用p指向;
2. 再用指针s指向要被删除的结点(p的下一个结点);
3. 然后修改指针，删除s所指结点; p->next = s->next
4. 最后释放s所指结点的空间。
   实现

List Delete( int i, List PtrL )
{
   List p, s;
   if ( i == 1 ) 
   { /* 若要删除的是表的第一个结点 */
      s = PtrL; /*s指向第1个结点*/ 
      if (PtrL!=NULL) 
         PtrL = PtrL->Next; /*从链表中删除*/
      else 
         return NULL; // 如果本身就是空链表，return NULL
      free(s);
      return PtrL;
   }
   p = FindKth( i-1, PtrL ); /*查找第i-1个结点*/   
   if ( p == NULL ) 
   {
      printf(“第%d个结点不存在”, i-1); 
   } 
   else if ( p->Next == NULL )
   {
      printf(“第%d个结点不存在”, i); 
   }else 
   {
      s = p->Next;   /*s指向第i个结点*/
      p->Next = s->Next;   /*从链表中删除*/
      free(s);  /*释放被删除结点 */
      return PtrL;
   }
}

广义表 Generalized List

二元多项式
可以将上述二元多项式看成关于x 的一元多项式
矩阵可以用二维数组表示，但二维数组表示有两个缺陷：

1. 一是数组的大小需要事先确定
2. 对于“稀疏矩阵 ”，将造成大量的存储空间浪费。
   采用一种典型的多重链表——十字链表来存储稀疏矩阵

• 只存储矩阵非0元素项 结点的数据域:行坐标Row、列坐标Col、数值Value
• 每个结点通过两个指针域，把同行、同列串起来
  • 行指针(或称为向右指针)Right
  • 列指针(或称为向下指针)Down

Term 代表非0项
特殊Term A 代表4行5列，7个非零项

堆栈 Stack

具有一定操作约束的线性表，只在一端(栈顶，Top)做 插入、删除
操作集:长度为MaxSize的堆栈S 属于 Stack，堆栈元素item 属于 ElementType

1. Stack CreateStack( int MaxSize ): 生成空堆栈，其最大长度为MaxSize;
2. int IsFull( Stack S, int MaxSize ):判断堆栈S是否已满;
3. void Push( Stack S, ElementType item ):将元素item压入堆栈;
4. int IsEmpty ( Stack S ):判断堆栈S是否为空;
5. ElementType Pop( Stack S ):删除并返回栈顶元素;

栈的顺序存储实现

栈的顺序存储结构通常由一个一维数组和一个记录.栈顶元素位置的变量组成。

#define MaxSize <储存数据元素的最大个数> 
typedef struct SNode *Stack;  //结构指针
struct SNode{
    ElementType Data[MaxSize];  //数组
    int Top; // 栈顶位置的数组下标
};

1. 入栈 Push

void Push( Stack PtrS, ElementType item )  // stack这个类型的指针
{
    if ( PtrS->Top == MaxSize-1 ) // 判断满不满。从 0 到 MaxSize-1
    { 
        printf(“堆栈满”); 
        return;
    }else 
    {
        PtrS->Data[++(PtrS->Top)] = item; 
        /* 相当于：
        (PtrS->Top)++;
        PtrS->Data[PtrS->Top] = item;
        */
        return;
    }
}

1. 出栈 Top

ElementType Pop( Stack PtrS ) 
{
    if ( PtrS->Top == -1 ) 
    {
         printf(“堆栈空”);
         return ERROR;  //ERROR是ElementType的特殊值，标志错误
    } else 
    {
        return ( PtrS->Data[(PtrS->Top)--] ); // return 出下标为top的这个值，同时Top-1
    }
}

[例] 请用一个数组实现两个堆栈，要求最大地利用数组空间，使 数组只要有空间入栈操作就可以成功。
【分析】 一种比较聪明的方法是使这两个栈分别从数组的两头开始 向中间生长;当两个栈的栈顶指针相遇时，表示两个栈都满了。

#define MaxSize <存储数据元素的最大个数> 

struct DStack {
    ElementType Data[MaxSize]; 
    int Top1; /* 堆栈1的栈顶指针 */ 
    int Top2; /* 堆栈2的栈顶指针 */
} S;

S.Top1 = -1; // 左边这个设为空
S.Top2 = MaxSize; // 右边设为空（已经超出了MaxSize -1)

入栈

void Push( struct DStack *PtrS, ElementType item, int Tag ) 
{ /* Tag作为区分两个堆栈的标志，取值为1和2 */
    if ( PtrS->Top2 – PtrS->Top1 == 1) /* 堆栈满, 两个指针相邻啦 */ 
    { 
        printf(“堆栈满”); 
        return ;
    }
    if ( Tag == 1 ) /* 对第一个堆栈操作 */
        PtrS->Data[++(PtrS->Top1)] = item;  // 放在第一个元素后面一位
    else /* 对第二个堆栈操作 */ 
        PtrS->Data[--(PtrS->Top2)] = item;  // 放在最后一个元素的前面一位
}

出栈

ElementType Pop( struct DStack *PtrS, int Tag ) 
{ /* Tag区分两个堆栈*/
    if(Tag==1) /*对第一个堆栈操作 */ 
    { 
        if ( PtrS->Top1 == -1 )  /*堆栈1空 */
        { 
            printf(“堆栈1空”); 
            return NULL;
        } else 
            return PtrS->Data[(PtrS->Top1)--]; // 先抛出再对top-1
    } else /* 对第二个堆栈操作 */
    { 
        if ( PtrS->Top2 == MaxSize )  /*堆栈2空 */
        {        
            printf(“堆栈2空”); 
            return NULL;
        } 
        else 
            return PtrS->Data[(PtrS->Top2)++]; // 先抛出再对top+1
    } 
}

堆栈的链式存储实

栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删 除操作只能在链栈的栈顶进行。

typedef struct SNode *Stack; struct SNode{
    ElementType Data;
    struct SNode *Next; 
};

初始化(建立空栈)

Stack CreateStack()
{ /* 构建一个堆栈的头结点，返回指针 */
    Stack S;
    S =(Stack)malloc(sizeof(struct SNode)); 
    S->Next = NULL;
    return S;
}

判断堆栈S是否为空

int IsEmpty(Stack S) /*判断堆栈S是否为空，若为空函数返回1，否则返回0 */
{ 
   return ( S->Next == NULL );
}

1. 入栈 Push

void Push( ElementType item, Stack S) /* 将元素item压入堆栈S */
{ 
    struct SNode *TmpCell;
    TmpCell=(struct SNode *)malloc(sizeof(struct SNode))
    TmpCell->Element = item;
    TmpCell->Next = S->Next;  // 插到头结点的后面
    S->Next = TmpCell;
}

1. 出栈 Top

ElementType Pop(Stack S)  /* 删除并返回堆栈S的栈顶元素 */
{ 
   struct SNode *FirstCell;
   ElementType TopElem;
   if( IsEmpty( S ) ) 
    {
        printf(“堆栈空”); 
        return NULL; 
    } 
    else 
    {
        FirstCell = S->Next;
        S->Next = FirstCell->Next; 
        TopElem = FirstCell ->Element; // 获得被删除的这个值,return出去
        free(FirstCell);
        return TopElem;
    } 
}

应用:表达式求值

1. 运算数相对顺序不变

2. 运算符号顺序发生改变: 需要存储“等待中”的运算符号,要将当前运算符号与“等待中”的最后一个运算符号比较

   如果最后一个符号的优先级比较高,则出栈

   如果最后一个符号的优先级更低,则等待

括号怎么办?
左括号(优先级比乘号*高.但左括号(在堆栈中优先级就降到最低, 左括号(优先级比加号+低.
碰到右括号)后,括号内的计算结束,把堆栈内的抛出来,直到遇到左括号(.

队列 Queue

FIFO
操作集:长度为MaxSize的队列Q Î Queue，队列元素item Î ElementType

1. Queue CreatQueue( int MaxSize ):生成长度为MaxSize的空队列;
2. int IsFullQ( Queue Q, int MaxSize ):判断队列Q是否已满;
3. void AddQ( Queue Q, ElementType item ): 将数据元素item插入队列Q中;
4. int IsEmptyQ( Queue Q ): 判断队列Q是否为空;
5. ElementType DeleteQ( Queue Q ):将队头数据元素从队列中删除并返回。

队列的顺序存储实现

一个一维数组,队列头元素位置的变量front, 队列为元素位置的变量rear, 而堆栈由一个一位数组加上一个top.
队列的结构

#define MaxSize <储存数据元素的最大个数> 
struct QNode {
    ElementType Data[ MaxSize ]; 
    int rear;
    int front;
};
typedef struct QNode *Queue;

循环队列
当front == rear时候, 空
rear指向这个队列实际的最后一个元素的位置,front是第一个元素的前一个. 加入一个元素的时候rear + 1, 删除一个元素的时候front + 1
使用额外标记 size或者tag
仅使用n-1个数组空间

1. 创建队列

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;
}

1. 入队列
   用求余数函数,实现循环队列 例如 (5+1)%6 = 0, 放在第0位

void AddQ( Queue PtrQ, ElementType item) {
    if ( (PtrQ->rear+1) % MaxSize == PtrQ->front ) // front rear相邻
    { 
        printf(“队列满”);
        return;
    }
    PtrQ->rear = (PtrQ->rear+1)% MaxSize; 
    PtrQ->Data[PtrQ->rear] = item;
}

1. 出队

ElementType DeleteQ ( Queue PtrQ ) // front和rear相同
{
    if ( PtrQ->front == PtrQ->rear ) 
    { 
        printf(“队列空”);
        return ERROR;
    } 
    else 
    {
        PtrQ->front = (PtrQ->front+1)% MaxSize; // front往后移一位指向第一个元素
        return PtrQ->Data[PtrQ->front];
    } 
}

队列的链式存储实现

链表结点结构

struct Node{ 
    ElementType Data; 
    struct Node *Next;
};

链表队列结构

struct QNode
{ 
    struct Node *rear; /* 指向队尾结点 */
    struct Node *front; /* 指向队头结点 */ 
};
typedef struct QNode *Queue;  
Queue PtrQ;  // 包含front和rear的这个结构的指针PtrQ

1. 出队

ElementType DeleteQ ( Queue PtrQ ) 
{ 
    struct Node *FrontCell;
    ElementType FrontElem;

    if ( PtrQ->front == NULL) 
    { 
        printf(“队列空”); 
        return ERROR;
    }
    FrontCell = PtrQ->front;  // 找到队列的头个元素
    if ( PtrQ->front == PtrQ->rear) /* 若队列只有一个元素 */
        PtrQ->front = PtrQ->rear = NULL; /* 删除后队列置为空 */ 
    else
        PtrQ->front = PtrQ->front->Next;
    FrontElem = FrontCell->Data;
    free( FrontCell ); /* 释放被删除结点空间 */ 
    return FrontElem;
}

应用: 多项式加法运算

算法思路:
两个指针P1和P2分别指向这两个多项式第一个结点，不断循环:

1. P1->expon==P2->expon相同: 系数相加，若结果不为0，则作为结果多项式对应项
   的系数。同时，P1和P2都分别指向下一项;
2. P1->expon>P2->expon 这时p1大: 将P1的当前项存入结果多项式，并使P1指向下一项;
3. P1->exponexpon 这时p2大: 将P2的当前项存入结果多项式，并使P2指向下一项;
4. 当某一多项式处理完时，将另一个多项式的所有结点依次复制到结果多项式中去。

struct PolyNode //结构类型
{
    int coef; // 系数
    int expon; // 指数 
    struct PolyNode *link;  // 指向下一个节点的指针
}
typedef struct PolyNode *Polynomial; 
Polynomial P1, P2;  // p1 p2都是这种结构的指针

实现

Polynomial PolyAdd (Polynomial P1, Polynomial P2) 
{
    Polynomial front, rear, temp;  // 结构多项式的头 尾.
    int sum;
    
    // 临时空结点点作为结果多项式的表头, front rear都指向这个空间点
    rear = (Polynomial) malloc(sizeof(struct PolyNode)); 
    front = rear; /* 由front 记录结果多项式链表头结点 */
    
    while ( P1 && P2 ) /* 当两个多项式都有非零项(都不空)待处理时 */ 
        switch ( Compare(P1->expon, P2->expon) ) // 比较两个指数
        { 
            case 1:  // p1大
                // 系数和指素接到rear的后面
                Attach( P1->coef, P1->expon, &rear); 
                P1 = P1->link;
                break;
            case -1: // p2大
                Attach(P2->coef, P2->expon, &rear); 
                P2 = P2->link;
                break;
            case 0: //p1 = p2
                sum = P1->coef + P2->coef;
                // 判断sum不等于0
                if ( sum ) Attach(sum, P1->expon, &rear); 
                P1 = P1->link;
                P2 = P2->link;
                break;
        }
    /* 将未处理完的另一个多项式的所有节点依次复制到结果多项式中去 */ 
    // p1不空
    for ( ; P1; P1 = P1->link ) 
        Attach(P1->coef, P1->expon, &rear);
    // p2 不空
    for ( ; P2; P2 = P2->link ) 
        Attach(P2->coef, P2->expon, &rear); 
    
    // rear 指向结果多项式的最后一项,现在结束了,把link设为NULL
    rear->link = NULL;
    // 释放临时结点
    temp = front;
    front = front->link; /*令front指向结果多项式第一个非零项 */ 
    free(temp); /* 释放临时空表头结点 */
    return front;
}

其中attach函数

//传入系数和指数,以及最后一个结点的指针位置(指针的指针),于在本函数中需要改变当前结果表达式尾项指针的值,所以函数传递进来的是结点指针的地址，*pRear指向尾项
 void Attach( int c, int e, Polynomial *pRear )
{
    Polynomial P;
    /* 申请新结点 */ 
    P =(Polynomial)malloc(sizeof(struct PolyNode)); 
    P->coef = c; /* 对新结点赋值 */
    P->expon = e;
    P->link=NULL;
    /* 将P指向的新结点插入到当前结果表达式尾项的后面 */ 
    (*pRear)->link = P;
    *pRear = P; /* 修改pRear值 */
}

树与树的表示

查找 Searching

• 静态查找 集合是固定的,没有插入和删除
• 动态查找 集合中的记录是动态变化的,可以插入和删除

静态查找 Sequential Search

结构体:

typedef struct Lnode *List;
struct Lnode{
    ElementType Element[MAXSIZE];
    int length;
}

函数:

int SequentialSearch(List tb1, ElementType K){
    int i;
    tb1->Element[0] = K; // 建立哨兵
    for(i = tb1->length; tb1->Element[i] != K; i--); //从下往上循环直到K
    return i;  // 成功返回下标,不成功返回0
}

顺序查找算法的时间复杂度为O(n)

二分查找 Binary Search

函数:

int BinarySearch ( StaticTable * Tb1, ElementType K) 
{ /*在表Tbl中查找关键字为K的数据元素*/
    int left, right, mid, NoFound=-1;
    left = 1;
    right = Tb1->Length; 
    while ( left <= right ) 
    {
        mid = (left+right)/2;
        if( K < Tb1->Element[mid]) right = mid-1;
        else if( K > Tb1->Element[mid]) left = mid+1;
        else return mid; /*查找成功，返回数据元素的下标*/
    }
return NotFound; /*查找不成功，返回-1*/ 
}

二分查找算法具有对数的时间复杂度O(logN)
判定树:
判定树上每个结点需要的查找次数刚好 为该结点所在的层数.
n个结点的判定树的深度 为[log2n]+1.

树 Tree

定义:n(n≥0)个结点构成的有限集合
子树是不相交的,除了根结点外，每个结点有且仅有一个父结点
结点的度(Degree):结点的子树个数
树的度:树的所有结点中最大的度数
结点的层次(Level):规定根结点在1层， 其它任一结点的层数是其父结点的层数加1。
树的深度(Depth):树中所有结点中的最 大层次是这棵树的深度。

二叉树

度为2的树,可以为空.若不为空由根节点和左子树和右子树

• 一个二叉树第 i 层的最大结点数为:2^(i-1)
• 深度为k的二叉树有最大结点总数为: 2^k -1
• 对任何非空二叉树T，若$n_0$表示叶结点的个数、$n_2$是度为2的非叶结点个数，那么两者满足关系$n_0 = n_2 +1$
  证明: 总边数=总节点数-1 (因为根没有向上的边)
  总边数= n0 + n1 +n2 -1
  总边数 = 0n0 + 1n1 + 2*n2 (往下看)

二叉树的存储结构

1. 顺序存储结构
   完全二叉树
   父节点:i/2
   左子节点: 2i
   右子节点: 2i+1
2. 链表存储

typedef struct TreeNode * BinTree; 
typedef BinTree Position;
struct TreeNode
{
    ElementType Data; 
    BinTree Left; 
    BinTree Right;
}

二叉树的遍历

2. 先序遍历 PreOrder Traversal
   根节点->左子树->右子树

 void PreOrderTraversal( BinTree BT )
{
     if( BT ) // BT不空
     {
        printf(“%d”, BT->Data);
        PreOrderTraversal( BT->Left );
        PreOrderTraversal( BT->Right );
     }
}

1. 中序遍历 InOrderT Traversal
   左子树->根节点->右子树
2. 后序遍历 Post-Order Traversal
   左子树->右子树->根节点

二叉树的非递归遍历
中序遍历的非递归算法实现

void InOrderTraversal( BinTree BT )
{  
    BinTree T=BT;
    Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/ 
    while( T || !IsEmpty(S) )
    {  //IsEmpty是判断堆栈空不空
        while(T){ /*一直向左并将沿途结点压入堆栈*/ \
            Push(S,T);
            T = T->Left; 
            }
        if(!IsEmpty(S)){
            T = Pop(S); /*结点弹出堆栈*/
            printf(“%5d”, T->Data); /*(访问)打印结点*/ 
            T = T->Right; /*转向右子树*/
        } 
    }
}

层序遍历

队列实现:遍历从根结点开始，首先将根结点入队，然后开始执 行循环:结点出队、访问该结点、其左右儿子入队
算法实现:

void LevelOrderTraversal ( BinTree BT )
{
    Queue Q; BinTree T;
    if ( !BT ) return; /* 若是空树则直接返回 */ 
    Q = CreatQueue( MaxSize ); /*创建并初始化队列Q*/ 
    AddQ( Q, BT ); // 把根节点放到队列里去
    while ( !IsEmptyQ( Q ) ) {
        T = DeleteQ( Q );  // pop出一个元素,产生的元素赋给 T指针
        printf(“%d\n”, T->Data); /*访问取出队列的结点*/ 
        if ( T->Left ) AddQ( Q, T->Left );
        if ( T->Right ) AddQ( Q, T->Right );
    } 
}

输出二叉树叶子节点

void PreOrderPrintLeaves( BinTree BT ) 
{
    if( BT ) {
        if ( !BT->Left && !BT->Right ) // 如果没有左右子树,就打印出来
            printf(“%d”, BT->Data ); 
        PreOrderPrintLeaves ( BT->Left ); 
        PreOrderPrintLeaves ( BT->Right );
    } 
}

求二叉树的高度

int PostOrderGetHeight( BinTree BT ) 
{
     int HL, HR, MaxH;
    if( BT ) 
    {
        HL = PostOrderGetHeight(BT->Left); /*求左子树的深度*/ 
        HR = PostOrderGetHeight(BT->Right); /*求右子树的深度*/ 
        MaxH = (HL > HR)? HL : HR; /*取左右子树较大的深度*/ 
        return ( MaxH + 1 ); /*返回树的深度*/
    }
    else return 0; /* 空树深度为0 */ 
}

层序生成二叉树

typedef int ElementType; //假设是int
#define NoInfo 0;

typedef struct TreeNode * BinTree; 
typedef BinTree Position;
struct TreeNode
{
    ElementType Data; 
    BinTree Left; 
    BinTree Right;
}

BinTree CreateBinTree()
{
    ElementType Data;
    BinTree BT, T;
    Q = CreateQueue();

    // 读入第一个检点,即根节点
    scanf("%d", &Data);
    if (Data != NoInfo)
    { // 不为空, 分配根节点单元,并将节点地址入队
        BT = (BinTree)mallo(sizeof(Struct Tnode));
        BT->Data = Data;
        Bt->Left = BT->Right = NULL;
        AddQ(Q, BT);
    }else return NULL; //若第一个数据0,则返回空树

    while(!IsEmpty(Q)){
        T->DeleteQ(Q);  //从队列中取出一节点地址
        // 读左孩子
        scanf("%d", &Data);
        if(Data != NoInfo)
            T->Left = NULL;
        else  // 分配新节点,作为出队节点的左孩子,分配的新节点入队
        {
            T->Left = (BinTree)mallo(sizeof(Struct Tnode));
            T->Left->Data = Data;
            T->Left->Left = T->Left->Right = NULL;
            AddQ(Q, T->Left);
        }

        // 读右孩子
        scanf("%d", &Data);
        if(Data != NoInfo)
            T->Right = NULL;
        else  // 分配新节点,作为出队节点的右孩子,分配的新节点入队
        {
            T->Right = (BinTree)mallo(sizeof(Struct Tnode));
            T->Right->Data = Data;
            T->Right->Left = T->Right->Right = NULL;
            AddQ(Q, T->Left);
        }
    }// while循环结束
    return BT;
}

二叉搜索树 Binary Search Tree

1. 非空左子树所有键值小于根节点的键值
2. 非空右子树所有键值大于根节点的键值
3. 左右子树都是二叉搜索树

操作的函数:

1. Position Find( ElementType X, BinTree BST ):从二叉搜索树BST 中查找元素X，返回其所在结点的地址;
2. Position FindMin( BinTree BST ):从二叉搜索树BST中查找并返回 最小元素所在结点的地址;
3. Position FindMax( BinTree BST ) :从二叉搜索树BST中查找并返回 最大元素所在结点的地址。
4. BinTree Insert( ElementType X, BinTree BST ) 插入
5. BinTree Delete( ElementType X, BinTree BST ) 删除

查找

递归实现

Position Find( ElementType X, BinTree BST ) {
    if( !BST ) return NULL; /*查找失败*/ 
    if( X > BST->Data )
        return Find( X, BST->Right ); /*在右子树中继续查找*/
    Else if( X < BST->Data )
        return Find( X, BST->Left ); /*在左子树中继续查找*/
    else 
        /* X == BST->Data */
        return BST; /*查找成功，返回结点的找到结点的地址*/
}

迭代实现

Position IterFind( ElementType X, BinTree BST ) {
    while( BST ) 
    {
        if( X > BST->Data )
            BST = BST->Right; /*向右子树中移动，继续查找*/ 
        else if( X < BST->Data )
            BST = BST->Left; /*向左子树中移动，继续查找*/ 
        else /* X == BST->Data */
            return BST; /*查找成功，返回结点的找到结点的地址*/ 
    }
        return NULL; /*查找失败*/
} 

返回最大值/最小值

最大元素一定在最右分支的端点上

Position FindMax( BinTree BST )
{
    if(BST ) // 结点不空
    {
        while( BST->Right ) // 右儿子不空
            BST = BST->Right; // 则往右
    }
    return BST;
}

最小元素在最左段上
递归法:

 Position FindMin( BinTree BST )
{
    if( !BST ) return NULL;/*空的二叉搜索树，返回NULL*/
    else if( !BST->Left )
        return BST; /*找到最左叶结点并返回*/
    else 
        return FindMin( BST->Left ); /*沿左分支继续查找*/

插入

BinTree Insert( ElementType X, BinTree BST ) {
    if( !BST ) /*若原树为空，生成并返回一个结点的二叉搜索树*/
    { 
        BST = malloc(sizeof(struct TreeNode)); 
        BST->Data = X;            
        BST->Left = BST->Right = NULL;
    }
    else /*开始找要插入元素的位置*/ 
    {
        if( X < BST->Data )
            BST->Left = Insert( X, BST->Left); /*递归插入左子树*/
        else if( X > BST->Data )
            BST->Right = Insert( X, BST->Right); /*递归插入右子树*/
    /* else X已经存在，什么都不做 */
    }
    return BST;
}

删除

2. 删除的是叶结点

3. 删除的只有一个孩子的结点

4. 要删除的结点右左右两棵子树,则:

   右子树最小元素替代

   左子树最大元素替代

实现

BinTree Delete( BinTree BST, ElementType X ) 
{ 
    Position Tmp; 
 
    if( !BST ) 
        printf("要删除的元素未找到"); 
    else {
        if( X < BST->Data ) 
            BST->Left = Delete( BST->Left, X );   /* 从左子树递归删除 */
        else if( X > BST->Data ) 
            BST->Right = Delete( BST->Right, X ); /* 从右子树递归删除 */
        else { /* BST就是要删除的结点 */
            /* 如果被删除结点有左右两个子结点 */ 
            if( BST->Left && BST->Right ) {
                /* 从右子树中找最小的元素填充删除结点 */
                Tmp = FindMin( BST->Right );
                BST->Data = Tmp->Data;
                /* 从右子树中删除最小元素 */
                BST->Right = Delete( BST->Right, BST->Data );
            }
            else { /* 被删除结点有一个或无子结点 */
                Tmp = BST; 
                if( !BST->Left )       /* 只有右孩子或无子结点 */
                    BST = BST->Right; 
                else                   /* 只有左孩子 */
                    BST = BST->Left;
                free( Tmp );
            }
        }
    }
    return BST;
}

平衡二叉树 Balanced Binary Tree

平均查找长度ASL
平衡因子(Balance Factor，简称BF): BF(T) = hL-hR，
|BF(T)| <= 1
平衡二叉树的高度
n_h: 高度为h的平衡二叉树最少结点数
n_h = n_h-1 + n_h-2 + 1
= F_h+2 - 1
给定结点数为 n的AVL树的 最大高度为O(log2n)!

调整

平衡二叉树是搜索树
右单旋
麻烦结点在发现者(被破坏者)的右子树的右子树上,因而RR插入,需要RR旋转
左单旋
麻烦结点在发现者(被破坏者)的左子树的左子树上,因而LL旋转
左右旋转
麻烦结点在发现者(被破坏者)的左子树的右子树上, LR旋转

习题: 是否同一颗二叉搜索树

2. 根据两个序列分别建树，再判别树是否一样
3. 不建树的判别方法
4. 建一棵树，再判别其他序列是否与该树一致

堆 Heap

优先队列(Priority Queue)
结构性:用 数组 表示的完全二叉树;
有序性:任一结点的关键字是其子树所有结点的最大值(或最小值)
* “最大堆(MaxHeap)”,也称“大顶堆”:最大值
* “最小堆(MinHeap)”,也称“小顶堆” :最小值

主要操作有:
• MaxHeap Create( int MaxSize ):创建一个空的最大堆。
• Boolean IsFull( MaxHeap H ):判断最大堆H是否已满。
• Insert( MaxHeap H, ElementType item ):将元素item插入最大堆H。
• Boolean IsEmpty( MaxHeap H ):判断最大堆H是否为空。
• ElementType DeleteMax( MaxHeap H ):返回H中最大元素(高优先级)。

结构

typedef struct HNode *MaxHeap;
struct HNode {
    ElementType *Elements; // 存储堆元素的数组
    int Size;   // 堆的当前元素的个数
    int Capacity  // 堆的最大容量
}

创建

MaxHeap CreateHeap(int Maxsize)
{
    MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));
    H->Elements = malloc((MaxSize+1) * sizeof(ElementType)); // 因为这里是一个数组,需要分配空间
    H->Size = 0; // 当前是空的
    H->Capacity = MaxSize;  // 堆的最大容量
    H->Elements[0] = MaxSize; /* 定义“哨兵”为大于堆中所有可能元素的值，便于以后操作 */
    return H;
}

插入

将新增结点插入到从其父结点到根结点的有序序列中
将新item放在最后的位置Size+1, 然后跟他的父节点i/2比较,不断把父节点往下(子节点)移动,直到其父节点大于item

void InsertHeap(MaxHeap H, ElementType item)
{
    int i;
    if (IsFull(H)){
        printf("FULL\n");
        return;
    }
    i = ++H->Size;  // H->Size++; i = H->Size; 把新增元素放在末尾H->Size++的位置上
    for(; H->Elements[i/2] < item; i/=2){  // 其父节点小于它
        H->Elements[i] = H->Elements[i/2]; // 把它的父节点,向下过滤, 插入的item向上过滤
    } 
    // 当它的父结点[i/2]比它大的时候, 跳出循环
    H->Elements[i] = item;  // 填上item
}

删除

取出根结点(最大值)元素，同时删除堆的一个结点。

• 最后的元素替补根的位置
• 有序化, 父结点和更大的那个子结点比较,将子结点不断往上移, 直到父结点不子结点大

ElementType DeleteMax(MaxHeap H)
{
    int parent, child;
    ElementType MaxItem, temp;
    if(IsEmpty(H)){
        printf("Empty\n");
        return;
    }

    MaxItem = H->Elements[1]; // 取出最大值
    /* 用最大堆中最后一个元素从根节点开始向上过滤下层节点 */
    temp = H->Elements[Size];  // 把堆中最后一个值,交给temp
    Size--;

    for(parent=1; parent*2 <= H->Size; parent=child)
    {
        child = parent*2  // 左儿子

        /* child=左右儿子中大的那个, 当右儿子存在,且右儿子的值比左儿子大时,让child=右儿子 */
        if((child!= H->Size) && 
        (H->Elements[child] < H->Elements[child+1])) 
            child++;
        
        /* 当temp比child的值大时跳出循环 */
        if (temp >= Elements[child]) 
            break;
        else 
            H->Elements[parent] = H->Elements[child]; //当parent < child,这个parent位置上变为child的值
    }
    H->Elements[parent] = temp; 
    return MaxItem; 
}

堆排序

方法1:通过插入操作，将N个元素一个个相继插入到一个初 始为空的堆中去，其时间代价最大为O(N logN)。

方法2:在线性时间复杂度下建立最大堆。O(N)
(1)将N个元素按输入顺序存入，先满足完全二叉树的结构特性
(2)调整各结点位置，以满足最大堆的有序特性。

void BuildHeap(MaxHeap H){
    int i;
    for(i = H->Size/2; i>0; i--) 
    {// 从最后一个结点的父节点开始,到根节点为止
        PercDown(H, i);
    }
}

// 下滤函数, 将Maxheap中以H->Data[p]为根的子堆调整为最大堆
void PercDown( MaxHeap H, int p)
{
    int parent, child;

    X = H->Data[p]; // 取出根节点的值
    for(parent =  p; parent*2 <= H->Size; parent = child)
    {
        child = parent * 2;
        if( (child != H->Size) && (H->Data[child] < H->Data[child+1]))
        {
            child++;
        }
        if (X > H->Data[child]) 
            break;
        else // 将X下滤
            H->Data[parent] = H->Data[child];
    }
    H->Data(parent) = X;
}

哈夫曼树与哈夫曼编码

带权路径WPL Weighted Path Length)长度最小, 最优二叉树.
数据结构:

typedef struct TreeNode *HuffmanTree;
struct TreeNode{
    int Weight;
    HaffmanTree left;
    HaffmantREE Right;
}

利用最小堆进行构造:

HuffmanTree Huffman(MinHeap H)
{
    int i;
    HuffmanTree T;
    BuildMinHeap(H); // 将H->Elements[]按照权重调整为最小堆
    for(i=1; i < H->Size; i++) // 做size-1次合并
    {
        T = malloc(sizeof(struct TreeNode)); // 建立新结点
        /*从最小堆中删除一个结点，作为新T的左子结点*/
        T->Left = DeleteMin(H);
        T->Right = DeleteMin(H);
        /*计算新权值*/
        T->Weight = T->Left->Weight+T->Right->Weight;
        Insert( H, T ); /*将新T插入最小堆*/
    }
    T = Deletemin(H); // 最小堆中的最后一个元素就是指向Huffman树根节点的指针
    return T; 
}

哈夫曼树的特点:

1. 没有度为1的结点
2. n个叶子结点的哈夫曼树共有2n-1个结点;
   因为: n2= n0 -1,
   总结点数 = n0 + n2 = 2n0 - 1
3. 哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树;
4. 对同一组权值{w1 ,w2 , … , wn}，存在不同构的两

集合及运算

双亲表示法: 孩子指向父节点
数据结构

typedef struct 
{ 
    ElementType Data; 
    int Parent;  // 其父节点的下标
} SetType;

查找某个元素所在的集合

用根节点表示

int Find(SetType S[], ElementType X)
{
    /* 在数组S中查找值为X的元素所属的集合, MaxSize为数组最大长度 */
    int i;
    for(i=0; i<MaxSize && S[i].Data != X; i++)
    if (i >= MaxSize) // 未找到
        return -1;
    for(; S[i].Parent >= 0; i = s[i].Parent);  // 向上找它的父节点
    return i;
}

集合的并运算

如果它们不同根，则将其中一个根结点的父结点指针设置成
另一个根结点的数组下标。

void Union( SetType S[], ElementType X1, ElementType X2 ) 
{
    int Root1, Root2;
    Root1 = Find(S, X1);
    Root2 = Find(S, X2);
    if( Root1 != Root2 )
        S[Root2].Parent = Root1;
}

为了使树更矮,合并时按秩合并
直接用一个数组表示,不用之前的数据结构了

#define MAXN 1000                  /* 集合最大元素个数 */
typedef int ElementType;           /* 默认元素可以用非负整数表示 */
typedef int SetName;               /* 默认用根结点的下标作为集合名称 */
typedef ElementType SetType[MAXN]; /* 假设集合元素下标从0开始 */

SetName Find(SetType S, ElementType X){
    for(; S[X] > 0; X=S[X]);
    return X.
}
void OldUnion(SetType S, SetName Root1, SetName Root2){
    S[Root2] = Root1;
}

void Union( SetType S, SetName Root1, SetName Root2 )
{ /* 这里默认Root1和Root2是不同集合的根结点 */
    /* 保证小集合并入大集合 */
    if ( S[Root2] < S[Root1] ) { /* 如果集合2比较大 */
        S[Root2] += S[Root1];     /* 集合1并入集合2  */
        S[Root1] = Root2;
    }
    else {                         /* 如果集合1比较大 */
        S[Root1] += S[Root2];     /* 集合2并入集合1  */
        S[Root2] = Root1;
    }
}

路径压缩

SetName Find( SetType S, ElementType X )
{ 
    if ( S[X] < 0 ) /* 找到集合的根 */
        return X;
    else
        return S[X] = Find( S, S[X] ); /* 路径压缩 */
}

图 Graph

顶点的集合 V (Vertex)
边的集合 E (Edge)

• 邻接矩阵
  用一个长度为N(N+1)/2的1维数组A存储
  O(N^2)
• 邻接表
  G[N]为指针数组，对应矩阵每行一个链表， 只存非0元素
  O(N+E)

建立图

邻接矩阵

// 用全局变量建图
int G[MAXN][MAXN], Nv, Ne; 
void BuildGraph()
{ 
    int i,j,v1,v2,w;
    scanf("%d", &Nv);
    /* CreateGraph */
    for (i=0; i<Nv; i++)
        for (j=0; j<Nv; j++)
            G[i][j] = 0; /* 或INFINITY */ 
    scanf("%d", &Ne);
    for (i=0; i<Ne; i++) {
         scanf("%d %d %d", &v1, &v2, &w);
         /* InsertEdge */
        G[v1][v2] = w;
        G[v2][v1] = w;
    }
}

图的遍历

深度优先搜索(Depth First Search, DFS)

类似于树的先序遍历

// 伪码
void DFS ( Vertex V )
{ 
    visited[V] = true;
    for ( V 的每个邻接点 W ) 
        if ( !visited[W] )
            DFS(W);
}

实现
以V为出发点对邻接表存储的图Graph进行DFS搜索

void Visit( Vertex V )
{
    printf("正在访问顶点%d\n", V);
}
 
void DFS( LGraph Graph, Vertex V, void (*Visit)(Vertex) )
{  
    PtrToAdjVNode W;
    Visit( V ); 
    Visited[V] = true; 
    /* 对V的每个邻接点W->AdjV */
    for( W=Graph->G[V].FirstEdge; W; W=W->Next ) 
        if ( !Visited[W->AdjV] )    
            DFS( Graph, W->AdjV, Visit );  
}

广度优先搜索(Breadth First Search, BFS)

层序遍历

// 伪码
void BFS ( Vertex V )
{ 
    visited[V] = true;
    Enqueue(V, Q);
    while(!IsEmpty(Q)){
        V = Dequeue(Q);
        for ( V 的每个邻接点 W )        
            if ( !visited[W] ) 
            {
                visited[W] = true;
                Enqueue(W, Q);
            }
    }
}
            

实现 邻接矩阵存储的图 - BFS

/* IsEdge(Graph, V, W)检查<V, W>是否图Graph中的一条边，即W是否V的邻接点。  */

bool IsEdge( MGraph Graph, Vertex V, Vertex W )
{
    return Graph->G[V][W]<INFINITY ? true : false;
}

```c
 
/* Visited[]为全局变量，已经初始化为false */
void BFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) )
{   /* 以S为出发点对邻接矩阵存储的图Graph进行BFS搜索 */
    Queue Q;     
    Vertex V, W;
 
    Q = CreateQueue( MaxSize ); /* 创建空队列, MaxSize为外部定义的常数 */
    /* 访问顶点S：此处可根据具体访问需要改写 */
    Visit( S );
    Visited[S] = true; /* 标记S已访问 */
    AddQ(Q, S); /* S入队列 */
     
    while ( !IsEmpty(Q) ) {
        V = DeleteQ(Q);  /* 弹出V */
        for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
            /* 若W是V的邻接点并且未访问过 */
            if ( !Visited[W] && IsEdge(Graph, V, W) ) {
                /* 访问顶点W */
                Visit( W );
                Visited[W] = true; /* 标记W已访问 */
                AddQ(Q, W); /* W入队列 */
            }
    } /* while结束*/
}

# 最短路径

在网络中，求两个不同顶点之间的所有路径 中，边的权值之和最小的那一条路径

## 无权图的单源最短路算法

按照递增(非递减)的顺序找出到各个顶 点的最短路

伪码描述:

```c

void Unweighted ( Vertex S )

{

Enqueue(S, Q);

while(!IsEmpty(Q)){

V = Dequeue(Q);

for ( V 的每个邻接点 W )

if(dist[W]==-1 ){

dist[W] = dist[V]+1;

path[W] = V;

Enqueue(W, Q);

}

}

}

```

实现

无权图的单源最短路算法 - 邻接表存储

dist[] path[]全部初始化为-1

```c

void Unweighted(LGraph Graph, int dist[], int path[], Vertex S){

Queue Q;

Vertex V;

PtrAdjVNode W;

Q = CreateQueue(Graph->Nv); // 创建空队列,MaxSize为外部定义的常数

dist[S] = 0; // 初始化源点

AddQ(Q, S);

while (IsEmpty(Q))

{

V = DeleteQ(Q);

for( W = Graph.G[V].FirstEdge; W; W=W->Next) // 对V的每个邻接点W->AdjV

if (dist[W->AdjV] == -1)

{ // W->AdjV 未被访问过

dist[W->AdjV] =dist[V] + 1; /* W->AdjV到S的距离更新 */

path[W->AdjV] = V; /* 将V记录在S到W->AdjV的路径上 */

AddQ(Q, W->AdjV);

}

}

}

```

## 有权图的单源最短路算法

Dijkstra 算法

按照递增的顺序找出到各个顶点的最短路

• 真正的最短路必须只经过S中的顶点
• 每次从未收录的顶点中选一个dist最小的收录
• 增加一个v进入S，可能影响另外一个w的dist值

1. dist[w] = min{dist[w], dist[v] + <v,w>的权重}

伪码

```c

void Dijkstra( Vertex s )

{

while (1){

V = 未收录顶点中dist最小者;

if ( 这样的V不存在 )

break;

collected[V] = true;

for ( V 的每个邻接点 W ){

if ( collected[W] == false ){

if ( dist[V]+E<V,W> < dist[W] ) {

dist[W] = dist[V] + E<V,W> ;

path[W] = V;

}

}

}

}

}

```

算法实现

邻接矩阵存储 - 有权图的单源最短路算法

```c

// 返回未被收录顶点中dist最小值

Vertex FindMinDist(MGraph Graph, int dist[], int collected[]){

Vertex MinV, V;

int MinDist = INFINITY;

for(V=0; VNv; V++){

if (collected[V] = false && dist[V]< MinDist){ /* 若V未被收录，且dist[V]更小 */

MinDist = dist[V];

MinV = V; /* 更新对应顶点 */

}

}

if (MinDist < INFINITY) /* 若找到最小dist */

return MinV; /* 返回对应的顶点下标 */

else return ERROR; /* 若这样的顶点不存在，返回错误标记 */

}

bool Dijkstra(MGraph Graph, int dist[], int path[], Vertex S)

{

int collected[MaxVertexNum];

Vertex V, W;

// 初始化dist[]和path[],邻接矩阵中不存在边的标记为INFINITY

for(V=0; VNv; V++){

dist[V] = Graph->G[S][V];

if (dist[V]<INFINITY) // S到V有直接路径

path[V] = S;

else

path[V] = -1;

collected[V] = false;

}

// 先将起点收入到集合中

dist[S] = 0;

collected[S] = true;

while(1)

{

V = FindMinDist(Graph, dist, collected); /* V = 未被收录顶点中dist最小者 */

if (V == ERROR) /* 若这样的V已经不存在 */

break;

collected[V] = true;

for(W=0; WNv; W++){ // 对图中的每个顶点W

if(collected[W] == false && Graph->G[V][W]<INFINITY)

{ // 未被收录,且有边(是邻接点)

if ( Graph->G[V][W]<0 ) /* 若有负边 */

return false; /* 不能正确解决，返回错误标记 */

/* 若收录V使得dist[W]变小 */

if ( dist[V]+Graph->G[V][W] < dist[W] ) {

dist[W] = dist[V]+Graph->G[V][W]; /* 更新dist[W] */

path[W] = V; /* 更新S到W的路径 */

}

}

} // for循环结束, 每个V的邻接点W遍历完

}// while结束

return true;

}

```

## 多源最短路算法

Floyd 算法

```c

bool Floyd( MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum] )

{

Vertex i, j, k;

/* 初始化 */

for ( i=0; iNv; i++ )

for( j=0; jNv; j++ ) {

D[i][j] = Graph->G[i][j];

path[i][j] = -1;

}

for( k=0; kNv; k++ )

for( i=0; iNv; i++ )

for( j=0; jNv; j++ )

if( D[i][k] + D[k][j] < D[i][j] ) {

D[i][j] = D[i][k] + D[k][j];

if ( i==j && D[i][j]<0 ) /* 若发现负值圈 */

return false; /* 不能正确解决，返回错误标记 */

path[i][j] = k;

}

return true; /* 算法执行完毕，返回正确标记 */

}

```

# 排序

## 冒泡排序

稳定!

最好情况:顺序 T = O(N)

最坏情况:逆序 T = O(N^2)

```c

void Swap(ElementType *a, ElementType *b){

ElementType c;

c = *a;

• a = *b;
• b = c;

}

void Bubble_Sort(ElementType A[], int N){

int P, i, flag;

for (P=N-1; P>0; P–){ // 最后一位下标是N-1

flag = 0;

for (i=0; i<P; i++){

if(A[i] > A[i+1]){

Swap(&A[i], &A[i+1]);

flag = 1; // 标识发生了交换

}

}

if (flag==0)

break; // 若全程无交换

}

}

```

## 插入排序

稳定!

最好情况:顺序 T = O(N)

最坏情况:逆序 T = O(N^2)

时间复杂度和逆序对有关 T(N,I) = O(N+I)

定理: 任意N个不同元素组成的序列平均具有 N ( N -1 ) / 4 个逆序对。

简单排序(交换相邻两个数)的时间复杂度下界: Omega(N^2)

```c

void Insertion_Sort(ElementType A[], int N){

ElementType Tmp;

int P, i;

for(P=1; P<N; P++){

Tmp = A[P]; // 摸下一张牌

for (i = P; i>0; i–)

{

if(A[i-1] > Tmp) // 若前一张牌比新摸的牌大

A[i] = A[i-1]; // 移出空位

else break; // 若新摸的牌比前一张牌大,则跳出循环

}

A[i] = Tmp; // 新牌落位

}

}

```

## 希尔排序

不稳定!

定义增量序列,如Sedgewick增量序列{1,5,19,41,109…}

对每个D进行D间隔的排序

```c

void Shell_Sort(ElementType A[], int N){

int D, P,i;

ElementType Tmp;

for (D=N/2; D>0; D/=2){ // 希尔排序增量

for ( P=D; P<N; P++){ // 插入排序

Tmp = A[P];

for (i = P; i-D>=0; i-=D)

{

if(A[i-D] > Tmp)

A[i] = A[i-D]; // 移出空位

else break;

}

A[i] = Tmp; // 新牌落位

}

}

}

```

## 堆排序

不稳定!

选择排序:

```c

void Selection_Sort ( ElementType A[], int N )

{

for(i=0;i<N;i++){

MinPosition = ScanForMin( A, i, N–1 );

Swap( A[i], A[MinPosition] );

}

}

```

重要的是如何找到最小元.

堆排序处理N个不同元素的 随机排列的平均比较次数是2NlogN - O(NloglogN)

用最大堆,交换根节点和最后一个结点,让最大的数到最后,然后减小堆的规模

```c

void PercDown(ElementType A[] , int p, int N)

{// 下滤函数, 将Minheap中以H->Data[p]为根的子堆调整为最小堆

int parent, child;

ElementType X;

X = A[p]; // 取出根节点的值

for(parent = p; parent*2+1 <= N-1 ; parent = child)

{

child = parent*2+1;

if( (child != N-1 ) && (A[child] < A[child+1]))

{

child++;

}

if (X >= A[child])

break;

else // 将X下滤

A[parent] = A[child];

}

A[parent] = X;

}

void Heap_Sort(ElementType A[], int N){

int i;

for (i=N/2; i>=0; i–) // Build MaxHeap

PercDown(A, i, N);

for (i=N-1; i>0; i–){

Swap(&A[0], &A[i]); // DeleteMax

PercDown(A, 0, i); // 重新整理成最大堆,堆的size为i

}

}

```

## 归并排序

稳定!

有序子列的归并

```c

void Merge(ElementType A[], ElementType TmpA[],

int L, int R, int RightEnd)

{

int LeftEnd, Num, Tmp;

int i;

LeftEnd = R - 1;

Tmp = L; // 存放结果的数组的初始位置

Num = RightEnd - L + 1; // 一共有几个数据

while (L <= LeftEnd && R <= RightEnd){ // 左和右都不为空

if (A[L] <= A[R])

TmpA[Tmp++] = A[L++];

else

TmpA[Tmp++] = A[R++];

}

// 跳出循环时左边还有剩下的

while (L <= LeftEnd)

TmpA[Tmp++] = A[L++];

// 跳出循环时右边还有剩下的

while (R <= RightEnd)

TmpA[Tmp++] = A[R++];

// 把TmpA倒回到A, 从RightEnd倒着复制回去

for(i=0; i<Num; i++){ // 重复Num次

A[RightEnd] = TmpA[RightEnd];

RightEnd–;

}

}

```

递归算法:

```c

void MSort(ElementType A[], ElementType TmpA[], int L, int RightEnd)

{

int Center;

if(L < RightEnd){ // L和RightEnd相等时,就只有一个元素了,不能再分

Center = (L+RightEnd)/2;

// 分

MSort(A, TmpA, L, Center);

MSort(A, TmpA, Center+1, RightEnd);

// 合

Merge(A, TmpA, L, Center+1, RightEnd);

}

}

// 同一接口

void Merge_Sort(ElementType A[], int N){

ElementType *TmpA; // 临时数组

TmpA = malloc(N * sizeof(ElementType));

if (TmpA != NULL){ // 分配空间成功

MSort(A, TmpA, 0, N-1);

free(TmpA);

}

else

printf(“空间不足\n”);

}

```

T(N) = T(N/2) + T(N/2) + O(N)

T(N) = O(NlogN)

非递归算法

```c

void Merge_Pass(ElementType A[], ElementType TmpA[], int N, int length) // lenght = 当前有序子列的长度, 一开始等于1

{

int i,j;

for (i=0; i <= N-2*length; i+=2*length) // 留两个length,分情况讨论

Merge(A, TmpA, i, i+length, i+2*length-1); // A TmpA L R RightEnd

if (i+length < N) // 归并最后两个子列

Merge(A, TmpA, i, i+length, N-1);

else // 最后只剩一个子列, 则复制过来

for (j=i; j<N; j++)

TmpA[j] = A[j];

}

void Merge_sort(ElementType A[], int N){

int length = 1; // 初始化子序列的长度

ElementType *TmpA; // 临时数组

TmpA = malloc(N * sizeof(ElementType));

if (TmpA != NULL){ // 分配空间成功

while (length < N){ // 有序子列长度等于N,则完成,跳出循环

Merge_Pass(A, TmpA, N, length);

length *= 2;

Merge_Pass(TmpA, A, N, length);

length *= 2;

}

free(TmpA);

}

else

printf(“空间不足\n”);

}

```

归并排序是稳定的

## 快速排序

不稳定

主元一次性放到正确的位置上

主元左边的都比主元小,右边的都比主元大

```c

// 选主元 pivot

ElementType Median3(ElementType A[], int Left, int Right){

int Center = (Left + Right) / 2;

// 整理成 A[Left] <= A[Center] <= A[Right]

if (A[Left] > A[Center])

Swap(&A[Left], &A[Right]);

if (A[Left] > A[Right])

Swap(&A[Left], &A[Right]);

if (A[Center] > A[Right])

Swap(&A[Center], &A[Right]);

// 将基准Pivot藏到右边Right-1处, 则之后只需考虑 A[Left+1] -> A[Right-2]

Swap(&A[Center], &A[Right-1]);

return A[Right-1];

}

void Qsort(ElementType A[], int Left, int Right){

int Pivot, Cutoff, Low, High;

// 如果序列元素足够多,则进入快排

Cutoff = 4;

if (Cutoff <= Right - Left){

Pivot = Median3(A, Left, Right);

Low = Left;

High = Right-1;

while(1){

while(A[++Low] < Pivot); // 一直循环,直到A[Low] >= Pivot, 停住

while(A[–High] > Pivot); // 一直循环,直到A[Hight] <= Pivot, 停住

if (Low<High)

Swap(&A[Low], &A[High]);

else // Low > High low已经越过了high,子序列排序结束

break;

}

Swap(&A[Low], &A[Right-1]); // 将Pivot归位,此时 Low>High, 所以Pivot和Low交换

Qsort(A, Left, Low-1); // 递归Pivot左边

Qsort(A, Low+1, Right); // 递归Pivot右边

}

else // 元素太少,用简单排序

Insertion_Sort(A+Left, Right-Left+1); // 待排序列表A从Left开始,即A+Left, 长度是R-L+1

}

void Quick_Sort(ElementType A[], int N){

Qsort(A, 0 ,N-1);

}

```

## 选择排序

不稳定

```c

#define MaxDigit 3 // 假设最大为三位数

#define Radix 10 // 十进制

/* 桶元素结点 */

typedef struct Node *PtrNode;

struct Node

{

int key;

PtrNode next;

};

/* 桶头结点 */

struct HeadNode

{

PtrNode head;

PtrNode tail;

};

typedef struct HeadNode Bucket[Radix];

/* 返回整型关键字X的第D位数字 */

int GetDigit(int X, int D){

// 默认次位D=1, 主位 D<= MaxDigit

int d, i;

for(i=1; i<=D; i++){

d = X % Radix;

X /= Radix;

}

return d;

}

// 次位优先(Least Significant Digit)排序

void LSDRadix_Sort(ElementType A[], int N){

int D, Di, i;

Bucket B;

PtrNode tmp, p, List=NULL;

// 初始化每个桶为空链表

for(i=0; i<Radix; i++)

B[i].head = B[i].tail = NULL;

// 将原始序列A[], 逆序(插在链表头)存入链表List

for(i=0; i<N; i++){

tmp = (PtrNode)malloc(sizeof(struct Node));

tmp->key = A[i];

tmp->next = List;

List = tmp;

}

// 开始排序

for (D=1; D<= MaxDigit; D++){ // 对数据的每一位循环处理

p=List;

while(p)

{

Di = GetDigit(p->key, D); // 获得当前元素的第D位数字

// 从链表P中删除结点

tmp = p;

p = p->next;

tmp->next = NULL;

// 把结点插入到对应的B[Di]桶里

if (B[Di].head == NULL)

B[Di].head = B[Di].tail = tmp;

else{

B[Di].tail->next = tmp; // 把tmp加在尾部

B[Di].tail = tmp; // 尾部指向最后一个结点,即tmp

}

} // while循环结束, 以第D位的分配完毕

// D位数排完以后开始收集

List = NULL;

for(Di=Radix-1; Di >= 0; Di–) // 将诶个桶的元素顺序收入List, 因为每次插入到List的头部,所以要从9开始收

{

if (B[Di].head){

B[Di].tail->next = List;

List = B[Di].head;

B[Di].head = B[Di].tail = NULL; // 清空桶

}

}

}// 大for循环结束

// 将List[]导入A[], 并释放空间

for(i=0; i<N; i++){

tmp = List;

List = List->next;

A[i] = tmp->key;

free(tmp);

}

}

```

时间复杂度 T = O(P(N+B))

当B较小时,基本是线性的.