美文网首页
线性表(顺序表和链表)的学习总结与C语言实现（数据结构学习2）

线性表(顺序表和链表)的学习总结与C语言实现（数据结构学习2）

作者: 读月鱼_Harlan | 来源:发表于2020-12-11 20:33 被阅读0次

    定义

    通过学习我们知道，具有“一对一”逻辑关系的数据，最佳的存储方式是使用线性表。那么，什么是线性表呢？

    线性表，全名为线性存储结构。使用线性表存储数据的方式可以这样理解，即“把所有数据用一根线儿串起来，再存储到物理空间中”。


    线性表.png

    将具有“一对一”关系的数据“线性”地存储到物理空间中，这种存储结构就称为线性存储结构（简称线性表）。

    使用线性表存储的数据，如同向数组中存储数据那样，要求数据类型必须一致，也就是说，线性表存储的数据，要么全不都是整形，要么全部都是字符串。一半是整形，另一半是字符串的一组数据无法使用线性表存储。

    顺序存储结构和链式存储结构

    把这“一串儿”数据放置到物理空间，我们可以选择以下两种方式：

    • 1、顺序存储；


      顺序存储结构.png

    如上图所示，将数据依次存储在连续的整块物理空间中，这种存储结构称为顺序存储结构（简称顺序表）；

    • 2、链式存储。


      链式存储结构.png

      如上图所示，数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系，这种存储结构称为链式存储结构（简称链表）；

    也就是说，线性表存储结构可细分为顺序存储结构和链式存储结构。

    对于非空的线性表和线性结构,其特点如下:

    1. 存在唯⼀的一个被称作”第⼀个”的数据元素;
    2. 存在唯⼀的一个被称作”最后一个"的数据元素；
    3. 除了了第一个之外,结构中的每个数据元素均有一个前驱；
    4. 除了了最后一个之外,结构中的每个数据元素都有一个后继。

    顺序表代码实现

    顺序表存储数据时，会提前申请一整块足够大小的物理空间，然后将数据依次存储起来，存储时做到数据元素之间不留一丝缝隙。

    我们可以发现，顺序表存储数据同数组非常接近。其实，顺序表存储数据使用的就是数组。
    使用顺序表存储数据之前，除了要申请足够大小的物理空间之外，为了方便后期使用表中的数据，顺序表还需要实时记录以下 2 项数据：

    • 顺序表申请的存储容量；
    • 顺序表的长度，也就是表中存储数据元素的个数；
    typedef struct{
    ElemType *data;
    int length;
} SqlTable;

    1、顺序表的初始化

    //1、初始化顺序结构线性表
Status initTable(SqlTable *table){
    
    table->data = malloc(sizeof(ElemType) * MAX_SIZE);
    if (!table->data) {
        return ERROR;
    }
    table->length = 0;
    return OK;
}

    2、顺序表插入数据

    //2、往线性表中插入数据
Status insertTable(SqlTable *table, int index, ElemType data){
    
    //存储位置不对
    if (index < 1 || index > table->length + 1) {
        return ERROR;
    }
    //存储空间已满
    if (table -> length >= MAX_SIZE) {
        return ERROR;
    }
    //如果不在表尾插入数据，则需要在指定位置的后继元素都向后移动一位
    if (index < table->length + 1) {
        for (int i = table->length + 1; i > index; i--) {
            table->data[i] = table->data[i-1];
        }
    }
    table->data[index] = data;
    table->length ++;
    return OK;
}

    3、顺序表遍历

    //3、遍历线性表
void traverseTable(SqlTable table){
    
    printf("遍历表：");
    for (int i = 1; i <= table.length ; i ++) {
        printf("%d ",table.data[I]);
    }
    printf("\n");
}

    4、顺序表取出值

    //4 顺序表的取值
Status GetElem(SqlTable table, int index, ElemType *data){
    //存储位置不对
    if (index < 1 || index > table.length) {
        return ERROR;
    }
    *data = table.data[index];
    return OK;
}

    5、顺序表删除数据

    //5 顺序表删除
/*
 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 操作结果: 删除L的第i个数据元素,L的长度减1
 */
