数据结构与算法-线性结构篇（一）（C语言版）

顺序表

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


typedef struct List {
    // 顺序表的实现（利用数组）
    int * arr;
    // 数组容量
    int capacity;
    // 当前存储元素个数
    int size;
} * ArrayList;

/**
 * 初始化顺序表
 * @param list 顺序表
 */
_Bool initList(ArrayList list) {
    // 动态分配内存空间
    list->arr = malloc(sizeof(int) * 5);
    // 初始化失败
    if(list->arr == NULL) {
        return 0;
    }
    list->capacity = 5;
    list->size = 0;
    // 成功
    return 1;
}

/**
 * 顺序表插入操作
 * @param list
 * @param index 位序，插入第几个位置
 */
_Bool insertList(ArrayList list, int index, int data) {
    // index非法，插入失败
    if(index < 1 || index > list->size + 1) {
        return 0;
    }
    // 扩容
    if(list->size == list->capacity) {
        // 原来容量的1.5倍
        int newCapacity = list->capacity + (list->capacity >> 1);
        // 使用函数realloc()扩大内存
        int * newArr = realloc(list->arr, sizeof(int) * newCapacity);
        list->arr = newArr;
        list->capacity = newCapacity;
    }
    for (int i = list->size; i > index - 1; i--) {
        // 从插入位置开始所有元素向后移动
        list->arr[i] = list->arr[i-1];
    }
    // 插入元素
    list->arr[index - 1] = data;
    // 记录元素个数
    list->size++;
    return 1;
}

/**
 * 顺序表删除操作
 * @param list
 * @param index 位序，从1开始
 * @return
 */
_Bool deleteList(ArrayList list, int index) {
    //非法删除
    if(index < 1 || index > list->size) {
        return 0;
    }
    // 从删除位置开始，后面的往前移动
    for (int i = index - 1; i < list->size; ++i) {
        list->arr[i] = list->arr[i+1];
    }
    // 长度减小
    list->size--;
    return 1;
}

/**
 * 通过位序查找元素
 * @param list
 * @param index 位序，从1开始
 * @return 返回查找的元素
 */
int getDataByIndex(ArrayList list, int index) {
    // 非法位序
    if(index < 1 || index > list->size) {
        return INT_MAX;
    }
    int data = list->arr[index - 1];
    return data;
}

/**
 * 顺序表当前长度
 * @param list
 * @return 返回长度大小
 */
int getListLength(ArrayList list) {
    return list->size;
}

/**
 * 打印数据
 * @param list
 */
void printList(ArrayList list) {
    for (int i = 0; i < list->size; ++i) {
        printf("%d", list->arr[i]);
        printf("\t");
    }
}


int main() {
    // 创建新的结构体变量（为什么不可以直接ArrayList list呢？）
    struct List list;
    printf("开始初始化\n");
    if(initList(&list)) {
        insertList(&list, 1, 20);
        insertList(&list, 1, 30);
        insertList(&list, 1, 50);
        insertList(&list, 1, 60);
        insertList(&list, 1, 70);
        insertList(&list, 1, 80);
        deleteList(&list, 6);
        printList(&list);
        printf("当前长度：%d\n", getListLength(&list));
        printf("当前查找元素为：%d", getDataByIndex(&list, 1));
    } else {
        printf("初始化失败");
    }
}

链表

单链表

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


// 链表的结构体
typedef struct LinkNode{
    int data;
    struct LinkNode * next;
} * LinkList;


/**
 * 初始化链表（带头节点）
 * @param lNode
 */
void initLinkNode(LinkList lNode) {
    // 头节点默认指向NULL, 头节点不存储数据
    struct LinkNode * head = lNode;
    head->next = NULL;
}

/**
 * 链表插入操作
 * @param head 头节点指针
 * @param index 位序（从1开始）
 * @param data 插入的数据
 * @return 0表示失败，1表示成功
 */
_Bool insertNode(LinkList head, int index, int data) {
    // 非法位序
    if(index < 1) {
        return 0;
    }
    struct LinkNode * p = head;
    // --index 先减然后再操作
    while(--index) {
        // 当index为0时，p指向的恰好是插入位置的前一个节点
        p = p->next;
        // index越界
        if(p == NULL) {
            return 0;
        }
    }
    // 为插入的新节点分配内存
    LinkList newNode = malloc(sizeof(LinkList));
    newNode->data = data;
    newNode->next = p->next;
    p->next = newNode;
    return 1;
}

/**
 * 链表删除操作
 * @param head 头节点指针
 * @param index 位序（从1开始）
 * @return
 */
