VB教程02.数据的线性结构

1、2 数据结构第二章 数据结构1 什么是数据结构什么是数据结构 程序程序=数据结构数据结构+算法算法l例例1 书目自动检索系统书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02书目文件按书名按作者名按分类号高等数学001，003理论力学002，.线性代数004，.樊映川001,华罗庚002,.栾汝书004,.L002,S001,003,索引表线性表l数据结构定义数据结构定义: 是一门研究是一门研究非数值计算非数值计算的程序设的程序设计问题中计算机的计问题中计算机的

2、操作对象操作对象以及它们之间的以及它们之间的关系关系和和操作操作等等的学科等等的学科l2 基本概念和术语基本概念和术语l数据（数据（data)所有能输入到计算机中去的所有能输入到计算机中去的描述客观事物的描述客观事物的符号符号l数据元素（数据元素（data element）数据的数据的基本单位基本单位，也称节点，也称节点（node）或记录（或记录（record）l数据项（数据项（data item）有独立含义的数据有独立含义的数据最小单位最小单位，也称，也称域域(field)l数据结构（数据结构（data structure)数据元素和数据元素关系的数据元素和数据元素关系的集合集合根据数据元素

3、间关系的基本特性，有四种基本数据结构（集合集合）数据元素间除“同属于一个集合”外，无其它关系线性结构线性结构一个对一个，如线性表、栈、队列树形结构树形结构一个对多个，如树图状结构图状结构多个对多个，如图l数据的逻辑结构数据的逻辑结构只抽象反映数据元素的只抽象反映数据元素的逻辑关系逻辑关系l数据的存储（物理）结构数据的存储（物理）结构数据的逻辑结构在计算数据的逻辑结构在计算机机存储器中的实现存储器中的实现数据的逻辑结构与存储结构密切相关算法设计 逻辑结构算法实现 存储结构存储结构分为：顺序存储结构借助元素在存储器中的相对位置相对位置来表示 数据元素间的逻辑关系链式存储结构借助指示元素存储地址的指

4、针指针表示数据 元素间的逻辑关系元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址存储地址 存储内容存储内容 指针指针 1345 1345 元素元素1 1 14001400 1346 1346 元素元素4 4 . . . . . 14001400 元素元素2 2 1536 1536 . . . . . 1536 1536 元素元素3 3 1346

5、 1346 链式存储链式存储 h 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面：l数据类型数据类型高级语言中指数据的高级语言中指数据的取值范围取值范围及其上及其上可进行的可进行的操作操作的总称的总称例 C语言中，提供int, char, float, double等基本等基本 数据类型数据类型，数组、结构体、共用体、枚举 等构造数

6、据类型构造数据类型，还有指针、空(void)类 型等。用户也可用typedef 自己定义数据类型自己定义数据类型typedef struct int num; char name20; float score;STUDENT;STUDENT stu1,stu2, *p;l3 算法的描述和算法分析简介算法的描述和算法分析简介l算法（算法（algorithm）解决某一特定问题的解决某一特定问题的具体步具体步骤的描述骤的描述，是指令的有限序列，是指令的有限序列l算法特性算法特性输出一个算法有零个或多个输出输入一个算法有零个或多个输入算法是能行的可行性义性切定义的，不能产生二算法的每一步必须是确确定性

7、限步骤之后结束一个算法必须在执行有有穷性算法的描述算法的评价衡量算法优劣的标准v正确性(correctness)v可读性(readability)v健壮性(robustness)v效率与低存储量算法效率算法效率用依据该算法编制的程序在计算机上执行所用依据该算法编制的程序在计算机上执行所消耗消耗的时间的时间来度量来度量1.事后统计事后统计利用计算机内记时功能，不同算法的程序可以用一组或利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分多组相同的统计数据区分 缺点：缺点：必须先运行依据算法编制的程序必须先运行依据算法编制的程序 所得时间统计量依赖于硬件、软件等环境因素，掩盖算法

