Sekyoro的博客小屋

数据结构noj_2

发表于 更新于 分类于
本文字数： 17k 阅读时长 ≈ 16 分钟

数据结构noj_2

数据结构10-20

我太菜了,有几道题只是能勉强过一下,但没按照要求做

后面有时间看能不能改一下

11

QQ截图20210517220735

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
#include<stdio.h>
#include<stdlib.h>
#define maxsize 101

typedef struct queue
{
    int data[maxsize];
    //int head;
    int rear;
}queue,*pqueue;

void move(pqueue);
void print(pqueue);
void initial(pqueue,int);

int main(void)
{
    int n,k;
    scanf("%d %d",&n,&k);
    pqueue q = (pqueue)malloc(sizeof(queue));
    if(q==NULL) printf("error");
    initial(q,n);
    while(k--)
    move(q);
    print(q);
    return 0;
}

void initial(pqueue q,int n)
{
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&q->data[i]);
    }
    q->rear = n;
}

void move(pqueue q)
{
    int temp;
    temp = q->data[q->rear];
    for(int i = q->rear;i>=2;i--)
    {
        q->data[i] = q->data[i-1];
    }
    q->data[1] = temp;
}

void print(pqueue q)
{
    for(int i = 1;i<=q->rear;i++)
    {
        printf("%d%c",q->data[i],(i==q->rear)?'\n':' ');
    }
}

12

image-20210517221211318

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <stdio.h>
#include <stdlib.h>
#define maxsize 101

typedef struct Tripe
{
    int data;
    int row;
    int col;
} Tripe;

typedef struct TSmatrix
{
    int num;
    Tripe Element[maxsize];
} TSmatrix, *pTsmatrix;

void initial(pTsmatrix);
void add(pTsmatrix, pTsmatrix, pTsmatrix);
void print(pTsmatrix);

int main(void)
{
    pTsmatrix a = (pTsmatrix)malloc(sizeof(TSmatrix));
    pTsmatrix b = (pTsmatrix)malloc(sizeof(TSmatrix));
    pTsmatrix c = (pTsmatrix)malloc(sizeof(TSmatrix));
    scanf("%d %d", &a->num, &b->num);
    initial(a);
    initial(b);
    add(a, b, c);
    print(c);
    return 0;
}

void print(pTsmatrix result)
{
    for (int i = 1; i <= result->num; i++)
    {
        printf("%d %d %d\n", result->Element[i].row, result->Element[i].col, result->Element[i].data);
    }
}
void add(pTsmatrix a, pTsmatrix b, pTsmatrix c)
{
    int i = 1, j = 1;
    int k = 0;
    
    while ((i <= a->num) && (j <= b->num))
    {

        if ((a->Element[i].row == b->Element[j].row) && (a->Element[i].col == b->Element[j].col))
        {

            if ((a->Element[i].data + b->Element[j].data) == 0)
            {
                i++;
                j++;
            }
            else
            {
                k++;
                c->Element[k].data = a->Element[i].data + b->Element[j].data;
                c->Element[k].row = a->Element[i].row;
                c->Element[k].col = a->Element[i].col;
                i++;
                j++;
            }
        }
        else if ((a->Element[i].row < b->Element[j].row) || (a->Element[i].row == b->Element[j].row && (a->Element[i].col < b->Element[j].col)))
        {
            k++;
            c->Element[k].row = a->Element[i].row;
            c->Element[k].col = a->Element[i].col;
            c->Element[k].data = a->Element[i].data;
            i++;
        }
        else
        {
            k++;
            c->Element[k].row = b->Element[j].row;
            c->Element[k].col = b->Element[j].col;
            c->Element[k].data = b->Element[j].data;
            j++;
        }
    }
    while (i <= a->num)
    {
        k++;
        c->Element[k].row = a->Element[i].row;
        c->Element[k].col = a->Element[i].col;
        c->Element[k].data = a->Element[i].data;
        i++;
    }
    while (j <= b->num)
    {
        k++;
        c->Element[k].row = b->Element[j].row;
        c->Element[k].col = b->Element[j].col;
        c->Element[k].data = b->Element[j].data;
        j++;
    }
    c->num = k;
}

void initial(pTsmatrix p)
{

    for (int i = 1; i <= p->num; i++)
    {
        scanf("%d %d %d", &p->Element[i].row, &p->Element[i].col, &p->Element[i].data);
    }
}

13

image-20210517221236404

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include <stdio.h>
#include <stdlib.h>

typedef struct OLNode
{
    int i, j, e;
    struct OLNode *down, *right;
} OLNode, *OLlink;

