Sekyoro的博客小屋

数据结构noj_1

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

数据结构noj_1

个人做的，不当之处欢迎提出，希望一起改进。

先发前10题 因为后面我也没做

1.

image-20210416000331032

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>
#define maxsize 1000
typedef struct list
{
    int elenum;
    int element[maxsize];
}list,* plist;
int main(void)
{
    int size;
    int num;
    int insert_num;
    int i,j;  
    scanf("%d",&size);
    plist l = (plist)malloc(sizeof(list));
 
        l->elenum=size;
        for(i = 0; i<l->elenum ;i++)
        {
            scanf("%d",&num);
            l->element[i] = num;
        }
        scanf("%d",&insert_num);      
        for(i = 0;i<l->elenum;i++)
        {
            if(l->element[i]>=insert_num)
            {
                for( j = size;j>i;j--)
                {
                l->element[j] = l->element[j-1];      
                }
                l->element[j] = insert_num;
                break;
            }
        }
        if(i==l->elenum)
        l->element[i] = insert_num;
        l->elenum++;   
    
 
    for(i=0;i<l->elenum;i++)
    {
        printf("%d%c",l->element[i],(i==l->elenum-1)?'\n':' ');
    }
    return 0;
}

2.

image-20210416000434268

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
#include <stdio.h>
#include <stdlib.h>
#define maxsize 1000
typedef struct Sequence_List
{
    int element[maxsize];
    int elenum;
} List, *pList;

typedef struct LinkList
{
    int num;
    struct LinkList *next;
} Node, *pLinkList;
int main(void)
{
    pList pa = (pList)malloc(sizeof(List));
    pLinkList pb, s, r;
    int size, i, num;
    scanf("%d", &size);
    pa->elenum = size;
    pb = (pLinkList)malloc(sizeof(Node));
    pb->next = NULL;
    s = pb;
    for (i = 0; i < size; i++)
    {
        scanf("%d", &num);
        pa->element[i] = num;
        r = (pLinkList)malloc(sizeof(Node));
        r->num = num;
        s->next = r;
        s = r;
    }
    s->next = NULL;
    int temp;
    for (i = 0; i <= (size - 1) / 2; i++)
    {
        temp = pa->element[i];
        pa->element[i] = pa->element[size - 1 - i];
        pa->element[size - i - 1] = temp;
    } //顺序表逆序
    s = pb->next;
    pb->next = NULL;
    Node *p;
    while (s)
    {
        p = s;
        s = s->next;
        p->next = pb->next;
        pb->next = p;
    }
    for (i = 0; i < size; i++)
    {
        printf("%d%c", pa->element[i], (i == size - 1) ? '\n' : ' ');
    }
    while (p)
    {
        printf("%d%c", p->num, (p->next == NULL) ? '\n' : ' ');
        p = p->next;
    }
    free(pa);
    free(pb);
    return 0;
}

3.

image-20210416000510643

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 maxsize 1000
typedef struct List
{
    int length;
    int data[maxsize];
} List, *pList;
void give_value(pList);
pList cross_list(pList, pList);
void delete_list(pList, int);
void delete_num(pList, pList);
int main(void)
{
    int i ;
    pList pa ;
    pa = (pList)malloc(sizeof(List));
    pList pb = (pList)malloc(sizeof(List));
    pList pc = (pList)malloc(sizeof(List));
    scanf("%d %d %d", &pa->length, &pb->length, &pc->length);
    give_value(pa);
    give_value(pb);
    give_value(pc);
    pb = cross_list(pb, pc);
    delete_num(pa, pb);
    for (i = 0; i < pa->length; i++)
    printf("%d%c", pa->data[i], (i == pa->length - 1) ? '\n' : ' ');
    free(pa);
    free(pb);
    free(pc);
    return 0;
}

void give_value(pList p)
{
    int num ;
    int i ;
    for (i = 0; i < p->length; i++)
    {
        scanf("%d", &num);
        p->data[i] = num;
    }
}
pList cross_list(pList p, pList q)
{
    pList result = (pList)malloc(sizeof(List));
    int i, j;
    int t ;
    i = 0;
    j = 0;
    t =0;
    while (i < p->length && j < q->length)
    {
        if (p->data[i] > q->data[j])
        {
            j++;   
        }
        else
        if(p->data[i] < q->data[j])
        {
            i++;
        }
        else
        {
            result->data[t] = p->data[i];
            i++;
            j++;
            t++;
        }
    }
    result->length = t+1;
    return result;
}
void delete_num(pList pa, pList pb)
{
    int i ;
    int j ;
    for (i = 0; i < pb->length; i++)
    {
        for (j = 0; j < pa->length;)
        {
            if (pb->data[i] < pa->data[j])
            {
                break;
            }
            else if (pb->data[i] > pa->data[j])
            {
                j++;
            }
            else
            {
                delete_list (pa, j);
                break;
            }
        }
    }
}
void delete_list(pList p, int n)
{
    int i ;
    for (i = n; i < p->length - 1; i++)
    {
        p->data[i] = p->data[i + 1];
    }
    p->length--;
}

