链表

本文最后更新于 2024年9月18日 凌晨

单链表

原理

定义一个结构体，里面包括data和next指针，其中，data表示的是这个单元存储的数据，而next则指向下一个结构体。于是，通过next的指针传递，组成一个单链。

我们为这个单链实现增添元素，打印元素，删除元素等基本操作。

添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void add(struct ls**pf,int num)
//这里使用struct ls**pf的原因是当
{  
    //头指针需要特殊处理
    if(*pf==NULL){  
        *pf=(struct ls*)malloc(sizeof(pf));  
        (*pf)->data=num;  
        (*pf)->next=NULL;  
        return;  
    }  
    struct ls *pb=NULL;  
    struct ls *addin;  
    //对于addin这一结构体指针动态分配
    addin=(struct ls*)malloc(sizeof(addin));  
    addin->data=num;  
    addin->next=NULL;  
    for(pb=*pf;pb->next!=NULL;pb=pb->next){}  
    pb->next=addin;  
    return;  
}

打印元素

1
2
3
4
5
6
7
8
void printf_linklist(struct ls *ph) {  
    struct ls *pcur;  
  
    for (pcur = ph; pcur->next != NULL; pcur = pcur->next) {  
        printf("%d\n", pcur->data);  
    }  
    printf("%d\n", pcur->data);  
}

删除元素

1
2
3
4
5
6
void delete(struct ls**pf)
{
	for(pb=*pf;pb->next->next!=NULL;pb=pb->next){}
	free(pb->next);
	pb->next=NULL;
}

释放单列表

1
2
3
4
5
6
7
8
9
10
void delete_all(struct ls*pf)  
{  
    struct ls*del;  
    struct ls*next_del;  
    for(del=pf;del->next!=NULL;del=next_del)  
    {  
        next_del=del->next;  
        free(del);  
    }  
}

例子

在链表中添加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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<stdio.h>  
#include<stdlib.h>  
struct ls {  
    int data;  
    struct ls* next;  
};  
void add(struct ls**pf,int num)  
{  
    if(*pf==NULL){  
        *pf=(struct ls*)malloc(sizeof(pf));  
        (*pf)->data=num;  
        (*pf)->next=NULL;  
        return;  
    }  
    struct ls *pb=NULL;  
    struct ls *addin;  
    addin=(struct ls*)malloc(sizeof(addin));  
    addin->data=num;  
    addin->next=NULL;  
    for(pb=*pf;pb->next!=NULL;pb=pb->next){}  
    pb->next=addin;  
    return;  
}  
void printf_linklist(struct ls *ph) {  
    struct ls *pcur;  
  
    for (pcur = ph; pcur->next != NULL; pcur = pcur->next) {  
        printf("%d\n", pcur->data);  
    }  
    printf("%d\n", pcur->data);  
}  
void delete(struct ls*pf)  
{  
    struct ls*del;  
    struct ls*next_del;  
    for(del=pf;del->next!=NULL;del=next_del)  
    {  
        next_del=del->next;  
        free(del);  
    }  
}  
int main()  
{  
    struct ls*h=NULL;  
    int t,n;
    scanf("%d",&n);  
    for(int i=1;i<=n;i++){  
        scanf("%d",&t);  
        add(&h,t);  
    }  
    printf_linklist(h);  
    delete(h);  
    return 0;  
}

拓展

顺序单链表

为了使链表有序，可以采取各种排序算法，但是由于链表是由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
void add(struct ls**pf,int num) {  
    if (*pf == NULL) {  
        *pf = (struct ls *) malloc(sizeof(pf));  
        (*pf)->data = num;  
        (*pf)->next = NULL;  
        return;  
    }  
    struct ls *pb =*pf;  
    struct ls *addin;  
    addin = (struct ls *) malloc(sizeof(addin));  
    addin->data = num;  
    addin->next = NULL;  
    if(pb->data>=num) {  
        struct ls *pre;  
        pre = (struct ls *) malloc(sizeof(pre));  
        pre->data = num;  
        pre->next = pb;  
        *pf = pre;  
    }  
    else {  
            for (; pb->next != NULL && pb->next->data < num; pb = pb->next) {}  
            if (pb->next != NULL) {  
                addin->next = pb->next;  
            }  
            pb->next = addin;  
        }  
    return;  
}