8、本所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本 身的优劣身的优劣 2.事前分析估计事前分析估计一个高级语言程序在计算机上运行所消耗的时间取一个高级语言程序在计算机上运行所消耗的时间取决于：决于： 依据的算法选用何种策略依据的算法选用何种策略 问题的规模问题的规模 程序语言程序语言 编译程序产生机器代码质量编译程序产生机器代码质量 机器执行指令速度机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，效率均不同，所以使用所以使用绝对时间单位绝对时间单位衡量算法效率衡量算法效率不合适不合适

9、时间复杂度：基本操作重复执行的次数的阶数 T(n)=o(f(n) 空间复杂度：s(n)=o(f(n)例1：NN矩阵相乘for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik*bkj; 33)(nOnTnnf数据的线性结构数据的线性结构线性结构线性结构特点特点：在数据元素的非空有限集中：在数据元素的非空有限集中l存在存在唯一唯一的一个被称作的一个被称作“第一个第一个”的数据元素的数据元素l存在存在唯一唯一的一个被称作的一个被称作“最后一个最后一个”的数据元素的数据元素l除第一个外，集合中的每个数据元素均除第一个外，集合

10、中的每个数据元素均只有一个只有一个前驱前驱l除最后一个外，集合中的每个数据元素均除最后一个外，集合中的每个数据元素均只有一只有一个后继个后继l1 线性表的逻辑结构线性表的逻辑结构l定义：一个线性表是定义：一个线性表是n个数据元素的有限序列个数据元素的有限序列niaaaa,21如例 英文字母表（A,B,C,.Z)是一个线性表例学号姓名年龄001张三18002李四19数据元素特征：v元素个数n表长度，n=0空表v1idata表示p指向结点的数据域(*p).linkp-link表示p指向结点的指针域生成一个JD型新结点：p=(JD *)malloc(sizeof(JD);系统回收p结点：free(p

11、)线性链表v定义：结点中只含一个指针域的链表叫，也叫单链表h空表 头结点：在单链表第一个结点前附设一个结点叫头结点指针域为空表示线性表为空头结点ha1a2an 单链表的基本运算单链表的基本运算 查找：查找单链表中是否存在结点X，若有则返回指向X结点的指针；否则返回NULL 算法描述While循环中语句频度为若找到结点X，为结点X在表中的序号否则，为n nOnTpabxsu算法评价l 插入：在线性表两个数据元素a和b间插入x，已知p指向as-link=p-link;p-link=s; 1OnTu算法描述u算法评价 算法描述 1OnTu算法评价l删除：单链表中删除b，设p指向ap-link=p-l

12、ink-link;pabc nOnTl动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针u算法描述u算法评价h头结点0头结点han 0头结点han-10an 头结点a2.han-10an 头结点ha1a2an .0单链表特点单链表特点 它是一种动态结构，整个存储空间为多个链表共用 不需预先分配空间 指针占用额外存储空间 不能随机存取，查找速度慢l循环链表循环链表(circular linked list)循环链表是表中最后一个结点的指针指向头结点，循环链表是表中最后一个结点的指针指向头结点，使链表构成环状使链表构成环状特点：从表中任一结点出发均可找到表中其他结点特

13、点：从表中任一结点出发均可找到表中其他结点，提高查找效率，提高查找效率操作与单链表基本一致操作与单链表基本一致,循环条件不同循环条件不同 单链表p或p-link=NULL 循环链表p或p-link=Hhh空表l双向链表（双向链表（double linked list）单链表具有单向性的缺点单链表具有单向性的缺点结点定义结点定义typedef struct node datatype element; struct node *prior,*next;JD;prior element nextL空双向循环链表非空双向循环链表 LABbcapp-prior-next= p= p-next-proi

14、r;void del_dulist(JD *p)p-prior-next=p-next; p-next-prior=p-prior; free(p);v删除l算法描述l算法评价：T(n)=O(1)p-prior-next=p-next;p-next-prior=p-prior;bcapvoid ins_dulist(JD* p,int x)JD *s; s=(JD*)malloc(sizeof(JD); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;l算法描述l算法评价：T(n)=O(1)xSbaPv插入l4

15、 线性表的应用举例线性表的应用举例l 一元多项式的表示及相加一元多项式的表示及相加l一元多项式的表示：一元多项式的表示：nnnxPxPxPPxP2210)(),(210nPPPPP可用线性表P表示200001000231)(xxxS但对S(x)这样的多项式浪费空间一般emmnxPxPxPxPee2121)(其中为非零系数）（iPemee210用数据域含两个数据项的线性表表示emPePePm，2121其存储结构可以用顺序存储结构，也可以用单链表l单链表的结点定义单链表的结点定义coefexpnext17787178522117)()()(9228)(5937)(xxxxBxAxCxxxxBxxx

16、xA-1A7 0 3 1 9 8 5 17 -1B8 1 22 7 -9 8 -1C7 0 11 1 22 7 5 17 一元多项式相加typedef struct node int coef,exp; struct node *next;JD;设p,q分别指向A,B中某一结点，p,q初值是第一结点比较p-exp与q-expp-exp exp: p结点是和多项式中的一项 p后移,q不动p-exp q-exp: q结点是和多项式中的一项 将q插在p之前,q后移,p不动p-exp = q-exp: 系数相加0：从A表中删去p, 释放p,q，p,q后移0：修改p系数域, 释放q，p,q后移直到p或q

17、为NULL 若q=NULL，结束 若p=NULL，将B中剩余部分连到A上即可运算规则q-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1

18、pb8 1 22 7 -9 8 ppre-1pa7 0 11 1 22 7 5 17 算法描述栈和队列栈和队列栈和队列是两种特殊的线性表，是栈和队列是两种特殊的线性表，是操作受限操作受限的线的线性表，称限定性性表，称限定性DSl1 栈（栈（stack）l栈的定义和特点栈的定义和特点l定义：限定仅在定义：限定仅在表尾表尾进行插入或删除操作的线性表，表尾进行插入或删除操作的线性表，表尾栈栈顶顶，表头，表头栈底栈底，不含元素的空表称空栈，不含元素的空表称空栈l特点：先进后出（特点：先进后出（FILO）或后进先出（或后进先出（LIFO）ana1a2.栈底栈顶.出栈进栈栈s=(a1,a2,an)l栈的存

19、储结构栈的存储结构顺序栈顺序栈 实现：一维数组sMtop=-1123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为-1top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=-1,栈空，此时出栈，则下溢（underflow)top=M-1,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空l入栈算法l出栈算法链栈链栈栈顶 .topdatalink栈底l结点定义l入栈算法l出栈算法typedef struct node int data; struct node *link;JD; .栈

20、底toptopxptop .栈底topqv回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，回文v多进制输出：字符串：“madam im adam”例 把十进制数159转换成八进制数(159)10=(237)815981982802 3 7 余 7余 3余 2toptoptop7top73732栈的应用栈的应用 l2 队列队列l队列的定义及特点队列的定义及特点l定义：队列是限定只能在表的一端进行插入，在表的另一端进定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表

21、行删除的线性表l 队尾(rear)允许插入的一端l 队头(front)允许删除的一端l队列特点：先进先出队列特点：先进先出(FIFO)a1 a2 a3.an 入队出队frontrear队列Q=(a1,a2,an)v双端队列a1 a2 a3.an 端1端2入队出队入队出队l链队列链队列结点定义结点定义typedef struct node int data; struct node *link;JD;头结点 .front队头队尾rear设队首、队尾指针front和rear,front指向头结点，rear指向队尾frontrearx入队xfrontreary入队xyfrontrearx出队xyfrontrear空队frontreary出队l队列的顺序存储结构队列的顺序存储结构实现：用一维数组实现实现：用一维