补拙·启源

抽象数据类型

数据结构可以通过组合建立层次结构。原子数据类型，例如int、char、double和枚举类型在层次结构的最底层。为了表示更加复杂的信息，可以通过数组、记录和指针三种基本的构建方法将这些原子类型组合成较大的结构。这些较大的结构可以组合成更大的结构，这是一个无穷的过程。

如果某一个类型的定义更注重它的行为而非表示，按照它的行为而非它的表示方式定义的类型就称为抽象数据类型，缩写为ADT。

栈

栈是这样一种编程结构：它的抽象行为特征为从栈中删除元素的顺序与加入元素的顺序相反（后进先出，last in first out，LIFO）。最后加入的元素最先出来。向栈中加入一个新值称为“入栈”，删除一个最新的值称为“出栈”。

栈中的数据值的类型必须由客户来决定。遗憾的是ANSI C没有为定义多态的接口提供一种理想的机制，以便使得同一个接口可以处理很多不同的类型。尽管限制了客户使用指针的类型，但是通过使用void *类型作为基础类型可以在一定程度上实现多态性。另一种方法是根据一种新的类型如stackElementT定义接口，这样使任何对于基础类型的依赖性都限制在单个的定义上。

定义栈为ADT使得改变他们的底层表示而客户不需要改变他们的代码成为了可能。在本章中，栈使用了静态和动态数组两种实现方式。

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

#ifndef _stack_h
#define _stack_h

typedef enum {false, true} bool;

typedef char stackElementT;

typedef struct stackCDT * stackADT;

stackADT NewStack(void);

void FreeStack(stackADT stack);

void Push(stackADT stack, stackElementT element);

stackElementT Pop(stackADT stack);

bool StackIsEmpty(stackADT stack);

bool StackIsFull(stackADT stack);

int StackDepth(stackADT stack);

stackElementT GetStackElement(stackADT stack, int index);

#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

#include <stdlib.h>
#include "stack.h"

#define MaxStackSize 100

struct stackCDT{
    stackElementT elements[MaxStackSize];
    int count;
};

stackADT NewStack(void){
    stackADT stack;
    stack = malloc(sizeof (* stack));
    stack->count = 0;
    return (stack);
}

void FreeStack(stackADT stack){
    free(stack);
}

void Push(stackADT stack, stackElementT element){
    if(!StackIsFull(stack)){
        stack->elements[stack->count++] = element;
    }
}

stackElementT Pop(stackADT stack){
    if(!StackIsEmpty(stack)){
        return (stack->elements[--stack->count]);
    }
}

bool StackIsEmpty(stackADT stack){
    return (stack->count == 0);
}

bool StackIsFull(stackADT stack){
    return (stack->count == MaxStackSize);
}

int StackDepth(stackADT stack){
    return (stack->count);
}

