线性表


主要是数据结构中的线性表相关的知识与实际应用。

1. 定义与基本运算

1.1 定义

  • 线性表(Linear List)是最简单和常用的一种数据结构,它是由n个数据元素(结点)a1,a2,…,an组成的有限序列。
  • 数据元素的个数n为表的长度。
  • n为0时称为空表。

1.2 特征

  • 有且仅有一个称为开始元素的a1,它没有前趋,仅有一个直接后继a2
  • 有且仅有一个称为终端元素的an,它没有后继,仅有一个直接前趋。
  • 其余元素ai称为内部元素,他们都有且仅有一个直接前趋ai-1和一个直接后继ai+1
  • 线性表中元素之间的逻辑关系就是上述的相邻关系,又称为线性关系,可见线性表是一种典型的线性结构。

1.3 基本运算

  • 置空表InitList(L),构造一个空的线性表L。
  • 求表长ListLength(L),返回线性表L中元素个数,即表长。
  • 取表中第i个元素GetNode(L, i),若1<=i<=ListLength(L),则返回第i个元素ai
  • 按值查找LocateNode(L, x),在表L中查找第一个值为x的元素,并返回该元素在表L中的位置,若表中没有元素的值为x,则返回0值。
  • 插入InsertList(L, i, x), 在表L的第i个元素之前插入一个值为x的新元素,表L的长度加1。
  • 删除DeleteList(L, i),删除表L的第i个元素,表L的长度减1.
    上述仅是线性表的基本运算,不是全部运算。对于不同问题的线性表,所需要的运算可能不同。对于实际问题中涉及其他更为复杂的运算,可用基本运算的组合来实现。

2. 顺序存储的线性表和基本运算的实现

2.1 顺序存储

线性表的顺序存储指的是将线性表的数据元素按其逻辑次序依次存入一组地址连续的存储单元里,用这种方法存储的线性表称为顺序表

2.2 顺序存储的线性表基本运算C语言实现

#include <stdio.h>
#include <stdlib.h>

/**
 * 线性表长度和基本类型
 */
#define ListSize 5
typedef int DataType;

/**
 * 线性表结构
 */
typedef struct {
    DataType data[ListSize];
    int length;
} SeqList;

/**
 * 线性表插入操作
 * @param L 线性表指针
 * @param i 插入索引
 * @param x 插入项
 */
void InsertList(SeqList *L, int i, DataType x)
{
    if (i < 1 || i > L->length + 1) {
        printf("position error");
        return;
    }
    if (L->length >= ListSize) {
        printf("overflow");
        return;
    }
    int j;
    for (j = L->length - 1; j >= i - 1; j--) {
        L->data[j + 1] = L->data[j];
    }
    L->data[i - 1] = x;
    L->length++;
}

/**
 * 删除线性表的第i个元素
 * @param L
 * @param i
 */
DataType DeleteList(SeqList *L, int i)
{
    if (i < 1 || i > L->length) {
        printf("position error");
        exit(0);
    }

    DataType result = L->data[i - 1];

    for (; i <= L->length; i++) {
        L->data[i - 1] = L->data[i];
    }
    L->length--;

    return result;
}

/**
 * 打印线性表所有元素与长度,用于测试方法是否正确
 * @return
 */
int printLineTable(SeqList *L)
{
    // 打印线性表所有元素及长度,测试是否正确
    printf("The element of the Line Table:(");
    int i;
    for (i = 0; i < L->length; i++) {
        printf("%d%s", L->data[i], i == L->length - 1 ? "" : ",");
    }
    printf(")\r\n");
    printf("The length of Line Table: %d\r\n\r\n", L->length);
    return 0;
}

/**
 * 获取线性表长度
 * @param L
 * @return
 */
int ListLength(SeqList *L)
{
    return L->length;
}

/**
 * 获取线性表中第i个元素
 * @param L
 * @return
 */
DataType GetNode(SeqList *L, int i)
{
    if (i < 1 || i > L->length) {
        printf("position error");
        exit(0);
    }

    return L->data[i - 1];
}

/**
 * 定位给定的值在线性表中的位置,有就返回该值的位置,否则返回0
 * @param L
 * @param node
 * @return
 */
int LocateNode(SeqList *L, DataType node)
{
    int i = 0;
    for (; i < L->length; i++) {
        if (L->data[i] == node) {
            return i + 1;
        }
    }
}

/**
 * 主函数,运行相关函数测试
 * @return
 */
int main() {
    printf("The max length of Line Table: %d\r\n\r\n", ListSize);

    // 定义一个顺序存储结构线性表,并初始化
    SeqList lineTable = { {}, 0 };
    printLineTable(&lineTable);

    InsertList(&lineTable, 1, 3);
    printLineTable(&lineTable);

    InsertList(&lineTable, 1, 8);
    printLineTable(&lineTable);

    InsertList(&lineTable, 1, 5);
    printLineTable(&lineTable);

    InsertList(&lineTable, 1, 8);
    printLineTable(&lineTable);

    int location = LocateNode(&lineTable, 5);
    printf("The %dst node value is 5\r\n\r\n", location);

    DataType node = GetNode(&lineTable, 1);
    printf("The %dst node value is %d\r\n\r\n", 1, node);

    DataType deletedNode = DeleteList(&lineTable, 1);
    printf("The Deleted Node Value is %d\r\n", deletedNode);
    printLineTable(&lineTable);

    int length = ListLength(&lineTable);
    printf("The length of the Line Table is %d\r\n\r\n", length);

    return 0;
}
评论