Tauruser

Enjoy Every Day
posts - 34, comments - 95, trackbacks - 0, articles - 5
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

简单的数据结构



  几何上的学习从点,到线,到面。而在数据结构上,就从最简单的线性结构开始。

2、1线性结构 从逻辑上来看是线性关系
   每一个节点都有一个唯一的前驱也后继,节点之间有先后的之分。
一些对应的中英文:
   linear list 线性表    predecesser 直接前驱 successor 直接后继

基本概念有:
①结点
②典型的存储方式:顺序存储即物理与逻辑顺序一致
③基本运算
 ⑴取
 ⑵修改
 ⑶插入
 ⑷删除
 ⑸排序
 ⑹查找
 ⑺测试
其中⑶⑷主要涉及空间的重新组织,⑸⑹主要涉及时间复杂度问题。

关于插入与删除的算法,将在数据结构的实验中谈到。

④算法复杂度估计(关键在于计算基本运算进行的次数)

算法复杂度估计基于假设:插入和删除的位置是随机的。即任意位置上发生的可能性一致。
通过概率与统计学的知识,可以求出基本运算的平均运行次数。这就是算法复杂度的计算。
一般情况,都可以把一些循环语句中的语句作为基本运算。(我自己的见解)

数组方式实现的线性表有不足,可通过用目录表的形式加以克服。

将结点的序号存储在顺序表中,而结点的内容则可用各种方式随机存储,既可解决存储空间的分散性问题,也可以实现快速查找。

Feedback

# re: 我的算法与数据结构学习(二)   回复  更多评论   

2006-03-22 18:15 by new apple
突然间发现还有这个东东,写得很好啊,以后我会关注你的,也当作是复习!

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理