初识数据结构——顺序表

【数据结构】之顺序表（C语言版）

目录

1.线性表的定义

线性表是n个具有相同特性的数据元素的有限序列，线性表是一种在实际生活中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串…

2.什么是顺序表

顺序表即是线性表的顺序存储，他是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

顺序表的定义

typedefint SLDataType;//类型重命名//动态顺序表typedefstructSeqList{
    SLDataType* a;//指向动态开辟的数组int size;//表示数组中存储了多少个数据int capacity;//数组实际能存储的空间是多大}SL;

3.顺序表的接口实现

需要分装三个部分实现：Seqlist.h、Seqlist.c、test.c。
【Seqlist.h】里面用来写相关头文件的引用、接口函数的声明和结构体的类型定义。
【Seqlist.c】里面用来实现所有的接口函数。
【test.c】里面用来测试接口函数以及功能菜单的实现
【Seqlist.c】头文件以及相关代码如下：

#pragmaonce//防止头文件倍二次引用#include<stdio.h>#include<stdlib.h>#include<string.h>#include<assert.h>typedefint SLDataType;//类型重命名//动态顺序表typedefstructSeqList{
    SLDataType* a;//指向动态开辟的数组int size;//表示数组中存储了多少个数据int capacity;//数组实际能存储的空间是多大}SL;//初始化顺序表voidSeqListInit(SL* ps);//顺序表尾插入voidSeqListPushBack(SL* ps);//顺序表尾删除voidSeqListPopBack(SL* ps);//顺序表头插入voidSeqListPusFront(SL* ps);//顺序表头删除voidSeqListPopFront(SL* ps);//顺序表检测增容问题voidSeqListCheckCapacity(SL* ps);//顺序表查找指定值intSeqListFind(SL* ps, SLDataType x);//顺序表指定下标位置插入voidSeqListInsert(SL* ps);//删除pos位置的数据voidSeqListErase(SL* ps);//打印顺序表voidSeqListPrint(SL* ps);//销毁顺序表voidSeqListDestory(SL* ps);//顺序表修改指定元素数值voidSeqListModify(SL* ps);

【test.c】文件中菜单的实现如下：

#define_CRT_SECURE_NO_WARNINGS1#include"Seqlist.h"voidmenu(){printf("                      顺序表操作                    \n");printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");printf("             1.尾插入           2.尾删除            \n");printf("             3.头插入           4.头删除            \n");printf("             5.指定下标位置插入 6.打印顺序表        \n");printf("             7.删除指定位置数据 8.修改指定数值      \n");printf("~~~~~~~~~~~~~~~~~~~~~0.退出程序~~~~~~~~~~~~~~~~~~~~~\n");}intmain(){int input =0;
    SL s1;SeqListInit(&s1);//初始化顺序表do{menu();printf("请选择:");scanf("%d",&input);switch(input){case1:SeqListPushBack(&s1);//尾插break;case2:SeqListPopBack(&s1);//尾删break;case3:SeqListPusFront(&s1);//头插break;case4:SeqListPopFront(&s1);//头删break;case5:SeqListInsert(&s1);//指定下标位置插入break;case6:SeqListPrint(&s1);//打印顺序表break;case7:SeqListErase(&s1);//删除指定位置数据break;case8:SeqListModify(&s1);//修改指定数值break;case0:SeqListDestory(&s1);//销毁顺序表printf("退出程序\n");break;default:printf("选择错误,请重新选择\n");break;}}while(input);return0;}

（1）初始化顺序表