_Bool deleteNode(LinkList head, int index) {
    //非法位序
    if(index < 1) {
        return 0;
    }
    LinkList p = head;
    // 只有头节点的时候
    if(p->next == NULL) {
        return 0;
    }
    while(--index){
        p = p->next;
        // index越界
        if(p == NULL) {
            return 0;
        }
    }
    // 记录要删除的节点后再删除
    struct LinkNode * q = p->next;
    p->next = q->next;
    // 释放内存
    free(q);
    return 1;
}

/**
 * 根据位序查找元素
 */
int findNodeData(LinkList head, int index) {
    //非法位序
    if(index < 1) {
        return 0;
    }
    LinkList p = head;
    if(p->next == NULL) {
        return INT_MAX;
    }
    while (--index) {
        p = p->next;
        if(p == NULL) {
            return INT_MAX;
        }
    }
    return p->next->data;
}

/**
 * 计算链表长度（除头节点）
 */
int getLinkListLength(LinkList head) {
    int size = 0;
    while (head->next) {
        head = head->next;
        size++;
    }
    return size;
}

/**
 * 打印数据
 */
void printLinkList(LinkList linkList) {
    while (linkList) {
        linkList = linkList->next;
        printf("%d\t", linkList->data);
    }
}

int main() {
    struct LinkNode head;
    initLinkNode(&head);
    insertNode(&head, 1, 10);
    insertNode(&head, 1, 20);
    insertNode(&head, 3, 30);
    deleteNode(&head, 1);
    printf("%d\n", findNodeData(&head, 2));
    printf("%d\n", getLinkListLength(&head));
    printLinkList(&head);
}

双向链表

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


// 双向链表的结构体
typedef struct DoubleLinkNode{
    int data;
    // 指向下一个
    struct DoubleLinkNode * next;
    // 指向上一个
    struct DoubleLinkNode * prev;
} * DoubleLinkList;


/**
 * 初始化双向链表
 * @param head
 */
void initLinkNode(DoubleLinkList head) {
    // 头节点默认指向NULL, 头节点不存储数据
    head->next = NULL;
    head->prev = NULL;
}

/**
 * 双向链表插入操作
 * @param head 头节点指针
 * @param index 位序（从1开始）
 * @param data 插入的数据
 * @return 0表示失败，1表示成功
 */
_Bool insertNode(DoubleLinkList head, int index, int data) {
    // 非法位序
    if(index < 1) {
        return 0;
    }
    struct DoubleLinkNode * p = head;
    // --index 先减然后再操作
    while(--index) {
        // 当index为0时，p指向的恰好是插入位置的前一个节点
        p = p->next;
        // index越界
        if(p == NULL) {
            return 0;
        }
    }
    // 为插入的新节点分配内存
    DoubleLinkList newNode = malloc(sizeof(DoubleLinkList));
    // 内存分配失败
    if(newNode == NULL) {
        return 0;
    }
    newNode->data = data;
    // 后继节点可能不存在
    if(p->next) {
        newNode->next = p->next;
        // 不判断，此处可能会空指针异常
        p->next->prev = newNode;
    } else {
        newNode->next = NULL;
    }
    p->next = newNode;
    newNode->prev = p;
    return 1;
}

/**
 * 双向链表删除操作
 * @param head 头节点指针
 * @param index 位序（从1开始）
 * @return
 */
_Bool deleteNode(DoubleLinkList head, int index) {
    //非法位序
    if(index < 1) {
        return 0;
    }
    DoubleLinkList p = head;
    // 只有头节点的时候
    if(p->next == NULL) {
        return 0;
    }
    while(--index){
        p = p->next;
        // index越界
        if(p == NULL) {
            return 0;
        }
    }
    // 记录要删除的节点后再删除
    struct DoubleLinkNode * q = p->next;
    if(q->next) {
        p->next = q->next;
        q->next->prev = p;
    } else { // 删除最后一个节点
        p->next = NULL;
    }
    // 释放内存
    free(q);
    return 1;
}

/**
 * 根据位序查找元素
 */
int findNodeData(DoubleLinkList head, int index) {
    //非法位序
    if(index < 1) {
        return 0;
    }
    DoubleLinkList p = head;
    if(p->next == NULL) {
        return INT_MAX;
    }
    while (--index) {
        p = p->next;
        if(p == NULL) {
            return INT_MAX;
        }
    }
    return p->next->data;
}

/**
 * 计算链表长度（除头节点）
 */
int getDoubleLinkListLength(DoubleLinkList head) {
    int size = 0;
    while (head->next) {
        head = head->next;
        size++;
    }
    return size;
}