顺序存储之顺序表

顺序表的创建与操作(顺序存储)

1.首先我们需要定义数据类型

//定义数据类型  这儿我们使用int
typedef int DATA;   //给int取别名为DATA

2.构建顺序表的排序准则

//定义顺序表以index为顺序升序或降序排序
struct Node
{
    int index;
    DATA data;
};

3.定义顺序表结构

typedef struct seqList
{
    int size;     //当前顺序表长度
    struct Node* memory;   //存储顺序表数据的内存
}SQL,*LPSQL;
//SQL为该结构体类型的别名
//LPSQL为该结构体指针类型的别名

4.顺序表的创建

LPSQL createSeqList()
{
    LPSQL sqlist = (LPSQL)malloc(sizeof(SQL));
    if (NULL == sqlist)
    {
        printf("顺序表创建失败!");
        return NULL;
    }
    sqlist->size = 0;
    sqlist->memory = (struct Node*)malloc(sizeof(struct Node) * MAX);
    return sqlist;
}

5.顺序表的扩容

//这里直接采用扩大两倍内存的方式
void reallocMemeory(LPSQL sqlist, int curSize, int newSize)
{
    int max = curSize > newSize ? curSize : newSize;
    (struct Data*)realloc(sqlist->memory, sizeof(struct Node) * max);
}

6.顺序表的数据插入

//插入,我们采用直接插入到表尾,然后(根据准则)移动元素
//采用准则升序排序
void insertData(LPSQL sqlist, struct Node data)
{
    if (sqlist->size == MAX)
    {
        reallocMemeory(sqlist, MAX, MAX * 2);
        printf("顺序表已扩容\n");
    }
    //直接插在表尾
    sqlist->memory[sqlist->size] = data;
    //调整位置
    for (int i = sqlist->size; i > 0; i--)   //注意此处下标越界问题
    {
        if (sqlist->memory[i - 1].index > sqlist->memory[i].index)
        {
            struct Node temp = sqlist->memory[i - 1];
            sqlist->memory[i - 1] = sqlist->memory[i];
            sqlist->memory[i] = temp;
        }
        else
        {
            break;
        }
    }
    sqlist->size++;
}

7.顺序表的数据删除

void deleteListData(LPSQL sqlist, int index)
{
    //找到位置  删除  移动后面的元素
    int pos = -1;
    for (int i = 0; i < sqlist->size; i++)
    {
        if (sqlist->memory[i].index == index)
        {
            pos = i;
            break;
        }
    }if (pos == -1)
    {
        printf("顺序表之中没有该元素!");
        return;
    }
    else  //移动元素
    {
        for (int i = pos; i < sqlist->size; i++)
        {
            sqlist->memory[i] = sqlist->memory[i + 1];
        }
    }
    sqlist->size--;
}

8.顺序表的遍历

void traverseList(LPSQL sqlist)
{
    for (int i = 0; i < sqlist->size; i++)
    {
        printf("index: %d\tDATA:%d\n", (sqlist->memory[i]).index,
            (sqlist->memory + i)->data);
    }
    printf("\n");
}

9.顺序表的销毁

//这里因为需要改变指针的指向,因此需要传入二级指针
void deleteList(LPSQL* psqlist)
{
    free(*psqlist);
    printf("销毁成功\n");
}

总体代码

#include<stdio.h>
#include<stdlib.h>   //system()函数头文件
#define MAX 2       //定义一个初始长度

//定义数据类型  这儿我们使用int
typedef int DATA;   
//构建准则 (构建顺序表以何种顺序排列)
struct Node
{
    int index;
    DATA data;
};
//定义顺序表结构
typedef struct seqList
{
    int size;     //当前顺序表长度
    struct Node* memory;   //存储顺序表数据的内存
}SQL,*LPSQL;
//创建顺序表
LPSQL createSeqList()
{
    LPSQL sqlist = (LPSQL)malloc(sizeof(SQL));
    if (NULL == sqlist)
    {
        printf("顺序表创建失败!");
        return NULL;
    }
    sqlist->size = 0;
    sqlist->memory = (struct Node*)malloc(sizeof(struct Node) * MAX);
    return sqlist;
}
//顺序表扩容
void reallocMemeory(LPSQL sqlist, int curSize, int newSize)
{
    int max = curSize > newSize ? curSize : newSize;
    (struct Data*)realloc(sqlist->memory, sizeof(struct Node) * max);
}
//数据插入
void insertData(LPSQL sqlist, struct Node data)
{
    if (sqlist->size == MAX)
    {
        reallocMemeory(sqlist, MAX, MAX * 2);
        printf("顺序表已扩容\n");
    }
    //直接插在表尾
    sqlist->memory[sqlist->size] = data;
    //调整位置
    for (int i = sqlist->size; i > 0; i--)   //注意此处下标越界问题
    {
        if (sqlist->memory[i - 1].index > sqlist->memory[i].index)
        {
            struct Node temp = sqlist->memory[i - 1];
            sqlist->memory[i - 1] = sqlist->memory[i];
            sqlist->memory[i] = temp;
        }
        else
        {
            break;
        }
    }
    sqlist->size++;
}
//数据删除
void deleteListData(LPSQL sqlist, int index)
{
    //找到位置  删除  移动后面的元素
    int pos = -1;
    for (int i = 0; i < sqlist->size; i++)
    {
        if (sqlist->memory[i].index == index)
        {
            pos = i;
            break;
        }
    }if (pos == -1)
    {
        printf("顺序表之中没有该元素!");
        return;
    }
    else  //移动元素
    {
        for (int i = pos; i < sqlist->size; i++)
        {
            sqlist->memory[i] = sqlist->memory[i + 1];
        }
    }
    sqlist->size--;
}
//顺序表遍历
void traverseList(LPSQL sqlist)
{
    for (int i = 0; i < sqlist->size; i++)
    {
        printf("index: %d\tDATA:%d\n", (sqlist->memory[i]).index,
            (sqlist->memory + i)->data);
    }
    printf("\n");
}
//销毁顺序表
void deleteList(LPSQL* psqlist)
{
    free(*psqlist);
    *psqlist = NULL;
    if (NULL == psqlist)
    printf("销毁成功\n");
}
int main()
{
    //创建顺序表
    LPSQL seqList = createSeqList();
    struct Node data[8] = { {2,522},{8,528},{1,521},{3,523},
                       {5,525},{7,527},{4,524},{6,526} };
    //数据插入
    for (int i = 0; i < 8; i++)
    {
        insertData(seqList,data[i]);
    }
    //打印数据
    traverseList(seqList);
    //数据删除
    deleteListData(seqList, 3);
    //打印数据
    traverseList(seqList);
    //销毁顺序表
    deleteList(&seqList);

    system("pause");
    return 0;
}

10.输出结果

到此就结束了-------------------------->