Status deleteElem(SqlTable *table, int index){
    
    if (index < 1 || index > table->length) {
        return ERROR;
    }
    if (table->length == 0) {
        return ERROR;
    }
    for (int i = index; i < table->length; i++) {
        table->data[i] = table->data[i+1];
    }
    table->length --;
    return OK;
}

    6、清空顺序表

    //6 清空顺序表
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
void ClearTable(SqlTable *table){
    
    table->length = 0;
}

    7、判断顺序表是否为空

    //7 判断顺序表是否为空
/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status tableEmpty(SqlTable table){
    
    if (table.length <= 0) {
        return S_TRUE;
    }
    else {
        return S_FALSE;
    }
}

    8、获取顺序表长度

    //8 获取顺序表长度ListEmpty元素个数 */
int tableLength(SqlTable table){
    return table.length;
}

    9、顺序表查找元素并返回位置

    //9 顺序表查找元素并返回位置
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int locateElem(SqlTable table, ElemType data){
    
    for (int i = 1; i <= table.length; i ++) {
        if (data == table.data[i]) {
            return I;
        }
    }
    return 0;
}

    其它辅助代码

    #include "stdlib.h"

#define MAX_SIZE 100
#define OK       1
#define ERROR    0
#define S_TRUE     1
#define S_FALSE    0

//ElemType 元素类型，这里设置为int
typedef int ElemType;
//状态码，返回操作是否成功，用OK或者ERROR
typedef int Status;

typedef struct{
    ElemType *data;
    int length;
} SqlTable;

int main(int argc, const char * argv[]) {
    printf("Hello, World!\n");
    
    //初始化
    SqlTable table;
    Status initStatus = initTable(&table);
    printf("线性表初始化是否成功 %d \n",initStatus);
    
    //插入数值
    for (int i = 1; i <= 10; i++) {
        insertTable(&table, i, i);
    }
    traverseTable(table);
    
    //取值
    ElemType data;
    GetElem(table, 6, &data);
    printf("顺序表第6个值是%d\n",data);
    
    //删除
    deleteElem(&table, 6);
    printf("删掉第6个值\n");
    traverseTable(table);
    
    //查找8在哪个位置
    int locate = locateElem(table, 8);
    printf("顺序表中8在第 %d 位\n",locate);
    
    //获取长度
    int length = tableLength(table);
    printf("获取长度是 %d\n",length);
    
    //清空
    ClearTable(&table);
    printf("清空表\n");
    
    //判断是否为空
    Status isEmpty = tableEmpty(table);
    printf("是否为空(1是0否)：%d\n",isEmpty);
    
    traverseTable(table);
    
    printf("\n");
    return 0;
}

    输出结果

    输出结果.png

    链表代码实现

    与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。

    如果只有一个值根本无法体现出各数据之间的逻辑关系。对此，链表的解决方案是，每个数据元素在存储时都配备一个指针，用于指向自己的直接后继元素。


    链表示意图.png

    于是，链表中每个数据的存储都由以下两部分组成：

    • 数据元素本身，其所在的区域称为数据域；

    • 指向直接后继元素的指针，所在的区域称为指针域；


      结点.png

    代码实现如下：

    typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

    一个完整的链表需要由以下几部分构成：

    • 头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据；
    • 节点：链表中的节点又细分为头节点、首元节点和其他节点：
    • 头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；
    • 首元节点：由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；
    • 其他节点：链表中其他的节点；

    1、链表的初始化

    //1、初始化单链表
Status InitList(LinkList *list){
    
    *list = malloc(sizeof(Node));
    if (*list == NULL) {
        return ERROR;
    }
    (*list)->next = NULL;
    return OK;
}

    2、单链表插入数据

    //2、单链表插入
Status ListInsert(LinkList *list, int index, ElemType data){
    
    LinkList p = *list;
    int i = 1;
    while (p && i < index) {
        p = p->next;
        I++;
    }
    if (i > index || !p) {
        return ERROR;
    }
    
    LinkList q = malloc(sizeof(Node));
    q->data = data;
    q->next = p->next;
    p->next = q;
    return OK;
}

    3、链表遍历

    //3、遍历链表
