01-数据结构实用概念专题讲座


数结构基概念专题讲座
数结构实概念
疑惑
1学完C语言现感觉写出代码
2什会种样程序存？
3程序质什？
程序具体问题存
程序需围绕问题解决进行设计
问题种解决方案
追求程序性价？
否量化方法判程序坏？
数结构起源
计算机解决数值计算问题解决生活中问题
现实生活中问题涉体间复杂联系
需计算机程序中描述生活中体间联系
数结构研究非数值计算程序问题中操作象间关系
研究复杂算法
数结构中基概念
数 – 程序操作象描述客观事物
数特点：
输入计算机
计算机程序处理
数抽象概念进行分类程序设计语言中类型：intfloatchar等等
数元素：组成数基单位
数项：数元素干数项组成
数象 – 性质相数元素集合

王保明提醒结构体课堂代码
声明结构体类型
struct _MyTeacher 种数类型
{
char name[32]
char tile[32]
int age
char addr[128]
}

int main21()
{
struct _MyTeacher t1 数元素
struct _MyTeacher tArray[30] 数象
memset(&t1 0 sizeof(t1))

strcpy(t1name name) 数项
strcpy(t1addr addr) 数项
strcpy(t1tile addr) 数项
t1age 1
}

数元素间独立存特定关系关系结构
数结构指数象中数元素间关系
：数组中元素间存固定线性关系
编写程序前必须分析处理问题中象特性象间关系
基概念总结：

数逻辑结构
指数元素间逻辑关系逻辑关系描述数数存储关独立计算机逻辑结构细分4类：

数物理结构


数运算

算法
算法概念
算法特定问题求解步骤描述
计算机中表现指令限序列
算法独立存种解决问题方法思想
算法言语言重重思想

算法数结构区
数结构静态描述数元素间关系
高效程序需数结构基础设计选择算法
è程序数结构+算法
总结：
算法解决实际问题设计
数结构算法需处理问题载体
数结构算法相辅相成
算法特性
输入
算法具0输入
输出
算法少1输出
穷性
算法限步骤会动结束会限循环
确定性
算法中步确定含义会出现二义性
行性
算法步行
算法效率度量
1事统计法
较算法组输入数运行处理时间
缺陷
获算法运行时间必须编写相应程序
运行时间严重赖硬件运行时环境素
算法测试数选取相困难
事统计法然直观实施困难缺陷
算法效率度量
事前分析估算
统计方法算法效率进行估算
影响算法效率素
算法采策略方法
问题输入规模
编译器产生代码
计算机执行速度
long sum1(int n)
{
long ret 0
int* array (int*)malloc(n * sizeof(int))
int i 0

for(i0 i {
array[i] i + 1
}

for(i0 i {
ret + array[i]
}

free(array)

return ret
}

long sum2(int n)
{
long ret 0
int i 0

for(i1 i {
ret + i
}

return ret
}

long sum3(int n)
{
long ret 0

if( n > 0 )
{
ret (1 + n) * n 2
}

return ret
}

int main()
{
printf(d＼n sum1(100))
printf(d＼n sum2(100))
printf(d＼n sum3(100))

return 0
}

int func(int a[] int len)
{
int i 0
int j 0
int s 0

for(i0 i {
for(j0 j {
s + i*j n*n
}
}
return s
}
n*n

注意1：判断算法效率时需关注操作数量高次项次项常数项忽略
注意2：没特殊说明时分析算法时间复杂度指坏时间复杂度

2O表示法
算法效率严重赖操作(Operation)数量
判断时首先关注操作数量高次项
操作数量估算作时间复杂度估算
O(5) O(1)
O(2n + 1) O(2n) O(n)
O(n2+ n + 1) O(n2)
O(3n3+1) O(3n3) O(n3)
常见时间复杂度

关系



3算法空间复杂度
算法空间复杂度通计算算法存储空间实现
S(n) O(f(n))
中n问题规模f(n))问题规模nn时占存储空间函数
O表示法样适算法空间复杂度
算法执行时需空间常数时空间复杂度O(1)
空间时间策略
数情况算法执行时时间更令关注
果必通增加空间复杂度降低时间复杂度
理通增加时间复杂度降低空间复杂度
练1：分析sum1 sum2 sum3函数空间复杂度
O(4n+12) O(8)O(1) O(4)O(1)
总结：实现算法时需分析具体问题执行时间空间求

练2：时间换空间
*
问题： 666
然数11000中某数字组成数组中数字出现零次者次
设计算法找出出现次数数字
*
方法1：
排序然找出出现次数数字

方法2：
void search(int a[] int len)
{
int sp[1000] {0}
int i 0
int max 0

for(i0 i {
int index a[i] 1

sp[index]++
}

for(i0 i<1000 i++)
{
if( max < sp[i] )
{
max sp[i]
}
}

for(i0 i<1000 i++)
{
if( max sp[i] )
{
printf(d＼n i+1)
}
}
}

int main()
{
int array[] {1 1 3 4 5 6 6 6 2 3}

search(array sizeof(array)sizeof(*array))

return 0
}


文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档