服务器做网站哪个系统好,河北住房和城乡建设厅网站6,大商创 多用户商城,wordpress主题 tao参考教材#xff1a;数据结构C语言版#xff08;严蔚敏#xff0c;吴伟民编著#xff09; 工具#xff1a;XMind、幕布、公式编译器 正在备考#xff0c;结合自身空闲时间#xff0c;不定时更新#xff0c;会在里面加入一些真题帮助理解数据结构 目录 2.1线性… 参考教材数据结构C语言版严蔚敏吴伟民编著 工具XMind、幕布、公式编译器 正在备考结合自身空闲时间不定时更新会在里面加入一些真题帮助理解数据结构 目录 2.1线性表的类型定义
2.2线性表的计算
2.3抽象数据类型线性表的定义
2.4线性表的基本操作
2.5线性表的顺序表示和实现
2.5.1顺序表中元素存储位置的计算
2.5.2顺序表的特点
2.5.3顺序表的顺序存储表示
2.5.4多项式的顺序存储结构类型定义
2.5.5类C语言有关操作的补充
2.5.6顺序表的实现方式
2.5.7顺序表基本操作的实现 1线性表L的初始化(参数用引用)
2销毁线性表L
3清空线性表L
4 求线性表L的长度
5判断线性表是否为空
6顺序表的取值根据位置i获取相应位置数据元素的内容
7线性表的查找
8顺序表的插入 9顺序表的删除
2.6顺序表的特点 2.1线性表的类型定义
线性表是最常用且最简单的一种数据结构是一种典型的线性结构一个线性表是n个数据元素的有限序列。
线性表
——是数据元素是线性起点起始结点是线性终点终端结点。
是的直接前驱是的直接后继。
n为元素总个数即表长线性表的长度。n 0时为空表。
是第一个数据元素是最后一个数据元素是第i个数据元素i为数据元素在线性表中的位序。位序是从1开始的数组下标是从0开始的
除了第一个元素外每个元素有且仅有一个直接前趋除了最后一个元素外每个元素有且仅有一个直接后继。开始结点没有直接前驱仅有一个直接后继终端结点没有直接后继仅有一个直接前驱
同一个线性表中的元素必定具有相同特征数据元素之间的关系是线性关系。线性表中每个数据元素所占的空间是一样大的。
2.2线性表的计算
一元多项式的运算实现两个多项式加、减、乘运算 把一元多项式中的每个系数拿出来把他存成一个线性表每一项的指数用系数的下标来隐含的表示。此时系数的下标与指数相同P0常数项就是X的0次方P₁就是X的一次方
线性表每一项的指数i隐含在其系数的序号中
例一 用数组表示 线性表
稀疏多项式
例一 线性表
线性表A7,03,19,85,17线性表B8,122,7-9,8
求两个多项式的和
1创建一个新的数组C
2分别从头遍历比较a和b的每一项
指数相同对应的系数相加若其和不为零则在C中增加一个新项为零就不要了
指数不相同将指数较小的项复制到C中
3一个多项式已经遍历完毕时将另一个剩余项依次复制到C中即可
所以数组C 思路 1首先比较线性表A7,0和线性表B8,1看它们的指数 一个是0一个是101所以将线性表A的7,0放到数组C中0,7。此处线性表A7,0解决了不要了。 2因为线性表B8,1并没有被解决所以接着和线性表A3,1比较11指数相同系数相加3811然后放入到数组C中1,11。此处线性表A3,1和线性表B8,1都解决了就不要了。 3然后线性表A变成了9,8和线性表B22,7比较87指数不同将线性表B22,7放入到数组C中7,22。此处数组B22,7解决了不要了 4接着看线性表A9,8和线性表B-9,888系数相加9(-9)0所以线性表A9,8和线性表B-9,8都不要了 5此处线性表B已经没有了线性表A还剩一项5,17所以直接将线性表A5,17复制到数组C中17,5 所以数组C为 顺序存储结构存在的问题
1存储空间不灵活 2运算的空间复杂度高
法二链式存储结构 首先遍历这两个多项式A多项式第一个系数为0B多项式第一个系数为101,所以保留0次项
接着看A多项式第二个系数为1B多项式第一个系数为111,然后系数相加3811 接着看A多项式第三个系数为8B多项式第二个系数为778,所以保留这个7次项 接着看A多项式第三个系数为8B多项式第三个系数为888,然后系数相加9-90都不要 所以此方法并不需要额外空间
2.3抽象数据类型线性表的定义
ADT List{ 数据对象:D {| ∈ElemSet, i 1,2,...,n,n≥0} 数据关系:R1 { |∈D, i 1,2,...,n} 基本操作: InitList(L) 操作结果构造一个空的线性表L。 DestroyList(L) 初始条件线性表L已存在。 操作结果将L重置为空表。 .........
}ADT List
2.4线性表的基本操作
InitList(L) Initialization List初始化线性表 操作结果构造一个空的线性表L。分配内存空间
DestroyList(L) 删除 初始条件线性表L已存在。 操作结果销毁线性表L。(从内存中删除线性表释放空间
ClearList(L) 重置 初始条件线性表L已存在。 操作结果将L重置为空表。内存还有但是没有元素
ListEmpty(L) 判断线性表是否为空表,空表n0 初始条件线性表L已存在。 操作结果若L为空表则返回TRUE否则返回FALSE。
ListLength(L) 求线性表的长度线性表当中元素的个数 初始条件线性表L已存在。 操作结果返回L中数据元素个数。
GetElem(L, i, e) (获取线性表当中元素) 初始条件:线性表L已存在,1 ≤ i ≤ ListLength(L)。 操作结果:用e返回L中第i个数据元素的值。
LocateElem(Lecompare()) 查找、定位 初始条件:线性表L已存在,compare()是数据元素判定函数。 操作结果:返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在,则返回值为0。
PriorElem(Lcur_epre_e) 求一个元素的前趋 初始条件:线性表L已存在。 操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败pre_e无定义。
NextElem(Lcur_e,next_e) 获取一个元素的后继 初始条件:线性表L已存在。 操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否则操作失败,next_e无定义。
ListInsert(L,i,e) (插入元素) 初始条件:线性表L已存在,1 ≤ i ≤ ListLength(L) 1。 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1。 例:插入元素e之前长度为n 插入元素e之后长度为n1 此处是e的后继 ListDelete(L,ie) 删除元素 初始条件:线性表L已存在且非空,1 ≤ i ≤ ListLength(L)。 操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1。 例删除前长度为n 删除后长度为n-1 ListTraverse(L,visit()) 遍历线性表 初始条件:线性表L已存在。 操作结果:依次对L的每个数据元素调用函数visit()。一旦visit()失败,则操作失败
PrintListL输出按照前后顺序输出线性表L的所有元素值。
2.5线性表的顺序表示和实现
线性表的顺序表示顺序存储结构或顺序映象。
线性表的顺序表示指的是用同一组地址连续的存储单元依次存储线性表的数据元素。
顺序存储定义把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
线性表是一种逻辑结构
线性表中第一个元素没有前驱最后一个元素没有后继除了第一个元素和最后一个元素其他元素有且仅有一个前驱和一个后继。线性表中第一个数据元素a1的存储位置称作线性表的起始位置或基地址首地址。
逻辑上相邻的元素在物理位置上也是相邻的。
例如线性表1,2,3,4,5,6的存储结构 是一个典型的线性表顺序存储结构。依次存储地址连续——中间没有空出存储单元
地址不连续——中间存在空的存储单元。不是一个线性表顺序存储结构。
线性表顺序存储结构占用一片连续的存储空间。知道某个元素的存储位置就可以计算其他元素的存储位置。
2.5.1顺序表中元素存储位置的计算
例如果每个元素占用8个存储单元存储位置是2000单元则 存储位置是 已知每个元素占8个存储单元所以占用2000~2007这8个存储单元则是从2008开始存储的。 假设线性表的每个元素需占个存储单元并以所占的第一个单元的存储地址作为数据元素的存储位置。则第个数据元素的存储位置和第 个数据元素的存储位置之间满足关系
线性表的第 i 个数据元素的存储位置为 与数学中的等差数列相似LOC是location的缩写。设线性表中第一个元素的存储位置是LOCL第二个元素的存储位置为LOCL数据元素的大小第三个为LOCL2 * 数据元素的大小 线性表顺序存储结构的图示
此图中的b也可以写成
2.5.2顺序表的特点
以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。任意元素均可随机存取优点
2.5.3顺序表的顺序存储表示 线性表的长度是可以变的删除 一位数组的定义方式 类型说明符 数组名[常量表达式] 说明常量表达式中可包含常量和符号常量不能包含变量。即C语言中不允许对数组的大小作动态定义 顺序表的定义模版
#define LIST_INIT_SIZE 10 //线性表存储空间的初试分配量定义一个整型常量值为100
typedef struct{ElemType elem[LIST_INIT_SIZE]; //用静态的“数组”存放数据元素int length; //顺序表的当前长度
}SqList; //顺序表的类型定义静态分配方式
2.5.4多项式的顺序存储结构类型定义 线性表
#define MAXSIZE 1000 //多项式可能达到的最大长度typedef struct{ //多项式非零项的定义float p; //系数int e; //指数
}Polynomial; //Polynomial多项式typedef struct{Polynomialp *elem; //存储空间的基地址int length; //多项式中当前项的个数
}SqList; //多项式的顺序存储结构类型为SqList例图书表的顺序存储结构类型定义 #define MAXSIZE 1000 //图书表可能达到的最大长度typedef struct{ //图书信息定义char no[20]; //图书ISBNchar name[50]; //图书名字float p; //图书价格
}Book; typedef struct{Book *elem; //存储空间的基地址int length; //图书表当前图书个数
}SqList; //图书表的顺序存储结构类型为SqList2.5.5类C语言有关操作的补充
一补充元素类型说明
顺序表类型定义
typedef struct{ElemType data[]; int length;
}SqList; //顺序表类型 ElemType可以是任意类型也可以是自定义的结构体类型即结构体数组 。 ElemType的含义“数据元素的类型”是一个抽象的概念是表示我们所要使用的数据元素应有的类型。ElemType的默认是int型。可以用typedef重定义你想要的类型。 在C语言中ElemType表示数据元素类型的通用数据类型可以根据具体需要定义 例typedef char ElemType;// 定义ElemType为char类型 typedef int ElemType;//定义ElemType为int类型 在数组中可以用ElemType类型定义每个元素的数据类型 typedef int ElemType;
ElemType arr[10]; 在链表中我们通常会定义一个节点结构包含一个数据域和一个指向下一节点的指针。 typedef struct node{ElemType data;struct node*next;
}Node;定义了一个Node的结构其中的数据域data的类型为ElemType表示节点存储的数据类型。 如果是一个复杂的部分若一个元素包含两个部分可以定义一个结构类型它包括一个实型的系数一个整型的指数。例 typedef struct{ //多项式非零项的定义float p; //系数int e; //指数
}Polynomial; //Polynomial多项式typedef struct{Polynomialp *elem; //存储空间的基地址int length; //多项式中当前项的个数
}SqList; //多项式的顺序存储结构类型为SqList*elem代表数组elem中第一个元素的地址 SqListSq: sequence——顺序序列 二补充C的动态存储分配
new 类型名T(初值列表)功能申请用于存放T类型对象的内存空间并依初值列表赋以初值结果值成功T类型的指针指向新分配的内存失败0(NULL)
例int *p1 new int; 或int *p1 new int(10);
delete 指针P
功能释放指针P所指向的内存。P必须是new操作的返回值 三补充C中的参数传递
函数调用时传送给形参表的实参必须与形参三个一致类型、个数、顺序
参数传递的两种方式
①传值方式参数为整型、实型、字符型等
②传地址参数为指针变量 参数为引用类型 参数为数组名 地址也是值只不过给了指针变量指针变量可以指向地址值对应的存储空间。 第一种传入a传入a的地址 第二种传入a本身 第三张数组名就是一个地址直接传入数组名a 传值方式
把实参的值传送给函数局部工作区相应的副本中函数使用这个副本执行必要的功能。函数修改的是副本的值实参的值不变。 cin 对应scanf()输入a和b的值 cout 对应printf()输出a和b的值 endl换行 例如a3b5将a的值传给mb的值传给n m3,n5 对m和n进行交换m5n3 改变了m和n 的值 传地址方式——指针变量作形参
形参变化影响实参 *m解引用 分析定义了两个指针p1和p2p1指向ap2指向b然后将两个指针p1和p2作为参数实参传递。假如a3b5p1存的a的地址p2存的b的地址具体多少不知道所以画一个箭头表示指向它这就是指针的由来存放地址的变量叫指针。然后开始调用函数将p1和p2作为参数传递把p1的值传给了mp2的值传给n。因为p1的值是a 的地址所以m也存放a的地址也指向a。p2里面存放的是b的地址所以n里面也存放b的地址也指向b。定义了一个实型变量交换的是他们的内容此处的*m是运算是取指针变量的内容m指针变量的内容就是a的这个变量交换的是m指针所指的变量和n指针所指的这个变量。交换了a变量和b变量的值所以a变成了5b变成了3。交换完成函数执行完毕形参被释放m和n就没有了执行完返回调用的地方输出a和b的值此处a和b的值发生了变化 形参变化不影响实参 分析a和m指向一个地方b和n指向一个地方交换mn和ab无关。这里是将声明的局部变量指针m、n的地址进行了交换而并没有将真正的指针p1、p2进行交换。m、n释放掉后就没得了所以实质上a和b的值压根没有任何变化。 传地址方式——数组名作参数
传递的是数组的首地址对形参数组所做的任何改变都将反映到实参数组中。 传地址方式——引用类型作参数
引用用来给一个对象提供一个替代的名字。 j是一个引用类型代表i的一个替代名。i值改变时j值也跟着改变所以会输出i7j7。 对引用的理解i是你的本名j是你的小名所以对i本名的操作和对j小名的操作相同。 在C是取地址符在C是引用替代名字在数据结构是返回参数。 右边代码的意思是这个函数传入了什么左边这个代码的意思是这个函数内部发生了什么。有个比较形象的比喻a就是一个人的名字而m就是他的小名 。 分析在实参里面输入了ab定义了两个引用型的m是对a的引用n是对b的引用。m和a用的是同一块空间n和b用的是同一块空间。所以对m的任何操作实际上都是对a的操作。此处交换了m和n的值实际上也就是交换了a和b的值。对mn的操作就相当于对形参的操作相当于对实参的操作。 引用类型作形参的三点说明
1传递引用给函数与传递指针的效果是一样的形参变化实参也发生变化
2引用类型作形参在内存中并没有产生实参的副本它直接对实参操作。而一般变量作参数形参与实参就占用不同的存储单元所以形参变量的值是实参变量的副本。因此当参数传递的数据量较大时用引用比用一般变量传递参数的时间和空间效率都好。
3指针参数虽然也能达到与使用引用的效果但在被调函数中需要重复使用“*指针变量名”的形式进行运算这很容易产生错误且程序的阅读性差;另一方面在主调函数的调用点处必须用变量的地址作为实参。 这个 * 代表 解引用操作也就是地址中存储的值。 单独的星号加指针变量名本质是内容值而类型名加星号加指针变量名本质是地址。 引用不是指针常量指针常量本身还要占用空间引用没有。 2.5.6顺序表的实现方式 逻辑位序和物理位序相差1 一静态分配
#define MaxSize 10 //定义最大长度
typedef struct{ElemType data[MaxSize]; //用静态的“数组”存放数据元素int length; //顺序表的当前长度
}SqList; //顺序表的类型定义静态分配方式 存储空间是静态的顺序表的表长一旦确定无法修改所以数组满了直接放弃。 二动态分配
#define MaxSize 10 //顺序表的初始长度
typedef struct{ElemType *data; //指示动态分配数组的指针int MaxSize //顺序表的最大容量int length; //顺序表的当前长度
}SeqList; //顺序表的类型定义动态分配方式 data[MaxSize]和*data都是定义一个数组data[MaxSize]是静态分配*data是动态分配 data[MaxSize这里的data有三种意思首地址地址常量data【0】 当我们访问第一个元素时可以使用a[0]也可以使用*a或者*a0 数组名是指针变量指针是地址指针变量是存放指针的空间数组名存放的是数组地址。 此处data的内存大小为 SqList L;
L.data(ElemType*)malloc(sizeof(ElemType)*MaxSize); 第一个是*指针指的是首地址。第二个*不是指针是相乘意思是分配MaxSize个ElemType类型的空间 由于malloc返回的是void*所以需要强制转换才行。(ElemType*)强制类型转换表示强制转换为一个指向ElemType形的指针 一malloc(m)函数开辟m字节长度的地址空间并返回这段空间的首地址。 malloc函数会申请一整片连续的存储空间。malloc函数返回一个指针需要强制转换为你定义的数组元素类型指针。malloc函数的参数指明要分配多大的连续内存空间。 二sizeof(x)运算计算变量x的长度。 三free(p)函数释放指针p所指变量的存储空间即彻底删除一个变量。 free释放的是空间而不是释放指针因此释放空间后还需要将指针置为NULL 动态开辟的空间记得free 需要加载头文件stdlib.h C 的初始动态分配语句为
L.data(ElemType*)malloc(sizeof(ElemType)*Initsize);
C的初始动态分配语句为
L.datanew ElemType[InitSize]; 注动态分配并不是链式存储它同样属于顺序存储结构物理结构没有变化依然是随机存取方式只是分配的空间大小可以在运行时动态决定。 顺序表示意图 SqList L; //定义变量LL是SqList这种类型的L是个顺序表
例如int a; //定义变量aa是int型 定义变量L改变成员变量L.length L是指针时*L改变成员变量用L-length 这里如果换成了*L要用malloc分配一下这个结构体的空间 注意L-elem(*L).elem 2.5.7顺序表基本操作的实现
线性表的基本操作 补充操作算法中用到的预定义常量和类型
//函数结果状态代码
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status是函数的类型其值是函数结果状态的代码
typedef int Status;
typedef char ElemType; 1线性表L的初始化(参数用引用)
Status InitList_Sq(SqList L){ //构造一个空的顺序表LL.elemnew ElemType[MAXSIZE]; //为顺序表分配空间if(!L.elem) exit(OVERFLOW);//存储分配失败L.length0; //空表长度为0return Ok;
} new表示动态分配空间即空间可伸缩 这个函数是初始化线性表1.给数组分配空间并检测分配是否成功 2.为长度赋值为0 if(!L.elem):这是一个条件语句检查线性表L中的elem’成员是否为NULL或者未分配。’!是逻辑非运算符所以’!L.elem”的意思是如果L.elem为NULL或者未分配条件成立。 c的写法是(elem type*)malloc(sizeof(elemtype)*maxsize; 2销毁线性表L
void DestroyList(SqList L){if(L.elem) delete L.elem;//释放存储空间
} 销毁从内存中将L占用的空间释放 前提条件有空间才才释放没有空间不需要释放 if(L.elem) delete L.elem如果这个线性表存在然后将他删除掉线性表L将不再存在。 3清空线性表L
vold ClearList(SqList L){L.length0; //将线性表的长度置为0
} 这个就属于逻辑上的清空让之前的数据找不到了就叫做清空。 逻辑清空假装已经清空了只要把长度变成0那么后面的访问超出范围就会主动拒绝掉。 4 求线性表L的长度
int GetLength(SqList L){return (L.length);
} 这里可以加这样当列表很大时可以节约开辟副本的时间和空间。 5判断线性表是否为空
int IsEmpty(SqList L){
if (L.length0) return 1;
else return 0;
} if (L.length0)判断线性表是否为空如果是空的则返回1不是空的返回0 6顺序表的取值根据位置i获取相应位置数据元素的内容
int GetElem(SqList L,int i,ElemType e){if (i1||iL.length) return ERROR;//判断i值是否合理若不合理返回ERROReL.elem[i-1];//第i-1的单元存储着第i个数据return Ok;
} 不引用是因为不需要修改牢记一点是否需要对这个数据进行修改不需要修改那么不需要引用。 只要记住引用的目的是修改这个数据不修改就不引用这个要点可以解答你所有有关“为什么为什么不”的问题 i是需要获取第i个元素e代表要取出的元素这里用引用直接会修改传入的变量e 这里i是位序逻辑位序物理位序的话是数组的下标差了1所以逻辑上的i实际上是数组里的i-1 判断里是逻辑序号1,2,...,length, e的赋值语句里是物理序号0,1,,...,length-1,也可以把判断换成i0||iL.length-1 因为每个语句只执行一次此处的时间复杂度为常量阶O(1) 线性表的常用的两种储存结构顺序存储结构顺序表和链式存储结构链表 7线性表的查找
1在线性表L中查找与指定值e相同的数据元素的位置
2从表的一端开始逐个进行记录的关键字和给定值的比较。如果找到返回该元素的位置序号未找到返回0。
int LocateELem(SqList L, ElemType e){
//在线性表L中查找值为e的数据元素返回其序号(是第几个元素for (i0;i L.length;i)if(L.elem[i]e) return i1; //查找成功返回序号return 0; //查找失败返回0
} 这里面elem如果是自定义类型是不可以做相等判断的需要重载 l.length就是元素的个数因为下标从0开始所以i0从0开始查找 i是对比数组里下标为i的数数组的实际使用个数l.length但是下标是length-1. 此算法的执行次数最多的语句是 if(L.elem[i]e) return i1; 时间复杂度O(n) int LocateELem(SqList L, ElemType e){
//在线性表L中查找值为e的数据元素返回其序号(是第几个元素while (i L.lengthL.elem[i]!e) i;if(iL.length) return i1; //查找成功返回序号return 0; //查找失败返回0
}
顺序表的查找分析
因为查找算法的基本操作为:将记录的关键字同给定值进行比较
基本操作:L.elem[i] e 比较次数ea1次eb2次ec3次......eg7次
平均查找次数1234567/7 4次 首相加末项/217/2
最好情况查找的元素就在表头仅需比较一次时间复杂度为O(1)。 最坏情况查找的元素在表尾(或不存在)时需要比较n次时间复杂度为O(n)
平均查找长度ASLAverage Search Length
为确定记录在表中的位置需要与给定值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度。
对含有n个记录的表查找成功时
Pi第i个记录被查找的概率 Ci找到第i个记录需比较的的次数
顺序查找的平均查找长度
假设每个记录的查找概率相等则 假如,则 8顺序表的插入
线性表的插入运算是指在表的第 i (1≤in(L.length)1)个位置上插入一个新结点(元素) e使长度为n(L.length)的线性表(a1,… ai -1,ai,… an)变成长度为n1(L.length1) 的线性表(a1, .. ai -1,e, ai,an)。
算法思想①判断插入位置i 是否合法。 ②判断顺序表的存储空间是否已满若已满返回ERROR。 ③将第n至第ì 位的元素依次向后移动一个位置空出第i个位置 ④将要插入的新元素e放入第i个位置。 ⑤表长加1插入成功返回OK。
Status ListInsert_Sq(SqList L,int i ,ElemType e){if(i 1 || i L.Length1)return ERROR; //i值不合法if(L.length MAXSIZE) return ERROR; //当前存储空间已满for(j L.length-1; j i-1; j--)L.elem[j1]L.elem[j]; //插入位置及之后的元素后移L.elem[i-1]e; //将新元素e放入第i个位置L.length; //表长增1return OK;
}if(i 1 || i L.Length1)return ERROR判断i的范围是否有效i只能在1~L.length1的范围如果i不在规定范围i1或i L.Length1则返回error。注意这里的i是位序 不是组数下标 if(L.length MAXSIZE) return ERROR判断当前的存储空间是否已满L.length MAXSIZE当前存储空间已满不能插入则返回error for(j L.length-1; j i-1; j--) L.elem[j1]L.elem[j]; j是数组下标将第i个元素及之后的元素后移将下标为j的元素放入到j1 p要小于等于n1就是只能紧贴着原数组的最后一个元素去插入因为线性表规定所有元素必须紧挨在一起不能出现空一个的情况 算法时间主要耗费在移动元素的操作上 若插入在尾结点之后则根本无需移动(特别快) 时间复杂度O(1)
若插入在首结点之前则表中元素全部后移(特别慢) 时间复杂度O(n)
若要考虑在各种位置插入(共n1种可能)的平均移动次数该如何计算? ixn1xn1-i i是第几个位置x是移动次数 i~n总共移动x次也就是总共x个元素移动后i~n下标变成i1~n1所以前面i个元素与后面x个元素的和为n1。 i是位序插到第几位n是下标x是移动次数例数组有5个元素把新元素添插在最后就是第6代入公式6051。 再来一个理解方法n1是插入新元素数组的最后一个位置i是插入元素的位置移动次数就是[最后-当前][n1-i] 设pi代表在第i个位置上插入一个结点的概率那么pi1/(n1)所以在长度为n个结点的顺序表中插入结点时所需要移动的平均次数可以这样表示· 顺序表插入算法的平均时间复杂度O(n) 插入不同位置的算法演示
插入位置在最后
插入位置在中间 实际操作的时候, 先判断数组是否满, 满就返回错误。然后如果是在中间插入, 当然需要挪元素, 需要挪最后一个元素,最后一个元素的位序是 length-1 , 然后挪到length的位置 插入位置在最前面 可以遍历整一个逆序的数组然后在最后面插入一个元素然后再遍历逆序一下回到原来的数组 9顺序表的删除
线性表的删除运算是指将表的第 i (1 ≤ i ≤ n(L.length) )个结点删除
使长度为n 的线性表
变成长度为n-1的线性表
算法思想:①判断删除位置i 是否合法(合法值为1≤i≤n)。不合法则返回ERROR ②将欲删除的元素保留在e中。 ③将第i1至第n 位的元素依次向前移动一个位置。 ④表长减1删除成功返回OK。
Status ListDelete_Sq(SqList L,int i){if((i 1)||(i L.length)) return ERROR; //i值不合法for (j i;j L.length-1; j ) L.elem[j-1 ] L.elem[j]; //被删除元素之后的元素前移 L.length- -; //表长减1return OK;
} Status ListDelete_Sq(SqList L,int i)在线性表L上面删除第i个位置上的元素删除的结果仍由线性表L保存 if((i 1)||(i L.length)) return ERROR判断删除位置是否合法如果是小于1或大于L.length则不合法返回ERROR位置合法进行下一步。L.length就是元素的个数。 for (j i;j L.length-1; j ) 从删除的元素i的后继开始一直到最后一个元素L.length。 L.length个元素在L.length-1的位置存储。 L.elem[j-1 ] L.elem[j]将后面一个元素赋值到前一个位置 i理解为位置j是下标i位置是(1n)j对应下标是(0n-1)所以删第i个位置就是删下标i-1。这里是j等于i是指位置序号不是数组下标 这里包括前面的代码都是删除指定位置的元素而不是指定索引的元素。 算法时间主要耗费在移动元素的操作上: 若删除尾结点则根本无需移动(特别快); 时间复杂度O(1) 若删除首结点则表中n-1个元素全部前移(特别慢); 时间复杂度O(n) 若要考虑在各种位置删除(共n种可能)的平均移动次数该如何计算? i1,2,3,...n x(次数)n-1n-2...0 i和x的关系n-i 将移动次数相加((n-1) (n-2)...(0)) / n 顺序表删除算法的平均时间复杂度为O(n)
2.6顺序表的特点
(1)利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系即线性表的逻辑结构与存储结构一致。 (2)在访问线性表时可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为访问每个元素所花时间相等。 这种存取元素的方法被称为随机存取法。
时间复杂度查找、插入、删除算法的平均时间复杂度为O(n)
空间复杂度顺序表操作算法的空间复杂度S(n) O(1) 没有占用辅助空间
顺序表的优缺点
优点 存储密度大结点本身所占存储量 / 结点结构所占存储量可以随机存取表中任一元素 结点本身所占存储量 / 结点结构所占存储量 1 是密度最大的情况 这里的存储密度应该是指而顺序表是不用存放别的东西比如说地址、前驱、后继之类的它的整个存储空间指存放这个数据就只用存放数据所以因为只用存放数据不用存放别的所以存储密度大达到了1。但是在整个顺序表中为了存放所有的元素令他不会溢出我们设定的这个数组往往很大所以整个空间是需要多的。这是存储空间的浪费 缺点 在插入、删除某一元素时需要移动大量元素浪费存储空间属于静态存储形式数据元素的个数不能自由扩充
通过链表可以克服顺序表的缺点 。
