11.1 可变数组
11.1.1 可变数组
可变数组
- 可以变大
- 可以取得当前大小
- 对数组元素可以访问
接口(创建一个函数库)
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);
void array_set(Array *a, int index, int value);
int array_get(const Array *a, int index);
ALYM13066289426
#include <stdio.h>
#include <array.h>
#include <stdlib.h>
const BLOCK_SIZE = 20;
/*typedef struct {
int *array;
int size;
} Array; */
Array array_create(int init_size) {
Array t;
t.size = init_size;
t.array = (int*)malloc(sizeof(int)*t.size);
return t;
}
int array_size(const Array *a) {
return a->size;
}//我们当然也可以直接使用printf("%d\n", a.size);但是区别就在于这里有名词叫封装,把size封装。因为当日后或许算法更加复杂,直接使用方法就不可以了,那么这个就能突显出优势
void array_free(Array *a) {
free(a->array);
a->array = NULL;
a->size = 0;
}
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]);
}//为什么要返回指针,而不是直接int?
/*要是想要查看某index的元素,需要用printf("%d", *array_at(&a, 0));
为什么还要这么麻烦加个*呢?
我们可以看到这里没有赋值的方法,而这样做的好处,就是能够赋值
例如:*array_at(&a, 0) = 10;
*/
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; i++) p[i] = a->array[i];
free(a->array);
a->array = p;
a->size += more_size;
}
int main(int argc, char const *argv[]) {
Array a = array_create(100);
printf("%d\n", array_size(&a));
array_set(&a, 0, 10);
printf("%d\n", *array_at(&a, 0));
int number = 0;
int cnt = 0;
while(number != -1) {
scanf("%d", &number);
if(number != -1) *array_at(&a, cnt++) = number;
//array_set(&a, cnt++, number);
}
array_free(&a);
return 0;
}
11.2 链表
可变数组有着缺陷
- 当遇到内存超额的时候,就会错误
- 那么思考一下,如果我们不是让内存更大,而是直接申请另一个block,把它们连起来,就告诉它下一个block在哪里
- 让一个数组指向下一个数组,如此类推
11.2.2 链表
- 结点由数据和指针两部分组成
代码
#include "node.h"
#include <stdio.h>
#include <stdlib.h>
typedef struct _node {
int value;
struct _node *next;
} Node;
void add(Node* head, int number);
int main(int argc, char const *argv[]) {
Node *head = NULL;
int number;
do {
scanf("%d", &number);
if(number != -1) {
head = add(head, number)
}
}while(number != -1);
return 0;
}
Node* add(Node* head, int number) {
//add to linked_list
Node *p = (Node*)malloc(sizeof(Node));
p->value = number;
p->next = NULL;
//find the last
Node *last = head;
if(last) {
while(last->next) {//到NULL会变为false
last = last->next;
}
last -> next = p;
} else {
head = p;
}
return head;
}
目标
做一个学生成绩管理系统
- 信息记录:序号,学生ID,成绩
- 功能菜单:插入(录入),删除,打印,保存,成绩从高到低排序
项目参考资料