主要内容： 1.第一部分 概述 2.第二部分 线性表、栈、队列

Presentation on theme: "主要内容： 1.第一部分 概述 2.第二部分 线性表、栈、队列"— Presentation transcript:

1 主要内容： 1.第一部分 概述 2.第二部分 线性表、栈、队列
数据结构学位考 复习课(1) 主要内容： 1.第一部分 概述 2.第二部分 线性表、栈、队列

2 第一部分：数据结构与算法的基本概念 考核内容及要求： 理解算法、算法正确性、复杂性的概念； 了解算法的时间与空间复杂性级别；
重点掌握数据类型、数据结构和表示、实现的概念； 掌握抽象数据类型的说明、高级语言对抽象数据类型的支持。

3 基本概念和术语 数据结构：数据元素之间的关系——结构 数据(Data)： 数据元素(Data Element)：
数据的基本单位，计算机中通常作为一个整体来考虑，如一棵树中的一个结点、一个图中的一个结点。 一个数据元素可以有若干个数据项(Data Item)组成。 数据对象(Data Object)：性质相同的数据元素的集合 数据结构：数据元素之间的关系——结构 四种基本结构 集合 线性结构 树形结构 图状结构/网状结构 数据结构的形式定义： 一个二元组： Data_Structure=(D,S) 其中：D是数据元素的集合，S是D上的关系集合

4 数据的逻辑、物理（存储）结构 数据结构的分类： 逻辑结构：数据元素之间的逻辑关系 物理结构：数据元素在计算机中的存储方法（表现和实现）
按照逻辑结构的不同分为：集合、线性结构、树状结构、网状结构 按照物理结构的不同分为： 顺序结构：利用在存储器中的物理关系来表示逻辑关系。 链式结构：用在存储器中附加指针的方式来表示逻辑关系。

5 算法：对特定问题求解步骤的一种描述，是指令的有序序列
算法的五个特性：有穷性、确定性、可行性、输入、输出 算法设计的要求：时间复杂度，空间复杂度

6 时间复杂度：算法执行时间随规模增长而增长的趋势
T(n)=O(f(n)) f(n)算法规模，T(n)称算法复杂度 估算办法：以算法中重复执行的次数作 为算法时间复杂度的依据。 三种最常见时间复杂度： O(1) 常量级 O(n) 线性级 O(n2) 平方级

7 算法的空间复杂度 S(n)=O(f(n)) 算法执行过程中所需的最大空间 估算方法：输入数据所占空间+ 程序所占空间+ 辅助变量所占空间

8 第二部分 线性表、栈、队列 考核内容及要求： 熟练掌握顺序分配、链接分配的表示及实现方法； 熟练掌握各种链表：单链、双链、多链、循环链表；
理解栈、队列、双向队列的顺序、链式表示及其算法复杂度分析； 熟练掌握表达式计算原理。

9 1. 线性表的顺序表示和实现 线性表的存储结构：顺序存储、链接存储 顺序存储：用一组地址连续的存储单元依次存储线性表的数据元素。 a1 a2
ai an b b+l b+(i-1)l b+(n-1)l b+nl 存储地址 存储内容 顺序存储结构 基地址：起始位置 第i个元素的位置LOC(ai)=LOC(a1)+(i-1)*l l：每个元素占用的存储单元

10 顺序表的特点 （1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构于存储结构（物理结构）一致；
（2）在访问线性表时，可以利用上述给出的数学公式，快速计算任何一个数据元素的存储地址。即访问每个数据元素所花费的时间相等。 （3）这种存取元素的方法被称为随机存取法。使用这种存取方法的存储结构被称为随机存储结构。

11 表示方法： 在高级语言中，用一维数组表示： 表示方法： const LIST_INIT_SIZE=100; //表初始分配空间
　表示方法： 　const LIST_INIT_SIZE=100; //表初始分配空间 const LISTINCREMENT=10;//空间分配增量 typedef struct{ ElemType *elem;　//存储空间 int length; //当前长度 int listsize; //当前存储容量 int LISTINCREMENT;//可增加存储空间 }SqList; 注意： 1. 数组指针elem指示线性表的基地址，length:线性表的当前长度。 2. C语言数组的下标从0开始，即数组中的第i个元素为L.elem[i-1]

