数据结构

数据结构和刷题路径如下：

以下代码全部是关键代码，自己认证研读，一定可以搞懂的

1.线性表

线性表的顺序存储

1. 顺序线性表初始化

长度变为零，数组初始化。

typedef struct Sqlist
{
    int a[MAX_SIZE];
    int length;
}Sqlist;

//*线性表的初始化*/
int Init_Sqlist(Sqlist **list)
{
    (*list)->length=0;
}

2. 顺序线性表的插入

(1) 将线性表L中的第i个至第n个结点后移一个位置。 (2) 将结点e插入到结点ai-1之后。 (3) 线性表长度加1。

//*线性表的插入*/
int insert_Sqlist(Sqlist *list,int j,int e)
{
    if(j<0||j>list->length)
        return ERROR;
    for(int i=list->length;i>=j-1;i--)
    {
        list->a[i]=list->a[i-1];
    }
    list->a[j-1]=e;
    list->length++;
    return OK;
}

3. 顺序线性表的删除

(1) 将线性表L中的第i+1个至第n个结点依此向前移动一个位置。(2) 线性表长度减1。

//*线性表的删除*/
int delete_Sqlist(Sqlist *list,int i)
{
    if(list->length==0)
        return ERROR;
    for(int j=i;j<list->length;j++)
    {
        list->a[j-1]=list->a[j];
    }
    list->length--;
    return OK;
}

4. 顺序线性表的查找定位删除

(1) 在线性表L查找值为x的第一个数据元素。(2) 将从找到的位置至最后一个结点依次向前移动一个位置。 (3) 线性表长度减1。

//*线性表的定位删除*/
int Locate_Delete_Sqlist(Sqlist *list,int x)
{
    int i=0,j;
    while(i<list->length)
    {
        if(list->a[i]!=x)
            i++;
        else
        {
            break;
        }
    }
    if(i==list->length)
        return ERROR;
    for(j=i+1;j<list->length;j++)
    {
        list->a[j-1]=list->a[j];
    }
    list->length--;
    return OK;
}

线性表的链式存储

1 建立单链表

⑴ 头插入法建表

每次插入的结点都作为链表的第一个结点。

typedef struct Lnode
{
    int data;
    struct Lnode *next;
}Lnode;
//*  头插入链表   *//
Lnode* Creat_List()
{
    Lnode *head=NULL,*p;
    while(1)
    {
        int m;
        scanf("%d",&m);
        if(m==0)
            break;
        p=(Lnode *)malloc(sizeof(Lnode));
        p->data=m;
        p->next=head;
        head=p;
    }
    return head;
}

(2) 尾插入法建表

新结点插入到当前链表的表尾，使其成为当前链表的尾结点。

//*  尾插入链表   *//
Lnode* Creat_List()
{
    Lnode *head,*p,*q=NULL;
    head=(Lnode *)malloc(sizeof(Lnode));
    head->next=q;
    q=head;
    while(1)
    {
        int m;
        scanf("%d",&m);
        if(m==0)
            break;
        p=(Lnode *)malloc(sizeof(Lnode));
        p->data=m;
        q->next=p;
        q=p;
    }
    q->next=NULL;
    return head->next;
}

2 单链表的查找

(1) 按序号查找

int search_list(Lnode *head,int j)
{
  int i=0;
  Lnode *first;
  for(first=head;first!=NULL,i<j;first=first->next)
   {
        i++;
   }
   if(first!=NULL)
   {
       return first->data;
   }
   else
   {
       return 0;
   }
}

(2) 按值查找

int search_list(Lnode *head,int key)
{
  Lnode *first;
  for(first=head;first!=NULL;first=first->next)
   {
        if(first->data==key)
            return first->data;
   }
       return 0;
}

3 单链表的插入

Lnode* insert_Lnode(Lnode *head,int x,int key)
{
   Lnode *first,*q;
   int i=2;
   for(first=head;first!=NULL,i<x;first=first->next)
   {
       i++;
   }
   q=(Lnode *)malloc(sizeof(Lnode));
   q->data=key;
   if(i==1)
   {
       q->next=head;
        return q;
   }
   else
   {
           q->next=first->next;
           first->next=q;
   }
   return head;
}

4 单链表的删除

⑴ 按序号删除

Lnode* delete_Lnode(Lnode *head,int x)
{
    Lnode *cur,*prew;
    int i=1;
    for(cur=head,prew=NULL;cur!=NULL,i<x;prew=cur,cur=cur->next)
    {
        i++;
    }
    if(cur==NULL)
        return head;
    else if(prew==NULL)
        head=head->next;
        else
        {
            prew->next=cur->next;
            free(cur);
        }
        return head;
}

⑵ 按值删除

Lnode* delete_Lnode(Lnode *head,int x)
{
    Lnode *cur,*prew;
    for(cur=head,prew=NULL;cur!=NULL,cur->data!=x;prew=cur,cur=cur->next)
    {
       ;
    }
    if(cur==NULL)
        return head;
    else if(prew==NULL)
        head=head->next;
        else
        {
            prew->next=cur->next;
            free(cur);
        }
        return head;
}

5 单链表的合并

struct node *merge(struct node *first,struct node *list)
{
    struct node *p,*q,*r,*t;
    p=first;
    q=list;
    r=malloc(sizeof(struct node));
    t=r;
    while(p&&q)
    {
        if(p->date<q->date)                                  //< 这里必须要注意，并且要注意排序>;
        {
           t->next=p;
           t=p;
           p=p->next;

        }
        else
        {
           t->next=q;
           t=q;
           q=q->next;
        }
    }
    if(p)
    {
        t->next=p;
    }
    if(q)
    {
        t->next=q;
    }
    return r->next;
}

6. 循环链表

对于单循环链表，除链表的合并外，其它的操作和单线性链表基本上一致，仅仅需要在单线性链表操作算法基础上作以下简单修改：
⑴ 判断是否是空链表：head->nexthead ;
⑵ 判断是否是表尾结点：p->nexthead ;

#include <stdio.h>
#include <stdlib.h>

typedef struct node
 {
     int data;
     struct node *next;
 }Node;
 Node *creat_list()
 {
     Node *first,*second=NULL,*p;
     first=malloc(sizeof(Node));
     first->next=second;
     second=first;
     for(int i=0;i<3;i++)
     {
         int m;
         scanf("%d",&m);
         p=malloc(sizeof(Node));
         p->data=m;
         second->next=p;
         second=p;
     }
     second->next=first->next;
     return first->next;
 }

 int main()
 {
     Node *list=NULL,*q;
     list=creat_list();
     printf("%d ",list->data);
     for(q=list->next;q!=list;q=q->next)
     {
         printf("%d ",q->data);
     }
 }

