顺序表与列表

顺序表

顺序表结构讲解

众所周知，数据结构=结构定义+结构操作，以下内容按这个思想去理解会更舒畅

顺序表可以类比成一个带有属性的数组(这里我不放图，可以自行去找图来理解)

顺序表结构定义三部分

1. 一段连续的存储区域，用于顺序表存储元素
2. 一个整形变量，用于标记顺序表的大小(size)
3. 一个整形变量，用于标记顺序表中到底储存了多少个元素(count)

顺序表插入操作
0 1 2 3 4 5 6
[1] [2] [3] [4] [5] [6] [ ]

现在要在2这个位置插入一个6，那么要进行的操作就是把位置2到5的3456全部平行向后移一格

0 1 2 3 4 5 6
[1] [2] [6] [3] [4] [5] [6]

然后size不变，因为原来是7个的数组，现在还是
count要+1，因为多了一个元素
顺序表删除操作
0 1 2 3 4 5 6
[1] [2] [3] [4] [5] [6] [ ]
现在要在2这个位置把元素3删了，后面向前移一格，size不变，count-1

顺序表代码演示

#include<stdio.h>
#include<stdlib.h>//引入标准库，提供动态内存分配（malloc、free）、进程控制（exit）等函数的声明。
#include<time.h>
//先写结构定义
typedef struct vector {
    int size,count;//按照前面说说的分别定义数据表的各个部分
    int *data; //用data这个指针指向整型存储区
} vector;

//初始化操作
vector *getNewVector(int n){
    vector *p=(vector *)malloc(sizeof(vector)); //分配内存空间,大小刚好能容纳一个 vector 结构体。
//malloc函数:在「堆（heap）」区动态分配一块指定字节数的连续内存空间，并返回这块空间的起始地址。
    p->size=n;
    p->count=0; //初始化计数器
    p->data=(int *)malloc(sizeof(int)*n); //分配数据存储区,在堆上再分配一块 n * sizeof(int) 字节的空间，用来存放实际的整数元素。
    return p; //返回指向新向量的指针
}

//插入操作
int insert(vector *v,int pos ,int val){
    if(pos<0 || pos>v->count){ //检查位置是否合法
        return 0; //位置不合法，返回0表示插入失败
    }
    if(v->size==v->count){
        return 0;
    }
    //这里用逆序遍历来进行位移操作
    for(int i=v->count-1;i>=pos;i--){
        v->data[i+1]=v->data[i]; //将元素向后移动一位
    }
    v->data[pos]=val; //在空出的位置插入新元素
    v->count++; //更新元素计数
    return 1;
}

//输出操作
void printVector(vector *v){
    int len=0;
    for(int i=0;i<v->size;i++){
        len+=printf("%3d",i);//计算第一行的输出的长度信息，方便第二行对齐
    }
    for(int i=0;i<len;i++){
        printf("-");
    }
    printf("\n");
    for(int i=0;i<v->count;i++){
        printf("%3d",v->data[i]); //输出每个元素
    }
    printf("\n");
    return ;
}
//删除操作
int erase(vector *v,int pos){
    if(pos<0||pos>=v->count){
        return 0;
    }
    //直接覆盖掉即可
    for(int i=pos+1;i<v->count;i++){
        v->data[i-1]=v->data[i]; //将后面的元素向前移动一位
    }
    v->count--; //更新元素计数
    return 1;
}


//销毁操作
void clear(vector *v){
    if(v==NULL){
        return ;
    }
    free(v->data);//free(v->data) 会将这块动态分配的内存还给系统，解除它的分配状态。
    free(v);//这一步将 vector 结构体对象本身的内存释放掉。通常在创建时，你会用 malloc(sizeof(vector)) 分配它，所以现在要成对地用 free 释放它
    return ;
}

int main(){
    srand(time(NULL)); //设置随机数种子
    #define N 10
    vector *v=getNewVector(N); //创建一个新顺序表
    for(int i=0;i<N;i++){
        int op=rand()%4,pos,val;
        switch (op)
        {
            case 0:
            case 1:
            case 2:
                pos=rand()%(v->count+1); //随机生成插入位置
                val=rand()%100;
                printf("insert %d  at %d to vector=%d\n", val, pos,insert(v, pos, val));
                break;
            case 3:
                pos=rand()%(v->count+1);
                printf("erase %d from vector=%d\n", pos, erase(v, pos));
                break;
        }
        printVector(v);
    }
    clear(v);
    return 0;
}