线性表

发表于 分类于
第一个简单的线性结构

前言

这一节开始学习线性结构的知识，线性结构是指数据元素之间存在一对一的线性关系。

线性表是一个简单的线性结构，可以通过这一个数据结构了解更多的数据结构是实现。

一、逻辑结构

线性表是一个若干个数据元素的一个线性序列，它是一个有限序列，其中每个元素都是一个数据元素，每个元素都有一个前驱和一个后继，除了第一个元素没有前驱，最后一个元素没有后继。

可以了解线性表在存储结构中可以使用数组或者列表来进行存放，因为这个线性表是一个连续的序列。

二、存储结构

从逻辑结构那分析出来知道这个线性表可以用顺序存储，也可以用非顺序结构，这里两个存储方式都不会分别实现。

1.数据类型

在开始存储前先介绍一下存储的结构，这里的结构如下：

1
2
3
4
5
typedef struct
{
    data_t data[MaxSize];
    int length;
} SqList, *SqListPtr;

data是存放数据的数组，length是存放数据的长度。

data_t是一个数据类型，这里可以使用int类型来进行存放。

MaxSize是数组的大小，这里可以使用宏定义来进行定义。

2.顺序存储

前面说过顺序存储是存放在一块地址连续的空间，我们可以用数组来进行存放，但是直接使用数组来进行存放就会有一个问题，直接使用数组那它开辟的空间是在栈上的，栈在程序结束时就会被释放，所以我们需要使用动态内存分配来进行存放，这样就会开辟到堆区上。

在堆区上会一直存放的，直到调用free函数来释放内存。

然后了解了使用过程后，我们可以开始实现顺序存储了。

在实现的时候先了解一下我们需要实现的功能，这里列出一些操作类型，等后面会一一实现：

1
2
3
4
5
6
7
8
9
SqListPtr InitList();   // 初始化线性表
Status DestroyList(SqListPtr* list);      // 销毁线性表
Status ClearList(SqListPtr list);         // 清空线性表
Status ListEmpty(SqListPtr list);         // 判断线性表是否为空
int ListLength(SqListPtr list);           // 获取线性表的长度
Status GetElem(SqListPtr list, int pos, data_t *elem);   // 获取线性表中指定位置的元素
int LocateElem(SqListPtr list, data_t elem);   // 获取线性表中指定元素的位置
Status ListInsert(SqListPtr list, int pos, data_t elem);   // 在线性表中指定位置插入元素
Status ListDelete(SqListPtr list, int pos, data_t *elem);   // 在线性表中指定位置删除元素

然后还有一些宏定义和类型的重命名：

1
2
3
4
5
6
7
#define MaxSize 100
#define OK 1
#define ERROR -1
#define IS_NULL 0
#define IS_NOT_NULL 1
typedef int data_t;
typedef int Status;

然后就可以开始写代码了。

2.1 初始化线性表

实现需要初始化一下线性表，前面说过，需要使用动态内存分配来进行存放，所以需要使用malloc函数来进行分配内存，然后直接创建结构体即可。

然后给结构体中的length赋值为0即可，这个length是用来记录线性表中元素的个数的，有些喜欢从-1，然后这个代表最后一个元素的下标。而我们这记录的是元素个数，所以从0开始。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
SqListPtr InitList()
{
    SqListPtr list = NULL;
    list = (SqListPtr)malloc(sizeof(SqList));
    if (list == NULL)
    {
        return NULL;
    }
    list->length = 0;
    return list;
}

2.2 销毁线性表

对于顺序结构来说，销毁直接就释放那个结构体就可以了，因为是连续的空间，不需要释放每个元素。

代码如下：

1
2
3
4
5
6
7
8
9
10
Status DestroyList(SqListPtr* list)
{
    if (*list == NULL)
    {
        return ERROR;
    }
    free(*list);
    *list = NULL;
    return OK； 
}

