0
0

顺序表C语言版

文章目录

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。
线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
在这里插入图片描述

2.顺序表

2.1概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组 上完成数据的增删查改。 顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储元素。在这里插入图片描述
2. 动态顺序表：使用动态开辟的数组存储。在这里插入图片描述

2.2接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
我们采用分文件的方式来实现：

2.2.1 SeqList.h

#pragma once#include<stdio.h>#include<string.h>#include<assert.h>typedefint SLDataType;typedefstruct SeqList
{
    SLDataType *a;int size;int capacity;}SL;voidSeqListInit(SL *ps);voidSeqListPrint(SL *ps);voidSeqListDestroy(SL *ps);voidSeqListCheckCapacity(SL *ps);//增删查改等接口函数// 时间复杂度是O(1) 尾插，尾删voidSeqListPushBack(SL* ps, SLDataType x);voidSeqListPopBack(SL* ps);// 时间复杂度是O(N)voidSeqListPushFront(SL* ps, SLDataType x);voidSeqListPopFront(SL* ps);// 在pos位置插入xvoidSeqListInsert(SL* ps, size_t pos, SLDataType x);// 删除pos位置的数据voidSeqListErase(SL* ps, size_t pos);// 顺序表查找intSeqListFind(SL* ps, SLDataType x);//顺序表改voidSeqListModify(SL *ps, size_t pos, SLDataType x);

2.2.2 SeqList.c

2.2.2.1 初始化顺序表

voidSeqListInit(SL *ps){
    ps->a =NULL;
    ps->size =0;
    ps->capacity =0;}

2.2.2.2 打印顺序表

voidSeqListPrint(SL *ps){assert(ps);for(int i=0;i<ps->size;i++){printf("%d ",ps->a[i]);}printf("\n");}

2.2.2.3 释放顺序表

voidSeqListDestroy(SL *ps){free(ps->a);
    ps->a=NULL;
    ps->size=ps->capacity=0;}

2.2.2.4 检查容量并扩容

voidSeqListCheckCapacity(SL *ps){if(ps->size==ps->capacity){int newcapacity = ps->capacity ==0?4:ps->capacity*2;//我们把capacity初始化为0，直接写成newcapacity=ps->capacity*2就出bug了哦
        SLDataType *tmp =(SLDataType*)realloc(ps->a,newcapacity*sizeof(SLDataType));if(tmp==NULL){printf("realloc fail\n");exit(-1);}else{
            ps->a=tmp;
            ps->capacity =newcapacity;}}}

在这里插入图片描述
注：我们知道realloc存在原地扩和异地扩的情况，而且扩容失败会返回空指针，所以用realloc扩容一定要记得检查是否扩容成功。

2.2.2.5 尾插

voidSeqListPushBack(SL *ps, SLDataType x){SeqListCheckCapacity(ps);
    ps->a[ps->size]=x;
    ps->size++;}

2.2.2.6 尾删

voidSeqListPopBack(SL *ps){assert(ps->size >0);
    ps->size--;}

2.2.2.7 头插

voidSeqListPushFront(SL *ps,SLDataType x){SeqListCheckCapacity(ps);int end = ps->size-1;while(end>=0){
        ps->a[end+1]=ps->a[end];
        end--;}
    ps->a[0]=x;
    ps->size++;}

在这里插入图片描述

2.2.2.8 头删

voidSeqListPopFront(SL *ps){assert(ps);if(ps->size>0){int start =1;while(start < ps->size){
            ps->a[start-1]=ps->a[start];
            start++;}
        ps->size--;}}

在这里插入图片描述

2.2.2.9 在pos位置插入x

// 在pos位置插入xvoidSeqListInsert(SL* ps, size_t pos, SLDataType x){assert(ps);if(pos>ps->size){printf("pos 越界:%d\n",pos);return;}SeqListCheckCapacity(ps);int end = ps->size-1;while(end >= pos){
        ps->a[end+1]=ps->a[end];
        end--;}
    ps->a[pos]=x;
    ps->size++;}

大家看这种写法有没有问题。
请看下面一种情况：
在这里插入图片描述
当end走到-1时，与end进行比较时会整型提升为

size_t

类型，会变成一个很大的数，此时程序会进入死循环。

正确的写法：

// 在pos位置插入xvoidSeqListInsert(SL* ps, size_t pos, SLDataType x){assert(ps);if(pos>ps->size){printf("pos 越界:%d\n",pos);return;}SeqListCheckCapacity(ps);
    size_t end = ps->size;while(end > pos){
        ps->a[end]=ps->a[end-1];
        end--;}
    ps->a[pos]=x;
    ps->size++;}

在这里插入图片描述
注：
在这里插入图片描述

2.2.2.10 删除pos位置的数据

// 删除pos位置的数据voidSeqListErase(SL* ps, size_t pos){assert(pos<ps->size);int start = pos+1;while(start < ps->size){
        ps->a[start-1]=ps->a[start];
        start++;}
    ps->size--;}

在这里插入图片描述
下一次尾插数据直接覆盖4.

2.2.2.11 顺序表查找