7. 双向链表

void insert(struct node *list,int m,int n)
{
    struct node *p,*q;
    int i=1;
    q=(struct node *)malloc(sizeof(struct node));
    q->date=n;
    for(p=list->next;i<m&&p!=list;p=p->next)
    {
        i++;
    }
    if(p==list&&i<m)
    {
        printf("error");
    }
    else
    {
        q->prior=p->prior;
        p->prior->next=q;
        q->next=p;
        p->prior=q;
    }
}

双向链表的删除

p->prior->next=p->next;
p->next->prior=p->prior;
free§;
注意：
与单链表的插入和删除操作不同的是，在双向链表中插入和删除必须同时修改两个方向上的指针域的指向。

                                          栈和队列

2.栈和队列

1.栈的基本概念

栈(Stack)：是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO (Last In First Out) 的线性表。
栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针(top)来指示栈顶元素。
栈底(Bottom)：是固定端，又称为表头。
空栈：当表中没有元素时称为空栈。

2. 栈的顺序存储表示

栈的顺序存储结构简称为顺序栈，和线性表相类似，用一维数组来存储栈。

根据数组是否可以根据需要增大，又可分为静态顺序栈和动态顺序栈。

3.栈的基本操作

1.栈的类型定义

int top;
int bottom;
typedef struct stack
{
    int stack[10];
}Sqstack;

2.栈的初始化

void Init_stack(void)  //多余的
{
    top=0;
    bottom=0;
}

3.压栈(元素进栈)

void push(Sqstack *s,int x)
{
    if(top<10)
    {
    s->stack[top++]=x;
    }
    else
    {
        printf("stack full\n");
    }
}

