---------------------------------------------------------------------------------------
可變數組：
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 = 20;
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 = 0;
}
// 封裝
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+1)*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=0; 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(100);
//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, 0, 10);
array_set(&a, 1, 14);
printf("%d\n", array_get(&a, 0)); //10
// 可變數組自動增長
int number = 0;
int cnt = 0;
while(number != -1) {
scanf("%d", &number); // 隨便輸入數字，循環輸出數組a的值，-1停止
if(number != -1) {
number = *array_at(&a, cnt++);
printf("%d\n", number);
}
}
array_free(&a);
return 0;
}
鏈表操作：
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 != -1 ) { // 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 != -1 ); return 0; }
改進：
// 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 != -1) {
add(&list, number);
}
} while(number != -1);
return 0;
}
// 添加函數獨立出來
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;
}
}
搜索
刪除
清除
Link：http://www.cnblogs.com/farwish/p/4628952.html
@黑眼詩人 <www.farwish.com>
