数据结构代码整理

2021-09-23

前几天朋友说三天可以过完一科,最开始不信,现在相信了。

线性表部分

  • 顺序表的建立、删除和插入节点
//2021.09.18
//表结构
typedef  struct  sqlist
{   
    ElemType  elem_array[MAX_SIZE] ;
	int    length ;
} SqList ;
//初始化
int Init_SqList( SqList *L ) 
{  
    L->elem_array=(int*)malloc(100*sizeof(int)) ;//数组的大小为100,不够可以用realloc再分配
	if ( !L -> elem_array ) 
        return  -1 ; 
	else {  
        L->length= 0 ;    
        return 1 ;  
    }  
}
//插入节点
int Insert_SqList(Sqlist *L,int i ,ElemType e)//数组可直接用下标进行操作,故不必用返回值再赋值一次
 {  
    int j ;
	if  ( i<1||i>L->length)   
        return  -1 ;
	if  (L->length>=MAX_SIZE)
	{    
        printf(“线性表溢出!\n”);  
        return  -1 ;  
    }
    for  ( j=L->length–1; j>=i-1; --j )
    	L->Elem_array[j+1]=L->Elem_array[j];
    /*  i-1位置以后的所有结点后移  */
    L->Elem_array[i-1]=e;    /*  在i-1位置插入结点  */
    L->length++ ;
    return  OK ;  
}
//删除节点,直接覆盖就行
int  Delete_SqList(Sqlist *L,int i)
{  
    int  k ;   
    int  x ;//返回被删除的值
	if  (L->length==0)
	{  
        printf(“线性表L为空!\n”); 
        return -1000;//假设表中值绝对值小于1000
    } 
	else if ( i<1||i>L->length ) 
	{  
        printf(“要删除的数据元素不存在!\n”) ; 
		return -1000 ; }
    else  {  x=L->Elem_array[i-1] ;   /*保存结点的值*/
        for ( k=i ;  k<L->length ; k++) 
              L->Elem_array[k-1]=L->Elem_array[k];
                     /*  i位置以后的所有结点前移  */
        L->length--; 
        return (x);
    }
} 
  • 链表的建立(头插法、尾插法)、插入、删除节点
//20210920
//节点结构
typedef  struct  Lnode
{
    int  data;     /*数据域,保存结点的值 */
	struct   Lnode  *next;      /*指针域*/
}LNode;

//头插法建表
LNode *CreateListHead(LNode *L,ElemType a[],int n){
     LNode *s;
     L=(LNode *)malloc(sizeof(LNode));//创建头结点,其data位为空
     L->next=NULL;   //将头结点next域置空
     for(int i=0;i<n;i++){   //循环建立数据结点
         //创建数据结点*s
         s=(LNode *)malloc(sizeof(LNode));
         //将每个新结点s插入到头结点之后
         s->data=a[i];
         s->next=L->next;
         L->next=s;
     }
     return L;//要将操作过的指针作为参数返回
     //C++中可以将指针作为引用传入,可直接修改数值,所以不用再作为返回值重新赋值
     //但C语言必须返回
};

//尾插法建表
LNode *CreateListTail(LNode *L,ElemType a[],int n){
     LNode *s,*r;
     L=(LNode *)malloc(sizeof(LNode));//创建头结点
     L->next = NULL; //将头结点next域置空
     r=L;//r始终指向尾结点,开始时头结点和尾结点是同一个

     for(int i=0;i<n;i++){
       s=(LNode *)malloc(sizeof(LNode));//创建数据结点
       s->data=a[i];//数据域
       r->next=s;//将s插入到r后
       r=s;//使r指向尾结点
     }
     r->next=NULL;//尾指针指针域置空
    //若要在循环内将s->next每次都置空,则要多次进行无意义的赋值,大可不必
     return L;
};

//插入节点
void insertLNode(LNode *L,int n,int data)
{
    LNode *s=L;
    int j=0;
    LNode *p=(LNode *)malloc(sizeof(LNode));
    p->data=data;
    while((j<n-1)&&(s!=NULL)&&(s->next!=NULL))
    //确保s->next不为空,避免s=NULL的赋值。
    //在最后一次判断中s->next!=NULL没意义,因为j=n-1了
    {
        s=s->next;
        j++;
    }//循环结束后,s指向了第n-1个节点
    if(j!=n-1)//循环提前退出,即节点数小于n-1
        printf("插入位置不合适,%d\n",j);
    else
    {
        p->next=s->next;
        s->next=p;
    }
}

//删除指定位置节点
void deleteLNode(LNode *L,int n)
{
    LNode *s=L;
    LNode *p=L->next;
    int j=0;
    while((j<n-1)&&(s!=NULL)&&(p!=NULL))
    {
        s=p;
        p=p->next;
        j++;
    }
    if(j!=n-1)//节点数小于n-1
        printf("删除位置不合适,%d\n",j);
    else
    {
        s->next=p->next;
        free(p);
    }
}

/*之前写过*/
//链表的合并
//链表的倒叙
//链表一元多项式和相加

栈和队列

//代码之前写过,没啥东西

  • 二叉树
//存储
数组存储,根节点下标为1,左子树下标为2*i,右子树下标为2*i+1,子树为空则空出数组中的位置

