数据结构与算法

基本概念

  • 数据(Data) ：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。
  • 数据元素(Data Element) ：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。
  • 一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。
  • 数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C={’A’,’B’, ‘C’,…} 。

image-20231204234859086

数据的逻辑结构

数据结构(Data Structure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型，

  • 集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。
  • 线性结构：结构中的数据元素之间存在一对一的关系。
  • 树型结构：结构中的数据元素之间存在一对多的关系。
  • 图状结构：结构中的数据元素之间存在多对多的关系。

image-20231204235727339

数据的存储结构

  • 顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。
  • 链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer)，用该指针来表示数据元素之间的逻辑结构(关系)。

image-20231204235637540

抽象数据类型ADT

image-20231204235824898

算法与数据分析

常量($c$) < 对数($\log_2n$) <$\log_2^2n$ < 线性($n$) < $nlogn$ < 平方($n^2$) <立方($n^3$) < 指数($2^n$) < 阶乘($n!$)

image-20231205205707340

线性表

顺序表

顺序表定义

1
2
3
4
5
6
#define  MAXSIZE 100     //最大长度
typedef  struct {
  ElemType  *elem;     //指向数据元素的基地址
  int  length;          //顺序表的当前长度
  int listsize;        //顺序表初始分配的空间大小               
 }SqList；

初始化顺序表

使用引用

1
2
3
4
5
6
7
Status InitList_Sq(SqList &L){  //构造一个空的顺序表L
    L.elem=new ElemType[MAXSIZE];   //为顺序表分配空间
    if(!L.elem) exit(OVERFLOW);       //存储分配失败
    L.length=0;					  //空表长度为0
    L.listsize=MAXSIZE;					  
    return OK;
}

使用指针

1
2
3
4
5
6
7
Status InitList_Sq(SqList *L){    //构造一个空的顺序表L
    L-> elem=new ElemType[MAXSIZE];   //为顺序表分配空间
    if(! L-> elem) exit(OVERFLOW);       //存储分配失败
    L-> length=0;	            	  //空表长度为0
    L-> listsize=MAXSIZE;
    return OK;
}

销毁顺序表

1
2
3
4
5
6
7
8
9
Status DestroyList(SqList &L){
  if (L.elem) {
      delete L.elem;    //释放存储空间
      L.elem=NULL;
      L.length=0;
      L.listsize=0;
   }
   return OK;
}

清空顺序表

1
2
3
4
5
6
Status ClearList(SqList &L) 
{
   L.length=0;                //将顺序表的长度置为0
   return OK;
}

求顺序表长度

1
2
3
4
5
Status ClearList(SqList &L) 
{
   L.length=0;                //将顺序表的长度置为0
   return OK;
}

判断顺序表是否为空

1
2
3
4
5
int IsEmpty(SqList L)
{
  if (L.length==0) return 1;      
   else return 0;
}

获取顺序表的指定元素位置

1
2
3
4
5
int IsEmpty(SqList L)
{
  if (L.length==0) return 1;      
   else return 0;
}

查找指定值的元素位置

1
2
3
4
5
6
int LocateElem(SqList L,ElemType e)
{
  for (i=0;i< L.length;i++)
      if (L.elem[i]==e) return i+1;                
  return 0;
}

在顺序表中插入元素

插入算法主要耗时在移动元素上

1
2
3
4
5
6
7
8
9
Status ListInsert_Sq(SqList &L,int i ,ElemType e){
   if(i<1 || i>L.length+1) return ERROR;	         //i值不合法
   if(L.length==L.listsize) return ERROR;    //当前存储空间已满     
   for(j=L.length-1;j>=i-1;j--) 
       L.elem[j+1]=L.elem[j];    //插入位置及之后的元素后移
    L.elem[i-1]=e;                     //将新元素e放入第i个位置
    L.length++;		     	//表长加1
    return OK;
}

在线性表中删除元素

同样耗时在移动元素上

1
2
3
4
5
6
7
8
Status ListDelete_Sq(SqList &L,int i,ElemType &e){
   if((i<1)||(i>L.length)) return ERROR;	 //i值不合法
   e=L.elem[i-1];                              //将欲删除的元素保留在e中
  for (j=i;j<=L.length-1;j++)                   
　  　L.elem[j-1]=L.elem[j];       //被删除元素之后的元素前移  
   --L.length;               	      //表长减1
  return OK;
}

顺序表优缺点

优点：

  • 存储密度大（结点本身所占存储量/结点结构所占存储量）
  • 可以随机存取表中任一元素

缺点：

  • 在插入、删除某一元素时，需要移动大量元素
  • 浪费存储空间
  • 属于静态存储形式，数据元素的个数不能自由扩充

随机存取法

image-20231205003159011

链表

头结点

image-20231205003017898

使用头节点的好处：

  • 便于首元结点的处理
    首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理;
  • 便于空表和非空表的统一处理
    无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

image-20231205003118494

顺序存储法

链表优缺点

优点：

  • 数据元素的个数可以自由扩充
  • 插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高

缺点：

  • 存储密度小
  • 存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）

单链表定义

1
2
3
4
5
typedef struct LNode{
     ElemType   data;       //数据域
     struct LNode  *next;   //指针域
}LNode,*LinkList;   
                // LinkList为Lnode类型的指针

初始化

1
2
3
4
5
6
Status InitList_L(LinkList &L){ 
   L=new LNode;     
   if (!L) exit(OVERFLOW);               	
   L->next=NULL;　　　　　
   return OK; 
}

销毁

1
2
3
4
5
6
7
8
9
10
Status DestroyList_L(LinkList &L){
    LinkList p;
       while(L)
        {
            p=L;  
            L=L->next;
            delete p;  
        }
     return OK;
 }

或者

1
2
3
4
5
6
7
8
9
LinkList p = L;
       while(p){
            q = p->next;
            delete p; 
            p=q;  
        }
       L=NULL;
       return OK;
}

清空

1
2
3
4
5
6
7
8
9
Status ClearList(LinkList &L){// 将L重置为空表 
   LinkList p;
   while(L->next) {               
        p=L->next; 
        L->next =p->next; 
        delete p; 
    }
    return OK;
}

或者

1
2
3
4
5
6
7
8
LinkList p = L->next, q;
       while(p){
            q=p->next;
            delete p; 
            p=q;}
       L->next=NULL;
       return OK;
}

求表长

1
2
3
4
5
6
7
8
9
10
int  ListLength_L(LinkList L){
//返回L中数据元素个数
    LinkList p;
    p=L->next;         //p指向第一个结点
     j=0;             
     while(p){           //遍历单链表,统计结点数
           j++;
           p=p->next;    } 
    return j;                             
 }

判断表是否为空

1
2
3
4
5
6
7
int ListEmpty(LinkList L){ 
//若L为空表，则返回1，否则返回0 
   if(L->next)   //非空 
     return 0;
   else
     return 1;
 }

获取表中第n个元素

1
2
3
4
5
6
7
8
9
Status GetElem_L(LinkList L,int i,ElemType &e){ 
    p=L->next;j=1; //初始化
     while(p&&j<i){	//向后扫描，直到p指向第i个元素或p为空
       p=p->next; ++j;                           
     } 
     if(!p || j>i)return ERROR; //第i个元素不存在 
     e=p->data; //取第i个元素 
     return OK; 
}//GetElem_L

获取表中值为e的元素

1
2
3
4
5
6
LNode *LocateElem_L (LinkList L，Elemtype e) { 
  p=L->next; 
  while(p &&p->data!=e)  
        p=p->next;                		
  return p; 	//返回L中值为e的数据元素的位置，查找失败返回NULL 
}

插入元素

