帮站seo,网站制作ppt模板,wordpress mysql 安装,wordpress如何添加自定义栏目线性表1. 线性表1.1 线性表的定义1.1.1 访问型操作1.1.2 加工型操作1.2 线性表的顺序存储结构1.2.1 定义顺序表数据类型方法11.2.2 定义顺序表数据类型方法21.3 顺序表的基本操作实现1.3.1 顺序表的初始化操作1.3.2 顺序表的插入操作1.3.3 顺序表的删除操作1.3.4 顺序表的更新操…
线性表1. 线性表1.1 线性表的定义1.1.1 访问型操作1.1.2 加工型操作1.2 线性表的顺序存储结构1.2.1 定义顺序表数据类型方法11.2.2 定义顺序表数据类型方法21.3 顺序表的基本操作实现1.3.1 顺序表的初始化操作1.3.2 顺序表的插入操作1.3.3 顺序表的删除操作1.3.4 顺序表的更新操作1.3.5 顺序表的定位操作1.3.6 顺序表的遍历操作1.3.7 顺序表的创建操作1. 线性表
具有1:1的线性关系的数据对象称为线性表。
1.1 线性表的定义
线性表是最简单的一种线性结构具有如下特征。 1线性表中必存在唯一的一个“第一元素”。 2线性表中必须存在唯一的一个“最后元素”。 3除了最后元素之外其余元素均有唯一的直接后继。 4除了第一个元素之外其余元素均有唯一的直接前驱。
线性表的抽象数据类型定义形式
ADT List { 数据对象 D{ai | ai∈ElemSet,i1,2,…,n0} { n为线性表的表长即数据元素的个数n0时的线性表为空表。} 数据关系 R { ai-1,ai |ai-1,ai∈D, i2,3,…,n } { 设线性表为(a1,a2,…,ai,…,an),称i为ai在线性表中的位序} 基础操作 初始化操作 销毁操作 访问型操作 加工型操作 } ADT List
L表示会引起线表的变化L表示不会引起线标的变化。
下面分别介绍线性表的各个基本操作的初始条件和实现的功能
1.1.1 访问型操作
这类操作只是访问线性表中的元素并没有改变线性表。 1判断线性表是否为空ListEmptyL。 初始条件线性表L存在。 操作结果若L为空表则返回TRUE否则返回FALSE。 2求线性表的长度ListLengthL 初始条件线性表存在。 操作结果放回L中的数据元素的个数。 3得到线性表中某个位置上的元素GetElemLie。 初始化条件线性表L已存在且 1iLengthListL。 操作结果用e返回L中第i个元素的值。 4通知比较寻找位置LocateElemLecompare。 初始条件线性表L已存在e为给定值compare是元素比较函数。 操作条件返回L中第1个与e满足关系compare的元素的位序。若这样的元素不存在则返回值-1 。 5遍历线性表ListTraverseL。 初始条件线性表L已存在。 操作结果依次访问L中的每个元素。
1.1.2 加工型操作
这类操作改变了原有的线性表。 1初始化操作InitListL。 操作结果构造一个空的线性表L。 2销毁操作DestroyListL。 初始条件线性表L已存在。 操作结果销毁线性表L。 3线性表置空CleaerListL。 初始化条件线性表L已存在。 操作结果将L重置为空表L由非空为空。 4修改线性表中某个位置上的元素置PutElemLie。 初始化条件线性表L已存在且1iLengthListL。 操作结果给L中第i个元素赋值e。L中的第i个元素的值发生了改变。 5在第i个位置上插入数据元素ListInsertLie。 初始条件线性表L已存在且1iLengthListL1. 操作结果在L的第i个元素之前插入新的元素e并将L的长度增1 。 6将线性表的第i个元素删除ListDeleteLie。 初始条件线性表L已存在且1iLengthListL。 操作结果删除L的第i个元素并且用e 返回其值同时将L的长度减1 。
其中最重要的是插入操作和删除操作。
1.2 线性表的顺序存储结构
线性表的顺序存储结构是用一组连续的存储空间存放线性表中的各个数据元素并用位置相邻的存储空间关系表示线性表中数据元素的直接前驱和直接后继的次序关系称为顺序表。
1.2.1 定义顺序表数据类型方法1
包括以下数据成员 1一片连续的存储空间数组用于存放数据元素。 2线性表的容量数组的大小防止溢出。 3线性表的长度已经存入到数组中的数据元素个数。
1.2.2 定义顺序表数据类型方法2
包括以下数据成员 1一片连续的存储空间的起始地址存放数组的起始地址。 2线性表的容量数组的大小防止溢出。 3线性表的长度已经存入到数组中的数据元素个数。
对于两种存储结构的不同描述。第一种容易理解使用相对简单但是数组是顺序表的成员大小固定因此缺乏灵活性。第二种理解起来有一定难度数组不是顺序表的成员可根据实际问题的需要吗在初始化操作中自定义数组的大小因此具有较好的灵活性。
1.3 顺序表的基本操作实现
为了使数据结构中的操作具有很好的健壮性在函数的定义中通常用函数值表示操作的成功与失败。函数值为1表示成功函数值为0表示失败。有时候为了方便起见也可以将操作的结果作为函数的返回值。
1.3.1 顺序表的初始化操作
顺序表的初始化操作是完成一片连续空间的申请将空间的起始地址、容量大小和数据个数0依次存放到顺序表中对应成员中。 算法的实现
int initSqList(SqList* L, int max)
{L-data (STD*)malloc(max * sizeof(STD));if (L-data NULL){perror(initSqList::);exit(0);}L-length 0;L-listSize max;return 1;//表示初始化操作成功
}函数exit0的功能是结束程序的执行。为什么当动态申请存储空间失败时不用“return 0”而是调用函数exit0原因是既然顺序表的初始化失败了其他的有关对顺序表的操作都不可能正确执行因此退出程序并放回到系统。 【算法分析】 该算法不涉及基本操作的循环执行算法的时间复杂度为T(n) O1。
1.3.2 顺序表的插入操作
顺序表的插入操作是将某个学生数据插入顺序表中指针成员指向数组的给定位置并将顺序表的长度成员加1 算法实现如下
int insertSqList(SqList* L, int i, STD x)//i是插入位置对应下标是i-1
{//插入失败的情况判断if (i1 || iL-length 1){printf(插入位置异常\n);return 0;}if (L-length L-listSize){printf(容量不够\n);return 0;}//将区间[i-1,L-lenght-1]内的一组数据元素向后移动一个位置for (int k L-length - 1; k i - 1; k--){L-data[k 1] L-data[k];}//将待插入数据放入指定位置i即下标i-1上L-data[i - 1] x;//长度加1L-length;//插入成功return 1;
}寻找插入位置将数据插进来需移动数据元素。 最好情况in1;基本语句执行0次时间复杂度为O1 最坏情况i1基本语句执行n次时间复杂度为O(n) 平均情况1in1:等概率pi 1/(n1)。 算法的时间复杂度为T(n)O(n) 。
1.3.3 顺序表的删除操作
顺序表的删除操作是将顺序表中指针成员指向数组的给定位置的数组元素删除并将数据个数减1. 算法实现如下
int deleteSqList(SqList* L, int i, STD* x)
//i表示接受删除数据元素位置的整形变量
//x是将被删除的数据元素存回到主调函数中某个变量的指针变量
{//判断删除失败的条件是否成立if (L-length 0){printf(没有数据不能删除\n);return 0;}if (i 0 || i L-length){printf(位置异常不能被删除\n);return 0;}//将被删除的数据元素存放到*x中*x L-data[i - 1];//将区间[i,L-length-1]内的一组数据元素向前移动一个位置for (int k i; k L-length; k){L-data[k - 1] L-data[k];}//长度减1L-length--;//删除成功return 1;
}【算法分析】 寻找删除位置将数据删除需移动数据元素。 最好情况in1;基本语句执行0次时间复杂度为O1 最坏情况i1基本语句执行n次时间复杂度为O(n) 平均情况1in:等概率pi 1/(n)。 算法的时间复杂度为T(n)O(n) 。
1.3.4 顺序表的更新操作
顺序表的更新操作是用新数据替换指定位置的数据。
int updateSqList(SqList* L, int i, STD x)
{//更新失败条件的判断if (L-length 0){printf(没有数据不能更新\n);return 0;}if (i1 || iL-length){printf(位置不合适\n);return 0;}//开始更新数据L-data[i - 1] x;//更新成功return 1;
}【算法分析】 该算法的操作不涉及循环均为顺序执行所以算法的时间复杂度为T(n)O(1)。
1.3.5 顺序表的定位操作
顺序表的定位操作是根据给定的条件得到某个数据元素的位置。定位操作又称为查找操作。 位置从1开始 算法实现如下
int locationSqList(SqList* L, char* newid)
{int i;//查找失败的条件判断if (L-length 0){printf(没有数据\n);return 0;}for (int i 0; i L-length; i){//查找成功的条件的判断if (strcmp(L-data[i].name, newid) 0){return i 1;}}//查找失败return 0;
}【算法分析】 按照给定的条件查找相应的数据元素需逐个判断。最好的情况是O(1)最坏的情况是O(n)。 等概率加权平均是O(n)。
1.3.6 顺序表的遍历操作
顺序表的遍历操作是输出顺序表中存放的所有数据元素。 分析遍历操作不会引起顺序表的变化遍历函数只需一个形参 算法实现如下
int dispSqlist(SqList* L)
{if (L-length 0){printf(没有数据\n);return 0;}for (int i 0; i L-length; i){printf(%10s%7.2f\n, L-data[i].name, L-data[i].score);}return 1;
}【算法分析】 显示所有的数据必须逐个依序显示时间复杂度为T(n)O(n)。
1.3.7 顺序表的创建操作
顺序表的创建操作依序存入顺序表中。 一共有两种算法 算法1调用初始化函数和插入函数创建顺序表
void createSqList1(SqList* L, int maxsize)
{int n 0;STD x;char yn;//调用初始化函数创建空表——申请空间来存储表的数据do{printf(请输入第%d个学生的姓名和分数用空格隔开, n 1);scanf(%s%f, x.name, x.score);//空度回车以便下次正确读入数据getchar();//调用插入函数将数据插入到尾部insertSqList(L, n, x);printf(继续输入吗Y/N\n);scanf(%c, yn);} while (yn Y || yn y);
}算法2直接读取数据来创建顺序表
void createSqList2(SqList* L, int maxsize)
{int n0;STD x;char yn;//初始化L-data (STD*)malloc(maxsize * sizeof(STD));if (L-data NULL){perror(createSqList2::);return 0;}L-listSize maxsize;L-length 0;//读取数据并插入do{printf(请输入第%d个学生的姓名和分数用空格隔开, n 1);scanf(%s%f, x.name, x.score);//空度回车以便下次正确读入数据getchar();L-data[n] x;if (n L-listSize - 1){break;}else{n;}printf(继续输入吗\n);scanf(%c, yn);} while (yn Y || yn y);
}