typedef struct BTNode//二叉链表存储
{  
    int  data ;
	struct BTNode  *Lchild , *Rchild ;
}BTNode ; 

typedef struct BTNode_3//三叉链表存储
{  
    int  data ;
	struct BTNode_3  *Lchild , *Rchild , *parent ;
}BTNode_3 ; 

/******************************
遍历:
分为递归和非递归
也可分为先序、中序、后序、层序
也可分为深度优先(先、中、后序)和广度优先遍历(层序)
*****************************/
//先序遍历
void  PreorderTraverse(BTNode  *T)//递归写法
{  
    if  (T!=NULL) 
    {  
        visit(T->data) ;       /*  访问根结点的数据域,具体操作看visit的定义  */
        PreorderTraverse(T->Lchild) ;
        PreorderTraverse(T->Rchild) ;     
    }
}
Void preOrder(BiTree T)//非递归写法
//BiTree是结构体指针,定义出的是指针变量  
{
	InitStack(S);//初始化栈
	BiTree p = T;
	while(p || !IsEmpty(S)){//判断条件是 或
		if(p){//一路向左下
			visit(p);
			Push(S,p);//入栈
			p = p->lchild;
		}else{
        //一般要连续执行多次,先弹出子树,直到p->rchild不为空
			p = Pop(S);//出栈
			p = p->rchild;
		}
	}
}

//中序遍历
void  InorderTraverse(BTNode  *T)//递归写法
{  
     if  (T!=NULL) 
    {  
        InorderTraverse(T->Lchild) ;
        visit(T->data) ;       /*   访问根结点   */
        InorderTraverse(T->Rchild) ;
    }
} 
Void InOrder(Bitree T)//非递归写法
{
	InintStack(S);
	Bitree p = T;
	while( p || !IsEmpty(S)){
		if(p){
			Push(S,p);
			p = p->lchild;
		}else{
            //左子树是在弹出时访问的
			p = pop(S);
			visit(p);
			p=p->rchild;
		}
	}
}

//后序遍历
void  PostorderTraverse(BTNode  *T)
{  
    if  (T!=NULL) 
    {  
        PostorderTraverse(T->Lchild) ;
        PostorderTraverse(T->Rchild) ; 
        visit(T->data) ;       /*  访问根结点  */ 
    }
} 
Void PostOrder(BiTree T)
{
	InitStack(S);  
    BiTree p = T;  
    BiTree r = NULL;//用于标记右子树有没有被访问
	while(p||!IsEmpty(S)){
		if(p){
			push(S,p);
            p = p->lchild;
		}
		else{
			p = GetTop(S);
			if(p->rchild&&p->rchild!=r)//当右子树存在且没有被访问
            {
				p=p->rchild;
			}
            else
            {
				pop(S,p);
				visit(p->data);
                r=p; 
                p=NULL;
			}
		}
	}
}

//层序遍历
#define MAX_NODE  50
void  LevelorderTraverse( BTNode  *T)
{  
    BTNode  *Queue[MAX_NODE] ,*p=T ;
    int  front=0 , rear=0 ;
    if  (p!=NULL) 
    {  
        Queue[++rear]=p;    /*   根结点入队  */
    	while (front<rear)
         {  
             p=Queue[++front];//出队操做,容易造成假溢出
             //+在前,先算加法
             visit( p->data );
             if (p->Lchild!=NULL)
                   Queue[++rear]=p->Lchild;  /*   左结点入队  */
             if (p->Rchild!=NULL)
                   Queue[++rear]= p->Rchild; /*   左结点入队  */
          }
    }
}
//层序遍历的递归算法不做要求
  • 线索二叉树的构建和访问
//N个节点,则有2N个指针域,N-1个指针域用于存放边,N+1个空闲指针域可用于对二叉树进行线索化
//左前驱,右后继
typedef struct BiThrNode
{   
    int  data;
    struct BiTreeNode *Lchild , *Rchild ; 
    int  Ltag , Rtag ;//value=1表示指向线索,value=0表示指向子树
}BiThrNode ;

//线索化二叉树
//主要分为先序、中序
//先序和中序,只是在遍历的visit(p->data)处加了线索化的操作

//递归先序线索化二叉树
void PreThread(ThreadTree p,ThreadTree pre)
{
    if(p){
        if(p->lchild == NULL){//左子树为空,建立前驱线索
            p->lchild=pre;
            p->Ltag=1;
        }
        if(pre!=NULL && pre->rchild==NULL){
            pre->rchild=p;//建立前驱结点的后继线索
            pre->Rtag=1;
        }
        pre=p;//标记当前结点成为刚刚访问过的结点
        if(p->Ltag != 1)
            //以1 2 3 NULL 4 5 6为例,在1和2处如果不判断会出现死循环
            //PreThread(1,2)->PreThread(1,2)(此时不会再线索化,只会pre=p,然后再下一次)->PreThread(1,2)
            //如果不判断ltag,则会死循环,
            PreThread(p->lchild,pre);//递归,线索化左子树
        if(p->Rtag != 1)
            PreThread(p->rchild, pre);//递归,线索化右子树
    }
}