1
2
3
4
5
6
7
8
9
10
Status ListInsert_L(LinkList &L,int i,ElemType e){ 
     p=L;j=0; 
      while(p&&j<i−1){p=p->next;++j;}	//寻找第i−1个结点 
      if(!p||j>i−1)return ERROR;	//i大于表长 + 1或者小于1  
      s=new LNode;			//生成新结点s 
      s->data=e;      		           //将结点s的数据域置为e 
      s->next=p->next;	   	          //将结点s插入L中 
      p->next=s; 
      return OK; 
}//ListInsert_L

若无头节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Status ListInsert_L(LinkList &L,int i,ElemType e){ 
    //添加这一段-----------------------------------------
      if(!L&&i!=1)  return ERROR;
      if(i==1) {
           s=new LNode; s->data=e; s->next=L; L=s;  return  OK;}
    //--------------------------------------------------
      p=L;j=1; 
      while(p&&j<i−1){p=p->next;++j;}	//寻找第i−1个结点 
      if(!p||j>i−1)return ERROR;	//i大于表长 + 1或者小于1  
      s=new LNode;			//生成新结点s 
      s->data=e;      		           //将结点s的数据域置为e 
      s->next=p->next;	   	          //将结点s插入L中 
      p->next=s; 
      return OK; 
}//ListInsert_L

删除元素

1
2
3
4
5
6
7
8
9
10
11
Status ListDelete_L(LinkList &L,int i,ElemType &e){
    p=L;j=0; 
    while(p->next &&j<i-1){//寻找第i个结点，并令p指向其前驱 
        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

若无头结点

1
2
3
4
5
6
7
8
9
10
11
12
Status ListDelete_L(LinkList &L,int i,ElemType &e){
    if(!L)  return ERROR;
    if(i==1) {p=L; L=L->next; delete p; return OK;}
    p=L;j=1; 
    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

建立链表

前插法

1
2
3
4
5
6
7
8
9
void CreateList_F(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; 	//插入到表头 
     } 
}//CreateList_F

尾插法

1
2
3
4
5
6
7
8
9
10
11
12
void CreateList_L(LinkList &L,int n){ 
      //正位序输入n个元素的值，建立带表头结点的单链表L 
      L=new LNode; 
      L->next=NULL; 	
      r=L; 	//尾指针r指向头结点 
      for(i=0;i<n;++i){ 
        p=new LNode;	　	//生成新结点 
        cin>>p->data;   		//输入元素值 
        p->next=NULL; r->next=p; 	    	//插入到表尾 
        r=p; 	//r指向新的尾结点 
      } 
}//CreateList_L

有序链表的合并

1
2
3
4
5
6
7
8
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
   pa=La->next;  pb=Lb->next;
   pc=Lc=La;             //用La的头结点作为Lc的头结点 
   while(pa && pb){
      if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next;}
      else{pc->next=pb; pc=pb; pb=pb->next;}
   pc->next=pa?pa:pb;    //插入剩余段  
   delete Lb;             //释放Lb的头结点}

双链表

1
2
3
4
5
typedef struct DuLNode{
    ElemType   data;              
    struct DuLNode  *prior;  
    struct DuLNode  *next;  
}DuLNode, *DuLinkList

双链表的插入

1
2
3
4
5
6
7
8
9
10
Status ListInsert_DuL(DuLinkList &L,int i,ElemType e){
   if(!(p=GetElemP_DuL(L,i))) return ERROR;
    s=new DuLNode; 
   s->data=e;
   s->prior=p->prior;  
   p->prior->next=s;
   s->next=p;  
   p->prior=s;
   return OK;
}

双链表的删除

1
2
3
4
5
6
7
8
Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e){
   if(!(p=GetElemP_DuL(L,i)))     return ERROR;
   e=p->data;
   p->prior->next=p->next;
   p->next->prior=p->prior;
   delete p; 
   return OK;
}

栈和队列

顺序栈

image-20231205171418265

顺序栈的定义

1
2
3
4
5
6
7
#define  MAXSIZE  100
typedef struct
{
	SElemType   *base;
	SElemType   *top;
	int stacksize;
}SqStack;

顺序栈的初始化

1
2
3
4
5
6
7
Status InitStack( SqStack &S ){
	S.base =new SElemType[MAXSIZE]；
	if( !S.base ) 	return OVERFLOW;
	S.top = S.base;
	S.stackSize = MAXSIZE;
	return OK;
}

判断是否为空

1
2
3
4
5
bool StackEmpty( SqStack S )
{
	if(S.top == S.base) return true;
   else return false;
}

求顺序栈的长度

1
2
3
4
int StackLength( SqStack S )
{
	return S.top – S.base;
}

清空顺序栈

1
2
3
4
5
Status ClearStack( SqStack  &S )
{
	if( S.base ) S.top = S.base;
	return OK;
}

销毁顺序栈

1
2
3
4
5
6
7
8
Status DestroyStack( SqStack &S ){
	if( S.base ){
		delete S.base ;
		S.stacksize = 0;
		S.base = S.top = NULL;
	}
  return OK;
}

进栈

1
2
3
4
5
6
7
Status Push( SqStack &S, SElemType e)  
{
	if( S.top - S.base== S.stacksize ) // 栈满
        return ERROR; 	
	*S.top++=e;
	return OK;
}

出栈

1
2
3
4
5
6
7
Status Pop( SqStack &S, SElemType &e)  
{
	if( S.top == S.base ) // 栈空
        return ERROR; 	
	e＝ *--S.top;
	return OK;
}

取顺序栈栈顶元素

1
2
3
4
5
6
Status GetTop( SqStack S, SElemType &e)  
{
	if( S.top == S.base )	 return ERROR; 	// 栈空
	e = *( S.top – 1 );
	return OK;
}

链栈

运算受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针

image-20231205171920231

定义

1
2
3
4
typedef  struct StackNode {
      SElemType  data; //数据域
      struct StackNode *next; //指针域
 } StackNode,  *LinkStack;

初始化

1
2
3
4
void InitStack(LinkStack &S )
{
	S=NULL;
}

判断是否为空

1
2
3
4
5
6
7
Status StackEmpty(LinkStack S) {
    if (S == NULL) {
        return TRUE;
    } else {
        return FALSE;
    }
}

进栈

1
2
3
4
5
6
7
8
9
10
Status Push(LinkStack &S, SElemType e) {
    p = new StackNode; // 生成新结点p
    if (!p) {
        exit(OVERFLOW);
    }
    p->data = e;
    p->next = S;
    S = p;
    return OK;
}

出栈

1
2
3
4
5
6
7
8
9
Status Pop (LinkStack &S,SElemType &e)
{
if (S==NULL) return ERROR;
e = S-> data;  
p = S;   
S =  S-> next;
delete p;   
return OK;  
}

取栈顶元素

1
2
3
4
5
6
7
SElemType GetTop(LinkStack S) {
    if (S == NULL) {
        exit(1);
    } else {
        return S->data;
    }
}

循环队列

定义

1
2
3
4
5
6
#define M  100   //最大队列长度
Typedef struct {
   QElemType *base;  //初始化的动态分配存储空间
   int  front;            //头指针   
   int  rear;             //尾指针
}SqQueue;

解决假溢出问题

image-20231205183321383

初始化

1
2
3
4
5
6
Status InitQueue (SqQueue &Q){
    Q.base =new QElemType[MAXQSIZE] ;
   if(!Q.base) exit(OVERFLOW);
    Q.front=Q.rear=0;
    return OK;
}

求循环队列的长度

1
2
3
int  QueueLength (SqQueue Q){
    return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;   
 }

入队

1
2
3
4
5
6
Status EnQueue(SqQueue &Q,QElemType e){
    if((Q.rear+1)%MAXQSIZE==Q.front)  return ERROR;
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXQSIZE;
     return OK; 
}

出队

1
2
3
4
5
6
Status DeQueue (LinkQueue &Q,QElemType &e){
   if(Q.front==Q.rear) return ERROR;
   e=Q.base[Q.front];
   Q.front=(Q.front+1)%MAXQSIZE;
   return OK;
}

链队列

image-20231205184146628

定义

1
2
3
4
5
6
7
8
typedef struct QNode{
   QElemType   data;
   struct Qnode  *next;
}Qnode, *QueuePtr;
typedef struct {
   QueuePtr  front;            //队头指针   
   QueuePtr  rear;             //队尾指针
}LinkQueue;

初始化

1
2
3
4
5
6
Status InitQueue (LinkQueue &Q){
   Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode)); 
    if(!Q.front) exit(OVERFLOW);
    Q.front->next=NULL;
     return OK;
}