4.栈(元素出栈

int pop(Sqstack *s)
{
    if(top!=bottom)
    {
        return s->stack[--top];
    }
    else
    {
        printf("stack empty\n");
        return 0;
    }
}

4.栈的链式存储表示

1.栈的初始化

typedef struct stack
{
     int data;
     struct stack *next;
}Stack_Node;
Stack_Node *Init_stack()
{
    Stack_Node *top;
    top=(Stack_Node *)malloc(sizeof(Stack_Node));
    top->next=NULL;
    return top;
}

2.压栈(元素进栈)

void Push_stack(Stack_Node **top,int x)
{
    Stack_Node *p;
    p=malloc(sizeof(Stack_Node));
    p->data=x;
    p->next=(*top)->next;
    (*top)->next=p;
}

3.栈(元素出栈

int Pop_stack(Stack_Node **top)
{
    Stack_Node *p=NULL;
    p=(*top)->next;
    if(p==NULL)
    {
        printf("stack empty");
        return 0;
    }
    else
    {
        int e=p->data;
        (*top)->next=p->next;
        free(p);
        return e;
    }

}

队列及其基本概念

1 队列的基本概念

​ 队列(Queue)：也是运算受限的线性表。是一种先进先出(First In First Out ，简称FIFO)的线性表。只允许在表的一端进行插入，而在另一端进行删除。
​ 队首(front) ：允许进行删除的一端称为队首。
​ 队尾(rear) ：允许进行插入的一端称为队尾。

2.循环队列的基本操作

1.循环队列的初始化

#define MAX_SIZE 30
typedef struct SqQueue
{
    int Queue[MAX_SIZE];
    int front;
    int rear;
}SqQueue;
void Init_Queue(SqQueue *Q)
{
    Q->front=0;
    Q->rear=0;
}

2.入队操作

int Insert_Queue(SqQueue *Q,int e)
{
    if((Q->rear+1)%MAX_SIZE==Q->front)
        return 0;
    Q->Queue[Q->rear]=e;
    Q->rear=(Q->rear+1)%MAX_SIZE;
    return 1;

}

3.出队操作

int Delete_Queue(SqQueue *Q)
{
    if(Q->front==Q->rear)
    {
        return 0;
    }
    int value=Q->Queue[Q->front];
    Q->front=(Q->front+1)%MAX_SIZE;
    return value;
}

3.链队列的基本操作

1.链队列的初始化

typedef struct Qnode
{
    int data;
    struct Qnode *next;
}Qnode;
typedef struct Queue
{
    Qnode *front,*rear;
}Queue;
void Init_list_Queue(Queue *Q)
{
    Q->front=malloc(sizeof(Qnode));
    Q->front->next=Q->rear=NULL;
    Q->rear=Q->front;
}

2.链队列的入队操作

int Insert_list_Queue(Queue *Q,int e)
{
    Qnode *p;
    p=malloc(sizeof(Qnode));
    if(!p)
        return 0;
    p->data=e;
    p->next=NULL;
    Q->rear->next=p;
    Q->rear=p;
    return 1;
}

3.链队列的出队操作

int delete_list_Queue(Queue *Q)
{
    Qnode *p;
    if(Q->front==Q->rear)
        return 0;
    p=Q->front->next;
    int m=p->data;
    Q->front->next=p->next;
    if(p==Q->rear)
        Q->rear=Q->front;
    free(p);
    return m;
}

3.串

串类型的定义

1. 串的基本概念

1.空串(空的字符串)：长度为零的串称为空串，它不包含任何字符。
2.空格串(空白串)：构成串的所有字符都是空格的串称为空白串 子串(substring)：串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。
3.子串的序号：将子串在主串中首次出现时的该子串的首字符对应在主串中的序号，称为子串在主串中的序号（或位置）。

1 串的联结操作

#include<stdio.h>
#include<string.h>

#define MAX_SIZE 256
typedef struct str
{
    char str[MAX_SIZE];
    int length;
}StringType;
int Strconcat(StringType *str1,StringType *str2)//插入并改变长度
{
    if(str1->length+str2->length>MAX_SIZE)
        return 0;
    for(int i=0;i<str2->length;i++)
    {
        str1->str[i+str1->length]=str2->str[i];
    }
    str1->length+=str2->length;
    return 1;
}

int main()
{
   StringType str1,str2;
   scanf("%s %s",str1.str,str2.str);
   str1.length=strlen(str1.str);
   str2.length=strlen(str2.str);
   Strconcat(&str1,&str2);
   printf("%s",str1.str);
}

2 求子串操作

#include<stdio.h>
#include<string.h>

#define MAX_SIZE 256
typedef struct str
{
    char str[MAX_SIZE];
    int length;
}StringType;
int Substring(StringType *str2,int left,int right,StringType *str3)//求子串操作
{
    if(right>str2->length||left<0)
        return 0;
    int i;
    for(i=left;i<right;i++)
    {
        str3->str[i-left]=str2->str[i];
    }
    str3->str[i-left]='\0';
    str3->length=right-left;
    return 1;
}
int main()
{
   StringType str2,str3;
   scanf("%s",str2.str);
   str2.length=strlen(str2.str);
   if(Substring(&str2,2,4,&str3))
   printf("%s",str3.str);
   else
   {
       printf("ERROR");
   }
}

3. 串的堆分配存储表示

 #include<stdio.h>
#include<string.h>

#define MAX_SIZE 256
typedef struct str
{
    char *str;
    int length;
}StringType;
int Strconcat(StringType *str1,StringType *str2,StringType *str3)//插入并改变长度
{
    str3->length=str2->length+str1->length;
    str3->str=malloc(sizeof(char)*str3->length);
    for(int i=0;i<str1->length;i++)
    {
        str3->str[i]=str1->str[i];
    }
    int i;
    for(i=0;i<str2->length;i++)
    {
        str3->str[i+str1->length]=str2->str[i];
    }
    str3->str[i+str1->length]
    return 1;
}

int main()
{
   StringType str1,str2,str3;
   str1.str=malloc(sizeof(char)*10);
   str2.str=malloc(sizeof(char)*10);
   scanf("%s %s",str1.str,str2.str);
   str1.length=strlen(str1.str);
   str2.length=strlen(str2.str);
   Strconcat(&str1,&str2,&str3);
   printf("%s",str3.str);
}

4.3 串的模式匹配算法

KMP算法如下

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void get_next(char *a,int *next)
{
    int i=0;
    next[0]=-1;
    int j=-1;
    int u=strlen(a);
    while(i<u)
    {
        if(j==-1||a[i]==a[j])
        {
            i++;
            j++;
            next[i]=j;
        }
        else
            j=next[j];
    }
}
int main()
{
    char a[100];
    int next[100];
    scanf("%s",a);
    int lena=strlen(a);
    get_next(a,next);
    for(int i=0;i<lena;i++)
    {
        printf("%d ",next[i]+1);
    }
}

4.数组和广义表

广义表是另一种推广形式的线性表，是一种灵活的数据结构
数组的定义
数组中的数据元素具有相同数据类型。
1.数组是一种随机存取结构，给定一组下标，就可以访问与其对应的数据元素。
2.数组中的数据元素个数是固定的。
矩阵的压缩存储

3. 多个相同的非零元素只分配一个存储空间；
   4. 零元素不分配空间。
   特殊矩阵
   1 对称矩阵
   k=i*(i-1)/2+j-1 i≧j
   k=j*(j-1)/2+i-1 i<j

5.二 叉 树 与 树

1.二 叉 树

1.二叉树的定义

二叉树(Binary Tree)是 n(n≥0)个数据元素的有限集合，该集合或者为空，或者由一个
称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。
此二叉树具有五种基本形态:A.是空树；B.是只有一个根结点的树；C.根节点只有左子树；D.根节点只
有右子树；E.根节点既有左子树又有右子树。

2.二叉树的基本概念

1.结点的层数及二叉树的深度:
2.特殊二叉树:满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶
子结点都在同一层上，这样的一棵二叉树称做满二叉树。

3.满二叉树的特点有

A. 叶子只能出现在最下一层。
B. 非叶子结点的度一定是 2。 C. 在同样深度的二叉树中，满二叉树的结点个数最多，叶子最多

4.完全二叉树的特点

1. 叶子结点只能出现在最下两层。 2. 最下层的叶子一定集中在左部连续位置。 3. 倒数二层若有叶子结点，一定都在右部连续位置。 4. 如果结点度为 1，则该结点只有左孩子，即不存在只有右孩子的情况。 4. 同样结点数的二叉树，完全二叉树的深度最小
   一棵非空二叉树的第 i 层上最多有 2i-1 个结点(i≥1)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct BINode             //树结构体
{
    char data;
    struct BINode *Lchild,*Rchild;
}BINode;

BINode* creat_Tree()      //创造树
{
    BINode *T,*q,*s[30];
    int i,j;
    while(1)
    {
        scanf("%d",&i);
        if(i==0)
            break;
        else
        {
            char ch;
            ch=getchar();
            q=(BINode *)malloc(sizeof(BINode));
            q->data=ch;
            q->Lchild=NULL;
            q->Rchild=NULL;
            s[i]=q;
        if(i==1)
        {
            T=q;
        }
        else
        {
             j=i/2;
            if(i%2==0)                  //这里需要注意
                s[j]->Lchild=s[i];
            else
                s[j]->Rchild=s[i];
        }
        }
    }
    return T;
}
void PreorderTraversal(BINode *T)        //先序遍历
{
    if(T==NULL)
        return;
    else
    {
        printf("%c ",T->data);
        PreorderTraversal(T->Lchild);
        PreorderTraversal(T->Rchild);
    }
}
void InorderTraversal(BINode *T)      // 中序遍历
{
     if(T==NULL)
        return;
    else
    {
        InorderTraversal(T->Lchild);
        printf("%c ",T->data);
        InorderTraversal(T->Rchild);
    }
}
void PostorderTraversal(BINode *T)     // 后序遍历
{
    if(T==NULL)
        return;
    else
    {
        PostorderTraversal(T->Lchild);
        PostorderTraversal(T->Rchild);
        printf("%c ",T->data);
    }
}
int main()
 {
    BINode *T;
    T=creat_Tree();
    PreorderTraversal(T);
    printf("\n");
    InorderTraversal(T);
    printf("\n");
    PostorderTraversal(T);
    printf("\n");
    return 0;
 }

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 30
typedef struct BINode             //树结构体
{
    char data;
    struct BINode *Lchild,*Rchild;
}BINode;
BINode* creat_Tree()      //创造树1111111111
{
     BINode *T,*q,*s[MAX_SIZE];
     int i,j;
     while(1)
     {
         scanf("%d",&i);
         if(i==0)
            break;
         else
         {
             char ch;
             ch=getchar();
             q=malloc(sizeof(BINode));
             q->data=ch;
             q->Lchild=NULL;
             q->Rchild=NULL;
             s[i]=q;
             if(i==1)
             {
                 T=q;
             }
             else
             {
                 j=i/2;
                 if(i%2==0)
                    s[j]->Lchild=s[i];
                 else
                    s[j]->Rchild=s[i];
             }
         }
     }
  return T;
}
void LevelorderTraverse(BINode *T)    //层次遍历（用队列）
{
    BINode *Queue[MAX_SIZE],*q;
    int top=0,bottom=0;
    q=T;
    if(q!=NULL)             //第一个入队列，以后的依次循环
    {
        Queue[bottom++]=q;
    }
    while(top<bottom)
    {
        q=Queue[top++];
        printf("%c ",q->data);
        if(q->Lchild!=NULL)
            Queue[bottom++]=q->Lchild;
        if(q->Rchild!=NULL)
            Queue[bottom++]=q->Rchild;
    }
    return;
}
int main()
 {
    BINode *T;
    T=creat_Tree();
    LevelorderTraverse(T);
    return 0;
 }

void Preorder_creat_Tree(BINode **T)      //先序遍历创造树22222222
{//这里必须是指向指针的指针
    char ch;
    ch=getchar();
    if(ch=='?')
    {
        *T=NULL;
        return;
    }
    else
    {
        *T=malloc(sizeof(BINode));
       (*T)->data=ch;
        Preorder_creat_Tree(&((*T)->Lchild));
        Preorder_creat_Tree(&((*T)->Rchild));
    }
}

//求叶子节点的个数
void Preorder_leaf(BINode *T)         
{
    if(T==NULL)
        return;
    else
    {
        if(T->Lchild==NULL&&T->Rchild==NULL)//中心语句
        {
            index++;
        }
        Preorder_leaf(T->Lchild);
        Preorder_leaf(T->Rchild);
    }
}

int Search_Depth(BINode *T) //层次遍历确定深度
{
    BINode *Queue[MAX_SIZE],*p;
    int top=0,bottom=0,leve,x=0;
    p=T;
    if(p!=NULL)
    {
        Queue[bottom++]=p;
        leve=bottom;
    }
    while(top<bottom)
    {
        p=Queue[top++];
        if(p->Lchild!=NULL)
            Queue[bottom++]=p->Lchild;
        if(p->Rchild!=NULL)
            Queue[bottom++]=p->Rchild;
        if(top==leve)             //leve指向最后一个，top等于最后一个层次就加一
        {
            x++;
            leve=bottom;
        }
    }
    return x;
}

6.图

图的定义和总类

1. 图的定义：图(graph)是一种网状数据结构，是由一个顶点(vertex)的有穷非空集 V(G)和一个弧(arc)

   的集合 E(G)组成，通常记作 G = (V，E)，其中 G 表示一个图，V 是图 G 中顶点的集合，E

   是图 G 中的弧的集合。

2. 图的总类：

   1. 无向图：若图中所有边都是不带方向的，则称该图是无向图。

   2. 有向图：若图中所有边都是有向的，则称该图是有向图。（在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图

      为有向完全图。在一个含有 n 个顶点的有向完全图中，有 n(n-1)条边。）

   3. 权、网或网络

   4. 顶点的度（顶点的度(degree)是指依附于某顶点 v 的边数，通常记为 TD(v)。在有向图中，要区别

      顶点的入度与出度的概念。顶点 v 的入度是指以顶点 v 为终点的弧的数目，记为 ID(v)；顶

      点 v 的出度是指以顶点 v 为始点的弧的数目，记为 OD(v)。有 TD(v) = ID(v) + OD(v)。）

   5. 路径和回路

   6. 子图

   7. 无向图邻接矩阵的特性
      ◆ 邻接矩阵是对称方阵；
      ◆ 对于顶点vi，其度数是第i行的非0元素的个数；
      ◆ 无向图的边数是上(或下)三角形矩阵中非0元素个数。

   8. 有向图邻接矩阵的特性
      ◆ 对于顶点vi，第i行的非0元素的个数是其出度OD(vi)；第i列的非0元素的个数是其入度ID(vi) 。
      ◆ 邻接矩阵中非0元素的个数就是图的弧的数目。

图的基本操作

(1) 顶点定位操作 LocateVex(G，v)：在图 G 中找到顶点 v，返回该顶点在图中的位置。

int LocateVex(Graph G,char v)
{
    int i=-1,k;
    for(k=0;k<G.vexnum;k++)
    {
        if(G.vex[k]==v)
        {
            i=k;
            break;
        }
    }
    return i;
}

(2) 取顶点操作 GetVextex(G，v)：在图 G 中找到顶点 v，并返回顶点 v 的相关信息。

int GetVextex(Graph G,char v)
{
    int i=-1,k;
    for(k=0;k<G.vexnum;k++)
    {
        if(G.vex[k]==v)
        {
            i=k;
            break;
        }
    }
    return i;
}

(3) 求第一个邻接点操作 FirstAdjVex(G，v)：在图 G 中，返回 v 的第一个邻接点。若

顶点 v 在 G 中没有邻接顶点，则返回“空”。

int Firstadjvex(Graph *G,int i)
{
    for(int j=0;j<G->vexnum;j++)
    {
        if(G->arc[i][j]==1&&visited[j]==0)
            return j;
    }
    return -1;
}

(4) 求下一个邻接点操作 NextAdjVex(G，v，w)：在图 G 中，返回 v 的(相对于 w 的)

下一个邻接顶点。若 w 是 v 的最后一个邻接点，则返回“空”。数据结构与算法设计

int Nextadjvex(Graph *G,int p,int i)
{
    for(int j=p+1;j<G->vexnum;j++)
    {
        if(G->arc[i][j]==1&&visited[j]==0)
            return j;
    }
    return -1;
}

(5) 插入顶点操作 InsertVex(G，v)：在图 G 中增添新顶点 v。

(6) 删除顶点操作 DeleteVex(G，v)：在图 G 中，删除顶点 v 以及所有和顶点 v 相关联

的边或弧。

(7) 插入弧操作 InsertArc(G，v，w)：在图 G 中增添一条从顶点 v 到顶点 w 的边或弧。

(8) 删除弧操作 DeleteArc(G，v，w)：在图 G 中删除一条从顶点 v 到顶点 w 的边或弧。

(9) 深度优先遍历图 DFSTraverse(G，v)：在图 G 中，从顶点 v 出发按深度优先对图中

每个结点访问一遍且仅一遍。

(1) 访问结点 v。

(2) 找到 v 的第一个邻接点 w。

(3) 如果邻接点 w 存在且未被访问，则从 w 出发深度优先遍历图；否则，结束。

(4) 找顶点 v 关于 w 的下一个邻接点，转(3)。

int visited[50];
int Firstadjvex(Graph *G,int i)
{
    for(int j=0;j<G->vexnum;j++)
    {
        if(G->arc[i][j]==1&&visited[j]==0)
            return j;
    }
    return -1;
}
int Nextadjvex(Graph *G,int p,int i)
{
    for(int j=p+1;j<G->vexnum;j++)
    {
        if(G->arc[i][j]==1&&visited[j]==0)
            return j;
    }
    return -1;
}
void DFS(Graph *G)
{
    for(int i=0;i<G->vexnum;i++)
    {
        visited[i]=0;
    }
    for(int i=0;i<G->vexnum;i++)
    {
        if(!visited[i])
        {
            Grephsearch(G,i);
        }
    }
}
void Grephsearch(Graph *G,int i)
{
    printf("%d ",i);
    visited[i]=1;
    int p;
    p=Firstadjvex(G,i);
    while(p!=-1)
    {
        if(!visited[p])
        {
            Grephsearch(G,p);
            p=Nextadjvex(G,p,i);
        }
    }
    return;
}

#include <stdio.h>
#include <stdlib.h>

#define MAX 10
int first[MAX]={0};
typedef struct node
{
    int vex;
    int adj[MAX][MAX];
}Graph;
void DFS(Graph G,int i)
{
    first[i]=1;
    printf("%d ",i);
    for(int j=0;j<G.vex;j++)
    {
        if(first[j]==0&&G.adj[i][j]==1)
            DFS(G,j);
    }
}
void DFSTrave(Graph G)
{
    for(int i=0;i<G.vex;i++)
    {
        if(first[i]==0)
            DFS(G,i);
    }
}
int main()
{
    Graph G;
    int i,j,k;
    scanf("%d",&G.vex);
    for(i=0;i<G.vex;i++)
    {
        for(j=0;j<G.vex;j++)
        {
            scanf("%d",&G.adj[i][j]);
        }
    }
    DFSTrave(G);
}

(10) 广度优先遍历图 BFSTraverse(G，v)：在图 G 中，从顶点 v 出发按广度优先对图

中每个结点访问一遍且仅一遍。

int visited[50];
int Queue[50];
int begin,end;
void DFS(Graph *G)
{
    for(int i=0;i<G->vexnum;i++)
    {
        visited[i]=0;
    }
    for(int i=0;i<G->vexnum;i++)
    {
        if(!visited[i])
        {
            Grephsearch(G,i);
        }
    }
}
void Grephsearch(Graph *G,int i)
{
    int k,v;
    printf("%d ",i);
    visited[i]=1;
    Queue[end++]=i;
    while(begin<end)
    {
        v=Queue[begin++];
        for(k=0;k<G->vexnum;k++)
        {
        if(visited[k]==0&&G->arc[v][k]==1)
        {
            printf("%d ",k);
            visited[k]=1;
            Queue[end++]=k;
        }
        }
    }
    return;
}

#include <stdio.h>
#include <stdlib.h>

#define MAX 50
int first[MAX]={0};
typedef struct node
{
    int vex;
    int adj[MAX][MAX];
}Graph;
void BFS(Graph G,int i)
{
    int Queue[MAX];
    int top=0,bottom=0;
    Queue[bottom++]=i;
    first[Queue[bottom-1]]=1;
    while(bottom>top)
    {
    for(int j=0;j<G.vex;j++)
    {
        if(first[j]==0&&G.adj[Queue[top]][j]==1)
        {
            Queue[bottom++]=j;
           first[Queue[bottom-1]]=1;  //一入队列就设置为1
        }
    }
        printf("%d ",Queue[top++]);
    }
}
void BFSTrave(Graph G)
{
    for(int i=0;i<G.vex;i++)
    {
        if(first[i]==0)
        {
            BFS(G,i);
        }
    }
}
int main()
{
    Graph G;
    int i,j;
    scanf("%d",&G.vex);
    for(i=0;i<G.vex;i++)
    {
        for(j=0;j<G.vex;j++)
        {
            scanf("%d",&G.adj[i][j]);
        }
    }
    BFSTrave(G);
    printf("\n");
}

图的存储结构

1. 邻接矩阵（图的邻接矩阵(Adjacency Matrix)存储结构，就是用一维数组存储图中顶点的信息，用

   矩阵表示图中各顶点之间的邻接关系。）

   #include <stdio.h>
   #include <stdlib.h>
   #include <string.h>
   #define INFE 78956
   #define MAXNODE 30
   typedef int arcnode;
   typedef char vexnode;
   typedef struct
    {
        vexnode vex[MAXNODE];//first
        arcnode arc[MAXNODE][MAXNODE];//two
        int vexnum,arcnum;//third
    }Graph;
    void Creat_Graph(Graph *G)
    {
        int i,j,k;
        scanf("%d %d",&G->vexnum,&G->arcnum);
        for(i=0;i<G->vexnum;i++)
        {
            scanf("%c",&G->vex[i]);
        }
        getchar();
        for(i=0;i<G->vexnum;i++)
        {
            for(j=0;j<G->vexnum;j++)
            {
                G->arc[i][j]=INFE;
            }
        }
        for(k=0;k<G->arcnum;k++)
        {
            int w;
            scanf("%d %d %d",&i,&j,&w);
            G->arc[i][j]=w;
            G->arc[j][i]=w;
        }
    }
   int main()
    {
        Graph G;
        int i,j;
        Creat_Graph(&G);
        for(i=0;i<G.vexnum;i++)
        {
            for(j=0;j<G.vexnum;j++)
            {
                 printf("%d ",G.arc[i][j]);
            }
            printf("\n");
        }
    }
   
   

迪杰斯特拉最短路径算法

#include <stdio.h>
#include <stdlib.h>
#define MAX 655674
 typedef struct node
 {
     int vexnum;
     int a[50][50];
 }Graph;
int final[50]={0},a[50];
void DIJ(Graph *G,int v)
{
    for(int i=0;i<G->vexnum;i++)
    {
        a[i]=MAX;               //一开始让a[i]全部为最大值
    }
    a[v]=0;
    for(int i=0;i<G->vexnum;i++)
    {
        int n=-1,min=MAX;
        for(int j=0;j<G->vexnum;j++)
        {
            if(a[j]<min&&final[j]==0)
            {
                n=j;
                min=a[j];
            }
        }
        if(n==-1)
            return;
        else
        {
            a[n]=min;
            final[n]=1;
        }
        for(int j=0;j<G->vexnum;j++)
        {
            if(final[j]==0&&G->a[n][j]+a[n]<a[j])
                a[j]=G->a[n][j]+a[n];
        }
    }
}
int main()
{
    int v,i,j;
    Graph G;
    scanf("%d %d",&G.vexnum,&v);
    for(i=0;i<G.vexnum;i++)
    {
        for(j=0;j<G.vexnum;j++)
        {
            int l;
            scanf("%d",&l);
            if(l!=0)
            {
                G.a[i][j]=l;
            }
            else
            {
                G.a[i][j]=MAX;
            }
        }
    }
    DIJ(&G,v);
    for(int i=0;i<G.vexnum;i++)
    {
        if(i!=v)
            printf("%d ",a[i]);
    }
}

3.克鲁斯卡尔(Kruskal)算法

#include<stdio.h>
struct node
{
    int x;
    int y;
    int value;
}KU[500];
int Father[500];
int find(int x)          //找父节点
{
    if(Father[x]==x)
        return x;
    else
        return find(Father[x]);
}
void Quicksort(int x,int y)    //快速排序
{
    if(x>y)
        return;
    int m=KU[x].value;
    int n=KU[x].x;
    int k=KU[x].y;
    int i=x;
    int j=y;
    while(i<j)
    {
        while(i<j&&KU[j].value>=m)
            j--;
        while(i<j&&KU[i].value<=m)
            i++;
        if(i<j)
        {
            int l=KU[j].value;
            KU[j].value=KU[i].value;
            KU[i].value=l;
            l=KU[j].x;
            KU[j].x=KU[i].x;
            KU[i].x=l;
            l=KU[j].y;
            KU[j].y=KU[i].y;
            KU[i].y=l;
        }
    }
    KU[x].value=KU[i].value;
    KU[i].value=m;
    KU[x].x=KU[i].x;
    KU[i].x=n;
    KU[x].y=KU[i].y;
    KU[i].y=k;
    Quicksort(x,i-1);
    Quicksort(i+1,y);
    return;
}
int Kruskal(int n,int k)        
{
    for(int i=0;i<n;i++)
    {
        Father[i]=i;
    }
    int ans=0,num=0;
    for(int i=0;i<k;i++)
    {
        int u=find(KU[i].x);
        int v=find(KU[i].y);
        if(v!=u)
        {
            Father[u]=v;
        num++;
        ans+=KU[i].value;
        }
        if(num==n-1)
            break;
    }
    return ans;
}
int main()
{
    int n,i,j,k=0;
    scanf("%d",&n);
    int a[n][n];
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            scanf("%d",&a[i][j]);
            if(a[i][j]!=0)
            {
                KU[k].x=i;
                KU[k].y=j;
                KU[k].value=a[i][j];
                k++;
            }
        }
    }
    Quicksort(0,k-1);
    int ans=Kruskal(n,k);
    printf("%d\n",ans);
}

