当前位置：文档之家 › 西安电子科技大学数据结构课件复习

西安电子科技大学数据结构课件复习

  • 格式：pdf
  • 大小：525.48 KB
  • 文档页数：43

下载文档原格式

  / 43

合集下载

电子科大 数据结构 课件

电子科大 数据结构 课件
return 1; }
2013年12月10日7时42分
Design By Chen Anlong
12
顺序表的插入
在表中第 i 个元素之前插入一个元素 x, 插入前：
0
1
2
i-1 i
n
a1
a2 …… ai-1
ai …… an
后移一个位置
在第i个位置插入一个元素x后的状态：
012
i-1 i
n n+1
a1
for(i=len;i>=pos;i--) L->elem[i+1] = L->elem[i]; /* 后移一个位置*/ L->elem[pos] = elem; L->length ++; /* 表长加1 */ status = success; } return status; }
2013年12月10日7时42分
}; typedef struct list List;
数据区
ai La.elem[i] …
List La; List *Lp; typedef struct list *ListPtr;
an La.elem[n] …
ListPtr Lp; < ------定义指针变量
La.elem[MAXSIZE]
9
指针表示法
为了编程实现和理解的方便，更多采用如下结构
typedef struct list { ElemType *elem; int length; int MaxSize; } List, *ListPtr;
Length为线性表的当前长度。 Maxsize为当前分配给线性表的存储空间 指针变量elem指向线性表的基地址。

西安电子科技大学_计算机组成与体系结构_第3章运算方法与运算器_课件PPT

西安电子科技大学_计算机组成与体系结构_第3章运算方法与运算器_课件PPT

17
3.1.1 加减运算 4. n位加法器的实现
2) 先行进位加法器
三级门的延时
P3* G3*
C4
C3
C2
C1
≥1
≥1
≥1
≥1
≥1
＆
＆＆ ＆
＆
＆＆ ＆
＆＆
＆
G3
＆
X3 Y3
P3
≥1
X3 Y3
G2
＆
X2 Y2
P2
≥1
G1 P1
＆ ≥1
G0 P0
＆ ≥1
X2 Y2 X1 Y1 X1 Y1 X0 Y0 X0 Y0 C0
x xxxxxxx
10
3.1.1 加减运算 2. 溢出判断 3) 根据运算结果的符号位和进位标志判别
适用于两同号数求和或异号数求差时判别溢出。溢出 的逻辑表达式为：
VF＝SF⊕CF
0 xxxxxxx 1 xxxxxxx ＋ 0 xxxxxxx ＋ 1 xxxxxxx
c s xxxxxxx c s xxxxxxx
01100010 …98
11000001 … －63 ＋ 11011101 …11111 … 63 ＋ 11011101 … －35
100011100 … 28
7
3.1.1 加减运算 2. 溢出判断
当两个同符号的数相加（或者是相异符号数相减）
时，运算结果可能发生溢出。 00111111 …63
补码一位乘法：校正法，布斯(Booth)法
补码二位乘法
阵列乘法器
适于流水线工作的阵列乘法器
32
3.1.2 乘法运算 1. 原码乘法运算
1) 原码一位乘法的法则 假定被乘数X和乘数Y为用原码表示的纯小数，

《复习提纲数据结构》课件

《复习提纲数据结构》课件

数据结构组成
数据结构由数据元素和它们之间的 关系组成，这些关系决定了数据元 素之间的逻辑关系。
数据结构分类
数据结构可以根据不同的分类标准 进行分类，如线性结构和非线性结 构、静态结构和动态结构等。
数据结构的重要性
01
02
03
提高数据处理效率
合理的数据结构能够提高 数据处理的速度和效率， 使得数据处理更加高效。
图的应用
图在计算机科学中有着广泛的应用， 如社交网络、路由算法、搜索引擎等 。
哈希表
哈希表的概念
哈希表是一种通过哈希函数将键映射到 桶中的数据结构，用于快速查找和存储
键值对。
哈希冲突的处理
当两个不同的键被映射到同一个桶时 ，会发生哈希冲突。常见的处理方式
有链地址法和开放地址法。
哈希表的性能分析
哈希表的查找、插入、删除等操作的 时间复杂度主要由哈希函数的设计和 哈希表的负载因子决定。
链式插入
在链式存储结构中，插入操作需要定位到插入位置的节点 ，并在其后插入新节点，同时修改指针。
AVL树的插入
在AVL树中，插入操作需要先找到合适的空位，然后将新 节点插入到该位置，并调整树的结构以保持平衡。
删除操作
顺序删除
在顺序存储结构的线性表中，删除操作需要定位到要删除的元素，然 后将其后一位元素覆盖到要删除的位置，并减少数组长度。
06
数据结构性能分析
时间复杂度分析
时间复杂度概念
时间复杂度是衡量算法执行时间随输入规模 增长而增长的量度，通常用大O表示法表示 。
时间复杂度分类
根据算法的时间复杂度，可以将算法分为线性时间 复杂度、多项式时间复杂度和指数时间复杂度。
时间复杂度分析方法