//递归中序线索化二叉树
Void inThread(ThreadTree *p,ThreadTree *pre)//pre为直接前驱
{
	if(p!=NULL){
        //递归,线索化左子树
        //不会出现死循环,故无需判断
		inThread(p->lchild,pre);
		if(p->lchild==NULL){
			p->lchild = pre;
			p->Ltag = 1;
		}
		if(pre!=NULL&&pre->rchild==NULL){
			pre->rchild = p;
			pre->Rtag = 1;
		}
		pre = p;
        //递归,线索化右子树
		inThread(p->rchild,pre);
	}
}

//线索二叉树的遍历
//先序遍历先序线索二叉树
void preorder_Thread_bt(BiThrNode *T)
 {  
    BiThrNode  *p=T ;
	while (p!=NULL)
    {  
        visit(p->data) ;
        if (p->Ltag==0)  
            p=p->Lchild;
        else  
            p=p->Rchild;
        //若有右子树,则跳转到右子树
        //若没有左子树,也没有右子树,则跳转到直接后继
	}
} 
//中序遍历中序线索二叉树
ThreadNode *FirstNode(ThreadNode *p){//访问的节点,必然是左子树的最深层左子树
	//有左子树返回左子树,否则返回自己
    while(p->ltag==0) 
        p = p->lchild;
	return p;
}
ThreadNode *Nextnode(ThreadNode *p){
	if(p->rtag==0) 
    //右子树存在,则返回其右子树的最深层左子树
        return Firstnode(p->rchild);
	else 
    //右子树不存在,返回直接后继
        return p->rchild;
}
Void Inorder(ThreadNode *T){
	for(ThreadNode *p = FirstNode(T);p!=NULL;p=NextNode(p))
		visit(p);
}
//存储结构
//双亲表示法
typedef  struct PTNode
{  
    int  data ;
 	int  parent ;
}PTNode ;
typedef  struct
{  
    PTNode  Nodes[MAX_SIZE] ;//用PTNode 数组存储
	int  root;    /*  根结点位置  */
	int  num ;   /*  结点数   */ 
}Ptree ;
//复合链表结构
typedef  struct  listnode
{   i
    nt   childno ;    /*  孩子结点编号  */
	struct listno  *next ;
}CTNode;    /*  表结点结构  */
typedef  struct
{  
    ElemType   data ;
	CTNode  *firstchild ;//叶子节点的孩子节点是NULL
}HNode;    /*  头结点结构  */
typedef  struct
{  
    HNode   nodes[MAX_NODE] ;//头节点数组,每一个数据元素都是头节点
	int  root;    /*  根结点位置  */
	int  num ;   /*  结点数   */
}CLinkList;    /*  复合链表结构  */
//孩子兄弟表示法(二叉树表示,左孩子,右兄弟)
typedef  struct   CSnode
{  int   data ;
	struct   CSnode *firstchild, *nextsibing ;
}CSNode;  


//树的遍历(先序、后序)
树的 先序遍历等同于将树转化为二叉树后的 先序遍历
树的 后序遍历等同于将树转化为二叉树后的 中序遍历
  • 哈夫曼树(节点定义、生成算法、哈夫曼编码算法)
//WPL  树的带权路径长度
//代码不要求
typedef struct
{     
    int Weight ;    /*  权值域  */
	int Parent , Lchild , Rchild ;
} HTNode ;

//生成算法,看看过程就行
void Create_Huffman(unsigned n, HTNode HT[ ], unsigned m)
/*  创建一棵叶子结点数为n的Huffman树  */
{  
    unsigned  int  w ;   int  k , j ;
    for (k=1 ; k<m ; k++)
    {   if  (k<=n)
        {  printf(“\n Please Input Weight : w=?”);
           scanf(“%d”, &w) ;HT[k].weight=w ;  
        }        /*  输入时,所有叶子结点都有权值  */
    	else  HT[k].weight=0;  /*  非叶子结点没有权值 */
     	HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0 ;
	}     /* 初始化向量HT */
    for (k=n+1; k<m ; k++)//从N+1开始是非叶子节点
    {   
        unsigned w1=32767 , w2=w1 ;
          /*  w1 , w2分别保存权值最小的两个权值  */
     	int  p1=0 , p2=0 ;
         /*  p1 , p2保存两个最小权值的下标  */
    	for (j=1 ; j<=k-1 ; j++)//找集合中权值最小的两个节点
        {   
        	if (HT[k].Parent==0)    /* 尚未合并 ,相当于排除掉已经合并过的节点*/
         	{   
                if (HT[j].Weight<w1)
                {   
                    w2=w1 ; 
                    p2=p1 ;
                    w1=HT[j].Weight ; 
                    p1=j ;  
                 }
				else if (HT[j].Weight<w2)
                 {  
                	w2=HT[j].Weight ;  
                    p2=j ;   
                }
     		}    /*  找到权值最小的两个值及其下标  */
		}
        HT[k].Lchild=p1 ; HT[k].Rchild=p2 ;
        HT[k].weight=w1+w2 ;
        HT[p1].Parent=k ; HT[p2].Parent=k ; 
    }
}

