《常用数据结构及其应用》由会员分享，可在线阅读，更多相关《常用数据结构及其应用（128页珍藏版）》请在金锄头文库上搜索。
1、1,江苏大学多媒体教学课件 计算机软件技术基础,江苏大学电气信息工程学院电子信息工程系2014 年 02 月,第三章 常用数据结构及其应用,NO:2,数据结构部分主要内容,第一节、数据结构概述 第二节、线性表 第三节、栈与队列 第四节、数组 第五节、树与二叉树 第六节、图,NO:3,第一节、数据结构概述,用计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题抽象出一个适当的数学模型；然后设计一个解此数学模型的算法；最后采用一种计算机语言编出程序，调试、修改直至得到最终答案。,程序 = 数据结构 + 算法,NO:4,例1: 书目自动检索系统,书目文件,索引表,1、数据结构示例 -
2、 1,按书名,按分类号,按作者名,NO:5,例3: 学生成绩表（复杂的线性表），数据元素是由若干个数据项组成，如每个学生的情况，称为记录（Record）；由多个记录组成的线性表称为文件（File).,例2: 英文26个字母表的数据结构是一个线形表，可表示为:B=D,R 其中：D= a , b, c, ，x ,y ,zR=(a,b),(b,c),，(y,z),数据结构示例 - 2,NO:6,树形结构例子结点间具有分层次的连接关系,例4：计算机中的目录结构问题,数据结构示例 - 3,NO:7,D= 1 , 2 , 3 , 4R=(1,2) , (1,3) , (1,4) ,(2,3)，(3,4)
3、, (2,4) ,D= 1 , 2 , 3 R= , , , ,图形结构 结点间的连结是任意的,例5：交通、道路问题的数学模型,数据结构示例 - 4,NO:8,通过上述例子可以看出：描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。 数据结构定义：数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间关系和操作的学科。,通过计算机解决问题，可以通过分析数学方程式来建立数学模型，并以之为加工对象的程序设计，这种程序设计的方式为数值分析型程序设计。,总,NO:9,数据（data)：是信息的载体，是可以用计算机表示并加工的各种“符号”的集合；数据元素（
4、data element）：是数据的基本单位，是数据集合中的一个个体；亦称节点（node）或记录（record）；数据项（data item）：有独立含义的数据最小单位，也称域(field)；数据对象（data object）：有相同性质的数据元素的集合；,2、数据结构的基本概念和术语,NO:10,数据结构（data structure)：数据元素和数据元素关系的集合，是指同一数据对象中个数据元素间存在的关系。数据结构的定义常采用集合论的方式，表示为：S = （ D，R ）其中，数据结构 S 是一个二元组D 是一个数据元素的非空有限集合R 是定义在 D 上的关系的非空有限集合,NO:11,1）
5、数据的逻辑结构：是指数据元素及其关系的数学特性，反映数据之间的逻辑关系。三种基本结构:线性结构: 数据元素存在着线性(一对一)的关系；树形结构: 数据元素存在着层次(一对多)的关系；图形结构: 数据元素存在着任意(多对多)的关系。2）数据的存储结构：数据在计算机内部的存储方式。 3）数据的操作：数据的操作即是对数据进行的处理。,3、数据结构研究的主要问题,NO:12,1.数据的逻辑结构2.数据的存储结构 3.数据的运算：检索、排序、插入、删除、修改等。,A.线性结构B.非线性结构,A. 顺序存储 B. 链式存储,线性表 栈 队列,树形结构 图形结构,数据元素在计算机内部的组织方式,4、数据结构
6、的三个方面,反映数据元素之间的逻辑关系,数据结构是一门研究数据组织、存储和运算的一般方法的学科,NO:13,Loc(元素i)= Lo +（i-1) * m 式中，Lo为第一个元素地址，m为一个元素站用空间的大小。顺序存储结构即将数据结构的数据元素存在一组地址连续的存储单元中。,5、数据的存储结构,NO:14,NO:15,在数据处理的过程中，大量的数据都是以表格的形式出现的，这种表格称为线性表，它是数据元素的有限序列。线性表是一种最简单、最常见的数据结构。线性表的主要运算有插入、删除、查找和排序。线性表的常用存储结构有：向量、链表。,第二节 线性表（Linear List）,NO:16,线性表是
7、 n 个元素的有限序列，是最常用最简单的数据结构，长度可增长或缩短。它们之间的关系可以排成一个线性序列，表示为：L =（a1 ，a2 ，. . . ，ai ，. . . ，an ）L 为线性表，ai为某一数据对象中的数据元素，n = 0 为线性表中元素的个数，即表长。 用集合论的方法，线性表可定义为：L = D = a1，a2，an R = （ai-1，ai）| ai-1，aiD，i 2，n ,一、线性表的概念,若线性表中数据元素相互间是可比较的，则称该线性表是有序表，否则为无序表。,NO:17,线性结构特点：对于数据元素的线性非空有限集合存在唯一的一个被称作“第一个”的数据元素；存在唯一的一
8、个被称作“最后一个”的数据元素；除第一个外，集合中每个数据元素均只有一个前驱；除最后一个外，集合中每个数据元素均只有一个后继。线性表上常用的运算有：初始化、求长度、取元素、定位、插入及删除等。,线性表中的数据元素是各种各样的，同一线性表中的元素必定具有相同的特性，即属于同一数据对象，相邻数据元素之间存在着序列关系。,二、线性表的特点与基本运算,NO:18,例2: 学生成绩表（复杂的线性表），数据元素是由若干个数据项组成，如每个学生的情况，称为记录（Record）；由多个记录组成的线性表称为文件（File).,例1: 英文26个字母表的数据结构是一个线形表，可表示为:B=D,R 其中：D= a
9、, b, c, ，x ,y ,zR=(a,b),(b,c),，(y,z),三、常见线性表示例,NO:19,线性表的存储结构采用顺序存储结构，称之为顺序表，亦为向量；采用链式存储结构，称之为链表。,四、线性表的存储结构及其运算,NO:20,1）特点：把线性表中数据元素依次存放到一组连续的存储单元中，每个数据元素对应一个存储单元。线性表中数据元素类型一致，占用相同大小的存储单元。存储空间利用率高。做插入、删除时需移动大量元素。空间估计不明时，按最大空间分配。,1. 线性表的顺序存储结构,NO:21,Loc ( 元素i )= Lo + ( i 1 ) * m 式中，Lo为第一个元素地址，m 为一个元
10、素站用空间的大小。,2）顺序存储结构示意图,NO:22,在高级语言中，常用一维数组来描述和表示线性表。 /* 定义M为常数100，M的值作为数组的最大容量 */ #define M 100 /* 数组的名字V ，假设数组中的元素是整型类型 */ int VM;,3）线性表顺序存储结构的描述,NO:23,在线性表的第i个元素之后插入一个新的元素x，先移动，后插入。,x,x,4）顺序表插入运算过程,NO:24,int insq(int i，int x , int V , int M, int *p） /* 在线性表V中第i个元素之后插入x，i的合法值为1in */int n, j; n = *p;
11、 /* 获取表长 */if（n=M) /* M是存储空间的大小，p是指向存储表长的指针 */ printf(“overflow n“); return (0); if( i n) printf(“i is error n“);return (0); /* i值不合法 */else for (j=n; ji; j-) Vj=Vj-1; /*插入位置后元素依次右移*/Vj=x; /* 插入x */p=+n; /* 表长加1,由p返回到函数调用处 */return (1); ,void main( ) int M=10, n=4; /*M是数组大小, n是元素个数,即表长*/int result,
12、k;static int V10 = 3,5,7,10; /* 数组赋初值 */result=insq(2,4,V,M, 运行结果:success! 3 4 5 7 10,5）顺序表的插入算法,NO:25,int delsq(int i , int V , int *p）/*在线性表V中删除第i 个元素*/ int n,j;n=*p;if（in-1） printf(“This element is not in the list n“); return (0); else for (j=i;jdata 表示 p 指向结点的数据域；(*p).link p-link 表示 p 指向结点的指针域；
13、生成一个struct LNode型新结点：p = (struct LNode *)malloc(sizeof(struct LNode);系统回收p结点：free(p)；,1）线性表链式存储结构的描述,NO:28,2）线性链表的基本运算,设p、q、s均为struct LNode变量，常用的几种基本运算是：,A）指针赋值 s = p; q = p - link;,B）指针移动 p = p - link;,C）在某点后插入 s-link = p-link; p - link = s；,head,NO:29,E）删除某结点 if (p-link !=NULL) q=p-link ; p-link=q-link; free(q); / 删除p的后继结点,D）在某点前插入 q = head； while （q-link != p）q = q-link; q-link = s; s-link = p；,NO:30,设无表头结点的线性链表的头指针为 h, 沿着链表的开始往后找结点x，若找到，则返回该结点在链表中的位置，否则返回空地址。 struct LNode *lbcz(struct LNode *h, int x) struct LNode *p;p=h;while (p!=NULL ,
