大四的萌新辣！

数据结构（一）

Posted on Edited on In Valine:

1.已知顺序表L的长度为n，试编写算法实现在顺序表中删除值为elem的数据元素（其中n与elem从键盘输入）

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;
const int maxn = 1000 + 10;
typedef struct node
{
    int *arr;
    int length;
    int maxsize;
}sqlist;
void createsqlist(sqlist &l)
{
    l.arr = (int*)malloc(maxn * sizeof(int));
    l.length = 0;
    l.maxsize = maxn;
}
void insqlist(sqlist &l, int n)
{
    int *p;
    printf("请依次输入数字来创建顺序表:\n");
    for(p = l.arr; p < l.arr + n; p++)
    {
        scanf("%d", p);
    }
    l.length = n;
}
void outsqlist(sqlist l)
{
    int *p;
    printf("顺序表的元素为:\n");
    for(p = l.arr; p < l.arr + l.length; p++)
        printf("%d ", *p);
}
void deletesqlist(sqlist &l, int elem)
{
    int i = 0;
    while(i < l.length && l.arr[i] != elem)
        i++;
    for(int j = i + 1; j < l.length; j++)
    {
        if(l.arr[j] != elem)
        {
            l.arr[i++] = l.arr[j];
        }
    }
    l.length = i;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, elem;
    sqlist L;
    createsqlist(L);
    printf("请输入n个元素:\n");
    scanf("%d", &n);
    insqlist(L, n);
    printf("请输入删除的元素值:\n");
    scanf("%d", &elem);
    deletesqlist(L, elem);
    outsqlist(L);
    return 0;
}

2.已知顺序表L长度为n，试编写算法实现在顺序表中值为elem的数据元素的后面插入一个值为key的数据元素（其中n、elem与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
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;
const int maxn = 1000 + 10;
typedef struct node
{
    int *arr;
    int length;
    int maxsize;
}sqlist;
void createsqlist(sqlist &l)
{
    l.arr = (int*)malloc(maxn * sizeof(int));
    l.length = 0;
    l.maxsize = maxn;
}
void insqlist(sqlist &l, int n)
{
    int *p;
    printf("请依次输入数字来创建顺序表:\n");
    for(p = l.arr; p < l.arr + n; p++)
    {
        scanf("%d", p);
    }
    l.length = n;
}
void outsqlist(sqlist l)
{
    int *p;
    printf("顺序表的元素为:\n");
    for(p = l.arr; p < l.arr + l.length; p++)
        printf("%d ", *p);
}

void insertsqlist(sqlist &l, int elem, int key)
{

    int flag;
    int *p;
    for(p = l.arr; p < l.arr + l.length; p++)
        if(*p == elem)
        {
            flag = p - l.arr;
        }
    for(p = l.arr + l.length; p >= l.arr + flag + 1; p--)
        *(p + 1) = *p;
    l.arr[flag + 1] = key;
    l.length++;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, elem, key;
    sqlist L;
    createsqlist(L);
    printf("请输入n个元素:\n");
    scanf("%d", &n);
    insqlist(L, n);
    printf("请输入要插入后边的元素的值和插入的元素值:\n");
    scanf("%d %d", &elem, &key);
    insertsqlist(L, elem, key);
    outsqlist(L);
    return 0;
}

