---------------------------------------------------------------------------------------
可变数组：
array.h
#ifndef _ARRAY_H_
#define _ARRAY_H_ typedef struct {
int *array;
int size;
} Array; // Array不定义成指针类型 *Array 的原因：定义成变量使用范围更广，如果定义一个指针类型，那么 array p 其实不容易看出是指针 // 函数原型
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_set(Array *a, int index, int value);
int array_get(const Array *a, int index);
void array_inflate(Array *a, int more_size); #endif
// main.c
// Created by weichen on 15/7/7.
// Copyright (c) 2015年 weichen. All rights reserved. #include "array.h"
#include <stdio.h>
#include <stdlib.h> const int BLOCK_SIZE = ; Array array_create(int init_size)
{
Array a;
a.size = init_size;
a.array = (int*)malloc(sizeof(int) * a.size);
return a; // 返回变量本身
} void array_free(Array *a)
{
free(a->array);
a->array = NULL;
a->size = ;
} // 封装
int array_size(const Array *a)
{
return a->size;
} // 返回指针
int* array_at(Array *a, int index)
{
if ( index >= a->size) {
// index位于哪个block，加1后乘以block，得到下一个block，最后减去原来的size
array_inflate(a, (index/BLOCK_SIZE+)*BLOCK_SIZE - a->size);
}
return &(a->array[index]);
} void array_set(Array *a, int index, int value)
{
a->array[index] = value;
} int array_get(const Array *a, int index)
{
return a->array[index];
} void array_inflate(Array *a, int more_size)
{
// 重新分配一块内存空间
int *p = (int*)malloc(sizeof(int) * (a->size + more_size));
int i;
// 复制原数组到新空间
for (i=; i>a->size; a++) {
p[i] = a->array[i];
}
// 释放内存空间
free(a->array);
// 赋值到a
a->array = p;
a->size += more_size;
} int main(int argc, const char * argv[]) {
/*
可变数组（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 int_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 #ifndef _ARRAY_H_
#define _ARRAY_H_ typeof struct {
int *array;
int size;
} Array; // Array 不定义成指针类型 *Array 的原因：定义成变量使用范围更广，如果定义一个指针类型，那么 array p 其实不容易看出是指针 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); #endif */ Array a = array_create();
//printf("%d\n", a.size);
//printf("%d\n", array_size(&a)); // 如果版本升级，直接用a.size不容易更改，封装保护具体实现细节 //*array_at(&a, 0) = 10; //函数调用返回指针，加*号指向指针所指的东西，变量可以赋值
//printf("%d\n", *array_at(&a, 0)); //上面写法的转换
array_set(&a, , );
array_set(&a, , );
printf("%d\n", array_get(&a, )); //10 // 可变数组自动增长
int number = ;
int cnt = ;
while(number != -) {
scanf("%d", &number); // 随便输入数字，循环输出数组a的值，-1停止
if(number != -) {
number = *array_at(&a, cnt++);
printf("%d\n", number);
}
} array_free(&a); return ;
}
链表操作：
node.h
#ifndef _NODE_H_
#define _NODE_H_ typedef struct _node {
int value; // 数据
struct _node *next; // 指针，下一个指向它自己（不能写成 Node *next，因为在这之后才定义的Node）
} Node; // 定义Node类型 #endif
// main.c
// Created by weichen on 15/7/8.
// Copyright (c) 2015年 weichen. All rights reserved. #include "node.h"
#include <stdio.h>
#include <stdlib.h> //typedef struct _node {
// int value;
// struct _node *next;
//} Node; int main(int argc, const char * argv[]) {
/*
链表 可变数组的缺陷：
拷贝需要花时间，如果原数组很大，会很慢
由于新数组需要申请更大的空间，由于之前还没free掉，总有一个时间点会出现尽管总内存够但无法再申请足够使用的情况
所以可变数组不够高效 解决办法：
linked blocks，no copy
就只申请block那么大的内存，与原来的内存空间链起来 理想中的效果：
|-------------|
| 内存1 |---+
|-------------| |
+--------------------+
| |-------------|
+->| block |---+
|-------------| |
+--------------------+
| |-------------|
+->| block |
|-------------| 实际中：
head
|
|-------------| |--------------| |-------------|
| 数据 | point |--->| 数据 | point |--->| 数据 | point |
|-------------| |--------------| |---------|---|
-
整个结构叫做链表，其中带有数据的叫做结点 让last一开始等于第一个的数据，看next有没有东西，让last所指那个东西的下一个，于是last指向了第二个的数据
*/ Node *head = NULL;
int number;
do {
scanf("%d\n", &number);
if ( number != - ) {
// add to linked-list
Node *p = (Node*)malloc(sizeof(Node)); // 为结构分配一块内存空间
p->value = number; // 初始化值为number
p->next = NULL; // 初始化第一个的next为null，即下一个为null
// find the last
Node *last = head; // 初始化：最后一个就是当前的这个
if ( last ) { // 如果last不为null了
while ( last->next ) { // 如果最后一个还有next的话，last就是last的next
last = last->next; // 当循环停止时，last所指的就是最后一个
}
// attach
last->next = p;
} else {
head = p; // 只有第一个，head为p
}
}
} while ( number != - ); return ;
}
改进：
// main.c #include "node.h"
#include <stdio.h>
#include <stdlib.h> // 单独定义一个数据类型表示list
typedef struct _list {
Node* head;
} List; void add(List* list, int number); int main(int argc, const char * argv[]) { List list;
int number;
list.head = NULL; do {
scanf("%d\n", &number); if (number != -) {
add(&list, number);
}
} while(number != -); return ;
} // 添加函数独立出来
void add(List* pList, int number)
{
Node *p = (Node*)malloc(sizeof(Node)); p->value = number;
p->next = NULL; Node *last = pList->head;
if (last) {
while (last->next) {
last = last->next;
}
last->next = p;
} else {
pList->head = p;
}
}
搜索
删除
清除