contributed by < Hsuhaoxiang
>
$ uname -a
Linux haoxiang-System-Product-Name 5.3.0-40-generic #32~18.04.1-Ubuntu SMP Mon Feb 3 14:05:59 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0
Copyright (C) 2017 Free Software Foundation, Inc.
int q_size(queue_t *q)
{
if (!q)
return 0;
return q->size;
}
queue_t *q_new()
{
queue_t *q = (queue_t *) malloc(sizeof(queue_t));
if (!q)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
bool q_insert_head(queue_t *q, char *s)
{
int Strlen = strlen(s);
if (!q)
return false;
list_ele_t *newh;
newh = (list_ele_t *) malloc(sizeof(list_ele_t));
if (!newh)
return false;
newh->value = (char *) malloc((Strlen + 1) * sizeof(char));
if (!(newh->value)) {
free(newh);
return false;
}
strncpy(newh->value, s, Strlen + 1);
newh->next = q->head;
q->head = newh;
q->size += 1;
if (q->size == 1)
q->tail = newh;
return true;
}
q_insert_head
非常相似,不同的地方在於要將插入前的 tail
的 next
指向正要插入的這個元素bool q_insert_tail(queue_t *q, char *s)
{
int Strlen = strlen(s);
if (!q)
return false;
list_ele_t *newh;
newh = (list_ele_t *) malloc(sizeof(list_ele_t));
if (!newh)
return false;
newh->value = (char *) malloc((Strlen + 1) * sizeof(char));
if (!(newh->value)) {
free(newh);
return false;
}
strncpy(newh->value, s, Strlen + 1);
newh->next = NULL;
q->size += 1;
if (q->size == 1)
q->head = newh;
else
q->tail->next = newh;
q->tail = newh;
return true;
}
head
指向新的頭也就是 head->next
size
減一,並將此元素所用到的記憶體空間釋放bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || q->size == 0)
return false;
if (sp) {
strncpy(sp, q->head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
if (q->size == 1) {
free(q->head->value);
free(q->head);
q->head = NULL;
q->size -= 1;
return true;
}
list_ele_t *tmp;
tmp = q->head;
q->head = q->head->next;
q->size -= 1;
free(tmp->value);
free(tmp);
if (q->size == 0)
q->tail = NULL;
return true;
}
queue
的 size 為 0 或 1 直接結束void q_reverse(queue_t *q)
{
if (!q || q->size == 0) {
return;
}
if (q->size == 1) {
return;
}
list_ele_t *pre, *cur, *pos;
pre = pos = NULL;
cur = q->head;
while (cur) {
pos = cur->next;
cur->next = pre;
pre = cur;
cur = pos;
}
cur = q->head;
q->head = q->tail;
q->tail = cur;
}
void q_free(queue_t *q)
{
if (!q) {
return;
}
if (q->head) {
list_ele_t *tmp;
while (q->head) {
tmp = q->head;
q->head = tmp->next;
free(tmp->value);
free(tmp);
}
}
free(q);
}
void q_sort(queue_t *q)
{
if (!q || !q->head) {
return;
}
if (q->head == q->tail) {
return;
}
q->head = merge_sort(q->head);
list_ele_t *iter;
iter= q->head;
while (iter && iter->next)
iter = iter->next;
q->tail = iter;
}
list_ele_t *merge_sort(list_ele_t *head)
{
if (!head || !head->next) {
return head;
}
list_ele_t *fast = head->next;
list_ele_t *slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
list_ele_t *left = head;
list_ele_t *right = slow->next;
slow->next = NULL;
left = merge_sort(left);
right = merge_sort(right);
return merge(left, right);
}
考慮以下改寫:
static list_ele_t *merge_sort(list_ele_t *head)
{
if (!head || !head->next)
return head;
list_ele_t *slow = head, *fast;
for (fast = head->next; fast && fast->next; fast = fast->next->next)
slow = slow->next;
list_ele_t *mid = slow->next;
slow->next = NULL;
return merge(merge_sort(head), merge_sort(mid));
}
要點:
static
,提示編譯器施加更多最佳化; jserv
list_ele_t *merge(list_ele_t *left, list_ele_t *right)
{
if (!left) {
return right;
}
if (!right) {
return left;
}
list_ele_t *start = NULL;
for (list_ele_t *merge_ele = NULL; left || right;) {
if (right == NULL || (left && strcmp(left->value, right->value) < 0)) {
if (!merge_ele)
start = merge_ele = left;
else {
merge_ele->next = left;
merge_ele = merge_ele->next;
}
left = left->next;
} else {
if (!merge_ele)
start = merge_ele = right;
else {
merge_ele->next = right;
merge_ele = merge_ele->next;
}
right = right->next;
}
}
return start;
}
考慮以下改寫:
static list_ele_t *merge(list_ele_t *left, list_ele_t *right)
{
list_ele_t *head = NULL;
for (list_ele_t **iter = &head; true; iter = &((*iter)->next)) {
if (!left) {
(*iter) = right;
break;
}
if (!right) {
(*iter) = left;
break;
}
if (strcmp(left->value, right->value) < 0) {
(*iter) = left;
left = left->next;
} else {
(*iter) = right;
right = right->next;
}
}
return head;
}
要點:
jserv
# Test of insert_head and remove_head
--- trace-01-ops 6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
--- trace-05-ops 5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
--- trace-06-string 6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
--- trace-07-robust 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
--- trace-10-malloc 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
--- trace-13-perf 6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
strcmp
改成 strnatcmp
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
--- trace-05-ops 5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
--- trace-06-string 6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
--- trace-07-robust 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
--- trace-10-malloc 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
--- trace-13-perf 6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up