链表反转

next的方向只有一个，会为我们的反向输出带来困难，于是我们就可以通过链表反转来简化后续的处理（双链表就没有这个问题）

1
2
3
4
5
void reverse(struct ls*h)  
{  
    if(h->next!=NULL)reverse(h->next);  
    printf("%d->",h->data);  
}

形成环

实际上只需要把末尾的next指向头指针即可。

1
2
3
4
5
6
void loop(struct ls*h)  
{  
    struct ls *pb;  
    for (pb=h; pb->next != NULL; pb = pb->next) {}  
    pb->next=h;  
}

双链表

原理

单链表只有next来连接整个链表，而双链表则用next和last两个指针来连接，使列表操作更加灵活。

创建双链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void add(struct ls**pf,int num) {  
    if (*pf == NULL) {  
        *pf = (struct ls *) malloc(sizeof(pf));  
        (*pf)->data = num;  
        (*pf)->next = NULL;  
        (*pf)->last=NULL;  
        return;  
    }  
    struct ls *pb =*pf;  
    struct ls *addin;  
    addin = (struct ls *) malloc(sizeof(addin));  
    addin->data = num;  
    addin->next = NULL;  
    for(;pb->next!=NULL;pb=pb->next){}  
    pb->next = addin;  
    addin->last=pb;  
    return;  
}

拓展

形成环

多一个指针只需要多维护一个指针即可。 

1
2
3
4
5
6
7
void loop(struct ls*h)  
{  
    struct ls *pb;  
    for (pb=h; pb->next != NULL; pb = pb->next) {}  
    pb->next=h;  
    h->last=pb;  
}

结构体如下： 

1
2
3
4
5
6
7
8
9
10
11
typedef struct arr{  
    int data;  
    int index;  
    struct arr* next;  
    struct arr* last;  
}arrs;  
typedef struct list{  
    arrs* proof;  
    arrs* end;    
    int len;  
}lists;

特征值拓展

对于一个链表来说特征值只有一个头结点，如果我们想要进行查找和比较时会增加很多不必要的操作，不仅增加了代码长度还增加了时间复杂度，但是例如链表长度，链表尾部元素指针等特殊值对于一个链表只需要一个，直接在链表的结构体上增加元素是不妥当的。 于是就可以用两个结构体来解决这个问题，让这个链表操作和数组操作差不多，甚至超过数组所具有的操作。

这里直接来个仿真数组的函数集合。 

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
//添加元素和特征值
void addarr(lists**ls,char c)  
{  
    if(*ls==NULL){  
        (*ls)=malloc(sizeof(lists));  
        (*ls)->proof=malloc(sizeof(arrs));  
        (*ls)->proof->data=c;  
        (*ls)->proof->next=NULL;  
        (*ls)->proof->last=NULL;  
        (*ls)->proof->index=1;  
        (*ls)->end=(*ls)->proof;    
        (*ls)->len=1;  
    }  
    else{  
        arrs*addin;  
        addin=malloc(sizeof(arrs));  
        addin->data=c;  
        addin->next=NULL;  
        addin->last=(*ls)->end;  
        (*ls)->end->next=addin;  
        addin->index=(*ls)->end->index+1;  
        (*ls)->end=addin;  
        (*ls)->len++;  
    }  
}
//字符串读入
int scan(lists**ls)
{
	int judge=0;
	while(1){
		char ch;
		ch=getchar();
		if(ch==' '||ch=='\n')break;
		if(judge==0)judge=1;
		addarr(ls,ch);
	}
	return judge;
}
//字符串输出
void print(lists*ls)  
{  
    arrs*t=ls->proof;   
    while(t!=NULL){  
        printf("%c",t->data);  
        t=t->next;  
    }  
}
//删除字符串
void delete(lists**p)  
{  
    arrs*del=(*p)->proof,*delnext;  
    while(del->next!=NULL){  
        delnext=del->next;  
        free(del);  
        del=delnext;  
    }  
    (*p)->proof=NULL;  
    free(*p);  
    *p=NULL;  
}
//下标查找
char seek(lists*ls,int indexs)  
{  
    if(ls==NULL)return NULL;  
    arrs*pos;  
    if(indexs>ls->len/2){  
        pos=ls->end;  
        while(pos!=NULL&&pos->index!=indexs)pos=pos->last;  
    }  
    else{  
        pos=ls->proof;  
        while(pos!=NULL&&pos->index!=indexs)pos=pos->next;  
    }  
    return pos->data;  
}

