首页 数据结构与算法

线性表的类型定义

[TOC]

数据结构三要素—逻辑结构、数据的运算、存储结构(物理结构)【存储结构不同，运算的实现方式就不同】

定义

线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，其中n为表长，当n=0时线
性表是一个空表。若用命名线性表，则其一般表示为

L = ( a 1 , a 2 , … , a i … , a n L=(a_1,a_2,…,a_i…,a_nL=(a1,a2,…,ai…,an

  1. a i a_iai是线性表中的“第i个”元素线性表中的位序
  2. a 1 a_1a1是表头元素；a n a_nan是表尾元素
  3. 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且只有一个直接后继。

在这里插入图片描述

基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。

DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。

ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。

GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。

其他常用操作：

Length(L) 求表长。返回线性表L的长度，即L中数据元素的个数。

PrintList(L) 输出操作。按前后顺序输出线性表L的所有元素值。

Empty(L) 判空操作。若L为空表，则返回true，否则返回false。

值得注意的是：

  1. 抽象数据类型仅是一个模型的定义，并不涉及模型的具体实现，因此这里描述中所涉及的参数不必考虑具体数据类型。在实际应用中，数据元素可能有多种类型，我们要随机应变。
  2. 上述抽象数据类型中给出的操作只是基本操作，由这些基本操作可以构成其它较复杂的操作。
  3. 对于不同的应用，基本操作的接口可能不同。
  4. 由抽象数据类型定义的线性表，可以根据实际所采用的存储结构形式，进行具体的表示与实现。

在这里插入图片描述

代码实现

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<stdio.h>
#include<stdlib.h>
/**
 * @author five-five
 * @created 2022/5/2
 *
 */



#define INIT_SIZE 10 //初试长度
typedef struct {
    int length;//顺序表的长度
    int *data;//顺序表的内容
    int maxsize;//顺序表的最大长度
} SeqList;

/**
 *
 * @param l 线性表指针
 * @return 1:success?fail
 */
int initList(SeqList *l) {
    //用malloc函数申请一片连续的存储空间
    //重点掌握为什么需要强转malloc()类型为int*类型
    //指针在移动是会根据sizeof(type)去进行移动，如果你不指定指针的类型，那么在指针移动检索的操作时，指针只会一个一个字节的去移动
    l->data = (int *) malloc(INIT_SIZE * sizeof(int));
    l->length = 0;
    l->maxsize = INIT_SIZE;
    return 1;
}

/**
 *
 * @param l 线性表指针
 * @param len 长度
 * @return 1:success?fail
 */
int increaseSize(SeqList *l, int len) {
    int *pInt = l->data;
    l->data = (int *) malloc(l->maxsize + len * sizeof(int));
    //复制
    for (int i = 0; i < l->length; ++i) {
        l->data[i] = pInt[i];//将数据复制到新区域
    }
    l->maxsize = l->maxsize + len;//顺序表的最大长度增加len
    free(pInt);//释放空间
    return 1;
}

/**
 *
 * @param l 线性表指针
 * @param i 下标
 * @param e 插入元素
 * @return
 */
int listInsert(SeqList *l, int i, int e) {
    for (int j = l->length; j >= i; --j) {
        l->data[j] = l->data[j - 1];
    }
    l->data[i] = e;
    l->length++;
    return 1;
}

/**
 *
 * @param l 线性表指针
 * @param i 下标
 * @param e int 指针，用于接收删除值
 * @return
 */
int listDelete(SeqList *l, int i, int *e) {
    if (i < 1 || i > l->length) {
        return 0;
    }
    *e = l->data[i - 1];
    for (int j = i; j < l->length; j++) {
        l->data[j - 1] = l->data[j];
    }
    l->length--;
    return 1;

}

/**
 * 取出下标对应的元素
 * @param l 线性表
 * @param i 要去除元素下标
 * @return 下标对应的元素
 */
int getElem(SeqList l, int i) {
    return l.data[i - 1];
}

/**
 * 按值查找，并返回下标
 * @param l 线性表
 * @param e 要查找元素值
 * @return -1表示没有找到
 */
int locateElem(SeqList l, int e) {
    for (int i = 0; i < l.length; ++i) {
        if (e == l.data[i]) {
            return i + 1;
        }
    }
    return -1;
}

int main() {
    SeqList seqList;
    initList(&seqList);
    increaseSize(&seqList, 100);
    printf("%l", sizeof(seqList));
}