文档介绍：莇第一章绪论莃袁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,