数据结构概述

1、数据结构概述东北师大附中谷方明为什么学数据结构算法 + 数据结构 = 程序N.Wirth基本概念数据：数据(data)是对客观事物的符号表示。在计算机领域，数据是指所有能输入到计算机中，并能被计算机存储、处理和输出的一切信息，如文字、图形、图像、声音、视频等。数据类型：数据类型是指数据的不同种类，如整形、实型、字符型、字符串等数据的物理结构例：学生成绩表数据结构数据结构：数据及数据之间的相互关系，即数据的组织形式。一般包括： 1、数据的逻辑结构 数据间抽象化的逻辑关系。 通常所说的数据结构是指数据的逻辑结构。 2、数据的物理结构（存储结构） 数据及其关系在计算机存储器内的表示 3、数据的运算

2、对数据施加的操作。 数据的逻辑结构DS=（D，R）D：数据(元素)的集合 R: 关系的集合数据之间的关系，取决于对数据的操作例1D= s1，s2，s3，s4，s5R=空集特点：数据之间，除了同一集合关系之外，无其它关系。集合结构例2D=s1，s2，s3，s4，s5R=(s1,s2)，(s2,s3)，(s3,s4)，(s4,s5)特点：数据之间的关系呈直线状。 除了第一个和最后一个元素，每个元素都有唯一前驱和唯一后继。数据之间的关系是1：1的联系线性结构例3D=s1，s2，s3，s4，s5R=(s1,s2)，(s1,s3)，(s2,s4)，(s3,s5)特点：数据之间的关系呈现层次状。除了第一个

3、数据没有前驱数据，其它数据元素都有唯一前驱；所有数据可以有0个或多个后继。数据元素之间的关系是1：N的关系。层次结构(树)例4D=s1，s2，s3，s4，s5R=(s1,s2)，(s1,s3)，(s2,s4)，(s3,s5)，(s1,s4)，(s1,s5)特点：数据之间的关系呈现网状。每个数据元素可以有0个或多个前驱和0个或多个后继。数据元素之间的关系是M：N的关系。网状结构(图)小结集合结构线性结构层次结构网状结构非线性结构：层次结构和网状结构数据之间的关系是由对数据的操作决定的顺序存储把逻辑上相邻的数据元素存储在相邻的存储单元中。在C+中，一般用数组描述。优点：便于查找，缺点：插入和删除时

4、会引起数据的大量移动链式存储逻辑上相邻的数据元素在存储空间内不连续，相邻关系通过存放地址维持和体现。在C+中，一般用指针来描述。优点：便于插入和删除；缺点：查找费时索引首先把一个线性表（主表）按照一定的条件划分成若干个子表，为每个子表分别建立一个索引项，由这些索引项构成一个索引表。优点：查找方便；缺点：插入、删除、修改时需要维护索引表。 散列以线性表中的每个元素的关键字k为自变量，通过一种函数h(k)计算出函数值，把这个函数值解释为一块连续存储空间上（数组）的地址值（下标）。这个函数成为hash函数，也叫散列函数、哈希函数。优点：查找快； 缺点：插入、删除、修改时需要解决冲突。 小结数据的物理

5、结构顺序存储链式存储索引散列线性表线性表是最简单、最常用的一种数据结构。 (1,2,3,4,5) (a,b,c,d,，z)姓名学号总分孙雪晖201302xx1000尚柯宇201303xx1000线性表中元素的个数n称为线性表的长度。当n=0时，称线性表为空表。在非空线性表(a1,a2,，an)中，a1是第一个元素，称为表头元素；an是最后一个元素，称为表尾元素。第i个数据ai在ai-1后，在ai+1前(1in)，这种位置上的有序性就是一种线性关系。除a1外，每个数据元素只有一个前驱；除an外每个数据元素只有一个后继。A1A2A3A4AN-1AN线性表的基本操作初始化：设置一个空的线性表求长度：

6、求线性表中元素的个数获取元素：取出线性表中的某个数据元素查找：搜索线性表中满足某一条件的数据元素插入：插入给定元素到线性表中删除：删除线性表中的元素判空：判断线性表是否空判满：判断线性表是否满线性表的顺序结构实现struct Stduent string name; int sco;Student lisMAXL;int len;练习1 电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排： (a1，b1)(a2，b2)(an，bn) 其中ai，bi(i=1，2n) 分别表示某人的名字和对应的电话号码。要求设计一个程序，完成以下功能： 1）输入N个人

7、的名字及电话号码 2）查找某个人的电话号码 3）加入一个人及其电话号码 4）删除某个人及其电话号码 5）按名字对号码簿排序 6）输出号码上所有人的名字和电话号码练习2插入线性表元素 a和b分别表示两个线性表，它们的数据元素类型相同，现要讲b中存在而a中不存在的元素插入到线性表a中。设线性表a的长度与线性表b的长度之和不超过线性表a允许的最大长度。练习3合并线性表 已知线性表a和线性表b中的数据元素按递增的顺序排列，现要求将a和b合并成一个新的线性表c，c中的数据元素仍按递增排列。练习4(Joseph问题)N只猴子选大王，选举办法如下：所有的猴子以顺时针按1到N编号围坐一圈，从编号为1的猴子开始按顺时针方向以1，2，M报数，M1，凡报M的人退出圈外，如此循环报数，直到圈内只剩下一只猴子就是大王，编程求出大王的