// 顺序表查找intSeqListFind(SL* ps, SLDataType x){for(int i=0;i<ps->size;i++){if(ps->a[i]==x){return i;}}return-1;}

2.2.2.12 顺序表修改

//顺序表改voidSeqListModify(SL *ps, size_t pos, SLDataType x){aseert(pos<ps->size);
    ps->a[pos]=x;}

2.2.2.13 利用Erase，Insert接口简化尾插、尾删、头插、头删

voidSeqListPushBack(SL* ps, SLDataType x){assert(ps);SeqListInsert(ps, ps->size, x);}

voidSeqListPopBack(SL* ps){assert(ps);SeqListErase(ps, ps->size-1);}

voidSeqListPushFront(SL* ps, SLDataType x){assert(ps);SeqListInsert(ps,0, x);}

voidSeqListPopFront(SL* ps){assert(ps);SeqListErase(ps,0);}

2.2.2.14 SeqList.c完整代码

#include"SeqList.h"voidSeqListInit(SL* ps){
    ps->a =NULL;
    ps->size =0;
    ps->capacity =0;}voidSeqListPrint(SL* ps){assert(ps);for(int i =0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");}voidSeqListDestroy(SL* ps){free(ps->a);
    ps ->a =NULL;
    ps->size = ps -> capacity =0;}voidSeqListCheckCapacity(SL* ps){if(ps->size == ps->capacity){int newcapacity = ps->capacity ==0?4: ps->capacity *2;//我们把capacity初始化为0，直接写成newcapacity=ps->capacity*2就出bug了哦
        SLDataType* tmp =(SLDataType*)realloc(ps->a, newcapacity *sizeof(SLDataType));if(tmp ==NULL){printf("realloc fail\n");exit(-1);}else{
            ps->a = tmp;
            ps->capacity = newcapacity;}}}voidSeqListPushBack(SL* ps, SLDataType x){SeqListCheckCapacity(ps);
    ps->a[ps->size]= x;
    ps->size++;}voidSeqListPopBack(SL* ps){assert(ps->size >0);
    ps->size--;}voidSeqListPushFront(SL* ps, SLDataType x){SeqListCheckCapacity(ps);int end = ps->size -1;while(end >=0){
        ps->a[end +1]= ps->a[end];
        end--;}
    ps->a[0]= x;
    ps->size++;}voidSeqListPopFront(SL* ps){assert(ps);if(ps->size >0){int start =1;while(start < ps->size){
            ps->a[start -1]= ps->a[start];
            start++;}
        ps->size--;}}// 在pos位置插入xvoidSeqListInsert(SL* ps, size_t pos, SLDataType x){assert(ps);if((int)pos > ps->size){printf("pos 越界:%d\n", pos);return;}SeqListCheckCapacity(ps);
    size_t end = ps->size;while(end > pos){
        ps->a[end]= ps->a[end -1];
        end--;}
    ps->a[pos]= x;
    ps->size++;}// 删除pos位置的数据voidSeqListErase(SL* ps, size_t pos){assert((int)pos < ps->size);int start = pos +1;while(start < ps->size){
        ps->a[start -1]= ps->a[start];
        start++;}
    ps->size--;}// 顺序表查找intSeqListFind(SL* ps, SLDataType x){for(int i =0; i < ps->size; i++){if(ps->a[i]== x){return i;}}return-1;}//顺序表改voidSeqListModify(SL* ps, size_t pos, SLDataType x){assert((int)pos < ps->size);
    ps->a[pos]= x;}

2.2.3 Test.c

