C语言超详细讲解数据结构中的线性表

目录
  • 前言
  • 一、分文件编写
    • 1、分文件编写概念
    • 2、代码展示
  • 二、动态分布内存malloc
    • 1、初识malloc
    • 2、使用方法
  • 三、创建链表并进行增删操作
    • 1、初始化链表
    • 2、在链表中增加数据
    • 3、删除链表中指定位置数据
  • 四、代码展示与运行效果
    • 1、代码展示
    • 2、运行效果
  • 总结

前言

计算机专业都逃不了数据结构这门课,而这门课无疑比较难理解,所以结合我所学知识,我准备对顺序表做一个详细的解答,为了避免代码过长,采用分文件编写的形式,不仅可以让代码干净利落还能提高代码可读性,先解释部分代码的含义,最后放上代码实现和效果图,让我们开始操作吧!!!

一、分文件编写

1、分文件编写概念

在Visual Stdio 编译器中我们可以通过创建.h头文件和.cpp源文件来实现程序运行,使代码更美观,可读性高,如图所示:

SqList.h 头文件 和 Sq.List.cpp 源文件分别存放全局变量、结构体及函数的声明 和 对应函数的完整实现代码。我们需要注意的是头文件和源文件的名称要一致,而且源文件要引用头文件(#include"SqList.h"),使用""而不用<>的原因是头文件是我们自己写的,只能用""引用。

2、代码展示

SqList.cpp内容如下:

tips: #pragma once 代码是为了避免重复引入头文件,我们稍作记忆即可

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define LIST_INIT_SIZE  10
#define LISTINCREMENT   10
#define OK              1
#define ERROR           0
typedef struct SqList {
    int* elem;
    int len;
    int size;
}SqList;
int InitList_Sq(struct SqList* L);//初始化顺序表
int ListInsert_Sq(struct SqList* L, int i, int e);// 向顺序表中插入数据
int ListDelete_Sq(struct SqList* L, int i, int* e);//删除顺序表中的数据
void ListShow_Sq(struct SqList* L, const char* s);//输出顺序表中的数据
void DestroyList(SqList* L);//销毁表

SqList.cpp部分内容如下:

#include"SqList.h"
int InitList_Sq(struct SqList* L)
{
    L->elem = (int*)malloc(LIST_INIT_SIZE * sizeof(int));
    if (!L->elem)exit(0);
    L->len = 0;
    L->size = LIST_INIT_SIZE;
    return OK;
}

二、动态分布内存malloc

1、初识malloc

C语言中malloc是动态内存分配函数。

函数原型:void *malloc(unsigned int num_bytes);

参数:num_bytes无符号整型,用于表示分配的字节数。

返回值:如果分配成功则返回指向被分配内存的指针(此存储区中的初始值不确定),否则返回空指针NULL。void* 表示未确定类型的指针,void *可以指向任何类型的数据,更明确的说是指申请内存空间时还不知道用户是用这段空间来存储什么类型的数据(比如是char还是int等等)

2、使用方法

typedef struct SqList {
    int* elem;
    int len;
    int size;
}SqList;
int InitList_Sq(struct SqList* L)
{
    L->elem = (int*)malloc(LIST_INIT_SIZE * sizeof(int));
    if (!L->elem)exit(0);
    L->len = 0;
    L->size = LIST_INIT_SIZE;
    return OK;
}

我们可以看到此行代码"L->elem = (int*)malloc(LIST_INIT_SIZE * sizeof(int));"这里的L->elem就是形参结构体变量L调用int * elem 属性,因此malloc需要返回(int *)类型的指针,同时malloc右边括号放的是内存空间,大小就是宏定义的数值乘以整型(int)所占字节数,在这里说白了就是10*4个字节。模板可以这样看:(分配类型 *)malloc(分配元素个数 *sizeof(分配类型)) 如果成功,则返回该空间首地址,该空间没有初始化,如果失败,则返回0

三、创建链表并进行增删操作

1、初始化链表

int InitList_Sq(struct SqList* L)

{
    L->elem = (int*)malloc(LIST_INIT_SIZE * sizeof(int));
    if (!L->elem)exit(0);
    L->len = 0;
    L->size = LIST_INIT_SIZE;
    return OK;
}

首先为 int*elem分配内存空间,如果失败返回零,成功就返回内存空间首地址,并把链表长度置为零,链表最大长度设为 LIST_INIT_SIZE(大小为10)

2、在链表中增加数据

int ListInsert_Sq(struct SqList* L, int i, int e)
{
    if (i<0 || i>L->len)
        return ERROR;
    if (L->len >= L->size) {
        int* newbase = (int*)realloc(L->elem,
        (LIST_INIT_SIZE + LISTINCREMENT) * sizeof(int));
        if (!newbase)exit(0);
        L->size += LISTINCREMENT;
    }
    int* q = &(L->elem[i]);
    *q = e;
    L->len++;
    return OK;
}

形参 i 对应L->len 也就是初始长度 ,e 对应插入的值,只看第一个if条件我们会觉得条件永远成立,实际上下面插入数据后会进行加一操作,因此插入数据只能挨个插入;第二个if不难理解,如果链表长度达到最大长度,进行空间扩容,从而可以插入更多数据;后面其实是尾插法,让*q指向链表的最后一个位置,把数据放到里面,然后长度加一,插入数据结束。

3、删除链表中指定位置数据

int ListDelete_Sq(struct SqList* L, int i, int* e) {
    if (i<1 || i>L->len) return ERROR;
    int* p = &(L->elem[i - 1]);
    *e = *p;
    int* q = L->elem + L->len - 1;
    for (++p; p <= q; ++p)
        *(p - 1) = *p;
    L->len--;
    return OK;
}

这里 i 代表链表中的位置,*e 是该位置的数据,这样我们就能知道删除元素的值了,然后我定义*q为链表中最后一个元素的地址,随后重复让链表删除位置后的元素前移,最后链表总长度减一,删除结束。修改链表利用插入和删除操作结合就可以完成,这里没有单独定义方法,具体内容会在下面的总代码体现。

四、代码展示与运行效果

1、代码展示

//1、SqList.h:
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define LIST_INIT_SIZE  10
#define LISTINCREMENT   10
#define OK              1
#define ERROR           0
typedef struct SqList {
    int* elem;
    int len;
    int size;
}SqList;
int InitList_Sq(struct SqList* L);//初始化顺序表
int ListInsert_Sq(struct SqList* L, int i, int e);// 向顺序表中插入数据
int ListDelete_Sq(struct SqList* L, int i, int* e);//删除顺序表中的数据
void ListShow_Sq(struct SqList* L, const char* s);//输出顺序表中的数据
void DestroyList(SqList* L);//销毁表
//2、SqList.cpp
#include"SqList.h"
int InitList_Sq(struct SqList* L)
{
    L->elem = (int*)malloc(LIST_INIT_SIZE * sizeof(int));
    if (!L->elem)exit(0);
    L->len = 0;
    L->size = LIST_INIT_SIZE;
    return OK;
}
int ListInsert_Sq(struct SqList* L, int i, int e)
{
    if (i<0 || i>L->len)
        return ERROR;
    if (L->len >= L->size) {
        int* newbase = (int*)realloc(L->elem, (LIST_INIT_SIZE + LISTINCREMENT) * sizeof(int));
        if (!newbase)exit(0);
        L->size += LISTINCREMENT;
    }
    int* q = &(L->elem[i]);
    *q = e;
    L->len++;
    return OK;
}
int ListDelete_Sq(struct SqList* L, int i, int* e) {
    if (i<1 || i>L->len) return ERROR;
    int* p = &(L->elem[i - 1]);
    *e = *p;
    int* q = L->elem + L->len - 1;
    for (++p; p <= q; ++p)
        *(p - 1) = *p;
    L->len--;
    return OK;
}
void ListShow_Sq(struct SqList* L, const char* s) {
    printf("%s", s);
    int i;
    for (i = 0; i < L->len; i++) {
        printf("%d ", L->elem[i]);
    }
    putchar('\n');
}
void DestroyList(SqList* L)
{
    free(L->elem);
    L->elem = NULL;
    L->len = 0;
    L->size = 0;
}
//3、链表操作.cpp
#include"SqList.h"
void mainview_user()//界面函数
{
    struct SqList L;
    InitList_Sq(&L);
    int c;
    printf("     ------------------------------------\n");
    printf("      |**********线性表***************|\n");
    printf("      |********1   输入数据***********|\n");
    printf("      |********2   查看数据***********|\n");
    printf("      |********3   删除数据***********|\n");
    printf("      |********4   改数据    *********|\n");
    printf("      |********5   插入数据***********|\n");
    printf("      |********0   退出系统***********|\n");
    printf("     ------------------------------------\n");
    printf("\n");
    while (1)
    {
        printf("请选择:");
        scanf_s("%d", &c);
        switch (c)
        {
        case 1: {
            int n = 0;
            printf("输入要插入的数据个数:");
            scanf_s("%d",&n);
            for (int i = 0; i < n; i++) {
                int t;
                scanf_s("%d", &t);
                ListInsert_Sq(&L, L.len, t);
            }
        }break;
        case 2: {
            ListShow_Sq(&L, "现在的数据为:");
            system("pause"); break;
        }
        case 3: {
            int s, v;
            printf("请输入数据删除的位置s :");
            scanf_s("%d", &s);
            if (ListDelete_Sq(&L, s, &v))
                printf("删除成功.删除的数据是:%d\n", v);
            else
                printf("删除失败.位置有误.");
            break;
        }
        case 4: {
            printf("请输入想要修改的位置:");
            int s, v;
            scanf_s("%d", &s);
            if (s<1 || s>L.len)
                printf("数据非法");
            else {
                ListDelete_Sq(&L, s, &v);
                printf("请输入修改的数据:");
                scanf_s("%d", &v);
                ListInsert_Sq(&L, s-1, v);
                ListShow_Sq(&L, "修改后为:");
            }
            break;
        case 5: {
            int i, b;
            printf("输入插入的位置:");
            scanf_s("%d", &i);
            if (i<1 || i>L.len)
                printf("数据非法");

            else {
                printf("插入的元素:");
                scanf_s("%d", &b);
                ListInsert_Sq(&L, i, b);
                ListShow_Sq(&L, "插入后的数据为:");
                break;
            }
        }
        case 0: {
            DestroyList(&L);
            return;
        }
        default:printf("输入错误,请重新输入!\n"); system("pause"); printf("请重新选择:"); scanf_s("%d", &c);
        }
              system("PAUSE");
        }
    }
}
int main()
{
    mainview_user();
}

2、运行效果

总结

这个案例充分包含了结构体与函数、指针、地址传递、链表的知识,非常适合大家的进阶,何不静下心来自己来实现这个程序呢,有什么问题一定私信我,我也不敢确保这个程序没有bug,如果有高见,共同交流,进步,感谢支持!!!

到此这篇关于C语言超详细讲解数据结构中的线性表的文章就介绍到这了,更多相关C语言线性表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言实现线性表的基本操作详解

    目录 前言 一.实训名称 二.实训目的 三.实训要求 四.实现效果 五.顺序存储代码实现 六.链式存储代码实现 前言 这里使用的工具是DEV C++ 可以借鉴一下 一.实训名称 线性表的基本操作 二.实训目的 1.掌握线性表的基本概念 2.掌握线性表的存储结构(顺序存储与链式存储) 3.掌握线性表的基本操作 三.实训要求 1.线性表可以顺序表也可以用单链表实现,鼓励大家用两种方式实现. 2.创建线性表时,数据从键盘输入整形数据 3.线性表类型定义和或各种操作的实现,可以用教材给出的方法,也可以自

  • 一起来看看C语言线性表的线性链表

    目录 定义 1.插入 2.建立线性链表 1)头插法 2)尾插法 3.删除 4.查找 5.求线性链表的表长 总结 定义 链表是通过一组任意的存储单元来存储线性表中的数据元素,每一个结点包含两个域:存放数据元素信息的域称为数据域,存放其后继元素地址的域称为指针域.因此n个元素的线性表通过每个结点的指针域连接成了一个“链条”,称为链表.若此链表的每个结点中只包含一个指针域,则被称为线性链表或单链表. 线性表的链式存储结构,它不需要用地址连续的存储单元来实现,因为它不要求逻辑上相邻的两个数据元素物理位置

  • C语言数据结构线性表教程示例详解

    目录 线性表 顺序表 线性表 数据结构里我们时常看到什么什么表,线性表是最基本.最简单.也是最常用的一种数据结构,其他各种表的万恶之源就是这个线性表,他是个啥其实顾名思义: 一个线性表是n个具有相同特性的数据元素的有限序列.数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部.比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储,但是把最后一个数据元素的尾指针指向了首位结点). 说的这么复杂其实就是

  • C语言的线性表之顺序表你了解吗

    目录 线性表 —— 顺序表 (C语言) 1. 顺序表的储存结构 2. 顺序表的基本操作 2.1 顺序表的插入 2.2 顺序表的查找 2.3 顺序表的删除 总结 线性表 —— 顺序表 (C语言) 概念 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表中的数据元素,这种表示也称做线性表的顺序储存结构或顺序映像.通常,称这种存储结构的线性表为顺序表 (Sequential List) .其特点是,逻辑上相邻的数据元素,其物理次序也是相邻的. 1. 顺序表的储存结构 #include <st

  • C语言线性表全面梳理操作方法

    线性表:零个或多个数据元素的有限序列 强调几点: 首先它是一个序列.也就是说,元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他都有一个前驱和后继. 其次线性表强调是有限的. 线性表有两种物理结构,第一种是顺序存储结构,另一种是链式存储结构. 线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素.用c语言的一维数组来实现顺序存储结构. 线性表顺序存储结构的优缺点 优点:可以快速地读取表中任一位置的元素 无需为表示表中元素之间的逻辑关系而增加额

  • C语言数据结构之线性表的链式存储结构

    1.什么是线性表的链式存储结构 -链表 存储结点:包括元素本身的信息,还有元素之间的关系逻辑的信息 这个结点有:数据域和指针域 一个指针域:指向后继结点, 单链表 二个指针域: 指向前继结点,还有一个指向后继结点 双链表 2.原理是: s=(LinkNode *)malloc(sizeof(LinkNode));// s->data=e; //这里赋值了 s->next=p->next; // p->next=s; //这里把指针s给到了p 结点a-> 结点b -> 结

  • C语言代码详细描述顺序线性表

    目录 代码内容包括: 代码实现如下: 总结 代码内容包括: 1.表的创建 2.增删改查插 3.界面跳转 代码实现如下: #include <stdio.h> #include<stdlib.h> #define MaxSize 20 typedef int ElemType;//将int类型赋予别名 //创建结构体 typedef struct{ ElemType A[MaxSize];//MaxSize是给表的一个预估容量 int n;//n是指当前A的元素个数,记录当下表的大小

  • C语言线性表中顺序表超详细理解

    目录 一.本章重点 二.线性表 三.顺序表 四.静态顺序表接口实现 4.1顺序表初始化 4.2顺序表打印 4.3顺序表尾插 4.4顺序表尾删 4.5顺序表头插 4.6顺序表头删 4.7顺序表任意位置插入 4.8顺序表任意位置删除 五.动态顺序表接口实现 5.1顺序表的初始化 5.2顺序表打印 5.3顺序表尾插 5.4顺序表尾删 5.5顺序表头插 5.6顺序表头删 5.7顺序表任意位置插入 5.8顺序表任意位置删除 六.在线0j练习 一.移除元素(力扣) 二.合并两个有序数组(力扣) 一.本章重点

  • C语言超详细讲解数据结构中的线性表

    目录 前言 一.分文件编写 1.分文件编写概念 2.代码展示 二.动态分布内存malloc 1.初识malloc 2.使用方法 三.创建链表并进行增删操作 1.初始化链表 2.在链表中增加数据 3.删除链表中指定位置数据 四.代码展示与运行效果 1.代码展示 2.运行效果 总结 前言 计算机专业都逃不了数据结构这门课,而这门课无疑比较难理解,所以结合我所学知识,我准备对顺序表做一个详细的解答,为了避免代码过长,采用分文件编写的形式,不仅可以让代码干净利落还能提高代码可读性,先解释部分代码的含义,

  • C语言超详细讲解数据结构中双向带头循环链表

    目录 一.概念 二.必备工作 2.1.创建双向链表结构 2.2.初始化链表 2.3.动态申请节点 2.4.打印链表 2.5.销毁链表 三.主要功能 3.1.在pos节点前插入数据 尾插 头插 3.2.删除pos处节点数据 尾删 头删 3.3.查找数据 四.总代码 List.h 文件 List.c 文件 Test.c 文件 五.拓展 一.概念 前文我们已经学习了单向链表,并通过oj题目深入了解了带头节点的链表以及带环链表,来画张图总体回顾下: 在我们学习的链表中,其实总共有8种,都是单双向和带不带

  • Java 超详细讲解数据结构中的堆的应用

    目录 一.堆的创建 1.向下调整(以小堆为例) 2.创建堆 3.创建堆的时间复杂度 二.堆的插入和删除 1.堆的插入 2.堆的删除 三.堆的应用 1.堆排序 2.top-k问题 [求最小的K个数] 四.常用接口的介绍 1.PriorityQueue的特性 2.优先级队列的构造 一.堆的创建 1.向下调整(以小堆为例) 让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子) 如果parent的左孩子存在,即:child < size,

  • Java 超详细讲解数据结构中的堆的应用

    目录 一.堆的创建 1.向下调整(以小堆为例) 2.创建堆 3.创建堆的时间复杂度 二.堆的插入和删除 1.堆的插入 2.堆的删除 三.堆的应用 1.堆排序 2.top-k问题(求最小的K个数) 四.常用接口的介绍 1.PriorityQueue的特性 2.优先级队列的构造 一.堆的创建 1.向下调整(以小堆为例) 让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子) 如果parent的左孩子存在,即:child < size, 进

  • C语言超详细讲解栈的实现及代码

    目录 前言 栈的概念 栈的结构 栈的实现 创建栈结构 初始化栈 销毁栈 入栈 出栈 获取栈顶元素 获取栈中有效元素个数 检测栈是否为空 总代码 Stack.h 文件 Stack.c 文件 Test.c 文件 前言 栈的概念 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作.进行数据插入和删除操作的一端称为栈顶,另一端称为栈底.栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则.有点类似于手枪弹夹,后压进去的子弹总是最先打出,除非枪坏了. 压栈:栈的插入

  • C语言超详细讲解指向函数的指针

    目录 一.函数的指针 二.指向函数的指针变量 三.调用函数的两种方式 四.指向函数的指针的作用 五.用指向函数的指针作函数参数(重点) 六.为什么要将指向函数的指针变量作为函数的形参(重点) 一.函数的指针 首先,函数名代表函数的起始地址,调用函数时,程序会从函数名获取到函数起始地址,并从该地址起执行函数中的代码,函数名就是函数的指针,所以我们可以定义一个指向函数的指针变量,用来存放函数的起始地址,这样一来,就可以通过该变量来调用其所指向的函数. 二.指向函数的指针变量 定义指向函数的指针变量

  • C语言 超详细讲解库函数

    目录 1 返回整数的getchar函数 2 更新顺序文件 3 缓冲输出与内存分配 4 库函数 练习 1 返回整数的getchar函数 代码: #include<stdio.h> int main() { char c; while((c = getchar())!=EOF)//getchar函数的返回值为整型 putchar(c); return 0; } 上述代码有三种可能: 某些合法的输入字符在被"截断"后使得c的取值与EOF相同,程序将在复制的中途停止. c根本不可能

  • C语言 超详细讲解算法的时间复杂度和空间复杂度

    目录 1.前言 1.1 什么是数据结构? 1.2 什么是算法? 2.算法效率 2.1 如何衡量一个算法的好坏 2.2 算法的复杂度 2.3 复杂度在校招中的考察 3.时间复杂度 3.1 时间复杂度的概念 3.2 大O的渐进表示法 3.3 常见时间复杂度计算举例 4.空间复杂度 5. 常见复杂度对比 1.前言 1.1 什么是数据结构? 数据结构(Data Structure)是计算机存储.组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合. 1.2 什么是算法? 算法(Algorit

  • C语言超详细讲解字符串相乘

    目录 前言 一. 分析思路 二.使用步骤 1.代码如下 2.memset函数 三.总结 前言 我们已经知道,正常的两位整形数据通过*相乘,C语言中int为4字节,32bit(字节),其机器码第一位为符号位,余下31位表示数字,表示范围:-2^31(-2147483648)~2^31-1(2147483647),但超过了这个范围我们该如何做呢? 提示:将数字以字符串的形式进行操作 一. 分析思路 示例: 我们把每一个数都看成是一个字符串,每一个元素为十进制数字所对应的字 符,由于是后面的元素先进行

  • C语言超详细讲解排序算法上篇

    目录 1.直接插入排序 2.希尔排序(缩小增量排序) 3.直接选择排序 4.堆排序 进入正式内容之前,我们先了解下初阶常见的排序分类 :我们今天讲前四个! 1.直接插入排序 基本思想:当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排 序码与array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移! 直接插入排序的特性总结: 1. 元素集

随机推荐