网易云课堂_C语言程序设计进阶

网易云课堂_C语言程序设计进阶_第5周：链表

5.1可变数组

5.2链表

5.1可变数组

Resizable Array

Think about a set of functions that provide a mechanism of resizable array of int.

Growable

Get the current size

Access to the elements

The Interface

Array array_create(int init_size);

void array_free(Array *a);

int array_size(const Array *a);

int *array_at(Array *a, int index);

void array_inflate(Array *a, int more_size);

头文件array.h

 1 #include <stdio.h>
 2 
 3 #ifndef _ARRAY_H_
 4 #define _ARRAY_H_
 5 
 6 typedef struct
 7 {
 8     int *array;
 9     int size;
10 }Array;
11 
12 Array array_create(int init_size);//清空数组
13 void array_free(Array *a);//返回数组元素数量
14 int array_size(const Array *a);//返回数组某个下标的值
15 int *array_at(Array *a, int index);//返回数组某个下标的值
16 int array_get(const Array *a, int index);//返回数组某个下标的值
17 void array_set(Array *a, int index, int value);//修改数组某个下标的值
18 void array_inflate(Array *a, int more_size);//增大数组
19 
20 #endif

源文件array.c

 1 #include "array.h"
 2 
 3 const BLOCK_SIZE = 20;
 4 
 5 //typedef struct
 6 //{
 7 //    int *array;
 8 //    int size;
 9 //}Array;
10 
11 Array array_create(int init_size)//创建数组
12 {
13     Array a;
14     a.size = init_size;
15     a.array = (int *)malloc(sizeof(int)*a.size);
16     return a;
17 }
18 
19 void array_free(Array *a)//清空数组
20 {
21     free(a->array);
22     a->array = NULL;
23     a->size = 0;
24 }
25 
26 int array_size(const Array *a)//返回数组元素数量
27 {
28     return a->size;
29 }
30 
31 int *array_at(Array *a, int index)//返回数组某个下标的值
32 {
33     if (index >= a->size)
34     {
35         array_inflate(a, (index / BLOCK_SIZE + 1)*BLOCK_SIZE - a->size);
36     }
37     return &(a->array[index]);
38 }
39 
40 int array_get(const Array *a, int index)//返回数组某个下标的值
41 {
42     return a->array[index];
43 }
44 
45 void array_set(Array *a, int index, int value)//修改数组某个下标的值
46 {
47     a->array[index] = value;
48 }
49 
50 void array_inflate(Array *a, int more_size)//增大数组
51 {
52     int *p = (int *)malloc(sizeof(int)*(a->size + more_size));
53     int i;
54     for (i = 0; i < a->size; i++)
55     {
56         p[i] = a->array[i];
57     }
58     free(a->array);
59     a->size += more_size;
60 }
61 
62 void main()
63 {
64     Array a = array_create(100);
65     printf("%d
", array_size(&a));
66     *array_at(&a, 0) = 10;
67     printf("%d
", *array_at(&a, 0));
68 
69     int number;
70     int cnt = 0;
71     while (1)
72     {
73         /*scanf("%d", &number);
74         *array_at(&a, cnt++) = number;*/
75         scanf("%d", array_at(&a, cnt++));
76     }
77     
78     array_free(&a);
79 
80     system("pause");
81 }

5.2链表

issues

Allocate new memory each time it inflates is an easy and clean way. BUT

It takes time to copy, and

may fail in memory restricted situation

必须保证：->箭头左边的指针，不能为空

1     for (q = 0, p = head; p; q = p, p = p->next)
2     {
3         if (p->value == 1)
4         {
5             q->next = p->next;
6         }
7     }

必须保证：->箭头左边的指针，不能为空