大四的萌新辣！

数据结构（二）

Posted on Edited on In Valine:

17.编写一个算法，将带头结点的单向链表拆分成一个奇数链表和一个偶数链表，并分别输出

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 <bits/stdc++.h>
using namespace std;
typedef struct Node
{
    int elem;
    struct  Node *next;
}*Linklist;
void inlinklist(Linklist &l, int n)
{
    l = (Linklist)malloc(sizeof(Node));
    l->next = NULL;
    Linklist p, END;//定义尾部节点
    END = l;
    printf("请输入想要创建的链表元素:\n");
    for(int i = 0; i < n; i++)
    {
        p = (Linklist)malloc(sizeof(Node));
        scanf("%d", &p->elem);
        END -> next = p;
        p->next = NULL;
        END = p;
    }
}
void outlinklist(Linklist l)
{
    printf("链表中的值为:\n");
    Linklist  p;
    p = l->next;
    while(p != NULL)
    {
        printf("%d ", p->elem);
        p = p->next;
    }
    printf("\n");
}
void splitlinklist(Linklist &l1, Linklist &l2, Linklist &l3)
{
    l2 = (Linklist)malloc(sizeof(Linklist));
    l3 = (Linklist)malloc(sizeof(Linklist));
    Linklist p, q, s;
    p = l1;
    q = l2;
    s = l3;
    p = l1 -> next;
    q -> next = s -> next = NULL;
    while(p)
    {
        if(p->elem % 2 == 1)
        {
            q -> next = p;
            //printf("q的元素值:%d\n", q -> elem);
            p = p -> next;
            q = q -> next;
            q -> next = NULL;
        }
        else if(p->elem % 2 == 0)
        {
            s -> next = p;
            //printf("s的元素值:%d\n", s -> elem);
            p = p -> next;
            s = s -> next;
            s -> next = NULL;
        }
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    Linklist L1, L2, L3;
    int n;
    printf("请输入创建n个元素的链表的n值:\n");
    scanf("%d", &n);
    inlinklist(L1, n);
    splitlinklist(L1, L2, L3);
    outlinklist(L2);
    outlinklist(L3);
    return 0;
}

18.已知一个带头结点的单链表lc={a1,b1,a2,b2….,an,bn}共２ｎ个元素，试设计一个算法将其拆分成二个带头结点的单向链表la 与lb,其中la={a1,a2,…an},lb={b1,b2,…,bn}

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
#include <bits/stdc++.h>
using namespace std;
typedef struct Node
{
    int elem;
    struct  Node *next;
}*Linklist;
void inlinklist(Linklist &l, int n)
{
    l = (Linklist)malloc(sizeof(Node));
    l->next = NULL;
    Linklist p, END;//定义尾部节点
    END = l;
    printf("请输入想要创建的链表元素:\n");
    for(int i = 0; i < n; i++)
    {
        p = (Linklist)malloc(sizeof(Node));
        scanf("%d", &p->elem);
        END -> next = p;
        p->next = NULL;
        END = p;
    }
}
void outlinklist(Linklist l)
{
    printf("链表中的值为:\n");
    Linklist  p;
    p = l->next;
    while(p != NULL)
    {
        printf("%d ", p->elem);
        p = p->next;
    }
    printf("\n");
}
void splitlinklist(Linklist &l1, Linklist &l2, Linklist &l3)
{
    l2 = (Linklist)malloc(sizeof(Linklist));
    l3 = (Linklist)malloc(sizeof(Linklist));
    Linklist p, q, s;
    p = l1;
    q = l2;
    s = l3;
    int j = 0;
    while(p)
    {
        j++;
        p = p->next;
    }
    p = l1 -> next;
    q -> next = s -> next = NULL;
    //printf("%d\n", j);//j-1(j包含了头节点)
    for(int i = 0; i < j - 1; i += 2)
    {
        q -> next = p;
        //printf("q的元素值:%d\n", q -> elem);
        p = p -> next;
        q = q -> next;
        q -> next = NULL;
        s -> next = p;
        //printf("s的元素值:%d\n", s -> elem);
        p = p -> next;
        s = s -> next;
        s -> next = NULL;
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    Linklist L1, L2, L3;
    int n;
    printf("请输入创建n个元素的链表的n值:\n");
    scanf("%d", &n);
    inlinklist(L1, n);
    splitlinklist(L1, L2, L3);
    outlinklist(L2);
    outlinklist(L3);
    return 0;
}

19.已知二个带头结点的单向链表la 与lb,其中la={a1,a2,…an},lb={b1,b2,…,bn}， 试设计一个算法将其合并到一个带头结点的单链表lc中，且lc={a1,b1,a2,b2….,an,bn}

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
#include <bits/stdc++.h>
using namespace std;
typedef struct Node
{
    int elem;
    struct  Node *next;
}*Linklist;
void inlinklist(Linklist &l, int n)
{
    l = (Linklist)malloc(sizeof(Node));
    l->next = NULL;
    Linklist p, END;//定义尾部节点
    END = l;
    printf("请输入想要创建的链表元素:\n");
    for(int i = 0; i < n; i++)
    {
        p = (Linklist)malloc(sizeof(Node));
        scanf("%d", &p->elem);
        END -> next = p;
        p->next = NULL;
        END = p;
    }
}
void outlinklist(Linklist l)
{
    printf("链表中的值为:\n");
    Linklist  p;
    p = l->next;
    while(p != NULL)
    {
        printf("%d ", p->elem);
        p = p->next;
    }
    printf("\n");
}
void mergerlinklist(Linklist &l1, Linklist &l2, Linklist &l3)
{
    l3 = (Linklist)malloc(sizeof(Node));
    Linklist p, q, s;
    p = l1->next;
    q = l2->next;
    s = l3;
    while(p != NULL && q != NULL)
    {
        s->next = p;
        //printf("%d ", s->elem);
        s = p;
        p = p->next;
        s->next= q;
        //printf("%d ", s->elem);
        s = q;
        q = q->next;
    }
    s->next = NULL;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    Linklist L1, L2, L3;
    int n;
    printf("请输入创建n个元素的链表的n值:\n");
    scanf("%d", &n);
    inlinklist(L1, n);
    inlinklist(L2, n);
    mergerlinklist(L1, L2, L3);
    outlinklist(L3);
    return 0;
}

20.已知单链表la={a1,a2,…an}，试编写一个算法，将la中的元素进行逆置，即la={an,an-1,…a1}

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
#include <bits/stdc++.h>
using namespace std;
typedef struct Node
{
    int elem;
    struct  Node *next;
}*Linklist;
void inlinklist(Linklist &l, int n)
{
    l = (Linklist)malloc(sizeof(Node));
    l->next = NULL;
    Linklist p, END;//定义尾部节点
    END = l;
    printf("请输入想要创建的链表元素:\n");
    for(int i = 0; i < n; i++)
    {
        p = (Linklist)malloc(sizeof(Node));
        scanf("%d", &p->elem);
        END -> next = p;
        p->next = NULL;
        END = p;
    }
}
void outlinklist(Linklist l)
{
    printf("链表中的值为:\n");
    Linklist  p;
    p = l->next;
    while(p != NULL)
    {
        printf("%d ", p->elem);
        p = p->next;
    }
    printf("\n");
}
void transpose(Linklist &l)
{
    Linklist p, q, s;
    p = l->next;
    l->next = NULL;
    while(p)
    {
        q = p ;
        p = p->next;
        q->next = l->next;
        l->next = q;
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    Linklist L;
    int n;
    printf("请输入创建n个元素的链表的n值:\n");
    scanf("%d", &n);
    inlinklist(L, n);
    transpose(L);
    outlinklist(L);
    return 0;
}
//参考大佬解法:1.https://blog.csdn.net/v_xchen_v/article/details/53067448
//参考大佬解法:2.https://www.cnblogs.com/yepei/p/7120634.html

21.试编写算法创建一个带头结点的单向循环链表la={a1,a2,…an}，并从指定的结点序号起输出循环链表。

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 <bits/stdc++.h>
using namespace std;
typedef struct Node
{
    int elem;
    struct  Node *next;
}*Linklist;
void inlinklist(Linklist &l, int n)
{
    l = (Linklist)malloc(sizeof(Node));
    l->next = NULL;
    Linklist p, END;//定义尾部节点
    END = l;
    printf("请输入想要创建的链表元素:\n");
    for(int i = 0; i < n; i++)
    {
        p = (Linklist)malloc(sizeof(Node));
        scanf("%d", &p->elem);
        END -> next = p;
        p->next = NULL;
        END = p;
    }
}
void outlinklist(Linklist l)
{
    printf("链表中的值为:\n");
    Linklist  p;
    p = l->next;
    while(p != NULL)
    {
        printf("%d ", p->elem);
        p = p->next;
    }
    printf("\n");
}
void special_traversal(Linklist &l, int n)
{
    Linklist p;
    p = l;
    int i = 0;
    while(p && i < n)
    {
        p = p->next;
        i++;
    }
    while(p)
    {
        printf("%d ", p->elem);
        p = p->next;
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    Linklist L;
    int n, m;
    printf("请输入创建n个元素的链表的n值:\n");
    scanf("%d", &n);
    inlinklist(L, n);
    printf("请输入指定的结点序号:\n");
    scanf("%d", &m);
    special_traversal(L, m);
    return 0;
}

22.已知带头结点的单链表la={a1,a2,…an}，试编写一个算法将值重复的结点删除，使所得的结果表中的值均不相同。

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
#include <bits/stdc++.h>
using namespace std;
typedef struct Node
{
    int elem;
    struct  Node *next;
}*Linklist;
void inlinklist(Linklist &l, int n)
{
    l = (Linklist)malloc(sizeof(Node));
    l->next = NULL;
    Linklist p, END;//定义尾部节点
    END = l;
    printf("请输入想要创建的链表元素:\n");
    for(int i = 0; i < n; i++)
    {
        p = (Linklist)malloc(sizeof(Node));
        scanf("%d", &p->elem);
        END -> next = p;
        p->next = NULL;
        END = p;
    }
}
void outlinklist(Linklist l)
{
    printf("链表中的值为:\n");
    Linklist  p;
    p = l->next;
    while(p != NULL)
    {
        printf("%d ", p->elem);
        p = p->next;
    }
    printf("\n");
}
void delete_repeat(Linklist &l)
{
    Linklist p, q, s;
    p = l;
    while(p)
    {
        q = p;
        while(q->next)
        {
            if(q->next->elem == p->elem)
            {
                s = q->next;
                q->next = s->next;
                free(s);
            }
            else
                q = q->next;
        }
        p = p->next;
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    Linklist L;
    int n;
    printf("请输入创建n个元素的链表的n值:\n");
    scanf("%d", &n);
    inlinklist(L, n);
    delete_repeat(L);
    outlinklist(L);
    return 0;
}

23.有一有序的单向链表（允许出现值相同的结点），试设计一个算法将值重复的结点删除，使所得的结果表中的值均不相同。

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 <bits/stdc++.h>
using namespace std;
typedef struct Node
{
    int elem;
    struct  Node *next;
}*Linklist;
void inlinklist(Linklist &l, int n)
{
    l = (Linklist)malloc(sizeof(Node));
    l->next = NULL;
    Linklist p, END;//定义尾部节点
    END = l;
    printf("请输入想要创建的链表元素:\n");
    for(int i = 0; i < n; i++)
    {
        p = (Linklist)malloc(sizeof(Node));
        scanf("%d", &p->elem);
        END -> next = p;
        p->next = NULL;
        END = p;
    }
}
void outlinklist(Linklist l)
{
    printf("链表中的值为:\n");
    Linklist  p;
    p = l->next;
    while(p != NULL)
    {
        printf("%d ", p->elem);
        p = p->next;
    }
    printf("\n");
}
void delete_order_repeat(Linklist &l)
{
    Linklist p, q;
    p = l->next;
    while(p->next)
    {
        if(p->next->elem == p->elem)
        {
            q = p->next;
            p->next = q->next;
            free(q);
        }
        else
            p = p->next;
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    Linklist L;
    int n;
    printf("请输入创建n个元素的链表的n值:\n");
    scanf("%d", &n);
    inlinklist(L, n);
    delete_order_repeat(L);
    outlinklist(L);
    return 0;
}

24.已知一个带头结点的单链表lc中结点数据元素类型为字符型数据，主在包括二类字符（字母字符与数字字符），试设计一个算法，将lc拆分成二个链表la与lb，其中la的数据为字母字符，lb的数据为数字字符。

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
#include <bits/stdc++.h>
#define debug printf("You Code AC!\n")
using namespace std;
typedef struct Node
{
    char elem;
    struct  Node *next;
}*Linklist;
void inlinklist(Linklist &l, int n)
{
    l = (Linklist)malloc(sizeof(Node));
    l->next = NULL;
    Linklist p, END;//定义尾部节点
    END = l;
    printf("请输入想要创建的链表元素:\n");
    for(int i = 0; i < n; i++)
    {
        p = (Linklist)malloc(sizeof(Node));
        scanf("%c", &p->elem);
        END -> next = p;
        p->next = NULL;
        END = p;
    }
}
void outlinklist(Linklist l)
{
    printf("链表中的值为:\n");
    Linklist  p;
    p = l->next;
    while(p != NULL)
    {
        printf("%c ", p->elem);
        p = p->next;
    }
    printf("\n");
}
void splitlinklist(Linklist &l1, Linklist &l2, Linklist &l3)
{
    l2 = (Linklist)malloc(sizeof(Linklist));
    l3 = (Linklist)malloc(sizeof(Linklist));
    Linklist p, q, s;
    p = l1;
    q = l2;
    s = l3;
    p = l1 -> next;
    q -> next = s -> next = NULL;
    while(p)
    {
        if(((p->elem) >= 'a' && (p->elem) <= 'z')||((p->elem) >= 'A' && (p->elem) <= 'Z'))
        {
            q -> next = p;
            debug;
            //printf("q的元素值:%c\n", q -> elem);
            p = p -> next;
            q = q -> next;
            q -> next = NULL;
        }
        else if((p->elem) >= '0' && (p->elem) <= '9')
        {
            s -> next = p;
            //printf("s的元素值:%c\n", s -> elem);
            p = p -> next;
            s = s -> next;
            s -> next = NULL;
        }
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    Linklist L1, L2, L3;
    int n;
    printf("请输入创建n个元素的链表的n值:\n");
    scanf("%d", &n);
    getchar();
    inlinklist(L1, n);
    splitlinklist(L1, L2, L3);
    outlinklist(L2);
    outlinklist(L3);
    return 0;
}

25.设单链表的前二个结点值为均为１，从第三个结点开始，结点值为前二个结点值之各，试设计一个具有ｎ（２５＞ｎ＞＝３）个结点的单向链表，并输出。

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100;
typedef struct Node
{
    int elem;
    struct  Node *next;
}*Linklist;
int arr[maxn];
void fibonacci_number(int arr[maxn])
{
    arr[1] = arr[2] = 1;
    for(int i = 3; i <= maxn; i++)
    {
        arr[i] = arr[i-1] + arr[i-2];
    }
}
void inlinklist(Linklist &l, int n)
{
    l = (Linklist)malloc(sizeof(Node));
    l->next = NULL;
    Linklist p, END;//定义尾部节点
    END = l;
    printf("想要创建的链表元素:\n");
    for(int i = 0; i < n; i++)
    {
        p = (Linklist)malloc(sizeof(Node));
        p->elem = arr[i+1];
        END -> next = p;
        p->next = NULL;
        END = p;
    }
}
void outlinklist(Linklist l)
{
    printf("链表中的值为:\n");
    Linklist  p;
    p = l->next;
    while(p != NULL)
    {
        printf("%d ", p->elem);
        p = p->next;
    }
    printf("\n");
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    Linklist L;
    int n;
    fibonacci_number(arr);
    printf("请输入创建n个元素的链表的n值:\n");
    scanf("%d", &n);
    inlinklist(L, n);
    outlinklist(L);
    return 0;
}

26.从键盘上输入一串括号组成的字符串，试编写一个算法，判断所输入的括号是否匹配，如匹配输出１否则输出０

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
#include <bits/stdc++.h>
#define debug1(x) {printf("%c ",x);}
#define debug2 {printf("You Code AC!\n");}
using namespace std;
const int maxn = 1000 + 10;
typedef struct Stack
{
    char *base;
    char *top;
    int stacksize;
}sqstack;
void createsqstack(sqstack &s)
{
    s.base = (char*)malloc(maxn * sizeof(char));
    s.top = s.base;
    s.stacksize = maxn;
}
void push(sqstack &s, char ch)
{
    if(s.top - s.base >= maxn)
    {
        s.base = (char *)realloc(s.base, (s.stacksize + maxn) * sizeof(char));
        s.top = s.base + s.stacksize;
        s.stacksize += maxn;
    }
    *s.top++ = ch;
}
char pop(sqstack &s)
{
    if(s.top == s.base)
        return '#';
        //printf("该栈已空\n");
    return *--s.top;
}
char gettop(sqstack &s)
{
    if(s.top == s.base)
        return '#';
        //printf("该栈已空\n");
    return *(s.top-1);
}
bool match(sqstack &s, char* str)
{
    push(s,str[0]);
    for(int i = 1; i < strlen(str); i++)
    {
        char flag = gettop(s);
        switch(flag)
        {
            case '(':
                if(str[i] == ')')
                    pop(s);
                else
                    push(s, str[i]);
                break;
            case '[':
                if(str[i] == ']')
                pop(s);
                else
                push(s, str[i]);
                break;
            case '#':
                if(str[i] == '(' || str[i] == ']')
                    push(s, str[i]);
                break;
            default:
                break;
        }
    }
    if(s.base == s.top)
        return true;
    else
        return false;
}
int main(void)
{
    Stack s;
    int n;
    char ch;
    char str[100];
    printf("请输入字符串:\n");
    scanf("%s", str);
    //for(int i = 0; i <= strlen(str); i++)
        //debug1(str[i]);
    createsqstack(s);
    bool conclusion = match(s, str);
    if(conclusion == true)
        printf("1\n");
    else
        printf("0\n");
    return 0;
}

27.从键盘上输入一个十进制数n，试编写一个算法，将其转换成对应的ｐ进制输出（ｐ为2.8.16）

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 10;
typedef struct Stack
{
    int *base;
    int *top;
    int stacksize;
}sqstack;
void createsqstack(sqstack &s)
{
    s.base = (int*)malloc(maxn * sizeof(int));
    s.top = s.base;
    s.stacksize = maxn;
}
void push(sqstack &s, int n)
{
    *s.top++ = n;
}
int pop(sqstack &s)
{
    return *--s.top;
}
bool is_stackempty(sqstack s)
{
    if(s.base == s.top)
        return true;//代表栈为空
    else
        return false;//代表栈不为空
}
void converison(sqstack &s, int n, int base)
{
    while (n)
    {
        push(s, n % base);
        n /= base;
    }
    while (!is_stackempty(s))
    {
        int x = pop(s);
        printf("%d  ",x);
    }
}
int main(void)
{
    sqstack s;
    createsqstack(s);
    int n, base;
    printf("请输入你要转换的数字和进制数:\n");
    scanf("%d%d", &n, &base);
    converison(s, n, base);
    return 0;
}

28.从键盘上输入二个定长串s1与s2，试编写一个算法判断s1是否是s2的子串，如果是则输出１否则输出０

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100 + 10;
typedef char SString[maxn];
void createstring(SString s, char *str)
{
    s[0] = strlen(str);
    for(int i = 1; i <= s[0]; i++)
    {
        s[i] = str[i - 1];
    }
}
void printstring(SString s)
{
    for(int i = 1; i <= s[0]; i++)
        printf("%c ",s[i]);
    printf("\n");
}
bool SString_match(SString s1, SString s2)
{
    int i, j;
    i = j = 1;
    while(i <= s1[0] && j <= s2[0])
    {
        if(s1[i] == s2[j])
        {
            i++;
            j++;
        }
        else
        {
            i = i - j + 2;
            j = 1;
        }
    }
    if(j > s2[0])
        return true;
    else
        return false;
}
int main(void)
{
    char str1[maxn], str2[maxn];
    SString s1, s2;
    printf("请创建第一个定长串s1:\n");
    scanf("%s", str1);
    getchar();
    printf("请创建第二个定长串s2:\n");
    scanf("%s",str2);
    createstring(s1, str1);
    createstring(s2, str2);
    //printstring(s1);
    //printstring(s2);
    bool is_SString_match = SString_match(s1, s2);
    if(is_SString_match)
        printf("1\n");
    else
        printf("0\n");
    return 0;
}

30.假设二叉树采用二叉链表存储结构，试设计一个算法求二叉树的叶子结点数并输出所有的叶子结点

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
#include <bits/stdc++.h>
using namespace std;
int ans = 0;
typedef struct BinTree
{
    char data;
    struct BinTree *lchild;
    struct BinTree *rchild;
}binnode, *bintree;
void creatbintree(bintree &T)
{
    char ch;
    scanf("%c",&ch);
    if(ch =='#')
        T = NULL;
    else
    {
        T = (bintree)malloc(sizeof(bintree));
        T->data = ch;
        creatbintree(T->lchild);
        creatbintree(T->rchild);
    }
}
void LNR(bintree T)
{
    if(T)
    {
        LNR(T->lchild);
        printf("%c ",T->data);
        LNR(T->rchild);
    }
}
void leaf_node(bintree T)
{
    if(T == NULL)
        return;
    if(T->lchild ==  NULL && T->rchild == NULL)
        ans++;
    else
    {
        leaf_node(T->lchild);
        leaf_node(T->rchild);
    }
}
int main(void)
{
    int n;
    bintree T;
    printf("请输入二叉树的节点数目:\n");
    scanf("%d", &n);
    getchar();
    creatbintree(T);
    leaf_node(T);
    printf("叶子结点数目:%d\n",ans);
    return 0;
}

31.假设二叉树采用二叉链表存储结构，试设计一个算法求二叉树的高度并给出指定结点的所在的层数（高度）

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
#include <bits/stdc++.h>
using namespace std;
typedef struct BinTree
{
    char data;
    struct BinTree *lchild;
    struct BinTree *rchild;
}binnode, *bintree;
void creatbintree(bintree &T)
{
    char ch;
    scanf("%c",&ch);
    if(ch =='#')
        T = NULL;
    else
    {
        T = (bintree)malloc(sizeof(bintree));
        T->data = ch;
        creatbintree(T->lchild);
        creatbintree(T->rchild);
    }
}
void LNR(bintree T)
{
    if(T)
    {
        LNR(T->lchild);
        printf("%c ",T->data);
        LNR(T->rchild);
    }
}
int height(bintree T)
{
    int a, b, max;
    if(T)
    {
        a = height(T->lchild);
        b = height(T->rchild);
        max = a > b ? a : b;
        return (max + 1);
    }
    else
        return 0;
}
int finddeep(bintree T, char s, int ans,int &x)
{
    if(T)
    {
        ans++;
        if(T->data = s)
        {
            x = ans;
        }
        finddeep(T->lchild, s, ans, x);
        finddeep(T->rchild, s, ans, x);
    }
}
int main(void)
{
    int n;
    char s;
    int x = 0;
    bintree T;
    printf("请输入二叉树的节点数目:\n");
    scanf("%d", &n);
    getchar();
    creatbintree(T);
    printf("树的高度:%d\n",height(T));
    printf("AC!!!\n");
    printf("请输入结点值:\n");
    getchar();
    scanf("%c", &s);
    finddeep(T, s,0,x);
    printf("结点值的:%d\n",x);
    return 0;
}