12 2. 线性表的链式表示和实现 顺序表的局限：插入、删除时要移动大量的元素，耗费大量时间。 链式表示：用一组任意的存储单元存储线性表
存储单元不要求连续：物理结构不反应逻辑结构 不可以随机存取，但插入和删除方便 需要两个域：一个表示数据本身；一个表示数据元素间的先后关联。——一个结点。 结点中表示关联的部分为指针域，内部存放指针或链。n个结点链接成一个链表。

13 线性链表 线性链表的物理存储结构 (Zhao,Qian,Sun,Li,Zhou,Wu,Zheng,Wang) L ^ Zhao Qian
数据域 指针域 存储地址 1 7 13 19 25 31 37 43 49 31 头指针 L Zhao Qian Sun Wang ^

14 线性链表（单链表）的定义： typedef struct LNode{ ElemType data; struct Lnode *next;
}Lnode, *LinkList L a1 ai ai-1 an ^ 带头结点的链表 L a1 ai ai-1 an ^

15 循环链表 循环链表：线性表的另一种链式存储结构。 H H 特点： 操作与单链表的差别： 从表的任何位置出发，都可以找到其他结点；
a1 an H 循环链表 空表 特点： 从表的任何位置出发，都可以找到其他结点； 操作与单链表的差别： 判断表尾的条件：P->next=H

16 双向链表 每一个结点有两个指针域：一个指向直接后继；另一个指向直接前驱。 H ^ H ^ 双向链表存储结构：
a1 a2 ^ H ^ 双向链表存储结构： typedef struct DuLNode{ ElemType data; struct DuLNode *prior; struct DuLNode *next; }DuLNode, *DuLinkList;

17 双向循环链表 H a1 a2 2个结点的双向循环链表 H 空的双向循环链表

18 3.栈的表示和实现 栈的表示： （1）顺序栈：栈的顺序存储 （2）链栈：栈的动态存储

19 顺序栈的表示和实现 顺序表示 #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; 　其中stacksize表示栈当前可以使用的最大容量。base为栈底，top为栈顶。栈顶指针指向栈顶元素的下一个位置（即下次压栈时元素所放的位置）

20 顺序栈的结构 top指向压栈时下一个元素将要存放的位置。 top减一指向弹栈时下一个元素的取值位置。 栈空的条件：top=base
空栈 非空非满栈 A B C 满栈 D E top指向压栈时下一个元素将要存放的位置。 top减一指向弹栈时下一个元素的取值位置。 栈空的条件：top=base 栈满的条件：top-base >= stacksize

21 链栈的结构和表示 定义栈结构 Typedef struct stack_node { elemtype data;
struct stack_node *next; } STKPTR; STKPTR *stk; 问：在这里为什么没有用到top指针？这样对栈结构的定义有否影响？ 1 ^ 7 2 8 S 栈顶 栈底

22 4.队列的表示和实现 链式队列 typedef struct Qnode { QElemType data;
struct Qnode *next; }Qnode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; 课堂练习：链队列的操作入对列、出队列 Q.front Q.rear ^ 链队列结构

23 #define MAXQSIZE 100 顺序队列 typedef struct { QElemType *base; int front;
int rear; }SqQueue; 其中base为连续空间首地址，front为队首，rear为队尾。

24 顺序队列的结构——循环队列： 为什么用循环队列来实现顺序队列？ rear rear rear front 非空非满队1 rear A B C
D D C C front front front 空队 非空非满队2 满队 空队：初始化队列时，两个指针rear＝front＝0 入队：队尾插入元素，尾指针rear后移 出队：队头删除元素，头指针front后移 为什么用循环队列来实现顺序队列？

