【精品数据结构】数据结构与算法

1、,DATA,10,65,865,数据结构,第二章数据结构与算法,2.1 概述 数据结构是一门研究数据组织、存储和运算的一般方法的学科。,第二章数据结构与算法,2.1 概述 数据结构是一门研究数据组织、存储和运算的一般方法的学科。,能输入到计算机中 并能被计算机程序处理的 符号的集合。,整数(1,2)、实数(1.1,1.2) 字符串(Beijing)、 图形、声音。,第二章数据结构与算法,2.1 概述 数据结构是一门研究数据组织、存储和运算的一般方法的学科。,计算机管理图书问题 在图书馆里有各种卡片：有按书名编排的、 有按作者编排的、有按分类编排 如何将查询图书的这些信息存入计算机中 既要考虑查

2、询时间短，又要考虑节省空间,第二章数据结构与算法,2.1 概述 数据结构是一门研究数据组织、存储和运算的一般方法的学科。,最简单的办法之一是建立一张表， 每一本书的信息在表中占一行，如,第二章数据结构与算法,2.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,数据元素在 计算机中的表示,第二章数据结构与算法,2.1 概述 数据结构是一门研

3、究数据组织、存储和运算的一般方法的学科。,对数据结构中的节点进行 操作处理 (插入、删除、修改、查找、排序),数据元素(Data Element),数据元素是数据的基本单位，即数据集合中的个体。 有时一个数据元数可由若干数据项(Data Item)组成。数据项是数据的最小单位。,数据元素亦称节点或记录。,名词解释,数据结构可描述为 Group=（D，R）,有限个数据元素的集合,有限个节点间关系的集合,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面

4、,数据结构可描述为 Group=（D，R）,线性结构,A , B , C , ，X ,Y , Z,学 生 成 绩 表,线性表结点间是以线性关系联结,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,数据结构可描述为 Group=（D，R）,树形结构,全校学生档案管理的组织方式,计算机程序管理系统也是典型的树形结构,树形结构 结点间具有分层次的连接关系,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构

5、,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) ,图形结构节点间的连结是任意的,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(亦称物理结构),元素n,.,元

6、素i,.,元素2,元素1,Lo,Lo+m,Lo+(i-1)*m,Lo+（n-1)*m,存储地址,存储内容,Loc(a)=Lo+（i-1)*m,顺序存储,每个元素所占用 的存储单元个数,元素n,.,元素i,.,元素2,元素1,存储内容,顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。,顺序存储结构的三个弱点： 1.作插入或删除操作时，需移动大量元数。 2.长度变化较大时，需按最大空间分配。 3.表的容量难以扩充。,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表

7、,栈,队,树形结构,图形结构,数据结构的三个方面,(亦称物理结构),1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,每个节点都由两部分组成：数据域和指针域。 数据域存放元素本身的数据， 指针域存放指针。 数据元素之间逻辑上的联系由指针来体现。,1536,元素2,1400,元素1,1346,元素3,元素4,head,链式存储,1345,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,1.比顺序存储结构的存储密度小 (每个节点都由数据域和指针愈组成)。 2.逻辑上相邻的节点物理上不必相邻。 3.插入、删除灵活 (不必移动节

8、点，只要改变节点中的指针)。,链接存储结构特点：,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(亦称物理结构),数据结构侧重于解决问题的策略和方法，即研究算法。 它不但要求给出问题的一种算法，还要求算法的时空效率高、算法结构和可读性好、容易验证等等。,for (i=1; i=n; +i) for (j=1; j= n; +j) cij= 0; 算法时间复杂度表示为（n) = O(n2),2.1.2 算法的基本概念,算法：是对特定问题求解步骤的

9、一种描述。,算法的五个特性： 有穷性、确定性、可行性、输入和输出。,评价算法： 正确性、易读性、健壮性、运行时间及占用空间。,2.2线性表,线性表是n个元素的有限序列，它们之间的关系可以排成一个线性序列： a1，a2， ，ai， ，an 其中n称作表的长度，当n=0时，称作空表。,2.2.1线性表及运算,2.除第一个和最后一个数据元素之外，其它数据元素有 且仅有一个前驱和一个后继。第一个数据元素无前驱， 最后一个数据元素无后继。,线性表的特点：,1.线性表中所有元素的性质相同。,3.数据元素在表中的位置只取决于它自身的序号。,在线性表上常用的运算有： 初始化、求长度、取元素、定位、插入及删除等

10、。,2.2.2 线性表的存储结构,1.顺序存储结构 2.链式存储结构,0,1,i-1,V.elemi-1,1. 线性表的顺序存储结构 ,可用C语言中的一维数组来描述. #define LISTINITSIZE 100 /线性表存储空间的初始分配量 typedef struct ElemType *elem；/数组指针表示存储空间基址 int length； /当前长度,int listsize /当前分配的存储容量（以sizeof（ElemType）为单位） Sqlist,C语言的库函数, 测算ElemType节点 需占用的字节数,Status ListInsert_sq（Sqlist V，i

11、nt i , ElemType x） if（iV.length+1）return ERROR; if(V.lengthV.listsize) return OVERFLOW; q=V.elemi-1; for(p=V.elemV.length-1; p=q; p) (p+1)= p; q=x; +V.length; return OK; ,.,a2,a1,0,1,i-1,i,Length-1,P,（P+1）,q,1.1插入运算,x,请同学们看以下的算法。,Status ListInsert_sq（Sqlist V，int i , ElemType x） /在线性中V中第i 个元素之前插入x，i

12、 的合法值为 1 iV.Length+1 if（iV.length+1）return ERROR; /i值不合法 if(V.lengthV.listsize) return OVERFLOW; /无存储空间 q=V.elemi-1; / / q为插入位置 for(q=V.elemV.length-1; p=q; p) /插入位置后的元素依次右移 (p+1)= p; q=x; / 插入x +V.length; /表长加1 return OK; / ListInsert_sq,1.2删除运算,Status ListDelete_sq（Sqlist V，int i , ElemType x） if（

13、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 线性表的链式存储结构 2.1 单链表的插入运算 2.2 单链表的删除运算,2. 线性表的链式存储结构,特点：用一组任意的存储单元(可以是连续的,也可以是不连续的)存放线性表的数据元素。,上图为(ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG) 线性表的线性链表存储结构，存储从头指针开始进行。,线性链表表示法:,L,.,Typedef struct

14、 Lnode Elem Type data； struct Lnode *next； Lnode，*linklist；,线性表的链式存储结构可用C语言中的“结构指针”来描述,2. 线性表的链式存储结构,带头结点的线性链表,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,单链表的插

15、入运算,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 ,在看程序之前，先介绍链表的创建。,Linklist creat() linklist

16、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”, 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=(stru

17、ct lnode*)malloc(LEN)； scanf(%d”, 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”, 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-n

18、ext=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, 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”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n=1) h

19、ead-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, 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”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-da

20、ta!0) n=n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, 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”, n=0；p1=p2=(struct lnode*)malloc(LEN

21、)； 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”, 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”, n=0；p1=p2

22、=(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”, 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(

23、LEN)； scanf(%d”, 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”, 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

24、；p1=(struct lnode*)malloc(LEN)； scanf(%d”, 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”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n= =1) head-next=

25、p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, 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”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n

26、=n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, 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”, 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”, n=0；p1=p2=(struct lnode*)malloc(LEN)； sca