typedef struct
{
    OLlink *rhead, *chead; //指向行或列第一个非零元(指向结构体的指针),可以用数组rhead[row]表示第row行的数据
    int m, n, len;         //行列数,非零元个数
} CrossList;

void initial(CrossList *);
void plus(CrossList *, CrossList *);
void print(CrossList *);
void Insert(CrossList *, OLlink, OLlink, OLlink *, OLlink *);
void add(CrossList *, OLlink, OLlink, OLlink *, OLlink *);

int main(void)
{
    CrossList *M = (CrossList *)malloc(sizeof(CrossList));
    CrossList *N = (CrossList *)malloc(sizeof(CrossList));
    scanf("%d %d", &M->m, &M->n);
    N->m = M->m;
    N->n = M->n;
    scanf("%d %d", &M->len, &N->len);
    initial(M);
    initial(N);
    plus(M, N);
    print(M);
    return 0;
}

void print(CrossList *M)
{
    for (int row = 1; row <= M->m; row++)
    {
        OLlink pa = M->rhead[row];
        while (pa)
        {
            printf("%d %d %d\n", pa->i, pa->j, pa->e);
            pa = pa->right;
        }
    }
}

void plus(CrossList *M, CrossList *N)
{
    OLlink pa, pb;
    OLlink pre; //指向前面一个节点,方便插入
    OLlink *hl = (OLlink *)malloc((M->n + 1) * sizeof(OLlink));

    for (int j = 1; j <= M->n; j++)
        hl[j] = M->chead[j]; //hl[]表示的是每列非零元的pre指向元素，与pre类似

    for (int row = 1; row <= M->m; row++) //行遍历
    {
        pa = M->rhead[row];
        pb = N->rhead[row];
        pre = NULL;
        while (pb) //当pb有非零元素时进行处理
        {
            if (pa == NULL || pa->j > pb->j)
            {

                Insert(M, pa, pb, &pre, hl);
                pb = pb->right;
            }
            else if (pa != NULL && pa->j < pb->j)
            {
                pre = pa;
                pa = pa->right;
            }
            else if (pa->j == pb->j)
            {
                add(M, pa, pb, &pre, hl);
                pb = pb->right;
            }
        }
    }
}

void add(CrossList *M, OLlink pa, OLlink pb, OLlink *pre, OLlink *hl)
{

    int data = pa->e + pb->e;
    if (data)
    {
        pa->e = data;
    }
    else
    {
        OLlink temp = (OLlink)malloc(sizeof(OLNode));
        if ((*pre) == NULL)
            M->rhead[pa->i] = pa->right;
        else
        {
            (*pre)->right = pa->right;
        }
        temp = pa;
        pa = pa->right;
        if (M->chead[temp->j] == temp)
            M->chead[temp->j] = hl[temp->j] = temp->down;
        else
            hl[temp->j]->down = temp->down;
        free(temp);
    }
}

void Insert(CrossList *M, OLlink pa, OLlink pb, OLlink *pre, OLlink *hl) //插入有两种情况，一种是pa该行无非零元素，另一种pb所在列小于pa所在列
{
    OLlink p = (OLlink)malloc(sizeof(OLNode));
    p->i = pb->i;
    p->j = pb->j;
    p->e = pb->e;
    p->down = p->right = NULL;
    if ((*pre) == NULL)
    {
        M->rhead[p->i] = p;
      
    }
    else
    {
        (*pre)->right = p;
      
    }
    p->right = pa;
    
    (*pre) = p;
    pa = (*pre)->right;//这一句可以不要
    if (!M->chead[p->j] || M->chead[p->j]->i > p->i)
    {
        p->down = M->chead[p->j];
        M->chead[p->j] = p;
    }
    else
    {
        p->down = hl[p->j]->down;
        hl[p->j]->down = p;
    }
    hl[p->j] = p;
   
}
void initial(CrossList *Clist)
{
    int i, j, e;
    Clist->rhead = (OLlink *)malloc((Clist->m + 1) * sizeof(OLlink));
    Clist->chead = (OLlink *)malloc((Clist->n + 1) * sizeof(OLlink));
    // if(rhead||chead)
    // exit(1);
    for (int i = 1; i <= Clist->m; i++)
        Clist->rhead[i] = NULL;
    for (int i = 1; i <= Clist->n; i++)
        Clist->chead[i] = NULL;
    OLlink s = (OLlink)malloc(sizeof(OLNode));
    for (int count = 0; count < Clist->len; count++)
    {
        OLlink cur = (OLlink)malloc(sizeof(OLNode));
        cur->down = NULL;
        cur->right = NULL;
        // if(cur==NULL)
        // exit(1);
        scanf("%d %d %d", &i, &j, &e);
        cur->i = i;
        cur->j = j;
        cur->e = e;
        if (Clist->rhead[i] == NULL)
        {
            Clist->rhead[i] = cur;
        }
        else
        {
            s = Clist->rhead[i];
            while (s->right != NULL && s->right->j < j)
                s = s->right;
            cur->right = s->right;
            s->right = cur;
        }
        if (Clist->chead[j] == NULL)
            Clist->chead[j] = cur;
        else
        {
            s = Clist->chead[j];
            while (s->down != NULL && s->down->i < i)
                s = s->down;
            cur->down = s->down;
            s->down = cur;
        }
    }
}

