用C语言实现顺序表（数据结构）

迷南。 2024-04-23 20:11 6阅读 0赞

线性表按其存储结构来分，可以分为顺序表和链表。  
![在这里插入图片描述][d715b8fd7a9542a6836880b967ab1bd8.png]

--------------------

**顺序表**：*表中元素的逻辑顺序与物理顺序相同*

#### 顺序表的特点 ####

*      1.随机存取(主要)，可在O(1)内找到指定的元素
 *      2.存储密度高
 *      3.插入和删除操作需要移动大量元素

C语言实现如下：

// 顺序表的最大长度
    #define MaxSize 20
    
    #define InitSize 20
    
    // 静态分配
    typedef struct 
    {
        
       int data[MaxSize]; // 用静态"数组"存放数据元素
       int length; // 顺序表的当前长度(当前元素的个数)
     }SqList1;
    
    // 动态分配
    typedef struct 
    {
        
        int *data; // 数据
        int MaxSize, length; // 数组的最大容量、当前元素个数
    }SqList;

#include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    
    // 顺序表的初始长度
    
    #define InitSize 20
    
    // 动态分配
    typedef struct 
    {
        
        int *data; // 数据
        int MaxSize, length; // 数组的最大容量、当前元素个数
    }SqList;
    
    // 基本操作
    
    /**
     * 初始化顺序表
     */
    void InitList(SqList *L) 
    {
        
        // 给结构体中的data分配内存空间
        L->data = (int *)malloc(sizeof(int) * InitSize);
        L->length = 0;
        L->MaxSize = InitSize;
    }
    
    /**
     * 增加顺序表的长度,动态扩容
     */
    void IncreaseSize(SqList *L)
    {
        
        int len;
        int *p = L->data; // p指针指向原来顺序表的首地址
        printf("请输入你要增加的顺序表的长度：\n");
        scanf("%d", &len);
    
        // 分配新的内存空间
        L->data = (int *)malloc(sizeof(int) * (L->MaxSize + len));
    
        // 把原来顺序表的元素复制到新的顺序表
        for (int i = 0; i < L->length; i++)
        {
        
            L->data[i] = p[i];
        }
        
        // 设置新的顺序表的最大长度
        L->MaxSize = L->MaxSize + len;
    
        // 释放原来的空间
        free(p);
      
    }
    
    
    /**
     * 插入一个元素
     */
    bool ListInsert(SqList *L, int i, int e)
    {
        
        // 1.涉及到位置的都要进行边界判断
        // 注意：这里的 i 表示位置，而不是下标，当i的值是[1,L->length+1]时，都是有效的插入位置。
        if (i < 1 || i > L->length+1)
        {
        
            return false;
        }
    
        // 2.判断当前的存储空间是否足够
        if (L->length >= L->MaxSize)
        {
        
            return false;
        }
    
        // 3.将第i个元素及之后的元素后移
        // 注意：数组下标从0开始，length个元素，最后一个元素的下标是length-1，所以j要从最后一个元素下标的后一个位置开始
        for (int j = L->length; j >= i; j--)
        {
        
            L->data[j] = L->data[j-1];
        }
    
        // 4.将待插入元素插入下标【i-1】处
        L->data[i-1] = e;
        
        // 5.将当前元素个数加1
        L->length++;
        return true;
    
    }
    
    /**
     * 删除某个位置的元素
     */
    bool ListDelete(SqList *L, int i)
    {
        
        // 1.判断位置是否合法 [1,L->length]
        if (i < 1 || i > L->length)
        {
        
            return false;
        }
        
        // 2.判断是否是空表
        if (!L->data)
        {
        
            return false;
        }
        
        // 3.删除: 将第i个位置之后的元素前移 [i,L->length-1]
        // 第i个元素下标为[i-1],所以 j 从下标[i]开始
        for (int j = i; j <= L->length-1 ; j++)
        {
        
            L->data[j-1] = L->data[j]; 
        }
        
        // 4.将当前元素个数减1
        L->length--;
    
        return true;
    }
    
    /**
     * 按值查找(顺序查找)
     * @return 该元素的位置(不是下标)
     */
    int GetElement(SqList *L, int target)
    {
        
        // 遍历整个线性表
        for (int i = 0; i < L->length; i++)
        {
        
            if (L->data[i] == target)
            {
        
                return i+1;
            }
        }
        
        return 0; // 返回0,说明查找失败
    }
    
    /**
     * 顺序表的销毁
     */
    void DestroyList(SqList *L)
    {
        
        char ch;
        printf("是否销毁顺序表(Y/N): ");
        scanf("%c", &ch);
        if (ch == 'Y')
        {
        
            L->length = 0;
            L->MaxSize = 0;
            free(L->data);
            printf("顺序表已成功销毁!");
        }
        
    }
    
    /**
     * 打印顺序表
     */
    void PrintList(SqList *L)
    {
        
        if (!L->data)
        {
        
          printf("该顺序表为空!");
          return;
        }
        for (int i = 0; i < L->length; i++)
        {
        
            printf("%d ", L->data[i]);
        }
        printf("\n");
        
    }

[d715b8fd7a9542a6836880b967ab1bd8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/90e75ea2fc9e43dbbbf294ba5ea355eb.png