数据结构——线性表和顺序表

1、线性表的基本概念

1.1 定义

        线性结构是简单且常用的数据结构，而线性表则是一种典型的线性结构

        存储数据，最简单，最有效的方法是吧它们存储在一个线性表中

        一个线性表是n个元素的有限序列。每个元素在不同的情况下有不同的含义，可以是整数，也可以是字符

        线性表：是具有相同数据类型的n个数据元素的有限序列

1.2 特点：围绕一对一关系进行描述

        存在唯一的第一个元素

        存在唯一的最后一个元素

        除第一个元素外，每一个元素只有一个直接前驱

        除最后一个元素外，每一个元素均只有一个直接后继

1.3 逻辑结构：线性结构 

1.4 线性表的存储结构

        顺序存储结构：顺序表

        链式存储结构：链表

1.5 操作

        表：创建、销毁

        数据： 增删改查

2、顺序表

2.1 定义

        就是把线性表中的所有元素按照其逻辑顺序依次存储到指定位置开始的一块连续的存储区域

        线性表中的第1个元素的存储位置就是指定的存储位置，第i个元素的存储位置紧接第i-1个元素的存储位置的后面

2.2 特点

        顺序表的元素是按顺序进行存储的，第i项就存在第i个位置

        对顺序表中的所有元素，既可以顺序访问，也可以随机访问，比较擅长随机访问和遍历

        不擅长插入、删除操作，需要移动大量元素

2.3 操作

        表：创建、销毁

        数据： 增删改查

2.4 顺序表的实现方式：数组、指针 

2.4.1 顺序表的数组的实现方式

顺序表和数组进行对比

        1、数组是一种特殊的顺序表

        2、顺序表是通过数组来实现的，顺序表的元素存储在一块连续的存储空间中

        3、数组的长度是不可变的，顺序表的长度是可以改变的

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <Windows.h>
#include <stdlib.h>
#include <memory.h>  //需要使用memset时引用
//创建顺序表结构体类型
#define MAX_SIZE 100  //宏定义，为了维护简单
typedef int elementType;  //重命名，为了维护简单
typedef struct Order_List {
    elementType data[MAX_SIZE];  //数组：存放顺序表元素
    int lenth;  //顺序表的元素总个数
}OrderList;

void print_menu();
OrderList* create_list();
void append_List(OrderList* List, elementType val);
void print_List(OrderList* List);
void insert_List(OrderList* List, int index, elementType val);
void delete_List(OrderList* List, int index);
void edit_List(OrderList* List, int index, elementType val);
void destory_List(OrderList* List);

int main() {
    print_menu();
    int order = 0;  //存储用户输入的操作指令
    //创建顺序表变量
    //OrderList list;  //结构体变量，静态分配
    OrderList* List = NULL;  //结构体指针，动态申请，手动释放
    elementType val = 0;
    int index = 0;
    while (1) {
        printf("请输入操作指令：");
        scanf("%d", &order);
        switch (order) {
            case 1:  //创建顺序表
                //创建空表
                List = create_list();
                break;
            case 2:  //打印顺序表
                print_List(List);
                break;
            case 3:  //追加一个节点，尾部插入
                printf("请输入要追加的元素：");
                scanf(" %d", &val);
                append_List(List, val);
                break;
            case 4:  //插入一个节点，随机插入，从0开始
                printf("请输入要插入的位置：");
                scanf(" %d", &index);
                printf("请输入要插入的元素：");
                scanf(" %d", &val);
                insert_List(List, index, val);
                break;
            case 5:  //删除一个节点，从1开始
                printf("请输入要删除第几个元素：");
                scanf(" %d", &index);
                delete_List(List, index);
                break;
            case 6:  //修改顺序表元素，从1开始
                printf("请输入要修改的元素位置：");
                scanf(" %d", &index);
                printf("请输入修改后的新值：");
                scanf(" %d", &val);
                edit_List(List, index, val);
                break;
            case 7:  //销毁顺序表

                //List存放的是表的地址，需要销毁List的地址，才能销毁顺序表
                destory_List(&List);
                break;
            case 8:  //退出
                break;
            default:
                printf("输入错误，请重新输入！");
        }
        if (order == 8) {
            break;
        }
    }
    return 0;
}

//打印菜单
void print_menu() {
    system("cls");  //系统函数，用于屏幕清空
    printf("操作指令：\n");
    printf("1、创建顺序表\n");
    printf("2、打印顺序表\n");
    printf("3、追加一个节点\n");
    printf("4、插入一个节点\n");
    printf("5、删除一个节点\n");
    printf("6、修改顺序表元素\n");
    printf("7、销毁顺序表\n");
    printf("8、退出\n");
}

