数组与链表

数组

数组是一种线性数据结构，其将相同类型的元素存储在连续的内存空间中。

数组常用操作

1. 初始化数组
   在数组中访问元素非常高效，我们可以在$O(1)$时间内随机访问数组中的任意一个元素

   int randomAccess(int *nums,int size)
   {
       int randomIndex=rand()%size;
       int randomNum=nums[randomIndex];
       return randomNum;
   }

2. 增删元素
   数组元素在内存中是紧挨着的，它们之间没有空间再存放任何数据。如果想在数组中间插入一个元素，则需要将该元素之后的所有元素都向后移动一位，之后再把元素赋值给该索引。

   void insert(int*nums,int size,int num,int index)
   {
       for(int i=size-1;i>index;i--)
       {
           nums[i]=nums[i-1];
       }
       nums[index]=num;
   }

   同理，删除某索引处的元素时，则需要把该索引之后的元素都向前移动一位。

   void delete(int *nums,int size,int index)
   {
       for(int i=index;i<size-1,i++)
       {
           nums[i]=nums[i+1];
       }
   }

3. 遍历数组
   既可以通过索引遍历数组，也可以直接遍历获取数组中的每个元素

   void traverse(int*nums,int size)
   {
       int count=0;
       for(int i=0;i<size;i++)
       {
           count+=nums[i];
       }
   }

4. 查找元素
   数组是线性数据结构，所以对其进行查找的操作被称为“线性查找”。

   int find(int*nums,int size,int target)
   {
       for(int i=0;i<size;i++)
       {
           if(nums[i]==target)
               return i;
       }
       return -1;
   }

5. 扩容数组
   在大多数编程语言中，数组的长度是不可变的。如果我们希望扩容数组，则需重新建立一个更大的数组，然后把原数组元素依次复制到新数组。

   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;
   }

链表

链表是一种线性数据结构，其中每一个元素都是一个节点对象，各个节点通过“引用”相连接，引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。链表的设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。

定义链表结构

/* 链表节点结构体 */
typedef struct ListNode
{
    int val;
    struct ListNode *next;
}ListNode;

/* 构造函数 */
ListNode *newListNode(int val)
{
    ListaNode *node; // 定义头节点
    node=(ListNode*)malloc(sizeof(ListNode)); // 为链表的第一个元素分配内存
    node->val=val; // 存储节点值
    node->next=NULL; // 下一个节点设为空 
    return node;
}

链表常用操作

1. 初始化链表
   分为两步：1.初始化各个节点对象 2.构建节点之间的引用关系

   /* 初始化链表 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. 增删节点
   插入节点只需改变两个节点引用（指针）即可，时间复杂度为$O(1)$

   void insert(ListNode *old1,ListNode *new)
   {
       ListNode *old2 = old1->next;
       new->next = old2;
       old1->next = new;
   }

   删除节点只需改变一个节点的引用即可

   /* 删除链表的节点 n0 之后的首个节点 */
   // 注意：stdio.h 占用了 remove 关键词
   void removeItem(ListNode *n0)
   {
       if(!n0->next)
           return;
       ListNode *P=n0->next;// 获取n0后第一个
       ListNode *n1=P->next;// 获取n0后第二个
       n0->next=n1;//链接n0和其后第二个
       free(P);
   }

3. 访问节点
   在链表中访问节点的效率较低。程序需要从头节点出发，逐个向后遍历，直至找到目标节点。

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

4. 查找节点
   遍历链表，查找其中值为目标值的节点，输出该节点在链表中的索引。此过程也属于线性查找。

   int find(ListNode *head,int target)
   {
       int index=0;
       while(head)
       {
           if(head->val==target)
               return index;
           head=head->next;
           index++;
       }
       return -1;
   }

常见链表类型

1. 单向链表：即上文所介绍的普通链表
2. 环形链表：由单向链表的尾结点指向头节点得到，环形链表中任意节点都能视作头节点。
3. 双向链表：其记录了两个方向的引用（后继节点和前驱节点），与单向链表相比其更具灵活性，可从两个方向遍历。

   /* 双向链表节点结构体 */
   typedef struct ListNode
   {
       int val;
       struct ListNode *next;
       struct ListNode *prev;
   }ListNode;
   ListNode *newListNode(int val)
   {
       ListNode*node;
       node=(ListNode*)malloc(sizeof(ListNode));
       node->val;
       node->next=NULL;
       node->prev=NULL;
       return node;
   }

列表

链表可以看作一个列表，其支持元素增删查改操作，并且可以灵活动态扩容。数组也支持元素增删查改，但由于其长度不可变，因此只能看作一个具有长度限制的列表，故可以使用动态数组来实现列表。

/* 初始化列表 */
// 需注意，C++ 中 vector 即是本文描述的 nums
// 无初始值
vector<int> nums1;
// 有初始值
vector<int> nums = { 1, 3, 2, 5, 4 };

list.cpp

/* 访问元素 */
int num = nums[1];  // 访问索引 1 处的元素

/* 更新元素 */
nums[1] = 0;  // 将索引 1 处的元素更新为 0

/* 清空列表 */
nums.clear();

/* 在尾部添加元素 */
nums.push_back(1);
nums.push_back(3);
nums.push_back(2);
nums.push_back(5);
nums.push_back(4);

/* 在中间插入元素 */
nums.insert(nums.begin() + 3, 6);  // 在索引 3 处插入数字 6

/* 删除元素 */
nums.erase(nums.begin() + 3);      // 删除索引 3 处的元素

/* 通过索引遍历列表 */
int count = 0;
for (int i = 0; i < nums.size(); i++) {
    count += nums[i];
}

/* 直接遍历列表元素 */
count = 0;
for (int num : nums) {
    count += num;
}
/* 拼接两个列表 */
vector<int> nums1 = { 6, 8, 7, 10, 9 };
// 将列表 nums1 拼接到 nums 之后
nums.insert(nums.end(), nums1.begin(), nums1.end());
/* 排序列表 */
sort(nums.begin(), nums.end());  // 排序后，列表元素从小到大排列

/* 列表类 */
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;
}