Harvard CS50 学习笔记（五）

 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

// node *list;
// 创建一个链表
node *list = NULL;
// 创建一个节点
node *n = malloc(sizeof(node));
// malloc 函数常规判断
// if (n != NULL)
// {
//     (*n).number = 1;
// }
if (n != NULL)
{
    // 节点的数字部分赋值为 1 
      n->number = 1;
      // 节点的指针部分赋值为 NULL  
    n->next = NULL;
}
// 将链表变量指向第一个节点
list = n;
// 再创建一个节点，还是n变量，指向不同的节点
node *n = malloc(sizeof(node));
if (n != NULL)
{
    n->number = 2;
    n->next = NULL;
}
// 添加一个节点
list->next = n;
// 又加了一个节点
node *n = malloc(sizeof(node));
if (n != NULL)
{
    n->number = 3;
    n->next = NULL;
}
// 再添加一个节点
list->next->next = n;

 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

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
  int number;
  struct node *next;
}
node;

int main(void) {
  // node *list;
  // 创建一个链表
  node *list = NULL;
  // 创建一个节点
  node *n = malloc(sizeof(node));
  // malloc 函数常规判断
  // if (n != NULL)
  // {
  //     (*n).number = 1;
  // }
  if (n == NULL)
  {
      return 1;
  } 
  // 节点的数字部分赋值为 1 
  n->number = 1;
  // 节点的指针部分赋值为 NULL  
  n->next = NULL;
  // 将链表变量指向第一个节点
  list = n;

  // 再创建一个节点，还是n变量，指向不同的节点
  n = malloc(sizeof(node));
  if (n == NULL)
  {
      free(list);
        return 1;
  }

  n->number = 2;
  n->next = NULL;
  // 添加一个节点
  list->next = n;

  // 又加了一个节点
  n = malloc(sizeof(node));
  if (n == NULL)
  {
        // 注意顺序！！
        free(list -> next);    
      free(list);
        return 1;
  }

  n->number = 3;
  n->next = NULL;

  // 再添加一个节点
  list->next->next = n;

}

1
2
3
4

// 打印链表
for (node *tmp = list; tmp != NULL; tmp = tem -> next) {
      printf("%i\n", tmp -> number);
}

1
2
3
4
5
6

// 释放内存
while (list != NULL) {
  node *tmp = list -> next;
  free(list);
  list = tmp;
}

1
2
3
4
5
6
7

typedef struct node
{
    int number;
    struct node *left;
    struct node *right;
}
node;

1
2
3
4
5
6

typedef struct node
{
  char word[LONGEST_WORD + 1];
  struct node *next;
}
node;

1
2
3
4
5
6

typedef struct node
{
  bool isWord;;
  struct node *children[SIZE_OF_ALPHABET];
}
node;

  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

// Simulate genetic inheritance of blood type

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Each person has two parents and two alleles
typedef struct person
{
    struct person *parents[2];
    char alleles[2];
}
person;

const int GENERATIONS = 3;
const int INDENT_LENGTH = 4;

person *create_family(int generations);
void print_family(person *p, int generation);
void free_family(person *p);
char random_allele();

int main(void)
{
    // Seed random number generator
    srand(time(0));

    // Create a new family with three generations
    person *p = create_family(GENERATIONS);

    // Print family tree of blood types
    print_family(p, 0);

    // Free memory
    free_family(p);
}

// Create a new individual with `generations`
person *create_family(int generations)
{
    // TODO: Allocate memory for new person
    person *child = malloc(sizeof(person));

    // Generation with parent data
    if (generations > 1)
    {
        // TODO: Recursively create blood type histories for parents
        generations--;
        person *father = create_family(generations);
        person *mother = create_family(generations);

        // TODO: Randomly assign child alleles based on parents
        int r = rand() % 2;
        child -> parents[0] = father;
        child -> parents[1] = mother;
        child -> alleles[0] = father -> alleles[r];
        child -> alleles[1] = mother -> alleles[r];

    }

    // Generation without parent data
    else
    {
        // TODO: Set parent pointers to NULL
        child -> parents[0] = NULL;
        child -> parents[1] = NULL;

        // TODO: Randomly assign alleles
        child -> alleles[0] = random_allele();
        child -> alleles[1] = random_allele();
    }

    // TODO: Return newly created person
    return child;
}