销毁链队列

1
2
3
4
5
6
Status InitQueue (LinkQueue &Q){
   Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode)); 
    if(!Q.front) exit(OVERFLOW);
    Q.front->next=NULL;
     return OK;
}

判断链队列是否为空

1
2
3
Status QueueEmpty (LinkQueue Q){
   return (Q.front==Q.rear);   
}

求链队列对头元素

1
2
3
4
5
Status GetHead (LinkQueue Q, QElemType &e){
   if(Q.front==Q.rear) return ERROR;
   e=Q.front->next->data;
   return OK;
}

链队列入队

1
2
3
4
5
6
7
8
Status EnQueue(LinkQueue &Q,QElemType e){
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(OVERFLOW);
    p->data=e; p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    return OK;
}

不带头结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Status EnQueue(LinkQueue &Q, QElemType e) {
    p = (QueuePtr)malloc(sizeof(QNode));
    if (!p) {
        exit(OVERFLOW);
    }
    p->data = e; 
    p->next = NULL;
    if (Q.front == NULL) {
        Q.front = p;
        Q.rear = p;
        return OK;
    }
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}

带头结点的链队的入队操作，只要把新生成的结点加到尾结点后即可

而不带头结点的操作则还要注意到边界操作，假如是第一次入队，需修改队头指针。

同样的道理，对于出队操作，假如是最后一个结点出队，需要注意修改队尾指针

由此，我们建议链式队列好采用带头结点的实现方式。

链队列出队

1
2
3
4
5
6
7
8
9
Status DeQueue (LinkQueue &Q,QElemType &e){
   if(Q.front==Q.rear) return ERROR;
   p=Q.front->next;
   e=p->data;
   Q.front->next=p->next;
   if(Q.rear==p) Q.rear=Q.front;
   free(p);
   return OK;
}

多维数组

image-20231225002740712

image-20231225002807844

分治算法

image-20231206225119768

分治算法的适用条件

  1. 该问题规模缩小到一定的程度就可以容易地解决
  2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有递归子结构性质
  3. 利用该问题分解出的子问题的解可以合并为该问题的解
  4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题

分治算法的复杂性分析

image-20231206225429113

排序和搜索

合并排序

主要思想：

  • 将数组分成均匀两半（divide）.
  • 递归解决每个半部分（sort）.
  • 把两部分合并起来组成一个新的排序（merge）.

image-20231206225730807

算法实现

image-20231206234629808

合并函数Merge的实现

image-20231206225916139

合并排序的计算时间

递归树展开

image-20231206232041554

直接展开

image-20231206232059654

数学归纳

image-20231206233433834

快速排序

基本思想

image-20231206234408095

算法实现

image-20231206235848725

image-20231206235253252

快速排序的计算时间

image-20231207000637393

二分搜索/折半查找

算法和时间复杂度

image-20231222001541952

递归式求解

三种常用方法：

  • 归纳法

  • 展开法

  • 主方法

主方法

image-20231222002015583

主定理

image-20231222002608857

image-20231222002622021

举例

image-20231222002240212

image-20231222002255618

特殊情况

image-20231222002405412

查找

顺序查找

改进：把待查关键字key存入表头（“哨兵”），从后向前逐个比较，可免去查找过程中每一步都要检测是否查找完毕，加快速度。

1
2
3
4
5
6
7
8
int Search_Seq( SSTable  ST , KeyType  key ){
   //若成功返回其位置信息，否则返回0
  ST.R[0].key =key;   
 for( i=ST.length; ST.R[ i ].key!=key;  - - i  );
 //不用for(i=n; i>0; - -i) 或 for(i=1; i<=n; i++)  
   return i; 

}
  • 空间复杂度：一个辅助空间。
  • 时间复杂度：
    • 查找成功时的平均查找长度
      设表中各记录查找概率相等
      $ASL_s(n)=(1+2+ … +n)/n =(n+1)/2$
    • 查找不成功时的平均查找长度 $ASL_f =n+1$

折半查找

1
2
3
4
5
6
7
8
9
10
int Search_Bin(SSTable ST,KeyType key){
//若找到，则函数值为该元素在表中的位置，否则为0
    low=1;high=ST.length;						 while(low<=high){
        mid=(low+high)/2;
        if(key==ST.R[mid].key) return mid; 
        else if(key<ST.R[mid].key) high=mid-1;//前一子表查找
        else low=mid+1;                       		//后一子表查找
    }									    
    return 0;		//表中不存在待查元素
}

递归方式

1
2
3
4
5
6
7
8
9
int Search_Bin (SSTable ST, keyType key, int low, int high) 
{ 
  if(low>high) return 0;   //查找不到时返回0 
  mid=(low+high)/2; 
  if(key等于ST.elem[mid].key)  return mid; 
  else if(key小于ST.elem[mid].key)  
    ……..//递归
  else…….  //递归
}

查找过程：每次将待查记录所在区间缩小一半，比顺序查找效率高,时间复杂度$O(\log_2n)$

适用条件：采用顺序存储结构的有序表，不宜用于链式结构

索引表的查找

  • 分块查找

分块查找

分块有序，即分成若干子表，要求每个子表中的数值都比后一块中数值小（但子表内部未必有序）。
然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。

image-20231223005627456

分块查找过程

  1. 对索引表使用折半查找法（因为索引表是有序表）；
  2. 确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；

分块查找性能分析

image-20231223005806882

分块查找优缺点

优点：插入和删除比较容易，无需进行大量移动。

缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算。

适用情况：如果线性表既要快速查找又经常动态变化，则可采用分块查找。

哈希表查找

有关术语

哈希方法：
选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；
查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比较，确定查找是否成功。

哈希函数：哈希方法中使用的转换函数

image-20231223010108740

冲突不可避免，哈希方法一般采用除留余数法。

哈希表的查找

image-20231223010410001

image-20231223010419020

哈希表的查找效率分析

image-20231223010503904

ASL与装填因子$\alpha$有关！既不是严格的$O(1)$，也不是$O(n)$

  • 哈希表的平均查找长度是装填因子$\alpha$的函数，而不是 $n$ 的函数。
  • 这说明，用哈希表构造查找表时，可以选择一个适当的装填因子 $\alpha$，使得平均查找长度限定在某个范围内。

几点结论

  • 对哈希表技术具有很好的平均性能，优于一些传统的技术
  • 链地址法优于开放地址法
  • 除留余数法作哈希函数优于其它类型函数

排序

排序算法的好坏如何衡量？

  • 时间效率——排序速度（比较次数与移动次数）
  • 空间效率——占内存辅助空间的大小
  • 稳定性——A和B的关键字相等，排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。否则就是不稳定的。

插入排序

  • 直接插入排序
  • 折半插入排序
  • 希尔排序

直接插入排序是最简单的排序法

image-20231223011039541