#define _CRT_SECURE_NO_WARNINGS 1#include"SeqList.h"voidTestSeqList1(){
    SL s;SeqListInit(&s);SeqListPushBack(&s,1);SeqListPushBack(&s,2);SeqListPushBack(&s,3);SeqListPushBack(&s,4);SeqListPushBack(&s,5);SeqListPushBack(&s,0);SeqListPrint(&s);SeqListPopBack(&s);SeqListPopBack(&s);SeqListPrint(&s);SeqListPrint(&s);SeqListPushBack(&s,10);SeqListPushBack(&s,20);SeqListPrint(&s);//SeqListPrint(NULL);// 越界不一定能检查出来，越界是抽查// 就像查酒驾一样。不一定会被查到，但是我们一定不能酒驾//int a[10];//a[10] = 1;//a[11] = 1;//a[12] = 1;//a[100] = 1;}voidTestSeqList2(){/*int* p = (int*)malloc(sizeof(int) * 10);
    printf("%p\n", p);

    int* p1 = (int*)realloc(p, sizeof(int) * 100);
    printf("%p\n", p1);*/

    SL s;SeqListInit(&s);SeqListPushBack(&s,1);SeqListPushBack(&s,2);SeqListPushBack(&s,3);SeqListPushBack(&s,4);SeqListPushFront(&s,0);SeqListPushFront(&s,-1);SeqListPrint(&s);SeqListPopFront(&s);SeqListPopFront(&s);SeqListPopFront(&s);SeqListPopFront(&s);SeqListPopFront(&s);SeqListPrint(&s);SeqListPopFront(&s);SeqListPrint(&s);SeqListPopFront(&s);SeqListPopFront(&s);SeqListPushFront(&s,0);SeqListPushFront(&s,-1);SeqListPrint(&s);}voidTestSeqList3(){
    SL s;SeqListInit(&s);SeqListPushBack(&s,1);SeqListPushBack(&s,2);SeqListPushBack(&s,3);SeqListPushBack(&s,4);SeqListPrint(&s);SeqListInsert(&s,10,100);SeqListInsert(&s,1,20);SeqListInsert(&s,5,50);SeqListInsert(&s,0,50);SeqListPrint(&s);SeqListDestroy(&s);}voidTestSeqList4(){
    SL s;SeqListInit(&s);SeqListPushBack(&s,1);SeqListPushBack(&s,2);SeqListPushBack(&s,3);SeqListPushBack(&s,4);SeqListPushBack(&s,5);SeqListPrint(&s);SeqListErase(&s,4);SeqListPrint(&s);SeqListErase(&s,0);SeqListPrint(&s);SeqListErase(&s,1);SeqListPrint(&s);}voidTestSeqList5(){
    SL s;SeqListInit(&s);SeqListPushBack(&s,1);SeqListPushBack(&s,2);SeqListPushBack(&s,3);SeqListPushBack(&s,4);SeqListPushBack(&s,5);SeqListPushFront(&s,-1);SeqListPushFront(&s,-2);SeqListPrint(&s);SeqListPopFront(&s);SeqListPopFront(&s);SeqListPopBack(&s);SeqListPopBack(&s);SeqListPrint(&s);}voidmenu(){printf("***********************************************\n");printf("1.尾插数据 2.头插数据\n");printf("5.打印数据 6.查找数据\n");printf("-1.退出 \n");printf("***********************************************\n");}intmain(){TestSeqList5();//SL s;//SeqListInit(&s);//int option = -1;//do//{//    menu();//    printf("请选择你的操作:>");//    scanf("%d", &option);//    if (option == 1)//    {//        printf("请输入你要尾插的数据:>");//        //int val = 0;//        SLDataType val = 0;//        scanf("%d", &val);//        SeqListPushBack(&s, val);//    }//    else if (option == 5)//    {//        SeqListPrint(&s);//    }//} while (option != -1);//SeqListDestroy(&s);return0;}

注：
测试接口时最好写一个接口测一个接口，不要一口气写完再测试，不然你会崩溃的哦。

2.2.4 运行结果

在这里插入图片描述

3.数组相关面试题

3.1. 原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。

思路1：

查找到每一个val，依次挪动数据覆盖,时间复杂度O(N^2).
在这里插入图片描述

思路2：

把不是val的值拷贝到新数组，时间复杂度O(N),空间复杂度O(N).
在这里插入图片描述

思路3：

双指针，时间复杂度O(N),空间复杂度O(1)
令dst，src为0，如果src下标处的值不等于val，则nums[dst]=nums[src]，src++，dst++。否则只让src++。
在这里插入图片描述

代码：

intremoveElement(int* nums,int numsSize,int val){int src =0;int dst =0;while(src < numsSize){if(nums[src]!= val){
            nums[dst]= nums[src];
            dst++;
            src++;}else{
            src++;}}return dst;}

3.2 删除排序数组中的重复项。

在这里插入图片描述
代码：

intremoveDuplicates(int* nums,int numsSize){int src =1;int dst =0;while(src < numsSize){if(nums[src]== nums[src-1]){
            src++;}else{
            nums[dst]= nums[src-1];
            src++;
            dst++;}}
    nums[dst]= nums[numsSize-1];
    dst++;return dst;}

3.3 合并两个有序数组

思路1：

在这里插入图片描述

思路2：

在这里插入图片描述

思路3：要求不能额外开数组。

一种情况：
在这里插入图片描述
另一种情况：
在这里插入图片描述

代码：

voidmerge(int* nums1,int nums1Size,int m,int* nums2,int nums2Size,int n){int i = m-1, j = n-1;int dst = m+n-1;while(i >=0&& j >=0){if(nums1[i]>nums2[j]){
            nums1[dst--]= nums1[i--];}else{
            nums1[dst--]= nums2[j--];}}while(j >=0){
        nums1[dst--]= nums2[j--];}}

4. 顺序表的问题及思考

问题：

  1. 中间/头部的插入删除，时间复杂度为O(N)
  2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
  3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。 思考：如何解决以上问题呢？这就需要链表的结构来解决。
标签： c语言 链表 数据结构
本文转载自: https://blog.csdn.net/iwkxi/article/details/123530398
版权归原作者 Yuucho 所有， 如有侵权，请联系我们删除。
登录后发布评论

“顺序表C语言版”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

Docker 中使用环境变量的安全实践

[Linux]——常见指令（中）

【IntelliJ IDEA】IntelliJ IDEA中文语言包不起作用

vscode gitlens收费破解

是时候用开源降低AI落地门槛了

毕设开源 深度学习手写数字识别系统(源码+论文)

毕业设计 大数据电商用户行为分析及可视化(源码+论文)

文章导航