1、1,数 据 结 构,（C语言版）,作者：黎剑兵,2,第 一 章 绪 论,学习内容 常用术语 算法评价 时间复杂度与空间复杂度的分析 重点了解逻辑结构 物理结构和数据的运算三方面相关概念及相互关系难点 时间复杂度的分析方法掌握 用类C语言的表示方法会用类C编写程序,3,第 一 章 绪 论,计算机科技 是 一门研究用计算机进行信息表示和处理的科学。主要涉及两方面的问题：信息的表示和信息的处理 信息的表示和组织直接关系到处理信息的程序 的效率，随着计算机的应用领域的扩大。信息量的增加，信息范围的拓宽，使系统程序和应用程序的规模的日趋增大，结构也日趋增大。因此，为了编写出一个“好”的程序，必须分析 处
2、理的对象的特征及个对象之间的存在的关系。这就是本课程所要研究的问题。,4,第 一 章 绪 论,计算机程序 是 对信息进行加工处理。这些信息之间大多数情况下往往具有重要的结构关系。这就是数据结构的内容。那么，什么是数据结构呢？,5,1.地位,第 一 章 绪 论,6,1.地位,第 一 章 绪 论,数据结构Data Structure,7,数据模型,问题,实现,2.主要内容,第 一 章 绪 论,8,数据模型,问题,实现,2.主要内容,第 一 章 绪 论,(1)要对所加工的对象进行逻辑组织 (2)如何把加工对象存储到计算机中去？(3)数据运算,9,3. 学科定义, 什么是数据结构,数据结构 是一门研究
3、非数值 计算的程序设 计问题中计算机的 操作对象以及它们之间的关系和 操作等等的学科。,10, 基本概念和术语,数据元素(data element) 数据基本单位，也称节或孩子，可由若干个数据项组成。数据项是数据最小单位数据(data) 是对客观事物的 表示，指所有能输入到计算机并被计算机程序处理的符号的总称。数据对象( data object)性质相同的数据元素的集合数据结构 数据元素之间的相互关系,11,1) 集合, 基本概念和术语,数据间的四种典型结构：,2）线形,3）树形,4）图或网络：,12, 基本概念和术语,四种典型结构：,1) 集合,13,四种典型结构, 基本概念和术语,2）线形
4、：,14,四种典型结构：, 基本概念和术语,3）树形：,15,四种典型结构：, 基本概念和术语,4）图或网络：,16, 基本概念和术语,（5）逻辑结构：从具体问题抽象出的数学模型。体现逻辑关系。,（6）物理结构(存储结构)： DE及关系在计算机中的表示。DE存储称为节点关系存储：a. 顺序存储 b. 链式存储,17, 基本概念和术语,（7）DS广义定义：DE 的逻 辑 结 构 DE 的物 理 结 构DE 的 抽 象 运 算 （8）基本操作加工型：插入 删除 更新 排序 引用型：查找,18, 基本概念和术语,19, 算法和算法分析,一、算法定义,算法是对特定问题求解步骤的一种描述，是指令的有限序
5、列。 特性： 有穷性 确定性 可行性 输入 输出,20, 算法和算法分析,二、算法的描述与分析描述：类C语言要求正确性： a. 语法 b. n个输入 c. 一组典型的苛刻的输入 d. 所有输入可读性健壮性效率与存贮量,21, 算法和算法分析,分析标准 a 、时间复杂度 ：算法中基本操作重复执行的次数(频度)。T(o)=O(f(n) 时间复杂度分为平均时间复杂度和最坏时间复杂度复杂度的值取规模函数最高阶,22,分析标准 a 、时间复杂度 ：算法中基本操作重复执行的次数。T(o)=O(f(n) 时间复杂度分为平均时间复杂度和最坏时间复杂度复杂度的值取规模函数最高阶, 算法和算法分析,b 、空间复杂
6、度： 算法所需存贮空间S(n)=O(f(n),23, 算法和算法分析,例：分析下列语句段的时间复杂度m = 0; 1for( k=0;kn;k+) n+1for(j=0;jk;j+) n(n+1)/2m +=2; O(n2),24,习题与练习 一,1.简要回答下列问题：a. 数据与数据元素有何区别？b. 逻辑结构与存储结构是什么？它们是什么关系？c. 什么是算法？它有什么特点？,25,习题与练习 一,2. 试写一个算法，统计输入的100个整数中奇数和偶数的个数。 3. 设计下面问题算法，并分析最坏情况时间复杂性:在数组 A1.n中查找值为 K的元素，若找到输出其位置 i ( 0 i n+1),
7、否则输出0。,26,习题与练习 一,4. 设 n 为正整数，写出下列程序段的时间复杂度：（1）for(I=1;In;I+)m=m+I;for(j=0;jn;j+) count +=m+j;,27,习题与练习 一,（2）for(I=0;In;I+)m=m+I;for(j=0;j10;) count +=m+j;j+;,28,习题与练习 一,（3）k=1;s=0;while(s=i;j-) vj=vj-1; vj=x; *p=+n; return (1); ,53,2.2 线性表的顺序存储和实现,插入一个元素图示1,54,2.2 线性表的顺序存储和实现,插入一个元素图示2,x,55,2.2 线性表
8、的顺序存储和实现,插入算法时间复杂度T(n) Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：,56,2.2 线性表的顺序存储和实现,向线性表中表头插入一个元素,InsertFront(List* L,const ElemType ,57,2.2 线性表的顺序存储和实现,向线性表中满足条件的位置插入一个元素,void Insert(List* L,const ElemType item) if(L-size = = MaxSize)printf( “List overflow!”);return; for(i=0; isize;
9、i+) if(item listi) break; for(j = L-size 1; j=i ; j-)L-listj+1 = L-listj; L-listi = item; L-size + ;,58,2.2 线性表的顺序存储和实现,向线性表中的末尾添加一个元素,void InsertRear(List* L, ElemType item) if(L-size = = MaxSize)printf( “List overflow!” );return;L-listL.size = item; L-size +; ,59,变成长度为n-1的线性表,需将第i+1至第n共（n-i）个元素前移,
10、2.2 线性表的顺序存储和实现,删 除 一 个 元 素 定义：线性表的删除是指将第i（1i n）个元素删除，使长度为n的线性表,60,2.2 线性表的顺序存储和实现,删 除 一 个 元 素算法,int sxbsc(int i, int v, int *p) int j,n; n=*p; if(in) return (0); for(j=i;jsize = = 0)printf( “L is an empty list!” );return 0;for(i = 0; isize; i+)if(L-listi = = item) break ;,65,2.2 线性表的顺序存储和实现,从线性表中删除
11、等于给定值的元素2,if(i = = L-size) printf( “Deleted element is not exist!” ); return 0;for(int j = i+1; jsize; j+)L-listj-1 = L.list;L-size - ;return 1; ,66,例 已知线性表(ao，a1，an-1)按顺序存储，且每个元素都是均不相等的 整数。设计把所有奇数移到所有的偶数前边的算法(要求时间最少，辅助空间最少)。,2.2 线性表的顺序存储和实现,解 从左向右找到偶数A.datai，从右向左找到奇数A.dataj，将两 者交换；循环这个过程直到i大于j为止,67
12、,2.2 线性表的顺序存储和实现,void move(sqlist A) int i=0,j=A.len-l,k; ElemType temp; while (i=j) while (A.datai%2=1) i+; while (A.dataj%2=0) j-; if(idata表示p指向结点的数据域(*p).next/p-next表示p指向结点的指针域生成一个LNode型新结点：p=(LNode *)malloc(sizeof(LNode);系统回收p结点：free(p), 2.3 线性表的链式存储结构,75, 2.3 线性表的链式存储结构,头结点：在单链表第一个结点前附设的一个结点。头结
13、点指针域为空表示线性表为空,76, 2.3 线性表的链式存储结构,在带头节点的单链表中查找第 i 个结点,Status ListSearch_L(LinkList L,int i, datatype *e)P = L-next;j = 1;While(p!=NULL return OK； ,77, 2.3 线性表的链式存储结构,在带头节点的单链表中第 i 个结点处插入新元素 x,78, 2.3 线性表的链式存储结构,Status ListInsert_L ( LinkList L, ElemType x, const int i ) p=L;j=0;while (p,79, 2.3 线性表的链
14、式存储结构,删除元素 ：,80, 2.3 线性表的链式存储结构,Status ListDelete_L (LinkList L,int I,ElemType *e)P = L; j= 0;While(p-next/ListDelete_L,删除元素 ：,81, 2.3 线性表的链式存储结构,两个有序单链表合并为一个有序单链表(非递减),MergeList_L(Linklist La,LinkList Lb,LinkList Lc)pa = La-next; pb = Lb-next;Lc = pc = La;While (pa ,82,它是一种动态结构，整个存储空间为多个链表共用不需预先分配空
15、间指针占用额外存储空间不能随机存取，查找速度慢, 2.3 线性表的链式存储结构,单链表具有单向性的缺点,单链表特点,83, 2.3 线性表的链式存储结构,循环链表:表中最后一个结点的指针指向表头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率,84, 2.3 线性表的链式存储结构,循环链表操作与单链表基本一致,循环条件不同单链表:p或p-next=NULL循环链:p或p-next=H,85, 2.3 线性表的链式存储结构,2.3.3双向链表（double linked list ),指向前驱结点,数据,指向后继结点,结点定义typedef struct node
16、datatype data; struct node *prior,*next; DLNode,*DLinkLIst,86,空双向循环链表：,非空双向循环链表：,L, 2.3 线性表的链式存储结构,双向链表图例,87,p-prior-next= p= p-next-proir;, 2.3 线性表的链式存储结构,双向链表图例,88, 2.3 线性表的链式存储结构,在给定结点p前插入一个新结点,89,在给定结点p前插入一个新结点,S=(DLinklist)malloc(sizeof(DLNode);s-data = x;s-prior = p-prior; s-next = p;p-prior-n
17、ext = s; p-prior = s; , 2.3 线性表的链式存储结构,90,p-prior-next=p-next;,p-next-prior=p-prior;, 2.3 线性表的链式存储结构,删除给定结点p,91,p-prior-next=p-next;,p-next-prior=p-prior;,删除给定结点p动画演示, 2.3 线性表的链式存储结构,92,p-prior-next = p-next;p-next-prior = p-prior;free(p);,删除给定结点 p 算法,就这么简单！, 2.3 线性表的链式存储结构,93,3 存储结构的选用,顺序与链式存储结构的选用
18、应考虑因素：（1）存储空间（2）运算时间（3）程序设计语言,94,习题与练习 二,1.描述以下三个概念的区别：头结点、头指针和开始结点2.从尾指针出发能访问到链表上所有结点的链表有 。3.假设有两个按元素值递增的线性表 A、B，编写算法将两表合并为一个按元素值递减的线性表C。（分别以顺序、链式实现）,95,习题与练习 二,4.设线性表存放在向量 AMAXSIZE的前elenum个分量中，且递增有序。试写一算法，将 x 插入线性表适当位置上，以保持线性表的有序性，并且分析算法的时间复杂性。 5.以链式存储结构实现上题。,96,习题与练习 二,6.在双向链表上实现线性表的下列基本运算：(1) 初始
19、化(2) 定位(3) 插入(4) 删除,97,【学习内容】 栈的抽象数据类型、顺序表示、链表表示及相应操作 (特别注意栈空和栈满的条件） 队列的定义、特性 队列的抽象数据类型、顺序表示、链表表示及相应操作 （特别是循环队列中队头与队尾指针的变化情况） 栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS。,第三章 栈与队列,98,第 三 章 栈 与 队列, 3.1 栈（stack）, 3.1.1 定义通常称插入、删除的这一端（如表尾）为栈顶(Top)，另一端（表头）为栈底(Bottom)。当表中没有元素时称为空栈 特点：先进后出（FILO）或后进先出（LIFO）,99,例：假设栈S=(
20、a1，a2，a3，an) 则a1称为栈底元素，an为栈顶元素。进栈 top+1;新元素插入elementstop位置出栈 top-1;栈中元素按a1，a2，a3，an的次序进栈，退栈按后进先出的原则进行的,因此按an a3 a2 a1的次序出栈,3.1 栈 （stack）,100,3.1 栈 （stack）,栈的主要操作：,（1）建立一个空栈 IniStack(&s)（2 ）判断一个栈是否为空StackEmpty(&s)（3）进栈 Push(&s,x)（4）出栈 Pop(&s,&e)（5）获得栈顶元素值 GetTop(s,&e),101,进栈：top+1;新元素插入elementstop位置出
21、栈：top-1,栈s=(a1,a2,an),3.1 栈 （stack）,栈的图示,102,3.1 栈 （stack）,栈和线性表类似，也有两种（顺序、链式）实现方法,103,存储结构定义#define MAXSIZE 6typedef struct datatype elementsMAXSIZE; int top;SqStack;,3.1 栈 （stack）,一、栈的顺序存储,104,3.1 栈 （stack）,栈的顺序存储,栈顶指针top 指示栈顶元素在顺序栈中的位置top=-1,栈空，此时出栈，则下溢（underflow）top= MAXSIZE-1,栈满，此时入栈，则上溢（overfl
22、ow）,105,3.1 栈 （stack）,顺序栈进、出栈图示,栈顶指针top,指向实际栈顶后的空位置，初值为-1,进栈,A,出栈,栈满,B,C,D,E,F,设数组维数为Mtop=-1,栈空，此时出栈，则下溢（underflow)top=M-1,栈满，此时入栈，则上溢（overflow),栈空,106,Status Push(SqStack *S,datatype e)If(S-top = MAXSIZE-1) /*上溢*/return ERROR; S-top +; S-elementsS-top = e;return OK; ,3.1 栈 （stack）,进栈算法,107,3.1 栈 （s
23、tack）,出栈算法,Status Pops (SqStack *S,datatype *e)If (S-top = -1) /*下溢*/return ERROR;S-top -; *e = S-elementsS-top+1;return OK;,108,二、链栈（单链表）,3.1 栈 （stack）,typedef struct node int data; struct node *link;LinkList;,结点定义,109,3.1 栈 （stack）,链栈的特点,链表的存储结构与链接存储的栈完全相同，只是链头指针就是栈顶指针。初始时为NULL 链式栈无栈满问题，空间可扩充插入与删除
24、仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作,110,3.1 栈 （stack）,链栈的进栈算法,进栈等同于不带头结点单链表的头插法Status Push(LinkList * S,datatype e )p = (LinkList *)malloc(sizeof(Linklist);p-data = e;p-next = S-top;S-top = p;return OK;,111,3.1 栈 （stack）,链栈的出栈算法,出栈等同于删除第一个结点Status Pop(LinkList * S,datatype *e )If(S-top=NULL) return ERROR;/*下溢*/
25、p = S-top;S-top = p-next;*e = p-data;free(p);return OK;,112,3.1 栈 （stack）,3.1.3 栈的应用,(1)“回溯”问题求解 (2) 过程的嵌套和递归调用,113,1嵌套调用,3.1 栈 （stack）,3.1.3 栈的应用,114,s,3.1 栈 （stack）,嵌套调用过程图示,115,递归：函数直接或间接的调用自身的过程 一个对象部分地包含它自己，或是用它自己给自己定义 一个过程直接地或间接地调用自己 利用前面运算来求得答案的过程实现：建立递归工作栈优点：递归函数结构清晰，程序易读，正确性易证明缺点：速度慢，空间大效率低
26、,3.1 栈 （stack）,2递归调用,116,3.1 栈 （stack）,void p (参数表) if （递归结束条件）可直接求解步骤；-基本项 else p（较小的参数）；-归纳项 ,递归算法的一般形式,117,3.1 栈 （stack）,例：求n! =,1， n=0n*(n-1)！ n0,int Factorial(int n) if (n=0) return 1; return n*Factorial(n-1);,118,例 ：递归的执行情况分析,3.1 栈 （stack）,119,void print(Int w) int i; if ( w!=0) print(w-1); for(i=1;idata = x;p-next = NULL;Q-rear-next = p;Q-rear = p;,131,3.2 队列（QUEUE）,
