C 语言顺序表原理与核心算法实战

3. 尾插与头插

• 尾插：直接写入 size 位置并自增，效率最高 O(1)。
• 头插：需将现有元素整体后移，时间复杂度 O(n)。

// 尾插
void SLPushBack(SL* ps, SLDataType x) {
    assert(ps);
    SLCheckCapacity(ps);
    ps->array[ps->size++] = x;
}

// 头插
void SLPushFront(SL* ps, SLDataType x) {
    assert(ps);
    SLCheckCapacity(ps);
    for (int i = ps->size; i > 0; i--) {
        ps->array[i] = ps->array[i - 1];
    }
    ps->array[0] = x;
    ps->size++;
}

4. 删除操作

• 尾删：直接减少 size，O(1)。
• 头删：需将后续元素前移覆盖，O(n)。

// 尾删
void SLPopBack(SL* ps) {
    assert(ps);
    assert(ps->size);
    --ps->size;
}

// 头删
void SLPopFront(SL* ps) {
    assert(ps);
    assert(ps->size);
    for (int i = 0; i < ps->size - 1; i++) {
        ps->array[i] = ps->array[i + 1];
    }
    ps->size--;
}

5. 插入与查找

指定位置插入需先腾出空间再移动数据；查找则遍历比对。

// 指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x) {
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);
    SLCheckCapacity(ps);
    for (int i = ps->size; i > pos; i--) {
        ps->array[i] = ps->array[i - 1];
    }
    ps->array[pos] = x;
    ps->size++;
}

// 查找
int SLFind(SL* ps, SLDataType x) {
    assert(ps);
    for (int i = 0; i < ps->size; i++) {
        if (ps->array[i] == x) return i;
    }
    return -1;
}

6. 销毁

释放动态内存并重置指针，防止野指针和内存泄漏。

void SLDestroy(SL* ps) {
    if (ps->array) free(ps->array);
    ps->array = NULL;
    ps->size = ps->capacity = 0;
}

四、完整代码示例

SeqList.h

#ifndef __SEQLIST_H__
#define __SEQLIST_H__
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLDataType;
typedef struct SeqList {
    SLDataType* array;
    int size;
    int capacity;
} SL;

void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);

#endif

SeqList.c

#include"SeqList.h"

void SLInit(SL* ps) {
    assert(ps);
    ps->array = NULL;
    ps->size = ps->capacity = 0;
}

void SLDestroy(SL* ps) {
    if (ps->array) free(ps->array);
    ps->array = NULL;
    ps->size = ps->capacity = 0;
}

void SLCheckCapacity(SL* ps) {
    if (ps->size == ps->capacity) {
        int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        SLDataType* temp = (SLDataType*)realloc(ps->array, newcapacity * sizeof(SLDataType));
        if (temp == NULL) {
            perror("realloc failed!");
            exit(1);
        }
        ps->array = temp;
        ps->capacity = newcapacity;
    }
}

void SLPushBack(SL* ps, SLDataType x) {
    assert(ps);
    SLCheckCapacity(ps);
    ps->array[ps->size++] = x;
}

void SLPushFront(SL* ps, SLDataType x) {
    assert(ps);
    SLCheckCapacity(ps);
    for (int i = ps->size; i > 0; i--) {
        ps->array[i] = ps->array[i - 1];
    }
    ps->array[0] = x;
    ps->size++;
}

void SLPopBack(SL* ps) {
    assert(ps);
    assert(ps->size);
    --ps->size;
}

void SLPopFront(SL* ps) {
    assert(ps);
    assert(ps->size);
    for (int i = 0; i < ps->size - 1; i++) {
        ps->array[i] = ps->array[i + 1];
    }
    ps->size--;
}

void SLInsert(SL* ps, int pos, SLDataType x) {
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);
    SLCheckCapacity(ps);
    for (int i = ps->size; i > pos; i--) {
        ps->array[i] = ps->array[i - 1];
    }
    ps->array[pos] = x;
    ps->size++;
}

void SLErase(SL* ps, int pos) {
    assert(ps);
    assert(ps->size);
    assert(pos >= 0 && pos < ps->size);
    for (int i = pos; i < ps->size - 1; i++) {
        ps->array[i] = ps->array[i + 1];
    }
    ps->size--;
}

int SLFind(SL* ps, SLDataType x) {
    assert(ps);
    for (int i = 0; i < ps->size; i++) {
        if (ps->array[i] == x) return i;
    }
    return -1;
}

test.c

#include"SeqList.h"

void test() {
    SL s;
    SLInit(&s);
    SLPushBack(&s, 1);
    SLPushBack(&s, 2);
    SLPushBack(&s, 3);
    SLPushBack(&s, 4);
    
    int find = SLFind(&s, 2);
    if (find < 0) {
        printf("所查找的数据不存在！\n");
    } else {
        printf("所查找的数据存在，该数据所在位置下标为%d\n", find);
    }
    
    SLInsert(&s, find, 100);
    SLErase(&s, find);
    SLDestroy(&s);
}

int main() {
    test();
    return 0;
}

五、算法实战

1. 移除元素

题目：移除数组中等于给定值的元素，返回新长度。

思路：双指针法。定义 src 遍历原数组，dst 记录有效数据位置。若 nums[src] != val，则赋值给 nums[dst] 并移动 dst。

int removeElement(int* nums, int numsSize, int val) {
    int dst = 0, src = 0;
    while (src < numsSize) {
        if (nums[src] != val) {
            nums[dst++] = nums[src];
        }
        src++;
    }
    return dst;
}

2. 合并两个有序数组

题目：将有序数组 nums2 合并到 nums1 中，nums1 有足够空间。

思路：逆序双指针。从后往前比较，避免覆盖 nums1 的有效数据。l1 指向 nums1 末尾有效数据，l2 指向 nums2 末尾，l3 指向 nums1 总末尾。谁大谁放 l3 位置。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int l1 = m - 1;
    int l2 = n - 1;
    int l3 = m + n - 1;
    
    while (l1 >= 0 && l2 >= 0) {
        if (nums1[l1] > nums2[l2]) {
            nums1[l3--] = nums1[l1--];
        } else {
            nums1[l3--] = nums2[l2--];
        }
    }
    
    while (l2 >= 0) {
        nums1[l3--] = nums2[l2--];
    }
}

总结

顺序表的优势在于随机访问效率高，但中间/头部插入效率较低（O(n)），且扩容涉及内存拷贝。在实际工程中，若频繁进行头部操作或数据量不确定，可能需要考虑链表或其他结构。