C语言数据结构学习

前言

高中打NOIP时，这部分是让我最头疼的地方，怎么也学不会。看着老师在上面写代码，我只能感到深深的迷茫，后来才发现原来是因为跳过了数据结构的基础直接开始编程。现在就来完成一下三年前留下的遗憾

数组

基础知识

定义与特点

数组是物理意义上连续的一组数据，创建时确定容量，之后就不能改变。因此要对数组存放的数据进行约束防止溢出。数组通过索引进行查找，复杂度O(1)，插入和删除需要移动后续数据，复杂度O(n)

初始化

a是数组名称，5是大小

1

int a[5]={1,2,3,4,5};

b是二维数组，可以理解成一个100*100矩阵

1

int b[100][100];

数组元素的访问与修改

数组括号中的数字就是索引，直接访问到的就是值
索引从0开始
如果不加索引会报错

1
2


n=a[1];
m=b[10][10];

在数组中插入元素

复杂度O(n)

1
2
3
4
5


int n=5,a[10];
for(int i=9;i>n;i--){
	a[i]=a[i-1];
}
a[n]=n;

在数组中删除元素

复杂度O(n)

1
2
3
4


int n=5,a[10];
for(int i=n;i<9;i++){
	a[i]=a[i+1];
}

数组的查找

复杂度O(n)

1
2
3
4
5
6


int data=10,a[10];
int i=0;
while(i<10&&a[i]!=data){
	i++;
}
printf("%d\n",a[i])

数组的反转

复杂度O(n)

1
2
3
4
5
6


int a[10],n=9;
for(int i=0;i<10/2;i++){
	int x=a[i];
	a[i]=a[n-i];
	a[n-i]=x;
}

题目练习

P3156 【深基15.例1】询问学号

基础的数组应用题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


#include <stdio.h>
#include <stdlib.h>

int m,n,s;
int a[1000000001];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<m;i++){
        scanf("%d",&s);
        printf("%d\n",a[s]);
    }
    return 0;
}

P3613 【深基15.例2】寄包柜

高中就经常被内存空间困扰，这次抱着侥幸心理定义了一个二维数组int a[100001][100001];，结果果然炸了

链表

知识理解

定义与特点

链表也就是靠链连接起来的一些节点，所谓的链就是指针。每一个节点里面存放着指针和数据，指针指向它的下一个节点，这种特性让链表在物理上可以不连续。如果直接引用这个节点的名字，得到的是地址而不是数据。单链表只有一个指针，双链表有两个

初始化链表

struct link*next;就是定义next指针
这里是创建一个结构体，一个结构体中可以有多个相同结构的链表

1
2
3
4


typedef struct link{
	int data;
	struct link*next;
}link;

初始化头节点

link*head=(link*)malloc(sizeof(link));意思是：在堆上新开辟一个 link 结构体节点，并用指针 head 指向它
等号前的指针指向等号后的节点，不能调转方向

1
2


link*head=(link*)malloc(sizeof(link));
head->next=NULL;

在头节点后新增节点

节点的连接需要先接后面再接前面，否则会导致断链

1
2
3
4


link*new=(link*)malloc(sizeof(link));
new->next=head->next;
head->next=new;
new->data=1;

在链表尾部新增节点

如果知道链表1尾部地址，复杂度O(1)，否则这里就需要对链表进行遍历，复杂度O(n)

1
2
3
4
5
6
7
8


link*s=head->next;
while(s->next!=NULL){
	s=s->next;
}
link*new=(link*)malloc(sizeof(link));
new->next=NULL;
s->next=new;
new->data=1;

在链表中某个位置插入节点

知道位置的地址，复杂度是O(1)，不知道的话复杂度O(n)

1
2
3
4
5
6
7
8
9


int n=10,data=1;
link*s=head->next;
while(s!=NULL&&s->data!=n){
	s=s->next;
}
link*new=(link*)malloc(sizeof(link));
new->next=s->next;
new->data=data;
s->next=new;

在链表中某个位置删除节点

复杂度同上，free(p);就是释放节点内存，p相当于存储需要删除节点的地址

1
2
3
4
5
6
7
8


int n=10;
link*s=head->next;
while(s->next!=NULL&&s->next->data!=n){
	s=s->next;
}
link*p=s->next;
s->next=p->next;
free(p);

链表的倒置

复杂度O(n)
核心原理是三个指针分别存储主节点、倒置前主节点的下一个节点、倒置后主节点的下一个节点，然后修改next指针指向

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


link*i=head->next;
link*j=NULL;
link*k=NULL;
while(i!=NULL){
	k=i->next;
	i->next=j;
	j=i;
	i=k;
}
head->next=j;

释放内存

