DataStructureHomework3

题目

假设以块链结构（blocked linked）表示串，试编写将串 s 插入到串 t 中某个字符之后的算法，若该字符不存在，则将串 s 联接在串 t 之后。

分析

定义结构

1
2
3
4
5
typedef struct block *PTNode;
struct block {
    char character[SIZE];
    PTNode next;
};

其中，本例常量定义为

1
#define SIZE 5

图示如下

写入

采用两个函数 WriteInList 和 WriteInBlock, 用flag来表示块是否写满

1
2
3
4
5
6
7
8
9
10
void WriteInList(PTNode pHead) {
    int flag = 1;
    while (flag) {
        PTNode pLast = pHead;
        while (pLast->next != NULL) {
            pLast = pLast->next;
        }
        flag = WriteInBlock(pLast);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int WriteInBlock(PTNode pLast) {
    PTNode pNew;
    pNew = (PTNode) malloc(sizeof(struct block));
    if (pNew == NULL) {
        printf("Memory allocation failed!");
        exit(1);
    }
    for (int i = 0; i < SIZE; i++) {
        pNew->character[i] = getchar();
        if (pNew->character[i] == '\n') {
            for (int j = i; j < SIZE; j++) {
                pNew->character[j] = '\0';
            }
            pLast->next = pNew;
            pNew->next = NULL;
            return 0;
        }
    }
    pLast->next = pNew;
    pNew->next = NULL;
    return 1;
}

输出（打印）表

character[i] == 1 表示该块中字符并未写满，但为提高后续串的连接、插入操作效率，将1(pass)作为标识符，输出读取到1时继续但不输出。

整体上输出遵循由块到块，逐个字符输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void PrintList(PTNode pHead) {
    PTNode p = pHead->next;
    while (p != NULL) {
        for (int i = 0; i < SIZE; i++) {
            if (p->character[i] == '\0') {
                printf("\n");
                break;
            }
            else if (p->character[i] == 1) {
                continue;
            }
            else {
                printf("%c", p->character[i]);
            }
        }
        p = p->next;
    }
}

插入操作

查找目标字符id

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void InsertList(PTNode s, PTNode t, char id) {
    //serach the id in the list s
    PTNode temp = NULL;
    int isfoundinblock = 0;
    while (s->next != NULL) {
        //loop over block
        for (int i = 0; i < SIZE; i++) {
            //is found id in block
            if (s->character[i] == id) {
                isfoundinblock = 1;
            }
            //not found id in block
            else {
                continue;
            }
        }
        if (isfoundinblock == 1) {
            break;
        }
        //search next block
        s = s->next;
    }
}

查询到id的后续操作

首先将同个block中id后的字符复制到buffer中，然后把该位置的字符定义为1(pass)

1
2
3
4
5
6
isfoundinblock = 1;
//copy remain of block to buffer
for (int j = i + 1; j < SIZE; j++) {
    buffer->character[j - i - 1] = s->character[j];
    s->character[j] = 1;
}

将s串指向t串，s串后半部分位置储存到temp

1
2
3
//relocation of pointers
temp = s->next;
s->next = t->next;

将t串最后一个block后缀改为1(pass)

1
2
3
4
5
6
7
8
9
10
//t tail of block set 1
while (t->next != NULL) {
    t = t->next;
}
for (int j = 0; j < SIZE; j++) {
    if (t->character[j] != '\0') {
        continue;
    }
    t->character[j] = 1;
}

将t串末尾指向buffer，将buffer指向temp

1
2
3
//relocation of pointers
t->next = buffer;
buffer->next = temp;

图示

特别的，当id为某个block末位字符时，代码相同，图示如下：

未查询到id的后续操作

将s串最后一个block后缀改为1(pass),并将s串指向t串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
while (s->next != NULL) {
    ...
}
if (isfoundinblock == 0) {
        //s tail of block set 1
        while (s->next != NULL) {
            s = s->next;
        }
        for (int j = 0; j < SIZE; j++) {
            if (s->character[j] != '\0') {
                continue;
            }
            s->character[j] = 1;
        }
        //relocation of pointers
        s->next = t->next;
    }

图示

输入及输出

输入：共三行，分别为s串、t串、id字符

输出：共四行，分别是id字符、s串、t串、结果

测试结果

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
>>>input
abcdefg
111
c
<<<output
id:	c
s :	abcdefg
t :	111
op:	abc111defg
---
>>>input
abcdefg
111
e
<<<output
id:	e
s :	abcdefg
t :	111
op:	abcde111fg
---
>>>input
abcdefg
111
z
<<<output
id:	z
s :	abcdefg
t :	111
op:	abcdefg111
---
>>>input
abcdefghij
111222
i
<<<output
id:	i
s :	abcdefghij
t :	111222
op:	abcdefghi111222j
---
>>>input
abcde
11111
a
<<<output
id:	a
s :	abcde
t :	11111
op:	a11111bcde
---

代码

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

#define SIZE 5
char id;
typedef struct block *PTNode;
struct block {
    char character[SIZE];
    PTNode next;
};
PTNode buffer = NULL;

int WriteInBlock(PTNode);

void WriteInList(PTNode);

void PrintList(PTNode);

void InsertList(PTNode, PTNode, char);

int main() {
    PTNode heads = (PTNode) malloc(sizeof(struct block));
    PTNode headt = (PTNode) malloc(sizeof(struct block));
    buffer = (PTNode) malloc(sizeof(struct block));
    for (int i = 0; i < SIZE; i++) {
        heads->character[i] = '\0';
        headt->character[i] = '\0';
        buffer->character[i] = 1;
    }
    heads->next = NULL;
    headt->next = NULL;
    buffer->next = NULL;
    WriteInList(heads);
    WriteInList(headt);

    id = getchar();

    PTNode headop = heads;
    printf("id:\t%c\n", id);
    printf("s :\t");
    PrintList(heads);
    printf("t :\t");
    PrintList(headt);

    InsertList(heads, headt, id);

    printf("op:\t");
    PrintList(headop);
    return 0;
}

int WriteInBlock(PTNode pLast) {
    PTNode pNew;
    pNew = (PTNode) malloc(sizeof(struct block));
    if (pNew == NULL) {
        printf("Memory allocation failed!");
        exit(1);
    }
    for (int i = 0; i < SIZE; i++) {
        pNew->character[i] = getchar();
        if (pNew->character[i] == '\n') {
            for (int j = i; j < SIZE; j++) {
                pNew->character[j] = '\0';
            }
            pLast->next = pNew;
            pNew->next = NULL;
            return 0;
        }
    }
    pLast->next = pNew;
    pNew->next = NULL;
    return 1;
}

void WriteInList(PTNode pHead) {
    int flag = 1;
    while (flag) {
        PTNode pLast = pHead;
        while (pLast->next != NULL) {
            pLast = pLast->next;
        }
        flag = WriteInBlock(pLast);
    }
}

void PrintList(PTNode pHead) {
    PTNode p = pHead->next;
    while (p != NULL) {
        for (int i = 0; i < SIZE; i++) {
            if (p->character[i] == '\0') {
                printf("\n");
                break;
            }
            else if (p->character[i] == 1) {
                continue;
            }
            else {
                printf("%c", p->character[i]);
            }
        }
        p = p->next;
    }
}

void InsertList(PTNode s, PTNode t, char id) {
    //serach the id in the list s
    PTNode temp = NULL;
    int isfoundinblock = 0;
    while (s->next != NULL) {

        //loop over block
        for (int i = 0; i < SIZE; i++) {
            //is found id in block
            if (s->character[i] == id) {
                isfoundinblock = 1;
                //copy remain of block to buffer
                for (int j = i + 1; j < SIZE; j++) {
                    buffer->character[j - i - 1] = s->character[j];
                    s->character[j] = 1;
                }
                //relocation of pointers
                temp = s->next;
                s->next = t->next;
                //t tail of block set 1
                while (t->next != NULL) {
                    t = t->next;
                }
                for (int j = 0; j < SIZE; j++) {
                    if (t->character[j] != '\0') {
                        continue;
                    }
                    t->character[j] = 1;
                }

                //relocation of pointers
                t->next = buffer;
                buffer->next = temp;
            }
                //not found id in block
            else {
                continue;
            }
        }
        if (isfoundinblock == 1) {
            break;
        }
        //search next block
        s = s->next;
    }
    if (isfoundinblock == 0) {
        //s tail of block set 1
        while (s->next != NULL) {
            s = s->next;
        }
        for (int j = 0; j < SIZE; j++) {
            if (s->character[j] != '\0') {
                continue;
            }
            s->character[j] = 1;
        }
        //relocation of pointers
        s->next = t->next;
    }
}