数据结构的书看不太懂?C语言代码实现顺序表(考研&工作必备)

文章目录

🔊个人介绍
🌳数据结构系列点击跳转
🌳戳我跳到本人个人主页
🇨🇳大家好，我是_奇奇，一名C/C++博主。河牧院大一在读。
🔔欢迎大家交流学习
❤️编程的前途是光明的，道路是曲折的。
🌳笑到最后才是赢家🍺

❤️前言

严老师的书来镇楼，压迫感有没有上升

• 数据结构的书看着无聊，没有欲望看词下去？看着感觉头大？那这一篇绝对是小白的福音。数据结构第二版严蔚敏的书看不懂？顺序表链表学不会，学不懂？或者学会了听会了。不知道怎么敲代码，感觉心里不踏实？
• 究其原因是因为学校的课程快，偏理论，而大多数人并不是天才的水平，达不到听几遍就会写代码了。所以需要多多画图，多多敲代码。但是，严蔚敏老师书上的代码是伪代码，不适合我们初学者使用，初学者不能说无法把伪代码变成C语言写出来。但我肯定应该会很难，甚至将你劝退，让你没有去把顺序表用代码写出来的欲望。
• 只有把顺序表用代码写出来，让你自然而然的真正做到理解顺序表。

此篇用C语言在带你从零基础开始复现顺序表的代码。带你从简单到复杂。从基础延伸到深度理解顺序表。实现数据结构从入门到精通。后期数据结构的全部内容都会设置在这个专栏里——>点我进入专栏。

• 对于计算机专业的学生，无论考研还是就业，数据结构都是重中之重。所以数据结构需要学好。
• 对于学好数据结构，有以下几个关键点。
• 1.注重细节，注重细节，注重细节。数据结构是对C语言的提升。能够锻炼我们的细节问题。考虑问题要全面。比如要考虑当顺序表只有1个元素或者为空时的临界点。保证程序的健壮性。一般bug的出现都在这里。
• 2.注重实践，就是多敲代码，学校教的课程偏理论，大部分是老师课堂没时间让我们实践。光教理论课程时间都紧缺。所以我们需要在课余时间学会上机实践。
• 实践是检验真理的唯一标准
• 3.多画图，多思考。数据结构在你想不出来的时候一定要多画图。可以用windows自带的画图工具 也可以在本本上用笔画图。都可以。适合自己的才是最好的。画完图之后你就思路开阔了。

提示：以下是本篇的正文，环境是vs2022编译器，用devc++也可以实现，再次提醒，要做到心中有图，你就会觉得如此简单

❤️准备任务

• 首先，在头文件中创建顺序表结构体。这个结构体里面包含一个指向这个结构体的指针a。和数据的个数size。因为我们实现的动态的顺序表，所以还有一个容量变量capacity。
• 学过C语言的应该都能看懂下面的代码。看不懂的就要好好补补C语言了。或者在评论区可以询问，第一时间回复喔。

一、🌳初始化