/* 初始条件：链表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
void ListTraverse(LinkList list){
    
    printf("遍历链表：");
    LinkList p = list->next;
    if (!p) {
        printf("空链表");
    }
    else {
        while (p) {
            printf("%d ",p->data);
            p = p->next;
        }
    }
    printf("\n");
}

    4、链表取值

    //4、单链表取值
Status GetElem(LinkList list, int index, ElemType *data){
    
    LinkList p = list;
    int i = 0;
    while (p && i < index) {
        p = p->next;
        I++;
    }
    if (i > index || !p) {
        return ERROR;
    }
    *data = p->data;
    return OK;
}

    5、链表删除元素

    //5、单链表删除元素
Status ListDelete(LinkList *list, int index, ElemType *data){
    
    LinkList p = *list;
    LinkList q = p->next;
    int i = 1;
    while (p && i < index) {
        p = q;
        q = p->next;
        I++;
    }
    if (i > index || !p || !q) {
        return ERROR;
    }
    p->next = q->next;
    *data = q->data;
    free(q);
    return OK;
}

    6、清空链表

    //6、清空链表
/* 初始条件：链表List已存在。操作结果：将List重置为空表 */
void ClearList(LinkList *list){
    
    LinkList p,q;
    p = (*list)->next;
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
    (*list)->next = NULL;
}

    7、链表前插法

    前插法.png 
    //7、单链表前插法
/* 随机产生n个元素值,建立带表头结点的单链线性表List(前插法)*/
void CreateListHead(LinkList *list, int n){
    
    *list = malloc(sizeof(Node));
    (*list)->next = NULL;
    
    LinkList p;
    for (int i = 1; i <= n; i ++) {
        p = malloc(sizeof(Node));
        p->data = I;
        p->next = (*list)->next;
        (*list)->next = p;
    }
}

    8、链表后插法

    后插法.png 
    //8、单链表后插法
/* 随机产生n个元素值,建立带表头结点的单链线性表List(后插法)*/
void CreateListTail(LinkList *list, int n){
    
    *list = malloc(sizeof(Node));
    LinkList p = *list;
    LinkList q;
    for (int i = 1; i <= n; i ++) {
        q = malloc(sizeof(Node));
        q->data = I;
        p->next = q;
        p = q;
    }
    p->next = NULL;
}

    其它辅助代码

    #include "stdlib.h"

#define OK       1
#define ERROR    0
#define S_TRUE   1
#define S_FALSE  0

typedef int ElemType;
typedef int Status;

typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

int main(int argc, const char * argv[]) {
    
    //初始化
    LinkList list;
    InitList(&list);
    printf("初始化链表\n");
    
    //插入数据
    for (int i = 1; i <= 10; i ++) {
        ListInsert(&list, 1, i);
    }
    printf("插入数据后\n");
    
    //遍历数据
    ListTraverse(list);
    
    //删除数据
    ElemType deleteData;
    ListDelete(&list, 6, &deleteData);
    printf("删除第6个元素：%d\n",deleteData);
    
    //遍历数据
    ListTraverse(list);
    
    //取出数据
    ElemType data;
    GetElem(list, 6, &data);
    printf("取出第6个数：%d\n",data);
    
    //清空链表
    ClearList(&list);
    printf("清空链表\n");
    //遍历数据
    ListTraverse(list);
    
    printf("前插法创建链表\n");
    CreateListHead(&list, 20);
    ListTraverse(list);
    
    printf("后插法创建链表\n");
    CreateListTail(&list, 20);
    ListTraverse(list);
    
    printf("\n");
    return 0;
}

    输出结果

    输出结果.png

    如有不对的地方，请指正，谢谢您的阅读～

    相关文章

      网友评论

          本文标题：线性表(顺序表和链表)的学习总结与C语言实现（数据结构学习2）

          本文链接：https://www.haomeiwen.com/subject/marsgktx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|线性表(顺序表和链表)的学习总结与C语言实现（数据结构学习2）|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！