3.已知顺序表{a0,a1,a2,…,an-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
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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 10;
typedef struct node
{
    int *arr;
    int length;
    int maxsize;
}sqlist;
void createsqlist(sqlist &l)
{
    l.arr = (int*)malloc(maxn * sizeof(int));
    l.length = 0;
    l.maxsize = maxn;
}
void insqlist(sqlist &l, int n)
{
    int *p;
    printf("请依次输入数字来创建顺序表:\n");
    for(p = l.arr; p < l.arr + n; p++)
    {
        scanf("%d", p);
    }
    l.length = n;
}
void outsqlist(sqlist l)
{
    int *p;
    printf("顺序表的元素为:\n");
    for(p = l.arr; p < l.arr + l.length; p++)
        printf("%d ", *p);
}
void swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
void change(sqlist &l)
{
    int *i = l.arr;
    int *j = l.arr + l.length - 1;
    while(i < j)
    {
        while((*i) % 2 == 0)//偶数
            i++;
        while((*j) % 2 == 1)//奇数
            j--;
        //printf("%d  %d",*i, *j);
        if(i < j)
        {
            swap(i, j);
            i++;
            j--;
        }
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    sqlist L;
    createsqlist(L);
    printf("请输入n个元素:\n");
    scanf("%d", &n);
    insqlist(L, n);
    change(L);
    outsqlist(L);
    return 0;
}

4.已知二个集合la与lb,采用顺序结构存储，其中la={a1,a2,…an},lb={b1,b2,…,bｍ}， 试设计一个算法将其合并到一个顺序表lc中。

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
#include <bits/stdc++.h>
using  namespace std;
const int maxn = 1000 + 10;
typedef struct node
{
    int *arr;
    int length;
    int maxsize;
}sqlist;
void createsqlist(sqlist &l)
{
    l.arr = (int*)malloc(maxn * sizeof(int));
    l.length = 0;
    l.maxsize = maxn;
}
void insqlist(sqlist &l, int n)
{
    printf("请依次输入数字来创建顺序表:\n");
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &l.arr[i]);
    }
    l.length = n;
}
void outsqlist(sqlist l)
{
    int i;
    printf("顺序表的元素为:\n");
    for(int i = 0; i < l.length; i++)
        printf("%d ", l.arr[i]);
}
void merger(sqlist &l1, sqlist &l2, sqlist &l3)
{
    for(int i = 0; i < l1.length ; i++)
    {
        l3.arr[i] = l1.arr[i];
    }
    l3.length = l1.length;
    for(int i = 0; i < l2.length; i++)
    {
        l3.arr[i + l1.length] = l2.arr[i];
    }
    l3.length += l2.length;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    sqlist  L1, L2, L3;
    printf("请输入n和m的值来创建两个顺序表:\n");
    scanf("%d %d", &n, &m);
    createsqlist(L1);
    createsqlist(L2);
    createsqlist(L3);
    insqlist(L1, n);
    insqlist(L2, m);
    merger(L1, L2, L3);
    outsqlist(L3);
    return  0;
}

5.已知一个顺序表la，其中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
#include <bits/stdc++.h>
using  namespace std;
const int maxn = 1000 + 10;
typedef struct node
{
    int *arr;
    int length;
    int maxsize;
}sqlist;
void createsqlist(sqlist &l)
{
    l.arr = (int*)malloc(maxn * sizeof(int));
    l.length = 0;
    l.maxsize = maxn;
}
void insqlist(sqlist &l, int n)
{
    printf("请依次输入数字来创建顺序表:\n");
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &l.arr[i]);
    }
    l.length = n;
}
void outsqlist(sqlist l)
{
    int i;
    printf("顺序表的元素为:\n");
    for(int i = 0; i < l.length; i++)
        printf("%d ", l.arr[i]);
}
void swap(int &a, int &b)
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}
void sortsqlist(sqlist l)
{
    for(int i = 0; i < l.length ; i++)
    {
        for(int j = 0; j < l.length - 1; j++)
        {
            if(l.arr[j] > l.arr[j + 1])
            {
                //int temp = l.arr[j];
                //l.arr[j] = l.arr[j + 1];
                //l.arr[j + 1] = temp;
                swap(l.arr[j], l.arr[j + 1]);
            }
        }
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    sqlist L;
    int n;
    createsqlist(L);
    printf("请输入n的值来创建一个顺序表:\n");
    scanf("%d", &n);
    insqlist(L, n);
    sortsqlist(L);
    outsqlist(L);
    return  0;
}

6.已知二个顺序la与lb，其中la={a1,a2,…an}，lb={b1,b2,…bm}， 试设计一个算法将它们合并到顺序表lc中，且lc仍然有序，再输出 。

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
#include <bits/stdc++.h>
using  namespace std;
const int maxn = 1000 + 10;
typedef struct node
{
    int *arr;
    int length;
    int maxsize;
}sqlist;
void createsqlist(sqlist &l)
{
    l.arr = (int*)malloc(maxn * sizeof(int));
    l.length = 0;
    l.maxsize = maxn;
}
void insqlist(sqlist &l, int n)
{
    printf("请依次输入数字来创建顺序表:\n");
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &l.arr[i]);
    }
    l.length = n;
}
void outsqlist(sqlist l)
{
    int i;
    printf("顺序表的元素为:\n");
    for(int i = 0; i < l.length; i++)
        printf("%d ", l.arr[i]);
}
void swap(int &a, int &b)
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}
void merger(sqlist &l1, sqlist &l2, sqlist &l3)
{
    for(int i = 0; i < l1.length ; i++)
    {
        l3.arr[i] = l1.arr[i];
    }
    l3.length = l1.length;
    for(int i = 0; i < l2.length; i++)
    {
        l3.arr[i + l1.length] = l2.arr[i];
    }
    l3.length += l2.length;
}
void sortsqlist(sqlist l)
{
    for(int i = 0; i < l.length ; i++)
    {
        for(int j = 0; j < l.length - 1; j++)
        {
            if(l.arr[j] > l.arr[j + 1])
            {
                //int temp = l.arr[j];
                //l.arr[j] = l.arr[j + 1];
                //l.arr[j + 1] = temp;
                swap(l.arr[j], l.arr[j + 1]);
            }
        }
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    sqlist  L1, L2, L3;
    printf("请输入n和m的值来创建两个顺序表:\n");
    scanf("%d %d", &n, &m);
    createsqlist(L1);
    createsqlist(L2);
    createsqlist(L3);
    insqlist(L1, n);
    insqlist(L2, m);
    merger(L1, L2, L3);
    sortsqlist(L3);
    outsqlist(L3);
    return  0;
}

7.设计一个算法，以先进先出的方式创建一个带头结点的单向链表，并输出 。

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 <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");
}
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);
    outlinklist(L);
    return 0;
}