4.拓扑排序

1.拓扑排序算法

① 在AOV网中选择一个没有前驱的顶点且输出；
② 在AOV网中删除该顶点以及从该顶点出发的(以该顶点为尾的弧)所有有向弧(边) ；
③ 重复①、②，直到图中全部顶点都已输出(图中无环)或图中不存在无前驱的顶点(图中必有环)。

2.算法实现说明
1.采用正邻接链表作为AOV网的存储结构；
2.设立堆栈，用来暂存入度为0的顶点；
3.删除顶点以它为尾的弧：弧头顶点的入度减1。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int inf=1e9;
const int maxn=1e6+5;
vector<int>edge[50];
int in[50];
int main()
{
    char s[5];
    set<int>k;
    while(cin>>s)
    {
        k.insert(s[2]-'A');
        k.insert(s[0]-'A');
        if(s[1]=='>')
        {
            in[s[2]-'A']++;
            edge[s[0]-'A'].push_back(s[2]-'A');
        }
        else
        {
            in[s[0]-'A']++;
            edge[s[2]-'A'].push_back(s[0]-'A');
        }
    }
    priority_queue<int,vector<int>,greater<int> >q;
    for(int i=0;i<30;i++)
    {
        if(in[i]==0&&k.count(i)!=0)
            q.push(i);
    }
    vector<int>ans;
    while(!q.empty())
    {
        int p=q.top(); q.pop();
        ans.push_back(p);
        for(int i=0;i<edge[p].size();i++)
        {
            int y=edge[p][i];
            in[y]--;
            if(in[y]==0&&k.count(y)!=0)
                q.push(y);
        }
    }
    if(ans.size()==k.size())
    {
        for(int i=0;i<ans.size();i++)
            printf("%c",ans[i]+'A');
        printf("\n");
    }
    else printf("No Answer!\n");
    return 0;
}

