C语言顺序表基础操作注释详解

如题，本菜鸡也是初学数据结构，由于C语言基础不扎实，遇到了很多问题，网上的资料基本只有代码没有详细注释，自己学习的过程有些麻烦。为了方便后面的同学，同时为自己总结一下，便发出来。不过毕竟个人能力有限，如有注释错误曲解，望大神们与我进行讨论指教。

#include<stdio.h>
typedef int datatype;//数据类型声明，便于切换，注意要加分号！！！
//此替换只在是类型符时候才替换，即会进行区分，是类型符再进行替换
#define maxsize 10//宏定义顺序表最大长度，暴力无脑替换，不用加分号
#define ok 1//便于使用
#define error 0
#define increment 10//扩容长度
/*顺序表其实就是将数组作为了结点成员的线性表，其基本内核就是数组的连续物理内存*/

typedef struct//顺序表三要素：元素基址、元素个数、表长
{
    datatype *data;//首地址(顺序表的首地址里有存数据)
    //此处采用了取内容符号*，即data本身是一个地址

    /*关于数组首地址，例如数组int a[10]；&a和a都是一个地址，且数值是相同的，
    但在计算机对其进行处理时，计算机对他们的定义是不一样的，
    a只是数组首元素这个元素的地址，即a就是&a[0]，
    而&a则是对于整个数组a[10]作为一个整体来说的地址，
    因此可以用&a对整个数组进行处理，结合本程序的datapype *data；
    &*data也就是首结点的tou->data，因此可以用指针tou->data对顺序表进行整体处理*/

    int length;//当前元素个数，此处将个数、表长等信息直接拿出，便于对相关信息的调用处理
    int size;//表长，length、size只由首结点调用
}shun;//typedef类型声明要加分号
//结构体和结构体指针，shunxubiao是这个结构体的变量名，而shun是这个结构体的指针
//C语言stuct是用来定义结构体的，而经typedef则将以具体定义的结构体类型取了个别名
//即给struct取名为shunxubiao，再给struct*取名为shun!!!

int chushihua(shun *tou)//初始化函数
{
    tou->data = (datatype*)malloc(maxsize*sizeof(datatype));
    //申请一个全表数据内存经强制转换为对应存储格式的指针类型放进首地址的对应成员变量

    //提问：为什么要强制类型转换？指针不都是4个字节吗？
    //回答：1.malloc函数的返回值是void类型，
    //      其他类型可直接赋给void，但void不能直接赋给其它类型
    //      2.指针还真不都是4个字节，因为成员函数指针不是指针，
    //      指向成员函数的指针通常实现为包含此信息的小结构，而非单纯的指针
    //      具体可阅览《C++必知必会》中文译本第16章的内容，在此知道这个概念即可，不作赘述

    if (!tou->data)//若所申请的首地址为空，即没有顺序表头，则失败结束进程
        return error;
    tou->length = 0;//首地址不为空，就将当前初始元素个数设置为0
    tou->size = maxsize;//设置表长大小
    return ok;
}

int xiaohui(shun *tou)//销毁顺序表，将地址释放、数据清除，但指针变量仍在，
//对此，插入函数中会有更为详细的介绍
{
    if (tou->data)//若顺序表的地址存在则可以释放
    {
        free(tou->data);//释放数组整体地址
        tou->length = 0;//让当前元素个数归零，
        tou = NULL;//清理头结点
        return ok;
    }
    return error;
}

int get(shun *tou, int weizhi, int *e)//取得表中指定位置的数据
//提问：为什么不将所得元素直接作为返回值传递？
//回答：因为除了正确执行函数后返回OK，也可能执行失败返回error(也就是0)，
//      这样的话还需要设置判断一下，这样将地址作为参数放进去便于调用
{
    if (weizhi<1 || weizhi>tou->length)//若所找位置没有元素则函数运行失败
        //由于此处数组操作是tou->data[weizhi-1],因此weizhi与1作比较
        return error;
    *e = tou->data[weizhi - 1];//提取数据
    return ok;
}

