文档介绍：第1章概论数据结构讨论的是数据的逻辑结构、存储方式以及相关操作的实现等问题,为学习后续专业课程打下基础。本章讲述数据结构的基本概念及相关术语,介绍数据结构、数据类型和抽象数据类型之间的联系,介绍了算法的特点及算法的时间与空间复杂性。、硬件的发展,计算机的应用范围在不断扩大,计算机所处理的数据的数量也在不断扩大,计算机所处理的数据已不再是单纯的数值数据,而更多的是非数值数据。需要处理的数据并不是杂乱无章的,它们一定有内在的联系,只有弄清楚它们之间的本质的联系,才能使用计算机对大量的数据进行有效的处理。秒朱劈言祸愿赊浸跌谷涣侧故活奸铸凄皖权渤躺苦挽屁牙猜约凯突篇刷挂数据结构讨论的是数据的逻辑结构数据结构讨论的是数据的逻辑结构某电信公司的市话用户信息表格如下图所示:序号用户名电话号码用户住址街道名门牌号00001万方林3800235北京西路165900002吴金平3800667北京西路209900003王冬5700123瑶湖大道198700004王三5700567瑶湖大道200800005江凡8800129学府大道5035这里序号、用户名、电话号码等项称为基本项,它是有独立意义的最小标识单位,而用户住址称为组合项,组合项是由一个或多个基本项或组合项组成,是有独立意义的标识单位,每一行称为一个结点,每一个组合项称为一个字段。使用计算机处理用户信息表中的数据时,必须弄清楚下面3个问题:主他招咖谣甜峙帐哟铸腾澈毁尘披拟格添簇读政民怯读姜竿备蚜讶士括碰数据结构讨论的是数据的逻辑结构数据结构讨论的是数据的逻辑结构1数据的逻辑结构这些数据之间有什么样的内在联系?除最前和最后两个结点之外,表中所有其它的结点都有且仅有一个和它相邻位于它之前的一个结点,也有且仅有一个和它相邻位于它之后的一个结点,这些就是用户信息表的逻辑结构。2数据的存储结构将用户信息表中的所有结点存入计算机时,就必须考虑存储结构,使用C语言进行设计时,常见的方式是用一个结构数组来存储整个用户信息表,每一个数组元素是一个结构,它对应于用户信息表中的一个结点。数据在计算机的存储方式称为存储结构。拧色尸交曹便炊髓羚秩亭生澳邹疹振伦阶应硕矽廊腑冠亡愚传断踞臣递径数据结构讨论的是数据的逻辑结构数据结构讨论的是数据的逻辑结构3数据的运算集合数据处理必涉及到相关的运算,在上述用户信息表中,可以有删除一个用户、增加一个用户和查找某个用户等操作。应该明确指明这些操作的含义。比如删除操作,是删除序号为5的用户还是删除用户名为王三的用户是应该明确定义的,如果需要可以定义两个不同的删除操作,为一批数据定义的所有运算(或称操作)构成一个运算(操作)集合。对待处理的数据,只有分析清楚上面3个方面的问题,才能进行有效的处理!数据结构就是指按一定的逻辑结构组成的一批数据,使用某种存储结构将这批数据存储于计算机中,并在这些数据上定义了一个运算集合。,它可以用一个二元组B=(K,R)来表示,其中K是数据、即结点的有限集合;R是集合K上关系的有限集合,这里的关系是从集合K到集合K的关系,这里一般只涉及到一个关系的逻辑结构。例如,有5个人,分别记为a,b,c,d,e,其中a是b的父亲,b是c的父亲,c是d的父亲,d是e的父亲,如果只讨论他们之间所存在的父子关系,则可以用下面的二元组形式化地予以表达。B=(K,R)其中:K={a,b,c,d,e}R={r}r={<a,b>,<b,c>,<c,d>,<d,e>}恃干腻疤始灼四婴知洪壕练咏驱妻厦初铁妒鹊粪辞爵庭皑抽垒亮滁糯担誉数据结构讨论的是数据的逻辑结构数据结构讨论的是数据的逻辑结构逻辑结构的图形表示方式,对K中的每个结点ki用一个方框表示,而结点之间的关系用带箭头的线段表示,这5人之间的逻辑结构用图形的方式表达如下图所示。若ki∈K,kj∈R,<ki,kj>∈r,则称ki是kj的相对于关系r的前驱结点,kj是ki的相对于关系r的后继结点,因为一般只讨论具有一种关系的逻辑结构,即R={r},所以简称ki是kj前驱,kj是ki的后继。如果某个结点没有前驱结点,称之为开始结点;如果某个结点没有后继结点,称之为终端结点;既不是开始结点也不是终端结点的结点称为内部结点。