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

2数据结构第二章数据结构1什么是数据结构

程序=数据结构+算法例1书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表数据结构定义:是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科2基本概念和术语数据（data)—所有能输入到计算机中去的描述客观事物的符号数据元素（dataelement）—数据的基本单位，也称节点（node）或记录（record）数据项（dataitem）—有独立含义的数据最小单位，也称域(field)数据结构（datastructure)—数据元素和数据元素关系的集合根据数据元素间关系的基本特性，有四种基本数据结构（集合）——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图数据的逻辑结构—只抽象反映数据元素的逻辑关系数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构 存储结构分为：顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1536元素21400元素11346元素3∧元素41345h存储地址

存储内容

指针1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

链式存储

h

数据的逻辑结构

数据的存储结构数据的运算：检索、排序、插入、删除、修改等

线性结构

非线性结构

顺序存储

链式存储线性表栈队树形结构图形结构数据结构的三个方面：数据类型—高级语言中指数据的取值范围及其上可进行的操作的总称例C语言中，提供int,char,float,double等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用typedef

自己定义数据类型typedef

struct

{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;3算法的描述和算法分析简介算法（algorithm）—解决某一特定问题的具体步骤的描述，是指令的有限序列算法特性—算法的描述算法的评价—衡量算法优劣的标准正确性(correctness)可读性(readability)健壮性(robustness)效率与低存储量算法效率——用依据该算法编制的程序在计算机上执行所消耗的时间来度量

1.事后统计——利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分缺点：必须先运行依据算法编制的程序所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣

2.事前分析估计——一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，———所以使用绝对时间单位衡量算法效率不合适时间复杂度：基本操作重复执行的次数的阶数T(n)=o(f(n))空间复杂度：s(n)=o(f(n))例1：N×N矩阵相乘for(i=1;i<=n;i++)

for(j=1;j<=n;j++){c[i][j]=0;

for(k=1;k<=n;k++)

c[i][j]=c[i][j]+a[i][k]*b[k][j];} 数据的线性结构线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继1线性表的逻辑结构定义：一个线性表是n个数据元素的有限序列例英文字母表（A,B,C,…..Z)是一个线性表例数据元素特征：元素个数n—表长度，n=0空表1<i<n时ai的直接前驱是ai-1，a1无直接前驱ai的直接后继是ai+1，an无直接后继元素同构，且不能出现缺项2线性表的顺序存储结构顺序表：定义：用一组地址连续的存储单元存放一个线性表叫~元素地址计算方法：LOC(ai)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai)+L其中：L—一个元素占用的存储单元个数LOC(ai)—线性表第i个元素的地址特点：实现逻辑上相邻—物理地址相邻实现随机存取实现：可用一维数组实现a1a2an01n-112n内存V数组下标元素序号M-1typedef

intDATATYPE;#defineM1000DATATYPEdata[M];例typedef

structcard{intnum;charname[20];charauthor[10];charpublisher[30];floatprice;}DATATYPE;DATATYPElibrary[M];备用空间数据元素不是简单类型时,可定义结构体数组或动态申请和释放内存DATATYPE*pData=(DATATYPE*)malloc(M*sizeof(DATATYPE));free(pData);插入定义：线性表的插入是指在第I（1in+1）个元素之前插入一个新的数据元素x，使长度为n的线性表

变成长度为n+1的线性表

需将第i至第n共（n-i+1)个元素后移算法内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1x算法时间复杂度T(n)设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：删除定义：线性表的删除是指将第i（1in）个元素删除，使长度为n的线性表

变成长度为n-1的线性表

需将第i+1至第n共（n-i)个元素前移算法内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+2算法评价设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低顺序存储结构的优缺点优点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充3线性表的链式存储结构特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点

数据域：元素本身信息指针域：指示直接后继的存储位置数据域指针域结点ZHAOQIANSUNLIZHOUWUZHENGWANG^H例线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针实现typedef

