网站的图形拖拽验证码怎么做的,手机优化电池充电是什么意思,广元建设银行网站,做养生网站怎么样数据结构知识点汇总(考研C版) 文章目录 数据结构知识点汇总(考研C版)二、线性表2.1 线性表的定义和操作2.1.1 线性表的定义2.1.2 线性表的基本操作 2.2 线性表的顺序表示2.2.1 顺序表的定义2.2.2 顺序表上的基本操作的实现 二、线性表
2.1 线性表的定义和操作
2.1.1 线性表的…数据结构知识点汇总(考研C版) 文章目录 数据结构知识点汇总(考研C版)二、线性表2.1 线性表的定义和操作2.1.1 线性表的定义2.1.2 线性表的基本操作 2.2 线性表的顺序表示2.2.1 顺序表的定义2.2.2 顺序表上的基本操作的实现 二、线性表
2.1 线性表的定义和操作
2.1.1 线性表的定义
线性表是具有相线性表是具有相同数据类型的n(n0)个数据元素的有限序列其中n为表长当n0时线性表是一个空表。若用工命名线性表则其一般表示为同数据类型的n(n0)个数据元素的有限序列其中n为表长当n0时线性表是一个空表。若用工命名线性表则其一般表示为 L ( a 1 , a 2 , ⋯ , a i , a i 1 , ⋯ , a n ) L(a_1,a_2,\cdots,a_i,a_{i1},\cdots,a_n) L(a1,a2,⋯,ai,ai1,⋯,an) 式中a是唯一的“第一个”数据元素又称表头元素;a,是唯一的“最后一个”数据元素又称表尾元素。除第一个元素外每个元素有且仅有一个直接前驱。除最后一个元素外每个元素有且仅有一个直接后继(“直接前驱”和“前驱”、“直接后继”和“后继”通常被视为同义词)。 线性表的特点
表中元素的个数有限。表中元素具有逻辑上的顺序性表中元素有其先后次序。表中元素都是数据元素每个元素都是单个元素。表中元素的数据类型都相同这意味着每个元素占有相同大小的存储空间。表中元素具有抽象性即仅讨论元素间的逻辑关系而不考虑元素究竟表示什么内容 线性表是一种逻辑结构表示元素之间一对一的相邻关系。顺序表和链表是指存储结构两者属于不同层面的概念因此不要将其混淆。 2.1.2 线性表的基本操作
InitList():初始化表。构造一个空的线性表。
Length():求表长。返回线性表工的长度即1中数据元素的个数。
LocateElem(L,e):按值査找操作。在表中査找具有给定关键字值的元素。
Getelem(L,i):按位査找操作。获取表工中第i个位置的元素的值。
ListInsert(,i,e):插入操作。在表工中的第i个位置上插入指定元素e 。ListDelete(L,i,e):删除操作。删除表工中第i个位置的元素,并用e返回删除元素的值 。Printzist():输出操作。按前后顺序输出线性表工的所有元素值。
Empty(L):判空操作。若为空表则返回true否则返回 false。
DestroyList(L):销毁操作。销毁线性表并释放线性表工所占用的内存空间。2.2 线性表的顺序表示
2.2.1 顺序表的定义
线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在顺序表的起始位置,第i个元素的存储位置后面紧接着存储的是第i1个元素称i为元素a在顺序表中的位序。因此顺序表的特点是表中元素的逻辑顺序与其存储的物理顺序相同。 假设顺序表工存储的起始位置为LOC(A)sizeof(ElemType)是每个数据元素所占用存储空间的大小则表所对应的顺序存储如图所示。 线性表的元素类型为 ElemType则静态分配的顺序表存储结构描述为
#define MaxSize 50
typedef struct{
ElemType data[MaxSize]; //顺序表的元素int length; //顺序表的当前长度
}SqList; //顺序表的类型定义 一维数组可以是静态分配的也可以是动态分配的。对数组进行静态分配时因为数组的大小和空间事先已经固定所以一旦空间占满再加入新数据就会产生溢出进而导致程序崩溃。而在动态分配时存储数组的空间是在程序执行过程中通过动态存储分配语句分配的一旦数据空间占满就另外开辟一块更大的存储空间将原表中的元素全部拷贝到新空间从而达到扩充数组存储空间的目的而不需要为线性表一次性地划分所有空间。动态分配的顺序表存储结构描述为:
#define InitSize 100 //表长度的初始定义
typedef struct{ ElemType *data; //指示动态分配数组的指针int MaxSize,length; //数组的最大容量和当前个数
}SeqList; //动态分配数组顺序表的类型定义C的初始动态分配语句为
L.data(ElemType*)malloc(sizeof(ElemType)*InitSize);C的初始动态分配语句为
L.datanew ElemType[InitSize];顺序表的主要优点:
可进行随机访问即可通过首地址和元素序号可以在 0(1)时间内找到指定的元素存储密度高每个结点只存储数据元素。顺序表的缺点也很明显元素的插入和删除需要移动大量的元素插入操作平均需要移动 n/2 个元素,删除操作平均需要移动(n-1)/2个元素;顺序存储分配需要一段连续的存储空间不够灵活。
2.2.2 顺序表上的基本操作的实现
1、顺序表的初始化 静态分配和动态分配的顺序表的初始化操作是不同的。静态分配在声明一个顺序表时就已为其分配了数组空间因此初始化时只需将顺序表的当前长度设为0。
//sqList L; //声明一个顺序表
void Initlist(SqList l){L.length0; //顺序表初始长度为0
}动态分配的初始化为顺序表分配一个预定义大小的数组空间,并将顺序表的当前长度设为 0。Maxsize指示顺序表当前分配的存储空间大小一旦因插入元素而空间不足就进行再分配。
void Initlist(Seqlist ){
L.data(ElemType *)malloc(MaxSize*sizeof(ElemType)); //分配存储空间
L.length0; //顺序表初始长度为0
L.MaxSizeInitSize;//初始存储容量
}2、插入操作 在顺序表工 的第i(1i.length1)个位置插入新元素 e。若i的输入不合法则返回 false表示插入失败;否则将第i个元素及其后的所有元素依次往后移动一个位置腾出一个空位置插入新元素 e顺序表长度增加 1插入成功返回 true。
bool ListInsert(SqList l,int i,ElemType e){if(i1||i.length1)return false; //判断i的范围是否有效if(1.lengthMaxSize)return false; //当前存储空间己满不能插入for(int j.length;ji;j--) //将第i个元素及之后的元素后移L.data[j]L.data[j-1]; L.data[i-1]e;L.length; //在位置i处放入e//线性表长度加1return true;
}3、删除操作 删除顺序表1 中第i(1iL.length)个位置的元素用引用变量e返回。若i的输入不合法则返回 false;否则将被删元素赋给引用变量 e并将第 i1 个元素及其后的所有元素依次往前移动一个位置返回true。
bool ListDelete(SqList l,int i,ElemType e){if(i1||i.length)
//判断i的范围是否有效
return false;
eL.data[i-1]; //将被删除的元素赋值给e
for(int ji;jL.length;j)
L.data[j-1]L.data[j];
L.length--; //线性表长度减1
return true;4、按值查找(顺序查找) 在顺序表工中查找第一个元素值等于e的元素并返回其位序。
int LocateElem(SqListl,ElemType e){int i;for(i0;iL.length;i)if(L.data[i]e)//下标为i的元素值等于e返回其位序i1return i1;
return 0; //退出循环说明查找失败 最好情况:查找的元素就在表头仅需比较一次时间复杂度为(1)。
最坏情况:查找的元素在表尾(或不存在)时需要比较n次时间复杂度为(n)。