int cunzai(shun *tou, int yuansu)//检测数据是否存在
{
    int i = 0;
    if (!tou->data)//判断首地址是否为空
        return error;
    while (i<tou->length)
        //数组内核因此i的初值为0，length是当前数据个数，
        //第n位元素下标为n-1，下面是用当前元素判等，因此用小于号<
    {
        if (tou->data[i] == yuansu)
            return ok;
        i++;
    }
    return error;
}

int kong(shun *tou)//判空函数
{
    return tou->length == 0 ? 1 : 0;//空表则1，否则0
}

int charu(shun *tou, int weizhi, int yuansu)//插入函数
{
    int* newbase;
    int i = 0;
    if (weizhi<1 || weizhi>tou->length + 1)//顺序表必须连续，末尾后一位也可插，因此length+1
    {
        printf("这里不能插了呐\n");
        return error;
    }
    if (tou->length == tou->size)//若元素个数已满，则需要扩容
    {
        newbase = (int*)realloc(tou->data, (tou->size + increment)*sizeof(int));
        /*注意：此处申请地址使用的是realloc而非malloc，realloc用于扩容使用，
        1.如果当前内存段后面有足够满足需要的内存空间，则直接扩展这段内存空间，
        realloc将返回原地址，即tou->data;
        2.如果当前内存段后面没有足够的内存空间，则找到一个能满足需要的内存块，
        将目前的数据复制到这个新的位置，并将原来的数据块释放掉，
        realloc将返回这个新地址
        3.如果申请失败，则返回NULL，此时原指针仍然有效*/
        tou->data = newbase;//将新的内存地址赋给指针变量
        /*注意：由于不知道relloc的具体执行结果，即不知道当前的内存地址是否改变
        因此必须将新地址赋给原指针变量。释放内存空间时，只是把地址中的数据清除
        但该地址的指针变量仍可使用，不过地址释放后有可能被正在运行的其他进程占用
        因此如果不对指针变量赋新地址而直接使用原地址，则可能出问题*/
        tou->size += increment;//顺序表容量增大扩容
    }
    for (i = tou->length - 1; i >= weizhi - 1; i--)
        //从最后一个元素向前遍历至i为待插位置的前一个结点，循环体操作是到待插位置
        //因为是用数组所以减一
        tou->data[i + 1] = tou->data[i];
    //遍历的同时将数组后移，最后一次后移是将插入位置后移一位
    tou->data[weizhi - 1] = yuansu;//将插入元素放在待插位置
    tou->length++;//顺序表当前元素个数加一
    return ok;
}

int shanchu(shun *tou, int weizhi, int *e)//删除函数
{
    int i;
    if (weizhi<1 || weizhi>tou->length)//位置不对则出错
        return error;
    *e = tou->data[weizhi - 1];//将待删位置的数据备份暂存
    for (i = weizhi - 1; i<tou->length; i++)//从待删位置起，将后面元素一次前移，起始i就是待删位置
        tou->data[i] = tou->data[i + 1];
    tou->length--;//当前元素个数减一
    return ok;
}

void display(shun *tou)//输出顺序表函数
{
    int i = 0;
    printf("\n顺序表表长=%d，元素个数=%d，元素分别为：", tou->size, tou->length);
    while (i<tou->length)
    {
        printf("%d\t", tou->data[i]);
        i++;
    }
    printf("\n");
}

int main()
{
    shun tou;//首先按照结构体类型定义一个结构体指针变量
    int e;
    int* ep;
    ep = &e;
    chushihua(&tou);//以前面的结构体变量进行初始化
    printf("初始化：size=%d，length=%d\n", tou.size, tou.length);
    display(&tou);//输出顺序表
    printf("\n是否为空表？%d", kong(&tou));//进行判空，确定一下顺序表是否正确
    int i = 0;
    while (i<20)
    {
        charu(&tou, i + 1, i);//在i+1的位置插入i
        i++;
    }
    display(&tou);
    get(&tou, 6, &e);//提取第6个元素
    printf("\n第六个元素是：%d\n", e);
    printf("\n6是否在表中？  %d\n", cunzai(&tou, 6));//判定数据6是否在顺序表中
    shanchu(&tou, 11, &e);//删除第11位置的元素
    printf("\n被删除的元素是：%d\n", e);
    printf("删除后的序列为：");
    display(&tou);
    xiaohui(&tou);//操作结束，执行销毁
    getchar();
    return 0;
}