14

image-20210517221259788

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef enum
{
    ATOM,
    LIST
} ElemTag;
typedef struct GLNode_1 //同层节点
{
    ElemTag tag;
    union
    {
        struct GLNode_1 *hp;
        char data;
    } atom_hp;
    struct GLNode_1 *tp;
} GLNode_1, *GList_1;

typedef struct GLNode_2 //头尾节点
{
    ElemTag tag;
    union
    {
        struct GLNode_2 *hp, *tp;
        char data;
    } atom_htp;
} GLNode_2, *GList_2;

GList_1 create_1(char *);
GList_2 create_2(char *);
int Depth_1(GList_1);
int Depth_2(GList_2);

int main(void)
{
    char GList[MAXSIZE];
    fgets(GList,sizeof(GList),stdin);
    char *p = GList;
    int depth;
    GList_1 s = create_1(p);
    depth = Depth_1(s);
    printf("%d\n%d\n",depth,depth);
    return 0;
}
// GList_2 create_2(char *s)
// {
//     char ch = *s++;
//     GList_2 cur;
//     if(ch!='\n')
//     {
//         cur = (GList_2)malloc(sizeof(GLNode_2));
//         if(ch == '(')
//         {
//             cur->tag = LIST;

//         }
//     }
// }
int Depth_1(GList_1 L)
{
    int d, max = 0;
    if (L->tag == ATOM)
        return 0;
    GList_1 s;
    s = L->atom_hp.hp;
    if (s == NULL)
        return 1;
    while (s != NULL)
    {
        if (s->tag == LIST)
        {
            d = Depth_1(s);
            if (d > max)
                max = d;
        }
        s = s->tp;
    }
    return (max + 1);
}
GList_1 create_1(char *s)
{
    char ch = *s++;
    GList_1 cur;
    if (ch != '\n')
    {
        cur = (GList_1)malloc(sizeof(GLNode_1));
        if (ch == '(') //字符为(时,创建表头
        {
            cur->tag = LIST;
            cur->atom_hp.hp = create_1(s);
        }
        else if (ch == ')') //字符尾)时,子表结束
            cur = NULL;
        else
        {
            cur->tag = ATOM;
            cur->atom_hp.data = ch;
        }
    }
    else
        cur = NULL;
    ch = *s++;
    if (cur != NULL)
    {
        if (ch == ',')
        {
            cur->tp = create_1(s);
        }
        else
            cur->tp = NULL;
    }
    return cur;
}

15

image-20210517221509727

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
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
//在栈中分配堆（heap）空间时

typedef struct Node
{
    int data;
    struct Node *lchild;
    struct Node *rchild;
} BiNode, *Bitree;

Bitree create();
void preNode(Bitree);

int main(void)
{
    // char data[MAXSIZE];
    // fgets(data, sizeof(data), stdin);
    Bitree r;
    r = create();
    preNode(r);
    return 0;
}
Bitree create() //字符数组,参数是指向字符的指针
{
   
    char fir_data,sec_data;
    Bitree root = (Bitree)malloc(sizeof(BiNode));
    fir_data = getchar();
    sec_data = getchar();
    root->rchild = root->lchild = NULL;
    if(fir_data == ',')
    {
        root->data = sec_data;
        fir_data = getchar();
        if(fir_data == '(')
        {
            root->lchild = create();
            root->rchild = create();
        }
    }
    else
    {
        root->data = fir_data;
        if(sec_data == '(')
        {
             root->lchild = create();
            root->rchild = create();
        }
    }
    return root;
}
void preNode(Bitree root)
{
    if(root)
    {
        printf("%c",root->data);
        preNode(root->lchild);
        preNode(root->rchild);
    }
}

16

image-20210517221532633

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
#include<stdio.h>
#include<stdlib.h>

typedef struct Node
{
    char data;
    struct Node *lchild;
    struct Node *rchild;
}BiNode,*BiTree;

BiTree create();
int cal_node(BiTree);