如上是基本用链表模拟数组字符串的操作。（虽然可能会被认为是没有必要的，但是具有启发意义）

应用

实现高精度计算器

原理

加法

就是我们常规列竖式的计算方法，但是要注意的是如果有三个数相加，我们在这里只采取两个数相加后再将上次计算的结果与第三个数相加，一方面是因为高精度计算器不是只有加法，一方面是减少开大量的链表使空间复杂度过高。

减法

实际上就是将第二个数反号再与第一个数相加，因为我实现加法的时候已经考虑了负数的情况，因此直接变号相加。

加减法算法统一和优化

我们会发现加法和减法在预处理结果的正负号后，只需要写两种情况，大数减小数的减法和两个正数相加，得出的结果是个正数（减少减法负数情况下退位和进位的判断问题）加上预处理的符号就得到正确的结果。

乘法

以第二个数上的每一个位数对第一个数每一个位数相乘，并且加到正确的位数上，同样是竖式算法。 这里给出图例。 图例

除法

除法需要建立在减法的基础上，首先还是对结果的符号进行预处理，非常容易，然后把被除数的符号改成正数，除数的符号改为负数，这样下面进行的相减操作可以直接调用加法的函数。 从被除数中的高位开始取，第一次取和除数一样的位数，做减法（注意说是做减法但是我们要先判断结果的符号，如果是负号就不用相减了）返回减的次数（有可能为0，但是我们可以写一个去掉前导零的函数来解决结果的前导零）然后依此将被除数的下一位加入继续减法，直到被除数的位数都被读完。（仍然是竖式除法）

代码

当然理论要实际到代码，这里是我实现高精度计算器的代码（在c++编译器中会报错，原因是c++要求malloc函数的返回指针不能自动变为我们的结构体指针，只需在malloc前面加上指针转化即可） 输入需要严格遵循：数字+空格+符号+空格+数字+\(\dots\)+数字+回车； 

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
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
#include <stdio.h>  
#include <stdlib.h>  
typedef struct arr{  
    int data;  
    int index;  
    struct arr* next;  
    struct arr* last;  
}arrs;  
typedef struct list{  
    arrs* proof;  
    arrs* end;  
    int flag;  
    int len;  
}lists;  
//建立链表
void addarr(lists**ls,int num,int f);
//模拟读入
int scan(lists**ls);
//模拟输出
void print(lists*ls);
//预处理结果的符号
int judgef(lists*ls1,lists*ls2);
//删除链表
void delete(lists**p);
//去除前导零
void clear(lists*ls);  
//查找函数返回元素指针
arrs* seek(lists*ls,int indexs);
//将ls3中的数据复制到ls1中并将ls3删除
void recopy(lists**ls3,lists**ls1); 

