夜雨聆风学习资料网 资料列表 开通 VIP 用登录 / 注册 ⌄
PDF

2.2.2_2_顺序表的查找_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表

查看资料信息、公开预览和下载状态。

共 13 页PDF · 611.0KB
下载

文档在线预览

公开展示前 7 页
100%
1
《2.2.2_2_顺序表的查找_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表》第1页预览
2
《2.2.2_2_顺序表的查找_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表》第2页预览
3
《2.2.2_2_顺序表的查找_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表》第3页预览
4
《2.2.2_2_顺序表的查找_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表》第4页预览
5
《2.2.2_2_顺序表的查找_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表》第5页预览
6
《2.2.2_2_顺序表的查找_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表》第6页预览
7
《2.2.2_2_顺序表的查找_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表》第7页预览

本文档共 13 页 剩余 6 页未展示,请下载后查阅

下载

文档文本内容

本节内容
顺序表
查找
王道考研/CSKAOYAN.COM知识总览
王道考研/CSKAOYAN.COM顺序表的按位查找
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];
}
王道考研/CSKAOYAN.COM顺序表的按位查找
GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。
#define InitSize 10 //顺序表的初始长度
typedef struct{
动态分配
ElemType *data; //指示动态分配数组的指针
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
} SeqList; //顺序表的类型定义(动态分配方式)
ElemType GetElem(SeqList L, int i){ 和访问普通数
return L.data[i-1]; 组的方法一样
}
如果一个 ElemType 占 6B,即 sizeof(ElemType)==6
ElemType *data
指针 data 指向的地址为 2000
内存
……
data[0] data[1] data[2]
(从2000开始的6B)(从2006开始的6B)(从2012开始的6B) 王道考研/CSKAOYAN.COM顺序表的按位查找
GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。
#define InitSize 10 //顺序表的初始长度
typedef struct{
动态分配
ElemType *data; //指示动态分配数组的指针
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
} SeqList; //顺序表的类型定义(动态分配方式)
ElemType GetElem(SeqList L, int i){ 和访问普通数
return L.data[i-1]; 组的方法一样
}
如果换一个类
int *p
型的指针,指
p[0] p[1] p[2] p[4] …… (注:一个int 占4B)
向同一个地址
内存
……
data[0] data[1] data[2]
(从2000开始的6B)(从2006开始的6B)(从2012开始的6B) 王道考研/CSKAOYAN.COM顺序表的按位查找
int *p
p[0] p[1] p[2] p[4] …… (注:一个int 占4B)
内存
……
data[0] data[1] data[2]
ElemType *data
再次理解,为何malloc函数返回的
存储空间起始地址要转换为与数
据元素的数据类型相对应的指针
王道考研/CSKAOYAN.COM按位查找的时间复杂度
内存
……
data[0] data[1] data[2]
ElemType *data
ElemType GetElem(SeqList L, int i){
return L.data[i-1];
}
由于顺序表的各个数据元素在内存中连续存放,
因此可以根据起始地址和数据元素大小立即找到
O(1)
时间复杂度: 第 i 个元素——“随机存取”特性
王道考研/CSKAOYAN.COM顺序表的按值查找
LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。
#define InitSize 10 //顺序表的初始长度
typedef struct{
ElemType *data; //指示动态分配数组的指针
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
} SeqList; //顺序表的类型定义(动态分配方式)
//在顺序表L中查找第一个元素值等于e的元素,并返回其位序
int LocateElem(SeqList 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; //退出循环,说明查找失败
}
王道考研/CSKAOYAN.COM内存
顺序表的按值查找
L.data
i=0 6data[0]
LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。 i=1 2data[1]
i=2 9data[2]
typedef struct{
4data[3]
int *data; //指示动态分配数组的指针
9data[4]
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度 3data[5]
}SeqList;
data[6]
data[7]
//在顺序表L中查找第一个元素值等于e的元素,并返回其位序
data[8]
int LocateElem(SeqList L,int e){
data[9]
for(int i=0;i<L.length;i++)
if(L.data[i]==e) length
= 6
基本数据类型:int、char、double、
i+1=3 return i+1;
float 等可以直接用运算符“==”比较
return 0;
}
结构类型的数据元素也这样吗?
调用:LocateElem(L, 9);
王道考研/CSKAOYAN.COM结构类型的比较
更好的办法:定义一个函数,童叟无欺,用过都说好
注意:C语言中,结构体的比较不能直接用 “== ”
需要依次对比各个分量来
判断两个结构体是否相等
王道考研/CSKAOYAN.COM顺序表的按值查找
LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。
//在顺序表L中查找第一个元素值等于e的元素,并返回其位序
int LocateElem(SeqList 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; //退出循环,说明查找失败
}
Tips:
《数据结构》考研初试中,手写代码可以直接用“==”,无论 ElemType 是基本数据类型还是
结构类型
手写代码主要考察学生是否能理解算法思想,不会严格要求代码完全可运行
有的学校考《C语言程序设计》,那么…也许就要语法严格一些
王道考研/CSKAOYAN.COM按值查找的时间复杂度
//在顺序表L中查找第一个元素值等于e的元素,并返回其位序
int LocateElem(SeqList L,ElemType e){
for(int i=0;i<L.length;i++)
if(L.data[i]==e)
关注最深层循环语句的执行
return i+1; //数组下标为i的元素值等于e,返回其位序i+1
次数与问题规模 n 的关系
return 0; //退出循环,说明查找失败
}
问题规模 n = L.length (表长)
最好情况:目标元素在表头
循环1次;最好时间复杂度 = O(1)
最坏情况:目标元素在表尾
循环 n 次;最坏时间复杂度 = O(n);
!
平均情况:假设目标元素出现在任何一个位置的概率相同,都是
"
目标元素在第1位,循环1次;在第2位,循环2次;…… ;在第 n 位,循环 n 次
! ! ! ! #(#%!) ! #%!
平均循环次数 = 1⋅ + 2 ⋅ + 3 ⋅ + …… + n ⋅ = = 平均时间复杂度 = O(n)
" " " " ' " '
王道考研/CSKAOYAN.COM知识回顾与重要考点
王道考研/CSKAOYAN.COM