免费网站主机,太原网站建设技术托管,网站 设计报价,wordpress 知识管理文章目录 二、线性表2.1 定义、基本操作2.1.1 知识总览2.1.2 线性表的定义2.1.3 线性表的基本操作2.1.4 知识回顾与重要考点 2.2 顺序表2.2.1 知识总览2.2.2 顺序表的定义2.2.3 顺序表的实现——静态分配2.2.4 顺序表的实现——动态分配2.2.5 知识回顾与重要考点2.2.6 顺序表的… 文章目录 二、线性表2.1 定义、基本操作2.1.1 知识总览2.1.2 线性表的定义2.1.3 线性表的基本操作2.1.4 知识回顾与重要考点 2.2 顺序表2.2.1 知识总览2.2.2 顺序表的定义2.2.3 顺序表的实现——静态分配2.2.4 顺序表的实现——动态分配2.2.5 知识回顾与重要考点2.2.6 顺序表的插入和删除2.2.6.1 插入2.2.6.2 插入操作的时间复杂度2.2.6.3 删除2.2.6.4 删除操作的时间复杂度2.2.6.5 知识回顾与重要考点 2.2.7 顺序表的查找2.2.7.1 按位查找2.2.7.2 按值查找2.2.7.3 知识回顾与重要考点 二、线性表
2.1 定义、基本操作
2.1.1 知识总览 线性表 定义逻辑结构基本操作运算
2.1.2 线性表的定义
线性表线性表是具有相同数据类型的nn$$0个数据元素的有限序列其中n为表长当n0时线性表是一个空表。若用L命名线性表则其一般表示为 以下是几个概念 ai是线性表中的“第i个”元素线性表中的位序a1是表头元素an是表尾元素除第一个元素外每个元素有且仅有一个直接前驱除最后一个元素外每个元素有且仅有一个直接后继
2.1.3 线性表的基本操作
InitList(L)初始化表。构造一个空的线性表L分配内存空间。DestoryList(L)销毁操作。销毁线性表并释放线性表L所占用的内存空间ListInsert(L,i,e)插入操作。在表L中的第i个位置上插入指定元素eListDelete(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。
Tips
对数据的操作记忆思路——创销、增删改查C语言函数的定义—— 返回值类型 函数名(参数1类型参数1参数2类型参数2……)实际开发中可根据实际需求定义其他的基本操作函数名和参数的形式、命名都可改变命名要有可读性什么时候要传入“”——对参数的修改结果需要“带回来” 为什么要实现对数据结构的基本操作》 团队合作编程你定义的数据结构要让别人能够很方便的使用封装将常用的操作/运算封装成函数避免重复工作降低出错风险 2.1.4 知识回顾与重要考点 2.2 顺序表
2.2.1 知识总览 2.2.2 顺序表的定义 顺序表用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中元素之间的关系由存储单元的邻接关系来体现。
2.2.3 顺序表的实现——静态分配
#define MaxSize 10 //定义最大长度
typeof struct{ElemType data[MaxSize]; //用静态的“数组”存放数据元素int length; //顺序表的当前长度
}SqList; //顺序表的类型定义静态分配方式上述代码中给各个数据元素分配连续的存储空间大小位MaxSize*sizeof(ElemType) 代码实现 #include stdio.h
#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;
}如果“数组”存满了怎么办 可以放弃治疗顺序表的表长刚开始确定后就无法更改存储空间是静态的 思考如果刚开始就声明一个很大的内存空间呢存在什么问题 2.2.4 顺序表的实现——动态分配 Key动态申请和释放内存空间
C —— malloc、free函数
malloc函数返回一个指针需要强制转型为你定义数据元素类型指针
egL.data (ElemType *)malloc(sizeof(ElemType)*InitSize)
表示要申请的一整片连续的内存空间
C —— new、delete关键字 代码实现
#include stdlib.h
#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 0;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; //顺序表最大长度增加lenfree(p); //释放原来的内存空间
}int main() {SeqList L; //声明一个顺序表InitList(L); //初始化顺序表//……往顺序表中随便插入几个元素……IncreaseSize(L, 5);return 0;
}顺序表的特点
随机访问即可以在O(1)时间内找到第i个元素。代码实现data[i-1]存储密度高每个节点只存储数据元素。拓展容量不方便即便采用动态分配的方式实现。拓展长度的时间复杂度也比较高插入、删除操作不方便需要移动大量元素。
2.2.5 知识回顾与重要考点 2.2.6 顺序表的插入和删除 2.2.6.1 插入 ListInsert(L,i,e)插入操作。在表L中的第i个位置插入指定元素e。
代码实现
#include stdio.h
#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
}
//插入
bool ListInsert(SqList L, int i, int e) {if (i1 || iL.length 1) //判断i的范围是否有效return false;if (L.length MaxSize) //当前存储空间已满不能插入return false;for (int j L.length; j i; j--) {L.data[j] L.data[j - 1]; //将第i个元素及之后的元素后移}L.data[i - 1] e; //在位置i出放入eL.length; //长度加1return true;
}int main() {SqList L; //声明一个顺序表InitList(L);//初始化顺序表//……此处省略一些代码插入几个元素ListInsert(L, 3, 3);printf(data[2]%d, L.data[2]);return 0;
}2.2.6.2 插入操作的时间复杂度 2.2.6.3 删除
ListDelete(L,i,e)删除操作。删除表L中第i个位置的元素并用e返回删除元素的值。 代码实现
#include stdio.h
#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
}
//插入
bool ListInsert(SqList L, int i, int e) {if (i1 || iL.length 1) //判断i的范围是否有效return false;if (L.length MaxSize) //当前存储空间已满不能插入return false;for (int j L.length; j i; j--) {L.data[j] L.data[j - 1]; //将第i个元素及之后的元素后移}L.data[i - 1] e; //在位置i出放入eL.length; //长度加1return true;
}
//删除
bool ListDelete(SqList L, int i, int e) {if (i1 || iL.length) //判断i的范围是否有效return false;e L.data[i - 1]; //将被删除的元素赋值给efor (int j i; j L.length; j) {L.data[j - 1] L.data[j]; //将第i个位置后的元素前移}L.length--; //线性表长度减1return true;
}
int main() {SqList L; //声明一个顺序表InitList(L);//初始化顺序表//……此处省略一些代码插入几个元素ListInsert(L, 3, 3);int e -1; //用变量e把删除的元素“带回来”if (ListDelete(L, 3, e))printf(已删除第3个元素删除元素为%d\n, e);elseprintf(位序i不合法删除失败\n);return 0;
}2.2.6.4 删除操作的时间复杂度 2.2.6.5 知识回顾与重要考点 2.2.7 顺序表的查找 2.2.7.1 按位查找
静态分配实现按位查找 动态分配实现按位查找 按位查找的时间复杂度 2.2.7.2 按值查找
LocateElem(L,e)按值查找操作。在表L中查找具有给定关键字值的元素。 注意数组下标为i的元素值等于e返回其位序i1 代码实现
#include stdio.h
#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
}
//插入
bool ListInsert(SqList L, int i, int e) {if (i1 || iL.length 1) //判断i的范围是否有效return false;if (L.length MaxSize) //当前存储空间已满不能插入return false;for (int j L.length; j i; j--) {L.data[j] L.data[j - 1]; //将第i个元素及之后的元素后移}L.data[i - 1] e; //在位置i出放入eL.length; //长度加1return true;
}
//删除
bool ListDelete(SqList L, int i, int e) {if (i1 || iL.length) //判断i的范围是否有效return false;e L.data[i - 1]; //将被删除的元素赋值给efor (int j i; j L.length; j) {L.data[j - 1] L.data[j]; //将第i个位置后的元素前移}L.length--; //线性表长度减1return true;
}
//在顺序表L中查找第一个元素值等于e的元素并返回其位序
int LocateElem(SqList L, int e) {for (int i 0; i L.length; i) {if (L.data[i] e)return i 1;}return 0;
}
int main() {SqList L; //声明一个顺序表InitList(L);//初始化顺序表//……此处省略一些代码插入几个元素ListInsert(L, 3, 3);int i LocateElem(L, 3);printf(位序为%d, i);return 0;
}按值查找的时间复杂度 2.2.7.3 知识回顾与重要考点