程序运行结束以后需要手动释放链表占用的内存，否则内存会被一直占用，同时不能直接释放前序节点，这会让后面的部分变成野指针，继续占用内存但无法访问，这里为了调用方便一般是写一个封装

1
2
3
4
5
6
7
8
9


void freel(link*fr){
	link*head=fr;
	link*next;
	while(head!=NULL){
		next=head->next;
		free(head);
		head=next;
	}
}

题目练习

链表通讯录

我的逻辑就是通过不同输入对应不同的操作，从而对链表进行增删改等操作，整体不难，属于熟悉语法的题目

  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


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct student{
        char name[20];
        char number[20];
        struct student*next;
    }student;
int main()
{
    student*head=(student*)malloc(sizeof(student));
    head->next=NULL;
    student* prev=head;

    while(1){
        char search;
        scanf(" %c",&search);
        if(search=='a'){
            prev = head;
            while(prev->next != NULL) {
                prev = prev->next;
            }
            printf("输入姓名电话：");
            student*nw=(student*)malloc(sizeof(student));
            nw->next=NULL;
            scanf("%19s",nw->name);
            scanf("%19s",nw->number);
            prev->next=nw;
            prev=nw;
            printf("添加成功");
            printf("\n");
        }
        else if(search=='d'){
            printf("输入需要删除的姓名或电话：");
            char a[20];
            int found=0;
            scanf("%19s",a);
            student*i=head;
            while(i->next!=NULL){
                if(strcmp(i->next->name, a) == 0){
                    student*p=i->next;
                    i->next=p->next;
                    found=1;
                    free(p);
                    break;
                }
                else if(strcmp(i->next->number, a) == 0){
                    student*p=i->next;
                    i->next=p->next;
                    found=1;
                    free(p);
                    break;
                }
                else{
                    i=i->next;
                }
            }
            if(!found) printf("无此信息");
            else printf("删除成功");
            printf("\n");
        }
        else if(search=='c'){
            printf("输入需要更改和更改后的信息：");
            char b[20],c[20];
            int found=0;
            scanf("%19s %19s",b,c);
            student* j=head;
            while(j->next!=NULL){
                if(strcmp(j->next->name, b) == 0){
                    strcpy(j->next->name, c);
                    found=1;
                    break;
                }
                else if(strcmp(j->next->number, b) == 0){
                    strcpy(j->next->number, c);
                    found=1;
                    break;
                }
                else{
                    j=j->next;
                }
            }
            if(!found) printf("无此信息");
            else printf("更改成功");
            printf("\n");
        }
        else if(search=='f'){
            printf("输入查找的信息：");
            char d[20];
            int found=0;
            scanf("%19s",d);
            student*k=head;
            while(k->next!=NULL){
                if(strcmp(k->next->name, d) == 0){
                    printf("号码：%19s ",k->next->number);
                    found=1;
                    break;
                }
                else if(strcmp(k->next->number, d) == 0){
                    printf("姓名：%19s ",k->next->name);
                    found=1;
                    break;
                }
                else{
                    k=k->next;
                }
            }
            if(!found) printf("无此信息");
            printf("\n");
        }
        else if(search=='i'){
            student*l=head;
            printf("通讯录信息:\n");
            while(l->next!=NULL){
            printf("姓名：%19s ",l->next->name);
            printf("电话：%19s\n",l->next->number);
            l=l->next;
            }
            printf("\n");
        }
        else if(search=='q'){
            break;
        }
    }
    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


#include <stdio.h>
#include <stdlib.h>

typedef struct p{
        int a;
        int b;
        struct p*next;
    }p;

typedef struct q{
        int a;
        int b;
        struct q*next;
    }q;

char c1[10001];
char c2[10001];

int main()
{
    p*head=(p*)malloc(sizeof(p));
    head->next=NULL;
    p*prev=head;

    q*head=(q*)malloc(sizeof(q));
    head->next=NULL;
    q*prev=head;

    scanf("%10000s",c1);
    scanf("%10000s",c2);

最开始逻辑是找到x,然后从x向左右遍历来找到两个系数，但这样很难处理没有x和各种边界情况，就改成了取运算符号分隔的式子进行存储，然后分离其中的系数

点击查看错误代码

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

typedef struct node{
        int a;
        int b;
        struct node*next;
    }node;

char c1[10001];
char c2[10001];

int main()
{
    node*p=(node*)malloc(sizeof(node));
    p->next=NULL;
    node*pn=p;

    node*q=(node*)malloc(sizeof(node));
    q->next=NULL;
    node*qn=q;

    scanf("%10000s",c1);
    scanf("%10000s",c2);

    int i=0;
    while(c1[i]!='\0'){
        while(c1[i]!='x'&&c1[i]!='0'){
            i++;
        }
        if(c1[i]=='\0') break;

        int n=1,m=2,a=0,b=0,c=1;
        while(c1[i-n]>='0'&&c1[i-n]<='\9'){
            a+=(c1[i-n]-'0')*c;
            c*=10;
            n++;
        }
        if(n==1) a=1;
        if(c1[i-n]=='-') a*=-1;
        while(c1[i+m]>='0'&&c1[i+m]<='9'){
            b=b*10+(c1[i+m]-'0');
            m++;
        }
        if(m==2) b=1;
        node*new=(node*)malloc(sizeof(node));
        new->next=pn->next;
        new->a=a;
        new->b=b;
        pn->next=new;
        pn=new;
    }
    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


#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct node{
        int a;
        int b;
        struct node*next;
    }node;

char c1[10001];
char c2[10001];

node*add_char_to_node(char cc[10001],node*nn){
    int i=0;
    while(cc[i]!='\0'){
        int x=1;
        if(cc[i]=='-'){
            x=-1;
            i++;
        }else if(cc[i]=='+'){
            x=1;
            i++;
        }
        char c[1000];
        int j=0;
        while(cc[i]!='+'&&cc[i]!='-'&&cc[i]!='\0'){
            c[j]=cc[i];
            j++;
            i++;
        }
        c[j]='\0';
        
        int k=0,a=0,b=0,r=0;
        while(c[k]!='x'&&c[k]!='\0'){
            a=a*10+(c[k]-'0');
            k++;
            r=1;
        }
        if(c[k]=='x'&&r==0) a=1;
        a*=x;
        if(c[k]=='x'){
            k++;
            while(c[k]!='\0'){
                b=b*10+(c[k]-'0');
                k++;
            }
        }

        node*new=(node*)malloc(sizeof(node));
        new->next=NULL;
        new->a=a;
        new->b=b;
        nn->next=new;
        nn=new;
    }
    return nn;
}

void freee(node*fr){
    node*head=fr;
    node*next;
    while(head!=NULL){
        next=head->next;
        free(head);
        head=next;
    }
}

int main()
{
    node*p=(node*)malloc(sizeof(node));
    p->next=NULL;
    node*pn=p;

    node*q=(node*)malloc(sizeof(node));
    q->next=NULL;
    node*qn=q;

    scanf("%10000s",c1);
    scanf("%10000s",c2);

    pn=add_char_to_node(c1,pn);
    qn=add_char_to_node(c2,qn);

    node*r=(node*)malloc(sizeof(node));
    r->next=NULL;
    node*rn=r;

    node*ps=p->next;
    node*qs=q->next;
    while(ps!=NULL&&qs!=NULL){
        if(ps->b==qs->b){
            int aa=ps->a+qs->a;
            if(aa!=0){
                node*new=(node*)malloc(sizeof(node));
                new->next=NULL;
                new->a=ps->a+qs->a;
                new->b=ps->b;
                rn->next=new;
                rn=new;
            }
            ps=ps->next;
            qs=qs->next;
        }else if(ps->b>qs->b){
            node*new=(node*)malloc(sizeof(node));
            new->next=NULL;
            new->a=ps->a;
            new->b=ps->b;
            rn->next=new;
            rn=new;

            ps=ps->next;
        }else if(ps->b<qs->b){
            node*new=(node*)malloc(sizeof(node));
            new->next=NULL;
            new->a=qs->a;
            new->b=qs->b;
            rn->next=new;
            rn=new;

            qs=qs->next;
        }
    }
    if(ps!=NULL) rn->next=ps;
    else if(qs!=NULL) rn->next=qs;

    node*print=r->next;
    while(print!=NULL){
        if(print->a>0&&print!=r->next) printf("+");
        if(print->b==0) printf("%d",print->a);
        else printf("%dx%d",print->a,print->b);
        print=print->next;
    }
    printf("\n");

    freee(p);
    freee(q);
    freee(r);

    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


    node*ps=p->next;
    node*qs=q->next;
    while(ps!=NULL){
        qs=q->next;
        while(qs!=NULL){
            int aa=ps->a*qs->a;
            int bb=ps->b+qs->b;
            int e=0;
            node*s=r->next;
            while(s!=NULL){
                if(s->b==bb){
                    s->a+=aa;
                    e=1;
                    break;
                }
                s=s->next;
            }
            if(e==0){
                node*new=(node*)malloc(sizeof(node));
                new->next=NULL;
                new->a=aa;
                new->b=bb;
                rn->next=new;
                rn=new;
            }
            qs=qs->next;
        }
        ps=ps->next;
    }