线性表的那些事儿

╰半橙微兮° 2022-05-27 03:43 199阅读 0赞

#### 前言 ####

现在已经大三，才开始系统的学习算法，虽然有些晚，但是因为之前有一些基础，学起来进度也挺快，不失为一件好事。在学习的过程中，必不可少的需要去复习数据结构，那么今天就从最基础的线性表开始聊起。我们都知道线性表是最简单的一种数据结构，但是他可以做的事情很多，因为表中的每一个节点都可以表示很多信息，一个数字、一个人的所有信息、一本书……线性表的实现可以是顺序实现，也可以是链式实现。顺序实现也就是通过我们最基础的数组，通过分配一段连续的存储单元，而链式实现则是通过动态的申请空间来实现。为了简单起见，下面的代码我们都把每个结点当做一个数字，并分别对链表进行增删改查操作。另外为了方便期间，对于异常情况的输出信息放在子函数实现。

#### 顺序实现 ####

#include<stdio.h>
    #define MAX 1005
    
    // 定义结构体
    typedef struct list {
        int data[MAX]; //数组
        int count; // 线性表元素总个数
    } List;
    // 线性表初始化
    void init(List *p) {
        // 总个数为0
        p->count = 0;
    }
    // 元素的插入
    void insert(List *p, int pos, int data) {
        int flag = 1;
        // 判断需要插入的位置是否大于目前线性表元素总个数
        if(pos > p->count) {
            printf("%d插入失败,插入位置大于元素总个数\n", data);
            flag = 0;
        }
        // 判断是否线性表已经满了
        if(p->count >= MAX) {
            printf("%d插入失败,线性表已经满了\n", data);
            flag = 0;
        }
        for(int i=p->count+1; i > pos; i--)
            p->data[i] = p->data[i-1];
        p->data[pos] = data;
        if(flag) p->count++;
    }
    // 元素的输出
    void print(List *p) {
        for(int i=0; i < p->count; i++)
            printf("%3d ", p->data[i]);
        printf("\n");
    }
    // 元素的修改
    void update(List *p, int pos, int data) {
        if(pos > p->count)
            printf("修改失败,不存在%d位置\n", pos);
        p->data[pos] = data;
    }
    // 删除元素
    void deleteByPos(List *p, int pos) {
        int flag = 1;
        if(pos > p->count) {
            printf("删除失败,不存在%d位置\n", pos);
            flag = 0;
        }
        for(int i=pos; i < p->count; i++)
            p->data[i] = p->data[i+1];
        if(flag) p->count--;
    }
    int main() {
        // 声明一个线性表
        List s;
        int insertResult;
        // 初始化
        init(&s);
        // 对线性表插入数据
        insert(&s, 0, 100);
        insert(&s, 1, 200);
        insert(&s, 2, 300);
        insert(&s, 0, 99);
        insert(&s, 10, 999);
        insert(&s, 2, 199);
        // 输出线性表
        print(&s);
        // 修改数据
        update(&s, 0, 0);
        update(&s, 10, 0);
        print(&s);
        // 删除数据
        deleteByPos(&s, 1);
        deleteByPos(&s, 20);
        print(&s);
        return 0;
    }

#### 链表实现 ####

#include<stdio.h>
    
    // 定义节点结构体
    typedef struct node {
        int data;
        struct node *next;
    } Node;
    // 定义链表结构体
    typedef struct list {
        Node *head;
    } List;
    
    // 线性表初始化
    void init(List *p) {
        // 头部节点为空
        p->head = NULL;
    }
    // 元素的插入
    void insert(List *p, int pos, int data) {
        Node *newNode, *m;
        newNode = (Node *)malloc(sizeof(Node));
        newNode->data = data;
        if(pos == 0){
            newNode -> next = p->head;
            p -> head = newNode;
        } else {
            m = p->head;
            for(int i=0; i < pos-1 && m != NULL; i++)
                m = m ->next;
            if(m != NULL){
                newNode -> next = m -> next;
                m -> next = newNode;
            } else printf("%d插入失败,插入位置大于元素总个数\n", data);
        }
    }
    // 元素的修改
    void update(List *p, int pos, int data) {
        Node *m;
        m = p -> head;
        for(int i=0; i < pos && m != NULL; i++)
            m = m->next;
        if(m != NULL)
            m -> data = data;
        else
            printf("修改失败,不存在%d位置\n", pos);
    }
    // 元素的删除
    void deleteByPos(List *p, int pos) {
        Node *m, *t;
        m = p -> head;
        if(pos == 0) {
            p -> head = m -> next;
            free(m);
        } else {
            for(int i=0; i < pos-1 && m != NULL; i++)
                m = m -> next;
            if(m != NULL) {
                t = m -> next;
                if(t != NULL) {
                    m -> next = t -> next;
                    free(t);
                } else  printf("删除失败,不存在%d位置\n", pos);
            } else  printf("删除失败,不存在%d位置\n", pos);
        }
    }
    // 元素的输出
    void print(List *p) {
        Node *m;
        m = p -> head;
        while(m != NULL) {
            printf("%3d ", m->data);
            m = m -> next;
        }
        printf("\n");
    }
    int main() {
        // 声明一个线性表
        List s;
        // 初始化
        init(&s);
        // 对线性表插入数据
        insert(&s, 0, 100);
        insert(&s, 1, 200);
        insert(&s, 2, 300);
        insert(&s, 0, 99);
        insert(&s, 10, 999);
        insert(&s, 2, 199);
        // 输出线性表
        print(&s);
        update(&s, 0, 0);
        update(&s, 10, 0);
        print(&s);
        // 删除数据
        deleteByPos(&s, 0);
        deleteByPos(&s, 5);
        deleteByPos(&s, 1);
        deleteByPos(&s, 20);
        print(&s);
        return 0;
    }