C语言 笔记3
可变数组
设计一个Array库，提供数组初始化，数组数据查看和修改的功能，且数组大小可变。
array.h
/*
可变数组 */
// array_block，每次触发自动增长时增长的数量，记作一个array_block
#define ARRAY_BLOCK 10
typedef struct {
int size;
int *array;
} Array;
Array array_create(int init_size);
void array_free(Array *a);
int array_size(const Array *a);
int array_get(const Array *a,int index);
void array_set(Array *a,int index,int value);
void array_inflate(Array *a,int add_size);
Array array_create(int init_size){
// 初始化数组
Array a = {
init_size,
(int*)malloc(sizeof(int)*init_size)
};
return a;
}
void array_free(Array *a){
// 释放数组
free(a->array);
a->size = 0;
a->array = NULL;
}
int array_size(const Array *a){
// 读取数组的大小
return a->size;
}
int array_get(const Array *a,int index){
// 读取数组中的成员的值
return a->array[index];
}
void array_set(Array *a,int index,int value){
// 设置数组中成员的值
if(index >= a->size){
// 越界自动增长
int over_size = (index+1) - a->size;
int block_num = (over_size/ARRAY_BLOCK) + 1;
int add_size = block_num * ARRAY_BLOCK;
array_inflate(a,add_size);
}
// 设置值
a->array[index] = value;
}
void array_inflate(Array *a,int add_size){
// 数组增长
int *t = (int*)malloc(sizeof(int)*(a->size+add_size));
for(int i = 0; i < a->size; i++){
t[i] = a->array[i];
}
free(a->array);
a->array = t;
a->size += add_size;
}
测试样例
main.c
#include<stdio.h>
#include<stdlib.h>
#include "array.h"
#include "style.h"
int main(){
Array arr = array_create(20);
hr('-',60);
for(int i = 1; i < 20; i++){
array_set(&arr,i,i);
printf("%d ",arr.array[i]);
}
printf("\b\n");
printf("array.size => %d\n",array_size(&arr));
hr('-',60);
for(int i = 1; i < 25; i++){
array_set(&arr,i,i);
printf("%d ",arr.array[i]);
}
printf("\b\n");
printf("array.size => %d\n",array_size(&arr));
hr('-',60);
return 0;
}
输出
------------------------------------------------------------
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
array.size => 20
------------------------------------------------------------
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
array.size => 30
------------------------------------------------------------
style.h
void hr(char ch,int num){
for(int i = 0; i < num; i++){
if(i!=num-1)
printf("%c",ch);
else
printf("%c\n",ch);
}
}
链表
声明节点类型
想要建立链表,就需要有一个可以表示单个结点的结构.先声明一个结构体类型.
struct node {
int data; // 存储数据
struct node *next; // 结构体指针,指向下一结点
}
可以使用 typedef 来给结构命名.
typedef struct _node *nextNode;
struct node {
int data; // 存储数据
nextNode next; // 结构体指针,指向下一结点
}
typedef nextNode List;
创建结点
构建链表时,需要逐个创建结点,并将结点添加在链表中.创建结点可以大致分为三个步骤:
- 把结点分配到内存单元中.
- 把数据存在结点中.
- 把结点插入到链表中.
下面是创建结点的一种方法:
List listadd(List list,int number) /* 添加新节点到链表 */
{
List new_node = (List)malloc(sizeof(struct _node)); // 把结点分配到内存单元中
new_node->data = number; // 把数据存在结点中
/* 把结点插入到链表中 */
new_node->next = list;
list = new_node;
return list; // 返回链表
}
这是创建结点的一种方法,是我们的教材中讲到的一种方法.这个函数并不会对原来的链表做修改,而是返回一个链表.然后用原来的链表等于函数的返回值.类似这样:
List list = NULL;
list = listadd(list,1);
list = listadd(list,2);
还有一点,如果使用上面这种方法创建新结点,这个链表会是倒序的.如果要创建正序的链表,需要用一个遍历先找到链表的最后一个结点,然后插入新节点.
搜索链表
创建链表后,可能需要去在链表中搜索某一个特定的值.一般情况使用for循环语句去遍历一个链表:
for(p = list; p! = NULL; p = p->next){
...CODE...
}
如果在函数内有一个链表的副本,在函数内修改它不会对原链表产生影响时,可以这样写:
for(;list != NULL; list = list->next){
...CODE...
}
当然也可以使用while循环去做这件事情:
// p = list;
while(p!=NULL){
p = p->next;
...CODE...
}
因此搜索链表可以写成下面这个函数:
List listsearch(List list,int number) /* 在链表中搜索 */
{
for(; list!=NULL && list->data != number; list = list->next);
return list; // 将搜索到的结点返回
}
删除结点
删除结点大概分为三个步骤:
- 搜索到要删除的结点.
- 让前一个结点与后一个结点链接.
- free掉要删除的结点.
List listdel(List list,int number) /* 删除结点 */
{
List cur = NULL; // 存储当前结点
List prev = NULL; // 存储上一结点
for(cur = list,prev = NULL;\
cur->data!=number && list!=NULL;\
prev = cur, cur = cur->next);
if(cur == NULL) // 未找到
{
return list;
}
else if(prev == NULL) // 在首结点处
{
list = list->next;
}
else // 搜索到,且不在首结点
{
prev = cur->next;
}
free(cur);
return list;
}
结尾
创建搜索删除是我们教材中举的三个例子.当然链表远不止这些.等到以后遇到需要记得东西,再在这里加一下.