递归列表

一般而言，自己定义自己就会产生递归。递归类型结构包含一个对相同类型的另一个值的引用。

链表的递归表述

如果将链表看成是指向一个表项的指针，那么链表是由更小的子链表构成。最简单的情景就是常量NULL，表示一个空链表。非空链表构成了递归的情况，每个链表都是由一个指向第一个元素的链表表项的指针和一个由随后元素组成的链表构成。链表的第一个元素称为头，除去头的子链表称为尾。链表的头和尾是不同的概念类型，链表的头总是单个元素，尾则是一个链表，尽管这个链表可能为空。在进行递归处理时，每个链表都符合以下两种情况之一：

空链表，由常量NULL表示；
非空链表，由一个紧随着一个链表的元素构成。

禁止用户对其底层进行任何修改的抽象类型称为不变类型。不变类型具有一下几个重要特征：

不变类型通常具有简单的内部结构；
在不变类型中，可以使用空指针来指名空抽象值；
使用不变类型通常使得程序的行为更易理解；
不变类型允许数据的内部共享。

1
2
3
4
5
6
7
8
9
10
11
#ifndef _list_h
#define _list_h

typedef void *listElementT;
typedef struct listCDT *listADT;

listADT ListCons(listElementT head, listADT tail);

listElementT ListHead(listADT list);
listADT ListTail(listADT list);
#endif

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 <stdlib.h>
#include "list.h"

struct listCDT{
    listElementT head;
    listADT tail;
};

listADT ListCons(listElementT head, listADT tail){
    listADT list;

    list = malloc(sizeof (*list));
    list->head = head;
    list->tail = tail;

    return (list);
}

listElementT ListHead(listADT list){
    return (list->head);
}
listADT ListTail(listADT list){
    return (list->tail);
}

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 <stdlib.h>
#include "list.h"

int ListLength(listADT list){
    if(list == NULL){
        return (0);
    }
    else{
        return (ListLength(ListTail(list)) + 1);
    }
}

listElementT NthElement(listADT list, int n){
    if(list == NULL){
        // 应抛出错误
    }
    else if(n == 0){
        return (ListHead(list));
    }
    else{
        return (NthElement(ListTail(list), n-1));
    }
}

listADT ListConcat(listADT list1, listADT list2){
    if(list1 == NULL){
        return (list2);
    }
    else{
        return (ListCons(ListHead(list1), ListConcat(ListTail(list1), list2)));
    }
}

用链表表示大整数

在编码过程中保护数字数据的现代技术通常需要使用比硬件所能提供的类型大得多的整数。解除硬件带来限制的最简单方法是将大整数打散成小块，每个小块存储到一个单独的内存空间，这种技术一般称为多精度算法（multiple-precision arithmetic）。

为了便于计算，以跟习惯相反的顺序在链表中存储数字，即各位在链表链的第一个位置出现，然后依次是高位数字。将表示bigIntADT的链表分为头和尾两个组成部分，头表示末位数，尾表示的是原整数的前面数字，即如果一个bigIntADT的数学值是n，则头为n%10，尾为n/10，用空表示数学值0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#ifndef _bigint_h
#define _bigint_h

typedef char *string;

typedef struct bigIntCDT *bigIntADT;

bigIntADT NewBigInt(int i);

bigIntADT StringToBigInt(string str);
string BigIntToString(bigIntADT n);

bigIntADT AddBigInt(bigIntADT n1, bigIntADT n2);

bigIntADT MultiplyBigInt(bigIntADT n1, bigIntADT n2);

#endif

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
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include "bigint.h"

struct bigIntCDT{
    int finalDigit;
    bigIntADT leadingDigits;
};

static bigIntADT StringToBigIntWithLength(string str, int len);
static bigIntADT AddWithCarry(bigIntADT n1, bigIntADT n2, int carry);
static bigIntADT MultiplyDigit(int digit, bigIntADT n);
static bigIntADT DigitCons(bigIntADT leadingDigits, int finalDigit);
static int FinalDigit(bigIntADT n);
static bigIntADT LeadingDigits(bigIntADT n);

bigIntADT NewBigInt(int i){
    if(i == 0){
        return (NULL);
    }
    else if(i > 0){
        return (DigitCons(NewBigInt(i/10), i%10));
    }
}

bigIntADT StringToBigInt(string str){
    int len;
    len = strlen(str);
    if(len == 0){
        return NULL;
    }
    return StringToBigIntWithLength(str, len);
}
string BigIntToString(bigIntADT n){
    string str1, str2, str3;
    int len;
    str1 = malloc(sizeof(char) * 2);
    str1[0] = FinalDigit(n) + '0';
    str1[1] = '\0';
    if(LeadingDigits(n) != NULL){
        str2 = BigIntToString(LeadingDigits(n));
        int len = strlen(str2);
        str3 = malloc(sizeof(char) * (2 + len));
        strcpy(str3, str2);
        strcpy(str3+len, str1);
        free(str1);
        free(str2);
        return (str3);
    }
    else{
        return (str1);
    }
}

bigIntADT AddBigInt(bigIntADT n1, bigIntADT n2){
    return (AddWithCarry(n1, n2, 0));
}

bigIntADT MultiplyBigInt(bigIntADT n1, bigIntADT n2){
    if(n1==NULL || n2==NULL){
        return (NULL);
    }
    return (AddBigInt(MultiplyDigit(FinalDigit(n1), n2), MultiplyBigInt(LeadingDigits(n1), DigitCons(n2, 0))));
}

static bigIntADT StringToBigIntWithLength(string str, int len){
    char digit;
    if(len == 0){
        return NULL;
    }
    digit = str[len-1] - '0';
    return (DigitCons(StringToBigIntWithLength(str, --len), digit));
}
static bigIntADT AddWithCarry(bigIntADT n1, bigIntADT n2, int carry){
    int sum;
    bigIntADT p1, p2;

    p1 = LeadingDigits(n1);
    p2 = LeadingDigits(n2);

    sum = FinalDigit(n1) + FinalDigit(n2) + carry;

    if(sum==0 && p1==NULL && p2==NULL){
        return (NULL);
    }
    return (DigitCons(AddWithCarry(p1, p2, sum/10), sum%10));
}
static bigIntADT MultiplyDigit(int digit, bigIntADT n){
    if(digit == 0){
        return NULL;
    }
    return (AddBigInt(n, MultiplyDigit(digit-1, n)));
}
static bigIntADT DigitCons(bigIntADT leadingDigits, int finalDigit){
    bigIntADT cp;

    int len;
    len = sizeof(*cp);

    if(leadingDigits==NULL && finalDigit==0){
        return NULL;
    }
    cp = malloc(sizeof(*cp));
    cp->finalDigit = finalDigit;
    cp->leadingDigits = leadingDigits;

    return (cp);
}
static int FinalDigit(bigIntADT n){
    return (n==NULL ? 0 : n->finalDigit);
}
static bigIntADT LeadingDigits(bigIntADT n){
    return (n==NULL ? NULL : n->leadingDigits);
}

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

#define LowerLimit 0
#define UpperLimit 20

static bigIntADT BigFact(int n);

main(){
    int i;
    for(i=LowerLimit; i<=UpperLimit; i++){
        printf("%2d!=%s\n", i, BigIntToString(BigFact(i)));
    }
}

static bigIntADT BigFact(int n){
    if(n == 0){
        return NewBigInt(1);
    }
    else{
        return (MultiplyBigInt(NewBigInt(n), BigFact(n-1)));
    }
}