Chao的随笔
Search K

Appearance

常见操作线性结构 ​

数组 ​

C 语言中，数组是具有相同类型的数据元素的集合。在所有的数据结构中，数组算是最常见、最简单的一种数据结构。

数组元素在内存中占用连续的存储空间，每个元素的地址依次递增（递增大小为元素类型的字节数）。

数组名的含义：数组名代表数组的首地址（第一个元素的地址），是一个常量指针（不能被赋值）。例如：arr 等价于 &arr[0]，除了通过下标遍历数组，还可以通过指针遍历数组。

特点 ​

  • 优 点

1、查找容易（通过下标），时间复杂度为O(1)。不需要额外申请或删除空间。

2、使用下标位置索引(index)十分高效的访问任意元素，修改快

  • 缺 点

1、插入、删除元素难，效率低。（需要移动大量元素以使元素空间连续）。

2、插入操作平均需要移动n/2个元素。

3、删除操作平均需要移动(n-1)/2个元素。

4、扩展相对繁琐。一方面需要确保能提供更大区域的连续内存空间，另一方面需要将原有数据复制到新的顺序表中。

代码实现 ​

c
#include <stdio.h>
#include <stdlib.h>

/**
 * 指定下标插入一个新的元素
 */
int *insert(int *arr, int index, int element, int *arrLen)
{
    int len = *arrLen;
    // 拷贝的元素
    int *tempArr = (int *)malloc((len + 1) * sizeof(int));

    for (int i = 0; i < index; i++)
    {
        tempArr[i] = arr[i];
    }

    /**
     * 实现思路：拷贝一个新元素指定下标内容直接替换为插入的新元素，再将下标之后的元素拷贝到插入元素下标的后面
     */
    tempArr[index] = element;

    for (int i = index; i < len; i++)
    {
        tempArr[i + 1] = arr[i];
    }

    (*arrLen)++;

    return tempArr;
}

/**
 * 尾部新增一个元素
 */
int *add(int *arr, int *arrLen, int element)
{
    /**
     * 核心思路：扩容，然后对最尾部元素赋值
     */
    int len = *arrLen;
    int *tempArr = (int *)malloc((len + 1) * sizeof(int));
    for (int i = 0; i < len; i++)
    {
        tempArr[i] = arr[i];
    }

    tempArr[len] = element;
    // 通过指针地址修改传入的len值
    (*arrLen)++;
    printf("新增成功！ \n");

    return tempArr;
}

/**
 * 删除指定下标的元素
 */
void delete(int *arr, int index, int *arrLen)
{
    /**
     * 实现思路：从指定下标开始每个元素都向前移动一位，覆盖前面的元素
     */
    int len = *arrLen;
    for (int i = index; i < len - 1; i++)
    {
        arr[i] = arr[i + 1];
    }
    (*arrLen)--;
    printf("删除成功！ \n");
}

int main()
{
    int arr[] = {10, 20, 30, 40, 50};
    int len = sizeof(arr) / sizeof(int);
    int *newArr;

    printf("最初的元素 \n");
    for (int i = 0; i < len; i++)
    {
        printf(" arr[%d] = %d \n", i, arr[i]);
    }

    newArr = insert(arr, 2, 99, &len);

    printf("插入后的元素 \n");
    for (int i = 0; i < len; i++)
    {
        printf(" arr[%d] = %d \n", i, newArr[i]);
    }

    delete (newArr, 3, &len);
    printf("删除后的元素 \n");
    for (int i = 0; i < len; i++)
    {
        printf(" arr[%d] = %d \n", i, newArr[i]);
    }

    int *newArr2 = add(newArr, &len, 100);
    printf("新增后的元素 \n");
    for (int i = 0; i < len; i++)
    {
        printf(" arr[%d] = %d \n", i, newArr2[i]);
    }

    return 0;
}

输出结果

最初的元素 
 arr[0] = 10 
 arr[1] = 20 
 arr[2] = 30 
 arr[3] = 40 
 arr[4] = 50 
插入后的元素 
 arr[0] = 10 
 arr[1] = 20 
 arr[2] = 99
 arr[3] = 30
 arr[4] = 40
 arr[5] = 50
