言成言成啊 | Kit Chen's Blog

考研专业课整理

发布于2020-09-27 21:40:51，更新于2020-12-10 15:18:16，标签：postgraduate data-structure c  文章会持续修订，转载请注明来源地址：https://meethigher.top/blog

一、C语言

1到100内的素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<stdio.h>
int main(){
    int flag=1;//用来判断是否是素数，
    for(int i=2;i<=100;i++){
        for(int j=2;j<i;j++){
            if(i%j==0) {
                flag=0;//如果不是负数，改成0
                break;
            }
        }
        if(flag==1){
            printf("%d ",i);
        }
        flag=1;
    }
    return 0;
}

分解质因数

99=3x3x11

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

/**
 * 短除法分解质因法
 * 思路：
 * 输入n，k=2（最小的素数）
 * 1.从k开始除，若能整除，就输出该数，并将n赋值为n/k
 * 2.若不能整除，则k++，重新执行1步
 * 输出n
 * @return
 */
int main() {
    int n;
    while (scanf("%d", &n)) {
        int k;
        for (k = 2; k < n; k++) {
            while (n != k) {
                if (n % k == 0) {
                    printf("%d*", k);
                    n = n / k;
                } else
                    break;
            }
        }
        printf("%d\n", n);
    }
    return 0;
}

一个数的约数

20的正约数有：1、2、4、5、10、20。

