目录
– 可变数组
– 思路
– 实现
– 定义结构
– 创建数组
– 释放数组
– 数组大小
– 获得指定单元的地址
– 数组的增长
– 链表
– 概述
– 实现思路
– 程序实现
– 定义节点的结构体
– 增加一个节点到链表末尾
– 链表的遍历
– 链表的检索与删除
可变数组
思路
C语言中, 数组被一旦定义就无法改变其大小
如果想得到一个”可变数组”, 应当有一下特点:
+ 可以增长
+ 要能知道当前数组确切的大小
+ 要有方便合理的方法访问到其中的单元
考虑创建一系列实现特定功能的函数库:
+ 创建这样的数组: 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);
实现
定义结构
typedef struct {
int *array;
int size;
} Array;
其实, 可以直接定义
*Array指针, 原因是函数调用基本都要求传指针, 直接定义为指针会显得方便美观
但是, ta有两个严重的弊端
首先, 阅读代码的人, 很难察觉这是一个指针
其次, 无法在局部范围内, 定义出一个Array因此, 还是老老实实的定义本体
创建数组
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;
}
为什么如此简单的事情还要额外创造一个函数?
这个做法有个专门的称呼: 封装
封装函数极为有用, 为后期的修改提供了可能
例如, 如果后来开发中, 要得到size必须先通过一段保护程序
那么就可以在这个封装函数中修改
而且外部不知道具体如何实现, 对size形成了保护
而如果每次都采用直接调用, 那么要耗费大量精力做修改, 这是很划不来的
获得指定单元的地址
int *array_at(Array *a, int index){
return &(a->array[index]);
}
为什么要的是指针?
因为这样可以 访问 这个元素
这意味着既能读取又能写入考虑到在函数前加星号
*可能会引起不适
可以再添加一对函数(名字可以是read和set), 来实现同样的功能
这么做繁琐, 但是增强了可读性, 当然, 直接获取指针其实也还行
数组的增长
简要来说, 就是: 申请一块新的, 把旧的释放掉
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; i++)
{
p[i] = a->array[i];
}
free(a->array);
a->array = p;
a->size += more_size;
}
什么时候要增长数组呢?
当我们访问一个元素的时候, 发现下标超出了数组的大小, 就意味着数组不够用了
因此改进array_at方法:
int *array_at(Array *a, int index)
{
if(index>=a->size){
array_inflate(a, ((index / BLOCK_SIZE) + 1) * BLOCK_SIZE - a->size);
}
return &(a->array[index]);
}
为什么有BLOCK_SIZE?
设想我们的数组撑满了, 此时需要再往里填一些数(比如在读入数据的时候)
那么如果增长的大小为index - a->size
即便只是读入一个数句, 就要调用一次array_inflate函数
要知道, 这意味着数组重新复制一遍, 无异于大动干戈因此最好的做法是一次增长 “一块”空间
比如说一次就增长5的倍数大小的空间
这样做最经济高效
为此, 我们还要在文件的前面添上常量声明:
const BLOCK_SIZE = 5;
如何理解
((index / BLOCK_SIZE) + 1) * BLOCK_SIZE呢?
其实就是向上取整
如果index是2, 那么就是5
如果index是67, 那么就是70
保证数组的大小总是BLOCK_SIZE的整数倍
链表
概述
自动增长的数组是一个很有用的工具
但是, ta最大的缺点在于: 每次都要申请一个能容纳全部元素的新的空间
这会导致两个问题:拷贝一次要花很多时间
当数组中的总数据量比可用空间的一半要多的时候, 明明可以容纳下, 但没法再申请空间了
链表, 就是不再拷贝数组, 当数组不够用的时候, 开辟一块新的空间, 并用一个指针将两者”链接”起来
这么做不但在时间上高效, 而且还能充分利用到可用空间的角角落落, 空间使用上也高效
实现思路
每一个储存单元包含一个 int 数组和一个 int 指针
其中:
+ 第一个储存单元要能表示自己是第一个, 要有个head标志
+ 中间每个指针都指向下一个单元的地址
+ 最后一个指针也要有个表示, 表明自己是最后的末尾
这样的每个单元被称为 节点(node), 整个这一系列的节点被称为 链表(linked list)
当我们要读入 未知数量的 数据时, 应当有下列的行为:
+ 先Node *head = NULL定义一个头部节点, 代表着有这么一个链表存在
+ 当有数据进入时申请空间, 创建一个新的Node
+ 把数据导入这个节点的value中, 并将*next指针设定为NULL(因为新节点添加在链表的末尾, 因此用指针指向NULL表示)
+ 找到链表的最后一个节点
– 先定义一个Node *last指针, 让ta的初始指向为*head一致
> 这里还需要判断一下, *last是不是就是*head
– 看*last指针指向的Node对应的*next是不是NULL
– 不是的话用循环继续找下去
– 是的话, 就说明此时这个*last指向的就是最后的节点了
+ 把最后的节点的*next改成 现在新添加的这个Node的地址, 即, 实现了 链接
程序实现
定义节点的结构体
typedef struct _node{
int value;
struct _node *next;
} Node;
注意一个细节, 观察下面这段错误代码和上面的正确的代码的区别:
typedef struct _node{
int value;
Node *next;
} Node;
区别在于定义结构指针的时候用_node还是声明好的结构Node
注意, 编译器在第三行声明成员变量的名称时, 还 “不认识”Node是什么
但如果改写成struct _node, 编译器是知道的
在那之后再将struct _node定义成Node(两者等价)P.S.这个做法很常见
增加一个节点到链表末尾
把方才实现思路中, “添加一个新节点到链表最末尾”这个功能抽离封装为函数
void add(Node *head, int number)
{
Node *p = (Node *)malloc(sizeof(Node));
p->value = number;
p->next = NULL;
Node *last = head;
if (last)
{
while (last->next)
{
last = last->next;
}
last->next = p;
}
else
{
head = p;
}
}
但这个粗糙的函数有个问题, 那就是head = p这处要求改变传入的head, 而由于在函数中, 因此不奏效
有多种方法可以解决:
1. 用全局变量
2. 用 return 返回一个head
3. 传入一个head的地址(指针的指针)
4. 自定义一个新的结构, 这个结构中包含的成员变量是Node的指针
前几种容易考虑到, 着重分析一下第4个方法:
先要额外定义一个结构_List
typedef struct _List{
Node *head;
} List;
接着修改函数, 传入一个List的指针List *pList以修改函数外的变量
再将head改成pList->head, 得到最终的版本:
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;
}
}
为什么要这么做呢?
因为, 用一个自己定义的List结构来容纳head这个node的指针
在阅读上更容易接受, 节点不再单独出现, 更有链表的样貌
此外, 这么做还能允许后期加入更多的功能例如, 为了寻找链表的尾巴, 每次都需要做一个循环
那么就可以在这个List结构中加入Node *last
每次添加新的Node之后更新last, 高效且易懂
链表的遍历
用一个循环搞定
Node *p;
for (p = list.head; p; p=p->next)
{
printf("%d\t", p->value);
}
封装为函数:
void pirnt(List *pList)
{
Node *p;
for (p = pList->head; p; p = p->next)
{
printf("%d\t", p->value);
}
printf("\n");
}
链表的检索与删除
检索就是在遍历的过程中比较value和目标值
实现删除有如下步骤:
+ 把前面Node的指针指向后面的Node
+ free当前的Node
问题在于, 无法获知 上一个Node
考虑再加一个指针, 记录上一个Node
void delet(List *pList, int number)
{
Node *p, *q;
for (q = NULL, p = pList->head; p; q = p, p = p->next)
{
if (p->value == number)
{
if (q)
{
q->next = p->next;
}else{
pList->head = p->next;
}
free(p);
break;
}
}
}
一定要检查边界条件!
任何在->左侧的指针必须要检查是否为NULL