删除成功！
删除后的元素
 arr[0] = 10
 arr[1] = 20
 arr[2] = 99
 arr[3] = 40
 arr[4] = 50
新增成功！
新增后的元素
 arr[0] = 10
 arr[1] = 20
 arr[2] = 99
 arr[3] = 40
 arr[4] = 50
 arr[5] = 100

通过指针遍历数组 ​

除了常规的通过下标遍历数组外，还可以使用指针遍历数组元素

c
#include <stdio.h>

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int len = sizeof(arr) / sizeof(arr[0]);
    int *p = arr;  // 指针指向数组首元素
    
    printf("指针遍历数组：");
    for (int i = 0; i < len; i++) {
        printf("%d ", *(p + i));  // p+i 指向第i个元素，解引用获取值
        // 等价于 printf("%d ", p[i]);
    }
    
    return 0;
}
c
#include <stdio.h>

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int len = sizeof(arr) / sizeof(arr[0]);
    int *p = arr;  // 指针指向数组首元素

    printf("使用p++遍历数组：");
    // 循环len次，每次移动指针并访问元素
    for (int i = 0; i < len; i++) {
        printf("%d ", *p);  // 访问当前指针指向的元素
        p++;  // 指针向后移动一位（指向 next 元素）
    }

    return 0;
}

链表 ​

链表当时也是博主学习数据结构时候的噩梦，那时候没有好好学习，现在才追悔莫及。

链表是一个线性结构，由一系列结点(Node)组成，每个结点包含一个数据元素和一个指向下一个结点的指针(Pointer)。所有结点通过指针相连，形成一个链式结构。通常我们将链表中的第一个结点称为头结点。

data ：数据域，存放结点的值。

next ：指针域，存放结点的直接后继的地址。

物理结构：与数组不同，链表中的结点需要自行组织，向系统申请很多分散在内存各处的结点，每个结点都保存了当前结点的数据和下一个结点的地址(指针)，通过指针将结点串成一串。

链表的分类 ​

链表又分为单链表、双链表、循环单链表、循环双链表。

特点 ​

优点

*1、插入和删除操作效率高。

*2、动态扩展性能更好，链表不需要像数组那样预先指定固定的大小，而是可以随时动态的增长或缩小。链表是真正的动态数据结构，不需要处理固定容量的问题。

缺点

*1、查找慢。由于链表中的结点不是连续存储的，无法像数组一样根据索引直接计算出每个结点的地址。必须从头结点开始遍历链表，直到找到目标结点，这导致了链表的随机访问效率较低。

*2、额外的存储空间。链表的每个结点都需要存储指向下一个结点的指针，这会占用额外的存储空间。所以，相比于数组，链表需要更多的内存空间来存储相同数量的数据元素。

代码实现 ​

c
#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node *next;
} Node;

typedef struct
{
    Node *head;
    size_t size;
} LinkedList;

/**
 * 初始化链表
 */
void initLinkedList(LinkedList *list)
{
    list->size = 0;
    list->head = NULL;
}

/**
 * 遍历链表
 */
void printList(LinkedList *list)
{
    Node *node = (Node *)malloc(sizeof(Node));
    node = list->head;
    for (int i = 0; i < list->size; i++)
    {
        printf("i = %d ; node = %d \n", i, node->data);
        node = node->next;
    }
}

/**
 * 获取链表长度
 */
size_t getLength(const LinkedList *list)
{
    return list->size;
}

/**
 * 指定下标插入元素
 */
void insertAt(LinkedList *list, size_t index, int element)
{

    if (index > list->size || index < 0)
    {
        printf("指针越界 \n");
    }
    else
    {
        // 创建待插入的元素
        Node *node = (Node *)malloc(sizeof(Node));
        // 赋值插入数据
        node->data = element;

        if (index == 0)
        {
            // 插入的新元素下一节点指向头节点
            node->next = list->head;
            // 此时新元素是头节点了，链表头节点应该指向新插入的元素
            list->head = node;
        }
        else
        {
            // pre保存待删除节点的前一个节点
            Node *pre = list->head;
            // 以index-1为最大值，移动临时头节点 index-1 次，此时pre就指向了待插入节点的前一个节点
            for (int i = 0; i < index - 1; i++)
            {
                pre = pre->next;
            }
            // 修改pre next之前，先将新节点next指向pre next
            node->next = pre->next;
            // 然后待插入前一节点位置指向新节点即可
            pre->next = node;
        }
        // 插入后修改链表长度
        list->size++;
    }
}