直接插入排序

image-20231223011158037

1
2
3
4
5
6
7
8
9
10
11
void InsertSort(SqList ＆L)
 {int i,j;
   for(i=2;i<=L.length;++i)
     if( L.r[i].key<L.r[i-1].key)//将L.r[i]插入有序子表
       { L.r[0]=L.r[i]; // 复制为哨兵
          L.r[i]=L.r[i-1];
          for(j=i-2; L.r[0].key<L.r[j].key;--j)
	            L.r[j+1]=L.r[j]; // 记录后移 
         L.r[j+1]=L.r[0]; //插入到正确位置
       }
 }

时间复杂度为 $O(n^2)$
空间复杂度为 $O(1)$
是一种稳定的排序方法

折半查找

前面的ppt好像讲过了？

1
2
3
4
5
6
7
8
9
10
11
12
13
Status BInsertSort ( SqList &L )
 { for ( i = 2;  i <= L.length ; ++i )
    {  L.r[0] = L.r[i]; low = 1 ; high = i-1 ;
       while ( low <= high )       
          {  m = ( low + high ) / 2 ; 
             if  ( LT( L.r[0].key , L.r[m]. key ) )  high = m -1 ;
            else  low = m + 1; 
           }
       for ( j=i-1; j>=high+1; - - j ) L.r[j+1] = L.r[j];
       L.r[high+1] = L.r[0];
     }
  }  // BInsertSort

折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快

当 n 较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差
在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比折半插入排序执行的关键码比较次数要少
折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列

减少了比较次数，但没有减少移动次数
平均性能优于直接插入排序

时间复杂度为 $O(n^2)$
空间复杂度为 $O(1)$
是一种稳定的排序方法

希尔排序

先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

image-20231225002909004

image-20231225002937357

1
2
3
4
5
6
void   ShellSort(SqList &L，int delta[ ]，int t){
        //按增量序列delta[0…t-1]对顺序表L作Shell排序
   for(k=0；k<t；++k)
    　ShellInsert(L，delta[k])；
　 　//增量为delta[k]的一趟插入排序
}  // ShellSort

image-20231225003022704

image-20231225003045557

image-20231225003107740

交换排序

两两比较，如果发生逆序则交换，直到所有记录都排好序为止。

冒泡排序$O(n^2)$
快速排序$O( n\log_2n )$

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
void bubble_sort(SqList &L)
{ int m,i,j,flag=1;   RedType x;
  m=n-1;
  while((m>0)&&(flag==1))
  {  flag=0;
     for(j=1;j<=m;j++)
        if(L.r[j].key>L.r[j+1].key)
         {  flag=1;
            x=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=x; //交换
          }//endif
     m--;
   }//endwhile
}

时间复杂度为 $O(n^2)$
空间复杂度为 $O(1)$
是一种稳定的排序方法

快速排序

前面也讲过了

①每一趟的子表的形成是采用从两头向中间交替式逼近法；

②由于每趟中对各子表的操作都相似，可采用递归算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void QSort ( SqList &L，int low,  int  high ) 
{  if  ( low < high ) 
    {  pivotloc = Partition(L, low, high ) ;
        Qsort (L, low, pivotloc-1) ; 
        Qsort (L, pivotloc+1, high ) 
     }
}

int Partition ( SqList &L，int low,  int  high ) 
{  L.r[0] = L.r[low];   pivotkey = L.r[low].key;
   while  ( low < high ) 
    { while ( low < high && L.r[high].key >= pivotkey )  --high;
                 L.r[low] = L.r[high];
      while ( low < high && L.r[low].key <= pivotkey )  ++low;
                 L.r[high] = L.r[low];
     }
    L.r[low]=L.r[0]; 
    return low;
}

可以证明，平均计算时间是$O(n\log_2n)$。
实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。
快速排序是递归的，需要有一个栈存放每层递归调用时参数（新的low和high）。
最大递归调用层次数与递归树的深度一致，因此，平均情况下空间复杂度为$O(\log_2n)$，最坏情况下为$O(n)$ 。

时间复杂度：$O(n^2) $
平均时间效率：$O(n\log_2n) $
空间效率：$O(n)$—递归要用到栈空间
稳 定 性： 不稳定 —可选任一元素为支点。

归并排序

排序过程
初始序列看成n个有序子序列，每个子序列长度为1
两两合并，得到$\lfloor$n/2$\rfloor$个长度为2或1的有序子序列
再两两合并，重复直至得到一个长度为n的有序序列为止

时间效率：$O(n\log_2n) $
空间效率：$O(n)$
稳 定 性：稳定

选择排序

前面讲过了

每一趟在后面 $n-i +1$个中选出关键码最小的对象, 作为有序序列的第$ i $个记录

1
2
3
4
5
6
7
8
9
10
void SelectSort(SqList &K)
 { 
    for (i=1; i<L.length; ++i)
    { //在L.r[i..L.length] 中选择key最小的记录
        k=i;     
        for( j=i+1;j<=L.length ; j++)
            if ( L.r[j].key <L.r[k].key) k=j; 
        if(k!=i)L.r[i]←→L.r[k];            
    }  
}

时间复杂度：$O(n²)$
空间复杂度：$O(1)$
不稳定

堆排序

堆的定义

image-20231224010047831

image-20231224010208704

基本思想

image-20231224010347129

有n 个结点的完全二叉树，最后一个分支结点的标号是$\lfloor$$\frac{n}{2}$$\rfloor$

将根结点r[1]与左、右子树根结点比较，并与大者交换
重复直至叶子结点，得到新的堆

时间效率：$O(n\log_2n) $
空间效率：$O(1)$
稳 定 性：不稳定
适用于$n$ 较大的情况

树和二叉树

二叉树是有序树（子树有序，不能颠倒）

  • 性质1: 在二叉树的第i层上至多有$2^i-1$个结点
  • 性质2: 深度为k的二叉树至多有$2^k-1$个结点
  • 性质3: 对于任何一棵二叉树，若2度的结点数有$n_2$个，则叶子数$n_0$必定为$n_2＋1 $（即$n_0=n_2+1$）
  • 性质4: 具有n个结点的完全二叉树的深度必为$⌊log2n⌋+1$
  • 性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2。

满二叉树和完全二叉树

image-20231225003500795

满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。

对n个元素组成的有序顺序表进行折半查找时，查找成功时的比较次数最多为$⌊log2n⌋+1$

image-20231225003828059

二叉链表

1
2
3
4
typedef struct BiNode{
   TElemType   data;
   struct  BiNode   *lchild,*rchild; //左右孩子指针
}BiNode,*BiTree;

image-20231225003946603

1
2
typedef struct TriTNode{  TelemType data;   struct TriTNode *lchild,*parent,*rchild; }TriTNode,*TriTree;
//三叉链表

遍历二叉树

先序

1
2
3
4
5
6
7
8
Status PreOrderTraverse(BiTree T){
  if(T==NULL) return OK; //空二叉树
  else{    
     cout<<T->data; //访问根结点
     PreOrderTraverse(T->lchild); //递归遍历左子树
     PreOrderTraverse(T->rchild); //递归遍历右子树
    }
}

中序

1
2
3
4
5
6
7
8
Status InOrderTraverse(BiTree T){
  if(T==NULL) return OK; //空二叉树
  else{    
     InOrderTraverse(T->lchild); //递归遍历左子树
  cout<<T->data; //访问根结点
     InOrderTraverse(T->rchild); //递归遍历右子树
    }
}

后序

1
2
3
4
5
6
7
8
Status PostOrderTraverse(BiTree T){
  if(T==NULL) return OK; //空二叉树
  else{    
     PostOrderTraverse(T->lchild); //递归遍历左子树
     PostOrderTraverse(T->rchild); //递归遍历右子树
     cout<<T->data; //访问根结点
    }
}

