ssy的小天地

愿汝如是 千金不换

0%

数据结构与算法之线性表

发表于 更新于 分类于

本节主要介绍了顺序表与链表的C++实现。

顺序表

  • 把线性表中的所有表项按照其逻辑顺序依次存储到从计算机存储中指定存储位置开始的一块连续的存储空间中
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
#include <iostream>
using namespace std;

#define MAXSIZE 20//最大存储容量
typedef int ElemType;

class SqList
{
public:
    SqList();//
    SqList(ElemType elems[],int n);//有参构造器
    ~SqList();//
    bool CreatList();//新建一个顺序表
    bool UnionList(SqList L1,SqList L2);
    int LocateElem(ElemType e);//按元素查找：成功则返回元素的序号（从1开始）,失败则返回0
    int ListLength();//顺序表的长度
    bool GetElem(int i, ElemType& e);//查找第i个位置的元素
    bool ListInsert(int i,ElemType e);//在第i个位置插入元素
    bool ListDelete(int i,ElemType& e);//删除第i个位置的元素
    bool ListEmpty();//判空
    void clearList();//清空顺序表
    void display();//显示当前的顺序表

private:
    ElemType data[MAXSIZE];//下标从0开始，但是对线性表的操作中的下标从1开始：第1个元素其实就是下标为0的元素
    int length;
};

SqList::SqList()//初始化
{
    length=0;//
}

SqList::SqList(ElemType elems[],int n)//有参构造器
{
    if(n>MAXSIZE)
    {
        cout<<"传入的顺序表长度超出最大范围，只接收了前"<<MAXSIZE<<"个元素"<<endl;
        length=MAXSIZE;
    }
    else
        length=n;//

    for(int i=0;i<length;i++)
        data[i]=elems[i];
}

SqList::~SqList()
{

}

bool SqList::CreatList()
{

    cout<<"插入多少个元素(0-20)?"<<endl;
    cin>>length;
    if(length<0||length>MAXSIZE)
    {
        length=0;
        return false;
    }
    for(int i=1;i<=length;i++)
    {
//        cout<<"请输入顺序线性表的第"<<i<<"个元素：";
//        cin>>L->data[i-1];
        data[i-1]=i;
    }
    return true;
}

bool SqList::UnionList(SqList L1,SqList L2)
{
    int i,j;
    for(i=0;i<L1.length;i++)
    {
        data[i]=L1.data[i];
    }

    for(j=0;j<L2.length;j++)
        if(L1.LocateElem(L2.data[j])==0)
        {
            if(i>=MAXSIZE)
                return false;
            data[i]=L2.data[j];
            i++;
        }
    length=i;
    return true;
}

int  SqList::LocateElem(ElemType e)//成功则返回元素的序号（从1开始）,失败则返回0
{
    for(int i=0;i<length;i++)
        if(data[i]==e)
            return i+1;
    return 0;
}

int  SqList::ListLength()
{
    return length;
}

bool SqList::GetElem(int i, ElemType& e)
{
    if(length==0 || i<1|| i>length)
        return false;
    e=data[i-1];
    return true;
}

bool SqList::ListInsert(int i,ElemType e)
{
    if(length==MAXSIZE || i<1|| i>length+1)//线性表满，或者i的范围不在合理范围内时返回错误
        return false;
    if(i<=length)//不在表尾
    {
        //插入位置的后续元素后移一位
        for(int k=length-1;k>=i-1;k--)
            data[k+1]=data[k];// 倒序挪动位置，避免覆盖问题
    }
    data[i-1]=e;//插入元素
    length++;
    return true;
}

bool SqList::ListDelete(int i,ElemType& e)
{
    if(length==0 || i<1|| i>length)//线性表满，或者i的范围不在合理范围内时返回错误
        return false;
    e=data[i-1];//取出元素
    if(i<=length)//不在表尾
    {
        //插入位置的后续元素前移一位
        for(int k=i-1;k<length-1;k++)
            data[k]=data[k+1];// 倒序挪动位置，避免覆盖问题
    }
    length--;
    return true;
}

bool SqList::ListEmpty()
{
    if (length==0)
        return true;
    return false;
}

void SqList::clearList()
{
    length=0;
}

void SqList::display()
{
    for(int i=0;i<length;i++)
        cout<<data[i]<<"  ";
    cout<<endl;
}

int main()
{
    SqList list;
    int num;
    ElemType elem;
    bool flag;
    cout<<"1.顺序表的创建与显示"<<endl;
    if(!list.CreatList())
        cout<<"顺序表创建失败！"<<endl;
    else
        cout<<"顺序表创建成功！"<<endl;
    //顺序表的显示
    list.display();
    cout<<endl<<endl;

    cout<<"2.按元素查找"<<endl;
    num=list.LocateElem(3);
    cout<<"3是顺序表的第"<<num<<"个元素"<<endl<<endl<<endl;

    cout<<"3.按位置查找"<<endl;
    list.GetElem(4,elem);
    cout<<"顺序表的第四个元素是:"<<elem<<endl<<endl<<endl;

    cout<<"4.顺序表的插入"<<endl;
    if(list.ListInsert(2,10))
        cout<<"插入成功!在第2个位置插入10后:"<<endl;
    else
        cout<<"插入失败"<<endl;
    list.display();
    cout<<endl<<endl;

    cout<<"5.删除元素"<<endl;
    list.ListDelete(5,elem);
    cout<<"删除第5个元素:"<<elem<<endl;
    cout<<"该表的长度为:"<<list.ListLength()<<endl;
    list.display();
    cout<<endl<<endl;

    cout<<"6.清空顺序表"<<endl;
    cout<<"清空顺序表前-----------";
    if(!list.ListEmpty())
    {
        cout<<"当前顺序表不是空表！"<<endl;
        list.clearList();
        cout<<"清空顺序表后-----------";
        if(list.ListEmpty())
            cout<<"当前顺序表是空表！"<<endl;
    }
    cout<<endl<<endl;

    cout<<"7.合并顺序表"<<endl;
    ElemType elems1[8]={0,1,2,3,4,5,6,7};
    ElemType elems2[9]={5,6,7,8,9,10,11,1,12};

    SqList list1={elems1,8};
    SqList list2={elems2,9};
    SqList list3;
    cout<<"合并前的两个表为:"<<endl;
    list1.display();
    list2.display();
    flag=list3.UnionList(list1,list2);
    if(!flag)
        cout<<"合并后，顺序表的长度超过最大范围"<<endl;
    cout<<"该表的长度为:"<<list3.ListLength()<<endl;
    list3.display();
    return 0;
}