// 在链表末尾插入元素
void insertEnd(LinkedList *list, int element)
{
    insertAt(list, list->size, element);
}

/**
 * 删除指定元素并返回删除的元素
 */
int deleteAt(LinkedList *list, size_t index)
{
    // 待返回需要要删除的元素
    int delVal = -1;
    if (index < 0 || index > list->size)
    {
        printf("指针越界 \n");
    }
    else
    {
        if (index == 0)
        {
            // 保存要删除的节点
            Node *current = list->head;
            delVal = current->data;
            // 删除节点，即移动头节点到下一个节点，释放原头节点即可
            list->head = current->next;
            free(current);
        }
        else
        {
            // 保存待删除节点的前一节点
            Node *pre = list->head;
            for (int i = 0; i < index - 1; i++)
            {
                // 移动index - 1次就pre此时就移动到了待删除节点的前一节点
                pre = pre->next;
            }
            // 待删除的节点
            Node *current = pre->next;
            delVal = current->data;
            // 删除节点前一节点直接指向待删除结点的下一节点，即删除了该节点
            pre->next = current->next;
            // 释放删除的节点
            free(current);
        }
        // 删除节点后修改链表长度
        list->size--;
        return delVal;
    }
}

/**
 * 删除末尾元素
 */
int deleteEnd(LinkedList *list)
{
    return deleteAt(list, list->size - 1);
}

/**
 * 获取指定位置元素
 */
int getElementAt(const LinkedList *list, size_t index)
{
    if (index > list->size || index < 0)
    {
        printf("指针越界 \n");
        return;
    }
    else
    {           
        Node *current = list->head;
        for (int i = 0; i < index; i++)
        {
            current = current->next;
        }
        return current->data;
    }
}

/**
 * 修改指定位置元素
 */
void modifyAt(LinkedList *list, size_t index, int newValue)
{
    if (index < 0 || index > list->size)
    {
        printf("指针越界 \n");
    }
    else
    {
        // pre指向了要替换下标的前一个节点
        Node *current = list->head;
        for (int i = 0; i < index ; i++)
        {
            current = current->next;
        }
        current->data = newValue;
    }
}

/**
 * 释放链表内存
 */
void destroyLinkedList(LinkedList *list)
{
    Node *current = list->head;
    for (int i = 0; i < list->size; i++)
    {
        // 定义一个临时节点保存当前节点
        Node *temp = current;
        current = current->next;
        // 然后释放临时节点，即可将这个地址内存释放
        free(temp);
    }

           list->size = 0;
    list->head = NULL;
}

int main()
{

    LinkedList list;

    initLinkedList(&list);

    insertAt(&list, 0, 4);
    insertAt(&list, 0, 3);
    insertAt(&list, 0, 2);
    insertAt(&list, 0, 1);
    printList(&list);

    insertAt(&list, 2, 99);
    insertAt(&list, 2, 200);
    printf("insertAt 插入后：\n");
    printList(&list);

    printf("insertEnd 插入后：\n");
    insertEnd(&list, 999);
    printList(&list);

    int del = deleteAt(&list, 2);
    printf("删除的元素：%d \n", del);
    printList(&list);

    int del1 = deleteEnd(&list);
    printf("删除末尾元素： %d \n", del1);
    printList(&list);

    int getVal = getElementAt(&list, 2);
    printf("getElementAt value:%d \n", getVal);

    modifyAt(&list,2,199);
    printf("修改节点元素之后：\n");
    printList(&list);

    destroyLinkedList(&list); // 销毁链表
    printf("链表销毁成功!\n");
    printList(&list);
    
    return 0;
}

