Try โ€‚โ€‰HackMD

2020q3 Homework1 (lab0)

contributed by < kevin30292 >
code GitHub

function ๅŠŸ่ƒฝ

queue.c ๅƒ…ๆไพ›ไป‹้ขไฝ†ๅฐšๆœชๆœ‰ๅฎŒๆ•ด็จ‹ๅผๅฏฆไฝœ๏ผŒ้œ€่ฆ่ฃœๅฎŒไธฆ้€ๆญฅ็ฒพ้€ฒ๏ผŒๅŒ…ๅซไปฅไธ‹๏ผš

  1. q_new: ๅปบ็ซ‹ๆ–ฐ็š„ใ€Œ็ฉบใ€ไฝ‡ๅˆ—;
  2. q_free: ้‡‹ๆ”พไฝ‡ๅˆ—ๆ‰€ไฝ”็”จ็š„่จ˜ๆ†ถ้ซ”;
  3. q_insert_head: ๅœจไฝ‡ๅˆ—้–‹้ ญ (head) ๅŠ ๅ…ฅ (insert) ็ตฆๅฎš็š„ๆ–ฐๅ…ƒ็ด  (ไปฅ LIFO ๆบ–ๅ‰‡);
  4. q_insert_tail: ๅœจไฝ‡ๅˆ—ๅฐพ็ซฏ (tail) ๅŠ ๅ…ฅ (insert) ็ตฆๅฎš็š„ๆ–ฐๅ…ƒ็ด  (ไปฅ FIFO ๆบ–ๅ‰‡);
  5. q_remove_head: ๅœจไฝ‡ๅˆ—้–‹้ ญ (head) ็งป้™ค (remove) ็ตฆๅฎš็š„ๅ…ƒ็ด ใ€‚
  6. q_size: ่จˆ็ฎ—ไฝ‡ๅˆ—ไธญ็š„ๅ…ƒ็ด ๆ•ธ้‡ใ€‚
  7. q_reverse: ไปฅๅๅ‘้ †ๅบ้‡ๆ–ฐๆŽ’ๅˆ—้ˆ็ตไธฒๅˆ—๏ผŒ่ฉฒๅ‡ฝๅผไธ่ฉฒ้…็ฝฎๆˆ–้‡‹ๆ”พไปปไฝ•้ˆ็ตไธฒๅˆ—ๅ…ƒ็ด ๏ผŒๆ›่จ€ไน‹๏ผŒๅฎƒๅช่ƒฝ้‡ๆŽ’ๅทฒ็ถ“ๅญ˜ๅœจ็š„ๅ…ƒ็ด ;
  8. q_sort: ใ€Œ้€ฒ้šŽ้›ป่…ฆ็ณป็ตฑ็†่ซ–่ˆ‡ๅฏฆไฝœใ€่ชฒ็จ‹ๆ‰€ๆ–ฐๅขž๏ผŒไปฅ้žๅขž้ †ๅบไพ†ๆŽ’ๅบ้ˆ็ตไธฒๅˆ—็š„ๅ…ƒ็ด ๏ผŒๅฏๅƒ้–ฑ Linked List Sort ๅพ—็Ÿฅๅฏฆไฝœๆ‰‹ๆณ•

้–‹็™ผ็ด€้Œ„

q_size

็”ฑๆ–ผ่ฆๅœจ O(1) ็š„ๅธธๆ•ธๆ™‚้–“ๅ…งๅŸท่กŒๅฎŒๆˆ๏ผŒๆ‰€ไปฅไนŸไธๅฏ่ƒฝ่ตฐ่จชๆ•ดๅ€‹้ˆ็ตไธฒๅˆ—๏ผŒไปฅๅ–ๅพ—ไฝ‡ๅˆ—็š„ๅฎน็ฉใ€‚
ๆ–ฐๅขž size ๅ€ผ็ด€้Œ„ queue ็š„ๅคงๅฐ๏ผŒๅˆๆ็คบ