8.设计一个算法，以后进先出的方式创建一个带头结点的单向链表，并输出 

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
#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;
    printf("请输入想要创建的链表元素:\n");
    for(int i = n; i > 0; i--)
    {
        Linklist  p;
        p = (Linklist)malloc(sizeof(Node));
        scanf("%d", &p->elem);
        p->next = l->next;
        l->next = 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;
    printf("请输入创建n个元素的链表的n值:\n");
    scanf("%d", &n);
    inlinklist(L, n);
    outlinklist(L);
    return 0;
}

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
#include <bits/stdc++.h>
using namespace std;
typedef struct Node
{
    int elem;
    struct  Node *prior;
    struct  Node *next;
}Node, *Linklist;
void inlinklist(Linklist &l, int n)
{
    Linklist  p, s;
    l = (Linklist)malloc(sizeof(Node));
    l ->next = NULL;
    l ->prior = NULL;
    s = l;
    p = (Linklist)malloc(sizeof(Node));
    printf("请输入想要创建的链表元素:\n");
    for(int i = 0; i < n; i++)
    {
        p = (Linklist) malloc(sizeof(Node));
        scanf("%d", &p->elem);
        s->next = p;
        p->prior = s;
        s = p;
    }
    s->next = NULL;
}
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;
    printf("请输入创建n个元素的链表的n值:\n");
    scanf("%d", &n);
    inlinklist(L, n);
    outlinklist(L);
    return 0;
}

10.设计一个算法，以后进先出的方式创建一个带头结点的双向链表，并输出 。

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;
typedef struct Node
{
    int elem;
    struct  Node *prior;
    struct  Node *next;
}Node, *Linklist;
void inlinklist(Linklist &l, int n)
{
    Linklist  p;
    l = (Linklist)malloc(sizeof(Node));
    l ->next = NULL;
    l ->prior = NULL;
    p = (Linklist)malloc(sizeof(Node));
    scanf("%d", &p->elem);
    p->next = l->next;
    l->next = p;
    printf("请输入想要创建的链表元素:\n");
    for(int i = 0; i < n; i++)
    {
        p = (Linklist) malloc(sizeof(Node));
        scanf("%d", &p->elem);
        p -> next = l -> next;
        l -> next -> prior = p;
        l -> next = p;
        p -> prior = l;
    }
}
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;
    printf("请输入创建n个元素的链表的n值:\n");
    scanf("%d", &n);
    inlinklist(L, n);
    outlinklist(L);
    return 0;
}

11.已知一个(head)单链表la，其中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
70
71
72
73
#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 swap(int &a, int &b)
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}
void sortlinklist(Linklist &l)
{
    Linklist p, s;//记录i 跟踪
    s = p = l->next;
    //p = l->next;
    //s = l->next;
    while(s)//表示前边的节点i
    {
        p = s;
        while(p)//表示后边的节点i + 1
        {
            if(s->elem > p->elem)
                swap(s->elem,p->elem);
            p = p->next;
        }
        s = s->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);
    sortlinklist(L);
    outlinklist(L);
    return 0;
}