//编码过程,看看就行
void Huff_coding(unsigned n , HTNode HT[] , unsigned m)
/*  m应为n+1,编码的最大长度n加1 */
{  
    int  k , sp ,fp ;//当前叶子下标,当前编码下标,当前父节点下标
    char *cd , *HC[m] ;
    cd=(char *)malloc(m*sizeof(char)) ;
    /*  动态分配求编码的工作空间  */
    cd[n]=‘\0’    /*  编码的结束标志 */
    for (k=1 ; k<n+1 ; k++)
    {       /*  逐个求字符的编码    */
        for (  ; fp!=0 ;p=fp , fp=HT[p].parent)
        /*   从叶子结点到根逆向求编码  */ 
            if  (HT[fp].lchild==p)  cd[--sp]=‘0’ ;
            else  cd[--sp]=‘1’ ;
            HC[k]=(char *)malloc((n-sp)*sizeof(char)) ;
            /*  为第k个字符分配保存编码的空间 */
            strcpy(HC[k] , &cd[sp]) ;//这里很有趣,讲一下。
     }
    free(cd) ;
}
  • 二叉排序树

天勤查找章节

KMP

讲解:https://zhuanlan.zhihu.com/p/83334559 dp数组,和原算法有出入

// 暴力匹配(伪码)
//pat为模式串,txt为主串
int search(String pat, String txt) {
    int M = pat.length;
    int N = txt.length;
    for (int i = 0; i <= N - M; i++) {
        int j;
        for (j = 0; j < M; j++) {
            if (pat[j] != txt[i+j])
                break;
        }
        // pat 全都匹配了
        if (j == M) return i;//看j是否走完
    }
    // txt 中不存在 pat 子串
    return -1;
}


//首先得到next数组,其值与最大公共前后缀有关
//pat串从下标0处开始存储
//主串指针永不回退
void getNext()
{
  // next[j]的值比next[j-1]最多只能增长1
  // k表示确定本次next数组值,所需要比较的字母的下标
  // 每次给next[j]赋值时,pat[j-1]是需要比较的字母之一
  int j, k;//k表示数组值,j表示数组下标
  j = 0; k = -1; nxt[0] = -1;
  while(j < patlen)
    if(k == -1 || pat[j] == pat[k])
      nxt[++j] = ++k;
    else
      k = nxt[k];//回退
}

/*
返回模式串pat在主串S中首次出现的位置
返回的位置是从0开始的。
*/
int KMP_Index()
{
  int i = 0, j = 0;
  getNext();//得到pat串的next数组
  while(i < slen && j < patlen)
 {
    if(j == -1 || S[i] == pat[j])
   {
      i++; j++;
   }
    else
      j = nxt[j];
 }
  if(j == patlen)
    return i - patlen;
  else
    return -1;
}

/*
返回模式串在主串S中出现的次数
*/
int KMP_Count()
{
  int ans = 0;
  int i, j = 0;
  if(slen == 1 && patlen == 1)
 {
    if(S[0] == pat[0])
      return 1;
    else
      return 0;
 }
  getNext();
  for(i = 0; i < slen; i++)
 {
    while(j > 0 && S[i] != pat[j])
      j = nxt[j];
    if(S[i] == pat[j])
      j++;
    if(j == patlen)
   {
      ans++;
      j = nxt[j];//回退j再进行下一次的比较
   }
 }
  return ans;
}

查找

//平均查找长度:所有查找中进行关键字比较的平均次数

//顺序查找
int Search(int arr[],int n,int data)
{
  for(int i=0;i<n;i++)
 {
    if(arr[i]==data)
      return i;
 }
  return -1;
}

//折半查找
//arr数组必须是有序的
int BinarySearch(int arr[],int n,int x)
{
  int low=0;
  int high=n-1;
  int mid;
  while(low<=high)
 {
    mid=(low+high)/2;
    if(arr[mid]==x)
      return mid;
    else if(arr[mid]>x)
      mid=high-1;
    else
      low=mid+1;
 }
  return -1;
}

//分块查找
//又称索引查找
//无代码,块间有序,块内无序
  • 二叉排序树
/*
左子树的所有值都小于等于根的值
右子树的所有值都大于等于根的值
左右子树也符合上述两个条件
*/
typedef struct BTNode
{
  int key;//存放的数值
  struct BTNode *lchild;
  struct BTNode *rchild;
}BTNode;

//二叉排序树的查找
BTNode* BSTSearch(BTNode *bt,int key)
{
  if(bt==NULL)
    return NULL;
  else
 {
    if(bt->key==key)
      return bt;
    else if(key < bt->key)
      return BSTSearch(bt->lchild,key);
    else
      return BSTSearch(bt->rchild,key);
 }
}

//插入key到二叉排序树中
int BSTInsert(BTNode *bt,int key)
{
  if(bt==NULL)//插入为根节点
 {
    bt=(BTNode*)malloc(sizeof(BTNode));
    bt->lchild=bt->rchild=NULL;
    bt->key=key;
    return 1;
 }
  else
 {
    if(key == bt->key)
      return 0;//默认无相同元素,所以不插入
    else if(key < bt->key)
      return BSTInsert(bt->lchild,key);
    else
      return BSTInsert(bt->rchild,key);
 }
}

//删除节点
/*
(1)p结点是叶子结点:直接删除
(2)p结点无左子树或无右子树:直接删除p后将p的子树连上p的父节点
(3)p结点既有左子树又有右子树:在p的左子树中,一直往右找,也就是找p的【左子树中的最大值】,替换
掉p点,然后接上p的左右子树
*/
  • 平衡二叉树