这里的参数指针不解释，其实就是二级指针的问题，大家有兴趣可以看我前面介绍的二级指针的内容。

2.3 清空线性表

清空其实就是将里面的元素全部清除，但是这里不需要这么麻烦，我们在使用这个线性表的时候是通过length的记录来记录线性表中的个数，当这个length为0的时候，就代表这个线性表中没有元素了，所以我们只需要将length赋值为0即可。

代码如下：

1
2
3
4
5
6
7
8
9
Status ClearList(SqListPtr list)
{
    if (list == NULL)
    {
        return ERROR;
    }
    list->length = 0;
    return OK; 
}

2.4 判断线性表是否为空

判断线性表是否为空，只需要判断length是否为0即可，为0就代表这个线性表中没有元素，不为0就代表这个线性表中有元素。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
Status ListEmpty(SqListPtr list)
{
    if (list == NULL)
    {
        return ERROR;
    }
    if (list->length == 0)
    {
        return IS_NULL;
    }
    
    return IS_NOT_NULL; 
}

2.5 获取线性表的长度

获取线性表的长度，只需要返回length的值即可。

代码如下：

1
2
3
4
5
6
7
8
int ListLength(SqListPtr list)
{
    if (list == NULL)
    {
        return ERROR;
    }
    return list->length;
}

2.6 获取线性表中指定位置的元素

获取线性表中指定位置的元素，只需要判断位置是否合法，然后返回指定位置的元素即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
Status GetElem(SqListPtr list, int pos, data_t *elem)
{
    if (list == NULL || elem == NULL)
    {
        return ERROR;
    }
    if (pos < 0 || pos >= list->length)
    {
        return ERROR;
    }
    *elem = list->data[pos];
    return OK; 
}

2.7 获取线性表中指定元素的位置

获取线性表中指定元素的位置，只需要遍历线性表，然后判断元素是否相等，相等就返回位置，不相等就返回-1。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int LocateElem(SqListPtr list, data_t elem)
{
    if (list == NULL)
    {
        return ERROR; 
    } 
    int i = 0;
    for (i = 0; i < list->length; i++)
    {
        if (list->data[i] == elem)
        {
            return i;
        }
    }
    return ERROR;
}

2.8 在线性表中指定位置插入元素

在线性表中指定位置插入元素，只需要判断位置是否合法，然后将指定位置后面的元素都向后移动一位，然后将元素插入到指定位置即可。

这里用一个图来演示这个过程：

这里分为两个情况，一个是在最后插入数据，这种情况不需要移动，另一种是在中间插入数据，这种情况需要移动：

首先有一个线性表，这里需要在位置2插入一个元素value，然后需要先找到一下这个线性表中的最后一个元素的下标，用一个指针进行存放，存放后比较一下这个指针存放的下标是否是需要插入的位置，如果是直接插入，如果不是需要让这个指针指向的内容向后移动：

然后指针又往前移动，再次比较是不是插入的位置，如果不是将这个指针存放的下标的内容向后移动：

如果这个指针指向的下标就是需要插入的位置，那先移动元素，移动完成后将指插入即可：

知道这个过程后我们就可以写一下代码了

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Status ListInsert(SqListPtr list, int pos, data_t elem)
{
    int i = list->length - 1;   // 因为存放的是元素个数，所以需要减1
    if (list == NULL)
    {
        return ERROR;
    }
    if (pos < 0 || pos > list->length)
    {
        return ERROR;
    }
    for (i = list->length - 1; i >= pos; i--)
    {
        list->data[i + 1] = list->data[i];
    } 
    list->data[pos] = elem;
    list->length++;         // 里面的元素增加
    return OK;
}

2.9 在线性表中指定位置删除元素