输出结果

i = 0 ; node = 1 
i = 1 ; node = 2 
i = 2 ; node = 3 
i = 3 ; node = 4 
insertAt 插入后：
i = 0 ; node = 1 
i = 1 ; node = 2 
i = 2 ; node = 200 
i = 3 ; node = 99 
i = 4 ; node = 3 
i = 5 ; node = 4 
insertEnd 插入后：
i = 0 ; node = 1 
i = 1 ; node = 2 
i = 2 ; node = 200 
i = 3 ; node = 99 
i = 4 ; node = 3 
i = 5 ; node = 4 
i = 6 ; node = 999 
删除的元素：200 
i = 0 ; node = 1 
i = 1 ; node = 2
i = 2 ; node = 99
i = 3 ; node = 3
i = 4 ; node = 4
i = 5 ; node = 999
删除末尾元素： 999
i = 0 ; node = 1
i = 1 ; node = 2
i = 2 ; node = 99
i = 3 ; node = 3
i = 4 ; node = 4
getElementAt value:99
修改节点元素之后：
i = 0 ; node = 1
i = 1 ; node = 2
i = 2 ; node = 199
i = 3 ; node = 3
i = 4 ; node = 4
链表销毁成功!

栈 ​

栈(stack)，是限制在只能在表的一端进行插入和删除操作的线性表。应用范围非常广泛。生活中也有栈的场景，比如堆叠的盘子、报 ，电梯中的人们，邮局的邮筒等。

特点 ​

特点：后进先出 或先进后出 的线性表。

  • 栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。栈顶由一个称为栈顶指针的位置指示器（其实就是一个变量）来指示，它是动态变化的。

  • 栈底(Bottom)：是固定不变的，不允许进行插入和删除的一端，又称为表头。

  • 空栈：不含任何元素的空表。

  • 设栈S=(a1,a2,…,an )，则a1称为栈底元素，an为栈顶元素，栈中元素按a1,a2,…,a_n的次序进栈(压栈、push)，出栈(弹栈，pop)的第一个元素应为栈顶元素，出栈顺序为：an,...,a2,a1。

代码实现 ​

c
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *data; // 动态数组存储元素
    size_t size; // 现在栈的长度
    size_t capacity; // 当前数组的容量，也就是可以容纳元素的最大个数
} Stack;

// 初始化栈
void initStack(Stack *stack, size_t capacity){
    stack->data = (int*)malloc(capacity * sizeof(int));
    stack->size = 0;
    stack->capacity = capacity;
};

size_t getSize(Stack *stack){
    return stack->size;
};

//  弹出一个元素
int pop(Stack *stack){
    if(stack->size == 0){
        return -1;
    }
    stack->size--;
    return stack->data[stack->size];
};

// 向栈顶添加一个元素
void push(Stack *stack,int element){
    // 1、先考虑当前data的容量是否充足，如果不充足需要进行扩容
    // 2、如果重组就将元素添加到栈顶，也就是表尾
    if(stack->size == stack->capacity){
        printf("当前栈容纳长度不足，进行动态扩容 \n");
        stack->capacity *= 2;
        // 进行扩容
        stack->data = (int *)realloc(stack->data,stack->capacity*sizeof(int));
    }
    stack->data[stack->size] = element;
    stack->size++;
};

// 打印整个栈元素
void printStack(Stack *stack){
    for(int i=0;i<stack->size;i++){
        printf("元素%d = %d \n",i,stack->data[i]);
    }
};

// 释放当前栈
void destroyStack(Stack *stack){
    free(stack->data);
    stack->size = 0;
    stack->capacity = 0;
}

int main(){
    Stack stack;
    initStack(&stack,2);
    push(&stack,4);
    push(&stack,3);
    push(&stack,2);
    push(&stack,1);

    printStack(&stack);

    printf("当前栈的长度为:%d \n",stack.size);

    printf("弹出一个元素：%d \n",pop(&stack));
    printStack(&stack);

    destroyStack(&stack);

    printf("当前栈的长度为:%d \n",stack.size);

    return 0;
}

打印结果