void plus(lists**ls1,lists**ls2);
void substract(lists**ls1,lists**ls2);  
void multiply(lists**ls1,lists**ls2);  
void devise(lists**ls1,lists**ls2);  
int main()  
{  
    lists*head1=NULL,*head2=NULL;  
    scan(&head1);  
    clear(head1);  
    char c;  
    while(1) {  
        scanf("%c%*c", &c);  
        if (scan(&head2)==0)break;  
        clear(head2);  
        switch (c) {  
            case '+':  
                plus(&head1, &head2);  
                delete(&head2);  
                break;  
            case '-':  
                substract(&head1, &head2);  
                delete(&head2);  
                break;  
            case '*':  
                multiply(&head1,&head2);  
                break;  
            case '/':  
                devise(&head1,&head2);  
                if(head1==NULL){  
                    printf("除数不能为0");  
                    return 0;  
                }  
                delete(&head2);  
                break;  
        }  
    }  
    switch (c) {  
        case '+':  
            plus(&head1, &head2);  
            break;  
        case '-':  
            substract(&head1, &head2);  
            break;  
        case '*':  
            multiply(&head1,&head2);  
            break;  
        case '/':  
            devise(&head1,&head2);  
            if(head1==NULL){  
                printf("除数不能为0");  
                return 0;  
            }  
            break;  
    }  
    print(head1);  
    return 0;  
}  
void addarr(lists**ls,int num,int f)  
{  
    if(*ls==NULL){  
        (*ls)=malloc(sizeof(lists));  
        (*ls)->proof=malloc(sizeof(arrs));  
        (*ls)->proof->data=num;  
        (*ls)->proof->next=NULL;  
        (*ls)->proof->last=NULL;  
        (*ls)->proof->index=1;  
        (*ls)->end=(*ls)->proof;  
        (*ls)->flag=f;  
        (*ls)->len=1;  
    }  
    else{  
        arrs*addin;  
        addin=malloc(sizeof(arrs));  
        addin->data=num;  
        addin->next=NULL;  
        addin->last=(*ls)->end;  
        (*ls)->end->next=addin;  
        addin->index=(*ls)->end->index+1;  
        (*ls)->end=addin;  
        (*ls)->len++;  
    }  
}  
int scan(lists**ls)  
{  
    int flag=1,judge=1;  
    while(1)  
    {  
        char ch;  
        ch=getchar();  
        if(judge&&ch=='-'){  
            flag=-1;  
            judge=0;  
            continue;  
        }  
        if(ch==' ')break;  
        if(ch=='\n')return 0;  
        addarr(ls,ch-'0',flag);  
    }  
    return 1;  
}  
int judgef(lists*ls1,lists*ls2)  
{  
    arrs*t1=ls1->proof;arrs*t2=ls2->proof;  
    if(ls1->flag==ls2->flag){  
        int m=ls1->flag;  
        ls1->flag=1;  
        ls2->flag=1;  
        return m;  
    }  
    if(ls1->len>ls2->len){  
        return ls1->flag;  
    }  
    else if(ls1->len<ls2->len){  
        return ls2->flag;  
    }  
    else{  
        while(t1!=NULL&&t1->data==t2->data){  
            t1=t1->next;t2=t2->next;  
        }  
        if(t1==NULL)return 0;  
        if(t1->data>t2->data)return ls1->flag;  
        else return ls2->flag;  
    }  
}  
void delete(lists**p)  
{  
    arrs*del=(*p)->proof,*delnext;  
    while(del->next!=NULL){  
        delnext=del->next;  
        free(del);  
        del=delnext;  
    }  
    (*p)->proof=NULL;  
    free(*p);  
    *p=NULL;  
}  
void clear(lists*ls)  
{  
    arrs*p=ls->proof;  
    arrs*del=p;  
    int i=0;  
    while(p->next!=NULL&&p->data==0){  
        p=p->next;  
        i++;  
        p->index-=i;  
        free(del);  
        del=p;  
        ls->len--;  
    }  
    ls->proof=p;  
    ls->proof->last=NULL;  
    while(p->next!=NULL){  
        p=p->next;  
        p->index-=i;  
    }  
}  
void recopy(lists**ls3,lists**ls1)  
{  
    delete(ls1);  
    arrs*pos=(*ls3)->end;  
    while(pos!=NULL){  
        addarr(ls1,pos->data,(*ls3)->flag);  
        pos=pos->last;  
    }  
    clear(*ls1);  
    delete(ls3);  
}  
void plus(lists**ls1,lists**ls2)  
{  
    lists*ls3=NULL;  
    arrs*pos1=(*ls1)->end;arrs*pos2=(*ls2)->end;  
    int jw=0;  
    int res,f;  
    f=judgef(*ls1,*ls2);  
    if(f==0){  
        delete(ls1);  
        addarr(ls1,0,1);  
        return;  
    }  
    else if(f==-1){  
        int tmp=(*ls1)->flag;(*ls1)->flag=(*ls2)->flag;(*ls2)->flag=tmp;  
    }  
    while(pos1!=NULL&&pos2!=NULL){  
        res=pos1->data*(*ls1)->flag+pos2->data*(*ls2)->flag+jw;  
        if(res>=0)jw=res/10;  
        else jw=-1;  
        addarr(&ls3,(10+res%10)%10,f);  
        pos1=pos1->last;  
        pos2=pos2->last;  
    }  
    while(pos1!=NULL){  
        res=pos1->data*(*ls1)->flag+jw;  
        if(res>=0)jw=res/10;  
        else jw=-1;  
        addarr(&ls3,(10+res%10)%10,f);  
        pos1=pos1->last;  
    }  
    while(pos2!=NULL){  
        res=pos2->data*(*ls2)->flag+jw;  
        if(res>=0)jw=res/10;  
        else jw=-1;  
        addarr(&ls3,(10+res%10)%10,f);  
        pos2=pos2->last;  
    }  
    while(jw!=0){  
        addarr(&ls3,jw%10,f);  
        jw=jw/10;  
    }  
    recopy(&ls3,ls1);  
}  
arrs* seek(lists*ls,int indexs)  
{  
    if(ls==NULL)return NULL;  
    arrs*pos;  
    if(indexs>ls->len/2){  
        pos=ls->end;  
        while(pos!=NULL&&pos->index!=indexs)pos=pos->last;  
    }  
    else{  
        pos=ls->proof;  
        while(pos!=NULL&&pos->index!=indexs)pos=pos->next;  
    }  
    return pos;  
}  
void print(lists*ls)  
{  
    arrs*t=ls->proof;  
    if(ls->flag==-1)printf("-");  
    while(t!=NULL){  
        printf("%d",t->data);  
        t=t->next;  
    }  
}  
void substract(lists**ls1,lists**ls2)  
{  
    (*ls2)->flag*=-1;  
    plus(ls1,ls2);  
}  
void multiply(lists**ls1,lists**ls2)  
{  
    lists*ls3=NULL;  
    int f=(*ls1)->flag*(*ls2)->flag;  
    int num;  
    arrs*pos1=(*ls1)->end;  
    while(pos1!=NULL){  
        arrs*pos2=(*ls2)->end;  
        while(pos2!=NULL){  
            arrs*p=seek(ls3,(*ls1)->len+(*ls2)->len-pos1->index-pos2->index+1);  
            num=pos2->data*pos1->data;  
            if(p==NULL)addarr(&ls3,num,f);  
            else p->data+=num;  
            pos2=pos2->last;  
        }  
        pos1=pos1->last;  
    }  
    int jw=0;  
    arrs*pos=ls3->proof;  
    while(pos!=NULL){  
        pos->data+=jw;  
        jw=pos->data/10;  
        pos->data=pos->data%10;  
        pos=pos->next;  
    }  
    if(jw!=0){  
        addarr(&ls3,jw%10,f);  
        jw/=10;  
    }  
    recopy(&ls3,ls1);  
    delete(ls2);  
}  
void devise(lists**ls1,lists**ls2)  
{  
    //判断除数是否为0
    if((*ls2)->len==1&&(*ls2)->proof->data==0){  
        delete(ls1);  
        delete(ls2);  
        return;  
    }  
    lists*ls3=NULL,*tmp=NULL;  
    int f=(*ls1)->flag*(*ls2)->flag;  
    (*ls1)->flag=1;  
    (*ls2)->flag=-1;  
    if((*ls1)->len<(*ls2)->len){  
        addarr(&ls3,0,1);  
        recopy(&ls3,ls1);  
        delete(ls2);  
    }  
    arrs*pos=(*ls1)->proof;  
    for(int i=1;i<=(*ls2)->len;i++){  
        addarr(&tmp,pos->data,1);  
        pos=pos->next;  
    }  
    while(1){  
        int l=0;  
        while(1) {  
            int fl = judgef(tmp, *ls2);  
            if (fl == -1)break;  
            plus(&tmp, ls2);  
            l++;  
            if(fl==0)break;  
        }  
        addarr(&ls3,l,f);  
        if(pos!=NULL){  
            addarr(&tmp,pos->data,1);  
            pos=pos->next;  
        }  
        else break;  
        clear(tmp);  
    }  
    delete(ls1);  
    arrs*t=ls3->proof;  
    while(t!=NULL){  
        addarr(ls1,t->data,1);  
        t=t->next;  
    }  
    delete(&ls3);  
    clear(*ls1);  
}