删除和插入一样，也是需要移动元素进行删除，前面插入是往后移动元素，而删除是往前移动，直接覆盖住需要删除的元素，然后让length减1即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Status ListDelete(SqListPtr list, int pos, data_t *elem)
{
    int i = 0;
    if (list == NULL)
    {
        return ERROR;
    } 
    if (pos < 0 || pos > list->length)
    {
        return ERROR;
    }
    *elem = list->data[pos];
    for (i = pos; i < list->length; i++)
    {
        list->data[i] = list->data[i + 1];
    }
    list->length--;
    return OK;
}

2.10 打印线性表

打印线性表，只需要遍历线性表，然后打印每个元素即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
void PrintList(SqListPtr list)
{
    if (list == NULL)
    {
        return;
    }
    int i = 0;
    for (i = 0; i < list->length; i++)
    {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

这样线性表的基本操作都做完了，下面来介绍一下链式存储，也就是非顺序存储。

3.链式存储

链式存储是指用一组任意的存储单元存储线性表中的数据元素，这组存储单元可以是连续的，也可以是不连续的。

链式存储是通过指针来进行连接的，每个元素都有一个指针，指向下一个元素，这样就可以通过指针来进行连接，这样就可以实现链式存储，链式存储的长度其实是根据堆区的大小来的，如果堆区空间还有内存，则可以创建结点。

所以在这里的链式存储结构就没有长度这个属性了，如果要判断这个线性表的长度，可以通过遍历链表来获取长度。

链式存储的结构如下：

1
2
3
4
typedef struct Node{
    data_t data;
    struct Node *next;      // 下一个结点的地址
}ListNode, *ListPtr;

data是存放数据的，next是指向下一个结点的地址。

下面是链式存储的有些函数：

1
2
3
4
5
6
7
8
9
ListPtr InitList();   // 初始化线性表
Status DestroyList(ListPtr* list);      // 销毁线性表
Status ClearList(ListPtr list);         // 清空线性表
Status ListEmpty(ListPtr list);         // 判断线性表是否为空
int ListLength(ListPtr list);           // 获取线性表的长度
Status GetElem(ListPtr list, int pos, data_t *elem);   // 获取线性表中指定位置的元素
int LocateElem(ListPtr list, data_t elem);   // 获取线性表中指定元素的位置
Status ListInsert(ListPtr list, int pos, data_t elem);   // 在线性表中指定位置插入元素
Status ListDelete(ListPtr list, int pos, data_t *elem);   // 在线性表中指定位置删除元素

3.1 初始化线性表

初始化线性表，只需要创建一个头结点，然后将头结点的指针指向NULL即可，这个头节点不需要任何的数据，相当于是一个指示的结点。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
ListPtr InitList()
{
    ListPtr list = NULL;
    list = (ListPtr)malloc(sizeof(ListNode));
    if (list == NULL)
    {
        return NULL;
    }
    list->data = -1;
    list->next = NULL;
    return list;
}

3.2 销毁线性表

销毁线性表，只需要遍历链表，然后释放每个结点即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Status DestroyList(ListPtr* list)
{
    ListPtr p = *list;
    ListPtr q = (*list)->next;
    if (*list == NULL)
    {
        return ERROR;
    }
    while(p)
    {
       free(p); 
       p = q;
       q = q->next;
    }
    *list = NULL;
    return OK;
}

3.3 清空线性表

这里可以直接让头节点的next指向NULL即可，但是后面的结点还是在的，如果不进行释放，那可能会导致内存溢出，所以这里需要先将后面的结点释放掉，然后再将头节点的next指向NULL即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Status ClearList(ListPtr list)
{
    // 这里让p指针领先q指针一个结点
    ListPtr p = list->next;
    ListPtr q = list->next;
    if (list == NULL)
    {
        return ERROR;
    }
    while(q)
    {
        p = p->next;
        free(q);
        q = p;
    }
    list->next = NULL;
    return OK;
}

3.4 判断线性表是否为空

判断线性表是否为空，只需要判断头节点的next是否为NULL即可，为NULL就代表这个线性表中没有元素，不为NULL就代表这个线性表中有元素。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
Status ListEmpty(ListPtr list)
{
    if (list == NULL)
    {
        return ERROR;
    }
    if (list->next == NULL)
    {
        return IS_NULL;
    }
    return IS_NOT_NULL;
}

3.5 获取线性表的长度

获取线性表的长度，只需要遍历链表，然后记录链表的长度即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int ListLength(ListPtr list)
{
    if (list == NULL)
    {
        return ERROR;
    }
    int length = 0;
    ListPtr p = list->next;
    while(p)
    {
        length++;
        p = p->next;
    } 
}

3.6 获取线性表中指定位置的元素

获取线性表中指定位置的元素，只需要遍历链表，然后找到指定位置的元素即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Status GetElem(ListPtr list, int pos, data_t *elem)
{
    if (list == NULL)
    {
        return ERROR;
    }
    if (pos < 0 || pos > ListLength(list))
    {
        return ERROR;
    }
    ListPtr p = list->next;
    int i = 0;
    for (i = 0; i < pos; i++)
    {
        p = p->next;
    }
    *elem = p->data;
    return OK; 
}

3.7 获取线性表中指定元素的位置

获取线性表中指定元素的位置，只需要遍历链表，然后找到指定元素的位置即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int LocateElem(ListPtr list, data_t elem)
{
    if (list == NULL) 
    {
        return ERROR; 
    }
    ListPtr p = list->next;
    int i = 0;
    while(p)
    {
        if (p->data == elem)
        {
            return i;
        }
        i++;
        p = p->next;
    }  
    return ERROR;
}

3.8 在线性表中指定位置插入元素

对于链表中，插入元素其实很简单，它不需要移动全部元素，只需要在对应的位置移动指针即可，让插入的结点的next获得前面的那个结点的next，然后让前面的那个结点的next指向这个新插入的结点。

图示如下：

有一个链表，第一个是头结点，头节点不算在内，现在需要插入到第1的位置

先找到要插入位置的结点的前面，相当于是0这个位置，然后让新插入的结点的next指向前面那个结点的next

然后让前面那个结点的next指向插入的这个结点

代码如下：

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
31
32
Status ListInsert(ListPtr list, int pos, data_t elem)
{
    linkList pNext = NULL;
    linkList pHead = list;
    int j = 0;
    if (pos < 1)
    {
        return ERROR;
    }
    if (value == -1)
    {
        return OK;
    }
    while (pHead && pos - 1 > j)
    {
        pHead = pHead->pNext;
        j++;
    }
    if (j > pos - 1) {
        // 如果找不到那个位置的内容
        return ERROR;
    }
    pNext = (linkList)malloc(sizeof(linkNode));
    if (pNext == NULL)
    {
        return ERROR;
    }
    pNext->pNext = pHead->pNext;
    pNext->data = elem;
    pHead->pNext = pNext;
    return OK;
}

3.9 删除元素

删除是比较简单的，其实就是找到想要删除的元素的前一个元素，然后让这个结点的next指向想要删除的结点的next，然后释放需要删除的结点就可以删除成功了。

代码如下：

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
31
Status ListDelete(ListPtr list, int pos, data_t *elem)
{
    int j = 1;
    data_t value = ERROR;
    linklist pNext, pEnd;
    pNext = link->pNext;
    pEnd = link;
    if (pos < 1)
    {
        return ERROR;
    }
    if (LinkList_ListEmpty(*link) == IS_NULL)
    {
        return ERROR;
    }
    while(pNext)
    {
        if (j == pos)
        {
            // 删除内容
            pEnd->pNext = pNext->pNext;
            value = pNext->data;
            free(pNext);
            break;
        }
        j++;
        pEnd = pNext;
        pNext = pNext->pNext;
    }
    return value;
}

总结

线性表还是比较简单的一个数据结构，后面还会介绍栈、队列和树这些数据结构。