效率

  • 时间效率:O(n) //每个结点只访问一次
  • 空间效率:O(n) //栈占用的最大辅助空间

重要结论

若二叉树中各结点的值均不相同，则：
由二叉树的前序序列+中序序列，或由其后序序列+中序序列均能唯一地确定一棵二叉树，
但由前序序列+后序序列却不一定能唯一地确定一棵二叉树。

应用

计算结点总数

1
2
3
4
5
6
7
8
int NodeCount(BiTree T)
{
	if(T==NULL)
		return 0; //如果是空树，则结点总数为0
	else
		return 1 + NodeCount(T- >lchild) + 
NodeCount(T->rchild);
}

计算叶子结点总数

1
2
3
4
5
6
7
8
9
10
11
int LeafCount(BiTree T)
{
	if(T==NULL)
		return 0; //如果是空树，则叶子结点个数为0
	else if(T->lchild==NULL&&T->rchild==NULL)
		return 1; //判断该结点是否是叶子结点（左孩子
右孩子都为空），若是则返回1
	else
		return LeafCount(T->lchild) + 
LeafCount(T->rchild);
}

计算树的高度

1
2
3
4
5
6
7
8
9
10
11
int Height(BiTree T)
{
	if(T==NULL)
		return 0; //如果是空树，则高度为0
	else 
           {
                        int hl = Height(T>lchild), 
                        int hr = Height(T->rchild);
		return (hl ≥ hr) ? (1 + hl): (1 + hr);
            }
}

层次遍历算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void LayeredTraverse(BiTree T){ 
    cout<<T->data; 		              //访问第v个顶点
    InitQueue(Q); EnQueue(Q, T);            	//辅助队列Q初始化， T进队
    while(!QueueEmpty(Q)){   		//队列非空 
       DeQueue(Q, p);        			//队头元素出队并置为p 
       if(p->lchild!=NULL){               	//p指向的结点有左孩子
             cout<<p->lchild->data; 	
             EnQueue(Q, p->lchild); //左孩子进队 
        }//if 
       if(p->rchild!=NULL){               	//p指向的结点有右孩子
             cout<<p->rchild->data; 	
             EnQueue(Q, p->rchild); //右孩子进队 
        }//if 
    }//while 
}//LayeredTraverse

线索二叉树

LTag :若 LTag=0, lchild域指向左孩子； 

       若 LTag=1, lchild域指向其前驱。

RTag :若 RTag=0, rchild域指向右孩子； 

        若 RTag=1, rchild域指向其后继。

区分前驱后继分别为前序中序后序

线索：指向结点前驱和后继的指针
线索链表：加上线索二叉链表
线索二叉树：加上线索的二叉树（图形式样）
线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程

image-20231225222739478

image-20231225222750296

避免指针域悬空，让空域指向根结点

树的存储结构

双亲表示法

image-20231225222910067

1
2
3
4
5
6
7
8
9
typedef struct PTNode{
    DataType data;
    int parent;
} PTNode;

typedef struct PTree{
    PTNode     nodes[MAXSIZE];
    int r, n; //根的位置和结点数
} PTree;

孩子表示法

image-20231225223040801

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct CTNode{
    int child;
   struct CTNode *next;
}CTNode;//孩子节点
typedef struct CTBox{
    DataType data;
   CTNode *firstchild;
}CTBox; //表头节点

typedef struct CTree{
    CTBox nodes[MAXSIZE];
    int n,r;
} CTree; //树

双亲孩子表示法

image-20231225223216145

孩子兄弟表示法

1
2
3
4
typedef struct CSNode{
  ElemType          data;
  struct CSNode     *firstchild,*nextsibling;
}CSNode,*CSTree;

树的存储结构——孩子兄弟表示法
也称为二叉树表示法、二叉链表表示法

image-20231225223711370

树和森林

树、森林和二叉树的相互转换

image-20231225224246469

image-20231225224314815

二叉树的应用

image-20231225224353330

二叉排序树

二叉排序树或是空树，或是满足如下性质的二叉树：

  1. 若其左子树非空，则左子树上所有结点的值均小于根结点的值；
  2. 若其右子树非空，则右子树上所有结点的值均大于等于根结点的值；
  3. 其左右子树本身又各是一棵二叉排序树

image-20231225224538259

二叉排序树的查找

1
2
3
4
5
BSTree SearchBST(BSTree T, KeyType key) {
   if((!T) || key==T->data.key) return T;       	 
   else if (key<T->data.key)  return SearchBST(T->lchild,key);	//在左子树中继续查找
   else return SearchBST(T->rchild,key);    		   		//在右子树中继续查找
} // SearchBST

平均查找长度和二叉树的形态有关，即，
最好：$\log_2n$（形态匀称，与二分查找的判定树相似）
最坏: $(n+1)/2$（单支树）

二叉排序树的生成就不讲了，主要讲讲删除

二叉排序树的删除

image-20231225224741963

image-20231225224845438

image-20231225224905773

平衡二叉树

根结点的左、右子树深度之差的绝对值≤ 1
左、右子树是平衡二叉树；

平衡因子:该结点左子树与右子树的高度差

对于一棵有n个结点的AVL树，其高度保持在$O(\log_2n)$数量级，ASL也保持在$O(\log_2n)$量级。

结点插入的平衡调整

image-20231225225708929

image-20231225225718278

image-20231225225728519

结点删除的平衡调整

image-20231225225755813

image-20231225225821608

image-20231225225927087

image-20231225225939585

练习

image-20231225230431930

image-20231225230454824

判断平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef struct BiNode{
   TElemType   data;
   struct  BiNode   *lchild,*rchild; //左右孩子指针
}BiNode,*BiTree; 

bool isBalanced(BiTree T) 

bool isBalanced(BiTree T) 
{ return height(T) >= 0; } 

int dfs(TreeNode* root) { 
      if (T == null) 
               { return 0; } // 记录左子树的高度
      int left_height = dfs(T->lchild); // 记录右子树的高度
      int right_height = dfs(T->rchild); 
      if (abs(left_height - right_height) > 1 || left_height == -1 || right_height == -1) { return -1; } 
     return 1 + max(left_height, right_height); } 
}

霍夫曼树

关键：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀－前缀编码

一棵有n个叶子结点的Huffman树有 $2n-1$个结点

image-20231225231001008

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
typedef  struct
{  int weight;
   int parent,lch,rch;
} HuffmanNode, *HuffmanTree;

算法
void CreatHuffmanTree (HuffmanTree HT,int n){
if(n<=1)return;
m=2*n-1;
HT=new HTNode[m+1];//0号单元未用，HT[m]表示根结点   
for(i=1;i<=m;++i)
  {HT[i].lch=0;HT[i].rch=0;HT[i].parent=0;}
for(i=1;i<=n;++i)cin>>HT[i].weight; 
for( i=n+1;i<=m;++i)       //构造  Huffman树
 { Select(HT, i-1, &s1, &s2);　
      //在HT[k](1≤k≤i-1)中选择两个其双亲域为0,
      // 且权值最小的结点,
      // 并返回它们在HT中的序号s1和s2
   HT[s1].parent=i;   HT[s2] .parent=i;  
     //表示从F中删除s1,s2
   HT[i].lch=s1;    HT[i].rch=s2 ; 
     //s1,s2分别作为i的左右孩子
   HT[i].weight=HT[s1].weight + HT[s2].weight;
     //i 的权值为左右孩子权值之和
    }
}