4.

image-20210416000602232

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
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
    int data;
    struct Node* next;
}Node,*Linklist;
Linklist initial_list(Linklist,int);
void merge(Linklist,Linklist);
int main(void)
{
    Linklist L,M;
    int n = 0,m=0;
    scanf("%d %d",&n,&m);
    L = initial_list(L,n);
    M = initial_list(M,m);
    merge(L,M);
    L = L->next;
    while(L)
    {
        printf("%d%c",L->data,(L->next==NULL)?'\n':' ');
        L = L->next;
    }
    return 0;

}
void merge(Linklist pa,Linklist pb)
{
    Linklist p=pa->next,q=pb->next;
    pb->next = NULL;
    while(p&&q)
    {
        if(p->data>q->data)
        {
            pa->next = p;
            p = p->next;
            pa = pa->next;
        }
        else
            {
                pa->next = q;
                q = q->next;
                pa = pa->next;

            }

    }
    while (p/* condition */)
    {
        pa->next = p;
        pa = p;
        p = p->next;
        /* code */
    }
    while(q)
    {
        pa->next = q;
        pa = q;
        q = q->next;
    }
    pa->next = NULL;

}
Linklist initial_list(Linklist L,int n)
{
    L = (Linklist)malloc(sizeof(Node));
    L->next = NULL;
    int num=0;
    Linklist s = NULL;
    while(n--)
    {
        s = (Linklist)malloc(sizeof(Node));
        scanf("%d",&num);
        s->data = num;
        s->next = L->next;
        L->next = s;
    }
    return L;
}

5.

image-20210416000639344

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
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
    int data;
    struct Node *next;
} Node, *Linklist;
void give_value(Linklist, int);
void cross_list(Linklist, Linklist);
void delete_list(Linklist, Linklist);
int main(void)
{
    Linklist pa = (Linklist)malloc(sizeof(Node));
    Linklist pb = (Linklist)malloc(sizeof(Node));
    Linklist pc = (Linklist)malloc(sizeof(Node));
    int num_1, num_2, num_3;
    scanf("%d %d %d", &num_1, &num_2, &num_3);
    give_value(pa, num_1);
    give_value(pb, num_2);
    give_value(pc, num_3);
    cross_list(pb, pc);
    delete_list(pa, pb);
    while (pa->next)
    {
        printf("%d%c", pa->next->data,(pa->next==NULL)?'\n':' ');
        pa = pa->next;
    }
    return 0;
}
void delete_list(Linklist pa, Linklist pb)
{
    Linklist tail = pa;
    Linklist p = tail->next;
    Linklist q;
    while (p)
    {
        q = pb->next;
        while (q)
        {
            if (p->data == q->data)
            {
                p = p->next;
                free(tail->next);
                tail->next = p;
                break;
            }
            else
            {
                q = q->next;
            }
        }
        if (q == NULL)
        {
            tail = tail->next;
            p = tail->next;
        }
    }
}
void give_value(Linklist p, int n)
{
    Linklist s, r;
    s = p;
    while (n--)
    {
        r = (Linklist)malloc(sizeof(Node));
        scanf("%d", &r->data);
        s->next = r;
        s = s->next;
    }
    s->next = NULL;
}
void cross_list(Linklist p, Linklist q)
{
    Linklist s, r, tail;
    tail = p;
    s = tail->next;
    while (s)
    {
        r = q->next;
        while (r)
        {
            if (s->data == r->data)
            {
                tail = tail->next;
                s = tail->next;
                break;
            }
            else
            {
                r = r->next;
            }
        }
        if (r == NULL)
        {
            s = s->next;
            free(tail->next);
            tail->next = s;
        }
    }
}

6.

image-20210416000713105

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

typedef struct Node
{
    int data;
    struct Node *pre;
    struct Node *next;
    int freq;
} Node, *pNode;
void sort(const pNode,int);
void initial(const pNode, int);
void Locate_(const pNode, char);
void print_List(const pNode);

