文档介绍：螂第一章绪论蒃葿1--1什么是数据结构薆例子膃学生成绩表(线性表)羁学号姓名语文数学物理化学芈001张三76809087蚆002李四65748060薄003王五59707660蚃羇例二对奕问题(树结构)螆羅例三多叉路口交通灯的管理问题(图的结构)膀CD聿袆膁B袂袈E羆A薂芀薇AC羆AB羃肂蚀肅AD莄BD蒀BC荿BA膅螅膂膈DC芅DB袂DA蚀羇莅ED芃EA莁羀EC蒅EB蚄衿数据结构::数据元素间的关系。薅基本概念和术语羃莀数据:对客观对象的抽象。莆数据元素:数据的基本单位。蒃数据对象:莄有相同性质的数据元素的集合。袈数据结构:荿结构:数据间的关系。薃蒁基本结构(四类)蕿集合膈线性结构蚃树形结构袁图状结构(网状结构)芁数据结构的形式定义:羆(D,S):其中D为数据元素有限集螃S为D上关系的有限集。节逻辑结构:(逻辑关系)蝿物理结构:(存储结构)在计算机中的表示蚅数据元素间的关系在计算机中的两种表示方法螃顺序映象-à顺序存储结构蚃非顺序映象-à链式存储结构蒁数据类型:一个值的集合和定义在这个值集上的一组操作的总称。螈抽象数据类型(ADT):一个数学模型以及定义在该模型上的一组操作可用(D,S,P)表示,其中D为数据对象S为D上的关系集P为对D的基本操作。袂袀ADT描述的一些说明及实现(P10)衿算法算法的描述和算法分析蒇一、算法是解决某一特定问题的有限运算序列,其特性有:羂有穷性芁确定性蚁能行性芆输入莆输出蚂二、描述算法的约定聿每一个算法以函数形式给出(类的概念)。艿有关结点的类型定义,全局变量的说明等均在算法之前说明。莆C的函数可直接调用肃NULL空指针#define预定义。螁如求10!肈#defineM10蒆intp(intx)蒄{inti,s;芈for(i=1,s=1;i<=10;i++)袇s=s*i;薆return(s);}薀三、算法分析羀时间、空间复杂性(时间消耗、空间占用量)薅渐近时间复杂度:T(n)=O(f(n))蚆羁线性表蒈线性表的特点:蚈存在唯一的一个被称作”第一个”的数据元素。蒂存在唯一的一个被称作”最后一个”的数据元素。肈除第一个外,集合中的每一个数据元素均只有一个前驱。袆除最后一个外,集合中的每一个数据元素一均只有一个后继。膃线性表的类型定义薁一、线性表葿线性表:具有上述四个特点的n个数据元素的有限序列莄数据项à记录à文件羂线性表的长度蚁注:线性表是一个相当灵活的数据结构,它的长度可根据需要增长或缩短蚆其运算有:存取,插入,删除,查找,合并,分拆,排序,求表的长度。肆二、抽象数据类型蚁螁ADTList{肇数据对象:D={ai|aiÎElementSet,i=1,2,…n,n>=0}蒄数据关系:R1={<ai-1,ai>|ai-1,aiÎD,i=2,3,….n}螄基本操作:(略)}袁三、例子蒈分别表示集合A和B的线性表LA和LB,现需求AÈB,即在LA中插入LB中在LA中没有的元素()芆四、,现要它们归并为一个新的线性表LC,且LC的数据元素也是按不减有序排列。羁衿如LA=(3,5,8,11)、LB=(2,6,8,9,11,15,20)蚃则LC=(2,3,5,6,8,8,9,11,11,15,20)芁()羁2—2线性表的顺序表示和实现艿一、线性表的顺序表示莅1)、线性表的顺序表示就是用一组地址连续的存储单元依次存储线性表的数据元素。芄2)、对于线性表a1,a2,…ai…,an肁如果每个元素占用s个存储单元,则ai+1的位置为:莆LOC(ai+1)=LOC(ai)+s肇LOC(ai+1)=LOC(a1)+(i-1)*s肃(存储结构示意图P22)膁二、线性表的实现螇1、动态分配顺序存储结构薅#defineLIST_INIT_SIZE100袂#defineLISTINCREMENT10芀typedefstruct{膈ElemType*elem;芇intlength;薁intlistsize;}SqList;莀2、基本操作蕿1)构造一个空表()蒁2)插入算法(P24)莀3)删除算法(P24)膆4)算法的复杂性分析(P25)蒂线性表的链式表示与实现膃2—3--1线性链表腿1、线性链表芆数据域->指针域->结点->线性链表袃注:蚀线性链表中的一个数据元素存储在一个结点中袈每个结点中只包含一个指针域的线性链表也称单链表莆图示芃莂羀 蒆(不带表头的单向链表)蚄螀蝿蒆 肅(带表头节点的单链表)薂蒈薅 膂(空表)羀芇2、线性链表的实现蚅1)单链表存储结构薃typedefstructLnode{蚂EleemTypedata;芀StructLnode*next;螅}Lnode,