数据结构严蔚敏——线性表的顺序存储

爱被打了一巴掌 2022-05-19 10:52 155阅读 0赞

**线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。**

**其实就是用数组来进行元素的存储以及一系列操作。**

它的存储结构为：

#define LIST_INIT_SIZE 100
    
    typedef struct Arry
    {
        int* Addr;              //数组的基地址
        int size;              //指示当前数组中元素的个数，也就是数组的长度
        int capacity;         //表示数组的容量
    }Arry;

所有的操作就是基于这个结构体进行操作，对其进行插入（尾插、有序插入）、删除（按位置，按值）、逆置等一系列操作，详细请看代码。

以下这个头文件是顺序存储的定义以及部分操作的实现Arry.h

#ifndef ARRY_H_INCLUDED
    #define ARRY_H_INCLUDED
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define LIST_INIT_SIZE 100
    
    typedef struct Arry
    {
        int* Addr;              //数组的基地址
        int size;              //指示当前数组中元素的个数
        int capacity;         //表示数组的容量
    }Arry;
    
    Arry *Init_Arry()    //初始化
    {
        Arry * myarry = (Arry *)malloc(sizeof(Arry));
        myarry ->size = 0;
        myarry ->capacity = LIST_INIT_SIZE;
        myarry ->Addr = (int*)malloc(sizeof(int) * myarry -> capacity);
        return myarry;
    }
    
    void Destory_Arry(Arry *arr)
    {
        if(arr == NULL)
        {
            return ;
        }
        arr ->size = 0;
    }
    void Push_Arry(Arry *arr,int value)//增
    {
        if(arr -> size == arr ->capacity)
        {
            int *newspace = (int *)malloc(arr -> capacity * 3 *sizeof(int));  //申请一块更大的存储空间
            memcpy(newspace,arr -> Addr,arr -> capacity * sizeof(int));       //将元素拷贝过来
            free(arr->Addr);                                                  //释放原来的空间
            if(!newspace)                                                     //判断是否申请成功
                exit(-1);
            arr->capacity = arr->capacity *3;                                 //更新容量
            arr->Addr = newspace;                                             //更新地址
        }
        arr ->Addr[arr->size] = value;                                        //插入新元素
        arr ->size++;
    }
    void Push_OrderArry(Arry *arr, int value)              //有序插入
    {
        if(arr -> size == arr -> capacity)
        {
            int *newspace = (int *)malloc(arr -> capacity *2*sizeof(int));
            memcpy(newspace,arr -> Addr , arr -> capacity * sizeof(int));
            free(arr -> Addr);
            if( !newspace)
                exit(-1);
            arr -> Addr = newspace;
            arr -> capacity = arr -> capacity * 2;
        }
        int i;
        for( i = arr -> size; value < arr -> Addr[i - 1]; i--)
        {
            arr -> Addr[i] = arr -> Addr[i - 1];
        }
        arr -> Addr[i] = value;
        arr -> size++;
    
    }
    void RemoveByPos(Arry *arr,int pos) //按位置删
    {
        if(arr == NULL)
        {
            printf("数组为空,不可以进行删除！");
            return;
        }
        if( pos < 0 || pos >= arr -> size)
        {
            printf("您输入的位置无效，请重新输入！");
            return;
        }
        int i;
        for(i = pos; i < arr -> size; i++)
        {
            arr -> Addr[i] = arr -> Addr[i+1];
        }
        arr ->size--;
    }
    
    void RemoveByValue(Arry *arr,int value)//按值删
    {
         if(arr == NULL)
        {
            printf("数组为空,不可以进行删除！");
            return;
        }
        int i = 0,j = 0;
        while(arr -> Addr[i] != value)
        {
           i++;
           if( i == arr ->size)
           {
              printf("你要删除的值不存在，请重新输入：");
              return;
           }
        }
        for(j = i - 1; j < arr -> size; j++)
        {
            arr -> Addr[j] = arr -> Addr[j+1];
        }
        arr ->size--;
    }
    
    int Find_Arry(Arry *arr,int value)            //查找
    {
         if(arr == NULL)
        {
            printf("数组为空,请为数组赋值!");
            return -1;
        }
        int i = 0;
        while(arr ->Addr[i++] != value)
            if( i == arr ->size)
            {
             printf("您要查找的值不存在！");
             return -1;
            }
        printf("您要查找的数位于下表为%d的位置！",i);
        return i;
    }
    
    void Print_Arry(Arry *arr)             //打印
    {
        int i;
        if(arr == NULL)
        {
            printf("数组为空！");
            return;
        }
        for(i = 0; i < arr -> size; i++)
        {
          printf("%d ",arr->Addr[i]);
        }
        printf("\n");
    }
    
    void Free_Arry(Arry *arr)         //释放
    {
        if(arr == NULL)
            return;
        if(arr ->Addr != NULL)
        {
            free(arr -> Addr);
        }
        free(arr);
    }
    void Reverse_Arry(Arry *arr)
    {
        if(arr == NULL)
        {
            printf("数组为空！\n");
            return;
        }
        int i,temp;
        for(i = 0; i < arr->size/2; i++)
        {
            temp = arr->Addr[i];
            arr->Addr[i] = arr->Addr[arr->size - i - 1];
            arr->Addr[arr->size - i - 1] = temp;
        }
        printf("数组逆转成功！\n");
    }
    #endif // ARRY_H_INCLUDED

下面是主函数对实现的顺序存储进行的测试main.c

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #include "Arry.h"
    void testReverse()      //测试逆置
    {
        int i;
        Arry * myarry = Init_Arry(); //初始化
    
        for( i= 1; i <= 5;i++ )   //插入元素
        {
            Push_Arry(myarry,i);
        }
        Print_Arry(myarry);    //打印
        Reverse_Arry(myarry);
        Print_Arry(myarry);
    }
    void test()                 //测试顺序存储
    {
        int i;
        Arry * myarry = Init_Arry(); //初始化
        Arry * myarry1 = Init_Arry();
        for( i= 0; i < 5;i++ )   //插入元素
        {
            Push_Arry(myarry,i);
        }
        for( ; i < 10; i++ )
        {
            Push_Arry(myarry1,i);
        }
        Print_Arry(myarry);    //打印
        Print_Arry(myarry1);
        printf("当前容量为；%d\n",myarry ->capacity);
        printf("当前元素个数为：%d\n",myarry ->size);
        //Find_Arry(myarry,5);
        //Push_OrderArry(myarry,0);
        //Print_Arry(myarry);
        /*Push_Arry(myarry,10);
        Print_Arry(myarry);
    
    
        printf("\n");
        printf("当前容量为；%d\n",myarry ->capacity);
        printf("当前元素个数为：%d\n",myarry ->size);
    
        RemoveByPos(myarry,10);
        printf("按位置删除后：");
        Print_Arry(myarry);
    
        RemoveByValue(myarry,5);
        printf("按值删除后:");
        Print_Arry(myarry);
        printf("释放后的数组：");
        Free_Arry(myarry);
    
        Print_Arry(myarry);*/
    }
    int main()
    {
        //testReverse();
        //test();
        system("pause");
        return 0;
    }

**注：部分函数在测试的时候已经注释掉，如需参考请略加修改。**