25 循环队列： 实现循环队列的操作： 关键问题1：rear和front指针后移 (Q.rear+1) mod MAXSIZE
1 front rear Q.rear 指向入队时下一个元素的存放位置 Q.front指向出队时下一个元素的存放位置 实现循环队列的操作： 关键问题1：rear和front指针后移 (Q.rear+1) mod MAXSIZE (Q.front+1) mod MAXSIZE

26 出队时，判断空队 Q.rear = = Q.front;
1 rear front 1 front rear 空队列 满队列 关键问题2： 出队时，判断空队 Q.rear = = Q.front; 入队时，判断满队 (Q.rear+1)mod MAXSIZE= = Q.front;

27 典型例题 1. 顺序表中逻辑上相邻的元素物理位置 相邻， 单链表中逻辑上相邻的元素物理位置 相邻。
1. 顺序表中逻辑上相邻的元素物理位置 相邻， 单链表中逻辑上相邻的元素物理位置 相邻。 2. 已知P为单链表中的非首尾结点，在P结点后 插入S结点的语句为： 也 不一定 S->next=P->next; P->next=S 3. 在单链表中，指针P所指的节点为最后一个节点的条件是： 4.设head指向单链表的表头，p指向单链表的表尾结点，则执行p->next=head后，该单链表构成 P->next=NULL 循环链表

28 2.5 画出执行下列各行语句后各指针及链表的示意图
L=(LinkList)malloc(sizeof(LNode)); P=L; for (i=1;i<=4;i++){ P->next=(LinkList) malloc(sizeof(LNode)); P=P->next; P->data=i*2-1; } P->next=NULL; for (i=4;i>=1;i--) Ins_LinkLIst(L,i+1;i*2); for (i=1;i<=3;i++) Del_LinkList(L,i);

29 2.8 已知P结点是双向链表的中间结点，试写出下列操作的语句序列： (1)在P结点后插入s结点 (2)在P结点前插入s结点
(3) R=P->next; P->next=R->next; R->next->prior=R->prior; free(R); S->next=P->next; S->prior=P; p->next->prior=S; P->next=S; (4) R=P->prior; P->prior=R->prior; R ->prior ->next=R->next; free(R); (2) S->next=P; S->prior=P->prior; p ->prior ->next=S; P->prior=S; (5) P->prior->next=P->next; P->next->prior=P->prior; free(R);

30 设rear是指向非空带头节点的单循环链表的尾指针，则写出删除表首结点的操作的语句序列
答案： P=rear->next->next; Rear->next->next=p->next; Free(P);

31 2.33已知一个线性链表表示的线性表中含有三类字符的数据元素（如字母、数字、和其他），试编写算法将该线性链表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。
要求：充分用原来的存储空间； 问题：如果要求建立3个单链表；也利用原来的存储空间