结果如下：

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
1.顺序表的创建与显示
插入多少个元素(0-20)?
9
顺序表创建成功！
1  2  3  4  5  6  7  8  9  

2.按元素查找
3是顺序表的第3个元素

3.按位置查找
顺序表的第四个元素是:4

4.顺序表的插入
插入成功!在第2个位置插入10后:
1  10  2  3  4  5  6  7  8  9  

5.删除元素
删除第5个元素:4
该表的长度为:9
1  10  2  3  5  6  7  8  9  

6.清空顺序表
清空顺序表前-----------当前顺序表不是空表！
清空顺序表后-----------当前顺序表是空表！

7.合并顺序表
合并前的两个表为:
0  1  2  3  4  5  6  7  
5  6  7  8  9  10  11  1  12  
该表的长度为:13
0  1  2  3  4  5  6  7  8  9  10  11  12

链表

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node *next;

    Node(int da = 0, Node *p = NULL) {
        this->data = da;
        this->next = p;
    }
};

class List {
private:
    Node *head, *tail;
    int position;
public:
    List() { head = tail = NULL; };

    ~List() {
        delete head;
        delete tail;
    };

    void print();//链表的打印

    void Insert(int da = 0);//链表的插入

    void Delete(int da = 0);//链表的删除

    void Search(int da = 0);//链表的查找

    int getValueAt(int position);//查找特定位置对应的值

    void setValueAt(int position, int da);//更新特定位置的值
};

int List::getValueAt(int position) {
    Node *p = head;
    if (p == NULL) {
        cout << "The List is Empty!" << endl;
    } else {
        int posi = 0;
        while (p != NULL && posi != position) {
            posi++;
            p = p->next;
        }
        if (p == NULL) {
            cout << "There is no value of this position in this List!" << endl;
        } else {
            cout << "In this Position,the value is:" << p->data << endl;
        }
    }
    return p->data;
}

void List::setValueAt(int position, int da) {
    Node *p = head;
    if (p == NULL) {
        cout << "The List is Empty!" << endl;
    } else {
        int posi = 0;
        while (p != NULL && posi != position) {
            posi++;
            p = p->next;
        }
        if (p == NULL) {
            cout << "There is No Position in this List!" << endl;
        } else {
            p->data = da;
            cout << "The Value in this position has been Updated!" << endl;
        }
    }
}

void List::Search(int da) {

    Node *p = head;
    if (p == NULL) {
        cout << "Sorry, The List is Empty!" << endl;
        return;
    }
    int count = 0;
    while (p != NULL && p->data != da) {
        p = p->next;
        count++;
    }
    cout << "the value you want to search is at position " << count << endl;
}

void List::Delete(int da) {
    Node *p = head, *q = head;
    if (p == NULL) {
        cout << "Sorry, The List is Empty!" << endl;
        return;
    }
    while (p != NULL && p->data != da) {
        q = p;
        p = p->next;
    }
    q->next = p->next;
    cout << "The Deletion Operation had been finished!" << endl;
}

void List::Insert(int da) {
    if (head == NULL) {
        head = tail = new Node(da);
        head->next = NULL;
        tail->next = NULL;
    } else {
        Node *p = new Node(da);
        tail->next = p;
        tail = p;
        tail->next = NULL;
    }

}

void List::print() {
    Node *p = head;
    while (p != NULL) {
        cout << p->data << " \a";
        p = p->next;
    }
    cout << endl;
}

int main() {
    cout << "Linked list test!" << endl;
    List l1;
    l1.Insert(1);
    l1.Insert(2);
    l1.Insert(3);
    l1.Insert(4);
    l1.Insert(5);
    l1.Insert(6);
    l1.Insert(7);
    l1.print();
    l1.Search(4);
    l1.Delete(6);
    l1.print();
    l1.getValueAt(3);
    l1.setValueAt(3, 9);
    l1.print();
    cout << "The End!" << endl;
    return 0;
}

结果如下：

image-20221207202053089

顺序表和链表的比较

  • 存储方面：

    • 顺序表为静态结构，而链表为动态结构

    • 数组从栈中申请空间，而链表从堆空间申请

    • 单链表的存储密度比顺序表低：
      $$
      存储密度=\frac{数据本身所占存储}{整个数据结构所占存储}
      $$

    • 字符串往往用字符数组来实现

  • 运算方面：

    • 定位操作：
      • 顺序表，通过定位公式可以随机访问任一元素
      • 单链表中，需要顺链逐个查找
    • 修改操作：
      • 顺序表数据元素移动，而链表修改指针
      • 在单链表里进行插入、删除运算比在顺序表容易
欢迎来到ssy的世界