int main(void)
{
    BiTree r;
    r = create();
    int num = cal_node(r);
    printf("%d\n",num);
    return 0;
}
BiTree create()
{
    char s;
    s = getchar();
    if(s=='#')
    return NULL;
    BiTree root = (BiTree)malloc(sizeof(BiNode));
    root->data = s;
    root->lchild = root->rchild = NULL;
    root->lchild = create();
    root->rchild = create();
    return root;
}
int cal_node(BiTree root)
{
    int n1 = 0,n2 = 0;
    if(root->lchild==NULL&&root->rchild==NULL)
    {
        return 1;
    }
    if(root->lchild)
    n1 = cal_node(root->lchild);
    if(root->rchild)
    n2 = cal_node(root->rchild);
    return (n1+n2);
}

17

image-20210517221555933

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
#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    struct Node *lchild;
    struct Node *rchild;
    int data;
} BiNode, *Bitree;

Bitree initial(void);
void midtree(Bitree);

int main(void)
{
    Bitree root = initial();
    midtree(root);
    printf("\n");
    return 0;
}

Bitree initial()
{
    int data;
    data = getchar();
    Bitree root;
    if (data == '#')
    {
        return NULL;
    }
    else
    //if(data != '\n')
    {
        Bitree root = (Bitree)malloc(sizeof(BiNode));
        root->data = data;
        root->lchild = initial();
        root->rchild = initial();
        return root;
    }
}
void midtree(Bitree root)
{
    if (root == NULL)
        return;
    if (root->lchild)
        midtree(root->lchild);
    printf("%c", root->data);
    if (root->rchild)
        midtree(root->rchild);
}

18

image-20210517221619298

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
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct BiNode
{
    struct  BiNode* lchild;
    struct BiNode* rchild;
    int data; 
}BiNode,*BiTree;

void postNode(BiTree);
int PreFindMid(char*,char*,int,int,int);
BiTree Create(char*,char*,int*,int,int);

int main(void)
{
    int len;
    char pre[100],mid[100];
    scanf("%s%s",pre,mid);
    len = strlen(pre);
    BiTree root;
    int pos_p = 0;
    root = Create(pre,mid,&pos_p,0,len-1);
    postNode(root);
    return 0;
}

BiTree Create(char *pre,char* mid,int *pos_p,int pos_le,int pos_ri)
{
    BiTree temp;
    temp = (BiTree)malloc(sizeof(BiNode));
    temp->data = pre[*pos_p];
    temp->lchild = temp->rchild = NULL;
    (*pos_p)++;
    int pos_m;
    pos_m = PreFindMid(pre,mid,*pos_p-1,pos_le,pos_ri);
    if(pos_m>pos_le)
    temp->lchild = Create(pre,mid,pos_p,pos_le,pos_m-1);
    if(pos_m<pos_ri)
    temp->rchild = Create(pre,mid,pos_p,pos_m+1,pos_ri);
    return temp;
}
int PreFindMid(char* pre,char* mid,int pos_p,int pos_le,int pos_ri)
{
    for(int i = pos_le;i<=pos_ri;i++)
    {
        if(pre[pos_p] == mid[i])
        {
            return i;
        
        } 
    }
    return 0;


}
void postNode(BiTree root)
{
    if(root==NULL)
    return;
    postNode(root->lchild);
    postNode(root->rchild);
    printf("%c",root->data);
}


19

image-20210517221728217

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
99
100
101
102
103
104
105
106
107
#include <stdio.h>
#include <stdlib.h>
#define MAX_NUM 100

typedef struct ArcNode
{
    int adjvex;              //邻接点的位置
    struct ArcNode *nextarc; //指向与顶点相邻的其他邻接点
} ArcNode;

typedef struct VertexNode
{
    int adjvex;        //储存顶点的位置值
    ArcNode *firstarc; //用于指向链表的第一个顶点
} VertexNode;

typedef struct
{
    VertexNode vertex[MAX_NUM]; //头接点表
    int vexnum, arcnum;         //节点个数，连线个数
} AdjList;

AdjList initial_adjList();
void test(AdjList);

int main(void)
{
    AdjList al;
    al = initial_adjList();
    test(al);
    return 0;
}

