ch2(1)_blue_dsnew

《ch2(1)_blue_dsnew》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、不断追求，高高飞翔上节课要点回顾数据结构课程——涉及数学、计算机硬件和计算机软件。数据结构定义——指互相有关联的数据元素的集合，用D_S=(D,S)表示。数据结构内容——数据的逻辑结构、存储结构和运算。算法效率指标——时间效率和空间效率。（了解）NANJINGUNIV.NANJINGUNIV.ofAERONAUT.&ASTRONAUT.ofAERONAUT.&ASTRONAUT.COLLEGEOFAUTOMATIONENGINEERINGCOLLEGEOFAUTOMATIONENGINEERING数据结构课程的内容线性数据结构若结构是非空有限集，则有且

2、仅有一个起始元素和一个终点元素，并且所有的数据元素最多只有一个直接前驱和一个逻辑结构唯一直接后继。→可表示为：（a,a,……,a）12n线性结构的逻辑特征：存储结构不唯一有且仅有一个起始元素，无直接前驱仅有一个直接后继；有且仅有一个终点元素，无直接后继仅有一个直接前驱；除起始元素和终点元素外，其它元素只有一个直接前趋和一运算的实现依赖于个直接后继。存储结构简言之，线性结构反映元素间的逻辑关系是一对一(1:1)的。NANJINGUNIV.NANJINGUNIV.ofAERONAUT.&ASTRONAUT.ofAERONAUT.&ASTRONAUT.

3、COLLEGEOFAUTOMATIONENGINEERINGCOLLEGEOFAUTOMATIONENGINEERING线性数据结构II第2章线性结构用线性序列来表示线性结构（a,a,…,a,…,a）2.1线性表12ina为起始元素，a为终点元素，2.2栈和队列1nai为索引号为i的内部元素2.3串2.4数组、特殊矩阵和广义表线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是------线性表NANJINGUNIV.NANJINGUNIV.ofAERONAUT.&ASTRONAUT.ofAERONAUT.&ASTRONAUT.C

4、OLLEGEOFAUTOMATIONENGINEERINGCOLLEGEOFAUTOMATIONENGINEERING12.1线性表2.1.1线性表的逻辑结构2.1.1线性表的逻辑结构2.1.2线性表的顺序存储及运算1.线性表的定义2.1.3线性表的链式存储及运算2.线性表的基本操作2.1.4顺序表和链表的比较NANJINGUNIV.NANJINGUNIV.ofAERONAUT.&ASTRONAUT.ofAERONAUT.&ASTRONAUT.COLLEGEOFAUTOMATIONENGINEERINGCOLLEGEOFAUTOMATIONENGINE

5、ERING1.线性表的定义例126个英文字母组成的英文表定义：线性表是n（n≥0）个相同类型的数据（A,B,C,D,……,Z）元素a,a,…,a所构成的有限线性序列。12n分析：数据元素都是字母；元素间关系是线性的。（a,a,…aa,a，…,a）12i-1，ii＋1n例2学生情况登记表数据元素学号姓名性别年龄班级2008011810205于春梅女182008级电信016班线性起点ai的直接前驱ai的直接后继线性终点2008011810260何仕鹏男182008级电信017班2008011810284王爽女182008级通信011班n=0时称为空表下标，

6、是元素的2008011810360王亚武男182008级通信012班n为元素总个序号，表示元素n>0时称为非空表数，即表长：：：：：在表中的位置分析：数据元素都是记录；元素间关系是线性的。其中数据元素a（1≤i≤n）只是一个抽象的符i号，其具体含义在不同的情况下可以不同。NANJINGUNIV.注意：同一线性表中的元素必定具有相同数据类型NANJINGUNIV.！ofAERONAUT.&ASTRONAUT.ofAERONAUT.&ASTRONAUT.COLLEGEOFAUTOMATIONENGINEERINGCOLLEGEOFAUTOMATIONENG

7、INEERING例：假设线性表L=(23,56,89,76,18)，i=3，2.线性表的基本操作(见书P11）x=56，y=88，则对L的一组操作及结果如下：1.置空表：Init_List（L）将线性表L置成空表Length(L)//所得结果为52.求长度：Length（L）求给定线性表L的长度3.取元素：Get_List（L，i)若1≤i≤length(L)，Get(L,i)//所得结果为89则取第i个位置上的元素，否则取得的元素为Locate(L,x)//所得结果为2NULL（空元素）。Insert(L,i,y)//所得结果为(23,56,88,8

8、9,76,18)4.定位函数：Locate_List（L，X）在线性表L中查找值为X的元素的位