int main(void)
{
    pNode pa = (pNode)malloc(sizeof(Node));
    int size, l_size;
    char ch;
    scanf("%d %d", &size, &l_size);
    initial(pa, size);
    while(l_size--)
    {
        scanf("%c",&ch);
        while(ch<='A'||ch>='z')
        {
            scanf("%c",&ch);
        }
        Locate_(pa,ch);
    }
    sort(pa,size);
    print_List(pa);
    return 0;
}
void print_List(pNode p)
{
    pNode r;
    r = p->next;
    while(r != p)
    {
        printf("%c%c",r->data,(r->next==NULL)?'\n':' ');
        r = r->next;
    }
}
void sort(const pNode p,int size)
{
  pNode head,pa,pb;
  int i,j;
  for(i=0;i<size-1;i++)
  {
      head = p;
      pa = head->next;
      pb = pa->next;
      j = size-i-1;
      while(j--)
      {
          if(pa->freq<pb->freq)
          {
              pa->next = pb->next;
              pb->next = pa;
              head->next = pb;
          }
          head = head->next;
          pa = head->next;
          pb = pa->next;
      }
  }
}
void Locate_(const pNode p, char ch)
{
    pNode r = p->next;
    while (r != p)
    {
        if (r->data == ch)
        {
            (r->freq)++;
            // printf("%c++\n",r->data);
            break;
        }
        else
        {
            r = r->next;
        }
    }
}
void initial(const pNode p, int size)
{
    pNode s, r;
    r = p;
    int ch;
    while (size--)
    {
        s = (pNode)malloc(sizeof(Node));
        scanf("%c",&ch);
        while(ch<='A'||ch>='z')
        {
            scanf("%c",&ch);
        }
        s->data = ch;
        s->freq = 0;
        s->pre = r;
        r->next = s;
        p->pre = s;
        s->next = p;
        r = s;
    }
}

7.

image-20210416000746427

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

typedef struct Stack
{
    int op;
    struct Stack *next;
}stack,*pStack;

int match(int,int);
void push_(pStack,int);
int pop(pStack);
int get_Pop(pStack);
int main(void)
{
    int ch;
    int flag=1;
    pStack op_stack = (pStack)malloc(sizeof(stack));
    op_stack->next = NULL;
    while((ch=getchar())!=EOF&&ch!='\n')
    {
        switch(ch)
        {
            case '{':
            case '[':
            case '(':
            push_(op_stack,ch);
            break;
            case ')':
            case ']':
            case '}':
            if(match(get_Pop(op_stack),ch))
            {
                pop(op_stack);
                break;
            }
            else
            {
                flag=0;
                break;
            }
            break;
            default:continue;
        }

    }
        if(flag)
        printf("yes\n");
        else
        printf("no\n");
        return 0;
}
void push_(pStack top,int ch)
{
    pStack s = (pStack)malloc(sizeof(stack));
    s->op = ch;
    s->next = top->next;
    top->next = s;
}
int pop(pStack top)
{
    int ret;
    pStack r = top->next;
    if(r==NULL)
    return 0;
    ret = r->op;
    top->next = r->next;
    free(r);
    return ret;
}
int get_Pop(pStack top)
{
    int ret;
    pStack r = top->next;
    if(r==NULL)
    return 0;
    ret = r->op;
    return ret;
}
int match(int src,int dst)
{
    int flag=0;
    if(src=='{')
    {
        if(dst=='}')
        flag=1;
    }
    else
    if(src=='[')
    {
        if(dst==']')
        flag=1;
    }
    else
    if(src=='(')
    {
        if(dst==')')
        flag=1;
    }
    if(flag)
    return 1;
    else
    return 0;
}

8.

image-20210416000817929

9.

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
#include <stdio.h>
#include <stdlib.h>
typedef struct Stack_
{
    int data;
    struct Stack_ *next;
} Stack_, *pStack;

void push_(pStack, int);
void pop_(pStack);
int get_top(pStack);
int is_alpha(int);
int is_op(int);
int compare_(int, int);
void Bolan(pStack, int);
int is_empty(pStack);

int main(void)
{
    pStack opr = (pStack)malloc(sizeof(Stack_));
    int ch;
    opr->next = NULL;
    while ((ch = getchar()) != '\n' && ch != EOF)
    {
        if (ch == '(')
            push_(opr, ch);
        else if (is_alpha(ch))
            printf("%c", ch);
        else
            Bolan(opr, ch);
    }
    while (!is_empty(opr))
    {
        printf("%c", opr->next->data);
        pop_(opr);
    }
    free(opr);
    return 0;
}
int is_empty(pStack pa)
{
    if (pa->next)
        return 0;
    return 1;
}
int is_op(int ch)
{
    if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
        return 1;
    return 0;
}

void pop_(pStack head)
{
    pStack pop_s = head->next;
    head->next = pop_s->next;
    free(pop_s);
}
int compare_(int op_1, int op_2)
{
    if (op_1 == '*' || op_1 == '/')
    {
        if (op_2 == '+' || op_2 == '-')
            return 1;
    }
    if (op_2 == '(')
        return 1;
    else if (op_2 == 0)//无元素，为空栈
    {
        return 1;
    }
    return 0;
}

