Icoding其他题解——数据结构
我只能说剩下的题都挺抽象，不是很愿意花时间为它们写题解了，因此将答案都放在这里，需要的自取吧。
字符串
块链串
逆天题。
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
| bool blstr_substr(BLString src, int pos, int len, BLString *sub) {
if(pos < 0 || pos >= src.len || len <= 0 || sub == NULL)
return false;
sub->head = (Block*)malloc(sizeof(Block));
if(sub->head == NULL)
return false;
Block* sub_ptr = sub->head;
Block* src_ptr = src.head;
int char_index = 0;
int src_block_index = 0;
int sub_block_index = 0;
while(char_index < pos + len && src_ptr != NULL && src_ptr->ch[src_block_index] != BLS_BLANK)
{
if (char_index < pos)
{
if(src_block_index < BLOCK_SIZE - 1)
src_block_index++;
else
{
src_ptr = src_ptr->next;
src_block_index = 0;
}
char_index++;
}
else
{
sub_ptr->ch[sub_block_index] = src_ptr->ch[src_block_index];
if(src_block_index < BLOCK_SIZE - 1)
src_block_index++;
else
{
src_ptr = src_ptr->next;
src_block_index = 0;
}
if(sub_block_index < BLOCK_SIZE - 1)
sub_block_index++;
else
{
sub_ptr->next = (Block*)malloc(sizeof(Block));
sub_ptr = sub_ptr->next;
sub_ptr->next = NULL;
sub_block_index = 0;
}
char_index ++;
sub->len ++;
}
}
if(sub_block_index != 0)
{
sub->tail = sub_ptr;
while(sub_block_index < BLOCK_SIZE)
{
sub_ptr->ch[sub_block_index] = BLS_BLANK;
sub_block_index++;
}
}
else
{
sub->tail = sub->head;
while(sub->tail->next != sub_ptr)
{
sub->tail = sub->tail->next;
if(sub->tail == NULL)
return false;
}
sub->tail->next = NULL;
free(sub_ptr);
}
return true;
}
|
串替换
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
| int pos_len(const char *str, int pos)
{
int num = 0;
for(int i = pos; str[i] != '\0'; i++)
num++;
return num;
}
int str_replace(const char *in, char *out, int outlen, const char *oldstr, const char *newstr){
int replace_count = 0;
int out_index = 0;
int newstr_len = pos_len(newstr, 0);
for(int i = 0; i < outlen;i++)
out[i] = '\0';
int in_index = 0;
while(in_index < outlen)
{
int oldstr_index = 0;
while(oldstr[oldstr_index] != '\0')
{
if(oldstr[oldstr_index] != in[in_index])
{
in_index = in_index - oldstr_index + 1;
break;
}
in_index++;
oldstr_index++;
}
if(oldstr[oldstr_index] != '\0')
{
out[out_index] = in[in_index - 1];
out_index++;
}
else
{
int current_len = pos_len(out, 0) + pos_len(in, in_index) + newstr_len;
if (current_len < outlen)
{
for(int i = 0; newstr[i] != '\0'; i++)
{
out[out_index] = newstr[i];
out_index++;
}
replace_count++;
}
else
{
while(oldstr_index != 0)
{
out[out_index] = in[in_index - oldstr_index];
out_index++;
oldstr_index--;
}
}
}
if(in[in_index] == '\0')
{
out_index++;
break;
}
}
return replace_count;
}
|
串比较
还算比较有人性。
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
| int str_compare(const char* ptr1, const char* ptr2){
int cmp_value = 0;
int i = 0;
while(1)
{
if(ptr1[i] == '\0' && ptr2[i] == '\0')
break;
if(ptr1[i] == '\0' && ptr2[i] != '\0')
{
cmp_value = -ptr2[i];
break;
}
if(ptr1[i] != '\0' && ptr2[i] == '\0')
{
cmp_value = ptr1[i];
break;
}
if(ptr1[i] != ptr2[i])
{
if(ptr1[i] + 'a' - 'A' == ptr2[i] || ptr2[i] + 'a' - 'A' == ptr1[i]);
else
{
cmp_value = ptr1[i] - ptr2[i];
break;
}
}
i++;
}
return cmp_value;
}
|
图的存储
邻接矩阵
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
| bool matrix_insert_vertex(MatrixGraph *G, VertexType v){
if(G == NULL)
return false;
if(G->vexnum == MAX_VERTEX_NUM)
return false;
int new_vex_index = matrix_locate_vertex(G, v);
if(new_vex_index != -1)
return false;
G->vexnum++;
new_vex_index = G->vexnum - 1;
G->vertex[new_vex_index] = v;
for(int i = 0; i < MAX_VERTEX_NUM; i++)
{
G->arcs[i][new_vex_index] = 0;
G->arcs[new_vex_index][i] = 0;
}
return true;
}
bool matrix_insert_arc(MatrixGraph *G, VertexType v, VertexType w){
if(G == NULL)
return false;
int vex_index_v = matrix_locate_vertex(G, v);
int vex_index_w = matrix_locate_vertex(G, w);
if(vex_index_v == -1 || vex_index_w == -1)
return false;
if(G->type == DG)
{
if(G->arcs[vex_index_v][vex_index_w] == -1)
G->arcs[vex_index_v][vex_index_w] = 1;
else
return false;
}
else
{
if(G->arcs[vex_index_v][vex_index_w] == -1)
G->arcs[vex_index_v][vex_index_w] = 1;
else
return false;
if(G->arcs[vex_index_w][vex_index_v] == -1)
G->arcs[vex_index_w][vex_index_v] = 1;
else
return false;
}
G->arcnum++;
return true;
}
|
邻接表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
| bool insert_vertex(ListGraph *G, VertexType v){
if(G == NULL)
return false;
int new_ver_index = locate_vertex(G, v);
if(new_ver_index != -1)
return false;
G->vexnum++;
new_ver_index = G->vexnum - 1;
G->vertex[new_ver_index].data = v;
G->vertex[new_ver_index].firstarc = NULL;
return true;
}
bool insert_arc(ListGraph *G, VertexType v, VertexType w){
if(G == NULL)
return false;
int v_index = locate_vertex(G, v);
int w_index = locate_vertex(G, w);
if(v_index == -1 || w_index == -1)
return false;
ArcNode *curr = G->vertex[v_index].firstarc;
ArcNode *prev = curr;
while(curr != NULL)
{
if(curr->adjvex == w_index)
return false;
prev = curr;
curr = curr->nextarc;
}
ArcNode* temp = (ArcNode*)malloc(sizeof(ArcNode));
if(temp == NULL) return false;
temp->adjvex = w_index;
temp->nextarc = NULL;
if(prev == curr)
G->vertex[v_index].firstarc = temp;
else
prev->nextarc = temp;
if(G->type == UDG)
{
ArcNode *curr1 = G->vertex[w_index].firstarc;
ArcNode *prev1 = curr1;
while(curr1 != NULL)
{
if(curr1->adjvex == v_index)
return false;
prev1 = curr1;
curr1 = curr1->nextarc;
}
ArcNode *temp1 = (ArcNode*)malloc(sizeof(ArcNode));
if(temp1 == NULL) return false;
temp1->adjvex = v_index;
temp1->nextarc = NULL;
if(curr1 == prev1)
G->vertex[w_index].firstarc = temp1;
else
prev1->nextarc = temp1;
}
G->arcnum ++;
return true;
}
|
邻接表2
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
| bool del_vertex(ListGraph *G, VertexType v){
if(G == NULL)
return false;
int v_index = locate_vertex(G, v);
if(v_index == -1)
return false;
ArcNode *curr = G->vertex[v_index].firstarc;
ArcNode *prev = curr;
while(curr != NULL)
{
prev = curr;
curr = curr->nextarc;
G->vertex[v_index].firstarc = curr;
free(prev);
G->arcnum--;
}
for(int i = v_index; i < G->vexnum; i++)
G->vertex[i] = G->vertex[i + 1];
G->vexnum--;
ArcNode *cur = NULL;
for(int i = 0; i < G->vexnum; i++)
{
cur = G->vertex[i].firstarc;
while(cur != NULL)
{
if(cur->adjvex > v_index)
{
cur->adjvex--;
cur = cur->nextarc;
}
else if(cur->adjvex == v_index)
{
ArcNode *del = cur;
if(G->vertex[i].firstarc == cur)
{
G->vertex[i].firstarc = cur->nextarc;
cur = cur->nextarc;
free(del);
}
else
{
ArcNode *pre = G->vertex[i].firstarc;
while(pre->nextarc != cur)
pre = pre->nextarc;
pre->nextarc = cur->nextarc;
cur = cur->nextarc;
free(del);
}
G->arcnum--;
}
else
cur = cur->nextarc;
}
}
return true;
}
|
数组广义表
十字链表
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
| int init_cross_list(PCrossList L, const ElemType *A, int m,int n){
L->rows = m;
L->cols = n;
L->nums = 0;
L->rowhead = (OLink*)malloc(sizeof(OLink) * (m + 1));
if(L->rowhead == NULL) exit(0);
for(int i = 0; i < m + 1; i++)
L->rowhead[i] = NULL;
L->colhead = (OLink*)malloc(sizeof(OLink) * (n + 1));
if(L->colhead == NULL) exit(0);
for(int i = 0; i < n + 1; i++)
L->colhead[i] = NULL;
OLink pRow = NULL;
OLink pCol = NULL;
for(int i = 0; i < m * n ; i ++)
{
if(A[i] == 0)
continue;
int rrow = i / n + 1;
int ccol = i % n + 1;
OLink curr = (OLink)malloc(sizeof(OLNode));
if (curr == NULL) exit(0);
curr->down = NULL;
curr->right = NULL;
curr->row = i / n + 1;
curr->col = i % n + 1;
curr->value = A[i];
L->nums++;
if(i % n == 0)
pRow = L->rowhead[rrow];
if(L->rowhead[rrow] == NULL)
{
L->rowhead[rrow] = curr;
curr->right = NULL;
pRow = curr;
}
else
{
while(pRow->right != NULL)
pRow = pRow->right;
pRow->right = curr;
curr->right = NULL;
pRow = curr;
}
pCol = L->colhead[ccol];
if(L->colhead[ccol] == NULL)
{
L->colhead[ccol] = curr;
curr->down = NULL;
pCol = curr;
}
else
{
while(pCol->down != NULL)
pCol = pCol->down;
pCol->down = curr;
curr->down = NULL;
pCol = curr;
}
}
return L->nums;
}
|
矩阵加法
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
| bool add_matrix(const TSMatrix *pM, const TSMatrix *pN, TSMatrix *pQ){
if(pM->m != pN->m || pM->n != pN->n)
return false;
pQ->m = pM->m;
pQ->n = pM->n;
int DataPosition = 0;
int m = 0;
int n = 0;
int judge = -1;
while(1)
{
if(m == pM->len && n == pN->len)
break;
if(m == pM->len)
judge = 1;
else if(n == pN->len)
judge = 2;
else
{
if(pN->data[n].i < pM->data[m].i)
judge = 1;
else if(pN->data[n].i == pM->data[m].i)
{
if(pN->data[n].j < pM->data[m].j)
judge = 1;
else if (pN->data[n].j > pM->data[m].j)
judge = 2;
else
judge = 0;
}
else
judge = 2;
}
switch (judge)
{
case 1:
pQ->data[DataPosition].i = pN->data[n].i;
pQ->data[DataPosition].j = pN->data[n].j;
pQ->data[DataPosition].e = pN->data[n].e;
n++;
DataPosition++;
break;
case 2:
pQ->data[DataPosition].i = pM->data[m].i;
pQ->data[DataPosition].j = pM->data[m].j;
pQ->data[DataPosition].e = pM->data[m].e;
m++;
DataPosition++;
break;
case 0:
pQ->data[DataPosition].i = pM->data[m].i;
pQ->data[DataPosition].j = pM->data[m].j;
pQ->data[DataPosition].e = pM->data[m].e + pN->data[n].e;
DataPosition++;
m++;
n++;
break;
default:
return false;
break;
}
}
pQ->len = DataPosition;
for(int q = 0; q < pQ->len; q++)
{
if(pQ->data[q].e == 0)
{
for(int k = q; k < pQ->len ; k ++)
pQ->data[k] = pQ->data[k+1];
q--;
pQ->len--;
}
}
return true;
}
|
查找
AVL
家人们谁懂啊，下头题。
有一说一AVL树建议去看大黑书，《数据结构与算法分析：C语言描述》，你会感到非常通透。
可以参考这篇博客.
里面有AVL树的详细实现，就是看着大黑书敲出来的。
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
| int Height(node_t* root)
{
if(root == NULL)
return 0;
else
return root->height;
}
int Max(int a, int b)
{
return a > b ? a : b;
}
node_t* SingleRotateWithLeft(node_t* T)
{
node_t* next_root;
next_root = T->left;
T->left = next_root->right;
next_root->right = T;
T->height = Max(Height(T->left), Height(T->right)) + 1;
next_root->height = Max(Height(next_root->left), Height(next_root->right)) + 1;
return next_root;
}
node_t* SingleRotateWithRight(node_t* T)
{
node_t *next_root = T->right;
T->right = next_root->left;
next_root->left = T;
T->height = Max(Height(T->left), Height(T->right)) + 1;
next_root->height = Max(Height(next_root->left), Height(next_root->right)) + 1;
return next_root;
}
node_t* DoubleRotateWithLeft(node_t* T)
{
T->left = SingleRotateWithRight(T->left);
return SingleRotateWithLeft(T);
}
node_t* DoubleRotateWithRight(node_t* T)
{
T->right = SingleRotateWithLeft(T->right);
return SingleRotateWithRight(T);
}
node_t* avl_insert(node_t *root, int val){
if(root == NULL)
{
root = (node_t*)malloc(sizeof(node_t));
if(root == NULL)
exit(0);
root->left = root->right = root->parent = NULL;
root->height = 1;
root->val = val;
}
else if(val <= root->val)
{
root->left = avl_insert(root->left, val);
if(root->left != NULL)
root->left->parent = root;
if( Height(root->left) - Height(root->right) > 1)
{
if(val < root->left->val)
root = SingleRotateWithLeft(root);
else
root = DoubleRotateWithLeft(root);
}
}
else if(val >= root->val)
{
root->right = avl_insert(root->right, val);
if(root->right != NULL)
root->right->parent = root;
if( Height(root->right) - Height(root->left) > 1 )
{
if(val > root->right->val)
root = SingleRotateWithRight(root);
else
root = DoubleRotateWithRight(root);
}
}
root->height = Max(Height(root->left), Height(root->right)) + 1;
return root;
}
|
哈希表创建
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| HashTable* create_hash(int size){
if (size <= 0)
return NULL;
HashTable* hashtbl = (HashTable*)malloc(sizeof(HashTable));
if (hashtbl == NULL)
return NULL;
hashtbl->size = size;
hashtbl->bucket = (HashEntry**)malloc(size * sizeof(HashEntry*));
hashtbl->last_error = HASH_OK;
if(hashtbl->bucket == NULL)
{
free(hashtbl);
return NULL;
}
memset(hashtbl->bucket, 0, size * sizeof(HashEntry*));
return hashtbl;
}
|
哈希表添加
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
| HASH_RESULT hash_add_int(HashTable *table, const char *key, int value ){
long hash = hash_string(key);
int index = hash % table->size;
HashEntry *curr = table->bucket[index];
HashEntry *prev = curr;
while(curr != NULL)
{
if(strcmp(key, curr->key.str_value) == 0)
{
if(value == curr->value.int_value)
return HASH_ALREADY_ADDED;
else
{
curr->value.int_value = value;
return HASH_REPLACED_VALUE;
}
}
prev = curr;
curr = curr->next;
}
HashEntry *new_entry = (HashEntry*)malloc(sizeof(HashEntry));
if(new_entry == NULL)
return HASH_ERROR;
new_entry->key.str_value = (char*)malloc(sizeof(char) * (strlen(key) + 1));
if(new_entry->key.str_value == NULL)
{
free(new_entry);
return HASH_ERROR;
}
strcpy(new_entry->key.str_value, key);
new_entry->value.int_value = value;
new_entry->next = table->bucket[index];
table->bucket[index] = new_entry;
return HASH_ADDED;
}
|