《数据结构》
教案
计算机科学系
《数据结构》
第一章绪论
[教学目标]
掌握数据结构的定义、内容、方法、描述、评价。
[重点、难点]
数据结构的研究范围，研究采用的方法，算法规则描述的工具，对算法作性能评价。[教学方法]
用多媒体课件（ ppt ）以及与生活实例相结合等方法讲授，这样便于描述相关概念及学生记笔记，加深他们的印象，使基础知识掌握地比较牢固。
[学习要点]
1. 熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。
2. 了解抽象数据类型的定义、表示和实现方法。
3．理解算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）。
4．掌握计算语句频度和估算算法时间复杂度的方法。
1.1 什么是数据结构（定义）
首先介绍数据结构的相关名词。
1.数据（Data）
数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。。
2.数据元素（Data Element）
数据元素是组成数据的基本单位 ,是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。例如：学生登记表是数据，每一个学生的记录就是一个数据元素。
3.数据对象（Data Object）
数据对象是性质相同的数据元素的集合，是数据的一个子集。
4.数据结构（DA TA Structure）
数据结构是指相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。
5.数据类型(Data Type)
数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。
6.数据抽象与抽象数据类型
１）数据的抽象
高级语言中提供整型、实型、字符、记录、文件、指针等多种数据类型，可以利用这些类型构造出象栈、队列、树、图等复杂的抽象数据类型。
２）抽象数据类型(Abstract Data Type)
抽象数据类型（简称ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。
抽象数据类型是近年来计算机科学中提出的最重要的概念之一，它集中体现了程序设计中一些最基本的原则：分解、抽象和信息隐藏。
一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将运算的实现过程隐藏起来。
图1.4 求解过程
数据结构是基础，抽象数据类型是中枢。
1.2 数据结构的内容
数据结构的内容可归纳为三个部分。逻辑结构、存储结构、运算集合。
数据结构是一门主要研究怎样合理地组织数据、建立合适的数据结构、提高计算机执行程序所用的时空效率的学科。
1.3 算法
1．算法（Algorithm）定义
算法是规则的有限集合，是为解决特定问题而规定的一系列操作。
2．算法的特性
⑴有限性有限步骤之内正常结束，不能形成无穷循环。
⑵确定性算法中的每一个步骤必须有确定含义，无二义性得以实现。
⑶输入有多个或0个输入
⑷输出至少有一个或多个输出。
⑸可行性原则上能精确进行，操作可通过已实现基本运算执行有限次而完成。
在算法的五大特性中，最基本的是有限性、确定性、可行性。
3．算法设计的要求
一般应该具有以下几个基本特征：
１）算法的正确性2)可读性3）健壮性4）高效率和低存储量
1.4 算法描述的工具
1．算法、语言、程序的关系
先分析数据结构中算法、语言、程序的关系：
⑴算法：描述了数据对象的元素之间的关系（包括数据逻辑关系、存贮关系描述）。
⑵描述算法的工具：（自然语言、框图或高级程序设计语言）
⑶程序是算法在计算机中的实现（与所用计算机及所用语言有关）
2．设计实现算法过程步骤：
●找出与求解有关的数据元素之间的关系（建立结构关系）
●确定在某一数据对象上所施加运算
●考虑数据元素的存储表示
●选择描述算法的语言
●设计实现求解的算法，并用程序语言加以描述。
3．类描述算法的语言选择
采用了标准C语言作为算法描述的工具。
1.5 对算法作性能评价
1．性能评价
对问题规模与该算法在运行时所占的空间S与所耗费的时间T给出一个数量关系的评价。
2．有关数量关系计算
数量关系评价体现在时间——算法编程后在机器中所耗费时间。
数量关系评价体现在空间——算法编程后在机器中所占存储量。
1）关于算法执行时间
一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指
该条语句的执行次数和执行一次所需时间的乘积。
2）语句频度
语句频度是指该语句在一个算法中重复执行的次数。
3）算法的时间复杂度:
所谓算法的时间复杂度，即是算法的时间量度记做：
T(n)=O(f(n))
它表示随问题规模n的增大算法的执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。
4）数据结构中常用的时间复杂度频率计数
数据结构中常用的时间复杂度频率计数有7个：
O(1) 常数型 O(n)线性型 O(n2)平方型 O(n3)立方型
O(2n)指数型 O(log2n)对数型 O(nlog2n)二维型
5）最坏时间复杂度
算法中基本操作重复执行的次数还随问题的输入数据集的不同而不同。
6）算法的空间复杂度
关于算法的存储空间需求，类似于算法的时间复杂度，我们采用空间复杂度作为算法所需存储空间的量度，记做：S(n)=O(f (n))
1.6 关于学习数据结构
1．数据结构课程地位
数据结构发展趋势包括两个方面：一是面向专门领域中特殊问题的数据结构的研究和发展，如图形数据结构、知识数据结构、空间数据结构，另一方面，从抽象数据类型的角度，用面向对象观点来讨论数据结构，已成为新的发展趋势。
2．数据结构课程学习特点
《数据结构》课程教学目标要求学生学会分析数据对象特征，掌握数据组织方法和计算机的表示方法，以便为应用所涉及数据选择适当的逻辑结构、存储结构及相应算法，初步掌握算法时间空间分析的技巧，培养良好的程序设计技能。
第2章线性表
[教学目标]
线性结构是一种最基本的数据结构,熟练掌握其逻辑结构、存储结构各种运算。
[重点、难点]
链表结构，重点掌握单链表、循环链表、双向链表，初步掌握静态链表。
[教学方法]
首先给出线性表的抽象数据类型定义，然后分别用顺序结构和链表结构实现线性表，最后给出一个应用实例。
[学习要点]
1. 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。
2. 熟练掌握这两类存储结构的描述方法，如一维数组中一个区域[i..j]的上、下界和长度之间的变换公式(L=j-i+1, i=j-L+1, j=i+L-1)，链表中指针p和结点*p的对应关系(结点*(p->next)是结点*p的后继等)，链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求。
3. 熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。
4. 熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。
5. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。
2.1 线性表的概念及运算
2.1.1 线性表的逻辑结构
线性表是n个类型相同的数据元素的有限序列，数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继。
2.1.2 线性表的抽象数据类型定义
一个抽象数据类型定义了一个模型，但不涉及模型的具体实现问题。
2.2 线性表的顺序存储
2.2.1 线性表的顺序存储结构
线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。采用顺序存储结构的线性表通常称为顺序表。
2.2.2 线性表顺序存储结构上的基本运算
1. 查找操作
线性表有两种基本的查找运算。
按序号查找GetData(L,i): 要求查找线性表L中第i个数据元素，其结果是L.elem[i-1]
或L->elem[i-1]。
按内容查找Locate（L,e）:要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。
2.插入操作
线性表的插入运算是指在表的第i (1≤i≤n+1)个位置，插入一个新元素e，使长度为n 的线性表(e1，…，e i-1，e i，…，e n) 变成长度为n+1的线性表（e1，…,e i-1，e，e i，…，e n）。
3. 删除操作
线性表的删除运算是指将表的第i(1≤i≤n)个元素删去，使长度为n的线性表(e1，…,e i-1，e i，e i+1，…，e n)，变成长度为n-1的线性表(e1，…,e i-1，e i+1，…，e n)。
2.3 线性表的链式存储
采用链式存储结构的线性表称为链表。
2.3.1 单链表
链表是用一组任意的存储单元来存放线性表的结点，在存储线性表的每个数据元素值的同时，存储指示其后继结点的地址（或位置）信息，这两部分信息组成的存储映象叫做结点（Node），如图2.5 所示。
图2.5 单链表的结点结构
它包括两个域：数据域用来存储结点的值；指针域用来存储数据元素的直接后继的地址（或位置）。由于链表的每个结点只有一个指针域，故将这种链表又称为单链表。
应设一个头指针H指向第一个结点，由于表中最后一个结点没有直接后继，则指定线性表中最后一个结点的指针域为“空”（NULL）。
例如：图2.6所示为线性表（A,B,C,D,E,F,G,H）的单链表存储结构，整个链表的存取需从头指针开始进行，依次顺着每个结点的指针域找到线性表的各个元素。
图2.6 单链表的示例图
有时为了操作的方便，还可以在单链表的第一个结点之前附设一个头结点，头结点的数据
域可以存储一些关于线性表的长度的附加信息，也可以什么都不存；而头结点的指针域存储指向第一个结点的指针。此时带头结点单链表的头指针就不再指向表中第一个结点而是指向头结点。如果线性表为空表，则头结点的指针域为“空”，如图 2.8所示。
(a)带头结点的空单链表
(b)带头结点的单链表
图2.8 带头结点单链表图示
2.3.2 单链表上的基本运算
1．建立单链表
动态建立单链表的常用方法有如下两种：
1）头插法建表
算法描述：从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头结点之后，直至读入结束标志为止。
2）尾插法建表
该方法是将新结点插到当前链表的表尾上。为此需增加一个尾指针r，使之始终指向当前链表的表尾。
2．查找
1）按序号查找
算法描述：设带头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链表的头指针L出发，从头结点（L->next）开始顺着链域扫描，用指针p指向当前扫描到的结点,初值指向头结点（pL->next），用j做记数器，累计当前扫描过的结点数（初值为0），当j = i 时，指针p所指的结点就是要找的第i个结点。
2) 按值查找
算法描述：按值查找是指在单链表中查找是否有结点值等于e的结点，若有的话，则返回首次找到的其值为e的结点的存储位置，否则返回NULL。
3．单链表插入操作
算法描述：要在带头结点的单链表L中第i个数据元素之前插入一个数据元素e，需要首先在单链表中找到第i-1个结点并由指针pre指示，然后申请一个新的结点并由指针s指示，其数据域的值为e，并修改第i-1个结点的指针使其指向s，然后使s结点的指针域指向第i个结点。
4．删除
算法描述：欲在带头结点的单链表L中删除第i个结点，则首先要通过计数方式找到第i-1个结点并使p指向第i-1个结点，而后删除第i个结点并释放结点空间。删除过程如图2.12所示。
2.3.3 循环链表
循环链表：是一个首尾相接的链表。其特点是将单链表最后一个结点的指针域由NULL 改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，并称为循环单链表。
（a）带头结点的循环单链表的一般形式
（b）带尾结点的循环单链表的一般形式
2.3.4 双向链表
链表中就有两条方向不同的链，我们称之为双( 向) 链表(Double Linked List)。
图2.14 双链表的结点结构
1、双向链表的前插操作
2、双向链表的删除操作
算法描述：欲删除双向链表中的第i个结点，则指针的变化情况如图所示：
图2.17 双向链表的删除操作
2.4 一元多项式的表示及相加
对于符号多项式的各种操作，实际上都可以利用线性表来处理。比较典型的是关于一元多项式的处理。在数学上，一个一元多项式P n(x)可按升幂的形式写成：
P n(x)=p0+p1x+p2x2+p3x3+ …+p n x n
（2）通过键盘输入一组多项式的系数和指数，以输入系数0为结束标志，并约定建立多项式链表时，总是按指数从大到小的顺序排列。
算法描述：从键盘接受输入的系数和指数；用尾插法建立一元多项式的链表。
第3章限定性线性表—栈和队列
[教学目标]
栈和队列是两种限定性线性表，在编译程序、操作系统等各种软件系统中应用广泛。熟练掌握逻辑、存储结构。
[重点、难点]
要求重点掌握利用栈和队列解决实际问题的方法。
[教学方法]
用栈和队列的典型应用引出栈和队列的抽象数据类型定义、分别用顺序结构和单链表结构实现栈和队列，栈与递归的实现。
[学习要点]
1. 掌握栈和队列这两种抽象数据类型的特点，并能在应用问题中正确选用它们。
2. 熟练掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法。
3. 熟练掌握循环队列和链队列的基本操作算法，特别注意队满和队空的描述方法。
4. 理解递归算法执行过程中栈的状态变化过程。
3.1 栈
3.1.1 栈的定义
栈又称为后进先出的线性表，简称为LIFO表。在日常生活中也可以见到很多“后进先出”的例子，如：手枪子弹夹中的子弹，子弹的装入与子弹弹出膛均在弹夹的最上端进行，先装入的子弹后发出，而后装入的子弹先发出。又如：铁路调度站，都是栈结构的实际应用。
3.1.2 栈的表示和实现
1．顺序栈
顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。通常以top=-1表示空栈。
⑴初始化。
void InitStack(SeqStack *S)
{/*构造一个空栈S*/
S->top= -1;
}
⑵判栈空。
int IsEmpty(SeqStack *S) /*判栈S为空栈时返回值为真，反之为假*/
{
return(S->top==-1?TRUE:FALSE);
}
⑶判栈满。
int IsFull(SeqStack *S)
{
return(S->top == Stack_Size?TRUE:FALSE);
}
⑷进栈。
int Push(SeqStack * S, StackElementType x)
{
if(S->top== Stack_Size-1) return(FALSE); /*栈已满*/
S->top++;
S->elem[S->top]=x;
return(TRUE);
}
⑸出栈。
int Pop(SeqStack * S, StackElementType *x)
{ /* 将栈S的栈顶元素弹出，放到x所指的存储空间中*/
if(S->top==-1) /*栈为空*/
return(FALSE);
else
{
*x= S->elem[S->top];
S->top--; /* 修改栈顶指针*/
return(TRUE);
}
}
⑹取栈顶元素。
int GetTop（SeqStack *S, StackElementType *x）
{ /* 将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变*/ if(S->top==-1) /*栈为空*/
return(FALSE);
else
{
*x = S->elem[S->top];
return(TRUE);
}
}
思考题：说明读栈顶元素的算法与退栈顶元素的算法的区别，并请写出读栈顶算法。2．链栈
链栈即采用链表作为存储结构实现的栈。
⑴进栈操作。
int Push(LinkStack top, StackElementType x)
/* 将数据元素x压入栈top中*/
{
LinkStackNode * temp;
temp=(LinkStackNode * )malloc(sizeof(LinkStackNode));
if(temp==NULL) return(FALSE); /* 申请空间失败*/
temp->data=x;
temp->next=top->next;
top->next=temp; /* 修改当前栈顶指针*/
return(TRUE);
}
⑵出栈操作。
int Pop(LinkStack top, StackElementType *x)
{ /* 将栈top的栈顶元素弹出，放到x所指的存储空间中*/
LinkStackNode * temp;
temp=top->next;
if(temp==NULL) /*栈为空*/
return(FALSE);
top->next=temp->next;
*x=temp->data;
free(temp); /* 释放存储空间*/
return(TRUE);
}
思考题：将可利用空间组成链栈，常用的申请一个新结点（如C语言中的mallock函数）与归还一个无用结点（如C语言中的free函数）操作，对可利用空间的链栈来说，分别相当做什么操作？
3.1.3 栈的应用举例
栈应用的典型例子。
1.括号匹配问题
假设表达式中包含三种括号：圆括号、方括号和花括号，它们可互相嵌套，如( [ { } ] ( [ ] ) )或( { ( [ ] [ ( ) ] ) } )等均为正确的格式，而{ [ ] } ) }或{ [ ( ) ]或( [ ] }均为不正确的格式。在检验算法中可设置一个栈，每读入一个括号，若是左括号，则直接入栈，等待相匹配的同类右括号；若读入的是右括号，且与当前栈顶的左括号同类型，则二者匹配，将栈顶的左括号出栈，否则属于不合法的情况。另外，如果输入序列已读尽，而栈中仍有等待匹配的左括号，或者读入了一个右括号，而栈中已无等待匹配的左括号，均属不合法的情况。当输入序列和栈同时变为空时，说明所有括号完全匹配。
2.算术表达式处理规则：
一、规定优先级表
二、设置两个栈：OVS(运算数栈)、OPTR(运算符栈)
三、自左向右扫描，遇操作数进OVS(运算数栈),操作符则与OPTR(运算符栈)栈顶优先数比较：当前操作符>OPTR栈顶, 当前操作符进OPTR栈,前操作符≤OPTR栈顶.
图3.7 A/B↑C+D*E的运算过程时栈区变化情况栈区变化示意图
3.2.1 队列的定义
队列(Queue) 是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出(Fist In Fist Out，缩写为FIFO)的特性。在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。
3.2.2 队列的表示和实现
1．链队列
用链表表示的队列简称为链队列。
（1）初始化操作。
int InitQueue(LinkQueue * Q)
{ /* 将Q初始化为一个空的链队列*/
Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
if(Q->front!=NULL)
{
Q->rear=Q->front;
Q->front->next=NULL;
return(TRUE);
}
else return(FALSE); /* 溢出！*/
}
（2）入队操作。
int EnterQueue(LinkQueue *Q, QueueElementType x)
{ /* 将数据元素x插入到队列Q中*/
LinkQueueNode * NewNode;
NewNode=(LinkQueueNode * )malloc(sizeof(LinkQueueNode));
if(NewNode!=NULL)
{
NewNode->data=x;
NewNode->next=NULL;
Q->rear->next=NewNode;
Q->rear=NewNode;
return(TRUE);
}
else return(FALSE); /* 溢出！*/
}
（3）出队操作。
int DeleteQueue(LinkQueue * Q, QueueElementType *x)
{ /* 将队列Q的队头元素出队，并存放到x所指的存储空间中*/
LinkQueueNode * p;
if(Q->front==Q->rear)
return(FALSE);
p=Q->front->next;
Q->front->next=p->next; /* 队头元素p出队*/
if(Q->rear==p) /* 如果队中只有一个元素p，则p出队后成为空队*/
Q->rear=Q->front;
*x=p->data;
free(p); /* 释放存储空间*/
return(TRUE);
}
2．循环队列
循环队列是队列的一种顺序表示和实现方法。由于只能在队尾入队，使得上述空单元无法使用。我们把这种现象称为假溢出，真正队满的条件是rear - front=MAXSIZE 。
为了解决假溢出现象并使得队列空间得到充分利用，是将顺序队列的数组看成一个环状的空间，即规定最后一个单元的后继为第一个单元，称之为循环队列。通过取模（求余）运算来实现：rear=（rear+1）mod MAXSIZE，显然，当rear+1=MAXSIZE时，rear=0，同样可求得最后一个单元Queue[MAXSIZE-1]的后继：Queue[0]。队尾指针的变化是：rear=（rear+1）mod MAXSIZE ；而出队操作时，队头指针的变化是：front=（front+1）mod MAXSIZE。图3.15给出了循环队列的几种情况。
第4章串
[教学目标]
字符串是最基本的非数值数据，在语言编译、信息检索、文字编辑等问题中，有广泛的应用。熟练掌握其逻辑结构、存储结构各种运算。
[重点、难点]
字符串的抽象数据类型定义，定长顺序串、堆串的存储结构和操作实现。一般性了解块链串。
[教学方法]
采用应用实例任务驱动给出字符串的抽象数据类型定义，然后分别用顺序结构和链表结构实现字符串。
[学习要点]
1. 了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。
2. 掌握对特殊矩阵进行压缩存储时的下标变换公式。
3. 了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。
4. 掌握广义表的结构特点及其存储表示方法，学会对非空广义表进行分解的两种分析方法：即可将一个非空广义表分解为表头和表尾两部分或者分解为n个子表。
4.1 串的定义
串(String)是零个或多个字符组成的有限序列。一般记为：
S=‘a1a2…a n’(n≥0)
其中S是串的名字,用单引号括起来的字符序列是串的值。n是串中字符的个数,称为串的长度，n=0时的串称为空串(Null String)。
串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常将字符在串中的序号称为该字符在串中的位置。
当且仅当两个串的值相等时,称这两个串是相等的。由一个或多个称为空格的特殊字符组成的串，称为空格串(Blank string),其长度为串中空格字符的个数。请注意空串(Null String)和空格串(Blank string)的区别。
串也是线性表的一种,因此串的逻辑结构和线性表极为相似,区别仅在于串的数据对象限定为字符集。
4.2 抽象数据类型串的实现
常用的实现方法有:定长顺序串、堆串和块链串。
4.2.1 定长顺序串
定长顺序串是将串设计成一种结构类型,串的存储分配是在编译时完成的。用一组地址连续的存储单元存储串的字符序列。
在进行串的插入时，插入位置pos将串分为两部分（假设为A、B,长度为LA、LB）,及待插入部分（假设为C, 长度为LC）,则串由插入前的AB变为ACB，可能有三种情况：（1）插入后串长(LA+LC+LB)≤MAXLEN：则将B后移LC个元素位置，再将C插入。
（2）插入后串长>MAXLEN且pos+LC
同上类似，在进行串的连接时（假设原来串为A，长度为LA, 待连接串为B，长度为LB），也可能有三种情况：
（1）连接后串长≤MAXLEN：则直接将B加在A的后面。
（2）连接后串长>MAXLEN且LA （3）连接后串长>MAXLEN且LA=MAXLEN：则B的全部字符被舍弃（不需连接）。 置换时的情况较为复杂，假设为原串为A、长度为LA，被置换串为B、长度为LB,置换串为C、长度为LC，每次置换位置为pos，则每次置换有三种可能： （1）LB=LC：将C复制到A中pos起共LC个字符处。 （2）LB>LC：将A中B后的所有字符前移LB-LC个字符位置，然后将C复制到A中pos起共LC个字符。 （3）LB 处理。 4.2.2 堆串 系统将一个地址连续、容量很大的存储空间作为字符串的可用空间，每当建立一个新串时，系统就从这个空间中分配一个大小和字符串长度相同的空间存储新串的串值。 假设以一维数组heap [MAXSIZE] 表示可供字符串进行动态分配的存储空间，并设int free 指向heap 中未分配区域的开始地址(初始化时free=0) 。在程序执行过程中，当生成一个新串时，就从free指示的位置起，为新串分配一个所需大小的存储空间，同时建立该串的描述。这种存储结构称为堆结构。 其中len域指示串的长度，ch域指示串的起始地址。 4.3 串的应用举例：文本编辑 文本编辑程序用于源程序的输入和修改，公文书信、报刊和书籍的编辑排版等。常用的文本编辑程序有Edit，WPS，Word等，文本编辑的实质是修改字符数据的形式和格式，虽然各个文本编辑程序的功能不同，但基本操作是一样的，都包括串的查找、插入和删除等。 为了编辑方便，可以用分页符和换行符将文本分为若干页，每页有若干行。我们把文本当作一个字符串，称为文本串，页是文本串的子串，行是页的子串。 采用堆存储结构来存储文本，同时设立页指针、行指针和字符指针，分别指向当前操作的页、行和字符，同时建立页表和行表存储每一页、每一行的起始位置和长度。 第5章数组和广义表 [教学目标] 数组和广义表，是扩展的线性数据结构，其中广义表是人工智能程序设计的基础。要求熟练掌握其逻辑结构、存储结构各种运算。 [重点、难点] 抽象数据类型数组的定义与实现，特殊矩阵的压缩存储，稀疏矩阵（分别用三元组表、十字链表实现转置、加减法等矩阵运），广义表的存储结构，稀疏矩阵的乘法运算。 [教学方法] 设问解疑，激发学生对数组和广义表的求知欲望和积极的思维活动。 [学习要点] 1. 了解数组的存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。 2. 掌握对特殊矩阵进行压缩存储时的下标变换公式。 3. 了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。 4. 掌握广义表的结构特点及其存储表示方法 5.1 数组的定义和运算 数组实际上是线性表的推广。数组中的每一个元素由一个值和一组下标来描述。对于数组的操作一般只有两类： 1）获得特定位置的元素值； 2）修改特定位置的元素值。 5.2 数组的顺序存储和实现 数组的顺序存储结构有两种：一种是按行序存储，另一种是按列序存储，。二维数组A mxn 以行为主的存储序列为： a11 ,a12, … a1n ,a21 ,a22 ,…,a2n , … … ,a m1 ,a m2 ,…,a mn 而以列为主存储序列为： a11, a21,… a m1 ,a12 ,a22 ,… ,a m2 ,… … ,a1n ,a2n , … ,a mn 地址计算公式： Loc[i,j]=Loc[1,1]+n×(i-1)+(j-1) 根据计算公式，可以方便的求得a ij的地址是Loc[i,j]。如果每个元素占size个存储单元，则 任意元素a ij的地址计算公式为： Loc[i,j]=Loc[1,1] + (n×(i-1)+j-1)×size 5.3.1 三角矩阵 三角矩阵大体分为三类：下三角矩阵、上三角矩阵、对称矩阵。对于一个n阶矩阵A 来说：若当i 下面以n×n下三角矩阵（图5.6）为例来讨论三角矩阵的压缩存储。 对于下三角矩阵的压缩存储，只存储下三角的非零元素，对于零元素则不存。下三角矩阵中元素a ij(i>j)，在一维数组A中的位置为： Loc[ i ,j]=Loc[1,1]+前i-1行非零元素个数+第i行中a ij前非零元素个数 LOC[ i ,j]= LOC[1,1]+ i (i -1)/2+ j-1 5.3.2 带状矩阵 所谓的带状矩阵即：在矩阵A中，所有的非零元素都集中在以主对角线为中心的带状区域中。其中最常见的是三对角带状矩阵。 对于三对角带状矩阵的压缩存储，以行序为主序进行存储，并且只存储非零元素。具体压缩存储方法如下： 一、确定存储该矩阵所需的一维向量空间的大小 二、确定非零元素在一维数组空间中的位置。 5.3.3 稀疏矩阵 所谓的稀疏矩阵，是指矩阵中大多数元素为零的矩阵。一般地，当非零元素个数只占矩阵元素总数的25%—30%,或低于这个百分数时，我们称这样的矩阵为稀疏矩阵。 一、稀疏矩阵的三元组表表示法： 把三元组按“行序为主序”用一维数组进行存放，即将j矩阵的任何一行的全部非零元素的三元组按列号递增存放。由此得到矩阵M，N的三元组表. 稀疏矩阵的三元组表示法虽然节约了存储空间，但比起矩阵正常的存储方式来讲，其实现相同操作要耗费较多的时间，同时也增加了算法的难度。即以耗费更多时间为代价来换取空间的节省。 二、稀疏矩阵的链式存储结构----十字链表 在十字链表中，同一行的非零元素通过right域链接成一个单链表。同一列的非零元素通过down域链接成一个单链表。这样，矩阵中任一非零元素Mij所对应的结点既处在第i 行的行链表上，又处在第j列的列链表上，这好像是处在一个十字交叉路口上，所以称其为十字链表。同时我们再附设一个存放所有行链表的头指针的的一维数组，和一个存放所有列链表的头指针的的一维数组。 广义表，顾名思义，它也是线性表的一种推广。它被广泛的应用于人工智能等领域的表处理语言LISP语言中。在LISP语言中，广义表是一种最基本的数据结构，就连LISP 语言的程序也表示为一系列的广义表。 由于广义表GL=（d1，d2，d3，…，d n）中的数据元素既可以是单个元素，也可以是子表，因此对于广义表，我们难以用顺序存储结构来表示它，通常我们用链式存储结构来表示。表中的每个元素可用一个结点来表示。广义表中有两类结点，一类是单个元素结点，一类是子表结点。从上节得知，任何一个非空的广义表都可以将其分解成表头和表尾两部分，反之，一对确定的表头和表尾可以唯一地确定一个广义表。由此，一个表结点可由三个域构成：标志域，指向表头的指针域，指向表尾的指针域。而元素结点置需要两个域：标志域和值域。 第六章树 [教学目标] 树是一种层次结构，在文件系统、数据库系统、编译系统等方面有重要应用。熟练掌握树与二叉树的抽象数据类型定义和实现，二叉树的遍历与线索二叉树，树、森林与二叉树的关系，哈父曼树及其应用。 [重点、难点] 二叉树、树、森林与二叉树的相互转换。 [教学方法] 提出树、二叉树和的森林问题，在教师组织和指导下，通过学生比较独立的探究和研究活动，探求问题的答案。 [学习要点] 1. 熟练掌握二叉树的结构特性，了解相应的证明方法。 2. 熟悉二叉树的各种存储结构的特点及适用范围。 3. 遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。不仅要熟练掌握各种遍历策略的递归和非递归算法，了解遍历过程中“栈”的作用和状态，而且能灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。 4. 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。 5. 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握1至2种建立二叉树和树的存储结构的方法。 6. 学会编写实现树的各种操作的算法。 7. 了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。 6.1 树的概念与定义 树是n（n≥0）个结点的有限集合T。当n=0时，称为空树；当n>0时，该集合满足如下条件：⑴其中必有一个称为根（root）的特定结点，它没有直接前驱，但有零个或多个直接后继。⑵其余n-1个结点可以划分成m（m≥0）个互不相交的有限集T1，T2，T3，…，Tm， 《数据结构》教学设计方案 1 课程的一般信息 1.1 教学对象 计算机科学与技术专业2012级本科学生 1.2 课程名称 《数据结构》 1.3 课程教材及分析 1.3.1 中文教材及分析 数据结构(C语言版)，严蔚敏，北京：清华大学出版社(国家精品课程配套教材)，2011.11。 该教材为国内关于数据结构最知名的教材之一，受到国内计算机教育界广泛的认可。 1.3.2 教材选取的背景 选取本教材的原因主要是受到本人对于该课程的教学改革驱动，在该课程教学中强调实践性，注重理论联系实际。 1.4 课程类型 专业必修课（开设时间为计算机科学学院各专业本科生二年级第一学期） 1.5 教师的基本信息 肖冰，1981年生，博士，讲师，计算机科学学院。主要研究方向为模式识别、机器学习、智能信息处理等。博士毕业后从事一线教学和科研工作，主讲了《计算机基础》、《ACCESS 数据库应用技术》，《数据结构》、《数据库原理与设计》及相关课程设计等课程。在Pattern Recognition（SCI二区）、Neurocomputing（SCI三区）、Signal Processing（SCI三区）、电子学报（中、英文版）等国际、国内权威期刊和会议上发表论文15篇，其中SCI检索6篇，EI检索9篇，在重要期刊上发表教学论文一篇。主持国家博士后科学基金、陕西省博士后科学基金、陕西师范大学中央高校基本科研业务费、西安电子科技大学优秀博士学位论文资助基金、陕西师范大学青年基金各一项，以第三完成人参与国家自然科学基金、博士点基金等多项科研项目。授权专利三项，获得陕西省科学技术奖一等奖（第三完成人）一项，陕西省自然科学优秀学术论文二等奖（第一完成人）一项。 2 该单元的教学目标 2.1 单元内容概要 第9章查找 第3节哈希表 《数据结构》教学纲要(doc 9页) 《数据结构》教学大纲 2001年9月 一、开课系（部）：经济信息管理系 二、教学对象：信息管理与信息系统专业本科 三、教学目的： 数据结构是高等教育计算机信息管理专业中的一门专业基础课，在计算机软件的各个领域中均会使用到数据结构的有关知识。本课程的目的和任务是使学生较全面地掌握各种常用的数据结构，为学习后续软件课程提供必要的基础，提高运用数据结构解决实际问题的能力。 四、教学要求： 1. 从数据结构的逻辑结构、存储结构和数据的运算三个方面去掌握线性表、栈、队列、串、数组、广义表、树、图和文件等常用的数据结构。 2. 掌握在各种常用的数据结构上实现的排序和查找运算。 3. 对算法的时间和空间复杂性有一定的分析能力。 4. 针对简单的应用问题.应能选择合适的数据结构及设计有效的算法解决之。 五、教学课时： 教学内容课内学时 第1章绪论 2 第2章线性表 4 第3章栈和队列 6 第4章串 4 笫5章数组和广义表 4 第6章树和二叉树 6 第7、8章略 第9章查找 4 第10章内部排序 4 课程总复习 2 六、考核形式： 期末考试与平时讨论相结合（80%和20%）。 期末试卷结构： 单项选择填空简答应用算法设计 20 15分20分15分30分 态。 3.3 算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。 第2章线性表 (一)课程内容 2.1 线性表的逻辑结构 2.2 线性表的顺序存储结构 2.3 线性表的链式存储结构 2.4 顺序表和链表的比较 (二)学习目的与要求 本章目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。要求在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。本章重点是熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。 (三)考核知识点与考核要求 1. 线性表的逻辑结构，要求达到“识记”层次。 1.1 线性表的逻辑结构特征。 1.2 线性表上定义的基本运算，并能利用基本运算构造出较复杂的运算。 2. 线性表的顺序存储结构.要求达到“综合应用”层次。 2.1 顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系。 2.2 顺序表上的插入、删除操作及其平均时间性能分析。 2.3 利用顺序表设计算法解决筒单的应用问题。 3. 线性表的链式存储结构，要求达到“综合应用”层次。 3.1 链表如何表示线性表中元素之间的逻辑关系。 3.2 链表中头指针和头结点的使用。 3.3 单链表、双链表、循环链表链接方式上的区别。 3.4 单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。 3.5 循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。 3.6 双链表的定义及其相关的算法。 3.7 利用链表设计算法解决简单的应用问题。 4.顺序表和链表的比较.要求达到“领会”层次。 2015 至2016 学年第二学期 数据结构课程 教 案 课程编码：1261D03 总学时／周学时：80 / 5 开课时间：2016年2 月24日第1 周至第16 周 授课年级、专业、班级：15级网工程2班 使用教材严蔚敏. 数据结构（C语言版）[M] 北京：清华大学出版社，2011.系别/教研室：信息工程学院/ 物联网工程 授课教师：刘波 教学目标： 《数据结构》是物联网工程专业的一门专业必修课。用计算机解决任何问题都需要进行数据表示和数据处理，而数据表示和数据处理正是《数据结构》要研究的内容。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。 通过本课程教学，使学生了解数据结构的基本概念，理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，掌握算法描述及算法的评价标准，熟悉在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会，旨在培养学生基本的、良好的程序设计技能，编制高效可靠的程序，并为学生日后学习操作系统和数据库等后续课程奠定基础。 教学要求: 本课程主要是以抽象数据类型的观点来组织和讲解线性表、栈、队列、树、二叉树、图等各种主要的数学模型并定义为相应的抽象数据类型，给出各种物理表示法和有关算法，关于数据处理技术介绍几种主要的排序和查找算法。 学生通过学习该课程后主要应掌握以下内容： 1．了解数据结构及有关的基本概念； 2．了解各种抽象数据类型的性质； 3．掌握各种抽象数据类型的实现和基本算法； 4．对算法的时间和空间复杂性有一定的分析能力； 5．能够选择适当的数据结构和存储结构以及设计有效的算法，解决实际问题； 6．掌握数据结构在排序和查找等常用算法中的应用。 教学重点： 抽象数据类型、顺序表、单链表、循环链表、栈、队列、数组、特殊矩阵、树和二叉树、最小生成树、拓扑排序、查找、内部排序 教学难点： 单链表、栈、循环队列、特殊矩阵、二叉树、关键路径、最短路径 教学方法与手段： 1．理论部分以讲授法为主，结合讨论及课堂练习实现教学目的。 2．传统教学手段与多媒体等现化手段相结合。 3．重视实验教学，要求学生利用一切可利用的时间和机会去实验室，实现并验证书本上的各种算法，达到真正实现教学目的。 考核与成绩评定方式： 本课程为考试科目，课程结束后采用闭卷考试。考核总成绩中，平时成绩占30%（出勤占10%，实验占10%，书面作业占10%），期末考试占70%；考核范围为教学大纲规定的基本要求教学内容。 教材与主要参考书目： 1．教材 严蔚敏、吴伟民. 数据结构（C语言版）[M] 北京：清华大学出版社，2011. 《数据结构》课程标准 适用专业：计算机应用技术、大数据技术 学时：72 前导课程：计算机应用基础、C语言程序设计 一、课程性质 《数据结构》是大数据应用专业的一门专业基础必修课程。本课程面向Android软件工程师的岗位需求，主要讲述集合、线性表、堆栈和队列、树和二叉树、查找和排序等基本数据结构和算法。本课程着重基本知识的掌握和基本技能的训练，为利用c语言进一步处理数据奠定基础。 二、课程理念 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。精心选择的数据结构可以带来更高的运行或存储效率，数据结构往往同高兴的检索算法和索引技术有关。 1、课程地位理念 在许多类型的程序设计中，数据结构的选择是一个基本的设计考虑因素。许多大型的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。选择了数据结构，算法随之确定，是数据而不是算法是系统构造的关键因素。 2、课程学情理念 本课程开设在嵌入式系统工程专科第一学期，学生在学习本课程前已具备计算机基础、C语言基础等知识，本课程力图让学生学会在C语言环境下，运用面向对象的思想编写规范的代码，实现经典的数据结构和算法。熟悉常用的数据结构和算法，使学生初步具备一个优秀的软件开发人员所应有的基本能力。 3、课程内容理念 根据本课程的教学目标，确定了课程内容体系结构的五个组成部分：集合结构、线性 表、堆栈和队列、树和二叉树、查找和排序。内容主要包括：绪论、线性表、有序线性表、堆栈、队列、树、二叉树、二叉树的遍历、顺序查找、折半查找、插入排序、选择排序等。 4、课程要求理念 《数据结构》是一门偏重理论的课程，有很强的理论性。在多年的教学研究和教学实践中，《数据结构》形成了独具特色的“七化”教学方法，即教学资源立体化、教师精讲主导化、学生学习团队化、教学过程流水化、程序项目核心化、知识技能点索引化、和C 语言结合化。 5、课程考核理念 如何客观反映出学生对数据结构的理解、掌握、综合应用的实际情况，传统的闭卷考试有不完善的地方，应该对考核内容和形式进行适当的调整，过程评价与终结评价相结合，形成全方位、更加公正客观的评价体系。考核方法采用“N+2”成绩评定方式，采用“课堂考勤＋课堂实训练习＋期末考试”的方式。 三、课程目标 （一）总目标 为学生的职业素质和职业技能的形成服务；为今后学习大数据处理技术奠定坚实的基础；为IT企业输送高质量的从业者。 （二）分目标 1、知识目标 （1）了解数据结构课程的体系结构,掌握数据结构的基本概念和基础知识。 （2）掌握线性表结构，能够运用C语言实现线性表结构； （3）掌握堆栈和队列以及树和二叉树结构。 （4）掌握查找和排序算法，并且结合项目达到在项目中运用的能力； 2、能力目标 （1）使学生初步具备一个优秀的软件开发人员所应有的基本能力：会编写基本的算法、会利用数据结构解决基础编程语言不能直接表达的数据； （2）为学生利用C进一步研究与学习大数据处理技术奠定基础。 3、情感态度价值观目标 （1）规范意识：让学生学会编写规范代码，熟悉常用程序设计技巧。 （2）团队精神：培养学生的合作精神、协调工作和组织管理的能力。 （3）探究精神：关注学科发展趋势和应用前景，注重培养学生的对新技术的探究精神。 习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后，i值为：（） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front 作业题（一） 一、单项选择题 1. 从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 2. 链表不具有的特点是（） A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 3.下面程序段的时间复杂度的量级为（）。 For(i=1;i<=n;i++) For(j=1;j<=I;j++) For(k=1;k<=j;k++) X=x+1; A．O(1) B．O(n) C．O(n2) D．O(n3) 4.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。 A．2 B．3 C．4 D．6 5、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。 A．98 B．100 C．102 D．106 6、判定一个栈s（最多元素为m0）为空的条件是（）。 A．s-〉top! =0 B．s-〉top= =0 C．s-〉top! =m0 D．s-〉top= =m0 7、循环队列用数组A[m]（下标从0到m-1）存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。 A．（rear-front+m）%m B．rear-front+1 C．rear-front-1 D． rear-front 8、设有两个串S1与S2，求串S2在S1中首次出现位置的运算称作（）。 A．连接 B．求子串 C．模式匹配 D．判子串 9、设串S1='ABCDEFG'，S2='PQRST'，函数con（x，y）返回x和y串的连接串，subs(s,i,j)返回串S的的从序号i的字符开始的j个字符组成的子串，len(s)返回串S的长度，则con(subs(S1,2,len(S2)),subs(S1,len(S2),2))的结果是（）。 《数据结构（本科）》课程设计方案导学方案 刘鹏 《数据结构（本科）》 课程设计方案导学方案 一、课程基本说明 课程对象：全国电大系统开放教育试点计算机科学与技术专业（专科起点本科）学生课程学时：72学分 课程学分：4学分 开课情况：从2000年春开始，一直开设至今。课程主讲和主编一直是清华大学殷人昆教授。 课程的基本特点：是计算机科学与技术专业的基础必修课，对学生进行基础性的、数据结构分析和算法设计能力的，为后续的操作系统、计算机网络、数据库、软件工程等课程奠定基础。 先修课程：面向对象程序设计 二、课程的内容体系及教学要求 第一部分有关数据结构和算法分析的基本知识 教学知识点： 数据逻辑结构和存储结构的定义和分类； 数据类型与抽象数据类型的概念； 面向对象的概念； 算法的特性； 算法的性能分析与度量，时间复杂度，空间复杂度，时间复杂度和空间复杂度的渐进表示法。 教学要求： 理解：有关数据结构的基本概念，抽象数据类型及面向对象的概念，算法的定义及算法的特性。 应用：算法的性能分析与度量方法。 第二部分数组 教学知识点： 作为抽象数据类型的数组：数组类的定义和初始化，相关操作的实现。 顺序表：顺序表类的定义；顺序表的查找、插入和删除算法。 稀疏矩阵：稀疏矩阵的抽象数据类型和压缩表示。 字符串：字符串类的定义和有关操作的实现。 教学要求： 理解：数组类的定义和操作实现，顺序表类的定义及操作实现，字符串类的定义及操作实现，稀疏矩阵的定义和表示。 应用：能够分析和设计带有数组类、顺序表类、字符串类的成员函数并分析其时间和空间复杂度，会把三角矩阵、对称矩阵、三对角矩阵等特殊矩阵用一维数组存储起来，并进行相应元素地址的计算。 第三部分链接表 教学知识点： 单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带表头结点的单链表；用模板定义的单链表类；静态链表。 循环链表：循环链表的类定义。 多项式及其相加：多项式的类定义；多项式的加法。 双向链表及其操作。 教学要求： 理解：单链表、循环链表及双向链表的定义及实现，多项式类的定义及其加法运算。 应用：针对单链表的各种插入、删除等运算的算法及性能分析。 第四部分栈与队列 教学知识点： 栈：栈的抽象数据类型；栈类的顺序存储表示和运算；栈类的链接存储表示和运算；利用栈进行表达式的计算。 队列：队列的抽象数据类型；队列类的顺序存储表示和运算；队列类的链接存储表示和运算。 优先级队列：优先级队列的定义；优先级队列的存储表示和操作实现。 教学要求： 理解：栈的定义及操作的实现，队列的定义及操作的实现，优先级队列的定义及操作的实现。 应用：表达式的各种表示法、相互转换和求值过程，按层次输出二项展开式的系数（杨 数据结构教案第七章图 第7章图 【学习目标】 1．领会图的类型定义。 2．熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。 3．熟练掌握图的两种遍历算法。 4．理解各种图的应用问题的算法。 【重点和难点】 图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。 【知识点】 图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径 【学习指南】 离散数学中的图论是专门研究图性质的一个数学分支，但图论注重研究图的纯数学性质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据结构，因此和线性表、树不同，虽然在遍历图的同时可以对顶点或弧进行各种操作，但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法，在本章中主要是介绍它们在计算机中的具体实现。这些算法乍一看都比较难，应多对照具体图例的存储结构进行学习。而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似，应将两者的算法对照学习以便提高学习的效益。 【课前思考】 1. 你有没有发现现在的十字路口的交通灯已从过去的一对改为三对，即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。你能否对某个丁字路口的6条通路画出和第一章绪论中介绍的"五叉路口交通管理示意图"相类似的图？ 2. 如果每次让三条路同时通行，那么从图看出哪些路可以同时通行？ 同时可通行的路为：(AB,BC,CA),(AB,BC,BA),(AB,AC,CA),(CB,CA,BC) 《数据结构》课程教学设计 一、课程内容体系 1. 基本描述 课程中文名称:数据结构 课程英文译名:Data Structures 总学时:授课 40 学时＋实验 20 学时 授课对象:计算机专业、自动化专业、信息专业、通讯专业、数学专业 课程要求:必修课 课程分类:专业（技术）基础 开课时间:第4学期 先修课:工科数学分析、高级语言程序设计或C++程序设计、集合与图论2. 教学定位 《数据结构》是计算机科学与技术各专业及其相关的一门专业基础课；是计算机科学与技术专业课程体系中的核心课程之一；是设计和实现编译程序、操作系统、数据库系统和其它系统软件、应用软件的重要基础。其后续课程有操作系统、编译原理、数据库系统概论、算法分析、图像处理等。在整个计算机知识体系中，数据结构具有不可替代的作用。瑞士著名的计算机科学家沃思教授曾提出:算法＋数据结构＝程序。算法:是对数据运算的描述；数据结构:是指数据的逻辑结构和存储结构。程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。由此可见数据结构在解决计算机问题中的重要地位。 学习本课程旨在使学生较全面地掌握各种常用的数据结构，为学习后续软件课程提供必要的基础，掌握和不断提高运用数据结构解决实际问题的能力。通过本门课程的学习，使学生透彻地理解各种数据结构对象的特点，学会各种数据结构的组织方法和实现方法，并进一步培养良好的程序设计编程能力。同时，学习《数据结构》的过程也是复杂程序设计的训练过程，要求学生编 写的程序结构清楚、正确易读，符合软件过程的规范，从而培养学生的数据抽象能力。因此，要想有效地进行数据组织和程序开发，就必须掌握数据结构的知识。 课程的内容重点立足于基础知识和基础理论的掌握、应用能力的培养以及实践能力的提高。该课程通过一些最常用的数据结构的介绍，阐明了数据结构内在的逻辑关系，讨论它们在计算机中的存储表示，并结合各种典型应用说明它们在进行各种运算时的动态性质及实际的执行算法。具体来说，就是从数据结构的逻辑结构、存储结构和数据的操作三个方面使学生较好的掌握线性表、树、二叉树、图和文件等常用的数据结构的基本概念及构建方法。并掌握在各种常用数据结构上实现的查找和排序算法。同时对算法的时间和空间复杂性有一定的分析能力。在课程学习结束后要求学生针对简单的应用问题，能够选择合适的数据结构设计并编写出有效的算法程序。 本课程是实践性很强的一门课程，不但要求学生要深刻理会相应的基本理论、基本原理等知识，还要求学生亲自动手设计、上机实现各种算法，以达到使学生理论与实践相结合，综合应用各知识点的目的，巩固、加深所学的理论，并培养学生的科学研究能力和创新精神，并为后继课程的学习奠定坚实的基础。 3. 知识点与学时分配 第一章绪论（1学时） 数据结构的基本概念和术语；数据结构在软件系统中的作用；课程的研究和学习内容等；算法及其特征；算法性能度量指标；算法时间和空间复杂性及其分析方法。 第二章线性表（4学时） 线性表的逻辑结构、各种存储结构、基本操作（算法）的实现及性能分析、不同存储结构的比较、线性表的应用等。 第三章栈与队列（4学时） 栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本操作。栈和队列的本质区别，并且能在相应的应用问题中正确选用它们。栈和队列的应用。 《数据结构》课程设计教学任务书 计算机2007-1 课程设计周数：第20周指导老师：刘文娟 一、课程设计的目的 数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力； ?训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科 学的工作方法和作风。 二、课程设计的基本要求 1、独立思考，独立完成：课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。 2、做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。 3、按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成； 其中包括： a）需求分析： 在该部分中叙述，每个模块的功能要求 b）概要设计 在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）。 c）详细设计 各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现） 源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。 d）调试分析 测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。 e）课程设计总结：（保存在word文档中）总结可以包括：课程设计过程的收获、遇到 《数据结构（C语言版）》教案 《数据结构（C语言版）》教案 2020 至2020 学年第一学期教案课程名称数据结构使用教材《数据结构（C语言版）》教学时数56课程性质必修任课班级（人数）信管（53人）信息系（部）信管教研室任课教师山东科技大学泰山科技学院课时授课计划2020-2020学年第二学期 第1周授课日期2月20 日星期1 月日星期月日星期月日星期月日星期班级信管10-1 基本课题第1章绪论 1.1-1.2 教学目的与要求： 1. 了解数据结构的基本概念 2. 理解常用术语教学重点： 数据结构的基本概念和术语教学难点： 数据元素之间的四种结构关系作业及参考书： 1、什么是数据结构？《数据结构算法实现及解析》/高一凡编著教具： 多媒体板书课堂类型： 讲授教学过程：自我介绍——开课——引入——展开——举例——小结——作业一、自我介绍和课程介绍约8min 课时：64 二、引入约2min 由问题的提出引入三、讲课进程设计1.1 什么是数据结构 1.1.1、数据结构与其它的关系约15min 数据结构+算法=程序程序设计: 为计算机处理问题编制一组指令集算法: 处理问题的策略数据结构: 问题的数学模型 1.1.2、当今计算机应用的特点： 约25min l) 所处理的数据量大且具有一定的关系； 2) 对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。 举例说明： 1) 学生成绩表2)井安棋对弈3)交通管理结论计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理； 我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。 1.2 基本概念和术语1.1.1、数据与数据结构约20min 数据：是对客观事物的符号表 《数据结构》教案 安庆师范学院 教案（课时计划） 课程名称：数据结构 授课班级： 授课地点： 主讲教师：程玉胜 2 2015----2016 学年第2学期 3 目录 01、数据结构的概念及相关术语 02、抽象数据类型的表示与实现、算法和算法分析 03、线性表的类型定义、线性表的顺序表示和实现 04、线性表的链式表示和实现（线性链表） 05、循环链表、双向链表、一元多项式的表示及相加 06、栈、栈应用举例（数制转换、括号匹配、行编辑） 07、迷宫求解、表达式求值、栈与递归的实现 08、队列 09、机动 10、习题课 11、串类型的定义、串的表示和实现 4 12、串的模式匹配算法、串操作应用举例 13、数组的定义、顺序表示和实现、矩阵的压缩存储 14、稀疏矩阵的存储结构、广义表 15、树的定义和基本术语、二叉树的定义 16、二叉树的性质、二叉树的存储结构 17、遍历二叉树和线索二叉树 18、树和森林 19、赫夫曼树及其应用 20、习题课 21、图的定义和术语、图的存储结构 22、十字链表、邻接多重表、图的遍历 23、图的连通性问题 24、有向无环图及其应用 25、最短路径 26、静态查找表 27、二叉排序树和平衡二叉树 5 28、B-树和B+树 29、哈希表 30、排序概述、插入排序 31、快速排序、选择排序 32、归并排序、基数排序 33、外部排序、各种排序方法的比较 34、文件 编号 1 周次1日期9.3课时安排2课题数据结构的概念及相关术语 教材的重点、难点分析重点：(1)数据结构的逻辑结构 (2)数据结构的存储结构 (3)抽象数据类型的概念 教学目标掌握数据、数据元素、数据对象的概念 熟练掌握数据结构的概念及其逻 6 《数据结构》教学大纲 课程性质：学科基础课程 适用专业：计算机科学与技术、网络工程、数字媒体技术 先行课：计算机科学导论、离散数学、高级语言程序设计； 选用教材及参考资料（与考试大纲一致） 教材：1．任燕主编《数据结构C++语言描述》，清华大学出版社，2011年 2. 严蔚敏《数据结构（C语言版）》清华大学出版社出版 实验教材： 1、任燕主编《数据结构上机实验指导C++语言描述》，清华大学出版社，2011年 2、系自制的实验指导 一、课程的目的与任务 数据结构是信息与计算科学专业中一门重要的专业基础课程。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构课程在计算机应用专业中具有举足轻重的作用。 本课程的目的是使学生掌握数据组织、存储和处理的常用方法，为以后进行软件开发和学习后续专业课程打下基础。主要任务是讨论现实世界中数据的各种逻辑结构，在计算机中的存储结构以及进行各种非数值运算的算法。 本课程达到《认证通用标准》规定中关于“毕业要求”的第三款项（具有运用工程基础知识和本专业基本理论知识解决问题的能力，具有系统的工程实践学习经历；了解本专业的前沿发展现状和趋势）、第四款项（具备设计和实施工程实验的能力，并能够对实验结果进行分析）。 二、课程的基本要求 通过本课程的学习，要求学生了解数据结构及其分类、数据结构与算法的密切关系；熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构；掌握设计算法的步骤和算法分析方法；掌握数据结构在排序、查找和路由选择等常用算法中的应用。 最后学生应达到知识技能两方面的目标：在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。 三、课程教学内容 第一章绪论 基本要求: 掌握数据结构的基本概念，抽象数据类型在软件设计中的意义，算法的概念和算法的时间复杂度分析，了解算法的描述和评价。 基本知识点: 数据结构的基本概念； 《数据结构》课程教案 课程类别：专业基础课 适用专业：计算机应用技术 授课学时：32学时 课程学分：4学分 一、课程性质、任务 课程性质：《数据结构》是计算机应用技术专业的必修课程，也是研究如何对数据进行组织和设计、如何编制高效率的处理程序的一门基础学科。 课程任务： 1、学习计算机程序编写中的数据组织和设计； 2、数据的物理结构和逻辑结构； 3、经典算法的设计和算法效率的分析。 二、课程培养目标： （一）知识目标 通过理论学习和程序的编写，使学生系统地掌握程序中数据的组织、数据的物理结构和逻辑结构，在重要算法的实现上逐步提高编程能力。 （二）技能目标 通过课程的学习，让学生掌握重要的数据结构，对数据的逻辑结构和物理结构有深入的理解，同时能编写出使用重要算法知识的程序，并运用所学知识编写程序解决实际中的问题。 （三）素质目标 通过课程的学习，让学习学会自学，培养学生的自学能力、克服学习困难的能力，同时让学生掌握计算机编程中数据结构的学习方法，并养成严谨、认真、仔细、踏实、上进的好习惯。 三、选用教材与参考资料 教材版本信息 《数据结构与算法简明教程（Java语言版）》清华大学出版社叶小平陈瑛主编 教材使用评价 本教材经过两年的使用，得到了读者一致认可，同时也在不断改进，适合高职高专教学使用，内容基础、重难点突出，符合高职高专“理论够用、注重实践”的要求。 选用的参考资料 严蔚敏.吴伟民《数据结构（C语言版）》.清华大学出版社.2009年版 殷人昆.《数据结构》.清华大学出版社.1999年版 《C语言程序设计》.石油大学出版社 《C语言程序设计》.中国石油大学出版社.2006年版 四、本课程与其他课程的联系与分工 先修课程 《离散数学》、《程序设计基础》 后续课程 《面向对象技术》、《操作系统》 与其他课程配合与取舍情况 《数据结构》与《离散数学》知识点结合较多，《离散数学》讲求逻辑思维能力的培养和训练，《数据结构》中逻辑结构的学习也需要逻辑思维能力做铺垫。同时《程序设计基础》课程也为学习《数据结构》打下了基础，对于本课程的教材，我们采用C语言来描述数据结构，因此程序设计基础也是以C语言作为的对象。本课程也与《算法设计与分析》结合得很紧密，因此在学习中我们也会引入常见算法的学习，达到两者共同促进的目的。 五、课程教学内容与基本要求 第一章数据结构导论 （一）、教学内容 第一节数据结构的基本概念 一、引言 二、数据结构有关概念及术语 第二节算法和算法描述 一、什么是算法 二、算法描述工具——类C语言 第三节算法评价 一、时间 二、空间 （二）、教学目的要求 通过本章的学习让学生了解数算法的基本概念，理解如何运用类C语言来描述算法，掌握据结构的概念和相关术语、算法的描述方法，学会从程序中分析算法效率和用函数式表示该程序的算法效率。 在学完本章后，要求学生对数据结构的涉及领域有大体的认识，同时了解数据结构的作用，明确数据结构和程序开发的关系。通过对算法效率的分析，学会使用这一知识点来优化自己所写程序的执行效率。 数据结构教案C语言版 Last updated on the afternoon of January 3, 2021 课程教案 课程名称：数据结构 授课教师： 学习对象： 任课时间： 一、学生情况分析 数据结构是计算机专业的一门核心专业课程。学生在前期的学习中已经学习了C语言程序设计课程。通过本课程学习使学生对提高编写程序的能力以及解决实际问题的能力。 二、课程教学目标 《数据结构》是计算机学科中一门核心专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。 三、课程教学内容 第一章绪论 教学内容： 1）什么是数据结构 2）抽象数据类型概念；数据类型；数据抽象与抽象数据类型；用于描述数据结构的语言 3）数据结构的抽象层次 4）算法定义 5）性能分析与度量；算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法； 教学要求： 了解：数据结构基本概念及数据结构的抽象层次 了解：抽象数据类型概念 了解：算法的定义及算法特性 掌握：算法的性能分析与度量方法 第二章线性表 教学内容： 1）线性表的定义和特点 2）线性表的顺序存储及查找、插入和删除操作 3）线性表的链式存储及查找、插入和删除操作 4）使用线性表的实例 教学要求： 了解：线性表的定义和特点 熟练掌握：线性表的顺序存储结构的查找、插入和删除等基本操作 熟练掌握：单链表、循环链表及双向链表的定义及实现 掌握：熟练掌握单链表的应用方法 数据结构课程设计报告题目：哈夫曼树和编码应用 学生姓名： 学号： 班级： 指导教师： 2011年 6 月3日 目录 ●课程设计目的------------------------3 ●课程设计题目------------------------3 ●需求分析----------------------------4 ●设计原理----------------------------4 ●系统功能框架图----------------------5 ●流程图------------------------------6 ●设计思路----------------------------7 1.主函数 2.创建哈夫曼树 3.输出哈夫曼树 4.对哈夫曼树进行编码 5.译码 ●程序源代码--------------------------8 ●运行结果----------------------------13 ●实验心得----------------------------21 一、课程设计目的 本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。 二、课程设计题目--哈夫曼树和编码应用 （1）从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树的存储结构； （2）利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对给定的n个字符正文进行编码，并输出每个字符的编码。 （3）利用已建好的哈夫曼树，对给定的一个哈夫曼编码进行译码，判断此编码对应的字符序列，并输出结果。 三、需求分析 1、利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（既可以双向传输信息的信道），每端都需要一个完整的编/译码系统。本次设计就是为这样的信息收发站写的一个哈夫曼的编/译码器。 本实验要求： 2、本演示程序中，用户可以输入键盘中的任意字符，长度为任意长，字符输入顺序不限，且允许出现重码 3、演示程序以用户与计算机的对话方式执行，即在计算机终端上显示“提示信息” 课程简介 人们在运用程序设计语言编写程序的过程中发现所有的数据都可以抽象为三种结构，而对这些数据的所有操作都可以转化为对这三种数据的几种基本操作，而大多数的程序设计技巧都可以抽象为一些最基本的算法。于是人们逐步发展了一门称为数据结构（或数据结构与算法）的计算机科学，它广泛应用于计算机领域。 数据结构是信息与计算专业的核心基础课程之一。数据是计算机处理的对象，本课程研究的数据是非数值性、结构性的数据。学习本课程要求掌握各种主要数据结构的特点、计算机内的表示方法，以及处理数据的算法，对于算法所花费的时间和空间代价的分析也要求有一定程度的了解和掌握。通过本课程的学习，使学生透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养基本的良好的程序设计能力。本课程主要包括如下三个方面的内容： 1．基本数据结构：线性表、栈、队列、串、数组和广义表，掌握它们的特点、表示和实现，对静态结构要求非常熟练的编程上机实现，对动态结构要求逐步熟悉链表的表示，通过模仿实验教程中的例子，掌握编程技巧。强调类C语言的书写规范，特别注意参数的区别，输入输出的方式和错误处理方式，以及抽象数据类型的表示和实现。能熟练完成以下的应用：多项式的计算、语法检查、回朔算法、递归算法、表达式求值、离散事件模拟、文字的编辑和稀疏矩阵进行矩阵运算采用的处理方法。 2．复杂数据结构：树、二叉树、图。掌握它们的定义和特点、表示和实现，特别注意与基本数据结构的区别，掌握各种遍历的递归和非递归算法，能熟练完成以下的应用：最优树、Huffman编码、拓扑排序、关键路径和最短路径问题。 3．数据结构的应用：查找和内部排序。熟练掌握静态查找表的查找方法和实现，了解哈希表的构造和查找方法。掌握各种内部排序方法的基本思想、算法特点、排序过程以及它们的时间复杂度分析。 课程教案 课程名称：数据结构授课教师： 学习对象： 任课时间： 一、学生情况分析 数据结构是计算机专业的一门核心专业课程。学生在前期的学习中已经学习了C语言程序设计课程。通过本课程学习使学生对提高编写程序的能力以及解决实际问题的能力。 二、课程教学目标 《数据结构》是计算机学科中一门核心专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。 三、课程教学内容 第一章绪论 教学内容： 1）什么是数据结构 2）抽象数据类型概念；数据类型；数据抽象与抽象数据类型；用于描述数据结构的语言 3）数据结构的抽象层次 4）算法定义 5）性能分析与度量；算法的性能标准；算法的后期测试；算法 的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度 的渐进表示法； 教学要求： 了解：数据结构基本概念及数据结构的抽象层次 了解：抽象数据类型概念 了解：算法的定义及算法特性 掌握：算法的性能分析与度量方法 第二章线性表 教学内容： 1）线性表的定义和特点 2）线性表的顺序存储及查找、插入和删除操作 3）线性表的链式存储及查找、插入和删除操作 4）使用线性表的实例 教学要求： 了解：线性表的定义和特点 熟练掌握：线性表的顺序存储结构的查找、插入和删除等基本操作 熟练掌握：单链表、循环链表及双向链表的定义及实现 掌握：熟练掌握单链表的应用方法 第三章栈和队列 教学内容： 1）栈：栈的抽象数据类型；栈的顺序存储表示；栈的链式存储表示 2）队列：队列的抽象数据类型；队列的顺序存储表示；队列的链式存储表示 3）队列的应用举例 教学要求：《数据结构》教学设计方案
《数据结构》教学纲要(doc 9页)
数据结构教案课程
《数据结构》课程标准.doc
第三章栈和队列习题_数据结构电子教案
数据结构专升本模拟题及参考答案讲课教案
数据结构课程(本科)教学设计方案
(完整版)数据结构详细教案——图
《数据结构》课程教学设计
数据结构课程设计教学任务书
《数据结构(C语言版)》教案
《数据结构》教案
任燕主编《数据结构》教学大纲
《数据结构》课程教案
数据结构教案C语言版
数据结构课程教学设计报告
数据结构教案
数据结构教案C语言版
相关主题
文本预览