西安电子科技大学数据结构期末复习题

西安电子科技大学数据结构期末复习题

西安电子科技大学《数据结构》复习题（含部分参考答案版）一、单项选择题1. 按照数据逻辑结构的不同，可以将数据结构分成 C 。

A. 动态结构和静态结构B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构D. 内部结构和外部结构2. 下列关于数据结构的叙述中正确的是 A 。

A. 数组是同类型值的集合B. 递归算法的程序结构比迭代算法的程序结构更为复杂C. 树是一种线性的数据结构D. 用一维数组存储二叉树，总是以先序顺序遍历各结点3. 在计算机的存储器中表示时，物理地址与逻辑地址相同并且是连续的，称之为BA.逻辑结构B.顺序存储结构C.链式存储结构D.以上都不对4. 以下关于算法特性的描述中， B 是正确的。

（1）算法至少有一个输入和一个输出（2）算法至少有一个输出但是可以没有输入（3）算法可以永远运行下去A. （1）B. （2）C. （3）D. （2）和（3）5. 对顺序存储的线性表（a1,a2,…,a n）进行插入操作的时间复杂度是 C 。

A.O(n)B. O(n-i)C. (n/2)D. O(n-1)6. 链表不具有的特点是A 。

A.可随机访问任一元素B.插入和删除时不需要移动元素C.不必事先估计存储空间D.所需空间与线性表的长度成正比7.线性链表中各链结点之间的地址 C 。

A.必须连续B.部分地址必须连续C.不一定连续D.连续与否无关8. 以下关于链式存储结构的叙述中， C 是不正确的。

A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构B.逻辑上相邻的结点物理上不必邻接C.可以通过计算直接确定第i个结点的存储地址D.插入、删除操作方便，不必移动结点9. 设依次进入一个栈的元素序列为d, a, c, b,得不到出栈的元素序列为D 。

A. dcbaB. acdbC. abcdD. cbda10. 将新元素插入到链式队列中时，新元素只能插入到 B 。

A. 链头B. 链尾C. 链中D. 第i个位置，i大于等于1，大于等于表长加111. 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、和e1，则栈S容量至少应该是 C 。

西安电子科技大学_数据结构_第十章内部排序_课件PPT

西安电子科技大学_数据结构_第十章内部排序_课件PPT

