Homework Assignment #8 Solutions

1. 假設一個三維整數陣列 A 的大小自第一維到第三維各為 m, n, 和 p, 且這些變數的值需到程式執行時才能決定。所以陣列 A 是一個動態陣列。畫出陣列 A 的位址圖示,並寫出陣列 A 記憶體空間分配的程式片段。

解答:

 

A = (int ***) malloc(sizeof(int **) * m);

for (i=0; i<m; i++) {

  A[i] = (int **) malloc(sizeof(int *) * n);

  for (j=0; j<n; j++)

    A[i][j] = (int *) malloc(sizeof(int) * p);

}

2. 下列圖示是一個單向連結表的圖,假設 ptr0, ptr1ptr2 是指向三個相鄰節點的指標:

a. 寫一個程式片段以定義單向連結表節點的資料型態。

b. 用圖示畫出改變節點指標的步驟,以交換 ptr1ptr2 所指的兩個紅色節點順序。

c. 寫一個程式片段以交換 ptr1ptr2 所指的兩個紅色節點順序。

解答:

a.

typedef struct Node {
  int data;
  struct Node* next;
} node;

typedef node* nodePtr;

b.

c.

ptr0->next = ptr2;

ptr1->next = ptr2->next;

ptr2->next = ptr1;

3. 下列圖示是一個雙連結表的圖,假設 ptr1ptr2 是兩個節點 (不一定相鄰) 的指標:

a. 寫一個程式片段以定義雙向連結表節點的資料型態。

b. 用圖示畫出改變節點指標的步驟,以交換 ptr1ptr2 所指的兩個紅色節點順序。

c. 寫一個程式片段以交換 ptr1ptr2 所指的兩個紅色節點順序。

 

解答:

a.

typedef struct Node {
  int data;
  struct Node* prev;

  struct Node* next;
} node;

typedef node* nodePtr;

 

b.

c.

ptr1->prev->next = ptr2;

ptr1->next->prev = ptr2;

ptr2->prev->next = ptr1;

ptr2->next->prev = ptr1;

temp = ptr2->prev;

ptr2->prev = ptr1->prev;

ptr1->prev = temp;

temp = ptr2->next;

ptr2->next = ptr1->next;

ptr1->next = temp;

4. 假設你將設計及實作以下 string.h 的副程式,即是你的實作不能呼叫 strig.h 的副程式,除非是本題已完成的副程式。各副程式的意義請參考 The C Library Reference Guide 的定義。使用迴圈 (loop) 或遞迴副程式 (recursive function) 寫出下列副程式的 C 語言程式碼 (program code):

size_t strlen(const char *str);

int strcmp(const char *str1, const char *str2);

char *strcpy(char *str1, const char *str2);

char *strcat(char *str1, const char *str2);

char *strpbrk(const char *str1, const char *str2);

size_t strspn(const char *str1, const char *str2);

char *strstr(const char *str1, const char *str2);

解答:

size_t strlen(const char *str) {
  size_t length;
  for (length = 0; str[length] != '\0'; length++) ;
  return length;
}

int strcmp(const char *str1, const char *str2) {
  int result = 0;
  int i = 0;
  while (!result && str1[i]!='\0' && str2[i]!='\0') {
    if (str1[i]>str2[i]) result = 1;
    else if (str1[i]<str2[i]) result = -1;
    i++;
  }
  if (!result && str1[i]!='\0') result = 1;
  else if (!result && str2[i]!='\0') result = -1;
  return result;
}

char *strcpy(char *str1, const char *str2) {
  int i;
  for (i=0; str2[i]!='\0'; i++) str1[i] = str2[i];
  str1[i] = '\0';
  return str1;
}

char *strcat(char *str1, const char *str2) {
  int length=strlen(str1), i;
  for (i=0; str2[i]!='\0'; i++) str1[length+i] = str2[i];
  str1[length+i] = '\0';
  return str1;
}

char *strpbrk(const char *str1, const char *str2) {
  int i, j;
  int found = 0;
  for (i=0; !found && str1[i]!='\0'; i++)
    for (j=0; !found && str2[j]!='\0'; j++) found = (str1[i]==str2[j]);
  if (found) return &str1[i-1];
  else return NULL;
}

size_t strspn(const char *str1, const char *str2) {
  int i, j;
  int done = 0, length = 0;
  for (i=0; !done && str1[i]!='\0'; i++) {
    for (j=0; str2[j]!='\0'; j++) {
      if (str1[i]==str2[j]) {length++; break;}
      else if (length>0 && str2[j+1]=='\0') done = 1;

    }
  }
  return length;
}

char *strstr(const char *str1, const char *str2) {
  char *ptr1, *ptr2, *temp;
  int cont;
  for (ptr1=str1; *ptr1!='\0'; ptr1++) {
    if (*ptr1==*str2) {
      if (*(str2+1)=='\0') return ptr1;
      temp = ptr1 + 1;
      cont = 1;
      for (ptr2=str2+1; cont && *ptr2!='\0'; ptr2++)
        if (*temp!=*ptr2) cont = 0;
       else if (*(ptr2+1)=='\0') return ptr1;
       else temp++;
    }
  }
  return NULL;
}