如何调整

  • B树

如何调整

  • 散列表

不写代码

  • 有向图中的概念

image-20210922153329858

image-20210922153423460

image-20210922153441025

  • 图的存储
//邻接矩阵
#define MaxSize 100
typedef char VertexType;
typedef int EdgeType;
typedef struct{
  VertexType Vex[MaxSize]; //存储顶点信息,如A、B、C、D
  EdgeType Edge[MaxSize][MaxSize]; //存储图的边或边的权值
  int vexNum,arcNum; //点的个数和边的个数
}MGraph;

//邻接表
#define MaxSize 100
typedef char VertexType;
typedef int EdgeType;
typedef struct ArcNode{//边类型
  int adjvex;//边指向的节点
  struct ArcNode *next;
  int info; //边的权值
}ArcNode;
typedef struct//点类型
{
  VertexType data;
  ArcNode *firstarc;//下一条边
}VNode;
typedef struct//图类型
{
  VNode adjlist[MaxSize];
  int vexNum,arcNum; //点的个数和边的个数
}AGraph;
//具体实例如下图

image-20210922163041678

十字链表

有箭头的一边表示 弧头

image-20210922161725104

顶点节点:数据域、第一个入度节点、第一个出度节点

弧节点: 弧尾、弧头、相同弧头节点、相同弧尾节点、权值

image-20210922162054333

邻接多重表

image-20210922162409552

Mark为标志位,表示该边有没有被访问过

  • 图的遍历

深搜和广搜与存储结构基本没有关系

邻接表广搜

while(!QueueEmpty(&Q))
{ //队非空则执行
i=DeQueue(&Q); //相当于vi出队
p=G->adjlist[i].firstedge; //取vi的边表头指针
while§
{ //依次搜索vi的邻接点vj(令p->adjvex=j)
if(!visited[p->adjvex])
{ //若vj未访问过
Visit(p->adjvex); //访问vj
visited[p->adjvex]=TRUE;
EnQueue(&Q,p->adjvex); //访问过的vj人队
}
p=p->next; //找vi的下一邻接点
}
}

邻接矩阵深搜
for (int i=1;i<=n;i++)

​ if (!visited[i])

​ dfs(i);

//广搜-----邻接矩阵
int visit[MaxSize];//全局变量,开始都为0
void BFS(AGraph *G,int v) //从v点开始广搜图
{
  InitQueue(Q); //初始化队列
  visit[v]=1;//修改标志位
  Visit(v);
  Enqueue(Q,v);
  while(!isEmpty(Q))
 {
    DeQueue(Q,v);//队首点弹出
    for(int i=1;i<=VexNum;i++)
   {
      if(G.Edge[v][i]==1&&!visit[i])//如果v点到i点存在边 且i点未访问过
     {
        Visit(i);
        visit[i]=1;
        Enqueue(Q,i);
     }
   }
 }
}
//有可能不是连通图,因此要BFS每一个连通分量
void BFSGraph(AGraph *G)
{
  for(int i=1;i<=G.VexNum;i++)
    visit[i]=0;
  for(int i=1;i<=G.VexNum;i++)
 {
    if(!visit[i])
      BFS(G,i);
 }
} 



//深搜-----邻接表
int visit[MaxSize];
void DFS(AGraph *G,int v)
{
  ArcNode *p
  visit[v]=1;
  Visit(v);
  p=G->adjlist[v].firstarc; //从v的第一条边开始
  while(p!=NULL)
 {
    if(visit[p->adjvex]==0)
      DFS(G,p->adjvex);
    p=p->nextarc;
 }
}
  • 最小生成树(连通但不存在回路的图)

仅存在于无向图中

//加点法----Prim算法/普里姆算法
const int INF=1e9+7;
const int MAXN=110;
bool vis[MAXN]; //标记顶点是否加入最小生成树
int lowc[MAXN]; //存每个点加入最小生成树的最小花费
//点是 从0 到n-1
int Prim(int Graph[][MAXN],int n)
{
  int ans=0;
  memset(vis,false,sizeof(vis)); //初始化数组,全部初始化为false
  vis[0]=true; //第0个点首先加入
  for(int i=1;i<n;i++)
    lowc[i]=Graph[0][i]; //初始化每个点加入最小生成树的花费为 从该点到0的距离
  for(int i=1;i<n;i++)//循环n-1次,每次添加一个点到生成树中
 {
    int minc=INF; //初始化最小花费为 无穷大
    int p=−1; //定义要加入最小生成树的顶点
    for(int j=0;j<n;j++)
      if(!vis[j]&&minc>lowc[j]) //在所有未加入最小生成树的顶点中,找到距离最小生成树花费最小的点
     {
        minc=lowc[j];
        p=j;
     }
    if(minc==INF)
      return −1;//原图不连通
    ans+=minc; //答案加上 加入p点的花费
    vis[p]=true; //更改标记
    for(int j=0;j<n;j++)
      if(!vis[j]&&lowc[j]>Graph[p][j]) //对于剩下所有没有加入最小生成树的点,更新加入最小生成树的花费
        lowc[j]=Graph[p][j];
 }
  return ans;
}


