QST2's BLOG

Version: WwJ

0%

编译原理 Lab1

Posted on In

编译原理 Lab1

课程代码也发一下吧；

环境配置

一看测试程序的 python 源码头：

1
2
#!/usr/bin/env python3
# encoding: utf-8

linux 环境，干脆弄个 docker 隔离一下：

Dockerfile

1
2
3
4
5
6
7
8
FROM python:3.13-rc-bookworm

LABEL name="compilation-principle"
LABEL version="1.0"

WORKDIR /apps
# to make sure the container never stop itself
CMD ["tail", "-f", "/dev/null"]

用 docker 构建环境：

1
2
3
4
docker build ./ --tag compilation-principal-labs
# 6ff7ff597e6d6da7e432e0672cb21c2b7e3dcb85d0cd3858e9b5ea39edf2c4b6
docker run -d --name cp-labs-env -v C:/Users/Westj/Desktop/semester5/240900CompilingPrincipal/Labs/vol:/apps 6ff
# d378173aa930f0d1278a67a5e372adebab9d889da3d933bd3801ae753f02dbfb

bash 与 docker 交互：

1
2
docker exec -it d37 /bin/bash
# root@d378173aa930:/apps#

Lab1

1
// 1. You will complete the following functions (declared in header file) in the linked_list.c file!

完成链表定义即可；

源码

linked_list.h

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

typedef struct node {
    union {
        int count;
        int value;
    };
    struct node *next;
} node;

/* initialize a linked list, head node is special */
node *linked_list_init();

/* destroy a linked list, free spaces */
void linked_list_free(node *head);

/* display elements in the linked list */
char *linked_list_tostring(node *head);

/* get the length of the linked list */
int linked_list_size(node *head);

/* insert val at the last of the linked list */
void linked_list_append(node *head, int val);

/*
 * You should implement functions according to the follow function
 * declarations. One thing to note that, the parameter *index*
 * refers to the position of value node, i.e., index 0 corresponds
 * to the next node of the header node.
 *
 * In case of out-of-bound index, your code should do nothing in all
 * functions. As for remove, if the value doesn't exist, do nothing.
 *
 * For get, if index out of bound, return INT_MIN.
 * For search, if value not exists. return -1.
 * For search_all, if value not exists, return empty list.
 */

/* insert val at position index */
void linked_list_insert(node *head, int val, int index);

/* delete node at position index */
void linked_list_delete(node *head, int index);

/* remove the first occurence node of val */
void linked_list_remove(node *head, int val);

/* remove all occurences of val */
void linked_list_remove_all(node *head, int val);

/* get value at position index */
int linked_list_get(node *head, int index);

/* search the first index of val */
int linked_list_search(node *head, int val);

/* search all indexes of val */
node *linked_list_search_all(node *head, int val);

linked_list.c

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

node *linked_list_init()
{
    node *head = (node *)malloc(sizeof(node));
    head->count = 0;
    head->next = NULL;
    return head;
}

void linked_list_free(node *head)
{
    node *cur = head;
    node *last;
    while (cur != NULL)
    {
        last = cur;
        cur = cur->next;
        free(last);
    }
}

char linked_list_string[0x10000];

char *linked_list_tostring(node *head)
{
    node *cur = head->next;
    char *position;
    int length = 0;
    while (cur != NULL)
    {
        position = linked_list_string + length;
        length += sprintf(position, "%d", cur->value);
        cur = cur->next;
        if (cur != NULL)
        {
            position = linked_list_string + length;
            length += sprintf(position, "->");
        }
    }
    position = linked_list_string + length;
    length += sprintf(position, "%c", '\0');
    return linked_list_string;
}

int linked_list_size(node *head)
{
    return head->count;
}

void linked_list_append(node *head, int val)
{
    node *cur = head;
    node *new_node;
    while (cur->next != NULL)
    {
        cur = cur->next;
    }
    new_node = (node *)malloc(sizeof(node));
    new_node->value = val;
    new_node->next = NULL;
    cur->next = new_node;
    head->count++;
}

/* your implementation goes here */

void linked_list_insert(node *head, int val, int index)
{
    node *cur = head;
    if (index > head->count || index < 0)
    {
        // do nothing
    }
    else
    {
        node *new_node = (node *)malloc(sizeof(node));
        new_node->value = val;
        for (int i = 0; i < index; i++)
        {
            cur = cur->next;
        }
        new_node->next = cur->next;
        cur->next = new_node;
        head->count++;
    }
}

void linked_list_delete(node *head, int index)
{
    node *cur = head;
    if (index >= head->count || index < 0)
    {
        // do nothing
    }
    else
    {
        for (int i = 0; i < index; i++)
        {
            cur = cur->next;
        }
        node *delete_node = cur->next;
        cur->next = cur->next->next;
        // free delete_node
        free(delete_node);
        head->count--;
    }
}

void linked_list_remove(node *head, int val)
{
    node *cur = head;
    while (cur->next != NULL)
    {
        if (cur->next->value == val)
        {
            node *remove_node = cur->next;
            cur->next = cur->next->next;
            free(remove_node);
            head->count--;
            return;
        }
        cur = cur->next;
    }
}

void linked_list_remove_all(node *head, int val)
{
    node *cur = head;
    while (cur->next != NULL)
    {
        while (cur->next->value == val)
        {
            node *remove_node = cur->next;
            cur->next = cur->next->next;
            free(remove_node);
            head->count--;
        }
        cur = cur->next;
    }
}

int linked_list_get(node *head, int index)
{
    node *cur = head;
    if (index >= head->count || index < 0)
    {
        return INT_MIN;
    }
    else
    {
        for (int i = 0; i < index; i++)
        {
            cur = cur->next;
        }
        return cur->next->value;
    }
}

int linked_list_search(node *head, int val)
{
    node *cur = head;
    for (int i = 0; i < head->count; i++)
    {
        if (cur->next->value == val)
        {
            return i;
        }
        cur = cur->next;
    }
    return -1;
}

node *linked_list_search_all(node *head, int val)
{

    node *search_list = linked_list_init();
    node *cur = head;
    for (int i = 0; i < head->count; i++)
    {
        if (cur->next->value == val)
        {
            linked_list_append(search_list, i);
        }
        cur = cur->next;
    }
    return search_list;
}

目录结构

./vol : /apps

编译操作

cd lab1 进入映射的 apps/lab1 ，make libll 编译 libll.so：

编译成功输出，运行测试程序：

测试通过；

车子

红拂夜奔；

他碰上了一件倒霉的事儿，昨天一个不小心，被洛阳留守大尉杨素看上了，要收他做一名东床快婿。这可不是闹着玩儿的。这个东床比太平间还厉害，躺上去就是死人啦！

跨年孤勇者；

你破旧的玩偶 你的 面具 你的自我

华北浪漫革命；

我面无表情 装作很冷静

去营造那不存在的暖风

脚下却只能踩着水坑

霍乱时期的毕业；

我为你保留了童贞可不是一场梦

我原以为什么，但什么，什么，什么，反倒显得什么什么了。