1-线性表

线性表定义#

线性表是具有相同数据类型的n（n\geqslant 0）个数据元素的有限序列

核心特点：个数有限、有先后次序、为数据元素、类型相同、抽象数据元素

包含：顺序表、链表

顺序表#

定义：用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的两个元素在物理位置上也相邻

优点：插入和删除操作简单、随机访问操作快、占用内存小

缺点：插入和删除操作耗时、需要连续存储空间不灵活

静态存储与动态存储#

静态分配：表大小固定

动态分配：表大小可变，另寻存储空间并拷贝原数据

（若定义新指针，realloc会自动处理数据复制）

顺序表动态存储典例#

"动态数组列表" 

typedef struct {
    int *data;      // 数组指针
    int size;       // 当前元素数量
    int capacity;   // 总容量
} DynamicArray;

DynamicArray* createArray(int initialCapacity) {
    DynamicArray *arr = (DynamicArray*)malloc(sizeof(DynamicArray));
    arr->data = (int*)malloc(initialCapacity * sizeof(int)); 
    arr->size = 0;
    arr->capacity = initialCapacity;
    return arr;
}

void add(DynamicArray *arr, int value) {
    if (arr->size == arr->capacity) {
        // 扩展容量
        arr->capacity *= 2;
        int *temp = (int*)realloc(arr->data, arr->capacity * sizeof(int));
        if (temp != NULL) {
            arr->data = temp;
        }
    }
    arr->data[arr->size++] = value; // 满时下标为size-1
}

"malloc(sizeof(type))：分配内存，内容随机，保证函数结束后内存不回收，数据可继续使用"
"calloc(n,sizeof(type))：分配并初始化为0"
"realloc(data,sizeof(type)*n)：调整已分配内存块的大小并拷贝原数据,返回新数据的指针"
"free(ptr)：传入malloc/calloc/realloc返回的地址,释放对应地址内存（不手动释放可能导致内存泄漏）"

链表#

线性表的链式表示：通过“链”建立元素之间的逻辑关系，不要求逻辑相邻的元素物理位置也相邻

优点：插入和删除操作不需要移动元素，只需修改指针

缺点：无法随机存取，需要遍历链表

单链表：每个节点存放一个指向后继的指针，尾节点指针指向NULL

双链表：每个节点有两个指针（直接前驱prior和直接后继next）,头节点prior为NULL，尾节点next为NULL

循环单链表：单链表尾节点的next指针指向头节点

循环双链表：双链表尾节点的next指针指向头节点，头节点的prior指针指向尾节点

静态链表：用数组来描述线性表的链式存储结构，节点包含数据域data和指针域next, 指针为后继节点在数组中的相对地址（数组下标）

基本操作实现（单链表）#

节点定义#

typedef struct Node{
    int data;
    struct Node* next;
}Node;
"内含Node类型，指Node标签，标签不可缺失"

新建节点#

Node* createNode(int data){
    Node* newNode= (Node*)malloc(sizeof(Node)); // malloc保证函数结束后节点继续存在可用
    if(newNode=NULL){
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data=data;
    newNode->next=NULL;
    return newNode;
}

遍历打印链表数据#

void traverseList(Node* head){
    Node* current=head;
    while(current->next!=NULL){
        printf("%d -> ",current->data);
        current=current->next;
    }
}
"单链表操作以第一个节点head为索引"

头部插入#

Node* insertAtHead(Node* head, int data){
    Node* newNode=createNode(data);
    newNode->next=head;
    return newNode;
}

尾部插入#

Node* insetAtTail(Node* head, int data){
    Node* newNode=createNode(data);

    if (head==NULL){
        return newNode;
    }

    Node* current=head;
    while(current->next!=NULL){
        current=current->next;
    }
    current->next=newNode;
    return head;
}

删除指定值的节点#

Node* deleteNode(Node* head, int key){
    if(head==NULL){
        return NULL;
    }

    //删除头节点
    if(head->data=key){
        Node* temp=head;
        head=head->next;
        free(temp);
        return head;
    }

    Node* prev=NULL;
    Node* current=head;

    while(current!= NULL&& current->data!=key){//必须先判断 current != NULL，再访问 current->data，否则可能访问空指针
        prev=current;
        current=current->next;
    }

    if(current!=NULL){
        prev->next=current->next;
        free(current);
    }else{
        printf("未找到值为%d的节点\n", key);
    }

    return head;
}