数据结构-线性表

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

1. 定义

线性表是由同一类型的数据元素构成的有序序列的线性结构。

2.实现

2.1 顺序存储在内存中用地址连续的一块存储空间顺序存放线性表中的各个元素用一维数组表示顺序存储的数据区域。

MAXSIZE 定义的数组的容量线性表中数据从Data[0]开始存放。
Last 记录线性表中最后一个元素的位置（数组下标。表空时Last = -1。
struct LNode 为了体现数据组织的整体性将数组Data和Last封装成结构作为顺序表的类型。
typedef PtrToLNode List由此可以利用List定义线性表 List L；通过L可以访问相应内容 L->Data[i] , L ->Last

#define MAXSIZE 10
#define ERROR -1
// 线性表的顺序存储

typedef int ElementType;// Data数组中存放数据的类型
typedef int Position;
typedef struct LNode *PtrToLNode;
typedef PtrToLNode List; // List 定义为结构体指针

struct LNode {
    ElementType Data[MAXSIZE];
    Position Last;
};

基本操作

  1. List MakeEmpty() 初始化线性表
  2. void PrintData(List L) 打印线性表Data中存储的所有内容
  3. bool Insert(List L,ElementType X, int i) 插入元素i为制定位序
  4. bool Delete(List L,int i) 删除元素i为指定位序
  5. Position Find(List L, ElementType X) 查找元素
  6. int Length返回线性表长度

完整代码

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

#define MAXSIZE 10
#define ERROR -1
// 线性表的顺序存储

typedef int ElementType;// Data数组中存放数据的类型
typedef int Position;
typedef struct LNode *PtrToLNode;
typedef PtrToLNode List; // List 定义为结构体指针

// 将数组Data和变量Last分装成一个结构体
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last;
};

// 初始化线性表
List MakeEmpty() {
    List L; // 利用List定义线性表L,构建一个空表
    L = (List) malloc(sizeof(struct LNode)); // 动态分配表结构所需要的存储空间
    L->Last = -1; // 将表中Last指针置-1
    return L;    // 返回结构体指针
}

// 打印线性表中的数据
void PrintData(List L) {
    int i = 0;
    if(L->Last==-1) printf("表为空");
    while (i < L->Last + 1) {
        printf("%d ", L->Data[i]);
        i++;
    }
    printf("\n");
}

// 插入元素: 在L的制定位序i前插入一个新元素X,成功返回true,失败返回false(位序i元素的数组下标为i-1)
bool Insert(List L, ElementType X, int i) {
    // 先判断插入是否合法 1) 表空间是否已满 2插入位序的合法性
    if (L->Last == MAXSIZE - 1 || i < 1 || i > L->Last + 2) {
        printf("插入失败\n");
        return false;
    }
    // i-1后的数都往后挪一位
    else{
        for (int j = L->Last; j >= i - 1; j--)
            L->Data[j + 1] = L->Data[j];
        L->Data[i - 1] = X;
        L->Last++;
        return true;
    }
}


// 删除元素: 给定位序i 删除数组中的i-1
bool Delete(List L,int i){
    // 先判断删除合法性
    if(i<1||i>L->Last){
        printf("表中不存在位序为 %d 的元素删除失败",i);
        return false;
    }
    // 删除元素
    else{
        for(int j = i-1;j<=L->Last;j++)
            L->Data[j-1] = L->Data[j];
        L->Last --;
        return true;
    }
}

// 查找元素: 查找和X相等的元素, 返回数组下标
Position Find(List L, ElementType X){
    Position i = 0;
    while(i<=L->Last){
        if(L->Data[i] == X) return i;
        i++;
    }
    return ERROR;
}

// 返回列表长度
int Length(List L){
    return L->Last+1;
}


int main() {
    int findResult;
    int len;
    List list;

    list = MakeEmpty();

    Insert(list, 10, 1);
    Insert(list, 20, 2);
    Insert(list, 30, 3);
    Insert(list, 40, 4);
    Insert(list, 50, 5);
    PrintData(list);

    findResult = Find(list,30);
    printf("%d\n",findResult);
    Delete(list,1);
    PrintData(list);

    len = Length(list);
    printf("%d\n",len);


}