• 这里在源文件里定义了SeqList结构体类型的变量s。`需要注意的是实参部分要传地址。第一是因为这样代码效率会高，假如传值的话形参会在栈区给实参再拷贝一份，这会导致压栈占用内存，
• 第二是因为在链表章节的时候要改变实参现有的值的话，你把s里的值传过去。形参psl只是一份拷贝而已。你改变psl里面的值是不会影响实参s的值的，这一点要格外注意。
• 关于为什么要初始化，原因是因为才开始需要给变量赋值，否则变量里面的值都是随机值，后面用的时候可能会出错。

1. testSeqList0310.c 2.Seqlist.h 3.SeqList.c

二、🌳尾插

• 因为尾插简单所以先写尾插的代码。
• 但在尾插之前，因为顺序表是空的，所以需要先扩容（SeqListCheckCapacity），也就是判断顺序表是否满了。来增加顺序表元素的数量。

1. testSeqList0310.c2.Seqlist.h

1.❤️扩容

1. SeqList.c
   

• 当if (psl->size == psl->capacity)判断完顺序表满的的时候。一般扩容都有个规则，就是扩容到原来的二倍。但是才开始初始化的capacity是0。所以乘2就是0了。这就是一个bug，所以就先暂时赋值给临时变量newCapaity。然后再托付给他值得一辈子人——也就是这个操作psl->capacity =newCapacity;
• 要考虑到扩容失败这个情况，顺序表提高就是我们的细节能力。假如扩容失败也就是tmp指向的空间为空，就exit结束程序。

2.尾插

• 尾插很简单啊，因为元素下标比元素个数少一。元素个数是psl->size.直接数组访问这个位置，然后赋值就可以了。顺便元素个数自增
• size分别为时0,1,2,3,4.可以带进去思考一下。

三、🌳打印

1. SeqList.c
   

• 尾插后我们要展示出道界面上查看。所以我们需要打印，用for循环遍历顺序表就可以打印了。如图为结果。

五、🌳头插

分别头插0和负一，然后打印

1. testSeqList0310.c

1. Seqlist.h
   

和上面几个操作一样。头文件内需要先声明函数。一般良好的编程习惯是函数的声明和定义分离。

3.

SeqList.c

头插就是把顺序表中的数依次往后挪一个位置，给第一个位置空出来。进而实现名义上的头插。
还是需要注意要先判断顺序表满了没有

六、🌳指定下标位置插入

1. testSeqList0310.c 注意。这里是在指定下标的位置插入数据。所以说只要下标所对应的值合法，就可以进行插入。

2. Seqlist.h
   

插入的算法时间复杂度为大O(n)

1. SeqList.c
   

注意细节。在这里需要先判断指针是否为空。然后再判断指定的下标是否越界。如果越界return返回。return的结果是跳出这个函数，然后执行此函数的下一条语句。这两步的判断可以使程序更加健壮
注意边界问题。

当指定的下标pos为0就相当于是头插了。当pos为size时，这时就相当于尾插了

。

七、🌳尾删

当我们学会了尾插。那尾删也易如反掌。但尾删也不是真正意义上的删除只需要让size–就达到尾删了。
当然这样就错了，你还需要判断顺序表是否为空。为空的话就return就好了。

1. Seqlist.h
   

1. SeqList.c
   

八、🌳头删

1. testSeqList0310.c 头删也不是真正的把首元素地址上的值删掉。而是后面的往前依次覆盖，把首元素的值覆盖了就完成头删了。

2. Seqlist.h
   

1. SeqList.c
   

九、🌳指定下标位置删除

同指定位置插入，不赘述

1. testSeqList0310.c

2. Seqlist.h
   

1. SeqList.c
   

十、🌳查找某个元素

遍历一遍顺序表，然后判断每个元素是否等于所查找的值，若查到则返回其下标。
3.

SeqList.c

最后，🌳销毁

• 销毁时需要注意要free掉原来的空间后，一定要将原来的地址置为空，否则a就是一个野指针了。
• free的时候编译器才会检查指针是否越界。这时候报的错一般都是越界的问题。

❤️总结

• 顺序表还是特别需要画图。画完图代码就是顺水成章就写出来了，也不是很难。
• 最重要的还是多练习。多思考。
• 顺序表直接访问某个元素的时间复杂度为O(1)头插，头删或者中间插入的时间复杂度为O(n)

喜欢数据结构系列的就点击订阅吧，下期更新最

常用的无头单向不循环

链表。

test0310.c

#define _CRT_SECURE_NO_WARNINGS#include"SeqList.h"intmain(){
    SeqList s;SeqListInit(&s);SeqListPushBack(&s,1);SeqListPushBack(&s,2);SeqListPushBack(&s,3);SeqListPushBack(&s,4);SeqListPushFront(&s,0);SeqListPushFront(&s,-1);SeqListPrint(&s);SeqListInsert(&s,2,5);SeqListPrint(&s);SeqListPopFront(&s);SeqListPrint(&s);SeqListErease(&s,2);SeqListPrint(&s);SeqListDestroy(&s);return0;}

SeqList.h

#define _CRT_SECURE_NO_WARNINGS//防止被重复包含#pragma once#include<stdio.h>#include<stdlib.h>#include<assert.h>//要求存储的数据必须从0开始，依次连续存储typedefint SLDataType;typedefstruct SeqList
{
    SLDataType* a;int size;//数据个数int capacity;//数据空间大小}SL, SeqList;//初始化voidSeqListInit(SeqList* psl);//扩容voidSeqListCheckCapacity(SeqList* psl);//尾插O(1)voidSeqListPushBack(SeqList* psl, SLDataType x);//打印voidSeqListPrint(SeqList* psl);//头插O(n)voidSeqListPushFront(SeqList* psl, SLDataType x);//指定位置插入O(n)voidSeqListInsert(SeqList* psl, SLDataType pos, SLDataType x);//尾删O(1)voidSeqListPopBack(SeqList* psl);//头删O(n)voidSeqListPopFront(SeqList* psl);//指定位置删除voidSeqListErease(SeqList* psl, SLDataType pos);//销毁动态开辟的空间voidSeqListDestroy(SeqList* psl);//查找voidSeqListFind(SeqList* psl, SLDataType x);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS#include"SeqList.h"//销毁voidSeqListDestroy(SeqList* psl){assert(psl);free(psl->a);
    psl ->a =NULL;
    psl->capacity = psl->size =0;}//初始化voidSeqListInit(SeqList* psl){assert(psl);
    psl->a =NULL;
    psl->size =0;
    psl->capacity =0;}//打印voidSeqListPrint(SeqList* psl){assert(psl);for(int i =0; i < psl->size; i++){printf("%d ", psl->a[i]);}printf("\n");}//检查是否需要扩容voidSeqListCheckCapacity(SeqList* psl){if(psl->size == psl->capacity){int newCapacity = psl->capacity ==0?4: psl->capacity *2;
        SLDataType* tmp =realloc(psl->a,sizeof(SLDataType)* newCapacity);if(tmp ==NULL){printf("realloc fail");exit(-1);}else{
            psl->a = tmp;
            psl->capacity =newCapacity;}}}//尾插voidSeqListPushBack(SeqList* psl, SLDataType x){assert(psl);SeqListCheckCapacity(psl);
    psl->a[psl->size]= x;
    psl->size++;}//尾删voidSeqListPopBack(SeqList* psl){assert(psl);if(psl->size >0){
        psl->size--;}}//头插voidSeqListPushFront(SeqList* psl, SLDataType x){assert(psl);SeqListCheckCapacity(psl);int end = psl->size -1;while(end >=0){
        psl->a[end +1]= psl->a[end];
        end--;}
    psl->a[0]= x;
    psl->size++;}//头删voidSeqListPopFront(SeqList* psl){assert(psl);//挪出数据，腾出头部空间if(psl->size >0){int begin =1;while(begin < psl->size){
            psl->a[begin -1]= psl->a[begin];++begin;}--psl->size;}}//指定位置插入voidSeqListInsert(SeqList* psl, SLDataType pos, SLDataType x){assert(psl);if(pos > psl->size){printf("pos越界");return;}else{int end = psl->size;SeqListCheckCapacity(psl);while(end > pos){
            psl->a[end]= psl->a[end -1];--end;}
        psl->a[pos]= x;++psl->size;}}//指定位置删除O(n)voidSeqListErease(SeqList* psl, SLDataType pos){assert(psl);if(pos >0&& pos < psl->size){int begin = pos;while(begin < psl->size){
            psl->a[begin -1]= psl->a[begin];++begin;}--psl->size;}}//查找voidSeqListFind(SeqList* psl, SLDataType x){assert(psl);for(int i =0; i < psl->size; i++){if(psl->a[i]== x){return i;}else{return-1;}}}