初始关键字序列：
12345678 49 38 65 97 76 13 27 49*
第一趟排序后：
38 49 65 76 13 27 49* 97
第二趟排序后：
38 49 65 13 27 49* 76 97
第三趟排序后：
38 49 13 27 49* 65 76 97
第四趟排序后：
38 13 27 49 49* 65 76 97
10.2 希尔排序算法
void ShellInsert(SqList &L,int dk) {//对顺序表L作一+i 1<i=<L=.eLn.getnhg;tih+;+i+) +)
iiff((LL..rr[[ii]]..kkeeyy<<LL..rr[[ii--d1k]]..kkeeyy)){{//需将L.r[i]插入有序增量子表
10.1 排序的基本概念(续)
正序与逆序
➢ 若有序表是按排序码升序排列的，则称为升序表或正序 表，否则称为降序表或逆序表。不失普遍性，我们一般 只讨论正序表。
排序方法度量
➢ 排序过程主要是比较记录的关键字和移动记录。因此排 序的时间复杂性可以算法执行中的数据比较次数及数据 移动次数来衡量。当一种排序方法使排序过程在最坏或 平均情况下所进行的比较和移动次数越少，则认为该方 法的时间复杂性就越好。
L.r[j+1] = L.r[j];
L.r[j+1] = L.r[0]; }//if
最好情况} 下// (I正ns序er)tSort
最坏情况下(逆序)
元素的❖ 比分较析次直数接为插: 入n 排- 1序算法中关键元字素的的比比较较次次数数和: 记(录n+移2动)(次n-数1)/2

电子科技大学数据结构第3章

电子科技大学数据结构第3章
A B C
D
E
F
G
H
数据结构@UESTC 电子科技大学 · 计算机科学 · 数据结构与算法 ·
基本概念
– 基本概念
• 满二叉树——在一棵二叉树中，如果所有分支结点都存在左子树和右子 树，并且所有叶子结点都在同一层上。 一棵满二叉树一定是一棵完 • 完全二叉树——对深度为k的满二叉树中的结点从上至下，从左至右从1 全二叉树，但一棵完全二叉 开始连续编号。对一棵具有n个结点深度为 k的二叉树，采用同样办法对 树中结点从上至下，从左至右从1开始连续编号，如果编号为 i（i<=n） 树未必是一棵满二叉树 的结点都与满二叉树中编号为i的结点在同一位置，则称此二叉树为一棵 完全二叉树。
typedef struct BiTreeNode{ Datatype data; struct BiTreeNode *lchild, *rchild, *parent; }BiTreeNode, *BiTree;
20 数据结构@UESTC
电子科技大学 · 计算机科学 · 数据结构与算法 ·
三叉链表
△ △ B * ★
深入返回的过程满足栈的特征，可用栈实现二叉树的 △ △ 遍历 D ★ F ★ △ E
C * * * ★ △ * G ★ △ *
A ★ *
★
28 数据结构@UESTC
电子科技大学 · 计算机科学 · 数据结构与算法 ·
– 二叉树的非递归遍历
• 例子：中序遍历非递归算法
p
p p
C p=NULL p p E B
电子科技大学 · 计算机科学 · 数据结构与算法 ·
链式存储结构
A
头指针bt
C
B
A
D

PowerPoint演示文稿西安电子科技大学(精)

PowerPoint演示文稿西安电子科技大学(精)

第 1章 绪 论
数据结构的内容
集合
1. 逻辑结构 数据元素之 间的关系 。 逻辑结构可 看作是从具 体问题抽象 出来的数学 模型。
线性表
树
图
第 1章 绪 论
学 校
系
处
研 究机 构
教 研室
实 验室
1
图1.2 学校组织层次结构图
2
5 4
3
图1.3 交通流量图
第 1章 绪 论
2. 存储结构（物理结构） 逻辑结构在计算机中的存储映象，是逻 辑结构在计算机中的实现，它包括数据 元素的表示和关系的表示。
顺序映象 （顺序存储结构） 非顺序映象（非顺序存储结构）
第 1章 绪 论
逻辑结构与存储结构的关系
存储结构是逻辑结构用计算机语言的实现； 如何用计算机语言表示数据元素之间的各种关系。 存储结构是逻辑关系的映象与元素本身的映象。逻辑结构是数
据结构的抽象，存储结构是数据结构的实现，两者综合起来建
第 1章 绪 论
第1章 绪论
1.1 什么是数据结构（定义） 1.2 数据结构的内容 1.3 算法 1.4 算法描述的工具 1.5 对算法作性能评价 1.6 关于学习数据结构
第 1章 绪 论
1.1 什么是数据结构（定义）
• 计算机的解题步骤
1、抽象出一个适当的数学模型； 2、设计解此数学模型的算法； 3、编写程序、测试、调整直到得到最终解答。
A
F
B
小张
小刘 小李
A
C C
B
D E
E
E C F
小红
小强
D
B
F
F
A
D
第 1章 绪 论
5. 数据类型(Data Type)

第4章 图 电子科大 数据结构 课件汇编

第4章 图 电子科大 数据结构 课件汇编
数据结构与算法
主讲人：陈安龙
电子科技大学信息与软件工程学院
2021年3月8日5时44分
Design By Chen Anlong
1
第四章 图
图的基本概念 图的常用存储结构 图的基本运算 图的基本应用
2021年3月8日5时44分
Design By Chen Anlong
2
道路建设、输电线 路铺设、煤气管线 铺设等。
Design By Chen Anlong
9
3. 顶点的度 TD（V）
无向图：为依附于顶点V的边数 有向图：等于以顶点V为弧头的弧数（称为V的 入度，记
为ID（V））与以顶点V为弧尾的弧数（称为V 的出度，记为OD（V））之和。即： TD（V）=ID（V）+OD（V）
结论：
• 无向图
e= 1/2（∑n TD(vi)） i=1
2021年3月8日5时44分
问题3: 如何连通所有房屋和 商店且造价最低?
14
如何表示？
如何存储？
如何快速计算？
商场 1
房屋 2 25
21
房屋 3
ห้องสมุดไป่ตู้
2021年3月8日5时44分
Design By Chen Anlong
5
图的基本概念
无向图（Undigraph） G=(V, E) 其中，V同有向图的顶点，E为顶点之间的边集合
① G1 ②
2021年3月8日5时44分
Design By Chen Anlong
3
问题1: 造价和管线长度成正
比,如何表示管线长度?
房屋 1
14
房屋 2
30
25
32
2021年3月8日5时44分

第7章 排序 电子科大 数据结构 课件

第7章 排序 电子科大 数据结构 课件

42 70 85 )
Design By Chen Anlong
15

