数据结构（二）线性表 の 顺序表

认识线性表

定义

零个或多个数据元素的有限序列

特点

• 它是一个序列，数据之间是有序的，数据元素是一对一的关系。
• 线性表的数据元素个数是有限的。

常见操作

• 创建和初始化队列
• 查找
• 插入
• 删除
• 清空

线性表的抽象数据类型

线性表的顺序存储结构

定义

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

优点

• 无须为表示表中元素之间的逻辑而增加额外的存储空间。
• 可以快速地存取任意位置的元素

缺点

• 插入删除操作需要移动大量的元素
• 当线性表长度变化较大时，难以确定元素存储空间的内容
• 造成空间的“碎片”

代码实现

// DataElement.h
#ifndef INC_01_DATAELEMENT_H
#define INC_01_DATAELEMENT_H
#define MAX_SIZE 255
// 定义数据元素
typedef struct {
    int id;
    char * name;
} ElementType;
// 定义顺序表结构
typedef struct {
    ElementType datas[MAX_SIZE];  // 顺序表中的数据集合
    int length;  // 当前顺序表中的元素个数
} SeqList;
#endif

// SequenceList.h
#ifndef INC_01_SEQUENCELIST_H
#define INC_01_SEQUENCELIST_H
#include <stdio.h>
#include <stdlib.h>
#include "DataElement.h"
/**
 * 初始化顺序表
 * @param seqList  需要初始化的顺序表指针
 * @param elemArray  初始化时要添加的元素内容
 * @param length  初始化时添加的元素个数
 */
void InitList(SeqList * seqList, ElementType * elemArray, int length);
/**
 * 向顺序表中插入某个元素
 * @param seqList  需要插入元素的顺序表指针
 * @param index  插入的位置
 * @param element 插入的元素
 */
void InsertElement(SeqList * seqList, int index, ElementType element);
/**
 * 打印顺序表
 * @param seqList
 */
void PrintList(SeqList * seqList);
/**
 * 在顺序表中删除某个元素
 * @param seqList  删除元素所在的顺序表指针
 * @param index  删除元素的下标
 * @return  返回删除的元素，如果删除失败返回 NULL
 */
ElementType * DeleteElement(SeqList * seqList, int index);
/**
 * 在顺序表中查找某个元素
 * @param seqList  查找元素所在的顺序表指针
 * @param index  查找元素的下标
 * @return  返回查找元素的下标，如果查找失败返回 NULL
 */
ElementType * GetElement(SeqList * seqList, int index);
/**
 * 返回顺序表的长度
 * @param seqList  返回总长度的顺序表指针
 * @return  返回顺序表长度
 */
int GetLength(SeqList * seqList);
/**
 * 判断顺序表是否为空
 * @param seqList  判断是否为空的顺序表指针
 * @return  顺序表为空返回 1，否则返回 0
 */
int IsEmpty(SeqList * seqList);
/**
 * 清空顺序表
 * @param seqList  要清空的顺序表指针
 */
void ClearList(SeqList * seqList);
#endif

// SequenceList.c
#include "SequenceList.h"
/**
 * 初始化顺序表
 * @param seqList  需要初始化的顺序表
 * @param elemArray  初始化时要添加的元素内容
 * @param length  初始化时添加的元素个数
 */
void InitList(SeqList * seqList, ElementType * elemArray, int length) {
    if (length > MAX_SIZE) {
        printf("超出了数组的最大容量，初始化失败！\n");
        return;
    }
    seqList -> length = 0;
    for (int i = 0; i < length; i++) {
        InsertElement(seqList, i, elemArray[i]);
    }
};
/**
 * 向顺序表中插入某个元素
 * @param seqList  需要插入元素的顺序表
 * @param index  插入的位置
 * @param element 插入的元素
 */
void InsertElement(SeqList * seqList, int index, ElementType element) {
    if (seqList->length + 1 >= MAX_SIZE) {
        printf("数组已满, 插入元素失败！\n");
        return;
    }
    if (index < 0 || index > MAX_SIZE -1) {
        printf("只能在允许的下标范围内插入元素[0, %d]！\n", MAX_SIZE - 1);
        return;
    }
    if (index > seqList -> length) {
        printf("插入的下标超过了数组的最大长度-1，插入失败！\n");
        return;
    }
    for (int i = seqList -> length - 1; i >= index; i--) {
        seqList -> datas[i + 1] = seqList -> datas[i];
    }
    // 插入元素
    seqList -> datas[index] = element;
    // 顺序表的总长度 +1
    seqList -> length++;
};
/**
 * 打印顺序表
 * @param seqList
 */
void PrintList(SeqList * seqList) {
    for (int i = 0; i < seqList -> length; i++) {
        printf("%d\t%s\n", seqList -> datas[i].id, seqList -> datas[i].name);
    }
};
void PrintList(SeqList * seqList);
/**
 * 在顺序表中删除某个元素 (使用完毕后必须 free！！！)
 * @param seqList  删除元素所在的顺序表
 * @param index  删除元素的下标
 * @return  返回删除的元素，如果删除失败返回 NULL
 */
ElementType * DeleteElement(SeqList * seqList, int index) {
    if (index < 0 || index > MAX_SIZE - 1) {
        printf("下标越界，无法删除！");
        return NULL;
    }
    // 保存已删除元素的副本
    ElementType * delElement = (ElementType*)malloc(sizeof(ElementType));
    *delElement = *GetElement(seqList, index);
    for (int i = index; i < seqList ->length - 1 ; ++i) {
        seqList -> datas[i] = seqList -> datas[i+1];
    }
    seqList -> length--;
    return delElement;
};
/**
 * 在顺序表中查找某个元素
 * @param seqList  查找元素所在的顺序表
 * @param index  查找元素的下标
 * @return  返回查找元素的下标，如果查找失败返回 NULL
 */
ElementType * GetElement(SeqList * seqList, int index) {
    if (index < 0 || index > MAX_SIZE) {
        printf("下标越界，无法找到指定元素！");
        return NULL;
    }
    ElementType * element;  // 要查找的元素
    element = &seqList -> datas[index];
    return  element;
};
/**
 * 返回顺序表的长度
 * @param seqList  返回总长度的顺序表指针
 * @return  返回顺序表长度
 */
int GetLength(SeqList * seqList) {
    if (seqList == NULL) {
        return 0;
    }
    return seqList ->length;
};
/**
 * 判断顺序表是否为空
 * @param seqList  判断是否为空的顺序表指针
 * @return  顺序表为空返回 1，否则返回 0
 */
int IsEmpty(SeqList * seqList) {
    return GetLength(seqList) == 0 ? 0 : 1;
};
/**
 * 清空顺序表
 * @param seqList  要清空的顺序表指针
 */
void ClearList(SeqList * seqList) {
    if (seqList == NULL) {
        return;
    }
    seqList->length = 0;
};

// main.c
#include <stdio.h>
#include <stdlib.h>
#include "SequenceList.h"

ElementType dataArray[] = {
        {1, "奇异博士"},
        {2, "美国队长"},
        {3, "太上老君"},
        {4, "齐天大圣"},
};

void TestSequenceList();

int main() {
    TestSequenceList();
    return 0;
}


void TestSequenceList() {
    SeqList seqList;  // 要操作的顺序表
    InitList(&seqList, dataArray, sizeof(dataArray) / sizeof(dataArray[0]));
    PrintList(&seqList);
};