生成霍夫曼编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n){
//从叶子到根逆向求每个字符的赫夫曼编码，存储在编码表HC中
HC=new char *[n+1];         		//分配n个字符编码的头指针矢量
cd=new char [n];			//分配临时存放编码的动态数组空间
cd[n-1]=’\0’; 	//编码结束符
for(i=1; i<=n; ++i){	//逐个字符求赫夫曼编码
    start=n-1; c=i; f=HT[i].parent;                 			
    while(f!=0){	//从叶子结点开始向上回溯，直到根结点
         --start;                          			//回溯一次start向前指一个位置
         if (HT[f].lchild= =c)  cd[start]=’0’;	//结点c是f的左孩子，则生成代码0
         else cd[start]=’1’;               		//结点c是f的右孩子，则生成代码1
         c=f; f=HT[f].parent;             		//继续向上回溯
    }                                  		//求出第i个字符的编码      
    HC[i]= new char [n-start];         	// 为第i 个字符编码分配空间
    strcpy(HC[i], &cd[start])；    //将求得的编码从临时空间cd复制到HC的当前行中
  }
  delete cd;                            	//释放临时空间
} // CreatHuffanCode

图与贪心算法

矩阵表示

邻接矩阵表示

1
2
3
4
5
6
7
8
9
10
//用两个数组分别存储顶点表和邻接矩阵
#define MaxInt 32767                    	//表示极大值，即∞
#define MVNum 100                       	//最大顶点数 
typedef char VerTexType;              	//假设顶点的数据类型为字符型 
typedef int ArcType;                  	//假设边的权值类型为整型 
typedef struct{ 
  VerTexType vexs[MVNum];            		//顶点表 
  ArcType arcs[MVNum][MVNum];      		//邻接矩阵 
  int vexnum,arcnum;                		//图的当前点数和边数 
}AMGraph;