7.2.2 折半插入排序 性能分析 折半插入排序过程中，每次在确定插入位置时，
采用二分的办法，需要比较的次数至多为
log2(n+1) ，总共需要n-1趟，因此，整个排序过
程需要比较的次数为O(nlog2n)。而数据的移动
次数和直接插入排序算法相同，也为O(n2)。
数据结构与算法
主讲人：陈安龙
电子科技大学信息与软件工程学院
2013年12月10日7时45分
Design By Chen Anlong
1
第7章 排序
2013年12月10日7时45分
Design By Chen Anlong
2
对查找问题，如果数据按关键字有序，查询效率会大 大提高。因此，经常需要将数据按关键字进行排序，排序操 作是计算机经常遇到的一类问题。如何设计快速高效的排序 算法，对数据处理特别是大规模数据的处理，至关重要。
其中，d 称为增量，它的值在排序过程中从大到小逐 渐缩小，直至最后一趟排序减为 1。
2013年12月10日7时45分
Design By Chen Anlong
18

7.2.3 希尔排序

排序算法
• 先选取一个小于n的整数di（步长），然后把 待排序的序列分成di个组，从第一个记录开 始，间隔为di的记录为同一组，分完组之后， 在每一组中采用直接插入排序或二分插入排 序进行排序。 • 第一趟完成之后，每一组内部已按关键字有 序，即间隔为di的记录已有序。这时，序列 的有序性和之前的序列相比已有所改善，减 小步长，再进行分组，再排序，序列的有序 性进一步得到改善。

西安电子科技大学数据结构C语言版第3章PPT课件

西安电子科技大学数据结构C语言版第3章PPT课件

第3章 栈 和 队 列
#define MAXSIZE 100
typedef int ElemType;
typedef struct { ElemType elem[MAXSIZE];
int top;
}SqStack;
/*顺序栈的类型标识符*/
SqStack S;
/*说明S是栈变量*/
第3章 栈 和 队 列
{ if(S->top<MAXSIZE-1)
{ S->top++;
S->elem([S->top])=x;
}
else printf("Overflow ! \n");
/*栈满*/
}/* Push */
第3章 栈 和 队 列 3. 出栈操作 算法3.3 /* 若栈不空，则删除栈顶元素，元素值由函数名返回*/ ElemType Pop( SqStack *p)
第3章 栈 和 队 列
(5) GetTop(S): 取栈顶元素操作，若栈S不空则取栈顶元 素的值(栈顶元素不删除，top指针不改变)。
(6) ClearStack(S): 置栈空操作。已知S为栈，不论操作之 前的栈是否为空栈，本操作的结果都是将S置为空栈。
(7) CurrentSize(S): 求当前栈中元素的个数。 (8) DestroyStack(S): 销毁S栈。
假设MAXSIZE取值为6，图3.2展示了顺序栈S中数据元 素和栈顶指针的关系。因为当top=-1为空栈，可利用有效空 间为S.elem[0]，…，S.elem[5]。
5
S.top=5
F
4
E
3
D
S.top=3
D
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