stackElementT GetStackElement(stackADT stack, int index){
    if(index>=0 && index<stack->count){
        return (stack->elements[stack->count - index - 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

#include <stdlib.h>
#include "stack.h"

#define InitialStackSize 100

struct stackCDT{
    stackElementT * elements;
    int count;
    int size;
};

static void ExpandStack(stackADT stack){
    stackElementT *array;
    int i, newSize;

    newSize = stack->size * 2;
    array = malloc(newSize * sizeof(stackElementT));
    for(i=0; i<stack->size; i++){
        array[i] = stack->elements[i];
    }
    free(stack->elements);
    stack->elements = array;
    stack->size = newSize;
}

stackADT NewStack(void){
    stackADT stack;
    stack = malloc(sizeof (* stack));
    stack->elements = malloc(InitialStackSize * sizeof(stackElementT));
    stack->count = 0;
    stack->size = InitialStackSize;
    return (stack);
}

void FreeStack(stackADT stack){
    free(stack->elements);
    free(stack);
}

void Push(stackADT stack, stackElementT element){
    if(stack->count == stack->size){
        ExpandStack(stack);
    }
    stack->elements[stack->count++] = element;
}

stackElementT Pop(stackADT stack){
    if(!StackIsEmpty(stack)){
        return (stack->elements[--stack->count]);
    }
}

bool StackIsEmpty(stackADT stack){
    return (stack->count == 0);
}

bool StackIsFull(stackADT stack){
    return (false);
}

int StackDepth(stackADT stack){
    return (stack->count);
}

stackElementT GetStackElement(stackADT stack, int index){
    if(index>=0 && index<stack->count){
        return (stack->elements[stack->count - index - 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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

#include <stdlib.h>
#include "stack.h"

typedef struct cellT{
    stackElementT element;
    struct cellT * link;
} cellT;

struct stackCDT{
    cellT * start;
};

stackADT NewStack(void){
    stackADT stack;

    stack = malloc(sizeof (* stack));
    stack->start = NULL;

    return (stack);
}

void FreeStack(stackADT stack){
    cellT *cp, *next;

    cp = stack->start;
    while(cp != NULL){
        next = cp->link;
        free(cp);
        cp = next;
    }

    free(stack);
}

void Push(stackADT stack, stackElementT element){
    cellT *cp;
    cp = malloc(sizeof (*cp));
    cp->element = element;
    cp->link = stack->start;
    stack->start = cp;
}

stackElementT Pop(stackADT stack){
    cellT *cp;
    stackElementT element;

    if(!StackIsEmpty(stack)){
        element = stack->start->element;
        cp = stack->start;
        stack->start = cp->link;
        free(cp);
    }

    // 此处存在错误，当是空栈时应该抛出异常
    return element;
}

bool StackIsEmpty(stackADT stack){
    return (stack->start == NULL);
}

bool StackIsFull(stackADT stack){
    return (false);
}

int StackDepth(stackADT stack){
    int count;
    cellT *cp;

    count = 0;
    cp = stack->start;
    while(cp != NULL){
        cp = cp->link;
        count++;
    }

    return count;
}

stackElementT GetStackElement(stackADT stack, int index){
    int i;
    cellT *cp;

    if(index>=0 && index<(StackDepth(stack))){
        cp = stack->start;
        for(i=0; i<index; i++){
            cp = cp->link;
        }
    }

    // 此处存在错误，当是空栈时应该抛出异常
    return cp->element;
}

编辑器缓冲区

编辑器在内部维护的是字符的序列，通常称为缓冲区。

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

#ifndef _buffer_h
#define _buffer_h
typedef struct bufferCDT * bufferADT;

bufferADT NewBuffer(void);

void FreeBuffer(bufferADT buffer);

void MoveCursorForward(bufferADT buffer);
void MoveCursorBackward(bufferADT buffer);

void MoveCursorToStart(bufferADT buffer);
void MoveCursorToEnd(bufferADT buffer);

void InsertCharacter(bufferADT buffer, char ch);
void DeleteCharacter(bufferADT buffer);

void DisplayBuffer(bufferADT buffer);
#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

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include "buffer.h"

typedef char *string;
typedef enum {false, true} bool;

static void ExecuteCommand(bufferADT buffer, string line);
static void HelpCommand(void);

main(){
    char str[80];
    bufferADT buffer;
    buffer = NewBuffer();
    while(true){
        printf("* ");
        scanf("%s", str);
        ExecuteCommand(buffer, str);
        DisplayBuffer(buffer);
    }
    FreeBuffer(buffer);
}

static void ExecuteCommand(bufferADT buffer, string line){
    int i;
    switch(toupper(line[0])){
        case 'I':
            for(i=1; line[i]!= '\0'; i++){
                InsertCharacter(buffer, line[i]);
            }
            break;
        case 'D':
            DeleteCharacter(buffer);
            break;
        case 'F':
            MoveCursorForward(buffer);
            break;
        case 'B':
            MoveCursorBackward(buffer);
            break;
        case 'J':
            MoveCursorToStart(buffer);
            break;
        case 'E':
            MoveCursorToEnd(buffer);
            break;
        case 'H':
            HelpCommand();
            break;
        case 'Q':
            exit(0);
        default:
            printf("Illegal command\n");
            break;
    }
}

static void HelpCommand(void){
    printf("Use the following commands to edit the buffer: \n");
    printf(" I      Inserts text up to the end of the line\n");
    printf(" F      Moves forward a character\n");
    printf(" B      Moves backword a character\n");
    printf(" J      Jumps to the beginning of the buffer\n");
    printf(" E      Jumps to the end of the buffer\n");
    printf(" D      Deletes the next character\n");
    printf(" H      Cenerates a help message\n");
    printf(" Q      Quits the program\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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

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

#define MaxBuffer 100

struct bufferCDT{
    char text[MaxBuffer];
    int length;
    int cursor;
};

bufferADT NewBuffer(void){
    bufferADT buffer;

    buffer = malloc(sizeof *buffer);
    buffer->length = buffer->cursor = 0;

    return (buffer);
}

void FreeBuffer(bufferADT buffer){
    free(buffer);
}

void MoveCursorForward(bufferADT buffer){
    if(buffer->cursor < buffer->length){
        buffer->cursor++;
    }
}
void MoveCursorBackward(bufferADT buffer){
    if(buffer->cursor > 0){
        buffer->cursor--;
    }
}

void MoveCursorToStart(bufferADT buffer){
    buffer->cursor = 0;
}
void MoveCursorToEnd(bufferADT buffer){
    buffer->cursor = buffer->length;
}

void InsertCharacter(bufferADT buffer, char ch){
    int i;
    if(buffer->length == MaxBuffer){
        return;
    }
    for(i=buffer->length; i>buffer->cursor; i--){
        buffer->text[i] = buffer->text[i-1];
    }
    buffer->text[buffer->cursor] = ch;
    buffer->length++;
    buffer->cursor++;
}
void DeleteCharacter(bufferADT buffer){
    int i;
    if(buffer->cursor < buffer->length){
        for(i=buffer->cursor+1; i<buffer->length; i++){
            buffer->text[i-1] = buffer->text[i];
        }
        buffer->length--;
    }
}

void DisplayBuffer(bufferADT buffer){
    int i;

    for(i=0; i<buffer->length; i++){
        printf("%c", buffer->text[i]);
    }
    printf("\n");

    for(i=0; i<buffer->cursor; i++){
        printf(" ");
    }
    printf("^\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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
#include "buffer.h"

struct bufferCDT{
    stackADT before;
    stackADT after;
};

bufferADT NewBuffer(void){
    bufferADT buffer;

    buffer = malloc(sizeof *buffer);
    buffer->before = NewStack();
    buffer->after = NewStack();

    return (buffer);
}

void FreeBuffer(bufferADT buffer){
    FreeStack(buffer->before);
    FreeStack(buffer->after);
    free(buffer);
}

void MoveCursorForward(bufferADT buffer){
    if(!StackIsEmpty(buffer->after)){
        Push(buffer->before, Pop(buffer->after));
    }
}
void MoveCursorBackward(bufferADT buffer){
    if(!StackIsEmpty(buffer->before)){
        Push(buffer->after, Pop(buffer->before));
    }
}

void MoveCursorToStart(bufferADT buffer){
    while(!StackIsEmpty(buffer->before)){
        Push(buffer->after, Pop(buffer->before));
    }
}
void MoveCursorToEnd(bufferADT buffer){
    while(!StackIsEmpty(buffer->after)){
        Push(buffer->before, Pop(buffer->after));
    }
}

void InsertCharacter(bufferADT buffer, char ch){
    Push(buffer->before, ch);
}
void DeleteCharacter(bufferADT buffer){
    if(StackIsEmpty(buffer->after)){
        Pop(buffer->after);
    }
}

void DisplayBuffer(bufferADT buffer){
    int i;
    int blen = StackDepth(buffer->before);
    int alen = StackDepth(buffer->after);

    for(i=blen-1; i>=0; i--){
        printf("%c", GetStackElement(buffer->before, i));
    }
    for(i=0; i<alen; i++){
        printf("%c", GetStackElement(buffer->after, i));
    }
    printf("\n");

    for(i=0; i<blen; i++){
        printf(" ");
    }
    printf("^\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
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

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

typedef struct cellT{
    char value;
    struct cellT * link;
} cellT;

struct bufferCDT{
    cellT * start;
    cellT * cursor;
};

bufferADT NewBuffer(void){
    bufferADT buffer;

    buffer = malloc(sizeof *buffer);
    buffer->start = buffer->cursor = malloc(sizeof(cellT));
    buffer->start->link = NULL;

    return (buffer);
}

void FreeBuffer(bufferADT buffer){
    cellT *cp, *next;
    cp = buffer->start;
    while(cp != NULL){
        next = cp->link;
        free(cp);
        cp = next;
    }
    free(buffer);
}

void MoveCursorForward(bufferADT buffer){
    if(buffer->cursor->link != NULL){
        buffer->cursor = buffer->cursor->link;
    }
}
void MoveCursorBackward(bufferADT buffer){
    cellT *cp;
    if(buffer->start != buffer->cursor){    // 此处判断可以省略，逻辑不会出现错误
        cp = buffer->start;
        while(cp->link != buffer->cursor){
            cp = cp->link;
        }
        buffer->cursor = cp;
    }
}

void MoveCursorToStart(bufferADT buffer){
    buffer->cursor = buffer->start;
}
void MoveCursorToEnd(bufferADT buffer){
    while(buffer->cursor->link != NULL){
        // MoveCursorForward(buffer);
        buffer->cursor = buffer->cursor->link;
    }
}

void InsertCharacter(bufferADT buffer, char ch){
    cellT *cp = malloc(sizeof(cellT));
    cp->value = ch;
    cp->link = buffer->cursor->link;
    buffer->cursor->link = cp;
    buffer->cursor = cp;
}
void DeleteCharacter(bufferADT buffer){
    cellT *cp;
    if(buffer->cursor->link != NULL){
        cp = buffer->cursor->link;
        buffer->cursor->link = cp->link;
        free(cp);
    }
}

void DisplayBuffer(bufferADT buffer){
    cellT *cp;

    for(cp=buffer->start->link; cp!=NULL; cp=cp->link){
        printf("%c", cp->value);
    }

    printf("\n");

    for(cp=buffer->start; cp!=buffer->cursor; cp=cp->link){
        printf(" ");
    }
    printf("^\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
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

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

typedef struct cellT{
    char value;
    struct cellT * prev;
    struct cellT * next;
} cellT;

struct bufferCDT{
    cellT * start;
    cellT * cursor;
};

bufferADT NewBuffer(void){
    bufferADT buffer;

    buffer = malloc(sizeof *buffer);
    buffer->start = buffer->cursor = malloc(sizeof(cellT));
    buffer->start->next = buffer->start;
    buffer->start->prev = buffer->start;

    return (buffer);
}

void InsertCharacter(bufferADT buffer, char ch){
    cellT *cp = malloc(sizeof(cellT));
    cp->value = ch;
    cp->next = buffer->cursor->next;
    cp->prev = buffer->cursor;
    cp->next->prev = cp;
    buffer->cursor->next = cp;
    buffer->cursor = cp;
}

void DeleteCharacter(bufferADT buffer){
    cellT *cp;
    if(buffer->cursor->next != buffer->start){
        cp = buffer->cursor->next;
        buffer->cursor->next = cp->next;
        cp->next->prev = buffer->cursor;
        free(cp);
    }
}

void FreeBuffer(bufferADT buffer){
    cellT *cp, *next;
    cp = buffer->start;
    do{
        next = cp->next;
        free(cp);
        cp = next;
    }while(cp != buffer->start);
    free(buffer);
}

void MoveCursorForward(bufferADT buffer){
    if(buffer->cursor->next != buffer->start){
        buffer->cursor = buffer->cursor->next;
    }
}
void MoveCursorBackward(bufferADT buffer){
    if(buffer->cursor->prev != buffer->start->prev){
        buffer->cursor = buffer->cursor->prev;
    }
}

void MoveCursorToStart(bufferADT buffer){
    buffer->cursor = buffer->start;
}
void MoveCursorToEnd(bufferADT buffer){
    buffer->cursor = buffer->start->prev;
}

void DisplayBuffer(bufferADT buffer){
    cellT *cp;

    for(cp=buffer->start->next; cp!=buffer->start; cp=cp->next){
        printf("%c", cp->value);
    }

    printf("\n");

    for(cp=buffer->start; cp!=buffer->cursor; cp=cp->next){
        printf(" ");
    }
    printf("^\n");
}

队列

以FIFO（first in, first out）规则存储其数据项的数据结构称为队列。队列的基本操作与栈的压入和弹出操作类似，即Enqueue和Dequeue。入队操作在队列的最后（队尾）增加一个新元素。出队操作删除在队列最前面（队首）的一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#ifndef _queue_h
#define _queue_h

#include <stdlib.h>

typedef enum {false, true} bool;

typedef void *queueElementT;
typedef struct queueCDT *queueADT;

queueADT NewQueue(void);
void FreeQueue(queueADT queue);

void Enqueue(queueADT queue, queueElementT element);
queueElementT Dequeue(queueADT queue);

bool QueueIsEmpty(queueADT queue);
bool QueueIsFull(queueADT queue);

int QueueLength(queueADT queue);

queueElementT GetQueueElement(queueADT queue, int index);

#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

#include "queue.h"

#define MaxQueueSize 100
#define QueueArraySize (MaxQueueSize+1)

struct queueCDT{
    queueElementT elements[QueueArraySize];
    int head;
    int tail;
};

queueADT NewQueue(void){
    queueADT queue;
    queue = malloc(sizeof (*queue));
    queue->head = queue->tail = 0;
    return (queue);
}
void FreeQueue(queueADT queue){
    free(queue);
}

void Enqueue(queueADT queue, queueElementT element){
    int tail;
    if(!QueueIsFull(queue)){
        queue->elements[tail] = element;
        queue->tail = (queue->tail + 1) % QueueArraySize;
    }
}
queueElementT Dequeue(queueADT queue){
    queueElementT element;
    if(!QueueIsEmpty(queue)){
        element = queue->elements[queue->head];
        queue->head = (queue->head + 1) % QueueArraySize;
        return (element);
    }
}

bool QueueIsEmpty(queueADT queue){
    return (queue->head == queue->tail);
}
bool QueueIsFull(queueADT queue){
    return ((queue->tail+1)%QueueArraySize == queue->head);
}

int QueueLength(queueADT queue){
    return ((queue->tail - queue->head + QueueArraySize) % QueueArraySize);
}

queueElementT GetQueueElement(queueADT queue, int index){
    if(index>=0 && index<QueueLength(queue)){
        return (queue->elements[(queue->head + index) % QueueArraySize]);
    }
}

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 "queue.h"

typedef struct cellT{
    queueElementT element;
    struct cellT *link;
} cellT;

struct queueCDT{
    cellT *head;
    cellT *tail;
};

queueADT NewQueue(void){
    queueADT queue;
    queue = malloc(sizeof (*queue));
    queue->head = NULL;
    return queue;
}
void FreeQueue(queueADT queue){
    cellT *cp, *next;
    cp = queue->head;
    while(cp != NULL){
        next = cp->link;
        free(cp);
        cp = next;
    }
    free(queue);
}

void Enqueue(queueADT queue, queueElementT element){
    cellT *cp;
    cp = malloc(sizeof (*cp));
    cp->element = element;
    cp->link = NULL;
    if(queue->head == NULL){
        queue->head = cp;
    }
    else{
        queue->tail->link = cp;
    }
    queue->tail = cp;
}
queueElementT Dequeue(queueADT queue){
    cellT *cp;
    queueElementT element;
    if(!QueueIsEmpty(queue)){
        cp = queue->head;
        element = cp->element;
        queue->head = cp->link;
        free(cp);
        return (element);
    }
}

bool QueueIsEmpty(queueADT queue){
    return (queue->head == NULL);
}
bool QueueIsFull(queueADT queue){
    return (false);
}

int QueueLength(queueADT queue){
    int n;
    cellT *cp;
    for(n=0,cp=queue->head; cp!=NULL; cp=cp->link){
        n++;
    }
    return (n);
}

queueElementT GetQueueElement(queueADT queue, int index){
    int i;
    cellT *cp;
    if(index>=0 && index<QueueLength(queue)){
        cp = queue->head;
        for(i=1; i<index; i++){
            cp = cp->link;
        }
        return (cp->element);
    }
}