用邻接矩阵创建无向网络

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Status CreateUDN(AMGraph &G){ 
    //采用邻接矩阵表示法，创建无向网络G 
    cin>>G.vexnum>>G.arcnum; 	//输入总顶点数，总边数 
    for(i = 0; i<G.vexnum; ++i)    
      cin>>G.vexs[i];                        	//依次输入点的信息 
    for(i = 0; i<G.vexnum;++i) 	//初始化邻接矩阵，边的权值均置为极大值                 
     for(j = 0; j<G.vexnum;++j)   
      G.arcs[i][j] = MaxInt;   
    for(k = 0; k<G.arcnum;++k){                     //构造邻接矩阵 
      cin>>v1>>v2>>w;                                 //输入一条边依附的顶点及权值 
      i = LocateVex(G, v1);  j = LocateVex(G, v2);  //确定v1和v2在G中的位置                    G.arcs[i][j] = w; //边<v1, v2>的权值置为w 
      G.arcs[j][i] = G.arcs[i][j];              //置<v1, v2>的对称边<v2, v1>的权值为w 
   }//for 
   return OK; 
}//CreateUDN 
 int LocateVex(MGraph G,VertexType u)
 { /* 初始条件:图G存在,u和G中顶点有相同特征 */
   /* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
   int i;
   for(i=0;i<G.vexnum;++i)
     if(u==G.vexs[i])
       return i;
   return -1;
 }

邻接表表示

空间效率为O(n+2e)。
若是稀疏图(e<<n2)，比邻接矩阵表示法O(n2)省空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define MVNum 100            //最大顶点数 
typedef struct ArcNode{      //边结点 
    int adjvex;                        //该边所指向的顶点的位置 
    struct ArcNode * nextarc;   //指向下一条边的指针 
    OtherInfo info;              //和边相关的信息 
}ArcNode; 
-----------------------------------------------------
typedef struct VNode{ 
    VerTexType data;        //顶点信息 
    ArcNode * firstarc;     //指向第一条依附该顶点的边的指针 
}VNode;               	
-----------------------------------------------------
typedef struct{ 
    VNode vertices[MVNum];  //邻接表 
    int vexnum, arcnum;          //图的当前顶点数和边数 
}ALGraph;

利用邻接表创建无向网络

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Status CreateUDG(ALGraph &G){ 
　　//采用邻接表表示法，创建无向图G 
　  cin>>G.vexnum>>G.arcnum;               	//输入总顶点数，总边数 
    for(i = 0; i<G.vexnum; ++i){          	//输入各点，构造表头结点表 
       cin>> G.vertices[i].data;           	//输入顶点值 
       G.vertices[i].firstarc=NULL;       	//初始化表头结点的指针域为NULL 
    }//for 
    for(k = 0; k<G.arcnum;++k){        		//输入各边，构造邻接表 
       cin>>v1>>v2;                 			//输入一条边依附的两个顶点 
       i = LocateVex(G, v1);  j = LocateVex(G, v2);    
       p1=new ArcNode;               			//生成一个新的边结点*p1 
　　  p1->adjvex=j;                   			//邻接点序号为j 
　  　p1->nextarc= G.vertices[i].firstarc;  G.vertices[i].firstarc=p1;  
      //将新结点*p1插入顶点vi的边表头部 
      p2=new ArcNode; //生成另一个对称的新的边结点*p2 
　　  p2->adjvex=i;                   			//邻接点序号为i 
　  　p2->nextarc= G.vertices[j].firstarc;  G.vertices[j].firstarc=p2;  
      //将新结点*p2插入顶点vj的边表头部 
    }//for 
    return OK; 
}//CreateUDG

对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。
邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。

用途：邻接矩阵多用于稠密图；而邻接表多用于稀疏图

十字链表表示法

1
2
3
4
5
6
7
8
9
10
11
12
typedef  struct  arcnode     //边结点
{   int   tailvex,  headvex;  //弧尾、弧头在表头数组中位置
     struct   arcnode   *hlink；//指向弧头相同的下一条弧
     struct   arcnode   *tlink;    //指向弧尾相同的下一条弧
}DGraphEdge;

typedef  struct  dnode  //顶点结点
{   int   data;  //与顶点有关信息
     struct   arcnode   *firstin；//指向以该顶点为弧头的第一个弧结点
     struct   arcnode   *firstout; //指向以该顶点为弧尾的第一个弧结点
}DGraph;
DGraph g[M];    //g[0]不用

十字链表
(1) 用于表示有向图
(2) 邻接表和逆邻接表的组合

邻接多重表表示法

1
2
3
4
5
6
7
8
9
10
11
12
typedef   struct  arcnode  //边结点
{   int  mark;   //标志域
     int  ivex, jvex;  //该边依附的两个顶点在表头数组中位置
     struct  arcnode  *ilink, *jlink; //分别指向依附于ivex和jvex的
                                                           下一条边
}NDGraphEdge;

typedef   struct  dnode  //顶点结点
{    int   data;   //存与顶点有关的信息
      struct   arcnode  *firstedge;  //指向第一条依附于该顶点的边
}NDGraph;
NDGraph G[M];   //G[0]不用

邻接多重表：
(1) 用于表示无向图
(2) 每条边只表示一次的邻接表

图的遍历

DFS算法

邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
void DFS(AMGraph G, int v){        		//图G为邻接矩阵类型 
  cout<<v;  visited[v] = true;  		//访问第v个顶点
  for(w = 0; w< G.vexnum; w++)  	//依次检查邻接矩阵v所在的行  
        if((G.arcs[v][w]!=0)&& (!visited[w]))  DFS(G, w); 
      //w是v的邻接点，如果w未访问，则递归调用DFS 
} 

typedef struct{ 
      VerTexType vexs[MVNum]; //顶点表 
      ArcType arcs[MVNum][MVNum]; //邻接矩阵 
      int vexnum,arcnum; //图的当前点数和边数 
}AMGraph;

邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void DFS(ALGraph G, int v){        		//图G为邻接表类型 
   cout<<v;  visited[v] = true;    		//访问第v个顶点
   p= G.vertices[v].firstarc;     //p指向v的边链表的第一个边结点 
   while(p!=NULL){              	//边结点非空 
     w=p->adjvex;               	//表示w是v的邻接点 
     if(!visited[w])  DFS(G, w);//如果w未访问，则递归调用DFS 
     p=p->nextarc;                	//p指向下一个边结点 
   } 
} 

typedef struct ArcNode{
    int adjvex;  
    struct ArcNode * nextarc; 
    OtherInfo info;           	
}ArcNode; 
typedef struct VNode{ 
    VerTexType data; 	
    ArcNode * firstarc; 	
}VNode; 

typedef struct{ 
    VNode vertices[MVNum]; 
    int vexnum, arcnum; }ALGraph;

效率分析

用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n2)。
用邻接表来表示图，需要访问n个头结点和2e 个表结点，时间复杂度为O(n+e)。

结论：
稠密图适于在邻接矩阵上进行深度遍历；
稀疏图适于在邻接表上进行深度遍历

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void BFS (Graph G, int v){ 
    //按广度优先非递归遍历连通图G 
    cout<<v; visited[v] = true;     		//访问第v个顶点
    InitQueue(Q);              			//辅助队列Q初始化，置空         
    EnQueue(Q, v);            			//v进队 
    while(!QueueEmpty(Q)){   		//队列非空 
       DeQueue(Q, u);        			//队头元素出队并置为u 
       for(w = FirstAdjVex(G, u); w>=0; w = NextAdjVex(G, u, w)) 
       if(!visited[w]){               	//w为u的尚未访问的邻接顶点 
             cout<<w; visited[w] = true;	
             EnQueue(Q, w); //w进队 
          }//if 
    }//while 
}//BFS

效率分析

如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（ n 个元素），总时间代价为O(n2)。
用邻接表来表示图，需要访问 n个头结点和2e个表节点，时间复杂度为O(n+e)。

DFS和BFS效率比较

空间复杂度相同，都是O(n)(借用了堆栈或队列）；

时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关

AOV网和AOE网

① AOV网(Activity On Vertices)—用顶点表示活动的网络
② AOE网(Activity On Edges)—用边表示活动的网络

拓扑排序算法的实现

以邻接表作存储结构
把邻接表中所有入度为0的顶点进栈
栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈
重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
typedef struct node
{   int vex;
    struct node *next;
}GraphNode;
typedef struct tnode
{   int vexdata;
    int in;
    struct node *link;
}Graph;

void toposort(Graph g[],int n)
{  int top,m,k,j,s[M];
   GraphNode *p;
   top=0; m=0;
   for(j=1;j<=n;j++)
     if(g[j].in==0)  s[top++]=j;
   while(top>0)
   {  j=s[--top];
      printf("%d  ",g[j].vexdata);
      m++;
      p=g[j].link;
      while(p!=NULL)
      {  k=p->vex;
	 	  g[k].in--;
	 	  if(g[k].in==0)
	      s[top++]=k;
	      p=p->next;
      }
   }
   printf("\nm=%d\n",m);
   if(m<n)  printf("The network has a cycle\n");
}

关键路径

AOE网(Activity On Edge)——也叫边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间
起点——表示整个工程的开始点，也称源点
终点——表示整个工程的结束点，也称汇点
路径长度——路径上各活动持续时间之和
关键路径——起点到终点的最长路径
Ve(j)——表示事件Vj的最早发生时间
Vl(j)——表示事件Vj的最迟发生时间
e(k)——表示活动ak的最早开始时间
l(k)——表示活动ak的最迟开始时间
l(k) – e(k)——表示完成活动ak的时间余量
关键活动——关键路径上的活动，即l(k)=e(k)的活动

image-20231228001642735

image-20231228004346092

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
Status TopoLogicalOrder( Graph G, Stack &T){
//T 拓扑排序栈
	FindInDegree(G, indegree); //求各的顶点的入度
	Stack S; //入度为0 的顶点栈
	InitStack(T); count=0; ve[0..G,vexnum-1]=0;
	while(!stackEmpty(S)){
		Pop(S,j); Push(T,j);++count;
		for (p=G.vertices[j].firstarc; p; p=p->nextarc){
			k=p->adjvex;
			if(--indegree[k]==0)Push(S,k);
			if(ve[j]+*(p->info)>ve[k]) ve[k]=ve[j]+*(p->info);
		}
	}
	if(count<G.vexnum) return ERROR;
	else return OK;
}

Status CriticalPath(Graph G){
	Stack T;
	if(!TopoLogicalOrder(G,T) return ERROR; //拓扑排序时已计算最早发生时间
	vl[0..G.vexnum-1]=ve[G.vexnum-1]; //初始化最迟发生时间
	while(!StackEmpty(T)){
		for(Popo(T,j), p=G.vertices[j].firstarc; p; p=p->nextarc){
			k=p->adjvex; dut=*(p->info); //dut<j,k>
			if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut
		}
	}
	for(j=0; j<G.vexnum; ++j){
		for(p=G.vertices[j].firstarc; p; p=p->nextarc){
			k=p->adjvex; dut=*(p->info);
			ee=ve[j]; el=vl[k]-dut;
			tag=(ee==el)?"*":"";	
			printf(j,k,dut,ee,el,tag); //输出关键活动
		}
	}
}

贪心算法

求解分数背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static float knapsack(float c, float [] w, float [] v, float [] x){
	int n=v.length;
	Element [] d = new Element [n];
	for (int i = 0; i < n; i++) d[i] = new Element(w[i],v[i],i);
	MergeSort.mergeSort(d);
	int i;
	float opt=0;
	for (i=0;i<n;i++) x[i]=0;
	for (i=0;i<n;i++) {
		if (d[i].w>c) break;
		x[d[i].i]=1;
		opt+=d[i].v;
		c-=d[i].w;
	}
	if (i<n){
		x[d[i].i]=c/d[i].w;
		opt+=x[d[i].i]*d[i].v;
	}
	return opt;
}

对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。
实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。

求解活动安排问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int greedySelector(int [] s, int [] f, boolean a[])
   {  sort all the job in ascending order of finishing time, 
      and relabel them.
      int n=s.length-1;
      a[1]=true;
      int j=1;
      int count=1;
      for (int i=2;i<=n;i++) {
        if (s[i]>=f[j]) {
          a[i]=true;
          j=i;
          count++;
          }\\if
        else a[i]=false;
      }\\for
      return count;
   }

求解最小生成树

Prime算法: 归并顶点，与边数无关，适于稠密网
Kruskal算法：归并边，适于稀疏网

这个看图掌握一下吧。

效率分析

image-20231228004929299

最短路径问题

一、 单源最短路径—用Dijkstra（迪杰斯特拉）算法
二、所有顶点间的最短路径—用Floyd（弗洛伊德）算法

迪杰斯特拉算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void ShortestPath_DIJ(AMGraph G, int v0){ 
    //用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径 
    n=G.vexnum;                    		//n为G中顶点的个数 
    S[v0]=true;                    	//将v0加入S 
    D[v0]=0;                      		//源点到源点的距离为0
    for(v = 1; v<n; ++v){             	//n个顶点依次初始化 
       S[v] = false;                  	//S初始为空集 
       D[v] = G.arcs[v0][v];           	//将v0到各个终点的最短路径长度初始化 
       if(D[v]< MaxInt)  Path [v]=v0; //v0和v之间有弧，将v的前驱置为v0 
       else Path [v]=-1;               	//如果v0和v之间无弧，则将v的前驱置为-1 
     }//for 
/*―开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集―*/ 
      for(i=1;i<n; ++i){               	//对其余n−1个顶点，依次进行计算 
          min= MaxInt; 
          for(w=0;w<n; ++w) 
          if(!S[w]&&D[w]<min)  
                {v=w; min=D[w];}         	//选择一条当前的最短路径，终点为v 
          S[v]=true;                   		//将v加入S 
          for(w=0;w<n; ++w) //更新从v0出发到集合V−S中顶点的最短路径长度 
                if(!S[w]&&(D[v]+G.arcs[v][w]<D[w])){ 
                      D[w]=D[v]+G.arcs[v][w];   	//更新D[w] 
                      Path [w]=v;              		//更改w的前驱为v 
               }//if 
    }//for       
}//ShortestPath_DIJ
弗洛伊德算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
采用图的邻接矩阵的存储结构
	怎样构造一个图，在此不赘述，直接给出floyd-wallshall算法。
