《数据结构总复习》由会员分享，可在线阅读，更多相关《数据结构总复习（92页珍藏版）》请在金锄头文库上搜索。
1、复习,算 法 (Algorithm) 定 义,解决某一特定问题的具体步骤的描述，是指令的有限、有序序列。,算 法 的 特 性,一,算法设计的要求,正确性 可读性 健壮性(鲁棒性) 高效率与低存储量,时 间 复 杂 度,算法中基本操作重复执行的次数的阶数,记做 T(n)=O(f(n).例如 1. x=x+1; 时间复杂度为O(1),称为常量阶 2. for(i=1;i=n;i+) x=x+1;时间复杂度为O(n),称为线性阶 3. for(i=1;i=n;i+) for(j=1;j=n;j+)x=x+1; 时间复杂度为O(n2),称为平方阶 4.for(i=1;i=n;i+)for(j=1;j=
2、n;j+)cij=0; for(k=1;kx,P17,应用,1. 线性表中的元素值按递增有序排列，针对顺序表存储方式，编写算法删除线性表中值介于a与b（ab）之间的元素。 先写出结构体。 顺序表： 算法思想：从0开始扫描线性表，用r记录下元素值在a与b之间的元素个数，对于不满足该条件的元素，前移r个位置，最后修改线性表的长度。,1,3,78,0,1,n-1,有序表,V数组下标,M-1,a=8,b=20,9,38,40,#define MaxLen 100 typedef struct elemtype elemMaxLen; int length;SeqList; SeqList Q;,voi
3、d del（SeqList *L,elemtype a，elemtype b） int i=0，r=0； While(i=a ,顺序存储结构的优缺点：优点 逻辑相邻，物理相邻 可随机存取任一元素 缺点 插入、删除操作需要移动大量的元素,C语言实现,2.3链表 线性链表定义及C语言实现 定义：结点中只含一个指针域的链表叫，也叫单链表,typedef struct node elementtype data; / 数据域struct node *next; / 指针域 node, *LinkList;,LinkList L； / L 为单链表的头指针,s-next=p-next;,p-next=s
4、;,/在带头结点的单链线性表L中第i个位置之前插入元素e Status ListInsert_L(LinkList /ListInsert_L,插入：在线性表两个数据元素a和b间插入x，已知p指向a,s-next=p-next;,p-next=s;,p-next=p-next-next;,/在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 Status ListDelete_L(LinkList /ListDelete_L,删除：单链表中删除b，设p指向a,L,第i个,e=f,某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环 链表，每个结点有价格、数量和链指针三个域。
5、现出库（销售）m台价格 为h的电视机，试编写算法修改原链表。,typedef struct snode float price;int num;struct sonde *next; tvnode;,变量名称可以自己设定，但是根据软件设计的要求，最好是能“见名思义”。,算法演示,void del(tvnode *head,float price,int num) q=head;p=head-next; while(q-pricenext; if(p-price=price) p-num=p-num-num; else printf(“无此产品“); if(p-num=0) q-next=p-n
6、ext; free(q); ,head,4假设带头结点的单链表，头指针为head，head表中的结点是按值非递减有序排列。编写一算法，将值为x的结点插入表head中，使得插入后的表head 仍然有序。（要求先写出存储结构。） 结点结构为,本章小节：,掌握的操作：顺序存储结构：数据类型的定义、初始化、插入、删除、查找 单链式存储结构：数据类型的定义、初始化、插入、删除、查找 循环链表、双向链表的特点,第三章 栈和队列,本章学习两种特殊的线性数据结构，它们特殊在定义的操作不同，即插入和删除操作只能在线性表的两端进行。只能在一端进行的栈 分别在两端进行的队列,小 结,顺序栈4要素 栈空：Ss_top
7、=-1 栈满：Ss_top=MAXSIZE-1 进栈操作：Ss_top+; SsSs_top=x; 出栈操作:x=SsSs_top;Ss_top-;,void conversion( ) initstack(s);scanf (“%”,n);while(n) push(s,n%8);n=n/8; while(! Stackempty(s) pop(s,e);printf(“%d”,e);,如：十进制数转化为二进制数,链栈4要素 栈空：top= =NULL 栈满：不存在 进栈操作：p-next=top; top=p; 出栈操作:top=top-next; free(q);,约定：非空队中，头指针
8、始终指向队列头元素的前一个元素，而尾指针始终指向队列尾元素。,J1,J2,J3,rear,J4,J5,J6入队,J4,J5,J6,front,设两个指针front,rear,约定： rear指示队尾元素； front指示队头元素位置 初值front=rear=0,空队列条件：front=rear 入队列：Q.data+rear=x; 出队列：x=Q.data+front;,J3,循环队列 基本思想：把队列设想成环形，让Q.data0接在Q.dataM-1之后，若rear+1=M,则令rear=0;,实现：利用“模”运算 入队： rear=(rear+1)%M; Q.dataQ.rear=x;
9、出队： front=(front+1)%M; x=Q.dataQ.front;,z,y,x,front,rear,x,y,z,rear,front,法一： if (rear=maxsize-1) rear=0;else rear+; 或： rear=(rear=maxsize-1)? 0:rear+1;,A,在Q.rear和Q.front可以循环指示时，如何判断队列的空和满？牺牲一个存储空间: 令：Q.rear = = Q.front 为空 令：(Q.rear + 1)% maxsize = = Q.front 为满,rear,front,队列为满,c,b,v,u,front,rear,c,d
10、,w,q,rear,front,队列为空,队满、队空判定条件,2顺序队列的基本运算算法(循环队) （1）入队列操作 Insert_Cq(Cq, Cq_rear, Cq_front, Cq_max, x) /插入元素x为Q的新的队尾元素 if ( (Cq_rear +1)%Cq_max) = Cq_front ) return ERROR;/队满Cq_rear = (Cq_rear +1)%Cq_max ; CqCq_rear = x ; return OK; ,x,y,m,x为m x为f,f,（2）出队列操作Delete_Cq(Cq, Cq_front, Cq_rear, Cq_max, x)
11、 if (Cq_front = Cq_rear) printf (“ The circular queue is empty!“) ;return Error;Cq_front = (Cq_front +1)%Cq_max ;x = CqCq_front ; ,x,y,m,出队队位号： Cq_front = (Cq_front +1)%Cq_max,(3)：判断队列为空int empty ( seqqueue Q) if (Q.front = = Q.rear)printf(“the queue is empty!”);return(1);else printf (“the queue is not empty!”);return (0); ,循环队中元素的个数:,(rear-front+maxsize)%maxsize,z,y,x,front,rear,x,y,z,rear,front,串,数据元素都是来自字符集 由于数据元素的特殊，它的操作有些不同与一般线性表，例如：操作对象一般是对子串（即一组数据元素）而不是单个数据元素。,本章学习另一种特殊的线性表，它特殊在：,
