# 数据结构

数据结构

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

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

1.线性表

线性表的顺序存储

1. 顺序线性表初始化

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

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;
}
1
2
3
4
5
6
7
8
9
10
11
12

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

线性表的链式存储

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

(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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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;
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

(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;
}
1
2
3
4
5
6
7
8
9
10

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

⑵ 按值删除

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

6. 循环链表

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

#include 
#include 

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

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

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

双向链表的删除

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

                                          栈和队列
1

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;
1
2
3
4
5
6

2.栈的初始化

void Init_stack(void)  //多余的
{
    top=0;
    bottom=0;
}
1
2
3
4
5

3.压栈(元素进栈)

void push(Sqstack *s,int x)
{
    if(top<10)
    {
    s->stack[top++]=x;
    }
    else
    {
        printf("stack full\n");
    }
}
1
2
3
4
5
6
7
8
9
10
11

4.栈(元素出栈

int pop(Sqstack *s)
{
    if(top!=bottom)
    {
        return s->stack[--top];
    }
    else
    {
        printf("stack empty\n");
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

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;
}
1
2
3
4
5
6
7
8
9
10
11
12

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;
}
1
2
3
4
5
6
7
8

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

队列及其基本概念

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;
}
1
2
3
4
5
6
7
8
9
10
11
12

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;

}
1
2
3
4
5
6
7
8
9

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;
}
1
2
3
4
5
6
7
8
9
10

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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;
}
1
2
3
4
5
6
7
8
9
10
11
12

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3.串

串类型的定义

1. 串的基本概念

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

1 串的联结操作

#include
#include

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

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

2 求子串操作

#include
#include

#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");
   }
}
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

3. 串的堆分配存储表示

 #include
#include

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

4.3 串的模式匹配算法

KMP算法如下

#include 
#include 
#include 
 
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);
    }
}
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

4.数组和广义表

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

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

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 
#include 
#include 

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;
 }
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

#include 
#include 
#include 
#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;
 }
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

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));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

//求叶子节点的个数
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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

(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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

(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;
}
1
2
3
4
5
6
7
8
9

(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;
}
1
2
3
4
5
6
7
8
9

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

#include 
#include 

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

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

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

#include 
#include 

#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
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
51
52
53
54

图的存储结构

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

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

   #include 
   #include 
   #include 
   #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");
        }
    }
   
   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
   51
   52

迪杰斯特拉最短路径算法

#include 
#include 
#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]);
    }
}
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

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

#include
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);
}
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

4.拓扑排序

1.拓扑排序算法

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

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

#include
using namespace std;
typedef long long LL;
const int inf=1e9;
const int maxn=1e6+5;
vectoredge[50];
int in[50];
int main()
{
    char s[5];
    setk;
    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,greater >q;
    for(int i=0;i<30;i++)
    {
        if(in[i]==0&&k.count(i)!=0)
            q.push(i);
    }
    vectorans;
    while(!q.empty())
    {
        int p=q.top(); q.pop();
        ans.push_back(p);
        for(int i=0;i

#include
#include 
#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");
	
}

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

#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;
}
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#include
#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);

 }
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

#include        //顺序已经排好了
#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);

 }

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

||||||||||||               插入                  |||||||||||||
#include    
#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);
 }
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

|||||||||                     查找              ||||||||
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);
}
1
2
3
4
5
6
7
8
9
10
11

1