返回目录

第二章 线性表

第一节 顺序表

线性表基础操作

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
#define MaxSize 100
typedef int ElemType;  // 元素类型

typedef struct {
    ElemType data[MaxSize];
    int length;
} SqList;

// 初始化线性表
void InitList(SqList& L) {
    L.length = 0;
}

// 销毁线性表
void DestroyList(SqList& L) {

}

// 获取线性表长度
int GetLength(SqList L) {
    return L.length;
}

// 获取线性表中第i个元素 保存在e中 返回1表示成功 0表示失败
bool GetElem(SqList L, int i, ElemType& e) {
    if (i < 1 || i > L.length) return false;
    e = L.data[i - 1];
    return true;
}

// 查找元素e在线性表中的位置 返回位置
int LocElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; ++i) {
        if (L.data[i] == e) return i + 1;
    }
    return false;
}

// 在第i个位置插入元素e 返回1表示成功 0表示失败
bool InsElem(SqList& L, ElemType e, int i) {
    if (i < 1 || i > L.length + 1) return false;
    if (L.length >= MaxSize) return false;
    for (int j = L.length; j >= i; j--) {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;
    return true;
}

// 删除第i个元素 返回1表示成功 0表示失败
bool DelElem(SqList& L, int i) {
    if (i < 1 || i > L.length) return false;
    for (int j = i; j < L.length; ++j) {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

// 输出线性表
void DisplayList(SqList L) {
    for (int i = 0; i < L.length; ++i) {
        std::cout << L.data[i] << " \n"[i == L.length - 1];
    }
}

删除最大元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Delmaxe(SqList& L) {
    int i, k = 0;
    ElemType mx = L.data[0];
    for (i = 1; i < L.length; i++) {
        if (L.data[i] > mx) {        //找出最大元素
            mx = L.data[i];
        }
    }
    for (i = 0; i < L.length; i++) {
        if (L.data[i] != mx) {        //将不为mx的元素插入到L中
            L.data[k] = L.data[i];
            k++;
        }
    }
    L.length = k;                    //重置L的长度
}

删除重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 仅保留第一个
void DelSame(SqList& L) {
    for (int ok = 1; ok == 1;) {
        ok = 0;
        for (int i = 0; i < L.length; i++) {
            for (int j = i + 1; j < L.length; j++) {
                if (L.data[i] == L.data[j]) {
                    DelElem(L, j + 1);
                    ok = 1;
                }
            }
        }
    }
}

移动

1
2
3
4
5
6
7
8
9
10
11
12
void Move(SqList& L) {
    int i = 0, j = L.length - 1;
    while (i < j) {
        while (i < j && L.data[i] < 0) i++;
        while (i < j && L.data[j] >= 0) j--;
        if (i < j) {
            ElemType temp = L.data[i];
            L.data[i] = L.data[j];
            L.data[j] = temp;
        }
    }
}

排序

1
2
3
4
5
6
7
8
9
10
11
12
13
// 对一个顺序表进行排序
void SortList(SqList& L) {
    ElemType temp;
    for (int i = 0; i < L.length - 1; i++) {
        for (int j = i + 1; j < L.length; j++) {
            if (L.data[i] < L.data[j]) {
                temp = L.data[i];
                L.data[i] = L.data[j];
                L.data[j] = temp;
            }
        }
    }
}

二路归并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void MergeList(const SqList& L1, const SqList& L2, SqList& L) {
    int i = 0, j = 0, k = 0;
    while (i < L1.length && j < L2.length) {
        if (L1.data[i] > L2.data[j]) {
            L.data[k++] = L1.data[i++];
        }
        else {
            L.data[k++] = L2.data[j++];
        }
    }
    while (i < L1.length) {
        L.data[k++] = L1.data[i++];
    }
    while (j < L2.length) {
        L.data[k++] = L2.data[j++];
    }
    L.length = k;
}

集合交并补

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
// 检测元素是否不重复
bool CheckElem(const SqList& L) {
    for (int i = 0; i < L.length; ++i) {
        for (int j = i + 1; j < L.length; ++j) {
            if (L.data[i] == L.data[j]) return false;
        }
    }
    return true;
}

// 求两个线性表的并集
SqList Union(const SqList& La, const SqList& Lb) {
    SqList Lc;
    InitList(Lc);
    for (int i = 0; i < La.length; ++i) {
        InsElem(Lc, La.data[i], Lc.length + 1);
    }
    for (int i = 0; i < Lb.length; ++i) {
        if (LocElem(La, Lb.data[i]) == 0) {
            InsElem(Lc, Lb.data[i], Lc.length + 1);
        }
    }
    return Lc;
}

// 求两个线性表的差集
SqList Difference(const SqList& La, const SqList& Lb) {
    SqList Lc;
    InitList(Lc);
    for (int i = 0; i < La.length; ++i) {
        if (LocElem(Lb, La.data[i]) == 0) {
            InsElem(Lc, La.data[i], Lc.length + 1);
        }
    }
    return Lc;
}

// 求两个线性表的交集
SqList Intersection(const SqList& La, const SqList& Lb) {
    SqList Lc;
    InitList(Lc);
    for (int i = 0; i < La.length; ++i) {
        if (LocElem(Lb, La.data[i]) != 0) {
            InsElem(Lc, La.data[i], Lc.length + 1);
        }
    }
    return Lc;
}