2.2 链式存储与顺序存储相比它不需要用地址连续的存储单元来实现通过一个指针来连接各个分散的结点形成链状结构。每个结点存放一个元素以及指向下一节点的指针。链表可分为带头结点的链表和不带头结点的链表。

完整代码(带头节点的链表)

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

#define ERROR -1


typedef int ElementType;// Data数组中存放数据的类型
typedef struct LNode *PtrToLNode;
typedef PtrToLNode Position; // 这里的位置是结点的地址
typedef PtrToLNode List; // List 定义为结构体指针


// 将数组Data和变量Last分装成一个结构体
struct LNode {
    ElementType Data; // 保存当前元素
    PtrToLNode Next; // 指向下一个结点的指针
};


List MakeEmpty() {
    List L; // 利用List定义线性表L,构建一个空表
    L = (List) malloc(sizeof(struct LNode)); // 动态分配表结构所需要的存储空间
    L->Next = NULL; // 将表中Last指针置-1
    return L;    // 返回结构体指针
}

// 插入数据
bool Insert(List L, ElementType X, int index) {
    Position tmp, pre;
    int cnt = 0;

    pre = L; // pre指向表头
    while (pre && cnt < index - 1) {
        pre = pre->Next;
        cnt++;
    }
    if (pre == NULL || cnt != index - 1) {
        printf("插入位置错误\n");
        return ERROR;
    } else {
        tmp = (Position) malloc(sizeof(struct LNode));
        tmp->Data = X;
        tmp->Next = pre->Next;
        pre->Next = tmp;
        return true;
    }
}

// 删除数据
bool Delete(List L, int index) {
    Position tmp, pre;
    int cnt = 0;

    pre = L; // pre指向表头

    // 查找位序为index-1的结点
    while (pre && cnt < index - 1) {
        pre = pre->Next;
        cnt++;
    }
    if (pre == NULL || cnt != index - 1) {
        printf("删除位置错误\n");
        return ERROR;
    } else {
        tmp = pre->Next;
        pre->Next = tmp->Next;
        free(tmp);
        return true;
    }
}

// 返回线性表的长度
int Length(List L) {
    int cnt = 0;
    while (L) {
        L = L->Next;
        cnt++;
    }
    return cnt;
}

// 打印线性表中的数据
void PrintData(List L) {
    // 表头不放数据, 跳过表头读取
    while (L->Next) {
        L = L->Next;
        printf("%d", L->Data);
    }
    printf("\n");
}



int main() {
    List list;
    list = MakeEmpty();
    printf("线性表长度为 %d \n", Length(list));

    Insert(list, 1, 1);
    PrintData(list);
    Insert(list, 2, 2);
    PrintData(list);
    Insert(list, 4, 3);
    PrintData(list);
    printf("线性表长度为 %d \n", Length(list));

    Delete(list, 1);
    PrintData(list);
    printf("线性表长度为 %d \n", Length(list));
}

3 顺序表 vs 链表

  1. 链表在随机访问元素时需要通过遍历来完成而顺序表利用数组特性直接访问得到
  2. 顺序表在插入元素时需要移动后续所有元素而链表只需要修改结点指向即可完成插入

总结 当读取数据多于插入删除数据时用顺序表；当插入删除数据多于读取时用链表。

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：局域网下两台电脑ping不通_两台电脑ping不通

下一篇：开发模型和测试模型

“数据结构-线性表” 的相关文章

html css中有哪些属性可以继承，哪些不可以继承1年前 (2023-02-02)
【ASP.NET Core】按用户角色授权1年前 (2023-02-02)
亚马逊云科技Build On - Serverless创新零售初体验1年前 (2023-02-02)
点餐系统数据库设计--SQL Server_sql数据库订餐系统设计1年前 (2023-02-02)
Postgresql 使用Vscode开发指南1年前 (2023-02-02)
如何使用 JuiceFS 创建 WebDAV 共享1年前 (2023-02-02)
关于STM32CubeIDE无法正常启动GDB服务端的解决办法1年前 (2023-02-02)
【数字电子技术课程设计】多功能数字电子钟的设计_多功能数字钟设计与实现csdn1年前 (2023-02-02)
玩转传感器——DHT11温湿度传感器（STM32版）_dht11温度传感器stm321年前 (2023-02-02)
element-ui table使用type=‘selection‘复选框全禁用-全选禁用_elementui表格全选框禁用1年前 (2023-02-02)

阿里云国际版