void MDNet::Floyd(CDC *pDC)
{
	typedef vector<int> path;//使用顺序表模板
	path p[max_vertex_num][max_vertex_num];
	//p存放每对顶点之间的最短路径

	int D[max_vertex_num][max_vertex_num];
	// D存放每对顶点之间的最短路径值
	int i,j,k;
	for(i=1;i<=vex_num;i++)
	{//初始化
		for(j=1;j<=vex_num;j++)
		{
			p[i][j].push_back(i);
			p[i][j].push_back(j);
			//顶点i和顶点j之间的路径初始时就是ij。
			D[i][j]=arcs[i][j];//路径值为边（i，j）的权值
		}
	} 
	for(k=1;k<=vex_num;k++)
	 {//对于每一个顶点都要试探
		for(i=1;i<=vex_num;i++)
		{
			for(j=1;j<=vex_num;j++)
			{//在顶点i和顶点j之间的路径上试探k
				if(i==j)continue;//对角线上的元素（即顶点自身之						//间）不予考虑
					if(D[i][k]+D[k][j]<D[i][j])
					{//发现更短的路径
						D[i][j]=D[i][k]+D[k][j];
						//新的i、j间的路径由两部分组成
						//p[i][k]+p[k][j]
						p[i][j]=p[i][k]								for(int m=1;m<p[k][j].size();m++)
						    p[i][j].push_back(p[k][j][m]);
					}
			}
		}
	 }
for(i=1;i<=vex_num;i++)
	 {//打印每两个顶点之间的路径
		 for(j=1;j<=vex_num;j++)
		 {
			 for(k=0;k<p[i][j].size();k++)
				 cout<<p[i][j][k]<<"  ";
			 cout<<D[i][j];
			 cout<<endl;
		 }
	 }
}

算法全局最优解

动态规划

动态规划与分治递归的区别

  • 共同点：递归子结构

将待求解问题分解成若干个规模较小的相同类型的子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

  • 不同点：重叠子问题

适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。

  • 解决方案

保存所有已解的子问题的答案以备后用。

基本步骤

  • 找出最优解的性质，并刻划其结构特征。
  • 递归地定义最优值。
  • 以自底向上的方式计算出最优值。
  • 根据计算最优值时得到的信息，构造最优解。

带权重的活动安排问题

不能使用贪心算法求解

image-20231201201600142

p(j)为与活动j兼容的最大活动序号

image-20231201201945542

分为两种情形，$v_j$表示第j个活动的权重

递归求解和动态规划求解对比

时间复杂度为$O(1.618^n)$

因为如下图可算得$\frac{1+\sqrt{5}}{2}\approx1.618$

image-20231201204000095

image-20231201203213987

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

因为完成两次递归调用填充一个$M[n]$,一共填充$2n$次

image-20231201204634428

时间复杂度为$O(n\log_2n)$

因为快速排序的时间复杂度是$O(n\log_2n)$

动态规划算法的基本要素

  1. 最优子结构

image-20231208193547509

  1. 重叠子问题

image-20231208193712313

矩阵连乘问题

结构

image-20231208193823638

矩阵乘法满足交换率，故矩阵连乘可能得到不同的结果

image-20231208194158482

image-20231208194228534

动态规划思路

image-20231208194317633

image-20231208194338316

得到递归的关系
$$
m[i,j]=\begin{cases}
0&&&&&&&i=j\
min{m[i,j]+m[k+1,j]+p_{i-1}p_kp_j}&&&&&&&i<j
\end{cases}
$$
image-20231208194402651

但是递归算法的许多子问题被计算了多次

动态规划算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void matrixChain(int [] p, int [][] m, int [][] s) {
      int n=p.length-1;
      for (int i = 1; i <= n; i++) m[i][i] = 0;
      for (int r = 2; r <= n; r++)                   \\ r 为矩阵链的长度
           for (int i = 1; i <= n - r+1; i++) {     \\ i 为首矩阵的序号
                 int j=i+r-1;                                \\ j 为尾矩阵的序号
                 m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];   \\ 首先尝试在矩阵 i 处分开
                 s[i][j] = i;
                 for (int k = i+1; k < j; k++) {           \\ 然后尝试在矩阵 k 处分开
                       int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
                       if (t < m[i][j]) {
                            m[i][j] = t;
                            s[i][j] = k;
                       }
                 }
           }
      }
}

算法的时间空间复杂度

算法复杂度分析：

算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为$O(1)$，而3重循环的总次数为$O(n^3)$。因此算法的计算时间上界为$O(n^3)$。算法所占用的空间显然为$O(n^2)$。

image-20231208201323117

0-1背包问题

结构

image-20231208201405215

贪心算法可能得不到最优解

image-20231208201533938

正确和错误分析

image-20231208201630933

image-20231208201644523

添加一个w来记录重量限制即可

动态规划求解

1
2
3
4
5
6
7
8
9
10
Input: n, w1,…,wN, v1,…,vN
for w = 0 to W
   M[0, w] = 0
for i = 1 to n
   for w = 1 to W
      if (wi > w)
         M[i, w] = M[i-1, w]
      else
         M[i, w] = max {M[i-1, w], vi + M[i-1, w-wi ]}
return M[n, W]

image-20231208202150974

时间复杂度

时间复杂度为 $\Theta(n W)$

最长子序列

image-20231208202351529

结构

image-20231208202553476

递归结构

image-20231208203024712

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Algorithm lcsLength(x,y,b)
1: m<-x.length;
2: n<-y.length;
3: m[i][0]=0; m[0][i]=0;
4: for (int i = 1; i <= m; i++)
5:    for (int j = 1; j <= n; j++) 
6:       if (x[i]==y[j]) 
7:           m[i][j]=m[i-1][j-1]+1;
8:           b[i][j]=1;
9:        else if (m[i-1][j]>=m[i][j-1]) 
10:          m[i][j]=m[i-1][j];
11:          b[i][j]=2;
12:      else 
13:           m[i][j]=c[i][j-1];
14:           b[i][j]=3;
1
2
3
4
5
6
7
8
9
10
11
构造最长公共子序列
Algorithm lcs(int i,int j,char [] x,int [][] b)
   {
      if (i ==0 || j==0) return;
      if (b[i][j]== 1){
        lcs(i-1,j-1,x,b);
        System.out.print(x[i]);
        }
      else if (b[i][j]== 2) lcs(i-1,j,x,b);
        else lcs(i,j-1,x,b);
   }

image-20231208204304688

时间复杂度

由于每个数组单元的计算耗费$O(1)$时间，算法LCSLength耗时$O(mn)$.

序列对齐

概念

image-20231208205556675

编辑距离

image-20231208205630884

问题结构

image-20231208205754456

image-20231208205851237

动态规划算法

image-20231208205956022

时间复杂度

时间复杂度为$O(n^2)$

参考：

董强老师ppt