for (i=1; i <=n; i++) { s=0; for (j=1; j <=n; j++) s=s+i×j; if (s%2) print(s) } 西安电子科技大学
①n ② n2 ③ n
- Xidian University, China
数据结构
– Data Structures
第二章 线性表
本章内容：
2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示与实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加
西安电子科技大学 - Xidian University, China
数据结构
– Data Structures
数据结构 Data Structures
期末复习
数据结构
– Data Structures
课程⺫目目录
第1章 概论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和干广广义表 第6章 树和二二叉树 第7章 图 第9章 查找 第10章 内部排序
西安电子科技大学 - Xidian University, China
西安电子科技大学 - Xidian University, China
数据结构
– Data Structures
第三章 栈和队列
本章内容：
3.1 栈 3.1.1 栈的定义 3.1.2 栈的表示和实现 3.2 栈的应用举例 3.3 栈与递归 3.4 队列 3.4.1 队列的定义 3.4.2 链队列 3.4.3 循环队列
A0,0 A1,0 A1,1
. . .
A7,0 A8,0 A7,1 A8,1
. . .
A7,2 A8,2
0
1) 45
B[8]
2) 100+(i(i+1)/2+j)*2
A7,7
...
A8,3
...
A8,8
西安电子科技大学 - Xidian University, China
数据结构
– Data Structures
e10
队列空：
Q.rear==Q.front
队列长度：
(Q.rear - Q.front+ MAXSIZE)% MAXSIZE
e5
e4
MAXSIZE=8
Q.rear Q.front
西安电子科技大学 - Xidian University, China
数据结构
– Data Structures
第四章 串
西安电子科技大学 - Xidian University, China
数据结构
– Data Structures
习题举例
令队列空间中的一个单元闲置，使得在任何时刻，保 持Q.rear和Q.front之间至少间隔一个空闲单元
e7 e6
e8
6 5
7 0 4 3
e9
1 2
队列满：
(Q.rear+1)%MAXSIZE == Q.front
Max{k|1<k<j 且‘p1...pk-1’==‘pj-k+1...pj-1’} 1 其他情况
西安电子科技大学 - Xidian University, China
数据结构
– Data Structures
第五章 数组与广义表
本章内容：
5.1 数组的定义 5.2 数组的表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构 5.6 m元多项式的表示
树和二叉树
西安电子科技大学 - Xidian University, China
数据结构
– Data Structures
第六章 树和二叉树
F
学习要点： 1. 掌握树的定义及基本术语：结点、结点的度、叶子、树 的度、孩子、双亲等。 2. 掌握二叉树有关概念和性质：满二叉树、完全二叉树、 4条重要特性。 3. 了解二叉树的两种存储结构及特点。 4. 掌握二叉树的三种遍历方法：先序、中序和后序。 5. 了解线索二叉树的定义以及二叉树的线索化过程。 6. 了解树的存储结构及3种表示方法，掌握树和森林与二叉 树的转换方法。 7. 掌握最优二叉树（赫夫曼树）的定义及相关概念：路 径长度、树的带权路径长度等，掌握建立最优树和赫夫 曼编码的方法。
第二章 线性表
学习要点：
1. 掌握线性表的两种表示示方方法：顺序表和链表 2. 掌握单链表的创建、插入入、删除以及将两个有序表并为 一一个有序表的算法。 3. 了解循环链表、双向链表的基本概念及基本操作。 4. 了解一一元多项式的表示示及加减运算实现。
西安电子科技大学 - Xidian University, China
数据结构
– Data Structures
关于考试
考题形式：
填空题（30空，每空1分） 选择题（10题，每题2分） 应用题（4题， 每题5分） 算法题（2题， 每题15分）
成绩统计：考试(闭卷)成绩(60%)+平时成绩(40%) 平时成绩：考勤（5%）＋作业（10%）＋上机（25％）
西安电子科技大学 - Xidian University, China
西安电子科技大学 - Xidian University, China
数据结构
– Data Structures
第六章
F 本章内容
6.1 树的定义和基本术语 6.2 二叉树 6.2.1 二叉树的定义及基本运算 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 6.3.2 二叉树的性质 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.6 赫夫曼树及应用 6.6.1 赫夫曼树（最优二叉树） 6.6.2 赫夫曼编码
数据结构
– Data Structures
习题举例
1. 顺序表中，逻辑上相邻的数据元素在物理位置上( 也相邻 ) 。 线性表L=(a1,a2,...,an)采用顺序存储，假定在不同的n+1个位置 上的插入概率相同，则插入一个新元素平均需要移动的元素个 数是( n/2 ) 。 2. 在表长为n的单链表中, 取得第i (1≤ i ≤ n)个数据元素必须从 ( 头指针 )出发开始寻找。 3. 编写算法，将一个带头结点的单链表就地逆置。（请先说明算 法思路，再用类高级语言编写算法。 ） 4. 编写算法实现在单链表L中的第i个位置之间插入元素e。（请 先说明算法思路，再用类高级语言编写算法。 ）
数据结构
– Data Structures
习题举例
1.数据结构中的逻辑结构是指(数据元素之间的逻辑关系)，物理结构是指（数据 结构在计算机中的表示）。 2.算法的基本特征包括有穷性、(确定性)、(可行性)、有输入和输出 。 3.算法分析的两个主要方面是分析算法的（时间复杂度）和（空间复杂度）。 4.设n为正整数，对下面的程序段，写出语句①、②、③的频度及该程序段的时 间复杂度。
西安电子科技大学 - Xidian University, China
数据结构
– Data Structures
习题举例
1. 模式串“abcde”的子串数目为( 1+2+3+4+5+1 )。 2. 已知S = “abcaabba”, 则其next函数值为（ ）。
0 next[j] =
当 j==1
数据结构
– Data Structures
第一章 绪论
学习要点：
1. 熟悉各名词、术语的含义，掌握基本概念。 数据、数据结构、逻辑结构、物理结构、数据类型、抽 象数据类型、 数据元素之间的关系在计算机中的两种不 同表示示方方法。
2. 理解算法五个重要特性的确切含义。 有穷性、确定性、可行行性、输入入、输出
西安电子科技大学 - Xidian University, China
数据结构
– Data Structures
第五章 数组与广义表
学习要点：
1. 掌握数组在以行行（列）为主的存储结构中的地址计算方方法。 2. 了解特殊矩阵的压缩存储方方法的特点。 3. 了解稀疏矩阵的压缩存储方方法的特点及相关操作。 4. 了解干广广义表的定义，掌握干广广义表的求⻓长度、求深度、求非非空 干广广义表的表头和表尾运算。
本章内容：
4.1 4.2 4.3 4.4 串类型的定义 串的表示和实现 串的模式匹配算法 串操作应用示例
西安电子科技大学 - Xidian University, China
数据结构
– Data Structures
第四章 串
学习要点：
1.掌握串类型的定义及概念：⻓长度、空串、空格串、子子串、 位置等。 2.了解串的定⻓长顺序存储结构上实现串的各种操作的方方法。 3.了解串的堆存储结构以及在其上实现串操作的基本方方法。 4.了解基本的串的模式匹配算法，了解串匹配的KMP算法， 了解NEXT函数的定义及计算。
习题举例
1. 设广义表L=（（（a, b）），（c，d），e），则L的表头 (（（a, b）） )，表尾是(（（c，d），e） )。 2. 已知广义表L =（((f)),(b),c,(a),(((d,e)))）,则该广义表的 长度和深度分别为（ 5 ）、（ 4 ），用求表头和求表尾 的方式求出原子a的式子为 ( head(head(tail(tail（tail(L))))) )。
西安电子科技大学 - Xidian University, China
数据结构
– Data Structures
第一章 绪论
3. 算法和算法分析 评价算法性能的两个重要方方面面：时间复杂度和空间复杂 度 掌握计算语句频度和估算算法时间复杂度的基本方方法。