只能说是逻辑简单，调试代码时要多关注细节，还是比较费力的，特别是没有对自己所写的函数的深度理解。这里为想要写高精度计算器的伙伴们提个醒，每次处理过后的数据一定要统一，无论是符号还是顺序，千万不要因为自己建立的是双向链表就觉得顺序可有可无，否则调试的时候会自闭。

启发

我一直提到的数据统一是必要的，就以上面的高精度计算器为例，既然可以进行整数计算那么经过一定的调整一定也能计算实数。于是我对上面的代码进行微调立刻就实现了。

现在说说调整的思路，首先我们要深刻理解原先的代码，整数与小数只相差一个小数点，而在竖式中整数的运算和小数的运算也只相差了小数点的位置，那么我们可以为链表增加小数点的位置这一特征值。接下来，由于发现整数加减法要求的是数据最低位的权值相同（比如1.22和0.23最低位权值相同，1.22和1的权值不同）于是我们再补充一个为小数末尾添加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
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
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
#include <stdio.h>  
#include <stdlib.h>  
typedef struct arr{  
    int data;  
    int index;  
    struct arr* next;  
    struct arr* last;  
}arrs;  
typedef struct list{  
    arrs* proof;  
    arrs* end;  
    int flag;  
    int len;  
    int point;  
}lists;  
void addarr(lists**ls,int num,int f);  
int scan(lists**ls);  
int judgef(lists*ls1,lists*ls2);  
void delete(lists**p);  
void clear(lists*ls);  
void recopy(lists**ls3,lists**ls1,int pointPos);  
void plus(lists**ls1,lists**ls2);  
int addzero(lists**ls1,lists**ls2);  
arrs* seek(lists*ls,int indexs);  
void print(lists*ls);  
void substract(lists**ls1,lists**ls2);  
void multiply(lists**ls1,lists**ls2);  
void devise(lists**ls1,lists**ls2);  
int main()  
{  
    lists*head1=NULL,*head2=NULL;  
    scan(&head1);  
    char c;  
    while(1) {  
        scanf("%c%*c", &c);  
        if (scan(&head2)==0)break;  
        switch (c) {  
            case '+':  
                plus(&head1, &head2);  
                delete(&head2);  
                break;  
            case '-':  
                substract(&head1, &head2);  
                delete(&head2);  
                break;  
            case '*':  
                multiply(&head1, &head2);  
                break;  
            case '/':  
                devise(&head1,&head2);  
                if(head1==NULL){  
                    printf("除数不能为0");  
                    return 0;  
                }  
                delete(&head2);  
        }  
    }  
    switch (c) {  
        case '+':  
            plus(&head1, &head2);  
            break;  
        case '-':  
            substract(&head1, &head2);  
            break;  
        case '*':  
            multiply(&head1,&head2);  
            break;  
        case '/':  
            devise(&head1,&head2);  
            if(head1==NULL){  
                printf("除数不能为0");  
                return 0;  
            }  
            delete(&head2);  
    }  
    print(head1);  
    return 0;  
}  
void addarr(lists**ls,int num,int f)  
{  
    if(*ls==NULL){  
        (*ls)=malloc(sizeof(lists));  
        (*ls)->proof=malloc(sizeof(arrs));  
        (*ls)->proof->data=num;  
        (*ls)->proof->next=NULL;  
        (*ls)->proof->last=NULL;  
        (*ls)->proof->index=1;  
        (*ls)->end=(*ls)->proof;  
        (*ls)->flag=f;  
        (*ls)->len=1;  
    }  
    else{  
        arrs*addin;  
        addin=malloc(sizeof(arrs));  
        addin->data=num;  
        addin->next=NULL;  
        addin->last=(*ls)->end;  
        (*ls)->end->next=addin;  
        addin->index=(*ls)->end->index+1;  
        (*ls)->end=addin;  
        (*ls)->len++;  
    }  
}  
int scan(lists**ls)  
{  
    int flag=1,judge=1,pointf=0;  
    while(1)  
    {  
        char ch;  
        ch=getchar();  
        if(judge&&ch=='-'){  
            flag=-1;  
            judge=0;  
            continue;  
        }  
        if(ch=='.'&&!pointf){  
            (*ls)->point=(*ls)->len;  
            pointf=1;  
            continue;  
        }  
        if(ch==' ')break;  
        if(ch=='\n'){  
            if(!pointf)(*ls)->point=(*ls)->len;  
            return 0;  
        }  
        addarr(ls,ch-'0',flag);  
    }  
    if(!pointf)(*ls)->point=(*ls)->len;  
    return 1;  
}  
int judgef(lists*ls1,lists*ls2)  
{  
    arrs*t1=ls1->proof;arrs*t2=ls2->proof;  
    if(ls1->flag==ls2->flag){  
        int m=ls1->flag;  
        ls1->flag=1;  
        ls2->flag=1;  
        return m;  
    }  
    if(ls1->len>ls2->len){  
        return ls1->flag;  
    }  
    else if(ls1->len<ls2->len){  
        return ls2->flag;  
    }  
    else{  
        while(t1!=NULL&&t1->data==t2->data){  
            t1=t1->next;t2=t2->next;  
        }  
        if(t1==NULL)return 0;  
        if(t1->data>t2->data)return ls1->flag;  
        else return ls2->flag;  
    }  
}  
void delete(lists**p)  
{  
    arrs*del=(*p)->proof,*delnext;  
    while(del->next!=NULL){  
        delnext=del->next;  
        free(del);  
        del=delnext;  
    }  
    (*p)->proof=NULL;  
    free(*p);  
    *p=NULL;  
}  
void clear(lists*ls)  
{  
    arrs*p=ls->proof;  
    arrs*del=p;  
    int i=0;  
    while(p->next!=NULL&&p->data==0){  
        p=p->next;  
        i++;  
        p->index-=i;  
        free(del);  
        del=p;  
        ls->len--;  
        ls->point--;  
    }  
    ls->proof=p;  
    ls->proof->last=NULL;  
    while(p->next!=NULL){  
        p=p->next;  
        p->index-=i;  
    }  
}  
void recopy(lists**ls3,lists**ls1,int pointPos)  
{  
    delete(ls1);  
    arrs*pos=(*ls3)->end;  
    while(pos!=NULL){  
        addarr(ls1,pos->data,(*ls3)->flag);  
        pos=pos->last;  
    }  
    (*ls1)->point=pointPos;  
    clear(*ls1);  
    delete(ls3);  
}  
int addzero(lists**ls1,lists**ls2)  
{  
    int res;  
    int ls1point=(*ls1)->len-(*ls1)->point;  
    int ls2point=(*ls2)->len-(*ls2)->point;  
    if(ls1point>=ls2point) {  
        res = ls1point;  
        for (int i = 1; i <= ls1point-ls2point; i++) {  
            addarr(ls2, 0, (*ls2)->flag);  
        }  
    }  
    else {  
        res =ls2point;  
        for (int i = 1; i <= ls2point - ls1point; i++) {  
            addarr(ls1, 0, (*ls1)->flag);  
        }  
    }  
    return res;  
}  
void plus(lists**ls1,lists**ls2)  
{  
    lists*ls3=NULL;  
    int pointPos;  
    pointPos=addzero(ls1,ls2);  
    arrs*pos1=(*ls1)->end;arrs*pos2=(*ls2)->end;  
    int jw=0;  
    int res,f;  
    f=judgef(*ls1,*ls2);  
    if(f==0){  
        delete(ls1);  
        addarr(ls1,0,1);  
        return;  
    }  
    else if(f==-1){  
        int tmp=(*ls1)->flag;(*ls1)->flag=(*ls2)->flag;(*ls2)->flag=tmp;  
    }  
    while(pos1!=NULL&&pos2!=NULL){  
        res=pos1->data*(*ls1)->flag+pos2->data*(*ls2)->flag+jw;  
        if(res>=0)jw=res/10;  
        else jw=-1;  
        addarr(&ls3,(10+res%10)%10,f);  
        pos1=pos1->last;  
        pos2=pos2->last;  
    }  
    while(pos1!=NULL){  
        res=pos1->data*(*ls1)->flag+jw;  
        if(res>=0)jw=res/10;  
        else jw=-1;  
        addarr(&ls3,(10+res%10)%10,f);  
        pos1=pos1->last;  
    }  
    while(pos2!=NULL){  
        res=pos2->data*(*ls2)->flag+jw;  
        if(res>=0)jw=res/10;  
        else jw=-1;  
        addarr(&ls3,(10+res%10)%10,f);  
        pos2=pos2->last;  
    }  
    while(jw!=0){  
        addarr(&ls3,jw%10,f);  
        jw=jw/10;  
    }  
    recopy(&ls3,ls1,ls3->len-pointPos);  
    clear(*ls1);  
}  
arrs* seek(lists*ls,int indexs)  
{  
    if(ls==NULL)return NULL;  
    arrs*pos;  
    if(indexs>ls->len/2){  
        pos=ls->end;  
        while(pos!=NULL&&pos->index!=indexs)pos=pos->last;  
    }  
    else{  
        pos=ls->proof;  
        while(pos!=NULL&&pos->index!=indexs)pos=pos->next;  
    }  
    return pos;  
}  
void print(lists*ls)  
{  
    arrs*t=ls->proof;  
    if(ls->flag==-1)printf("-");  
    if(ls->point<=0){  
        printf("0");  
        printf(".");  
        for(int i=0;i>ls->point;i--)printf("0");  
    }  
    while(t!=NULL){  
        printf("%d",t->data);  
        if(ls->point==t->index&&t->next!=NULL)printf(".");  
        t=t->next;  
    }  
}  
void substract(lists**ls1,lists**ls2)  
{  
    (*ls2)->flag*=-1;  
    plus(ls1,ls2);  
}  
void multiply(lists**ls1,lists**ls2)  
{  
    int pointPosv=(*ls1)->len+(*ls2)->len-(*ls1)->point-(*ls2)->point;  
    lists*ls3=NULL;  
    int f=(*ls1)->flag*(*ls2)->flag;  
    int num;  
    arrs*pos1=(*ls1)->end;  
    while(pos1!=NULL){  
        arrs*pos2=(*ls2)->end;  
        while(pos2!=NULL){  
            arrs*p=seek(ls3,(*ls1)->len+(*ls2)->len-pos1->index-pos2->index+1);  
            num=pos2->data*pos1->data;  
            if(p==NULL)addarr(&ls3,num,f);  
            else p->data+=num;  
            pos2=pos2->last;  
        }  
        pos1=pos1->last;  
    }  
    int jw=0;  
    arrs*pos=ls3->proof;  
    while(pos!=NULL){  
        pos->data+=jw;  
        jw=pos->data/10;  
        pos->data=pos->data%10;  
        pos=pos->next;  
    }  
    if(jw!=0){  
        addarr(&ls3,jw%10,f);  
        jw/=10;  
    }  
    recopy(&ls3,ls1,ls3->len-pointPosv);  
    delete(ls2);  
}  
void devise(lists**ls1,lists**ls2)  
{  
    if((*ls2)->len==1&&(*ls2)->proof->data==0){  
        delete(ls1);  
        delete(ls2);  
        return;  
    }  
    int f=(*ls1)->flag*(*ls2)->flag;  
    int ws1=(*ls1)->len-(*ls1)->point;  
    int ws2=(*ls2)->len-(*ls2)->point;  
    if(ws2>ws1)addzero(ls1,ls2);  
    int pointPos=(*ls1)->len-(ws1-ws2);  
    lists*ls3=NULL,*tmp=NULL;  
    (*ls1)->flag=1;  
    (*ls2)->flag=-1;  
    for(int i=1;i<=9-ws1;i++)addarr(ls1,0,(*ls1)->flag);  
    arrs*pos=(*ls1)->proof;  
    addarr(&tmp,pos->data,1);  
    pos=pos->next;  
    (*ls2)->point=(*ls2)->len;  
    clear(*ls2);  
    while(1){  
        int l=0;  
        while(1) {  
            tmp->point=tmp->len;  
            int fl = judgef(tmp, *ls2);  
            if (fl == -1)break;  
            plus(&tmp, ls2);  
            l++;  
            if(fl==0)break;  
        }  
        addarr(&ls3,l,f);  
        if(pos!=NULL){  
            addarr(&tmp,pos->data,1);  
            pos=pos->next;  
        }  
        else break;  
        clear(tmp);  
    }  
    delete(ls1);  
    arrs*t=ls3->proof;  
    while(t!=NULL){  
        addarr(ls1,t->data,f);  
        t=t->next;  
    }  
    (*ls1)->point=pointPos;  
    delete(&ls3);  
    clear(*ls1);  
}

这里再补充说明一下实数除法的实现，统一的数据结构在加减乘上非常容易，但是由于我的除法是在整数除法的基础上实现的，因此在除法时反而要破坏我实现的统一的数据结构，不是很令人满意，但目前没有想到在不改变数据结构的情况下的算法，如果有好的想法，欢迎留言。

计算机 > C语言
#算法学习
链表
http://example.com/posts/链表/
作者
晓寒
发布于
2022年11月30日
许可协议