当前栈容纳长度不足，进行动态扩容 
元素0 = 4
元素1 = 3
元素2 = 2
元素3 = 1
当前栈的长度为:4
弹出一个元素：1
元素0 = 4
元素1 = 3
元素2 = 2
当前栈的长度为:0

队列 ​

队列(Queue)：也是操作受限的线性表，限制为仅允许在表的一端进行插入(入队或进队），在表的另一端进行删除(出队或离队)操作。

特点 ​

  • 队首(front) ：允许进行删除的一端称为队首。

  • 队尾(rear)： 允许进行插入的一端称为队尾。

在空队列中依次加入元素a1,a2, …, an之后，a1是队首元素，an是队尾元素。显然退出队列的次序也只能是a1,a2, …, an。

队列，是一种先进先出(First In First Out ，简称FIFO)的线性结构。类似于生活中的排队行为。

队列中没有元素时，称为空队列。

可用顺序表(数组)和链表来存储队列，队列按存储结构可分为顺序队列和链式队列两种。

常见问题 ​

出现的问题：

顺序队列中存在“假溢出”现象：尽管队列中实际元素个数可能远远小于数组大小，但可能由于尾指针rear已超出向量空间的上界而不能做入队操作。

为充分利用空间，克服上述“假溢出”现象，有两种方法

方法1：使用数组实现，入队列时添加到队列的最后，出队列时移除第一个元素同时将右侧的元素左移。

方法2：为队列分配的向量空间看成是一个首尾相接的圆环，这种队列称为循环队列。

代码实现 ​

c
#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    int *data;
    size_t size;     // 队列当前的长度
    size_t capacity; // 队列即数组可容纳的最大长度
    size_t front;    // 队列头下标节点
    size_t rear;     // 队列尾下标节点
} Queue;

// 初始化队列
void initQueue(Queue *queue, size_t capacity)
{
    queue->capacity = capacity;
    queue->data = (int *)malloc(capacity * sizeof(int));
    queue->size = 0;
    queue->front = 0;
    queue->rear = 0;
}

// 返回当前队列长度
size_t getSize(Queue *queue)
{
    return queue->size;
}

// 队列入队
void enqueue(Queue *queue, int element)
{
    if (queue->size == queue->capacity)
    {
        printf("队列已满 \n");
    }
    else
    {
        queue->data[queue->rear] = element;
        queue->rear = (queue->rear + 1) % queue->capacity;
        queue->size++;
    }
}

// 元素出队
int dequeue(Queue *queue)
{
    if (queue->size == 0)
    {
        printf("队列元素为空 \n");
        return -1;
    }
    else
    {
        int frontElement = queue->data[queue->front];
        queue->front = (queue->front + 1) % queue->capacity;
        queue->size--;
        return frontElement;
    }
}

void printQueue(Queue *queue)
{
    for (int i = queue->front, j = 0; j<queue->size; i++,j++)
    {
        int data = queue->data[i % queue->capacity];
        printf("元素[%d] = %d \n", i, data);
    }
}

void destroyQueue(Queue *queue)
{
    free(queue->data);
    queue->data = NULL;
    queue->size = 0;
    queue->capacity = 0;
    queue->front = 0;
    queue->rear = 0;
}

int main()
{
    Queue myQueue;

    // 初始化队列
    initQueue(&myQueue, 3);
    printf("初始化队列,初始容量为2\n");
    // 入队元素
    enqueue(&myQueue, 1);
    enqueue(&myQueue, 2);
    enqueue(&myQueue, 3);
    printf("队列内元素个数:%zu\n", getSize(&myQueue));
    printQueue(&myQueue);
    // 出队元素
    printf("出队元素:%d\n", dequeue(&myQueue));
    printQueue(&myQueue);
    // 释放队列内存
    destroyQueue(&myQueue);
    printf("队列内存已释放\n");
    return 0;
}

输出结果

初始化队列,初始容量为2
队列内元素个数:3
元素[0] = 1
元素[1] = 2
元素[2] = 3
出队元素:1
元素[1] = 2
元素[2] = 3
队列内存已释放

上次更新于: