《数据结构》爬坡 — — 顺序表的初始化&基本操作（删查找）

---

1.《数据结构》的第一次爬坡

2.《数据结构》爬坡 — — 算法的基本概念与效率的度量

3.《数据结构》爬坡 — — 线性表的定义

4.《数据结构》爬坡 — — 顺序表的初始化&基本操作

---

一、顺序表的定义

顺序表 ---- 用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

a1的数组下标为0；内存地址：LOC(A)
a3的数组下标为2；内存位置：LOC(A) + 2 * sizeof(ElemType)
… …
an的数组下标为n-1；内存位置：LOC(A) + (n-1) * sizeof(ElemType)

数据元素的存储位置与线性表的起始位置相差 __ 个，这个自己要细心注意。

我们知道，每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序成正比的常数，因此，线性表中的任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。通常用高级程序设计语言中的数组来描述线性表的顺序存储结构。

注意： 线性表中元素的位序是从1开始的，而数组中元素的下标是从0开始的。

---

---

1.1 顺序表的初始化

一维数组可以是静态分配的，也可以是动态分配的。

• 静态分配，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃。

• 动态分配，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要为线性表一次性地划分所有空间。

---

1.2 静态顺序表代码实现

静态顺序表代码实现：

#include <iostream>
#include <cstdio>    // 在C++语言导入才能实现print语句
using namespace std;
#define MaxSize 10  // 定义最大长度

typedef int ElemType; // ElemType为可定义的数据类型，此设为int类型

typedef struct{
    ElemType data[MaxSize];  // 用静态的"数组"存放数据元素
    int length; // 当前长度
} Sqlist;

void Initlist(Sqlist &L){
    L.length = 0; // 表初始长度为0.
}

int main(){
    Sqlist L;       // 声明一个顺序表
    Initlist(L);    // 初始化顺序表
    for(int i=0; i<L.length; i++)
        printf("data[%d]=%d\n", i, L.data[i]);
    printf("初始化完成");
    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

---

1.3 动态顺序表代码实现

动态顺序表代码实现：

#include <iostream>
#include <cstdio>
#include <stdlib.h>
using namespace std;

#define InitSize 10
typedef struct{
    int *data;      // 指示动态分配数组的指针
    int MaxSize;    // 顺序表的最大容量
    int length;     // 顺序表的当前长度
}SeqList;       // 类型定义（动态）

void InitList(SeqList &L){
    // 用malloc 函数申请一片连续的空间
    L.data = (int *)malloc(InitSize*sizeof(int));
    L.length = 5;
    L.MaxSize = InitSize;
}

// 增加动态数组长度
void IncreaseSize(SeqList &L,int len){
    int *p=L.data;
    L.data = (int *)malloc((L.MaxSize+len)*sizeof(int));
    for(int i=0; i<L.length; i++){
            L.data[i] = p[i]; // 将数据复制到新区域
    }
    L.MaxSize = L.MaxSize+len;  // 最大长度+len
    free(p);    // 释放原来空间
}

int main(){
    SeqList L;       // 声明一个顺序表
    InitList(L);    // 初始化顺序表
    IncreaseSize(L, 5);
    printf("初始化,插入完成");
    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
32
33
34
35
36
37

---

知识点补充说明：

C的初始动态分配语句为:
L.data= (E1 emType* )malloc (sizeof(ElemType)*InitSize);

C++的初始动态分配语句为:
L.data=new ElemType [InitSize];
1
2
3
4
5

注意： 动态分配并不是链式存储，它同祥属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时动态决定。

---

1.4 顺序表最主要的特点

1. 随机访问，即通过首地址和元素序号可在时间复杂度0(1)内找到指定的元素。
2. 顺序表的存储密度高，每个结点只存储数据元素。
3. 顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

---

二、 顺序表上基本操作的实现

2.1 按位查找

#include <iostream>
#include <cstdio>
#include <stdlib.h>
using namespace std;

#define InitSize 10
typedef int ElemType;
typedef struct{
    int *data;      // 指示动态分配数组的指针
    int MaxSize;    // 顺序表的最大容量
    int length;     // 顺序表的当前长度
}SeqList;       // 类型定义（动态）

// 顺序表的取值，时间复杂度O(1);
ElemType GetElem(SeqList L, ElemType i) {
	if (i < 1 || i > L.length)
		return ERROR; // 判断i值是否合理，若不合理，返回ERROR
	return L.data[i - 1]; // elem[i-1]单元存储第i个数据元素
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.2 按值查找

#include <iostream>
#include <cstdio>
#include <stdlib.h>
using namespace std;

#define InitSize 10
typedef int ElemType;
typedef struct{
    int *data;      // 指示动态分配数组的指针
    int MaxSize;    // 顺序表的最大容量
    int length;     // 顺序表的当前长度
}SeqList;       // 类型定义（动态）

// 按值返回位置，时间复杂度O(n);
int LocateElem(SeqList L, ElemType e){
    for(int i=0;i<L.length;i++){ // 循环遍历表
        if(L.data[i]==e)    // 当值相等返回i+1
            return i+1;
    return 0; // 退出循环，说明查找失败。
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

2.3 插入操作

在顺序表L的第i (1<=i<=L.length+1) 个位置插入新元素e。若i的输入不合法，则返回false，表示插入失败；否则，将第i个元素及其后的所有元素依次往后移动一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true。

// 顺序表的插入，时间复杂度O(n)
bool ListInsert_Sq(SeqList &L, int i, ElemType e) { 
	//在顺序表L中第i个位置之前插入新的元素e
	//i值的合法范围是1<=i<=L.length+1
	if ((i < 1) || (i > L.length + 1))
		return false; //i值不合法
	if (L.length == MAXSIZE)
		return false; //当前存储空间已满
		
	for (int j=L.length; j>=i-1; j--)
		L.elem[j] = L.elem[j+1]; //插入位置及之后的元素后移
	L.data[i-1] = e; //将新元素e放入第i个位置
	L.length++; //表长增1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

2.4 删除操作

删除顺序表L中第i (1<=i<=L. length)个位置的元素，用引用变量e返回。若i的输入不合法，则返回false;否则，将被删元素赋给引用变量e，并将第i+1个元素及其后的所有元素依次往前移动-一个位置，返回true。

// 删除操作，时间复杂度O(n)
ElemType ListDelete(SwqList &L, int i,int &e) { 
	// 在顺序表L中删除第i个元素，并用e返回其值
	// i值的合法范围是1<=i<=L.length
	if ((i < 1) || (i > L.length))
		return false; //i值不合法
	e = L.data[i-]; 
	for (int j = i; j <= L.length; j++)
		L.data[j-1] = L.data[j]; // 被删除元素之后的元素前移
	L.length--; // 表长减1
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12