structnode{

datatype

data;

structnode*link;}JD;JD*h,*p;datalinkp结点（*p）(*p)表示p所指向的结点(*p).datap->data表示p指向结点的数据域(*p).linkp->link表示p指向结点的指针域生成一个JD型新结点：p=(JD*)malloc(sizeof(JD));系统回收p结点：free(p)线性链表定义：结点中只含一个指针域的链表叫~，也叫单链表h空表^头结点：在单链表第一个结点前附设一个结点叫~头结点指针域为空表示线性表为空头结点ha1a2an^……单链表的基本运算查找：查找单链表中是否存在结点X，若有则返回指向X结点的指针；否则返回NULL算法描述While循环中语句频度为若找到结点X，为结点X在表中的序号否则，为npabxs算法评价插入：在线性表两个数据元素a和b间插入x，已知p指向as->link=p->link;p->link=s;算法描述算法评价算法描述算法评价删除：单链表中删除b，设p指向ap->link=p->link->link;pabc动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针算法描述算法评价h头结点0^头结点han^0头结点han-10an^头结点a2…...han-10an^头结点ha1a2an^…...0单链表特点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢循环链表(circularlinkedlist)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致,循环条件不同单链表p或p->link=NULL循环链表p或p->link=Hhh空表双向链表（doublelinkedlist）单链表具有单向性的缺点结点定义typedef

structnode{

datatypeelement;

structnode*prior,*next;}JD;priorelementnextL空双向循环链表非空双向循环链表LABbcapp->prior->next=p=p->next->proir;voiddel_dulist(JD*p){p->prior->next=p->next;

p->next->prior=p->prior;

free(p);}删除算法描述算法评价：T(n)=O(1)p->prior->next=p->next;p->next->prior=p->prior;bcapvoidins_dulist(JD*p,intx){JD*s;s=(JD*)malloc(sizeof(JD));s->element=x;

s->prior=p->prior;

p->prior->next=s;

s->next=p;

p->prior=s;}算法描述算法评价：T(n)=O(1)xSbaP插入4线性表的应用举例一元多项式的表示及相加一元多项式的表示：可用线性表P表示但对S(x)这样的多项式浪费空间一般其中用数据域含两个数据项的线性表表示其存储结构可以用顺序存储结构，也可以用单链表单链表的结点定义coefexpnext-1A703198517^-1B81227-98^-1C70111227517^一元多项式相加typedef

structnode{int

coef,exp;

structnode*next;}JD;设p,q分别指向A,B中某一结点，p,q初值是第一结点比较p->exp与q->expp->exp<q->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为NULL

若q==NULL，结束

若p==NULL，将B中剩余部分连到A上即可运算规则q-1pa703198517^-1pb81227-98^ppreq-1pa703198517^-1pb81227-98^ppreq-1pa7011198517^-1pb81227-98^ppreq-1pa7011198517^-1pb81227-98^ppreq=NULL-1pa7011198517^-1pb81227-98^ppreq=NULL-1pa7011198517^-1pb81227-98^ppre-1pa70111227517^算法描述栈和队列栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS1栈（stack）栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)栈的存储结构顺序栈实现：一维数组s[M]top=-1123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为-1top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=-1,栈空，此时出栈，则下溢（underflow)top=M-1,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空入栈算法出栈算法链栈栈顶^…...topdatalink栈底结点定义入栈算法出栈算法typedef

structnode{intdata;

structnode*link;}JD;^…...栈底toptopxptop^…...栈底topq回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，回文多进制输出：字符串：“madamim

adam”例把十进制数159转换成八进制数(159)10=(237)81598198280237余7余3余2toptoptop7top73732栈的应用2队列队列的定义及特点定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)——允许插入的一端队头(front)——允许删除的一端队列特点：先进先出(FIFO)a1a2a3…….an入队出队frontrear队列Q=(a1,a2,……,an)双端队列a1a2a3…….an端1端2入队出队入队出队链队列结点定义typedef

structnode{intdata;

structnode*link;}JD;头结点^…...front队头队尾rear设队首、队尾指针front和rear,front指向头结点，rear指向队尾frontrearx入队^xfrontreary入队x^yf