//创建空表
OrderList* create_list() {
    //申请内存
    //malloc分配的内存空间不确定，一般使用memset初始化
    OrderList* List = (OrderList*)malloc(sizeof(OrderList));  
    //申请失败
    if (List == NULL) {
        printf("内存申请失败，创建失败！\n");
        return NULL;
    }
    //申请成功
    //需要导入memory.h或string.h
    memset(List, 0, sizeof(OrderList));  //功能：将指定内存设置为指定内容，一般用来进行数组清零
    List->lenth = 0;
    printf("初始化成功！\n");
    return List;
}

//追加一个节点，末尾增加
void append_List(OrderList* List, elementType val) {
    //判断是否初始化
    if (List == NULL) {  //!List
        printf("请先建表\n");
        return;
    }
    //判断表是否已满
    if (List->lenth >= MAX_SIZE) {
        printf("表已满，无法追加！\n");
        return;
    }
    //正常追加
    List->data[List->lenth] = val;
    List->lenth++;
    printf("追加成功！\n");
}

//打印顺序表
void print_List(OrderList* List) {
    //判断是否初始化
    if (List == NULL) {  //!List
        printf("请先建表\n");
        return;
    }
    
    if (List->lenth == 0) {
        printf("空表，无法打印！\n");
        return;
    }
    //正常打印
    for (int i = 0;i < List->lenth;i++) {
        printf("%d ", List->data[i]);
    }
    printf("\n");
}

//插入一个节点，随机插入
void insert_List(OrderList* List, int index, elementType val) {
    //判断是否初始化
    if (List == NULL) {  //!List
        printf("请先建表\n");
        return;
    }
    //判断表是否已满
    if (List->lenth == 0) {
        printf("空表，无法打印！\n");
        return;
    }
    //正常插入，倒序遍历，位置后移
    for (int i = List->lenth - 1;i >= index;i--) {
        List->data[i + 1] = List->data[i];
    }
    List->data[index] = val;
    List->lenth++;
    printf("插入成功！\n");
}

//删除
void delete_List(OrderList* List, int index) {
    //判断是否初始化
    if (List == NULL) {  //!List
        printf("请先建表\n");
        return;
    }
    //判断索引是否合法
    int ind = index - 1;  //要删除的元素的索引
    if (ind<0 || ind>List->lenth - 1) {
        printf("请输入合适的位置！\n");
        return;
    }
    //执行删除，元素前移
    for (int i = ind;i < List->lenth;i++) {
        List->data[i] = List->data[i + 1];
    }
    List->lenth--;
    printf("删除成功！\n");
}

//修改
void edit_List(OrderList* List, int index, elementType val) {
    //判断是否初始化
    if (List == NULL) {  //!List
        printf("请先建表\n");
        return;
    }
    //判断索引是否合法
    int ind = index - 1;  //要删除的元素的索引
    if (ind<0 || ind>List->lenth - 1) {
        printf("您要修改的元素不存在！\n");
        return;
    }
    //执行修改
    List->data[ind] = val;
    printf("修改成功！\n");
}

//销毁  注意：形参是二级指针
void destory_List(OrderList** List) {
    free(*List);  //释放内存空间
    *List = NULL;  //销毁后要置空
    printf("销毁成功！\n");
}

2.4.2 顺序表的指针的实现方式

2.4.2.1 02.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <Windows.h>
#include <stdlib.h>
#include <memory.h> 
#define MAX_SIZE 100
typedef int ElementT;
//定义结构体类型
typedef struct OrderListPtr {
    ElementT* datap;  //元素类型指针，用于申请内存后，存放数组元素
    int length;  //存放数组元素的总个数
}ODP;
void print_menu();
void create_List(ODP* list);
void append_List(ODP* list, ElementT value);
void print_List(ODP list);
void insert_List(ODP* list, int index, ElementT value);
void delete_List(ODP* list, int index);
void delete_List(ODP* list, int index);
void edit_List(ODP* list, int index, ElementT value);
void destroy_List(ODP* list);

2.4.2.1 02.c

#include "02.h"
//顺序表的指针的实现方式

//如果要改datap或length的值需要传地址，不需要则传值