//加边法----Kruskal算法/克鲁斯卡尔算法
//默认图是连通的
int n,m; //n个点,m条边
int pre[MAX]; //每个点所在连通图的标志点
struct edge //边
{
  int from,to; //边的左右连接的两个点
  int len; //边的权值或长度
};
edge arr[MAX]; //边数组
bool cmp(edge a,edge b) //比较函数,按照边长从小到大排序
{
  return a.len<b.len;
}
int Find(int x) //并查集查找函数,用了路径压缩
{
  if(pre[x]==x) return x;
  return pre[x]=Find(pre[x]);//直到找到pre[x]=x为止,也就是所有生成树的父节点
  //实现了路径压缩
}
int main()
{
  cin>>n>>m;
  for(int i=0;i<m;i++)
 	cin>>arr[i].from>>arr[i].to>>arr[i].len;
  sort(arr,arr+m,cmp);
  for(int i=1;i<=n;i++) //初始化,每个点都是单独的连通图
    pre[i]=i;
  int pFrom,pTo;
  int ans=0;
  for(int i=0;i<m;i++)
 {
    pFrom=Find(arr[i].from); //查找左边的点所在连通图的标志点
    pTo=Find(arr[i].to); //查找右边的点所在的连通图的标志点
    if(pFrom!=pTo) //当前边所连接的两个点不在同一个连通图
   {
      ans+=arr[i].len;
      pre[pFrom]=pTo; //把左边的点所在的连通图加入右边
   }
 }
  cout<<ans<<endl;
  return 0;
}
  • 最短路
//Floyd算法------暴力算法
//总共有n个顶点,graph是原图 dis是记录最短路的结果
//假设原来存放了最短路的结果
void Floyd(int n,int graph[][],int dis[][])
{
  for(int k=1;k<=n;k++)
 {
    for(int i=1;i<=n;i++)
   {
      for(int j=1;j<=n;j++)
     {
        dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
     }
   }
 }
}


//Dijkstra算法
int n; //n个点
int m; //m条边
int G[MaxSize][MaxSize]; //矩阵存图
int MinDis[MaxSize]; //出发点到其他点的最短距离
bool vis[MaxSize]; //标记当前节点是否已经最近无法更新
void Init() //初始化
{
    for(int i=1;i<=n;i++)
    {
        vis[i]=0;
        for(int j=1;j<=n;j++)
        	G[i][j]=MaxInt;//全部是最大值
    }
}
void djs(int index) //index表示出发点
{
    vis[index]=1;
    for(int i=1;i<=n;i++)
        MinDis[i]=G[index][i];
    int time=0; //更新的次数
    while(time<n)
    {
        int node;
        int MinNum=MaxInt;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&MinDis[i]<MinNum)
            {
            	MinNum=MinDis[i];
            	node=i;//下一个出发的节点
            }
        }
        vis[node]=1;
        for(int i=1;i<n;i++)
        {
            if(!vis[i]&&MinDis[i]>MinDis[node]+G[node][i])
            {
            	MinDis[i]=MinDis[node]+G[node][i];
            }
        }
        time++;
	}
}
int main()
{
    scanf("%d%d",&n,&m);
    Init();
    int x,y,dis;
    for(int i=0;i<m;i++)//输入边
    {
        scanf("%d%d%d",&x,&y,&dis);
        G[x][y]=G[y][x]=dis;
    }
    djs(1);//求1点到其它点的最短路径
    for(int i=2;i<=n;i++)
        cout<<MinDis[i]<<endl;
    return 0;
}
  • 拓扑排序(AOV网)
//退出条件:删除完全部节点,或出现环
//如何判断环?  通过count计数

//要事先建立一个indegree[]数组,统计所有顶点的入度
bool TopologicalSort(Graph G){
  InitStack(S);
  for(int i=0;i<G.vexNum;i++)
    if(indegree[i]==0)
      Push(S,i); //将所有入度为0的顶点入栈
  int count=0;
  while(!IsEmpty(S)){
    Pop(S,i);
    print[count++]=i;//先赋值到print数组,后自增
    for(p=G.vertice[i].firstarc;p;p=p->nextarc){
      v=p->adjvex;
      if(!(--indegree[v]))//如果删掉i节点后,v的入度为0
        Push(S,v);
   }
 }
  if(count<G.vexNum)//栈为空,遇到环了
    return false;
  else
    return true;
}
  • 关键路径(AOE网)

不要求代码

关键路径执行完后,图中所有时间全都执行完了

AOE网:
1.只有某顶点所代表的事件发生后,从该顶点出发的各条边的活动才能开始。
2.只有所有指向该顶点的边的活动都结束,该顶点的事件才开始。
3.只存在一个入度为0的顶点,称为源点,一个出度为0的顶点,称为汇点。

沿着汇点,【逆序找最大值】形成的路径就是关键路径

求出事件的最早开始时间VE 和最晚开始时间VL

求出活动的最早开始时间E 和最晚开始时间L

L-E=0的活动即为关键活动

关键活动连接而成的路径即为关键路径(没有时间余量的活动)

排序

不需要写代码:希尔排序、基数排序、外排序

需要代码:直接插入排序、折半插入排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、计数排序

计数排序和基数排序都称作桶排序,但二者思想不同

