算法-数组与链表

「算法 algorithm」是在有限时间内解决特定问题的一组指令或操作步骤。

「数据结构 data structure」是计算机中组织和存储数据的方式。

算法设计追求两个层面的目标：

找到问题解法：算法需要在规定的输入范围内，可靠地求得问题的正确解。
寻求最优解法：同一个问题可能存在多种解法，我们希望找到尽可能高效的算法。

数组

「数组 array」是一种线性数据结构，其将相同类型元素存储在连续的内存空间中。将元素在数组中的位
置称为该元素的「索引 index」。

数组常用操作

1.初始化数组

/* 初始化数组 */
int array[5] = { 0 }; // { 0, 0, 0, 0, 0 }
int nums[5] = { 1, 3, 2, 5, 4 };

2. 访问元素

/* 访问元素 */
int access(int *nums, int index) {
	// 获取并返回元素
	int randomNum = nums[index];
	return randomNum;
}

3.插入元素

/* 在数组的索引 index 处插入元素 num */
void insert(int *nums, int size, int num, int index) {
	// 把索引 index 以及之后的所有元素向后移动一位
	for (int i = size - 1; i > index; i--) {
		nums[i] = nums[i - 1];
	}
	// 将 num 赋给 index 处元素
	nums[index] = num;
}

4. 删除元素

/* 删除索引 index 处元素 */
// 注意： stdio.h 占用了 remove 关键词
void removeItem(int *nums, int size, int index) {
	// 把索引 index 之后的所有元素向前移动一位
	for (int i = index; i < size - 1; i++) {
		nums[i] = nums[i + 1];
	}
}

数组的插入与删除操作有以下缺点 :

时间复杂度高：数组的插入和删除的平均时间复杂度均为 𝑂(𝑛) ，其中 𝑛 为数组长度。
丢失元素：由于数组的长度不可变，因此在插入元素后，超出数组长度范围的元素会丢失。
内存浪费

5. 遍历数组

/* 遍历数组 */
void traverse(int *nums, int size) {
	int count = 0;
	// 通过索引遍历数组
	for (int i = 0; i < size; i++) {
		printf("%d\n", nums[i]);
	}
}

6. 查找元素

/* 在数组中查找指定元素 */
int find(int *nums, int size, int target) {
	for (int i = 0; i < size; i++) {
		if (nums[i] == target)
			return i;
	}
	return -1;
}

7. 扩容数组

/* 扩展数组长度 */
int *extend(int *nums, int size, int enlarge) {
	// 初始化一个扩展长度后的数组
	int *res = (int *)malloc(sizeof(int) * (size + enlarge));
	// 将原数组中的所有元素复制到新数组
	for (int i = 0; i < size; i++) {
		res[i] = nums[i];
	}
	// 初始化扩展后的空间
	for (int i = size; i < size + enlarge; i++) {
		res[i] = 0;
	}
	// 返回扩展后的新数组
	return res;
}

数组优点与局限性

优点 :

空间效率高: 数组为数据分配了连续的内存块，无须额外的结构开销。
支持随机访问: 数组允许在 𝑂(1) 时间内访问任何元素。
缓存局部性: 当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓
存来提升后续操作的执行速度。

缺点 :

插入与删除效率低。
长度不可变。
空间浪费。

链表

「链表 linked list」是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。

链表的组成单位是「节点 node」对象。每个节点都包含两项数据：节点的“值”和指向下一节点的“引用”。

/* 链表节点结构体 */
typedef struct ListNode {
    int val;               // 节点值
    struct ListNode *next; // 指向下一节点的指针
} ListNode;

