二、线性表
2.1线性表的定义和基本操作
2.1.1 线性表的基本概念
线性表:是具有相同数据类型的 n 个数据元素的有限序列。
(Eg:所有的整数按递增次序排列,不是顺序表,因为所有的整数是无限的)
其中n为表长,当n=0时线性表是一个空表。若用L表示一个线性表,则
是线性表中的第i个元素,称为线性表中的位序
是表头元素;是表尾元素。
除第一个元素外,每个元素有且仅有一个直接前驱;
除最后一个元素外,每个元素有且仅有一个直接后继
2.1.2 线性表的基本操作
- 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 的长度,即表中元素的个数。
- PrintList(L):输出操作。按前后顺序输出线性表 L 的所有元素值。
- Empty(L):判空操作。若表L 为空表,则返回 true,否则返回 false。
对数据操作的思路:创销、增删改查
什么时候要传入引用“&”—―对参数的修改结果需要“带回来”时
#include<stdio.h>
void test ( int &x) {
x=1024;
printf ( "test函数内部x=%d\n",x) ;
}
int main() {
int x =1;
printf( "调用test前x=d\n",x) ;
test (x);
printf ( "调用test后x=%din",x);
}
2.2线性表的顺序表示
2.2.1 顺序表的定义
顺序表:用顺序存储的方式实现线性表
顺序存储:把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中
C语言中通过sizeof(ElementType)可以知道一个数据元素的大小
2.2.2 顺序表的实现
静态分配
#define MaxSize 10 // 定义最大长度
typedef struct {
int data[MaxSize]; // 使用静态的数组存放数据元素
int length; // 顺序表的当前长度
}SqList; //顺序表的类型定义
//基本操作 —— 初始化一个顺序表
void InitList(SqList &L) {
for(int i=0;i<MaxSize;i++)
L.data[i]=0; //将所有数据元素设置为默认初始值
L.length = 0; // 顺序表初始长度为0
}
int main() {
SqList L; // 声明一个顺序表
InitList(L); // 初始化顺序表
return 0;
}
如果不设置数据元素的默认值
静态数组的表长确定后就无法更改(存储空间是静态的),最好使用动态分配
动态分配
#include <stdlib.h> //malloc函数要使用的头文件
#define InitSize 10 // 顺序表的初始长度
typedef struct {
int *data; // 声明动态分配数组的指针
int MaxSize; // 顺序表的最大容量
int length; // 顺序表的当前长度
}SeqList;
// 初始化顺序表
void InitList(SqList &L) {
// 用malloc函数申请一片连续的存储空间
L.data = (int *)malloc(InitSize * sizeof(int));
//(int*)把malloc返回的指针转换成定义的同类型的指针
L.length = 0; //把数据表的长度设为0
L.MaxSize = InitSize; //把数据表的最大长度设为初始值
}
// 增加动态数组的长度
void IncreaseSize(SqList &L, int len) {
int *p = L.data; //把顺序表的data指针的值赋给指针p
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); //再多申请5个空间
return 0;
}
顺序表的特点:
- 随机访问,即可以在 O(1) 时间内找到第 i 个元素
- 存储密度高,每个节点只存储数据元素
- 拓展容量不方便(即使使用动态分配的方式实现,拓展长度的时间复杂度也比较高,要把数据复制到新的区域)
- 插入删除操作不方便,需移动大量元素
2.2.3 顺序表的插入删除
Listlnsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e
#define MaxSize 10 // 定义最大长度 10个元素
typedef struct {
int data[MaxSize]; // 用静态的数组存放数据元素
int length; // 顺序表的当前长度
}SqList; //定义数据表SqlList
// 在顺序表i位置插入e
bool ListInsert(SqList &L, int i, int e) { //注意位序、数组下标的关系
if (i < 1 || i > L.length+1) // 判断i的范围是否有效
return false;
if (L.length >= MaxSize) // 判断存储空间是否已满
return false;
for (int j = L.length; j >= i; j--) // 将第i个元素之后的元素后移
L.data[j] = L.data[j-1];
L.data[i-1] = e; // 在位置i处放入e i-1 下标
L.length++; // 长度+1
return true;
}
int main() {
SqList L; //声明一个顺序表
InitList(L); //初始化顺序表
...//此次省略一些代码,插入几个元素
ListInsert(L, 3, 3); //调用函数 在顺序表L的第三个位置插入数据3
return 0;
}
插入操作的时间复杂度 问题规模n=L.length(表长)
最好情况:新元素插入到表尾,不需要移动元素 i = n+1,循环0次;
最好时间复杂度 = O(1)
最坏情况:新元素插入到表头,需要将原有的 n 个元素全都向后移动 i = 1,循环 n 次;
最坏时间复杂度 = O(n)
平均情况:假设新元素插入到任何一个位置的概率相同,即 i = 1,2,3, … , length+1 的概率都是 p = ,循环 n 次;i=2 时,循环 n-1 次;i=3,循环 n-2 次 …… i =n+1时,循环0次 ,平均循环次数 np + (n-1)p + (n-2)p +... + 1⋅p ==
平均时间复杂度 = O(n)
ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值。
#define MaxSize 10
typedef struct {
int data[MaxSize];
int length;
} SqList;
// 删除顺序表i位置的数据并存入e
bool ListDelete(SqList &L, int i, int &e) { //注意e加了&引用,这里处理的e跟main函数中的e在内存中对应的是同一份数据
if (i < 1 || i > L.length) // 判断i的范围是否有效
return false;
e = L.data[i-1]; // 将被删除的元素赋值给e
for (int j = i; j < L.length; j++) //将第i个位置后的元素前移
L.data[j-1] = L.data[j];
L.length--; //线性表长度-1
return true;
}
int main() {
SqList L; //声明一个顺序表
InitList(L); //初始后顺序表
...//此次省略一些代码,插入几个元素
int e = -1; //用变量e把删除的元素“带回来”
if (ListDelete(L, 3, e)) //调用删除操作,删除第三个位置的元素用e返回
printf("已删除第3个元素,删除元素值为%d\n", e);
else
printf("位序i不合法,删除失败\n");
return 0;
}
插入操作的时间复杂度 问题规模n=L.length(表长)
最好情况:删除表尾元素,不需要移动其他元素 i = n,循环 0 次;
最好时间复杂度 = O(1)
最坏情况:删除表头元素,需要将后续的 n-1 个元素全都向前移动 i = 1,循环 n-1 次;
最坏时间复杂度 = O(n)
平均情况:假设删除任何一个元素的概率相同,即 i = 1,2,3, … , length 的概率都是 p = ,i=1时,循环 n-1 次;i=2 时,循环 n-2 次;i=3,循环 n-3 次 …… i =n时,循环0次 ,平均循环次数 (n-1)p + (n-2)p +... + 1⋅p ==
平均时间复杂度 = O(n)
2.2.4 顺序表的查找
GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。
// 静态分配的按位查找
#define MaxSize 10
typedef struct {
ElemType data[MaxSize];
int length;
}SqList;
ElemType GetElem(SqList L, int i) {
return L.data[i-1];
}
// 动态分配的按位查找
#define InitSize 10
typedef struct {
ElemType *data;
int MaxSize;
int length;
}SeqList;
ElemType GetElem(SeqList L, int i) {
return L.data[i-1];
}
LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。
#define InitSize 10
typedef struct {
ElemType *data;
int MaxSize;
int length;
}SqList;
// 查找第一个元素值为e的元素,并返回其位序
int LocateElem(SqList L, ElemType e) {
for (int i = 0; i < L.length; i++)
if (L.data[i] == e)
return i+1; // 数组下标为i的元素值等于e,返回其位序i+1
return 0; // 没有查找到
}