32 Status D_S_2.33(LinkList &L;DuLinkList &La; L;DuLinkList &Lb; L;DuLinkList &Lc)
{ if (!(La=(DuLinkList)malloc(sizeof(DuNode))))return ERROR; if (!(Lb=(DuLinkList)malloc(sizeof(DuNode))))return ERROR; Lc=L; a=La; b=Lb; q=L;p=L->next; while (p){ if (p->data IN 字母字符集){q=p;p=p->next} if (p->data IN 数字字符集){ q->next=p->next; //将p结点从L中删除 a->next=p; a=p; //将p结点插入到La的末尾； p=q->next; } //重置指针p if (p->data IN 其他字符集){q->next=p->next; //将p结点从L中删除 b->next=p; b=p; //将p结点插入到Lb的末尾； p=q->next} //重置指针p } q->next=Lc; //使Lc为循环链表 a->next=La; //使La为循环链表 b->next=Lb; //使Lb为循环链表

33 2.22 单链表的就地逆置：利用原来的存储空间。 Status D_S_2.22(LinkList &L){
p=L->next; L->next=null; while (p){ q=p; p=p->next; } 答案： q->next=L->next; L->next=q;

34 算法设计题 线性表类型定义 顺序表： 单链表 typedef struct Lnode {
ElemType data; Struct Lnode *next; }Lnode, *LinkList; 顺序表： #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { ElemType *elem; int length; int listsize; }SqList;

35 4.(2.19) 已知线性单链表中的元素以值递增有序排列，试写一个高效的算法，删除表中所有介于（mink,maxk）的元素。（***）
c e g i o q ^ L P (mink,maxk)=(h,o) 查找第一个大于mink的结点P->next while (P->next->data<maxk) 则：删除P->next

36 Status LL_DEL(LinkList &L,ElemType mink,ElemType maxk)
{//删除大于mink小于maxk的所有元素,L是带头结点的单链表 P=L; while (P->next!=NULL &&P->next->data<=mink) P=P->next;//找出第一个大于mink的元素 if P->next=NULL return error; Q=P->next; while (!Q &&Q->data<maxk){ P->next=Q->next; dispose(Q); Q=P->next; } }//LL_DEL c e g i o q ^ L (mink,maxk)=(h,o)

37 5.(2.24) 假设有两个按值递增有序排列的单链表A和B，编写算法归并A和B成C，使得C是按值递减有序排列（允许有值重复的结点），并且C利用A、B原来的结点空间。（****）
p 3 5 7 19 ^ A q 4 6 8 20 ^ B 4 3 C

38 Status UNIT_A_B(LinkList &A,&B,&C){
//合并A和B成C，C利用A、B原来的结点空间。 P=A->next; q=B->next; C=B,C->next=NULL; free(A); //初始化C While (!p&&!q){ if (p->data<=q->data){s=p;p=p->next} else{s=q;q=q->next} s->next=C->next;C->next=s;//s结点插入到C的首结点之前； } if (!q) p=q; While (!p) {s=p;p=p->next;s->next=C->next;C->next=s} }//UNIT_A_B

39 栈与队列的相关习题 1.栈与线性表的差别 2.队列与栈两种数据类型的相同点和差异
3.(3.4)分析以下算法的功能(SElemType为int) Status algo1(Stack S){ int I,n,A[255]; n=0; while (! StackEmpty(S)){n++;Pop(S,A[n])}; for (i=1;i<=n;i++) Push(S,A[i]); } 算法功能：将栈S中的元素逆置

40 算法功能：删除栈S中与e相等的元素 (2)Status algo2（Stack S,int e）{ Stack T; int d;
InitStack(T); while (! StackEmpty(S)){ Pop(S,d); if (d!=e) Push(T,d); } while(! StackEmpty(T)){ Pop(T,d); Push(S,d); 算法功能：删除栈S中与e相等的元素

41 while (!QueueEmpty(Q)){ DeQueue(Q,d); Push(S,d); }
4.（3.13）简述下列算法的功能 void algo3(Queue &Q){ Stach S; int d; InitStack (S); while (!QueueEmpty(Q)){ DeQueue(Q,d); Push(S,d); } while(!StackEmlpty(S)){ Pop(S,d); EnQueue(Q,d); 算法功能：将队列Q中的元素逆置

42 算法设计题 顺序栈 #define STACK_INIT_SIZE 100; 类型定义：
#define STACKINCREMENT 10; typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack

43 顺序循环队列： #define MAXQSIZE 100; typedef struct { QElemType *base; int front; int rear; }SqQueue;

44 3.15 假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这两个双向栈的操作的算法：初始化inistack(tws)、入栈push(tws,i,x)、出栈pop(tws,i)。并讨论按过程或函数设计这些操作算法各有什么优缺点。 分析： 栈的一般状态 Tws firtop sectop 初始化 Tws top1 top2 Length=100; Typedef struct { datatype data[Length] int top1,top2} Twins 还有最后一个存储空间 Tws top1 top2

45 else top1--;return tws.data[top1]} if i=1 if ERROR else{ } }
Pop(twins tws;int i ){ if i=0 if top1=0 ERROR else top1--;return tws.data[top1]} if i=1 if ERROR else{ } } top2=Length-1 top2++;return tws.data[top2]

46 c.当字符为&时，依次读下面的字符，并与出栈元素比较。有一个不相等，则ERROR
且序列2是序列1的逆序列。如‘a+b&b+a’ 分析：算法中采用何种数据类型？线性表、栈、队列？ a.初始化一个栈S， b.依次读入字符，并压栈 c.当字符为&时，依次读下面的字符，并与出栈元素比较。有一个不相等，则ERROR d.字符结束时，栈空,则OK。否则ERROR

47 int symmetry() //为不对称。 InitStack(s); scanf(ch); while (ch <> “&”){ push(s, ch); scanf(ch);} scanf(ch); pop(s,x); while (ch <> &&!empey(s)) { if (ch= = x) {scanf(ch); pop(s,x);} else return 0; } if (ch = = && empty(s)) return 1; else return 0; }//symmetry

48 P->next=R->next Free(R) 问：若R＝Q.rear,如何？
6(3.28).假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(不设头指针)，编写相应的队列初始化、入队和出队的算法。 Q.rear Q.rear 出队操作： P=Q.rear->next R=P->next P->next=R->next Free(R) 问：若R＝Q.rear,如何？ 初始化：Q.rear->next=Q.rear 入队：new p p->next=Q.rear->next Q.rear->next=p

49 出队算法： Status DeQu(LinkQueue &Q,ElemType &e){ if Q.rear->next=Q.rear return ERROR; P=Q.rear->next; R=P->next; P->next=R->next; e=R->data; if R=Q.rear Q.rear=P; free(R) } 课堂练习：写出入队算法

50 Fib(n)= 1 Fib(n-1)+fib(n-2) n=0 n=1 n>1 算法：初始化队列new Q.base;Q.rear=0
7.(3.32)利用循环队列编写求K阶Fabonacci数列中前n+1项(f0,f1,···,fn)的算法。要求：fn<=max,fn+1>max,其中max是某个约定的常数（注意：循环队列的最大容量是K,结束时队列中应该存放的是数列的后k项）。 Fib(n)= 1 Fib(n-1)+fib(n-2) n=0 n=1 n>1 算法：初始化队列new Q.base;Q.rear=0 f=Q.base[Q.rear-1]+ Q.base[Q.rear-2] if f<=max,则f入队。

51 算法 Status Fabonacci(int K,SqQueue &Q;int MAX){ Q.base=(QE.emtype*) malloc(K*sizeof(QElemType)); if (!Q.base) exit(OVERFLOW); Q.base[0]=0;Q.base[1]=1;Q.rear=2;f=1; while (f<=MAX){ Q.base[Q.rear]=f; Q.rear=(Q.rear+1)%K; i=(Q.rear-1+K)%K; j=(Q.rear-2+K)%K; f=Q.base[i]+Q.base[j]; }

52 8(3.33). 在顺序存储结构上实现输出受限的双端循环队列的入列和出列（只允许队头出列）算法。设每个元素表示一个待处理的作业，元素值表示作业的预算时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。 分析：用顺序队列实现。 出队列与普通队列没有区别； 入队：元素值<平均值，队头入队（优先考虑） 元素值>=平均值，队尾入队

53 Status EnQueue(SqQueue &Q, QElemType e)
{ //插入受限，小于平均时间入队头，否则入队尾 　　if ((Q.rear+1) %MAXQSIZE = = Q.front) return ERROR; //队列满 t = Q.base[Q.front]+Q.base[(Q.rear-1) %MAXQSIZE]/2 if (e <t) { if (Q.front == 0) Q.front = MAXQSIZE-1; else Q.front = Q.front –1; Q.base[Q.front] = e;} else { Q.base[Q.rear] = e; 　　 Q.rear = (Q.rear+1) %MAXQSIZE;} return OK; }//EnQueue

54 Status DeQueue(SqQueue &Q, QElemType &e)
{ if (Q.front = = Q.rear) return ERROR; e = Q.base[Q.front]; Q.front = (Q.front+1)%MAXSIZE; return OK; }