数据结构—线性表

线性表的定义：

        线性表是具有相同特性的数据元素的一个有限序列，类似于数组。

        线性表中的元素都有一个直接前驱和直接后继，除了第一个首元素和最后一个元素

线性表的实现：

        使用线性表模拟动态数组的实现：

//.h 文件
#ifndef DYNAMICARRAY_H
#define DYNAMICARRAY_H

//使用c语言实现
#include <stdio.h>
#include <stdlib.h>


//首先定义动态数组的结构体
typedef struct DYNAMICARRAY
{
    int* pAddr;    //存放数据的地址
    int size;      //表示当前数组存放的元素个数
    int capacity;  //当前数组所能容纳的元素的个数
}Dynamic_Array;


//以下是对上述结构体的操作函数


//初始化
Dynamic_Array* Init_Array();

//插入
void Pushback_Array(Dynamic_Array* arr,int value);


//根据值进行删除
void RemoveByValue_Array(Dynamic_Array* arr,int value);

//根据位置进行删除
void RemoveByPos_Array(Dynamic_Array* arr,int pos);

//根据值查找
int FindByValue_Array(Dynamic_Array* arr,int value);

//根据位置查找
int FindByPos_Array(Dynamic_Array* arr,int pos);

//打印
void Print_Array(Dynamic_Array* arr);

//清空数组
void Clear_Array(Dynamic_Array* arr);

//获取数组元素个数
void getSize_Array(Dynamic_Array* arr);

//获取容量
int getCapacity_Array(Dynamic_Array* arr);

//释放数组内存
void FreeSpace_Array(Dynamic_Array* arr);


#endif

//.c 文件

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "DynamicArray.h"

//初始化
Dynamic_Array* Init_Array()
{
    //首先申请一块连续的内存
    Dynamic_Array* arr = (Dynamic_Array*)malloc(sizeof(Dynamic_Array));
    
    arr->size = 0;
    arr->capacity = 20;    //将数组的初始容量设置为20

    arr->pAddr = (int*)malloc(sizeof(int) * arr->capacity);

    return arr;
}

//插入
void Pushback_Array(Dynamic_Array* arr,int value)
{
    if(arr == NULL) return;

    //判断空间是否不足
    if(arr->size == arr->capacity)    //空间已满
    {
        //申请一块内存更大的新空间
        int* newSpace = (int*)malloc(sizeof(int) * arr->capacity * 2);
        //将原来空间中的数据拷贝到新空间
        memcpy(newSpace,arr->pAddr,sizeof(int)*arr->capacity);
        //释放旧内存的空间
        free(arr->pAddr);

        //更新容量
        arr->capacity = arr->capacity*2;
        //将指针指向新的内存空间
        arr->pAddr = newSpace;  
    }    

    //现在进行元素插入
    arr->pAddr[arr->size] = value;
    //将元素个数增加1
    arr->size++;
}


//根据值进行删除
void RemoveByValue_Array(Dynamic_Array* arr,int value)
{
    if(arr == NULL) return;
    
    int flag = -1;
    for(int i = 0; i < arr->size; i++)
    {
        if(arr->pAddr[i] == vlaue)
        {
            flag = i;
            break;
        }
    }    

    for(int j = flag; j < arr->size; j++)
        arr->pAddr[j] = arr->pAddr[j+1];

    arr->size--; 

}

//根据位置进行删除
void RemoveByPos_Array(Dynamic_Array* arr,int pos)
{
    if(arr == NULL)    return;

    if(pos < 0 || pos > arr->size)    return;

    //删除元素
    for(int i = pos; i < arr->size; i++)
        arr->pAddr[i] = arr->pAddr[i+1];

    arr->size--;
}

//根据值查找
int Find_Array(Dynamic_Array* arr,int value)
{
    if(arr == NULL)    return 0;
    
    int pos = -1;
    for(int i = 0; i < arr->size; i++)
    {
        if(arr->pAddr[i] == value)
        {
            pos = i;
            break;
        }
    }

    return pos;
}


//打印
void Print_Array(Dynamic_Array* arr)
{
    if(arr == NULL)    return;

    for(int i = 0; i < arr->size; i++)
        printf("%d ",arr->pAddr[i]);
    printf("\n");
}

//清空数组
void Clear_Array(Dynamic_Array* arr)
{
    if(arr == NULL)    return;

    arr->size = 0;
}

//获取数组元素个数
int getSize_Array(Dynamic_Array* arr)
{
    if(arr == NULL)    return 0;
    
    return arr->size;
}

//获取容量
int getCapacity_Array(Dynamic_Array* arr)
{
    if(arr == NULL)    return 0;
    
    return arr->capacity;
}

//释放数组内存
void FreeSpace_Array(Dynamic_Array* arr)
{
    if(arr == NULL)    return;
    if(arr != NULL)    free(arr->pAddr);
    free(arr);
}


int main()
{
    //初始化动态数组
    Dynamic_Array* myArray = Init_Array();
    //插入元素
    for(int i = 0; i < 10; i++)
    {
        Push_Back_Array(myArray,i);
    }
    //打印
    Print_Array(myArray);

    //销毁
    FreeSpace_Array(myArray);

    return 0;
}

小知识点：

        free() 函数释放的是用 malloc() 申请在堆上的内存空间，而不是指针本身。

当我们使用 malloc() 函数动态分配内存时，会在堆(heap)上分配一块指定大小的内存，并返回其起始地址。当我们使用完这块内存时，需要使用 free() 函数将这块内存释放掉，以便我们后面再度使用这块内存。