软件技术基础数 据结 构1.ppt

《软件技术基础数 据结 构1.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、软件技术基础软件技术基础数据结构一、数据结构的基本概念现实事物如气候、人信息（表征现实事物）如气温、姓名数据（信息的载体）如25ºC、张三数据结构（数据在计算机中的存储形式及相互关系）注意：数据≠数值65706667960131王五585928893960131李四487908891960131张三390968180960131马二284969097960131丁一1C语言电路分析物理数学班级姓名学号学生成绩表数据结构举例每一行为一个数据元素，也称为数据结点或记录每一列为一个数据项或称为字段数据元素的C语言类型可

2、定义如下:typedefstructstudent{intid;charname[20];intclasses;floatscore[4];}elemtype;可以用该类型来定义数据元素变量:elemtypestu1,stu2,stu3;此表中每个数据元素占用40个字节的存储空间。思考：这张二维表格是否可以用一个二维数组来实现？数据结构的三个层次数据的逻辑结构——面向用户(1)线性结构有且仅有一个起点数据元素和一个终点数据元素，每个数据元素最多有一个直接前驱和一个直接后继。马二丁一直接前驱张三直接后继前面提到的学

3、生成绩表就属于线性结构！(2)非线性结构一个数据元素可以有多个直接前驱和多个直接后继，如树结构、图结构。丁一马二张三李四图结构大学英语高等数学大学物理操作系统微机原理选课情况电子科技大学通信学院计算机学院自动化学院专业1专业2专业1专业1专业2专业3树结构机构设置数据的存储结构——面向机器(1)顺序存储将逻辑上相邻的数据元素按顺序存储在物理上相邻的存储单元。马二丁一张三李四……2000H内存地址内存2028H2050H2078H首地址(2)链接存储不要求元素按逻辑顺序存储，每个元素含有指针字段，并指向逻辑上相邻的

4、元素的物理存储位置。李四马二丁一……2000H内存地址内存2028H2050H2078H20a0H张三2000H20c8H20c8H2028H……首地址(3)索引存储需要建立一个索引表，表中有两项：关键字和地址，指明了每个元素的物理存储位置。索引表首地址李四马二丁一……2000H内存地址内存2028H2050H2078H20a0H张三20c8H20f0H……2028H42000H320f0H22078H1地址学号索引表即能够区分每个数据元素、具有唯一性的数据项。(4)散列存储基本思想是：通过一个设计好的散列函数f

5、(x)，将元素的关键字作为自变量代入该函数，得到的结果就作为该元素的物理存储地址，这种方法也称为地址转移法。数据的操作集合就是对数据进行处理和运算等操作，主要有：（1）遍历（2）插入（3）更新（4）删除（5）查找（6）排序二、线性结构线性表的基本操作主要有：（1）初始化：建立一个空的初始线性表。（2）求表长：求线性表中元素的个数。（3）取元素：获取给定序号的数据元素的值或首地址。（4）定位：查找等于给定值的数据元素的序号。（5）插入：在给定序号的位置上插入一个新的数据元素。（6）删除：删除给定序号的数据元素。1.

6、线性表线性表是n(n≥0)个相同类型的元素构成的有限的线性序列，线性表的长度为n。(1)顺序表即采用顺序存储方式的线性表，数据元素在物理上按逻辑顺序进行存储，整个表占用一组地址连续的存储单元。马二丁一张三李四……2000H内存地址内存2028H2050H2078H首地址数组是计算机中采用顺序存储的一种数据结构，因此，顺序表可采用数组来实现。数组元素[i]的地址＝数组首地址+i×数据元素字节数可见，顺序表是一种随机存取结构。顺序表的C语言实现顺序表的结构类型定义typedefstructlist_type{elem

7、typedata[MAXNUM];intnum;}listtype;已定义的数据元素类型事先定义的字符常量，表示顺序表的最大长度表示顺序表的当前长度则可以用此类型来定义一个结构体变量：listtypelist;此变量存放的就是一个顺序表顺序表的操作函数定义初始化函数：voidinitiatelist(listtype*l){l->num=0;}将顺序表当前长度置0，表示为空表指向顺序表的首地址，即l=&list数据元素插入函数：（在给定序号位置插入一个新元素）intinsert(listtype*l,inti,e

8、lemtypex){intj;if(l->num>=MAXNUM){printf("thelistisfull,cannotinsert.");return(0);}if((i<0)

9、

10、(i>l->num)){printf("iisinvalidvalue!");return(0);}for(j=l->num-1;j>=i;j--)l->data[j+1]=l->data