/* 构造函数 */
ListNode *newListNode(int val) {
    ListNode *node;
    node = (ListNode *) malloc(sizeof(ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

链表常用操作

1. 初始化链表

/* 初始化链表 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各个节点
ListNode* n0 = newListNode(1);
ListNode* n1 = newListNode(3);
ListNode* n2 = newListNode(2);
ListNode* n3 = newListNode(5);
ListNode* n4 = newListNode(4);
// 构建节点之间的引用
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;

2. 插入节点

/* 在链表的节点 n0 之后插入节点 P */
void insert(ListNode *n0, ListNode *P) {
    ListNode *n1 = n0->next;
    P->next = n1;
    n0->next = P;
}

3.删除节点

/* 删除链表的节点 n0 之后的首个节点 */
// 注意：stdio.h 占用了 remove 关键词
void removeItem(ListNode *n0) {
    if (!n0->next)
        return;
    // n0 -> P -> n1
    ListNode *P = n0->next;
    ListNode *n1 = P->next;
    n0->next = n1;
    // 释放内存
    free(P);
}

4.访问节点

/* 访问链表中索引为 index 的节点 */
ListNode *access(ListNode *head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == NULL)
            return NULL;
        head = head->next;
    }
    return head;
}

5.查找节点

/* 在链表中查找值为 target 的首个节点 */
int find(ListNode *head, int target) {
    int index = 0;
    while (head) {
        if (head->val == target)
            return index;
        head = head->next;
        index++;
    }
    return -1;
}

常见链表类型

单向链表
环形链表
双向链表

链表典型应用

栈与队列
哈希表
图

列表

「列表 list」是一个抽象的数据结构概念，它表示元素的有序集合，支持元素访问、修改、添加、删除和遍历等操作，无须使用者考虑容量限制的问题。C语言，列表可以基于链表或数组实现。

许多编程语言中的标准库提供的列表是基于动态数组实现的，例如 Python 中的 list 、Java 中的 ArrayList 、C++ 中的 vector 和 C# 中的 List 等。在接下来的讨论中，我们将把“列表”和“动态数组”视为等同的概念。

/* 列表类 */
typedef struct {
    int *arr;        // 数组（存储列表元素）
    int capacity;    // 列表容量
    int size;        // 列表大小
    int extendRatio; // 列表每次扩容的倍数
} MyList;

/* 构造函数 */
MyList *newMyList() {
    MyList *nums = malloc(sizeof(MyList));
    nums->capacity = 10;
    nums->arr = malloc(sizeof(int) * nums->capacity);
    nums->size = 0;
    nums->extendRatio = 2;
    return nums;
}

/* 析构函数 */
void delMyList(MyList *nums) {
    free(nums->arr);
    free(nums);
}

/* 获取列表长度 */
int size(MyList *nums) {
    return nums->size;
}

/* 获取列表容量 */
int capacity(MyList *nums) {
    return nums->capacity;
}

/* 访问元素 */
int get(MyList *nums, int index) {
    assert(index >= 0 && index < nums->size);
    return nums->arr[index];
}

/* 更新元素 */
void set(MyList *nums, int index, int num) {
    assert(index >= 0 && index < nums->size);
    nums->arr[index] = num;
}

/* 在尾部添加元素 */
void add(MyList *nums, int num) {
    if (size(nums) == capacity(nums)) {
        extendCapacity(nums); // 扩容
    }
    nums->arr[size(nums)] = num;
    nums->size++;
}

/* 在中间插入元素 */
void insert(MyList *nums, int index, int num) {
    assert(index >= 0 && index < size(nums));
    // 元素数量超出容量时，触发扩容机制
    if (size(nums) == capacity(nums)) {
        extendCapacity(nums); // 扩容
    }
    for (int i = size(nums); i > index; --i) {
        nums->arr[i] = nums->arr[i - 1];
    }
    nums->arr[index] = num;
    nums->size++;
}

/* 删除元素 */
// 注意：stdio.h 占用了 remove 关键词
int removeItem(MyList *nums, int index) {
    assert(index >= 0 && index < size(nums));
    int num = nums->arr[index];
    for (int i = index; i < size(nums) - 1; i++) {
        nums->arr[i] = nums->arr[i + 1];
    }
    nums->size--;
    return num;
}

/* 列表扩容 */
void extendCapacity(MyList *nums) {
    // 先分配空间
    int newCapacity = capacity(nums) * nums->extendRatio;
    int *extend = (int *)malloc(sizeof(int) * newCapacity);
    int *temp = nums->arr;

    // 拷贝旧数据到新数据
    for (int i = 0; i < size(nums); i++)
        extend[i] = nums->arr[i];

    // 释放旧数据
    free(temp);

    // 更新新数据
    nums->arr = extend;
    nums->capacity = newCapacity;
}

/* 将列表转换为 Array 用于打印 */
int *toArray(MyList *nums) {
    return nums->arr;
}

目录CONTENT

算法-数组与链表

算法-数组与链表

数组

数组常用操作

数组优点与局限性

链表

链表常用操作

常见链表类型

链表典型应用

列表

评论区