void fn2() {
    while (1) {
        print_menu();
        int order = 0;  //存储用户输入的操作指令
        ODP list = { NULL,0 };  //定义结构体变量
        ElementT value = 0;
        int index = 0;
        while (1) {
            printf("请输入操作指令：");
            scanf("%d", &order);
            switch (order) {
            case 1:  //创建顺序表
                //创建空表
                create_List(&list);
                break;
            case 2:  //打印顺序表
                print_List(list);
                break;
            case 3:  //追加一个节点，尾部插入
                printf("请输入要追加的元素：");
                scanf(" %d", &value);
                append_List(&list, value);
                break;
            case 4:  //插入一个节点，随机插入，从0开始
                printf("请输入要插入的元素的位置：");
                scanf(" %d", &index);
                printf("请输入要插入的元素：");
                scanf(" %d", &value);
                insert_List(&list, index, value);
                break;
            case 5:  //删除一个节点，从1开始
                printf("请输入要删除的元素的位置：");
                scanf(" %d", &index);
                delete_List(&list, index);
                break;
            case 6:  //修改顺序表元素，从1开始
                printf("请输入要修改的元素的位置：");
                scanf(" %d", &index);
                printf("请输入要修改的元素：");
                scanf(" %d", &value);
                edit_List(&list, index, value);
                break;
            case 7:  //销毁顺序表
                destroy_List(&list);
                break;
            case 8:  //退出
                break;
            default:
                printf("输入错误，请重新输入！");
            }
            if (order == 8) {
                break;
            }
        }
        return 0;
    }
}
//打印菜单
void print_menu() {
    system("cls");  //系统函数，用于屏幕清空
    printf("操作指令：\n");
    printf("1、创建顺序表\n");
    printf("2、打印顺序表\n");
    printf("3、追加一个节点\n");
    printf("4、插入一个节点\n");
    printf("5、删除一个节点\n");
    printf("6、修改顺序表元素\n");
    printf("7、销毁顺序表\n");
    printf("8、退出\n");
}
//创建顺序表
void create_List(ODP* list) {
    //申请内存空间
    list->datap = (ElementT*)malloc(sizeof(ElementT*) * MAX_SIZE);
    if (!list->datap) {
        printf("内存申请失败！\n");
        return;
    }
    //清0
    memset(list->datap, 0, sizeof(ElementT*) * MAX_SIZE);
    list->length = 0;
    printf("初始化成功！\n");
}

//追加一个节点，尾部插入
void append_List(ODP* list, ElementT value) {
    //判断是否建过表
    if (!list->datap) {
        printf("请先建表！\n");
        return;
    }
    //判断表是否满
    if (list->length >= MAX_SIZE) {
        printf("表已满，无法追加！\n");
        return;
    }
    //正常追加
    *(list->datap + list->length) = value;  //list->datap首元素的地址
    另一种方法
    //list->datap[list->length] = value;
    list->length++;
    printf("追加成功！\n");
}

//打印顺序表
void print_List(ODP list) {
    if (!list.datap) {
        printf("请先建表！\n");
        return;
    }
    if (list.length == 0) {
        printf("空表，无法打印！\n");
        return;
    }
    for (int i = 0;i < list.length;i++) {
        printf("%d ", list.datap[i]);  //当成数组
        另一种方法
        //printf("%d ", *(list.datap + i));  //当成指针
    }
    printf("\n");
}

//插入一个节点，随机插入，从0开始
void insert_List(ODP* list, int index, ElementT value) {
    //判断是否建过表
    if (!list->datap) {
        printf("请先建表！\n");
        return;
    }
    //判断表是否满
    if (list->length >= MAX_SIZE) {
        printf("表已满，无法插入！\n");
        return;
    }
    //正常插入
    //从index位置，倒叙遍历，位置后移
    for (int i = list->length - 1;i >= index;i--) {
        list->datap[i + 1] = list->datap[i];
    }
    //判断插入的位置是否合法
    if (index<0 || index>list->length - 1) {
        printf("插入位置不合法！\n");
        return;
    }
    list->datap[index] = value;
    另一种方法
    //*(list->datap + list->length) = value;
    list->length++;
    printf("插入成功！\n");
}

//删除一个节点，从1开始
void delete_List(ODP* list, int index) {
    //判断是否建过表
    if (!list->datap) {
        printf("请先建表！\n");
        return;
    }
    if (list->length == 0) {
        printf("空表，无法删除！\n");
        return;
    }
    //判断要删除的元素的位置是否合法
    int ind = index - 1;
    if (ind<0 || ind>list->length - 1) {
        printf("您要删除的元素不存在！\n");
        return;
    }
    //正常删除，从index开始，所有元素前移
    for (int i = ind;i < list->length;i++) {
        list->datap[i] = list->datap[i + 1];
    }
    list->length--;
    printf("删除成功！\n");
}

//修改顺序表元素，从1开始
void edit_List(ODP* list, int index, ElementT value) {
    //判断是否建过表
    if (!list->datap) {
        printf("请先建表！\n");
        return;
    }
    if (list->length == 0) {
        printf("空表，无法修改！\n");
        return;
    }
    //判断要修改的元素的位置是否合法
    int ind = index - 1;
    if (ind<0 || ind>list->length - 1) {
        printf("您要修改的元素不存在！\n");
        return;
    }
    //正常修改
    list->datap[ind] = value;
    另一种方法
    //*(list->datap + ind) = value;
    printf("修改成功！\n");
}

//销毁顺序表
void destroy_List(ODP* list) {
    //判断是否建过表
    if (!list->datap) {
        printf("请先建表！\n");
        return;
    }
    free(list->datap);  //释放内存
    list->datap = NULL;
    list->length = 0;
    printf("销毁成功！\n");
}

2.4.2.1 02main.c 

#include "02.h"
int main() {
    fn2();
    return 0;
}