// Free `p` and all ancestors of `p`.
void free_family(person *p)
{
    // TODO: Handle base case
    if (p -> parents[0] == NULL) {
        free(p);
        return;
    }

    // TODO: Free parents
    free_family(p -> parents[0]);
    free_family(p -> parents[1]);

    // TODO: Free child
    free(p);

}

// Print each family member and their alleles.
void print_family(person *p, int generation)
{
    // Handle base case
    if (p == NULL)
    {
        return;
    }

    // Print indentation
    for (int i = 0; i < generation * INDENT_LENGTH; i++)
    {
        printf(" ");
    }

    // Print person
    printf("Generation %i, blood type %c%c\n", generation, p->alleles[0], p->alleles[1]);
    print_family(p->parents[0], generation + 1);
    print_family(p->parents[1], generation + 1);
}

// Randomly chooses a blood type allele.
char random_allele()
{
    int r = rand() % 3;
    if (r == 0)
    {
        return 'A';
    }
    else if (r == 1)
    {
        return 'B';
    }
    else
    {
        return 'O';
    }
}

  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

// Implements a dictionary's functionality

#include <stdbool.h>
#include <stdio.h>
#include "dictionary.h"
#include <string.h>
#include <ctype.h>
#include <cs50.h>
#include <stdlib.h>

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Number of buckets in hash table
const unsigned int N = 262144;

// Hash table
node *table[N];

int total = 0;

node* createNode(char str[LENGTH + 1]);
void freeNodes(node* node);

// Returns true if word is in dictionary, else false
bool check(const char *word)
{

    char target[LENGTH + 1];
    int i = 0;

  	// 记录检索单词每个小写字母到数组
    while (word[i] != '\0') {
        target[i] = tolower(word[i]);
        i++;
    }

  	// 多余的位置用0占位，否则Hash值不同
    for (int j = i; j < LENGTH + 1; j++) {
        target[j] = 0;
    }

    int index = hash(target);
    if (table[index] == NULL) {
        return false;
    }

  	// 链表的头节点
    node* pointer = table[index];

  	// 比较单词是否相同
    while (true) {
        if (strcmp(target, pointer -> word) == 0) {
            return true;
        }
        if (pointer -> next == NULL) {
            break;
        } else {
            pointer = pointer -> next;
        }
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // BKDR Hash Function

  unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
	unsigned int hash = 0;

	while (*word)
	{
		hash = hash * seed + (*word++);
	}

	unsigned int result = (hash & 0x7FFFFFFF) / 10000;
	if (result > N) {
	    result /= 10;
	}
    return result;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    FILE* file = fopen(dictionary, "r");
    if (file == NULL) {
        return false;
    }

    char str[LENGTH + 1];
    while (fscanf(file,"%s", str) != EOF) {
        total++;
        int index = hash(str);
        if (table[index] == NULL) {
          	// 第一个节点
            node* firstNode = createNode(str);

            table[index] = firstNode;
            // free(firstNode);
        } else {
          	// 头插法记录后续节点
            node* subsequentNode = createNode(str);
            strcpy(subsequentNode -> word, str);
            node* firstNode = table[index];
            subsequentNode -> next = firstNode;
            table[index] = subsequentNode;
            // free(subsequentNode);
        }
    }
    fclose(file);
    return true;

}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    return total;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    for (int i = 0; i < N; i++) {
        if (table[i] == NULL) {
            continue;
        } else {
            freeNodes(table[i]);
        }
    }
    return true;
}

// 创建节点
node* createNode(char str[LENGTH + 1]) {
    node* pointer = malloc(sizeof(node));
    if (pointer != NULL) {
        strcpy(pointer -> word, str);
        pointer -> next = NULL;
    }
    return pointer;
}

// 递归释放所有节点
void freeNodes(node* node) {
    if (node -> next == NULL) {
        free(node);
    } else {
        freeNodes(node);
    }
}