int get_top(pStack head)
{
    if (is_empty(head))
        return 0;
    return head->next->data;
}
void push_(pStack head, int ch)
{
    pStack r = (pStack)malloc(sizeof(Stack_));
    r->data = ch;
    r->next = head->next;
    head->next = r;
}
int is_alpha(int ch)
{

    if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))
        return 1;
    return 0;
}

void Bolan(pStack opr, int ch)
{
    int top_ch;
    if (ch == ')')
    {
        while ((top_ch = get_top(opr)) != '(')
        {
            printf("%c", top_ch);
            pop_(opr);
        }
        pop_(opr);
    }
    else
    {
        top_ch = get_top(opr);

        if (compare_(ch, top_ch)) //比较
        {
            push_(opr, ch);
        }
        else
        {
            pop_(opr);
            printf("%c", top_ch);
            push_(opr, ch);
        }
    }
}

10.

image-20210416001130594

这个题系统设置有问题，不用太注意

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

typedef struct Queue
{
    int Element[maxsize];
    int rear;
    int length;
    int head;
} Queue, *pQueue;

void initial(pQueue);
// void push(pQueue, int);
void pop(pQueue);
int get_top(pQueue);
void print(pQueue);

int main(void)
{
    pQueue queue = (pQueue)malloc(sizeof(Queue));
    if (!queue)
    {
        printf("malloc fail");
        exit(1);
    }
    initial(queue);
    // fflush(stdin);
    if(queue->rear<=queue->length)
    {
        char temp[100];
        scanf("%s",temp);
    }
    int pop_date;
    scanf("%d",&pop_date);
    while(get_top(queue)!=pop_date)
    {
        pop(queue);
    }
    pop(queue);
    print(queue);
    return 0;
}
void initial(pQueue q)
{
    int date;
    scanf("%d", &q->length);
    q->head = q->rear = 0;
    do
    {
        scanf("%d", &date);
        q->Element[q->rear] = date;
        (q->rear)++;
    }while((q->rear<q->length)&&getchar()!='\n');
}
void print(pQueue q)
{
    for(int i = (q->head)%q->length;i<q->rear;i++)
    printf("%d%c",q->Element[i],(i==q->rear-1)?'\n':' ');
    if(q->head!=q->rear)
    printf("%d",get_top(q));
    printf("\n");
}
// void push(pQueue q, int x)
// {
//     // if ((q->rear+1)%q->length==q->head)
//     // return false;
//     q->Element[q->rear] = x;
//     q->rear = (q->rear+1)%(q->length);
// }
int get_top(pQueue q)
{
    int x;
    x = q->Element[q->head];
    return x;
}
void pop(pQueue q)
{
    // if(q->head==q->rear)
    // return false;
    q->Element[q->head] = 0;
    q->head = (q->head+1)%q->length;
}

image-20210416001238359

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

typedef struct Queue
{
    int data[Maxsize];
    int rear;
    int head;
} Queue, *pQueue;

void initial(pQueue, int);        //初始化队列，将前k项赋值，前k-1项为0，k项为1
void fibonacci(pQueue, int, int); //叠加，求得k的值
void print(pQueue, int);          //输出
void add(pQueue, int);

int main(void)
{
    int max, k;
    scanf("%d %d", &max, &k);
    pQueue q = (pQueue)malloc(sizeof(Queue));
    initial(q, k);
    fibonacci(q, max, k);
    print(q, k);
    return 0;
}
void print(pQueue q, int t)
{
    for (int i = q->head; i <= q->rear; i++)
    {
        printf("%d%c", q->data[i], (i == q->rear) ? '\n' : ' ');
    }
}
void initial(pQueue q, int k)
{
    for (int i = 0; i <= k - 1; i++)
        q->data[i] = 0;
    q->head = 1;
    q->data[k] = 1;
    q->rear = (q->head) + k - 1;
}
void fibonacci(pQueue q, int max, int k)
{

    while (!((q->data[q->rear] <= max) && (q->data[(q->rear) + 1] > max)))
    {

        add(q, k);
    }
}
void add(pQueue q, int t)
{
    q->head += 1;
    q->rear = q->head + t - 1;
    for (int k = q->head; k <= (q->rear) + 1; k++)
    {

        if (k < t)
        {
            q->data[k] = 0;
            continue;
        }
        else if (k == t)
        {
            q->data[k] = 1;
            continue;
        }
        else
        {
            q->data[k] = 0;
            for (int i = k - t; i < k; i++)
            {
                q->data[k] += q->data[i];
            }
        }
    }
}
-------------本文结束感谢您的阅读-------------
相关文章
感谢阅读.

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