Return 0 if q is NULL or empty





int q_size(queue_t *q)
{
    return (q == NULL) ? 0 q->size
}

new_q

TODO: What if malloc returned NULL?

malloc ๅ›žๅ‚ณ NULL ๅฏ่ƒฝ็‚บ่จ˜ๆ†ถ้ซ”ไธ่ถณ๏ผŒๅ› ๆญคๅคฑๆ•—ใ€‚
ๅŠ ๅ…ฅๆชขๆŸฅๆฉŸๅˆถ๏ผš





if(q == NULL){
            printf("Error! Allocation was failed. \n");
            return 1;
    }

q_free

้œ€้€ไธ€ free ๆ‰€ๆœ‰queueไธญ็š„ๅ€ผๅŠๅญ—ไธฒ














void q_free(queue_t *q)
{
    if (q != NULL) {
        list_ele_t *next;
        while (q->head != NULL) {
            next = q->head->next;
            free(q->head->value);
            free(q->head);
            q->head = next;
        }
        free(q);
    }
}

q_insert_head

็ฌฌ19่กŒ้œ€่ฆ free(newh) ๅ› ็‚บ็ฌฌ10่กŒ็š„ malloc ๅคฑๆ•—๏ผŒไฝ†็ฌฌ6่กŒ็š„mallocๆ˜ฏๆœ‰ๆˆๅŠŸ็š„































bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    if (q != NULL) {
        list_ele_t *newh;
        newh = malloc(sizeof(list_ele_t));
        if (newh != NULL) {
            int length;
            length = strlen(s);
            newh->value = malloc(length * sizeof(char));
            if (newh->value != NULL) {
                memcpy(newh->value, s, length);
                newh->next = q->head;
                q->head = newh;
                q->size++;
                return true;
            }
            else {
                free(newh);
                return false
            }
        }
        else {
            return false;
        }
    }
    else {
        return false;
    }
}

q_insert_tail

  • ่ฆๅœจ O(1) ็š„ๅธธๆ•ธๆ™‚้–“ๅ…งๅŸท่กŒๅฎŒๆˆ

ไธ่ƒฝๅพž head ๆ…ขๆ…ขๆ‰พ tail

ๅŠ ๅ…ฅ tail ๆ€ง่ณช
queue.h ๅŠ ๅ…ฅ๏ผš

list_ele_t *tail;

้œ€ไฟฎๆ”น code ไปฅ็ถญ่ญทๆญคๅƒๆ•ธ
new_q ๅŠ ๅ…ฅ๏ผš

q->tail = NULL;  // Add for the q_insert_tail

q_insert_head ๅŠ ๅ…ฅ๏ผš




if (q->size == 0) {
    q->tail = newh;
}

12-16่กŒ๏ผŒ้ฟๅ… head ็ผบๅคฑๆƒ…ๆณ
































bool q_insert_tail(queue_t *q, char *s)
{
    if (q != NULL) {
        list_ele_t *newt;
        newt = malloc(sizeof(list_ele_t));
        if (newt != NULL) {
            int length;
            length = strlen(s) + 1;
            newt->value = malloc(length * sizeof(char));
            if (newt->value != NULL) {
                memcpy(newt->value, s, length);
                if (q->size == 0) {
                    q->head = newt;
                } else {
                    q->tail->next = newt;
                }
                q->tail = newt;
                newt->next = NULL;
                q->size++;
                return true;
            } else {
                free(newt);
                return false;
            }
        } else {
            return false;
        }
    } else {
        return false;
    }
}

Debug

ๆธฌ่ฉฆๆ™‚็™ผ็พไบ‚็ขผๅŠ Segmentation fault

q = [gerbilโ–’โ–’โ–’ bearโ–’โ–’โ–’ dolphinโ–’โ–’โ–’]
cmd> # Now at the tail
cmd> it meerkat
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
make: *** [Makefile:51: check] Aborted (core dumped)

