C语言软件基础部分知识点.doc

数据结构的基础知识内容

:
1).数据元素之间的逻辑关系是什么?
2).适宜选用什么样的存储结构?
3).采用什么样的操作实现算法效率更高?
.
1)线性结构:线性结构的逻辑特征是:.
2)非线性结构:非线性结构的逻辑特征是:,在图结构中,任何数据元素的直接前趋和直接后继的人数都不作限制,在非线性结构中有一类较特殊的结构,我们称为树结构,它的逻辑特征是:所有数据元素(除根元素)都存在一条从根元素到该元素的路径.
,数据的存储结构图:有时它称为数据的物理结构,:
1).顺序存储方法:该方法是把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里,,如线性表,.
2).链接存储方法:该方法不要求逻辑上相邻的元素其物理位置上亦相邻,元素间的逻辑关系是由附加的指针字段表示的,由此得到的存储表称为链式存储结构,链式存储结构要借助于程序结构的指针类型来描述元素的存储地址,即在此存储方法中,每个数据元素所占存储单元分成两部分:一部分为元素本身数据项; 而另一部分为指针项,指出其后继前趋元素的存储地址,从而形成一个链.
3).索引存储方法:该方法通常是在存储元素信息的同时,还建立附加的索引表,索引表中的每一项称为索引项,索引项的一般形式是:关键字,地址。,则该索引位置称为稠密索引();若一级元素在索引表中只对应一个索引项,则该索引位置称稀疏索引(),稠密索引中索引项的地址指示元素所在存储位置,而稀疏索引中索引项的地址则指示一级元素的起始存储位置.
4).散列存储方法:,-----地址转移法.
,并以适当的方法存储在计算机系统的存储器里,其最终目的是有效处理数据,提高数据处理的运算速度.
在数据结构中,要讨论的常用数据处理与运算有下列几种:
1).遍历:在数据结构的各个元素移动,或查看所有数据元素.
2).插入:往数据结构中加新的元素.
3).更新:修改或替代数据结构中指定元素的一个或多个数据项(字段值).
4).删除:把指定的数据元素从数据结构中去掉.
5).查找:在数据结构中查找满足一定条件的数据元素.
6).排序:在数据结构中数据元素个数不变的前提下,.
线性结构
:

.正如上一节所述:线性结构的逻辑特征是在其结构中,有且仅有一个无直接前趋而仅有一个直接后继的数据元素为起始元素:有且仅有一个无直接后继而仅有一个直接前趋的数据元素为终点元素:其余均为内部元素,,线性结构的数据元素可排成一个线性的序列:
A1,a2,……an
其中,a1为起始元素,an为终点元素,ai为索引号为i的数据元素.
:
线性结构有各种类型,如线性表,堆栈,队列,数组,串等.
(一)线性表:线性表是n(n0)个相同类型的元素a1,a2,……an所构成的有限线性序列,通常表示为(a1,a2,……an),(1in),:一个整数序列:(1,12,123,1234,321,21,22)是一个线性表,表中元素ai是一个整数,表长为7.
线性表有两种存储方式,对应地把线性表分成了两类:顺序存储结构的顺序表和链式存储结构的链表.
(1).顺序表:
顺序表:在顺序表的存储结构中,数据元素按其逻辑次序集中存放在地址连续的存储单