12.已知二个单链表有序链表la与lb，其中la={a1,a2,…an}，lb={b1,b2,…bm}， 试设计一个算法将它们合并到单链表lc中，且lc仍然有序，再输出 。

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>
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 swap(Linklist &a, Linklist &s)
{
    s->next = a;
    s = a;
    a = a->next;
}
void mergerlinklist(Linklist &l1, Linklist &l2, Linklist &l3)
{
    Linklist p, q, s;
    p = l1->next;
    q = l2->next;
    l3 = s = l1;
    while(p != NULL && q != NULL)
    {
        if(p->elem < q->elem)
        {
            //s->next = p;
            //s = p;
            //p = p->next;
            swap(p,s);
        }
        else
        {
            //s->next = q;
            //s = q;
            //q = q->next;
            swap(q,s);
        }
    }
    s->next = p ? p : q;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    Linklist  L1, L2, L3;
    int  n, m;
    printf("请输入创建n个元素的链表的n值:\n");
    scanf("%d", &n);
    inlinklist(L1, n);
    printf("请输入创建m个元素的链表的m值:\n");
    scanf("%d", &m);
    inlinklist(L2, m);
    mergerlinklist(L1, L2, L3);
    outlinklist(L3);
    return 0;
}

13.设计一个算法实现在带头结点的单向链表中删除给定值的结点。（链表中的数据元素值均不相同）

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
#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 deletelinklist(Linklist &l, int x)
{
    Linklist p, s;
    //p = l;
    //s = l; 若没有 则无法删除链表第一个元素
    p = s = l;
    while(p->elem != x)
    {
        s = p;
        p = p->next;
    }
    if(p)
    {
        s->next = p->next;
        free(p);
    }
}
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("请输入要删除的值m:\n");
    scanf("%d", &m);
    deletelinklist(L, m);
    outlinklist(L);
    return 0;
}

14.试设计一个算法，将单链表中值最小的那个结点删除

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
#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 deletelinklist(Linklist &l)
{
    Linklist cur, curpre, min, minpre;
    //cur:要删除节点的前面一个（遍历作用） curpre: 要删除节点的前面一个的前驱
    //min:最小值的节点                   minpre:最小值的节点的前驱
    cur = min = curpre = minpre = l;
    while(cur != NULL)
    {
        if(cur->elem < min->elem)
        {
            minpre = curpre;
            min = cur;
        }
        curpre = cur;
        cur = cur->next;
    }
    minpre->next = min->next;
    free(min);
}
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);
    deletelinklist(L);
    outlinklist(L);
    return 0;
}

15.试设计一个算法，将单链表中值最大的那个结点删除

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
#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 deletelinklist(Linklist &l)
{
    Linklist cur, curpre, max, maxpre;
    //cur:要删除节点的前面一个（遍历作用） curpre: 要删除节点的前面一个的前驱
    //max:最大值的节点                   maxpre:最大值的节点的前驱
    cur = max = curpre = maxpre = l;
    max->elem = -1;
    while(cur != NULL)
    {
        if(cur -> elem > max -> elem)
        {
            maxpre = curpre;
            max = cur;
        }
        curpre = cur;
        cur = cur->next;
    }
    maxpre->next = max->next;
    free(max);
}
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);
    deletelinklist(L);
    outlinklist(L);
    return 0;
}

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
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
#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 insertlinklist(Linklist &l, int x)
{
    //1.如果链表序列是递增的
    Linklist p, s, q;
    s = l;
    p = s->next;
    while(p != NULL && p->elem < x)
    {
        s = p;
        p = p->next;
    }
    q = (Linklist)malloc(sizeof(Linklist));
    q->elem = x;
    q->next = p;
    s ->next = q;
    
    //2.如果链表序列是递减的
    Linklist p, s, q;
    s = l;
    p = s->next;
    while(p != NULL && p->elem > x)
    {
        s = p;
        p = p->next;
    }
    q = (Linklist)malloc(sizeof(Linklist));
    q->elem = x;
    q->next = p;
    s ->next = q;

}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    Linklist L;
    int n, x;
    printf("请输入创建n个元素的链表的n值:\n");
    scanf("%d", &n);
    inlinklist(L, n);
    printf("请输入要插入的数值x:\n");
    scanf("%d", &x);
    insertlinklist(L, x);
    outlinklist(L);
    return 0;
}