voidSeqListInit(SL* ps){
    ps->a =NULL;//初始化顺序表为空
    ps->capacity = ps->size =0;//初始化数据个数和数组实际存储的空间为空}

（2）顺序表检测增容问题

为避免频繁增容，我们一次性去增容上一次空间大小的两倍，在这里需要注意的是当传给realloc的指针为空时，realloc的用法等同于malloc。

voidSeqListCheckCapacity(SL* ps){if(ps->capacity == ps->size){//如果是第一次开辟空间，先开辟四个字节大小的存储空间//之后就以原空间二倍的大小去增加容量int newcapacity = ps->capacity ==0?4: ps->capacity *2;
        SLDataType* tmp =realloc(ps->a, 
        newcapacity *sizeof(SLDataType));if(tmp ==NULL){printf("realloc fail\n");exit(-1);//如果内存开辟失败，直接退出程序}
        ps->a = tmp;//将数组指向新开辟的动态存储空间
        ps->capacity = newcapacity;//将容量指向新开辟的大小}}

（3）顺序表尾插

在这里我们使用while循环可以一次性插入多个数据。

voidSeqListPushBack(SL* ps){SeqListCheckCapacity(ps);//插入数据之前，先检测容量是否已满
    SLDataType x;printf("请输入您要插入的元素:");scanf("%d",&x);while(x!=EOF){
        ps->a[ps->size]= x;
        ps->size++;//数据个数+1SeqListCheckCapacity(ps);//检测容量是否已满scanf("%d",&x);}}

函数功能测试

（4）顺序表尾删

voidSeqListPopBack(SL* ps){assert(ps->size);//先断言顺序表是否为空if(ps->size >0){
        ps->size--;//只需将有效数据个数减一即可printf("尾删成功\n");}}

函数功能测试

（5）顺序表头插

和尾插一样，在这里我们可以使用循环一次性插入多个数据

voidSeqListPusFront(SL* ps){SeqListCheckCapacity(ps);//头插之前先检测是否需要增容
    SLDataType x;printf("请输入您要头插的元素:");scanf("%d",&x);while(x !=EOF){int i =0;//遍历数组，使得头部数据到尾部数据依次向后挪动一位for(i = ps->size -1; i >=0; i--)
            ps->a[i +1]= ps->a[i];
        ps->a[0]= x;
        ps->size++;SeqListCheckCapacity(ps);//每插入一个元素，都需要检测容量scanf("%d",&x);}}

函数功能测试

（6）顺序表头删

voidSeqListPopFront(SL* ps){assert(ps->size);//先判断顺序表数据个数是否为空if(ps->size >0){int i =0;//遍历数组，将头元素之后的元素依次向前挪动一位for(i =0; i < ps->size -1; i++)
            ps->a[i]= ps->a[i +1];}
    ps->size--;//有效数据个数减一printf("头删成功\n");}

函数功能测试

（7）顺序表查找指定值

intSeqListFind(SL* ps, SLDataType x){assert(ps->size);//顺序表元素个数是不能为空int i =0;//遍历数组，将所有元素与所需查找的指定元素一一对比while(i < ps->size){//若能找到，返回元素下标if(ps->a[i]== x)return i;
        i++;}return-1;//找不到，则返回-1}

（8）顺序表指定下标位置插入

voidSeqListInsert(SL* ps){int pos =0;
    SLDataType x;printf("请输入下标和需要插入的数据");scanf("%d%d",&pos,&x);//判断指定下标是否超出有效范围，超出范围，则重新输入while(pos<0||pos > ps->size){printf("下标位置超出范围,请重新输入:");scanf("%d",&pos);}SeqListCheckCapacity(ps);//检测顺序表容量是否已满for(size_t i = ps->size -1; i >= pos; i--)
        ps->a[i +1]= ps->a[i];
    ps->a[pos]= x;//插入数据
    ps->size++;//有效数据个数+1printf("插入成功\n");}

函数功能测试

（9）删除指定位置的数据

在这里我们需要注意的是指定pos的范围是大于size-1，而上面的指定插入的pos的范围是大于size。这是因为数组的插入可以在最后一个元素的后面插入，而删除只能是删除最后一个元素。

voidSeqListErase(SL * ps){assert(ps->size);int pos =0;printf("请输入所需删除的数值下标");scanf("%d",&pos);//判断指定位置下表是否超出有效范围while(pos<0|| pos>ps->size -1){printf("pos invalid,请重新输入下标:");//超出范围，重新输入scanf("%d",&pos);}for(int i = pos; i < ps->size; i++)
        ps->a[i]= ps->a[i +1];
    ps->size--;//有效数据个数-1printf("删除成功\n");}

函数功能测试

（10）打印数据表

voidSeqListPrint(SL* ps){assert(ps->size);//断言，元素个数不能为0for(int i =0; i < ps->size; i++)printf("%d ", ps->a[i]);//遍历数组，打印出每一个元素printf("\n");}

（11）顺序表修改指定数值

这里我们需要用到“顺序表查找指定值”这个函数，用一个整型变量来接收所需要修改元素的下标，最后再修改。

voidSeqListModify(SL* ps){
    SLDataType value, x ;//x为所需要修改的元素，value为该元素修改后的值printf("请输入所需要修改的元素:");scanf("%d",&x);int tmp =SeqListFind(ps, x);while(tmp ==-1){printf("该元素不存在,请重新输入:");scanf("%d",&x);//重新输入所需要修改的元素
        tmp =SeqListFind(ps, x);//重新接受新输入元素的下标}if(tmp !=-1){printf("请输入修改后的值:");scanf("%d",&value);
        ps->a[tmp]= value;//将该元素修改为valueprintf("修改成功\n");}}

函数功能测试

（12）销毁顺序表

voidSeqListDestory(SL* ps){assert(ps);free(ps->a)//释放开辟的空间
    ps->a=NULL;
    ps->size =0;//数据个数置为0
    ps->capacity =0;//空间容量置为0}

总节
好了，以上就是顺序表的详解了，各位小伙伴们如果觉得不错的话可以支持一下哦！