一、可变数组

编写可变数组函数库

创建数组
回收数组
获取数组中单元个数
访问数组中的某个单元
增长数组长度

定义Array结构体：

定义为指针类型的结构体，似乎可以简化某些函数的调用传递参数，节省内存空间？

#ifndef ARRAY_H
#define ARRAY_H

typedef struct{
    int *array;
    int size;
}*Array;

#endif

但是，当我们在函数内部创建变量的时候，这个时候a指向的是已经存在的内存空间。

void test()
{
	Array a;
}

所以，一般情况下，定义结构体变量不要加*，不要定义指针类型

#ifndef ARRAY_H
#define ARRAY_H

typedef struct{
    int *array;
    int size;
}Array;

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 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;//防止重复调用，free(Null)是无害操作
	a->size = 0;
	
}

获取数组大小

思考：为什么不直接a.size获取大小？

目的：封装，保护了a的size，防止被修改，也利于后期维护

int array_size(const Array *a)
{
   return a->size; 
}

获取数组中对应元素的位置

思考：为什么要返回int类型指针而不直接返回int

使用array_at(&a,0)取地址
使用*array_at(&a,0)=10;可以直接进行赋值操作

当然，也可以重新编写array_set，array_get两个函数，分别用于赋值和取值

int* array_at(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));//定义缓存指针，申请more_size个内存空间
    int i;
    for(i=0;i<a->size;i++){
        p[i]=a->array[i];//将array原本的内存空间中的值赋给p
    }
    free(a->array);//释放内存空间
    a->array = p;//将p值还原给a
    a->size += more_size;//增大a的size大小
}

不断写入数组内容

一直循环下去，总会出现数组越界的情况。

于是，继续修改array_at

引入block概念

二、可变数组的缺陷

拷贝时间开销大
在内存受限的情况下，可能难以申请到更大的内存空间

解决方案：
不去修改原来的内存空间，链接1个block即可拓展数组长度

三、链表

链表中的元素簇称为“节点”

每个节点仅包含两个部分:

数据
指向下一个节点的指针

typedef struct _node{
    int value;
    struct _node next;
}Node;

思考：为什么不用：

1	struct Node next;

因为在这一行还没有执行Node的类型重定义，编译器无法识别。

使用struct _node{

}定义了struct _node类型的结构体

使用typedef … Node重定义了struct _node类型

程序：循环输入数字，如果为-1则退出，

1. 定义head

1	Node *head = Null;

2.定义第一个节点

1
2
3

Node *p = (Node*)malloc(sizeof(Node));
p->value = number;
p->next = Null;

3. 定义last

Node *last = head;
while(last -> next)
{
    last = last -> next;
}
last->next = p;

4. 链表函数——添加节点

实现一个创建节点的函数：

缺点：函数内部对head进行改变，但是并不影响外部的head（PS:这里的head为指针）

tips：尽量少用全局变量

void 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){//如果last指向非空
        while(last->next){//last的nest指向非空
            last = last->next;//last等于last指向的next
        }
        // attach
        last->next = p;//last指向的next等于p
    }else{
        head = p;//修改head
    }
}

| |

修改程序

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){//如果last指向非空
        while(last->next){//last的nest指向非空
            last = last->next;//last等于last指向的next
        }
        // attach
        last->next = p;//last指向的next等于p
    }else{
        head = p;//修改head
    }
    return head; // <================= 将head返回出去
}

在主程序中，即可实现改变head的操作，但是这也存在一个缺点，如果忘记调用head = …，程序会报错，封装还不够完美

1	head = add(...);

| |

第三种方案，传head改为传递head的指针（实际上是指针的指针）

tips：数据结构

实际上，现在这个函数，return返回值，以及主程序中的赋值都可以不进行，提高了程序的易用性，根本原因是因为pHead是head的指针，即指针的指针

Node* add(Node** pHead,int number)
{
    //add to linked-list
    Node *p = (Node*)malloc(sizeof(Node));
    p->value = number;
    p->next = NULL;
    //find the last
    Node *last = *pHead;
    if(last){//如果last指向非空
        while(last->next){//last的nest指向非空
            last = last->next;//last等于last指向的next
        }
        // attach
        last->next = p;//last指向的next等于p
    }else{
        *pHead = p;//修改head
    }
    return *pHead; 
}

| |

第四种方案，添加一个List类型结构体

1
2
3

typedef struct _list{
    Node *head;
}List;

这样，函数可以改写为

void add(List *plist,int number)
{
    //add to linked-list
    Node *p = (Node*)malloc(sizeof(Node));
    p->value = number;
    p->next = NULL;
    //find the last
    Node *last = plist->head;
    if(last){//如果last指向非空
        while(last->next){//last的nest指向非空
            last = last->next;//last等于last指向的next
        }
        // attach
        last->next = p;//last指向的next等于p
    }else{
        plist->head = p;//修改head
    }
}

思考：调用这个函数，last每次都要从head开始指向，执行了没有必要的操作，如何让函数执行完之后，last指向保持上一次的指向？

| |

typedef struct _list{
    Node *head;
    Node *tail;
}List;

实现：

在 List 结构体中添加一个指向链表尾节点的指针 tail，然后每次添加节点时，直接更新 tail 的指向。这样可以避免每次都从头开始遍历链表，优化了插入操作的效率。

修改后的代码示例

修改 List 结构体：添加一个 tail 指针，指向链表的最后一个节点。
修改 add 函数：在每次添加新节点时，直接更新 tail 指针。

void add(List *plist,int number)
{
    //add to linked-list
    Node *p = (Node*)malloc(sizeof(Node));
    p->value = number;
    p->next = NULL;
    //find the last
    if(plist->tail){//如果尾节点存在
            plist->tail->next = p;//尾节点的next指向新节点
    }else{
        plist->head = p;//头节点指向新节点
    }
    plist->tail = p;  // 更新 tail 为新添加的节点
}

这种方式通过维护一个指向尾节点的指针，可以避免每次添加节点都从头遍历，优化了链表操作的效率。

5. 链表函数——打印

void print(List *list){
    Node *p;
    for(p=list->head;p;p=p->next){
        printf("%d\t",p->value);
        printf("\n");
    }
}

6. 链表函数——删除

7. 链表函数——清除

void clear(List *plist) {
    Node *current = plist->head;
    Node *nextNode;

    while (current != NULL) {
        nextNode = current->next;  // 保存下一个节点
        free(current);             // 释放当前节点
        current = nextNode;        // 移动到下一个节点
    }

    plist->head = NULL;  // 清空头指针
    plist->tail = NULL;  // 清空尾指针
}