数据结构--线性表

发表于 更新于 分类于 阅读次数： 本文字数： 2.2k 阅读时长 ≈ 2 分钟

本文写于 2020 年 3 月 19 日，2022 年 3 月 5 日重新整理

定义

线性表是由同类型的数据元素构成的有序序列数据结构，表中的元素个数称为线性表的长度，无元素的线性表称为空表，表起始位置称为表头，结束位置称位表尾。

线性表的ADT描述如下：

  • 类型名: 线性表
  • 数据对象集: 由 $n(n >= 0)$ 个元素构成的有序序列 $(a_1, a_2, …, a_n)$
  • 操作集: 
    1
    2
    3
    4
    5
    6
    List makeEmptyList(); // 创建空表
    ElementType findKth(const int K,List list); // 找到第K个元素
    int find(const ElementType ele,List list); // 找到元素ele第一次出现的位置
    void insert(ElementType ele,const int position,List list); // 把元素ele插入position位置的前面
    void delete(const int position,List list); // 删除位置position处的元素
    int length(); // 返回线性表的长度

实现

线性表内部可以使用顺序储存的数组实现，或者使用链表实现。

链表实现

原型

1
2
3
4
5
6
7
8
#define ElementType int

List *makeEmptyList(); // 创建空表
List *findKth(const int K, List *list); // 找到第K个元素
int find(const ElementType ele, List *list); // 找到元素ele第一次出现的位置
List *insert(ElementType ele, const int position, List *list); // 把元素ele插入position位置的前面
List *delete (const int position, List *list); // 删除位置position处的元素
int length(List *list);

创建空表

1
2
3
4
5
List *makeEmptyList()
{
    List *list = (List *)malloc(sizeof(List));
    return list;
}

查找第K个元素

1
2
3
4
5
6
7
8
9
10
11
List *findKth(const int K, List *list)
{
    List *listCopy = list; //make a copy
    int i = 0;
    while (listCopy && i < K)
    {
        i++;
        listCopy = listCopy->next;
    }
    return listCopy;
}

按值查找

1
2
3
4
5
6
7
8
9
int find(const ElementType ele, List *list)
{
    List *listCopy = list;
    while (listCopy && listCopy->data != ele)
    {
        listCopy = listCopy->next;
    }
    return listCopy;
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
List *insert(ElementType ele, const int position, List *list)
{
    if (position == 1)
    {
        List *n = makeEmptyList();
        n->data = ele;
        n->next = list;
        return n;
    }
    List *target = findKth(position - 1, list);
    if (target == NULL)
    {
        return NULL; //error
    }
    List *n = makeEmptyList();
    n->data = ele;
    n->next = target->next;
    target->next = n;
    return list;
}

删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
List *delete (const int position, List *list)
{
    if (position == 1)
    {
        if (list == NULL)
            return NULL;
        else
        {
            List *copy = list;
            list = list->next;
            free(copy);
            return list;
        }
    }
    List *target = findKth(position - 1, list);
    List *lastNode = target;
    if (target == NULL)
    {
        return;
    }
    else if (target->next == NULL)
    {
        return;
    }

    target = target->next;
    lastNode->next = target->next;
    free(target);
    return list;
}

获取长度

1
2
3
4
5
6
7
8
9
10
11
int length(List *list)
{
    int i = 0;
    List *listCopy = list;
    while (listCopy)
    {
        listCopy = listCopy->next;
        i++;
    }
    return i;
}