Segmentation fault ้ƒจๅˆ†๏ผŒๆชขๆŸฅ็™ผ็พ new_q ๆฒ’ๆœ‰๏ผš

  1. initialize q->size
  2. ๆชขๆŸฅ q ๆ˜ฏๅฆ็‚บ NULL

ๆ”นๅฏซ q_new














queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (q == NULL) {
        printf("Error! Allocation was failed. \n");
        return q;
    } else {
        q->head = NULL;
        q->tail = NULL;  // Add for the q_insert_tail
        q->size = 0;
        return q;
    }
}

ไบ‚็ขผ้ƒจๅˆ†๏ผŒๆชขๆŸฅ็™ผ็พ q_insert_head length ๅ€ผ้Œฏ่ชค

length = strlen(s);

ๆ”น็‚บ๏ผš

length = strlen(s) + 1;

q_reverse

็”จๅ…ฉๅ€‹ pointer ็ด€้Œ„๏ผŒ้Ž็จ‹ไธญ็š„ head ๅŠ tail ๅ‘ฝๅ็‚บ tmph ๅŠ tmpt
ๅพž่ˆŠ head ้–‹ๅง‹ๅ่ฝ‰๏ผŒhead->next ๆŒ‡ๅ›ž head ไปฅๆญค้กžๆŽจใ€‚
็ถญๆŒ q->head ๆŒ‡ๅ‘ๅฐšๆœชๅ่ฝ‰็š„ไฝ‡ๅˆ—็š„้ฆ–้ …


















void q_reverse(queue_t *q)
{
    if (q != NULL && q->size > 1) {
        list_ele_t *tmph, *tmpt;
        tmpt = q->head;
        tmph = q->head->next;
        q->tail = q->head;
        while (q->head->next != NULL) {
            q->head = tmph->next;
            tmph->next = tmpt;
            tmpt = tmph;
            tmph = q->head;
        }
        q->head->next = tmpt;
        q->tail->next = NULL;
    }
}

ๅœ–่งฃ๏ผš

  1. ๅˆๅง‹ tmpt ๅŠ tmph






linkedlist



a

1

 



b

2

 



a:a->b:data






c

3

 



b:c->c:data






head

head



head->a





tail

tail



tail->c





tmph

tmph



tmph->b





tmpt

tmpt



tmpt->a
  1. tail ็งป่‡ณ head






linkedlist



a

1

 



b

2

 



a:a->b:data






c

3

 



b:c->c:data






head

head



head->a





tail

tail



tail->a





tmph

tmph



tmph->b





tmpt

tmpt



tmpt->a
  1. while ่ฟดๅœˆ






linkedlist



a

1

 



b

2

 



a:a->b:data






b:c->a:data






c

3

 



head

head



head->c





tail

tail



tail->a





tmph

tmph



tmph->b





tmpt

tmpt



tmpt->a












linkedlist



a

1

 



b

2

 



a:a->b:data






b:c->a:data






c

3

 



head

head



head->c





tail

tail



tail->a





tmph

tmph



tmph->c





tmpt

tmpt



tmpt->b
  1. while ่ฟดๅœˆ็ตๆŸ head->next ็‚บ NULL






linkedlist



a

1

 



b

2

 



b:c->a:data






c

3

 



c:c->b:data






head

head



head->c





tail

tail



tail->a





tmph

tmph



tmph->c





tmpt

tmpt



tmpt->b

q_sort








































