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

时间：2022-09-26 09:34:59|栏目：C代码|点击：次

前言

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

一、分文件编写

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();
}