5.最长路径

#include<stdio.h>
#include<bits/stdc++.h> 
#define MAX  200
typedef char TElemType;
typedef int status; 
typedef struct BiNode
{
	TElemType data;
	struct BiNode *lchild;
	struct BiNode *rchild;
}BiNode,*BiTree;
void CreateBiTree(BiTree &T)//二叉树的先序创建 
{
	TElemType ch;
	scanf("%c",&ch);
	if(ch=='#')
		T=NULL;
	else 
	{
		T=(BiNode*)malloc(sizeof(BiNode));
		if(!T)
			exit(-1);
		T->data=ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
}
void longest_path(BiTree T,int *path,int &len,int *longestpath,int &longest_len)
{
	if(T!=NULL)
	{
		if(T->lchild==NULL&&T->rchild==NULL)//当遇到叶子结点时，该条路径完毕 
		{
			path[len]=T->data;
			if(len>longest_len)//如果长于longest_len就替换 
			{
				for(int j=0;j<=len;j++)
				{
					longestpath[j]=path[j];
				}
				longest_len=len;//longest_len更新 
			}
		}
		else//当遇到的不是叶子结点时，该条路径继续 
		{
			path[len++]=T->data;
			longest_path(T->lchild ,path,len,longestpath,longest_len);
			longest_path(T->rchild ,path,len,longestpath,longest_len);
			len--;
		}
	}
}
int main()
{
	BiTree T;
	printf("创建树输入树T的先序序列(其中使用#代表空节点)\n");
	CreateBiTree(T);
	int path[MAX]={0};
	int longestpath[MAX]={0};
	int len=0;
	int longest_len=0;
	longest_path(T,path,len,longestpath,longest_len);
	printf("第一条最长的路径长度为：%d\n",longest_len);
	printf("路径为："); 
	for(int i=0;i<=longest_len;i++)
	{
		
		printf("%c ->",longestpath[i]);
	}
	printf("NULL");
	
}

6.关键路径

#define Maxvex 100
typedef char vextype;
typedef int undform;
typedef struct arcnode//边表
{
	int arcnode;//此边节点对应顶点的下标
	struct arcnode* nextarcnode;//下一个此根节点指向的边节点
	int weight;//边的权值
}Arcnode;
 
typedef struct vexnode//节点表
{
	vextype val;//节点值
	Arcnode* Nextarc;//节点指向的第一个边
}Vexnode[Maxvex], onevexnode;
 
typedef struct Graph//图
{
	Vexnode vexall;//所有的节点作为一个数组
	int vexnum, arcnum;//节点，边的个数
}Graph;
bool ToPosort(Graph* gp, int * Topo)//拓扑排序
{
	int* indegree = (int*)new int[gp->vexnum];//建立入度数组
	memset(indegree, 0, sizeof(int) * gp->vexnum);
	std::stack<int> st;//建立栈
	for (int i = 0; i < gp->vexnum; i++)//计算所有顶点的入度
	{
		arcnode* node = gp->vexall[i].Nextarc;
		while (node != NULL)
		{
			indegree[node->arcnode]++;
			node = node->nextarcnode;
		}
	}
	for (int i = 0; i < gp->vexnum; i++)//入度为0入栈
	{
		if (indegree[i] == 0)
		{
			st.push(i);
		}
	}
	int size = 0;//判断多少个顶点无环
	int topo_i = 0;
	while (!st.empty())
	{
		int i = st.top();
		st.pop();
		Topo[topo_i++] = i;//顶点入拓扑序列
		size++;
		arcnode* node = gp->vexall[i].Nextarc;
		while (node != NULL)
		{
			--indegree[node->arcnode];
			if (indegree[node->arcnode] == 0)
			{
				st.push(node->arcnode);
			}
			node = node->nextarcnode;
		}
	}
	if (size == gp->vexnum) return true;
	else return false;
}

7.查找

1.静 态 查 找 表

1. 顺序表

在顺序表上查找的基本思想是：用给定关键字与顺序表中各元素的关键字逐个比较，直到成功或失败(所有元素均不成功)。存储结构可为顺序存储结构，也可为链式存储结构。

#include<stdio.h>
#define MAX_VEX 30

typedef struct ST
{
    int a[100];
    int length;
}ST;
int search(ST g,int n)
{
    g.a[0]=n;
    int i=g.length;
    while(g.a[i]!=n)
    {
        i--;
    }
    return i;
}
int main()
 {
     ST g;
     g.length=1;
     int n,i;
     scanf("%d",&n);
     for(i=1;i<=n;i++)
     {
         scanf("%d",&g.a[i]);
         g.length++;
     }
    int m=search(g,n);
    printf("%d",m);

 }

2.折半查找

折半查找又称为二分查找法，这种方法要求待查找的表顺序存储而且表中关键字大小有序排列.

#include<stdio.h>        //顺序已经排好了
#define MAX_VEX 30

typedef struct ST
{
    int a[100];
    int length;
}ST;
int BINsearch(ST g,int n)
{
     int i,j,mid;
     i=1;
     j=n;
     while(i<=j)
     {
       mid=(i+j)/2;
       if(g.a[mid]==n)
        return mid;
       else if(g.a[mid]<n)
         i=mid+1;
         else
            j=mid-1;
     }
     return 0;
}
int main()
 {
     ST g;
     g.length=1;
     int n,i;
     scanf("%d",&n);
     for(i=1;i<=n;i++)
     {
         scanf("%d",&g.a[i]);
         g.length++;
     }
    int m=BINsearch(g,n);
    printf("%d",m);

 }

3. 索引顺序表

无

2. 动 态 查 找 表

1. 二叉排序树

二叉排序树又称为二叉查找树，它是一种特殊的二叉树，其定义为：二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：

① 若它的左子树非空，则左子树上所有结点的值均小于根结点的值；

② 若它的右子树非空，则右子树上所有结点的值均大于根结点的值；

③ 它的左、右子树也分别是二叉排序树。

||||||||||||               插入                  |||||||||||||
#include<stdio.h>    
#define MAX_VEX 30

typedef struct node
{
    int key;
    struct node *Lchild,*Rchild;
}BSTtree;
void insert_BST(BSTtree **bt,int key)
{
    BSTtree *s;
    if((*bt)==NULL)
    {
        s=malloc(sizeof(BSTtree));
        s->key=key;
        s->Lchild=NULL;
        s->Rchild=NULL;
        *bt=s;
    }
    else if((*bt)->key>key)
        insert_BST(&((*bt)->Lchild),key);
    else
       insert_BST(&((*bt)->Rchild),key);
}
int main()
 {
     BSTtree *bt=NULL,*l=NULL;
     int n;
     scanf("%d",&n);
     for(int i=0;i<n;i++)
     {
         int m;
         scanf("%d",&m);
         insert_BST(&bt,m);
     }
     l=bt->Lchild;
     printf("%d %d",bt->key,l->key);
 }

|||||||||                     查找              ||||||||
BSTtree *searchBST(BSTtree *bt,int key)
{
    if(!bt) return NULL;
    else if(bt->key==key)
        return bt;
    else if(bt->key<key)
        return searchBST(bt->Rchild,key);
    else
        return searchBST(bt->Lchild,key);
}

2. 二叉排序树的删除

在二叉排序树中删除一个结点，不能将以该结点为根的子树全部删除，只能删除该结点并使得二叉树依然满足二叉排序树的性质。也就是说，在二叉排序树中删除一个结点相当于在一个有序序列中删除一个结点。

在二叉排序树中删除一个结点的过程描述如下：查找待删结点，若找不到，空操作；否则，假设待删除结点为 p，结点 p 的双亲为 f，并假设 p 是 f 的左孩子(右孩子的情况类似)。下面分三种情况进行讨论：

1.p 为叶子结点，由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可： f->lchild = NULL; free§;

2.p 结点只有左子树，或只有右子树，则 p 的左子树或右子树直接改为其双亲结点 f的左子树：f->lchild = p->lchild或 f->lchild = p->rchild；free§；

3.p 结点既有左子树，又有右子树首先找到p结点在二叉排序树的中序遍历序列中的直接前驱s结点(无右子树)，然后将 p 的左子树改为 f 的左子树，而将 p 的右子树改为 s 的右子树： f->lchild = p->lchild; s->rchild = p->rchild; free§;

8.排序

1.冒泡排序

#include <stdio.h>
#include <stdlib.h>

void BubbleSore(int *a,int length)
{
 int i,j;
 for(i=0;i<length-1;i++)
 {
     for(j=0;j<length-1-i;j++)
     {
         int temp;
         if(a[j]>a[j+1])
         {
             temp=a[j];
             a[j]=a[j+1];
             a[j+1]=temp;
         }
     }
 }
}
int main()
{
  int n,i;
  scanf("%d",&n);
  int a[n];
  for(i=0;i<n;i++)
  {
      scanf("%d",&a[i]);
  }
  BubbleSore(a,n);
  for(i=0;i<n;i++)
  {
       printf("%d ",a[i]);
  }
}

2.选择排序

void swap(int *a,int *b)
{
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}
void SelectionSore(int *a,int length)
{
    int i,j;
    for(i=0;i<length;i++)
    {
         int k=i;
         for(int j=i+1;j<length;j++)
         {
             if(a[j]<a[k])
             {
                 k=j;
             }
         }
         if(k!=i)
         {
             swap(&a[k],&a[i]);
         }
    }
}

3.插入排序

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
void function_sort(int *arr,int n)
{
    int i,j;
    int length_arr=n;    //长度不能用strlen,strlen是计算字符串长度的
    for(i=1;i<length_arr;i++)   //核心代码
    {
        int insert_value=arr[i];     //注意，一定要这样做。
        for(j=i-1;j>=0&&insert_value<arr[j];j--)
        {
           arr[j+1]=arr[j] ;
        }
        arr[j+1]=insert_value;
    }
}
int main()
{
    int a[100];
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    function_sort(a,n);
    for(int i=0;i<n;i++)
    {
         printf("%d ",a[i]);
    }
}

4.希尔排序

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
void function_sort(int *arr,int n)
{
    int i,j;
    int d=n;
    while(d>1)
    {
        d=d/2;
        for(i=0;i<d;i++)
        {

            for(j=i+d;j<n;j=j+d)
            {
                int temp=arr[j];
                int x;
                for(x=j-d;x>=0&&arr[x]>temp;x=x-d)
                {
                    arr[x+d]=arr[x];
                }
                arr[x+d]=temp;
            }
        }
    }
}
int main()
{
    int a[100];
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    function_sort(a,n);
    for(int i=0;i<n;i++)
    {
         printf("%d ",a[i]);
    }
}

5.快速排序

void f(int*a,int b,int e)
{
    if(b>e)
        return;
    int i,j,m,k;
    m=a[b];
    i=b;
    j=e;
    while(i!=j)
    {
        while(a[j]>=m&&i<j)
 
            j--;
 
        while(a[i]<=m&&i<j)
 
            i++;
 
    if(j>i)
    {
            k=a[i];
            a[i]=a[j];
            a[j]=k;
    }
    }
    a[b]=a[i];
    a[i]=m;
    f(a,b,i-1);
    f(a,i+1,e);
 
}

6.归并排序

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define maxn 100
void Merge(int *a,int x1,int y1,int x2,int y2)//合并，从小到大排序
{
    int i=x1;
    int j=x2;
    int temp[maxn],index=0;
    while(i<=y1&&j<=y2)
    {
        if(a[i]<a[j])
        {
            temp[index++]=a[i++];
        }
        else
        {
            temp[index++]=a[j++];
        }
    }
    while(i<=y1)
    {
         temp[index++]=a[i++];
    }
    while(j<=y2)
    {
        temp[index++]=a[j++];
    }
    for(i=0;i<index;i++)
    {
        a[x1+i]=temp[i];
    }
}
void Mergesort(int *a,int left,int right)  //拆分，往小的拆分
{
    if(left<right)
    {
        int mid=(left+right)/2;
        Mergesort(a,left,mid);
        Mergesort(a,mid+1,right);
        Merge(a,left,mid,mid+1,right);
    }
}
int main()
{
    int a[100];
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    Mergesort(a,0,n-1);
    for(int i=0;i<n;i++)
    {
         printf("%d ",a[i]);
    }
}

7.堆排序

1.创建

#include<stdio.h>


const int maxn=100;
int a[100],n;
void swap(int *c,int *b)
{
    int temp=*c;
    *c=*b;
    *b=temp;
}
void downAdjust(int low,int high)    //向下调整
{
    int i=low,j=i*2;
    while(j<=high)
    {
        if(j+1<=high&&a[j+1]>a[j])
        {
            j=j+1;
        }
        if(a[j]>a[i])
        {
            swap(&a[j],&a[i]);
                 i=j;
                j=i*2;
        }
        else
            break;
    }
}
void CreatHeap()//创建堆
{
    for(int i=n/2;i>=1;i--)
    {
        downAdjust(i,n);
    }
}
void deleteTop()//删除堆顶元素
{
    a[1]=a[n--];
    downAdjust(1,n);
}
void upAdjust(int low,int high)  
{
    int i=high,j=i/2;
    while(j>=low)
    {
        if(a[i]>a[j])
        {
            swap(&a[i],&a[j]);
            i=j;
            j=i/2;
        }
        else
            break;
    }
}
void insert(int x)
{
    a[++n]=x;
    upAdjust(1,n);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    CreatHeap();
    for(int j=1;j<=n;j++)
    {
        printf("%d ",a[j]);
    }
}

void heapSort()
{
    CreatHeap();
    for(int i=n;i>1;i--)
    {
        swap(&a[1],&a[i]);
        downAdjust(1,i-1);
    }
}

8.基数排序

import java.util.LinkedList;
 
public class Radix {
 
	public static void main(String[] args) {
 
		int[] arr = { 23, 1, 4, 9, 98, 132, 42 };
 
		sort(arr);
 
	}
 
	public static void sort(int[] arr) {
		// 1.找 分类-收集 的轮数（最大值的长度）
		int radix = getRadix(arr);
		// 2.创建桶 list所有桶的集合 每一个桶是LinkedList当成队列来用
		LinkedList<Integer>[] list = new LinkedList[10];
		for (int i = 0; i < list.length; i++) {
			list[i] = new LinkedList<>();
		}
		// 3.开始 分类-收集
		for (int r = 1; r <= radix; r++) {
			// 分类过程
			for (int i = 0; i < arr.length; i++) {
				list[getIndex(arr[i], r)].offer(arr[i]);
			}
			int index = 0; // 遍历arr原数组
			// 收集的过程
			for (int i = 0; i < list.length; i++) {
				while (!list[i].isEmpty()) {
					arr[index++] = list[i].poll();
				}
			}
 
		}
 
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + "  ");
		}
 
	}
 
	private static int getIndex(int num, int r) {
		int ret = 0;
		for (int i = 1; i <= r; i++) {
			ret = num % 10;
			num /= 10;
		}
		return ret;
	}
 
	private static int getRadix(int[] arr) {
		int max = arr[0];
		for (int i = 1; i < arr.length; i++) {
			if (arr[i] > max) {
				max = arr[i];
			}
		}
		return (max + "").length();
	}
 
}