基本数据结构与运算-1线性表.ppt

第三章基本数据结构及运算,3.1 概述 3.2 线性表3.3 栈3.4 队列3.5 数组3.6 树与二叉树3.7 图,第三章基本数据结构及运算,3.1 概述 数据结构是一门研究数据组织、存储和运算的一般方法的学科。,第三章基本数据结构及运算,3.1 概述 数据结构是一门研究数据组织、存储和运算的一般方法的学科。,能输入到计算机中并能被计算机程序处理的符号的集合。,整数(1,2)、实数(1.1,1.2)字符串(Beijing)、图形、声音。,第三章基本数据结构及运算,3.1 概述 数据结构是一门研究数据组织、存储和运算的一般方法的学科。,计算机管理图书问题 在图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间,第三章基本数据结构及运算,3.1 概述 数据结构是一门研究数据组织、存储和运算的一般方法的学科。,最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如,第三章基本数据结构及运算,3.1 概述 数据结构是一门研究数据组织、存储和运算的一般方法的学科。,如何将0,1,2,3,4,5,6,7,8,9这10个数存放在计算机中能最快地达到你所需要的目的？目的不同，最佳的存储方方法就不同。从大到小排列：9,8,7,6,5,4,3,2,1,0输出偶数：0,2,4,6,8,1,3,5,7,9,数据元素在计算机中的表示,第三章基本数据结构及运算,3.1 概述 数据结构是一门研究数据组织、存储和运算的一般方法的学科。,对数据结构中的节点进行操作处理(插入、删除、修改、查找、排序),数据：计算机处理的对象数据元素(Data Element)：数据的基本单位 一个数据元素可由若干数据项(Data Item)组成。数据项：数据的最小单位。数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。,数据元素亦称结点或记录数据项亦称字段或域,数据结构可描述为 Group=（D，R）,有限个数据元素的集合,有限个结点间关系的集合,数据元素间的关系：前后件关系,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队列,树形结构,图形结构,数据结构的三个方面,数据结构可描述为 Group=（D，R）,数组,A.线性结构（一对一）,特性：1.有且只有一个根结点 2.每个结点最多一个前件，最多一个后件。（第一个数据元素无前件，最后一个无后件，其它 有且仅有一个前驱和一个后继。）例：（A,B,C,，X,Y,Z）,例：学 生 成 绩 表,1数据的逻辑结构,DS1=（D1，R1）集合表示法D1=k1，k2，k3，k4R1=（k1，k2），（k2，k3），（k3，k4）DS2=(D2,R2)D2=k1,k2,k3R2=(k1,k2),(k1,k3),例：,例：,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,数据结构可描述为 Group=（D，R）,数组,B非线性结构:树形结构（一对多）,全校学生档案管理的组织方式,计算机程序管理系统也是典型的树形结构,识别“体”字的过程,按分支和层次组织的数据，称为：“树形结构”,树形结构 结点间具有分层次的连接关系,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(亦称物理结构),数组,D=1,2,3,4 R=(1,2),(1,3),(1,4),(2,3)(3,4),(2,4),D=1,2,3 R=(1,2),(2,3),(3,2),(1,3),B非线性结构:图形结构（多对多）,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(亦称物理结构),数组,元素n,.,元素i,.,元素2,元素1,Lo,Lo+m,Lo+(i-1)*m,Lo+（n-1)*m,存储地址,存储内容,Loc(a)=Lo+（i-1)*m,A.顺序存储,每个元素所占用的存储单元个数,2、数据的存储结构,元素n,.,元素i,.,元素2,元素1,存储内容,顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。,顺序存储结构的三个弱点：1.插入或删除操作时，需移动大量元素。2.长度变化较大时，需按最大空间分配。3.表的容量难以扩充。,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(亦称物理结构),数组,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,B.链式存储,每个节点都由两部分组成：数据域和指针域。数据域存放元素本身的数据，指针域存放指针。数据元素之间逻辑上的联系由指针来体现。,1536,元素2,1400,元素1,1346,元素3,元素4,head,链式存储,1345,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,1.比顺序存储结构的存储密度小(每个节点都由数据域和指针愈组成)。2.逻辑上相邻的节点物理上不必相邻。3.插入、删除灵活(不必移动节点，只要改变节点中的指针)。,链式存储结构特点：,链表的一个重要特点是插入、删除运算灵活方便，不需移动结点，只要改变结点中指针域的值即可,插 入,删 除,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(亦称物理结构),数组,例 管理信息系统中的查询问题各种计算机管理信息系统中，通常相关的信息(记录)组成一个表文件,表文件是一类很重要的数据结构,文件中的记录可按顺序方式组织,顺序文件,导出的链表,为提高检索效率，可将所有选修“算法分析”课的同学记录串接到一起，这种串接称为“加链”,3.2.1.线性表的逻辑结构3.2.2 线性表的存储结构及运算3.2.3 线性表的应用3.2.4 作业,3.2 线性表,3.2.1.线性表的逻辑结构,线性表逻辑结构n个数据元素的有限序列:(a1,a2,a3,an)n为线性表的长度(n0)，n=0的表称为空表特性：数据元素呈线性关系.所有数据元素ai在同一个线性表中须是相同的数据类型例：学生表,线性表的基本运算：(1)插入：在两个确定的元素之间插入一个新的元素；(2)删除：删除线性表中某个元素；(3)修改：按某种要求查找线性表中的一个元素，需要时，还可找到元素进行值的更新,3.2.2 线性表的存储结构,1.顺序存储结构及插入删除运算2.链式存储结构及插入删除运算（1）单链表（2）循环链表（3）双向链表,0,1,i-1,V.elemi-1,线性表的顺序存储结构,可用C语言中的一维数组来描述.#define LISTINITSIZE 100/线性表存储空间的初始分配量typedef structElemType*elem；/数组指针表示存储空间基址int length；/当前长度,int listsize/当前分配的存储容量（以sizeof（ElemType）为单位）Sqlist,C语言的库函数,测算ElemType节点需占用的字节数,元素数据类型,1.顺序存储结构及插入删除运算,Status ListInsert_sq（Sqlist V，int i,ElemType x）/在线性表V中第i个元素之前插入x，i 的合法值为 1 iV.Length+1if（iV.length+1）return ERROR;/i值不合法 if(V.lengthV.listsize)return OVERFLOW;/无存储空间 q=V.elemi-1;/下行注：插入位置后的元素依次右移 for(p=V.elemV.length-1;p=q;p)(p+1)=p;q=x;/插入x+V.length;/表长加1 return OK;,.,a2,a1,0,1,i-1,i,Length-1,P,（P+1）,q,插入运算,x,删除运算,Status ListDelete_sq（Sqlist V，int i,ElemType x）if（iV.length）return ERROR;P=V.elemi-1;x=P;q=V.elem+V.length1;for(+p;p=q;+p)*(p1)=*p V.length;return OK;,2.链式存储结构及插入删除运算,特点：用一组任意的存储单元(可以是连续的,也可以是不连续的)存放线性表的数据元素。,上图为(ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG)线性表的线性链表存储结构，存储从头指针开始进行。,线性链表表示法:,L,.,Typedef struct LnodeElem Type data；struct Lnode*next；Lnode，*linklist；,线性表的链式存储结构可用C语言中的“结构指针”来描述,（1）线性表的单链式存储结构,带头结点的线性链表,data,next,单链表的插入运算,Status ListInsert_L(LinkList,P,P,L,单链表的插入运算,Status ListInsert_L(LinkList,S,P,L,单链表的插入运算,Status ListInsert_L(LinkList,L,单链表的插入运算,Status ListInsert_L(LinkList,P,L,单链表的插入运算,Status ListInsert_L(LinkList,P,P,L,单链表的插入运算,Status ListInsert_L(LinkList,P,L,单链表的插入运算,Status ListInsert_L(LinkList,S,P,L,单链表的插入运算,Status ListInsert_L(LinkList,S,P,L,单链表的插入运算,Status ListInsert_L(LinkList,S,P,L,单链表的插入运算,Status ListInsert_L(LinkList,L,p,q,Status ListDelete_L(LinkList,单链表的删除运算,（2）循环链表 将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。,循环链表：首尾相接的链表。将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。,L,.,带头结点的单链表,L,.,循环单链表,（3）双向链表 在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。可提高效率。,data,next,before,编写算法的一般步骤,1、分析问题描述输入，输出及模块功能等2、分析算法实现的总体框架，关键问题的突破方法3、核心算法的实现4、算法补充完善，如：增加算法有效性的保护措施越界判断等其它更高效的算法实现？,3.2.3.线性表的应用 应用最广的数据结构高级语言中的数组；计算机的文件系统；计算机的目录系统；电话号码查询系统（可采用顺序表或单链表结构）；各种事务处理（各种表格均采用顺序表和线性链表结构）,作业1：某百货公司仓库中，有一批电视机，按其价格由高到低的顺序存储在计算机中，经常发生的操作是入库和出库。现在又新到m 台价格为h 元的电视机需入库，请你为仓库管理系统设计一种数据结构，并画出逻辑示意图。用框图的形式给出增加电视机到数据结构中（插入操作）的思想。注意：数据元素是（数量，价格），数据元素之间的价格不同。,(1)L=P-link;,作业2：对以下单链表分别执行下列各程序段,并画出结果示意图.,(2)R-data=P-data;,(3)R-data=P-link-data;,(4)P-link-link-link-data=P-data;,(5)T=P;while(T!=NULL)T-data=(T-data)*2;T=T-link;,(6)T=P;while(T-link!=NULL)T-data=(T-data)*2;T=T-link;,(7)P=(JD*)malloc(sizeof(JD);P-data=10;R-link=P;P-link=S;,(8)T=L;T-link=P-link;free(P);,(9)S-link=L;,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,创立具有头指针的链表（自学）,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,n=0,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,n=0,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,n=0,15,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,n=0,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,n=1,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,23,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,n=2,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,n=2,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,n=2,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,n=2,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,n=2,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,n=2,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,n=3,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,n=3,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,n=3,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,n=3,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,n=3,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,n=3,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,p1,p2,n=3,Linklist creat()linklist head,p1,p2;n=0；p1=p2=(struct lnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；else p2-next=p1；p2=p1；p1=(struct lnode*)malloc(LEN)；scanf(%d”,&p1-data)；p2-next=NULL；return(head)；,Head,n=3,重新播放单击此处,作业1：某百货公司仓库中，有一批电视机，按其价格由高到低的顺序存储在计算机中，经常发生的操作是入库和出库。现在又新到m 台价格为h 元的电视机需入库，请你为仓库管理系统设计一种数据结构，并画出逻辑示意图。用框图的形式给出增加电视机到数据结构中（插入操作）的思想。注意：数据元素是（数量，价格），数据元素之间的价格不同。,若：Pi-1 h Pi,(1)L=P-link;,作业2：对以下单链表分别执行下列各程序段,并画出结果示意图.,(2)R-data=P-data;,(3)R-data=P-link-data;,(4)P-link-link-link-data=P-data;,(5)T=P;while(T!=NULL)T-data=(T-data)*2;T=T-link;,(6)T=P;while(T-link!=NULL)T-data=(T-data)*2;T=T-link;,(7)P=(JD*)malloc(sizeof(JD);P-data=10;R-link=P;P-link=S;,(7)P=(JD*)malloc(sizeof(JD);P-data=10;R-link=P;P-link=S;,P,(7)P=(JD*)malloc(sizeof(JD);P-data=10;R-link=P;P-link=S;,P,10,(7)P=(JD*)malloc(sizeof(JD);P-data=10;R-link=P;P-link=S;,P,10,(7)P=(JD*)malloc(sizeof(JD);P-data=10;R-link=P;P-link=S;,P,10,(8)T=L;T-link=P-link;free(P);,(9)S-link=L;,如果 S-link=L 则S所指向的结点为尾结点.,