2019q1 Homewok1(lab0)

contributed by < asd617140123 >

認真看作業要求，除了提及如何逐步達到要求，還需要進行:

1. 改善程式效能
2. 解釋自動評分系統運作的原理
3. 提及 qtest 的行為和裡頭的技巧

還未達成符合預期目標，請繼續付出！

jserv

開發環境

Linux ubuntu 4.4.0-31-generic #50~14.04.1-Ubuntu SMP Wed Jul 13 01:07:32 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux

等待解決

• scanf()例外處理

Requirement

• 實作 link list
• 實作 FIFO & LIFO queue
  q_insert_tail 和q_size要constant time
• 搞懂 malloc 和 free function
• 搞懂 strlen,strcpy,strncpy實作流程
• 閱讀 http://www.cs.cmu.edu/~iliano/courses/18S-CMU-CS122/handouts/10-linkedlist.pdf

參考

https://hackmd.io/s/S1NttXtrV#
https://hackmd.io/s/BysQssYHN#

實作

在尾端跟長度查詢 複雜度是O(1),所以在下方加入

typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    long long size;
} queue_t;

q_free

void q_free(queue_t *q) 
{
    queue_t *q_new() {
     queue_t *q = malloc(sizeof(queue_t));
  /* What if malloc returned NULL? */
  if(q){
	  q->head = NULL;
	  q->tail = NULL;
	  // q->head->value = malloc(sizeof(queue_t));
	  //q->head->value[0] = 'a';
	  q->size = 0;
  }
  //q->head = malloc(sizeof(queue_t));
  return q;
}
}

q_insert_head

bool q_insert_head(queue_t *q, char *s) {
  list_ele_t *newh;
  /* What should you do if the q is NULL? */
  if(q == NULL)
  {
	  return false;
  }
  int length = strlen(s);
  //length = 0;
  if(q)
  {
	newh = malloc(sizeof(list_ele_t));
	newh->next = q->head;
	
	q->head = newh;
	if(q->size == 0)
		q->tail = newh;
	newh -> value = malloc(sizeof(char)*length);
	strcpy(newh->value,s);

	q->size++;
	return true;
  }
  else 
	  return false;
 

  /* Don't forget to allocate space for the string and copy it */
  /* What if either call to malloc returns NULL? */
 
}

q_insert_tail

bool q_insert_tail(queue_t *q, char *s) {
  /* You need to write the complete code for this function */
  /* Remember: It should operate in O(1) time */
	if(q==NULL)
	{
		return false;
	}
	else
	{
		list_ele_t* tmp_node = malloc(sizeof(list_ele_t));
		
		tmp_node -> value = malloc(sizeof(char)*(strlen(s)+1));
		stpcpy(tmp_node->value,s);
		tmp_node -> next = NULL;
		if(q -> size == 0)
		{
			q->head = tmp_node;
		}
		else
		{	//避免蓋掉第一個節點
			q->tail->next = tmp_node;
		}
		//因為每次加入需要把q->tail 更新
		q->tail = tmp_node;
		
		q->size++;
		
		return true;
		
	}

}

q_remove_head

一開始發現使用free() function remove 會有下方 錯誤資訊

ERROR: Corruption detected in block with address 0x1aa2600 when attempting to free it
Removed k from queue
q = [j ... ]

後來發現要在queue.c加入
#define INTERNAL 1
並且使用 test_free() 才不會跳error

相關原理還要再看 qtest.c 裡面的實作

bool q_remove_head(queue_t *q, char *sp, size_t bufsize) {
  /* You need to fix up this code. */
	if (q == NULL || q->size == 0)
        return false;
	else
	{
		list_ele_t* tmp_node = q->head;
		q->head = q->head->next;
		if (q->head == NULL)
		q->tail = NULL;
		if(sp)
		{
			size_t value_str_len = strlen(tmp_node->value);
			if (value_str_len >= bufsize) {
				strncpy(sp, tmp_node->value, bufsize - 1);
				sp[bufsize - 1] = '\0';
			} else {
				strncpy(sp, tmp_node->value, value_str_len);
				sp[value_str_len] = '\0';
			}
		}
		free(tmp_node->value);
		free(tmp_node);
		q->size--;
	}
	return true;
}

q_size

直接回傳存好的值大小：

int q_size(queue_t *q) {
  /* You need to write the code for this function */
  /* Remember: It should operate in O(1) time */
	 if (!q || !q->head)
        return 0;
    return q->size;
}

q_reverse

void q_reverse(queue_t *q)
{
    if (!q || !q->head || !q->head->next)
        return;
	q->tail = q->head;
    q->head = q->head->next;

    list_ele_t* back = q->tail, *curr = q->head->next;

    while (curr != NULL)
    {
        q->head->next = back;
        back = q->head;
        q->head = curr;
        curr = curr->next;
    }
	//最後一個指標指到q->head-next
    q->head->next = back;
    q->tail->next = NULL;
}