AdjList initial_adjList()
{
    AdjList adj_list;
    ArcNode *node = (ArcNode*)malloc(sizeof(ArcNode));
    ArcNode *node_2 = (ArcNode*)malloc(sizeof(ArcNode));
    int vex, arc;
    scanf("%d%d", &vex, &arc);
    adj_list.vexnum = vex;
    adj_list.arcnum = arc;
    for (int i = 1; i <= vex; i++)
    {
        scanf("%d", &adj_list.vertex[i].adjvex);
        adj_list.vertex[i].firstarc = NULL;
    }//进行初始化，将每个头接点赋值，并置firstarcNULL
    int i, j;
    while (arc--)//为每条边给信息
    {
        scanf("%d%d", &i, &j);
        for (int ix = 1; ix <= vex; ix++)
        {
            if (i == adj_list.vertex[ix].adjvex)//找到头接点
            {
                if (adj_list.vertex[ix].firstarc == NULL)//如果为空,即没有连接点
                {
                    node->adjvex = j;
                    node->nextarc = NULL;
                    adj_list.vertex[ix].firstarc = node;
                    // adj_list.vertex[ix].firstarc->adjvex = j;
                    // adj_list.vertex[ix].firstarc->nextarc = NULL;
                    continue;
                }
                // else
                // {
                //     node.adjvex = j;
                //     node.nextarc = NULL;
                //     adj_list.vertex[ix].firstarc->nextarc = &node;

                // }
                node_2->adjvex = j;
                node_2->nextarc = NULL;
                node = adj_list.vertex[ix].firstarc;
                while (node->nextarc)
                {
                    node = node->nextarc;
                }
                node->nextarc = node_2;
            }
        }
    }
    return adj_list;
}
void test(AdjList adj_list)
{
    int ix, jx;
    ArcNode *node;
    scanf("%d%d", &ix, &jx);
    for (int i = 1; i <= adj_list.arcnum; i++)
    {
        if (ix == adj_list.vertex[i].adjvex)
        {
            for (node = adj_list.vertex[i].firstarc; node != NULL; node = node->nextarc)
            {
                if (jx == node->adjvex)
                {
                    printf("yes\n");
                    return;
                }
            }
        }
    }
    printf("no\n");
    return;
}

20

image-20210517221747666

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

typedef struct ArcNode
{
    //数据
    int data;
    ///邻节点 
    struct ArcNode *nextarc;
} ArcNode;

//头接点
typedef struct VertexNode
{
    int data;
    //头接点的第一个节点域
    ArcNode *firstarc;
} VertexNode;

typedef struct
{
    /* data */
    VertexNode vertex[100];
    int vexnum, arcnum; //节点数与弧数
} AdjList;

//初始化
AdjList initial();

//查找有无邻接点
void search(AdjList);

int main(void)
{
    AdjList al;
    al = initial();
    search(al);
    return 0;
}

AdjList initial()
{
    AdjList adj_list;
    int vex, arc;
    scanf("%d %d", &vex, &arc);
    adj_list.vexnum = vex; //输入顶点数与边数
    adj_list.arcnum = arc;

    //初始化节点的值
    for (int i = 0; i < vex; i++)
    {
        scanf("%d", &adj_list.vertex[i].data);
        adj_list.vertex[i].firstarc = NULL;//头节点第一个连接点初始化为NULL
    }

    int i, j;
    ArcNode *node = (ArcNode *)malloc(sizeof(ArcNode));
    ArcNode *node_2 = (ArcNode *)malloc(sizeof(ArcNode));
    while (arc--)
    {
        scanf("%d%d", &i, &j);
        for (int ix = 0; ix < vex; ix++)
        {
            if (adj_list.vertex[ix].data == i)
            {
                if (adj_list.vertex[ix].firstarc == NULL)//检查头节点第一个是否为空
                //若为空,意味着第一个节点为空,则加入
                {
                    node->data = j;
                    node->nextarc = NULL;
                    adj_list.vertex[ix].firstarc = node;
                }
                else//否则加到最后面
                {
                    node = adj_list.vertex[ix].firstarc;
                    while (node->nextarc)//遍历走到最后
                    {
                        node = node->nextarc;
                    }
                    node_2->data = j;
                    node_2->nextarc = NULL;
                    node->nextarc = node_2;
                }
            }
        }
    }
    return adj_list;
}

void search(AdjList adj_list)
{
    int src, dst;
    ArcNode *node = (ArcNode *)malloc(sizeof(ArcNode));
    scanf("%d%d", &src, &dst);
    for (int ix = 0; ix < adj_list.vexnum; ix++)
    {
        if (src == adj_list.vertex[ix].data)
        {
            for (node = adj_list.vertex[ix].firstarc;node!=NULL;node = node->nextarc)
            {
                if(node->data == dst)
                {
                    printf("yes\n");
                    return;
                }

            }
        }
    }
    printf("no\n");
    return;
}

-------------本文结束感谢您的阅读-------------
相关文章
感谢阅读.

欢迎关注我的其它发布渠道