/*
直接插入排序
时间复杂度:O(N^2)
空间复杂度:O(1)
稳定性:稳定
*/
void straight_insert_sort(Sqlist *L)//升序排列    
{   
    int i, j ;
    for (i=2; i<=L->length; i++)//下标0处用作哨兵
    {  
        L->R[0]=L->R[i]; /*   设置哨兵   */
        j=i-1;
        /*
        while循环作用:
        第i个元素和前面的逐一比较,然后位移
        最终j+1就是要插入的位置
        */
        while( L->R[0].key < L->R[j].key )//查找插入位置,若最终没找到,会停在哨兵前面
        {   
            L->R[j+1]=L->R[j];
            j--;
        }          /*   查找插入位置   */
        L->R[j+1]=L->R[0];      /*   插入到相应位置   */
    }
}
//降序排列:
//只需将while循环的条件改为 vL->R[0].key > L->R[j].key


/*
折半插入排序  
时间复杂度:O(N^2)  减少了比较次数,但未减少移动次数
空间复杂度:O(1)
稳定性:稳定
*/
void Binary_insert_sort(Sqlist *L)//升序排列
{ 
    int i, j, low, high, mid ;
    for (i=2; i<=L->length; i++)
    {  
        L->R[0]=L->R[i];      /*   设置哨兵   */
        low=1 ; 
        high=i-1 ; 
        while (low<=high)
        {  
            if ( L->R[0].key < L->R[mid].key)
            	high=mid-1 ;
         	else   
                low=mid+1 ;
        }       /*   查找插入位置   */
        for (j=i-1; j>=high+1; j--)//移动,空出待插入位置
            L->R[j+1]=L->R[j]; 
        L->R[high+1]=L->R[0];  /*   插入到相应位置   */
    }
}
//降序:将while循环中if判断条件改成【大于号】即可


/*
冒泡排序
时间复杂度:O(N^2)
空间复杂度:O(1)
稳定性:稳定的
*/
void Bubble_Sort(Sqlist *L)
{  
    int j ,k ;
    for (j=0; j<L->length; j++)       /*   共有n-1趟排序   */
    {
        for (k=1; k<=L->length-j; k++)   /*   一趟排序   */
            //k<length-j
            if (LT(L->R[k+1].key, L->R[k].key ) )
            {
                 L->R[0]=L->R[k] ; 
                 L->R[k]=L->R[k+1] ; 
                 L->R[k+1]=L->R[0] ;  
            }
    }
}
//LT中为【小于号】是升序,【大于号】为降序


/*
快速排序
时间复杂度:O( nlog2(N) )  //一趟快排为O(N),因为三个循环加起来只有N次;共有log2(N)次一趟快排
空间复杂度:O( log2(N) )  //递归需要堆栈辅助,最深可以深入到log2(N)层,然后开始弹出
稳定性:不稳定
*/
int  quick_one_pass(Sqlist  *L , int low, int high)//一趟快速排序
{  
    int i=low, j=high ;
    L->R[0]=L->R[i] ;       /*   R[0]作为临时单元和哨兵  */
    do
        //以升序为例,将大于R[i] 的值放在其右侧,小于R[i]的值放在其左侧
        //利用双指针进行双向查找
    {  
        while (LQ(L->R[0].key, L->R[j].key)&&(j>i))
         j-- ;
        if  (j>i)  
        	{  L->R[i]=L->R[j] ; i++;   }
        //此时R[i]的值被保存到R[0],R[i]可视为空,故直接赋值
        while (LQ(L->R[i].key, L->R[0].key)&&(j>i))
              i++ ;
        if  (j>i)  
        	{  L->R[j]=L->R[i] ; j--;   }
        //此时R[j]的值已经被保存到了【前一步】的R[i],故也可直接赋值
    } while(i!=j) ;    /*   i=j时退出扫描  */
    L->R[i]=L->R[0] ; 
    Return i ;//返回值为分界点
}
void  quick_Sort(Sqlist  *L , int low, int high)//递归实现快排
{  
    int k ;
    if  (low<high) 
    {  
        k=quick_one_pass(L, low, high);
        quick_Sort(L, low, k-1);
        quick_Sort(L, k+1, high);
    }     /*   序列分为两部分后分别对每个子序列排序   */
}


/*
简单选择排序/直接选择排序
时间复杂度:O(N^2)
空间复杂度:O(1)
稳定性:不稳定
*/
//以升序为例,降序每次选择最小值即可
/*
不稳定原因:
以{80,80(重),70}为例,排序后,结果为{70,80(重),80},两个80交换了顺序
*/
void simple_selection_sort(Sqlist *L)
{  
    int m, n , k;
    //k为要和R[0]交换的位置
    for (m=1; m<L->length; m++)
    {  
        k=m ; 
        for  (n=m+1; n<=L->length; n++)
            if  ( LT(L->R[n].key, L->R[k].key) )  
                k=n ;
        if  (k!=m)      /*   记录交换   */
            {  L->R[0]=L->R[m]; L->R[m]=L->R[k];
                L->R[k]=L->R[0];
             } 
        }
}


