线性表
1. 顺序表
顺序表是指用一段连续的地址，依次存放数据元素的线性数据结构。此种存储方式使得顺序表的物理结构与逻辑结构都是连续的。
与数组的区别：函数中的数组被存放在栈段中，而栈段有系统限制的大小（可使用ulimit -s查看系统限制的大小，单位为KB），因此顺序表往往使用在堆段中操作管理动态数组的方式实现。
1.1 管理结点
在顺序表中，管理节点内部一般存放：数据域地址(*data)、**总容量(size)以及当前数据量(len)**等等。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Vector {
//数据域
int *data;
//总容量
int size;
//当前元素个数 或 指向末尾元素的后一位
int len;
} Vector;
//初始化
Vector *initVector(int size){
Vector *v = (Vector *) malloc(sizeof(Vertor));
v->data = (int *) malloc(sizeof(int) * size);
v->len = 0;
v->size = size;
return v;
}
//释放
void freeVector(Vector *v){
if(!v) return;
free(v->data);
free(v);
}
int main(){
//初始化size为10的线性表
Vector *v = initVector(10)
return 0;
}
1.2 顺序表的插入
//插入
//将 v->data[idx] 处变成 val
void insert(Vector *v, int idx, int val){
//判断 v 是否为空 返回
if(!v) return;
//判断 idx 是否合法
if(idx > v->len || idx < 0) return ;
//判断 v 的容量是否已满
if(v->len == v->size) return ;
//维护顺序表的特性 将 idx 及之后的元素后移
for(int i = v->len; i > idx ;i++){
v->data[i] = v->data[i - 1];
}
//在 idx 处插入数据
v->data[i] = val;
//更新当前元素个数
v->len++;
}
1.3 顺序表的删除
//删除
//将 v->data[idx] 删除
void delete(Vector *v, int idx){
if(!v) return ;
if(idx >= v->len || idx < 0) return ;
// idx 之后的元素前移
for(int i = idx; i < v->len-1; i++){
v->data[i] = v->data[i + 1];
}
v->len--;
}
1.4 顺序表的扩容
扩容：新创建 原size * 2 的空间，然后将原数据从原空间迁移到新空间
//倍增法扩容 size -> size + exsize
int expand(Vector *v){
//扩容为 size + exSize
int exSize = v->size;
int *tmp;
while(exSize){
//尝试向内存申请空间
tmp = (int *) realloc(v->data, sizeof(int) * (v->size + exSize));
//申请成功
if(tmp) break;
//申请不成功 exSize/2 继续申请
exSize >>= 1;
}
//彻底失败 未申请到空间
if(!tmp) return 0;
//扩容成功
v->data = tmp;
v->size += exSize;
return 1;
}
//插入
//将 v->data[idx] 处变成 val
void insert(Vector *v, int idx, int val){
...
if(v->len == v->size) {
//尝试扩容 扩容成功为 1 失败为 0
if(!expand(v)) return;
}
...
}
2. 链表
2.1 定义
链表是一种物理结构不连续，但可以依靠结点中的指针实现逻辑结构连续的线性数据结构。
构成链表的数据元素被称为“结点”，节点内部存放数据与指向下一个结点的指针。
//定义结点
typedef struct Node{
int val;
struct Node *next;
} Node;
//结点初始化
Node *initNode(int val){
Node *node = (Node *) malloc(sizeof(Node));
node->val = val;
node->next = NULL;
return node;
}
//释放结点
void freeNode(Node *node){
if(!node) return ;
free(node);
}
只有单一结点指针的链表的全程是“单链表”，经常被简称为链表。
链表的管理结点一般仅需要存放头结点指针(*head)。
如果需要频繁获取链表长度，管理结点中可以额外存放链表长度(len)。
//定义链表 管理结点
typedef struct List{
Node *head;
int len;
} List;
//初始化链表
List *initList() {
List *list = (List *) malloc(sizeof(List));
list->head = NULL;
list->len = 0;
return list;
}
2.2 头部插入
头插法：将新插入的节点放在 head 后，时间复杂度O（1）
//头部插入
void insertToHead(List *list, int val){
if(!list) return ;
Node *node = initNode(val);
node->next = list->head;
list->head = node;
list->len++;
}
2.3 尾部插入
尾插法：找到最后一个结点，将新节点插入。如果没有设计尾指针，则时间复杂度为O（n）。
//尾部插入
void insertToTail(List *list, int val){
if(!list) return ;
Node *node = initNode(val);
//如果list为空 则node为第一个结点 让head等于node
//判断条件可更改为list->len == 0
if(list->head == NULL){
list->head = node;
list->len++;
return ;
}
Node *p = list->head;
while(p->next != NUll){
p = p->next;
}
p->next = node;
list->len++;
}
//测试
int main(){
List *list1 = initList();
List *list2 = initList();
for(int i = 0;i <= 10;i += 2){
insertToHead(list1,i);
}
Node *p = list1->head;
while(p){
printf("%d -> ",p->val);
p = p->next;
}
printf("\n");
for(int i = 1;i <= 10;i += 2){
insertToTail(list2,i);
}
Node *q = list2->head;
while(q){
printf("%d -> ",q->val);
q = q->next;
}
printf("\n");
return 0;
}
输出结果：
2.4 任意位置插入
//任意位置的插入
// idx = 0 待插入结点为头结点
// idx > 0 插入至第 i 个结点后
void insert(List *list, int idx, int val){
if(!list) return ;
if(idx > list->len || idx < 0) return ;
if(idx == 0){
//头插法
insertToHead(list,val);
return;
}
Node *node = initNode(val);
//结点索引为 0
Node *p = list->head;
//p 找到第 idx - 1个结点
// i = 1 结点索引为 1
// i = 2 结点索引为 2
// i = idx - 1 结点索引为 idx - 1
for(int i = 1;i <= idx - 1;i++){
p = p->next;
}
//插入
node->next = p->next;
p->next = node;
list->len++;
}
2.5 任意位置删除
//任意位置的删除
void remove(List *list, int idx){
if(!list) return ;
if(idx > list->len || idx < 0) return ;
//p为0号索引结点
Node *p = list->head;
//删除索引为 0 的结点 更改head
if(idx == 0){
list->head = p->next;
list->len--;
freeNode(p);
return;
}
//找到idx-1个结点
for(int i = 1;i <= idx - 1;i ++){
p = p->next;
}
Node *node = p->next;
//删除
p->next = p->next->next;
list->len--;
freeNode(node);
}
2.6 虚头结点
在需要特殊处理头结点的时候，可以实现一个带有虚头结点的链表。在链表初始化或在某些操作执行时，将一个额外的结点放在头指针执行的地方。虚头结点可以使得整个链表永远不空，永远有头。所以拥有虚头结点的链表在处理各类结点操作时会更加便捷。
任意位置插入：不需要特殊考虑插入位置是否在链表头部。
任意位置删除：不需要特殊考虑删除的结点是否是链表的第一个结点。
//结点部分没有改动
//定义结点
typedef struct Node{
int val;
struct Node *next;
} Node;
//结点初始化
Node *initNode(int val){
Node *node = (Node *) malloc(sizeof(Node));
node->val = val;
node->next = NULL;
return node;
}
//释放结点
void freeNode(Node *node){
if(!node) return ;
free(node);
}
//定义链表 管理结点
typedef struct List{
Node *head;
int len;
} List;
//初始化链表
List *initList() {
List *list = (List *) malloc(sizeof(List));
//变动 ：初始化的时候赋予一个结点 任意数值都可以
list->head = initNode(-1);
list->len = 0;
return list;
}
//头部插入
void insertToHead(List *list, int val){
if(!list) return ;
Node *node = initNode(val);
// 变动
node->next = list->head->next;
// 变动
list->head->next = node;
list->len++;
}
//尾部插入
void insertToTail(List *list, int val){
if(!list) return ;
Node *node = initNode(val);
//变动 删除对链表是否为空的判断 可以直接进行插入
//此处可以谢伟 Node *p = list->head->next;
Node *p = list->head;
while(p->next != NULL){
p = p->next;
}
p->next = node;
list->len++;
}
//任意位置的插入
void insert(List *list, int idx, int val){
if(!list) return ;
if(idx > list->len || idx < 0) return ;
//变动 ： 删除对链表是否为空的判断
Node *node = initNode(val);
Node *p = list->head;
for(int i = 1;i <= idx;i++){
p = p->next;
}
//插入
node->next = p->next;
p->next = node;
list->len++;
}
//任意位置的删除
void remove(List *list, int idx){
if(!list) return ;
if(idx > list->len || idx < 0) return ;
Node *p = list->head;
for(int i = 1;i <= idx;i ++){
p = p->next;
}
Node *node = p->next;
//删除
p->next = p->next->next;
list->len--;
freeNode(node);
}