queue_t*  merge_list(queue_t *l1, queue_t *l2)
{
    if (!l1) return l2;
    if (!l2) return l1;
    if( l1->value < l2->value) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l2->next, l1);
        return l2;
    }
}
queue_t* merge_sort(list_ele_t *l)
{
    if (!q || !q->next) return q;
    list_ele_t* fast;
    list_ele_t* slow;
    fast = q->head->next;
    slow = q->head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    fast = slow->next;
    slow->next = NULL;
    list_ele_t* l1 = merge_sort(q);
    list_ele_t* l2 = merge_sort(q2);
    return merge_list(l1,l2);
}
void q_sort(queue_t *q)
{
    if (q && q->size > 0) {
        merge_sort(q);
        return;
    } else {
        printf("Something going wrong!!");
        return;
    }
}

ๅกๅœจmerge_sort()๏ผŒไธ็Ÿฅ้“ๆ‡‰่ฉฒ็”จไป€้บผๅž‹ๆ…‹็š„ input ๏ผŒ่€ƒๆ…ฎๅˆฐ recursive ๅ‘ผๅซใ€‚
ๅƒ่€ƒๅ‰ไบบๅฏฆไฝœ๏ผšZhuMon๏ผŒๆŽก็”จ pointer to pointer ็š„ๆ–นๅผ๏ผŒๅณๅฏไธ็”จ่€ƒๆ…ฎๅ›žๅ‚ณ type ็š„ๅ•้กŒใ€‚













































void merge_sort(list_ele_t **head)
{
    if(!(*head) || !((*head)->next)) return;

    list_ele_t* fast;
    list_ele_t* slow;

    fast = (*head)->next;
    slow = *head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    fast = slow->next;
    slow->next = NULL;
    slow = *head;
    merge_sort(&fast);
    merge_sort((&slow));

    list_ele_t **tmp = head;
    *head = NULL;
    while (fast && slow) {
        if (strcmp(fast->value, slow->value) < 0) {
            *tmp = fast;
            fast = fast->next;
        } else {
            *tmp = slow;
            slow = slow->next;
        }
        tmp = &(*tmp)->next;
    }
    *tmp = fast ? fast : slow;
}
void q_sort(queue_t *q)
{
    if (!q || q->size == 1) {
        return;
    } else if (q && q->size > 1) {
        merge_sort(&q->head);
        return;
    } else {
        return;
    }
}

็™ผ็พ sorting ๅœจๅŒ…ๅซๅคงๅฏซ็š„ๆ™‚ๅ€™ๆœƒไธๆญฃๅธธ:

Last changed by 
โ€‰
kevin30292
0
462

Read more

Assignment 1

Paper Term LLVM https://llvm.org/ LLVM IR https://blog.gopheracademy.com/advent-2018/llvm-ir-and-go/ LLVM IR is a low-level intermediate representation used by the LLVM compiler framework. You can think of LLVM IR as a ==platform-independent assembly language== with an infinite number of function local registers. SSA https://www.geeksforgeeks.org/static-single-assignment-with-relevant-examples/

Jun 15, 2023
2023 Spring Break

Mar 11 to Mar 19 CheckList [x] airlines UA $598 [x] airB&B [x] rental car [x] park ticket California National Park Sequoia

Feb 24, 2023
Florida

Tampa Tarpon Springs Sponge Docks 735 Dodecanese Blvd, Tarpon Springs, FL 34689 Shells Seafood Restaurant $$ 202 S Dale Mabry Hwy, Tampa, FL 33609 https://goo.gl/maps/1npaAUwccFYCUaHU9 google maps ==4.5== (2700) Menu

Dec 26, 2022
Lab 2 (Working)

Question Investigate two options highlighting the major concepts and components needed for it. https://pytorch.org/tutorials/beginner/dist_overview.html Distributed Data-Parallel Training (DDP) It is a single-program multiple-data training paradigm. The model is replicated on every GPUs, and every GPUs will train different set data. It need communicaiton to synchronize the gradients, thus this approach need some libraries to perfrom allreduce and brodcast operation. such as NCCL, gloo or some MPI libraries. It will only support data parallelism, but it is the easiest way to do distributed training. RPC-Based Distributed Training (RPC)

Nov 13, 2022
Read more from kevin30292
Published on HackMD