/*
计数排序
时间复杂度:O(N)
空间复杂度:O(N)
稳定性:不稳定
*/
//用计数的原理,只能对正整数进行排序,且有较多的空间冗余
void bucketSort(int[] arr) {
   if (arr == null || arr.length < 2) {
      return;
   }
   int max = Integer.MIN_VALUE; //保证max比数组中任何一个数都小
   //将max变为数组中的最大值
   for (int i = 0; i < arr.length; i++) {//将max和arr[i]中的较大值赋值给max
      max = Math.max(max, arr[i]);
   }
   int[] bucket = new int[max + 1];
   //将数组中的元素依次放入对应的桶
   for (int i = 0; i < arr.length; i++) {
      bucket[arr[i]]++;
   }
   int i = 0; //指向原数组,用于往数组中放入桶中的数据
   for (int j = 0; j < bucket.length; j++) {
      while (bucket[j]-- > 0) { //将每一个桶中的数据全部取出
         arr[i++] = j;
      }
   }
}



/*
归并排序
时间复杂度:O( nlog2(N) )
空间复杂度:O(N)
稳定性:稳定
*/
void MergeSort_UptoDown(int *num, int start, int end)
 /* 将序列对半拆分直到序列长度为1*/   
{
    int mid = start + (end - start) / 2;
    if (start >= end)
    {
        return;
    }
    MergeSort_UptoDown(num, start, mid);
    MergeSort_UptoDown(num, mid + 1, end);
    //递归到最底层后开始合并,此时start=mid; mid+1=end
    Merge(num, start, mid, end);
}
void Merge(int *num, int start, int mid, int end)
{
    int *temp = (int *)malloc((end-start+1) * sizeof(int)); //申请空间来存放两个有序区归并后的临时区域
    int i = start;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= end)
    {
        if (num[i] <= num[j])
        {
            temp[k++] = num[i++];
        }
        else
        {
            temp[k++] = num[j++];
        }
    }
    while (i <= mid)//如果i还有剩余
    {
        temp[k++] = num[i++];
    }
    while (j <= end)
    {
        temp[k++] = num[j++];
    }
    //将临时区域中排序后的元素,整合到原数组中
    for (i = 0; i < k; i++)
    {
        num[start + i] = temp[i];
    }
    free(temp);
}


/*
堆排序
时间复杂度:O( nlog2(N) )
空间复杂度:O(1)
稳定性:不稳定
*/
//堆:完全二叉树、父节点的关键字 > 子节点的关键字
//heap堆  heapify堆调整
//从倒数第二层开始做heapify,就能把二叉树变成堆
//从最后一个节点的parent节点开始,倒着做heapify,即可将一个混乱的树构建成堆
//从最后一个节点开始,与根节点交换、脱离堆、然后再heapify调整堆,经过n-1次调整,就能实现堆排序

//参考灯神的代码
int tree[]={10,4,5,6,7,8};//注意,从0开始计数,显然第i个节点父母的坐标为(i-1)/2,左孩子下标为2*i+1,右孩子下标为2*i+2
void swap(int tree[],int i,int j)
{
    int temp=tree[i];
    tree[i]=tree[j];
    tree[j]=temp;
}

void heapify(int tree[],int n,int i)
{
    if(i >= n)//递归的出口
        return ;
    int c1=2*i+1;
    int c2=2*i+2;
    int max=i;//随便给一个最大值
    if(c1<n && tree[c1]>tree[max])
        max=c1;
    if(c2<n && tree[c2]>tree[max])
        max=c2;
    if(max != i)//找到最大值,需要做交换
    {
        swap(tree,max,i);
        heapify(tree,n,max);//对交换之后的堆再做调整
    }
}

void build_heap(int tree[],int n)
{
    int last_node=n-1;//最后一个节点
    int parent=(last_node-1)/2;
    int i;
    for(i=parent;i>=0;i--)
    {
        heapify(tree,n,i);//从最后一个节点的父节点开始,
    }
}

void heap_sort(int tree[],int n)
{
    build_heap(tree,n);
    int i;
    for(i=n-1;i>=0;i--)
    //实现最后一个节点和根节点交换,砍断,然后堆调整
    {
        swap(tree,i,0);
        heapify(tree,i,0);//通过i的递减,控制了每次堆调整时【堆的大小】,模拟了【砍断】的效果
    }
}

堆的表示(用数组)

堆排序(heapsort)_哔哩哔哩_bilibili

image-20210923190738930

代码尝试

sizeof
//关于sizeof在外函数和main中的用法
void Fun(int arr[])
{
    for(int i=0;i<sizeof(arr)/sizeof(int);i++)
        arr[i]=1;
}
int main()
{
    int arry[8]={0};
    Fun(arry);
    for(int i=0;i<sizeof(arry)/sizeof(int);i++)
        printf("%d\n",arry[i]);
    return 0;
}
/*输出:
1
1
0
0
0
0
0
0
*/
//在Fun函数中传入的是地址,不必再除int的大小
arry[++q]=1;
//究竟会赋值给谁
int q=1;
arry[q++]=1;  //结果:q=2;arry[1]=1;

int q=1;
arry[++q]=1;  //结果,q=2;arry[2]=1;

int q=1;
arry[q++]=q;  //结果,q=2;arry[1]=2;

int q=1;
arry[++q]=q;  //结果,q=2;arry[2]=2;
鲁ICP备2021033904号-1