注意：一个数的约数必然包括1及其本身。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
int main()
{
    int n;
    while(scanf("%d",&n)){
        for(int i=1;i<n;i++){
            if(n%i==0){
                printf("%d、",i);
            }
        }
        printf("%d\n",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
#include <stdio.h>
#include <string.h>

int main() {
    int num = 0, upper = 0, lower = 0;
    char s[20];
    while (gets(s)) {
        for (int i = 0; i < strlen(s); i++) {
            if (s[i] >= 'a' && s[i] <= 'z') {
                lower++;
            }
            if (s[i] >= 'A' && s[i] <= 'Z') {
                upper++;
            }
            if (s[i] >= '0' && s[i] <= '9') {
                num++;
            }
        }
        printf("数字=%d,大写字母=%d,小写字母=%d\n", num, upper, lower);
    }
    return 0;
}

统计正整数出现的次数

例如

输入1,2,2,3,3,3,5,5,5,6

输出0:0次 1:1次 2:2次 3:3次 4:0次 5:3次 6:1次 7:0次 8:0次 9:0次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>

int main() {
    int a[10] = {
            1, 2, 2, 3, 3, 3, 5, 5, 5, 6
    };
    int b[10] = {0};
    for (int i = 0; i < 10; i++) {
        b[a[i]]++;
    }
    for (int i = 0; i < 10; i++) {
        printf("%d:%d次 ", i, b[i]);
    }
    return 0;
}

分解一个n位数

输入333

输出 300 30 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <math.h>

int main() {
    int n, i = 0;
    int b[10] = {
            0
    };
    scanf("%d", &n);
    while (n != 0) {
        b[i] = n % 10;
        n /= 10;
        i++;
    }
    for (int j = 0; j < i; j++) {
        printf("%d ", b[j] * (int) pow(10, i - j - 1));
    }
    return 0;
}

俩数的最大公约数和最小公倍数

最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。

互质数为数学中的一种概念，即两个或多个整数的公因数只有1的非零自然数。公因数只有1的两个非零自然数，叫做互质数。

约数，又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。

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

/**
 * 最大公约数
 * Greatest Common Divisor
 * @param a
 * @param b
 * @return
 */
int GCD(int a, int b) {
    int temp;
    if (a < b) {
        temp = a;
        a = b;
        b = temp;
    }
    while (temp != 0) {
        temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

/**
 * 最小公倍数
 * Least Common Multiple
 * @param a
 * @param b
 * @return
 */
int LCM(int a, int b) {
    for (int i = a; i > 0; i++) {
        if (i % a == 0 && i % b == 0) {
            return i;
        }
    }
}

int main() {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("最大公约数：%d", GCD(a, b));
    printf("最小公倍数：%d", LCM(a, b));
    return 0;
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
int main(){
    int a[10]={
            1,9,8,7,6,5,4,3,2,10
    };
    int temp;
    for(int i=0;i<10-1;i++){
        for(int j=0;j<10-i-1;j++){
            if(a[j]>a[j+1]){
                temp=a[j+1];
                a[j+1]=a[j];
                a[j]=temp;
            }
        }
    }
    for(int i=0;i<10;i++){
        printf("%d ",a[i]);
    }
    return 0;
}

已排好序的数组插入一个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>

int main() {
    int a[11] = {
            1, 2, 3, 3, 5, 6, 7, 8, 9, 10
    };
    int temp;
    scanf("%d", &temp);
    for (int i = 9; i >= 0; i--) {
        if (temp < a[i]) {
            a[i + 1] = a[i];
        } else {
            a[i + 1] = temp;
            break;
        }
    }
    for (int i = 0; i < 11; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

数组奇偶数分类

设计一个C语言函数，将整数数组a[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
#include<stdio.h>

void divide(int a[], int n) {
    int i = 0, j = n - 1, temp;
    while (i < j) {
        //若是奇数，则自增
        //若不是奇数，则执行下步的交换
        while (a[i] % 2 != 0) {
            i++;
        }
        //若是偶数，则自减
        //若不是偶数，则执行下步的交换
        while (a[j] % 2 != 1) {
            j--;
        }
        //这是保证左边是奇数，右边偶数
        if (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    //为了帮助理解
    printf("结束的i=%d,j=%d\n", i, j);
    for (int k = 0; k < n; k++) {
        printf("%d ", a[k]);
    }
}

int main() {
    int a[10] = {
            1, 9, 1, 2, 9, 7, 5, 1, 9, 3
    };
    divide(a, 10);
    return 0;
}

数组逆序

矩阵逆序

设给定一个m行n列整型矩阵A，编写一个函数swap，使得它对A的元素进行交换，具体如下：第一个元素和倒数第一个元素交换，第二个元素和倒数第二个元素交换，在具体实现时，不允许另设矩阵。

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 <stdio.h>

#define m 3
#define n 4

void swap(int a[m][n]) {
    int i, j, temp;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
    printf("================\n");

    //关键代码
    for (i = 0; i < m / 2; i++) {
        for (j = 0; j < n; j++) {
            temp = a[i][j];
            a[i][j] = a[m - i - 1][n - j - 1];
            a[m - i - 1][n - j - 1] = temp;
        }
    }
    //如果不是奇数行的话，截止到上面部分的代码，就能完美实现该功能了。
    //比如，是3行的话，3/2=1,那么数组就会在区间[0,1)取值，如果将区间改成闭区间，那么偶数行又会出问题，相当于换了一遍，又再换回去了。
    //所以如果是奇数行的话，需要再加逻辑单独处理
    if (m % 2 != 0) {
        i = m / 2;
        for (j = 0; j <= n / 2; j++) {
            temp = a[i][j];
            a[i][j] = a[m - i - 1][n - j - 1];
            a[m - i - 1][n - j - 1] = temp;
        }
    }

    //输出结果
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int a[m][n] = {
            0, 1, 2, 3,
            10, 11, 12, 13,
            20, 21, 22, 23
    };
    swap(a);
    return 0;
}

向量逆序

已知在一维数组A[M+N]中，依次存放着两个向量{1,3,5,7,9}跟{2,4}，现要求将向量逆序，变成{2,4}和{1,3,5,7,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
#include <stdio.h>

#define M 5
#define N 2

void reverse(int a[], int n) {
    int i, temp;
    for (i = 0; i < n / 2; i++) {
        temp = a[i];
        a[i] = a[n - 1 - i];
        a[n - 1 - i] = temp;
    }
}

int main() {
    int i;
    int a[M + N] = {
            1, 3, 5, 7, 9, 2, 4
    };
    //将整个数组进行逆序
    reverse(a, M + N);
    //将前部分数组进行正序
    reverse(a, N);
    //将后部分数组进行正序
    reverse(a + N, M);
    
    //输出验证结果
    for (i = 0; i < M + N; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

奇偶数分类并排序

有100个正整数存放在数组中，试编一函数，要求：

  1. 所有的奇数按从小到大的顺序存放在数组的前半部
  2. 所有的偶数按从小到大的顺序存放在数组的后半部

例如：1,4,3,2,5,9,7

输出：1,3,5,7,9,2,4

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>

#define N 7

/**
 * 对数组进行排序
 * @param a
 * @param n
 */
void inOrder(int a[], int n) {
    int temp;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}

/**
 * 对数组进行分类
 * 奇数放到左边，偶数放到左边
 * @param a
 * @param n
 */
void sort(int a[], int n) {
    int i = 0, j = n - 1;
    int temp;
    while (i < j) {
        //如果是奇数，则后移
        while (a[i] % 2 != 0) {
            i++;
        }
        //如果是偶数，则前移
        while (a[j] % 2 == 0) {
            j--;
        }
        //奇偶数互换
        if (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    inOrder(a, i);
    inOrder(a + i, n - i);
}


int main() {
    int a[N] = {
            1, 4, 3, 2, 5, 9, 7
    };
    sort(a, N);
    for (int i = 0; i < N; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

数组排序

设给定数组变量A和B，它们的值满足条件：

A[i]<=A[i+1]，B[j]<=B[j+1]，其中i=0,1,…,m，j=0,1,…,n

试写一个程序，将A和B合并成一个有序数组C，使得C[k]<=C[k+1]，k=0,1,…,m+n

这个题最笨的方法，就是将元素，一股脑存储到c中，然后再对C进行冒泡排序。

此处，用另一个思路。

  1. 将a、b两个数组之间从下标0开始，进行比较，更小的就放到c数组中
  2. 将a或者b中剩余的数，依次存放到c中
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<stdio.h>

#define m 5
#define n 6

void sort(int a[], int b[], int c[]) {
    int i = 0, j = 0, k = 0;
    while (i < m && j < n) {
        if (a[i] < b[j]) {
            c[k] = a[i];
            i++;
        } else {
            c[k] = b[j];
            j++;
        }
        k++;
    }
    if (i == m) {
        for (int d = m; d < n; d++, k++) {
            c[k] = b[d];
        }
    }
    if (i == n) {
        for (int d = n; d < m; d++, k++) {
            c[k] = a[d];
        }
    }

    for (i = 0; i < m + n; i++) {
        printf("%d ", c[i]);
    }

}

int main() {
    int a[m] = {
            2, 4, 6, 8, 10
    };
    int b[n] = {
            1, 3, 5, 7, 9, 11
    };
    int c[m + n];
    sort(a, b, c);
    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
#include<stdio.h>

#define N 10

int main() {
    int a[N] = {
            20, 19, 18, 17, 16, 15, 14, 13, 12, 11
    };
    int i, num, low = 0, high = N - 1, mid;
    scanf("%d", &num);
    while (low <= high) {
        mid = (low + high) / 2;
        if (a[mid] == num) {
            break;
        } else if (a[mid] > num) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    if (low > high) {
        printf("查找失败\n");
    } else {
        printf("%d的下标为%d\n", a[mid], mid);
    }
    return 0;
}

平台问题

设给定N个元素的一维整型数组变量A，若有下面条件：

  • A[i-1]!=A[i]
  • A[i]=A[i+1]=…=A[k]
  • A[k]!=A[k+1]

则称A[i],A[i+1]…A[k]为饱和平台，并定义其长度为k+1-i。

写一个函数，使得它对任给的数组变量A求出最长平台的长度。

例如，假如有序列（3,3,2,2,4,4,4），则（3,3）和（2,2）以及（4,4,4）都是饱和平台，并且最长的平台的长度是3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>

int getLen(int a[], int n) {
    int max = 0, mark = 1;
    for (int i = 0; i < n; i++) {
        if (a[i] == a[i + 1]) {
            mark++;
        } else {
            mark = 1;
        }
        if (mark > max)
            max = mark;
    }
    return max;
}

int main() {
    int a[] = {
            2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4
    };
    printf("最长平台的长度：%d\n", getLen(a, sizeof(a) / sizeof(a[0])));

    return 0;
}

特殊值

设有N个非负数，存放于一维数组中，要求将其中的0移动到后面，非0的数保持原有次序。

例如，当 N=7 时，原有序列 7,0,0,3,0,5,0 移动后称为 7,3,5,0,0,0,0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>
void sort(int a[],int n){
    int temp;
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-i-1;j++){
            if(a[j]==0){
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
    for(int i=0;i<n;i++){
        printf("%d ",a[i]);
    }
}
int main(){
    int a[]={
            7,0,0,3,0,5,0
    };
    sort(a, sizeof(a)/ sizeof(a[0]));
    return 0;
}

最垃圾的思想，冒泡。虽然能做出来，但是效率很低

换个思想

  1. 找到第一个0元素
  2. 从当前位置找第一个非0元素
  3. 两个元素互换，找不到就结束

循环执行

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

void sort(int a[], int n) {
    int temp;
    for (int i = 0; i < n; i++) {
        if (a[i] == 0) {
            for (int j = i; j < n; j++) {
                if (a[j] != 0) {
                    temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                    break;
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
}

int main() {
    int a[] = {
            7, 0, 0, 3, 0, 5, 0
    };
    sort(a, sizeof(a) / sizeof(a[0]));
    return 0;
}

编写一个函数，从给定的向量A中删除元素值在x到y（x<=y）之间的所有元素（向量要求各元素之间不能有间断）。

函数原型为：int del(int A,int n,int x,int y)。

其中，参数n为输入向量的维数，返回值为删除元素后的维数。

1
2
3
4
5
6
int del(int a[],int n,int x,int y){
    for(int i=x,j=y+1;i<x+(n-y)-1;i++,j++){
        a[i]=a[j];
    }
    return n-(y-x)-1;
}

一开始理解成删除元素下标为x-y的值了

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

int del(int a[], int n, int x, int y) {
    int i = 0, k = 0;
    while (i < n) {
        if (a[i] >= x && a[i] <= y) {
            k++;
        } else {
            a[i - k] = a[i];
        }
        i++;
    }
    return n - k;
}

int main() {
    int a[] = {
            1, 2, 3, 4, 5, 6, 7, 8, 9, 10
    };
    int n = del(a, sizeof(a) / sizeof(a[0]), 3, 5);
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

编写函数，把整数数组中值相同的元素删除得只剩一个，并把剩余元素全部移动到前面。

1
2


二、数据结构

七桥问题（判断欧拉回路）

技巧：

  1. 图形必须是连通的
  2. 图中的奇点个数是0或者2
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
#include <stdio.h>
int EulerCircuit(int mat[4][4],int n);
int main(){
    int mat[4][4]={
            {0,1,2,2},{1,0,1,1},{2,1,0,0},{2,1,0,0}
    };
    int num=EulerCircuit(mat,4);
    if(num>2)
        printf("有%d个地方通奇数桥，不存在欧拉回路\n",num);
    else
        printf("存在欧拉回路\n");
    return 0;
}
int EulerCircuit(int mat[4][4],int n){
    int i,j,degree,count=0;
    for(i=0;i<n;i++){
        degree=0;
        for(j=0;j<n;j++){
            degree=degree+mat[i][j];
        }
        if(degree%2!=0)
            count++;//如果是奇数，就进行自增
    }
    return count;
}

百钱白鸡

已知公鸡5元一只，母鸡3元一只，小鸡1元一只，花100块钱买100只鸡，问公鸡、母鸡、小鸡各多少只？

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<stdio.h>

int main() {
    int rooster, hen;
    for (rooster = 0; rooster <= 20; rooster++) {
        for (hen = 0; hen <= 33; hen++) {
            if ((100 - rooster - hen) % 3 == 0 && (rooster * 5 + hen * 3 + (100 - rooster - hen) / 3 == 100)) {
                printf("公鸡%d只，母鸡%d只，小鸡%d只\n", rooster, hen, 100 - rooster - hen);
            }
        }
    }
    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
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
#include <stdio.h>
/*
 * 顺序表的存储结构定义
 */
#define MaxSize 10
typedef int DataType;

// 这是省略结构体名的写法
typedef struct {
    DataType data[MaxSize];
    int length;
} SeqList;

/**
 * 初始化顺序表
 * @param L 顺序表
 */
void InitList(SeqList *L) {
    L->length = 0;
}

/**
 * 创建顺序表
 * @param L 顺序表
 * @param a 数据元素
 * @param n 顺序表的长度
 * @return 建立顺序表是否成功，非0为真
 */
int CreateList(SeqList *L, DataType a[], int n) {
    if (n > MaxSize) {
        printf("顺序表的空间不够，无法建立顺序表\n");
        return 0;
    }
    for (int i = 0; i < n; i++)
        L->data[i] = a[i];
    L->length = n;
    return 1;
}

/*
 * 销毁顺序表，顺序表时静态存储分配，在顺序表变量退出作用域时，自动释放该变量所占内存单元
 * 故，顺序表无需销毁
 */

/**
 * 判空操作
 * @param L 顺序表
 * @return 是否为空，非0为真
 */
int Empty(SeqList *L) {
    if (L->length == 0)
        return 1;
    else
        return 0;
}

/**
 * 求顺序表的长度
 * @param L 顺序表
 * @return 顺序表的长度
 */
int Length(SeqList *L) {
    return L->length;
}

/**
 * 遍历操作，输出值
 * @param L 顺序表
 */
void PrintList(SeqList *L) {
    for (int i = 0; i < L->length; i++)
        printf("%d ", L->data[i]);

}

/**
 * 按值查找
 * 平均时间性能为 O(n)
 * @param L 顺序表
 * @param x 需要查找的值
 * @return 返回位置，非0为真
 */
int Locate(SeqList *L, DataType x) {
    for (int i = 0; i < L->length; i++)
        if (L->data[i] == x)
            return i + 1;//自然序号要加一
    return 0;
}

/**
 * 按位查找
 * 时间复杂度 O(1)
 * @param L 顺序表
 * @param i 元素的自然顺序
 * @param p 指针参数，将查到的数据值放到该地址
 * @return 返回结果
 */
int Get(SeqList *L, int i, DataType *p) {
    if (i < 1 || i > L->length) {
        printf("查找位置非法，查找失败\n");
        return 0;
    } else {
        *p = L->data[i - 1];
        return 1;
    }
}

/**
 * 插入操作
 * @param L 顺序表
 * @param i 插入位置，自然顺序
 * @param x 插入的元素值
 * @return 是否成功，非0为真
 */
int Insert(SeqList *L, int i, DataType x) {
    if (L->length >= MaxSize) {
        printf("上溢错误，插入失败\n");
        return 0;
    }
    if (i < 1 || i > L->length + 1) {
        printf("位置错误，插入失败\n");
        return 0;
    }
    for (int j = L->length; j >= i; j--) {
        L->data[j] = L->data[j - 1];
    }
    L->data[i - 1] = x;
    L->length++;
    return 1;
}

/**
 * 删除操作
 * @param L 顺序表
 * @param i 位置，自然顺序
 * @param p 用来存储被删除元素的值
 * @return 是否成功，非0为真
 */
int Delete(SeqList *L, int i, DataType *p) {
    if (L->length == 0) {
        printf("下溢错误，删除失败\n");
        return 0;
    }
    if (i < 1 || i > L->length) {//注意插入跟删除这个地方的异同
        printf("位置错误，删除失败\n");
        return 0;
    }
    *p = L->data[i - 1];
    for (int j = i; j < L->length; j++) {
        L->data[j - 1] = L->data[j];
    }
    L->length--;
    return 1;
}

/**
 * 演示
 * @return 0
 */
int main() {
    SeqList L;
    int i, x, r[5] = {
            1, 2, 3, 4, 5
    };
    CreateList(&L, r, 5);
    printf("当前线性表的数据：\n");
    PrintList(&L);
    Insert(&L, 1, 99);
    printf("\n插入后的数据：\n");
    PrintList(&L);
    printf("\n当前线性表的长度：%d\n", Length(&L));
    printf("\n请输入查找元素的值：\n");
    scanf("%d", &x);
    i = Locate(&L, x);
    if (0 == i)
        printf("\n查找失败\n");
    else
        printf("\n元素%d的位置是：%d\n", x, i);
    if (1 == Get(&L, i, &x))
        printf("\n第%d个元素的值是%d\n", i, x);
    else
        printf("\n没有第%d个元素\n", i);
    printf("\n请输入要删除第几个元素\n");
    scanf("%d", &i);
    if (1 == Delete(&L, i, &x)) {
        printf("\n删除第%d个元素的值是%d,删除后数据\n", i, x);
        PrintList(&L);
    } else
        printf("\n删除操作失败\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
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
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
/**
 * 单链表的结点结构定义
 */
typedef struct Node{
    DataType data;
    struct Node *next;
} Node;
/**
 * 单链表的初始化
 * @return 单链表
 */
Node *InitList(){
    Node *first=(Node *)malloc(sizeof(Node));
    first->next=NULL;
    return first;
}
/**
 * 判空操作
 * @param 单链表
 * @return 是否为空，非0为真
 */
int Empty(Node *first){
    if(first->next=NULL)
        return 1;
    else
        return 0;
}
/**
 * 遍历单链表
 * @param first
 */
void PrintList(Node *first){
    Node *p=first->next;
    while(p!=NULL){
        printf("%d ",p->data);
        p=p->next;
    }
}
/**
 * 求链表长度
 * @param first
 * @return
 */
int Length(Node *first){
    Node *p=first->next;
    int count=0;
    while(p!=NULL){
        p=p->next;
        count++;
    }
    return count;
}
/**
 * 按值查找
 * @param first
 * @param x
 * @return 返回位置，0表示未找到
 */
int Locate(Node *first,DataType x){
    Node *p=first->next;
    int count=1;
    while(p!=NULL){
        if(p->data==x)
            return count;
        p=p->next;
        count++;
    }
    return 0;
}
/**
 * 按位查找
 * @param first
 * @param i
 * @param ptr
 * @return
 */
int Get(Node *first,int i,DataType *ptr){
    Node *p=first->next;
    int count=1;
    while(p!=NULL&&count<i){
        p=p->next;
        count++;
    }
    if(p==NULL){
        printf("位置错误，查找失败\n");
        return 0;
    }else{
        *ptr=p->data;
        return 1;
    }
}
/**
 * 插入操作
 * @param first
 * @param i
 * @param x
 * @return 返回 0 或 1
 */
int Insert(Node *first,int i,DataType x){
    Node *s=NULL,*p=first;
    int count=0;
    while(p!=NULL&&count<i-1){
        p=p->next;
        count++;
    }
    if(p==NULL){
        printf("位置错误，插入失败\n");
        return 0;
    }
    else{
        s=(Node *)malloc(sizeof(Node));
        s->data=x;
        s->next=p->next;
        p->next=s;
        return 1;
    }
}
/**
 * 头插法
 * @param a
 * @param n
 * @return
 */
Node *CreateList1(DataType a[],int n){
    Node *s=NULL;
    Node *first=(Node *)malloc(sizeof(Node));
    first->next=NULL;
    for(int i=0;i<n;i++){
        s=(Node *)malloc(sizeof(Node));
        s->data=a[i];
        s->next=first->next;
        first->next=s;
    }
    return first;
}
/**
 * 尾插法
 * @param a
 * @param n
 * @return
 */
Node *CreateList2(DataType a[],int n){
    Node *s=NULL,*r=NULL;
    Node *first=(Node *)malloc(sizeof(Node));
    r=first;
    for(int i=0;i<n;i++){
        s=(Node *)malloc(sizeof(Node));
        s->data=a[i];
        r->next=s;
        r=s;
    }
    r->next=NULL;
    return first;
}
/**
 * 删除操作
 * @param first
 * @param i
 * @param ptr
 * @return 返回值 1 或 0
 */
int Delete(Node *first,int i,DataType *ptr){
    Node *p=first,*q=NULL;
    int count=0;
    DataType x;
    while(p!=NULL&&count<i-1){
        p=p->next;
        count++;
    }
    if(p==NULL||p->next==NULL){
        printf("位置错误，删除失败\n");
        return 0;
    }else{
        q=p->next;
        *ptr=q->data;
        p->next=q->next;
        free(q);
        return 1;
    }
}
/**
 * 销毁单链表
 * @param first
 */
void DestroyList(Node *first){
    Node *p=first;
    while(first!=NULL){
        first=first->next;
        free(p);
        p=first;
    }
}
/**
 * 演示
 */
 int main(){
     int r[5]={
             1,2,3,4,5
     },i,x;
     Node *first=NULL;
     first=CreateList1(r,5);
     printf("当前线性表的数据为：");
     PrintList(first);
     Insert(first,2,8);
     printf("执行插入操作后的数据为：");
     PrintList(first);
     printf("当前单链表的长度为：%d\n",Length(first));
     printf("请输入要查找的元素值：");
     scanf("%d",&x);
     i=Locate(first,x);
     if(0!=i)
         printf("元素%d的元素位置为：%d\n",x,i);
     else
         printf("单链表中没有元素%d\n",x);
     printf("请输入要删除第几个元素：");
     scanf("%d",&i);
     if(Delete(first,i,&x)==1){
         printf("删除的元素值是%d，执行删除操作后数据为：",x);
         PrintList(first);
     } else
         printf("删除操作失败\n");
     DestroyList(first);
     return 0;
 }
发布：2020-09-27 21:40:51
修改：2020-12-10 15:18:16
链接：https://meethigher.top/blog/2020/c-algorithm/
标签：postgraduate data-structure c 
付款码 打赏 分享
访客数calculating人
Shift+Ctrl+1 可控制工具栏