|
数据结构教程 |
||
|
第一课
本课主题：数据结构的基本概念和术语
教学目的：了解数据结构的基本概念，理解常用术语
教学重点：基本概念：数据与数据元素
教学难点：数据元素间的四种结构关系。
授课内容：
一、数据、数据元素、数据对象、数据结构的定义
1、数据的定义
定义一：数据是客观事物的符号表示。
|
学号 |
姓名 |
语文 |
数学 |
C语言 |
|
6201001 |
张三 |
85 |
54 |
92 |
|
6201002 |
李四 |
92 |
84 |
64 |
|
6201003 |
王五 |
87 |
74 |
73 |
|
6201004 |
|
|
|
|
|
... |
|
|
|
|
例：张三的C语言考试成绩为92分，92就是该同学的成绩数据。
定义二：能输入到计算机中并被计算机程序处理的符号的总称。
例：图像、声音等。
总结：现实世界信息的分析、复制、传播首先要符号化，这样才便于处理，尤其是便于计算机的处理。家长、社会要了解一个学生的学习成绩和能力，要看他的学习档案，而学习档案即是说明该学生学习情况的数据。
2、数据元素、数据项
数据元素是数据的基本单位，它也可以再由不可分割的数据项组成。如图示：
3、数据对象
是性质相同的数据元素的集合。如上例：一个班级的成绩表可以看作一个数据对象。
4、数据结构
定义一、数据元素集合（也可称数据对象）中各元素的关系。
定义二、相互之间存在特定关系的数据元素集合。
|
|
特征 |
示例 |
|
集合 |
元素间为松散的关系 |
|
|
线性结构 |
元素间为严格的一对一关系 |
如上面的成绩表中各元素 |
|
树形结构 |
元素间为严格的一对多关系 |
|
|
图状结构（或网状结构） |
元素间为多对多关系 |
|
数据结构的形式定义：
数据结构名称=（D，S）
其中D为数据元素的有限集，S是D上关系的有限集
|
逻辑结构 |
|
“数据结构”定义中的“关系”指数据间的逻辑关系，故也称数据结构为逻辑结构。 |
|
存储结构 |
|
数据结构在计算机中的表示称为物理结构。又称存储结构。 |
|
顺序存储结构 |
||
|
链式存储结构 |
存储结构详解：
计算机中存储信息的最小单位：位，8位为一字节，两个字节为一字，字节、字或更多的二进制位可称为位串。在逻辑描述中，把位串称为元素或结点。
当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域(Data Field)。
例：上述成绩表数据用C语言的结构体数组classonestu[50]来存储：
struct
stu {
int stuno;/*数据项，也称stu位串中的一个子位串，或叫做数据域*/
char name[20];
int maths;
int language;
int c_language;
} classonestu[50];
二、数据类型
1、定义：数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
例：C语言中的整型，其内涵为一定范围的自然数集合，及定义在该集合上的加减乘除及取模、比较大小操作。而实型则无取模操作。当然整型也不需四舍五入。
2、数据类型的种类：
|
|
特征 |
例 |
|
原子类型 |
值在逻辑上不可分解 |
int float |
|
结构类型 |
值由若干成分按某种结构组成 |
struct stu |
数据类型封装了数据存储与操作的具体细节。
三、总结
数据->数据元素
具有特定关系的数据元素集合->数据结构
数据结构的逻辑表示与物理存储->逻辑结构与存储结构
人们不仅关心数据的逻辑结构、存储结构，还关心数据的处理方法（算法）与处理结果->数据类型
数据类型->分类
第二课
本课主题： 抽象数据类型的表示与实现
教学目的： 了解抽象数据类型的定义、表示和实现方法
教学重点： 抽象数据类型表示法、类C语言语法
教学难点： 抽象数据类型表示法
授课内容：
一、抽象数据类型定义（ADT）
作用：抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系。
定义：一个数学模型以及定义在该模型上的一组操作。
关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。
例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继。可以有这样一些操作：插入一个元素、删除一个元素等。
|
抽象数据类型分类 |
|
|
原子类型 |
值不可分解，如int |
|
固定聚合类型 |
值由确定数目的成分按某种结构组成，如复数 |
|
可变聚合类型 |
值的成分数目不确定如学生基本情况 |
抽象数据类型表示法：
三元组表示：（D，S，P）
其中D是数据对象，S是D上的关系集，P是对D的基本操作集。
二、书中的定义格式：
ADT 抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
}ADT 抽象数据类型名
例：线性表的表示
|
名称 |
线性表 |
|
|
数据对象 |
D={ai| ai(-ElemSet,i=1,2,...,n,n>=0} |
任意数据元素的集合 |
|
数据关系 |
R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n} |
除第一个和最后一个外，每个元素有唯一的直接前趋和唯一的直接后继 |
|
基本操作 |
ListInsert(&L,i,e) |
L为线性表，i为位置，e为数据元素。 |
|
ListDelete(&L,i,e) |
||
|
... |
二、类C语言语法
|
类C语言语法示例 |
|
|
|||
|
1、预定义常量和类型 |
#define TRUE 1 |
|
|||
|
2、数据结构的存储结构 |
typedef ElemType first; |
|
|||
|
3、基本操作的算法 |
函数类型 函数名（函数参数表）{ |
|
|||
|
4、赋值语句 |
简单赋值： |
变量名=表达式； |
|
||
|
串联赋值： |
变量名1=变量名2=...=变量名k=表达式； |
|
|||
|
成组赋值: |
（变量名1，...,变量名k）=（表达式1，...,表达式k); |
||||
|
交换赋值： |
变量名<-->变量名； |
|
|
||
|
条件赋值： |
变量名=条件表达式？表达式？表达式T：表达式F |
|
|
||
|
5、选择语句 |
1、if（表达式） 语句； ... ... |
|
|
||
|
6、循环语句 |
for（赋初值表达式；条件；修改表达式序列）语句； |
|
|
||
|
7、结束语句 |
return [表达式]； |
|
|
||
|
8、输入和输出语句 |
scanf（[格式串]，变量1，...,变量n）； |
|
|
||
|
9、注释 |
//文字序列 |
|
|
||
|
10、基本函数 |
max（表达式1，...，表达式n） |
|
|
||
|
11、逻辑运算 |
&&与运算；||或运算 |
|
|
||
数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
数据关系: R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n}
基本操作：
InitList(&L)
DestroyList(&L)
ListInsert(&L,i,e)
ListDelete(&L,i,&e)
}ADT List
ListInsert(List &L,int i,ElemType e)
{if(i<1||i>L.length+) return ERROR;
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;
*q=e;
++L.length;
return OK;
}
下面是C语言编译通过的示例：
|
#define ERROR 0 strcpy(e.name,"bobjin"); |
|
E:\ZM\Zmdoc\datastru\class02>listdemo name stuno age score zmofun 100001 80 1000 List length now is 1. name stuno age score bobjin 100002 80 1000 zmofun 100001 80 1000 List length now is 2. |
三、总结
第三课
本课主题： 算法及算法设计要求
教学目的： 掌握算法的定义及特性，算法设计的要求
教学重点： 算法的特性，算法设计要求
教学难点： 算法设计的要求
授课内容：
一、算法的定义及特性
1、定义：
ispass(int num[4][4])
{
int i,j;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
if(num[i][j]!=i*4+j+1)/*一条指令，多个操作*/
return 0;
return
1;
}/*上面是一个类似华容道游戏中判断游戏是否结束的算法*/
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列五个重要特性：
|
有穷性 |
一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成； |
|
确定性 |
算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。有任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。 |
|
可行性 |
一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 |
|
输入 |
一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。 |
|
输出 |
一个算法有一个或多个的输出。这些输出是同输入有着某些特定关系的量。 |
例：
|
有穷性 |
haha() |
|
确定性 |
float average(int *a,int num) |
|
可行性 |
|
|
输入 |
|
|
输出 |
getsum(int num) |
二、算法设计的要求
1、正确性
|
算法正确性的四个层次 |
|
|
程序不含语法错误。 |
max(int a,int b,int c) |
|
程序对于几组输入数据能够得出满足规格说明要求的结果。 |
max(int a,int b,int c) |
|
程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。 |
max(int a,int b,int c) |
|
程序对于一切合法的输入数据都能产生满足规格说明要求的结果。 |
|
2、可读性
3、健壮性
4、效率与低存储量需求
效率指的是算法执行时间。对于解决同一问题的多个算法，执行时间短的算法效率高。
存储量需求指算法执行过程中所需要的最大存储空间。
|
|
算法一 |
算法二 |
|
在三个整数中求最大者 |
max(int a,int b,int c) |
max(int a[3]) |
|
求100个整数中最大者 |
同上的算法难写，难读 |
max(int a[100]) |
三、总结
1、算法的特性
2、算法设计要求：正确性、可读性、健壮性、效率与低存储量需求。
第四课
本课主题： 算法效率的度量和存储空间需求
教学目的： 掌握算法的渐近时间复杂度和空间复杂度的意义与作用
教学重点： 渐近时间复杂度的意义与作用及计算方法
教学难点： 渐近时间复杂度的意义
授课内容：
一、算法效率的度量
算法执行的时间是算法优劣和问题规模的函数。评价一个算法的优劣，可以在相同的规模下，考察算法执行时间的长短来进行判断。而一个程序的执行时间通常有两种方法：
1、事后统计的方法。
缺点：不利于较大范围内的算法比较。（异地，异时，异境）
2、事前分析估算的方法。
|
程序在计算机上运行所需时间的影响因素 |
|
|
算法本身选用的策略 |
|
|
问题的规模 |
规模越大，消耗时间越多 |
|
书写程序的语言 |
语言越高级，消耗时间越多 |
|
编译产生的机器代码质量 |
|
|
机器执行指令的速度 |
|
综上所述，为便于比较算法本身的优劣，应排除其它影响算法效率的因素。
从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。 （原操作在所有该问题的算法中都相同）
T(n)=O(f(n))
上示表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。
|
求4*4矩阵元素和，T(4)=O(f(4)) f=n*n; |
sum(int num[4][4]) { int i,j,r=0; for(j=0;j<4;j++) r+=num[i][j]; /*原操作*/ return r; |
|
最好情况： 最坏情况： |
ispass(int num[4][4]) { int i,j; for(j=0;j<4;j++) if(num[i][j]!=i*4+j+1) return 0; return 1; |
原操作执行次数和包含它的语句的频度相同。语句的频度指的是该语句重复执行的次数。
|
语句 |
频度 |
时间复杂度 |
|
{++x;s=0;} |
1 |
O(1) |
|
for(i=1;i<=n;++i) {++x;s+=x;} |
n |
O(n) |
|
for(j=1;j<=n;++j) for(k=1;k<=n;++k) {++x;s+=x;} |
n*n |
O(n*n) |
|
|
|
O(log n) |
|
|
|
|
|
基本操作的执行次数不确定时的时间复杂度 |
|
|
平均时间复杂度 |
依基本操作执行次数概率计算平均 |
|
最坏情况下时间复杂度 |
在最坏情况下基本操作执行次数 |
二、算法的存储空间需求
类似于算法的时间复杂度，空间复杂度可以作为算法所需存储空间的量度。
记作：
S(n)=O(f(n))
若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。
如果所占空间量依赖于特定的输入，则除特别指明外，均按最坏情况来分析。
三、总结
渐近时间复杂度
空间复杂度
第五课
本课主题： 线性表的类型定义
教学目的： 掌握线性表的概念和类型定义
教学重点： 线性表的类型定义
教学难点： 线性表的类型定义
授课内容：
复习：数据结构的种类
线性结构的特点：
|
在数据元素的非空有限集中， （1）存在唯一的一个被称做“第一个”的数据元素； （2）存在唯一的一个被称做“最后一个”的数据元素； （3）除第一个之外，集合中的每个数据元素均只有一个前驱； （4）除最后一个之外，集合中每个数据元素均只有一个后继。
|
|
|
||||||||||||||
线性表是最常用且最简单的一种数据结构。
一个线性表是n个数据元素的有限序列。
数据元素可以是一个数、一个符号、也可以是一幅图、一页书或更复杂的信息。
线性表例：
1、
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
2、
|
|
|
|
|
|
|
|
3、
|
学号 |
姓名 |
语文 |
数学 |
C语言 |
|
6201001 |
张三 |
85 |
54 |
92 |
|
6201002 |
李四 |
92 |
84 |
64 |
|
6201003 |
王五 |
87 |
74 |
73 |
|
6201004 |
|
|
|
|
|
... |
|
|
|
|
数据元素也可由若干个数据项组成（如上例3）。这时常把数据元素称为记录。含有大量记录的线性表又称文件。
线性表中的数据元素类型多种多样，但同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。
|
a1 |
... |
ai-1 |
ai |
ai+1 |
... |
an |
ai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。
线性表中元素的个数n定义为线性表的长度，为0时称为空表。在非空表中的每个数据元素都有一个确定的位置。ai是第i个元素，把i称为数据元素ai在线性中的位序。
1、抽象数据类型线性表的定义如下：
ADT List{
数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
数据关系: R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n}
基本操作：
InitList(&L)
DestroyList(&L)
ClearList(&L)
ListEmpty(L)
ListLength(L)
GetElem(L,i,&e)
LocateElem(L,e,compare())
PriorElem(L,cur_e,&pre_e)
NextElem(L,cur_e,&next_e)
ListInsert(&L,i,e)
ListDelete(&L,i,&e)
ListTraverse(L,visit())
union(List &La,List &Lb)
}ADT List
2、部分操作的类C实现：
InitList(&L)
{L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)exit(OVERFLOW);
L.length=0;
L.listsize=LIST_INIT_SIZE;
return OK;
}//InitList
GetElem(L,i,&e)
{*e=L.lem[i]
}//GetElem
ListInsert(List &L,int i,ElemType e)
{if(i<1||i>L.length+) return ERROR;
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;
*q=e;
++L.length;
return OK;
}//ListInsert
void union(List &La,List &Lb)
{La_len=ListLength(La);Lb_len=ListLength(Lb);
for(i=1;i<=Lb_len;i++){
GetElem(Lb,i,e);
if(!LocateElem(La,e,equal))
ListInsert(La,++La_len,e);
}//union
void MergeList(List La,List Lb,List &Lc)
{InitList(Lc);
i=j=1;k=0;
La_len=ListLength(La);Lb_len=ListLength(Lb);
while((i<=La_len)&&(j<Lb_len)){
GetElem(La,i,ai);GetElem(Lb,j,bj);
if(ai<=bj){ListInsert(Lc,++k,ai);++i;}
else{ListInsert(Lc,++k,bj);++j;}
}
while(k<=La_len){
GetElem(La,i++,ai);ListInsert(Lc,++k,ai);
}
while(j<=Lb_len){
GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);
}
}//MergeList
|
-------------------List Demo is running...---------------- Second is UnionList function. Welcome to visit http://zmofun.heha.net ! |
三、总结
第六课
本课主题： 线性表的顺序表示和实现
教学目的： 掌握线性表的顺序表示和实现方法
教学重点： 线性表的顺序表示和实现方法
教学难点： 线性表的顺序存储的实现方法
授课内容：
复习
1、存储结构
|
逻辑结构 |
|
“数据结构”定义中的“关系”指数据间的逻辑关系，故也称数据结构为逻辑结构。 |
|
存储结构 |
|
数据结构在计算机中的表示称为物理结构。又称存储结构。 |
|
顺序存储结构 |
||
|
链式存储结构 |
一、线性表的顺序表示
用一组地址连续的存储单元依次存储线性表的数据元素。C语言中的数组即采用顺序存储方式。
|
|
a[9] |
|
假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则存在如下关系：
LOC(ai+1)=LOC(ai)+l
LOC(ai)=LOC(a1)+(i-1)*l
式中LOC(a1)是线性表的第一个数据元素的存储位置，通常称做线性表的起始位置或基地址。常用b表示。
线性表的这种机内表示称做线性表的顺序存储结构或顺序映象。
称顺序存储结构的线性表为顺序表。顺序表的特点是以元素在计算机内物理位置相邻来表示线性表中数据元素之间的逻辑关系。
二、顺序存储结构的线性表类C语言表示：
|
线性表的动态分配顺序存储结构 |
|
#define LIST_INIT_SIZE 100 ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量以一数据元素存储长度为单位 }SqList; |
三、顺序存储结构的线性表操作及C语言实现：
顺序表的插入与删除操作：
|
序号 |
数据元素 |
序号 |
数据元素 |
|
序号 |
数据元素 |
序号 |
数据元素 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
->24 |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
插入前n=8;插入后n=9; |
|
删除前n=8;删除后n=7; |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
顺序表的插入算法 |
|
status ListInsert(List *L,int i,ElemType e) { struct STU *p,*q; if (i<1||i>L->length+1) return ERROR; q=&(L->elem[i-1]); for(p=&L->elem[L->length-1];p>=q;--p) *(p+1)=*p; *q=e; ++L->length; return OK; }/*ListInsert Before i */ |
|
void MergeList(List *La,List *Lb,List *Lc) { ElemType *pa,*pb,*pc,*pa_last,*pb_last; pa=La->elem;pb=Lb->elem; Lc->listsize = Lc->length = La->length + Lb->length; pc = Lc->elem = (ElemType *)malloc(Lc->listsize * sizeof(ElemType)); if(!Lc->elem) exit(OVERFLOW); pa_last = La->elem + La->length - 1; pb_last = Lb->elem + Lb->length - 1; while(pa<=pa_last && pb<=pb_last) { if(Less_EqualList(pa,pb)) *pc++=*pa++; else *pc++=*pb++; } while(pa<=pa_last) *pc++=*pa++; while(pb<=pb_last) *pc++=*pb++; } |
|
顺序表的查找算法 |
|
int LocateElem(List *La,ElemType e,int type) { int i; switch (type) { case EQUAL: for(i=0;i<length;i++) if(EqualList(&La->elem[i],&e)) return 1; break; default: break; } return 0; } |
|
顺序表的联合算法 |
|
void UnionList(List *La, List *Lb) { int La_len,Lb_len; int i; ElemType e; La_len=ListLength(La); Lb_len=ListLength(Lb); for(i=0;i<Lb_len;i++) { GetElem(*Lb,i,&e); if(!LocateElem(La,e,EQUAL)) ListInsert(La,++La_len,e); } } |
三、C语言源程序范例
四、总结
第七课
本课主题： 实验一 线性表的顺序存储实验
教学目的： 掌握顺序表的定义及操作的C语言实现方法
教学重点： 顺序表的操作的C语言实现方法
教学难点： 顺序表的操作的C语言实现方法
实验内容：
利用顺序表完成一个班级的一个学期的所有课程的管理：能够增加、删除、修改学生的成绩记录。
实验要求：
在上机前写出全部源程序。
第八课
本课主题： 线性表的链式表示与实现
教学目的： 掌握线性链表、单链表、静态链表的概念、表示及实现方法
教学重点： 线性链表之单链表的表示及实现方法。
教学难点： 线性链表的概念。
授课内容：
一、复习顺序表的定义。
二、线性链表的概念：
以链式结构存储的线性表称之为线性链表。
特点是该线性表中的数据元素可以用任意的存储单元来存储。线性表中逻辑相邻的两元素的存储空间可以是不连续的。为表示逻辑上的顺序关系，对表的每个数据元素除存储本身的信息之外，还需存储一个指示其直接衙继的信息。这两部分信息组成数据元素的存储映象，称为结点。
|
|
|
例:下图是若干抽屉，每个抽屉中放一个数据元素和一个指向后继元素的指针，一号抽屉中放线性表的第一个元素，它的下一个即第二个元素的位置标为5，即放在第5个抽屉中，而第三个放在2号抽屉中。第三个元素即为最后一个，它的下一个元素的指针标为空，用0表示。
用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示的
二、线性链表的存储实现
struct LNODE{
ElemType data;
struct LNODE *next;
};
typedef struct LNODE LNode;
typedef struct LNODE * LinkList;
头指针与头结点的区别：
头指针只相当于结点的指针域，头结点即整个线性链表的第一个结点，它的数据域可以放数据元素，也可以放线性表的长度等附加信息，也可以不存储任何信息。
三、线性表的操作实现(类C语言)
1初始化操作
Status Init_L(LinkList L){
if (L=(LinkList *)malloc(sizeof(LNode)))
{L->next=NULL;return 1;}
else return 0;
}
2插入操作
Status ListInsert_L(LinkList &L,int i,ElemType e){
p=L,j=0;
while(p&&j<i-1){p=p->next;++j;}
if(!p||j>i-1) return ERROR;
s=(LinkList)malloc(sizeof(LNode));
s->data=e;s->next=p->next;
p->next=s;
return OK;
}//ListInsert_L
3删除操作
Status ListDelete_L(LinkList &L,int i,ElemType &e){
p=L,j=0;
while(p&&j<i-1){p=p->next;++j;}
if(!p->next||j>i-1) return ERROR;
q=p->next;p->next=q->next;
e=q->data;free(q);
return OK;
}//ListDelete_L
4取某序号元素的操作
Status GetElem_L(LinkList &L,int i,ElemType &e){
p=L->next,j=1;
while(p&&j<i){p=p->next;++j;}
if(!p||j>i) return ERROR;
e=p->data;
return OK;
}//GetElem_L
5归并两个单链表的算法
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
//已知单链线性表La和Lb的元素按值非递减排列
//归并后得到新的单链线性表Lc,元素也按值非递减排列
pa=La->next;pb=Lb->next;
Lc=pc=La;
while(pa&&pb){
if(pa->data<=pb->data){
pc->next=pa;pc=pa;pa=pa->next;
}else{pc->next=pb;pc=pb;pb=pb->next;}
}
pc->next=pa?pa:pb;
free(Lb);
}//MergeList_L
四、总结
1、线性链表的概念。
2、线性链表的存储
3、线性链表的操作
第九课
本课主题： 循环链表与双向链表
教学目的： 掌握循环链表的概念，掌握双向链表的的表示与实现
教学重点： 双向链表的表示与实现
教学难点： 双向链表的存储表示
授课内容：
一、复习线性链表的存储结构
二、循环链表的存储结构
循环链表是加一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点。
循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p->next是否为空，而是它们是否等于头指针。
三、双向链表的存储结构
提问：单向链表的缺点是什么？
提示：如何寻找结点的直接前趋。
双向链表可以克服单链表的单向性的缺点。
在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。
1、线性表的双向链表存储结构
typedef struct DulNode{
struct DulNode *prior;
ElemType data;
struct DulNode *next;
}DulNode,*DuLinkList;
对指向双向链表任一结点的指针d，有下面的关系：
d->next->priou=d->priou->next=d
即：当前结点后继的前趋是自身，当前结点前趋的后继也是自身。
2、双向链表的删除操作
|
Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e){ if(!(p=GetElemP_DuL(L,i))) return ERROR; e=p->data; p->prior->next=p->next; p->next->prior=p->pror; free(p); return OK; }//ListDelete_DuL |
3、双向链表的插入操作
|
Status ListInsert_DuL(DuLinkList &L,int i,ElemType &e){ if(!(p=GetElemP_DuL(L,i))) return ERROR; if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) return ERROR; s->data=e; s->prior=p->prior; p->prior->next=s; s->next=p; p->prior=s; return OK; }//ListInsert_DuL |
四、一个完整的带头结点的线性边表类型定义：
|
typedef struct LNode{ ElemType data; struct LNode *next; }*Link,*Position;
typedef struct{ Link head,tail; int len; }LinkList;
Status MakeNode(Link &p,ElemType e); //分配由p指向的值为e的结点，并返回OK；若分配失败，则返回ERROR void FreeNode(Link &p); //释放p所指结点 Status InitLinst(LinkList &L); //构造一个空的线性链表L Status DestroyLinst(LinkList &L); //销毁线性链表L，L不再存在 Status ClearList(LinkList &L); //将线性链表L重置为空表，并释放原链表的结点空间 Status InsFirst(Link h,Link s); //已知h指向线性链表的头结点，将s所指结点插入在第一个结点之前 Status DelFirst(Link h,Link &q); //已知h指向线性链表的头结点，删除链表中的第一个结点并以q返回 Status Append(LinkList &L,Link s); //将指针s所指(彼此以指针相链)的一串结点链接在线性链表L的最后一个结点 //之后，并改变链表L的尾指针指向新的尾结点 Status Remove(LinkList &L,Link &q); //删除线性链表L中的尾结点并以q返回，改变链表L的尾指针指向新的尾结点 Status InsBefore(LinkList &L,Link &p,Link s); //已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之前， //并修改指针p指向新插入的结点 Status InsAfter(LinkList &L,Link &p,Link s); //已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之后， //并修改指针p指向新插入的结点 Status SetCurElem(Link &p,ElemType e); //已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值 ElemType GetCurElem(Link p); //已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值 Status ListEmpty(LinkList L); //若线性链表L为空表，则返回TRUE,否则返回FALSE int ListLength(LinkList L); //返回线性链表L中的元素个数 Position GetHead(LinkList L); //返回线性链表L中头结点的位置 Position GetLast(LinkList L); //返回线性链表L中最后一个结点的位置 Position PriorPos(LinkList L,Link p); //已知p指向线性链表L中的一个结点，返回p所指结点的直接前趋的值 //若无前趋，返回NULL Position NextPos(LinkList L,Link p); //已知p指向线性链表L中的一个结点，返回p所指结点的直接后继的值 //若无后继，返回NULL Status LocatePos(LinkList L,int i,Link &p); //返回p指示线性链表L中第i个结点的位置并返回OK,i值不合法时返回ERROR Position LocateElem(LinkList L,ElemType e, //返回线性链表L中第1个与e满足函数compare()判定关系的元素的位置， //若下存在这样的元素，则返回NULL Status ListTraverse(LinkList L,Status(*visit)()); //依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。 |
五、总结本课内容
循环链表的存储结构
双向链表的存储结构
第十课
本课主题： 栈的表示与实现
教学目的： 栈的数据类型定义、栈的顺序存储表示与实现
教学重点： 栈的顺序存储表示与实现方法
教学难点： 栈的定义
授课内容：
一、栈的定义
栈是限定仅在表尾进行插入或删除操作的线性表。
栈的表尾称为栈顶，表头称为栈底，不含元素的空表称为空栈。
栈的抽象数据类型定义：
ADT Stack{
数据对象:D={ai|ai(- ElemSet,i=1,2,...,n,n>=0}
数据关系:R1={<ai-1,ai>|ai-1,ai(- D,i=2,...,n}
基本操作:
InitStack(&S) 构造一个空栈S
DestroyStack(&S) 栈S存在则栈S被销毁
ClearStack(&S) 栈S存在则清为空栈
StackEmpty(S) 栈S存在则返回TRUE,否则FALSE
StackLength(S) 栈S存在则返回S的元素个数,即栈的长度
GetTop(S,&e) 栈S存在且非空则返回S的栈顶元素
Push(&S,e) 栈S存在则插入元素e为新的栈顶元素
Pop(&S,&e) 栈S存在且非空则删除S的栈顶元素并用e返回其值
StackTraverse(S,visit())栈S存在且非空则从栈底到栈顶依次对S的每个数据元素调用函数visit()一旦visit()失败,则操作失败
}ADT Stack
二、栈的表示和实现
栈的存储方式：
1、顺序栈:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置
2、链栈:利用链表实现
顺序栈的类C语言定义:
typedef struct{
SElemType *base;
SElemType *top; //设栈顶栈底两指针的目的是便于判断栈是否为空
int StackSize; //栈的当前可使用的最大容量.
}SqStack;
顺序栈的的模块说明:
struct STACK {
SElemType *base;
SElemType *top;
int stacksize;
};
typedef struct STACK Sqstack;
Status InitStack(SqStack &S);
Status DestroyStack(SqStack &S);
Status ClearStack(SqStack &S);
Status StackEmpty(SqStack S);
int StackLength(SqStack S);
Status GetTop(SqStack S,SElemType &e);
Status Push(SqStack &S,SElemType e);
Status Pop(SqStack &S,SElemType &e);
Status StackTraverse(SqStack S,Status (*visit)());
Status InitStack(SqStack &S) {
S.base=(SelemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType));
if(!S.base)exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INI_SIZE;
return OK;
}//IniStack
Status DestroyStack(SqStack &S); {
}//DestroyStack
Status ClearStack(SqStack &S); {
S.top=S.base;
} //ClearStack
Status StackEmpty(SqStack S); {
if(S.top==S.base) return TRUE;
else return FALSE;
} //StackEmpty
int StackLength(SqStack S); {
int i; SElemType *p;
i=0;
p=S.top;
while(p!=S.base) {p++; i++; }
} //stackLength
Status GetTop(SqStack S,SElemType &e); {
if(S.top==S.base) return ERROR;
e=*(S.top-1);
return OK;
} //GetTop
Status Push(SqStack &S,SElemType e); {
if(S.top - s.base>=S.stacksize) {
S.base=(ElemType *) realloc(S.base,
(S.stacksize + STACKINCREMENT) * sizeof(ElemType));
if(!S.base)exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
} //Push
Status Pop(SqStack &S,SElemType &e); {
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}//Pop
Status StackTraverse(SqStack S,Status (*visit)()); {
}//StackTraverse
三、总结
栈的定义
栈的顺序存储实现
第十一课
本课主题： 栈的应用
教学目的： 掌握栈的应用方法,理解栈的重要作用
教学重点： 利用栈实现行编辑,利用栈实现表达式求值
教学难点： 利用栈实现表达式求值
授课内容：
将十进制数转换成其它进制的数有一种简单的方法：
例：十进制转换成八进制：(66)10=(102)8
66/8=8 余 2
8/8=1 余 0
1/8=0 余 1
结果为余数的逆序:102 。先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的先入后出性质，故可用栈来实现数制转换：
|
void conversion() { pSqStack S; SElemType e; int n; InitStack(&S); printf("Input a number to convert to OCT:\n"); scanf("%d",&n); if(n<0) { printf("\nThe number must be over 0."); return;} if(!n) Push(S,0); while(n){ Push(S,n%8); n=n/8; } printf("the result is: "); while(!StackEmpty(*S)){ Pop(S,&e); printf("%d",e);} } |
请看：数制转换的C源程序
一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。允许用户输入出错时可以及时更正。可以约定＃为退格符，以表示前一个字符无效，@为退行符，表示当前行所有字符均无效。
例：在终端上用户输入为
whli##ilr#e(s#*s) 应为
while(*s)
|
void LineEdit() { pSqStack S,T; char str[1000]; int strlen=0; char e; char ch; InitStack(&S); InitStack(&T); ch=getchar(); while(ch!=EOFILE) { while(ch!=EOFILE&&ch!='\n') { switch(ch){ case '#': Pop(S,&ch); break; case '@': ClearStack(S); break; default: Push(S,ch); break; } ch=getchar(); } if(ch=='\n') Push(S,ch); while(!StackEmpty(*S)) { Pop(S,&e); Push(T,e); } while(!StackEmpty(*T)) { Pop(T,&e); str[strlen++]=e; } if(ch!=EOFILE) ch=getchar(); } str[strlen]='\0'; printf("\n%s",str); DestroyStack(S); DestroyStack(T); } |
请看:行编辑的C源程序
一个程序设计语言应该允许设计者根据需要用表达式描述计算过程，编译器则应该能分析表达式并计算出结果。表达式的要素是运算符、操作数、界定符、算符优先级关系。例：1+2*3有+,*两个运算符，*的优先级高,1,2,3是操作数。 界定符有括号和表达式结束符等。
算法基本思想：
１首先置操作数栈为空栈，表达式起始符＃为运算符栈的栈底元素；
２依次讲稿表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。
|
char EvaluateExpression() { SqStack *OPND,*OPTR; char c,x,theta; char a,b; InitStack(&OPTR); Push(OPTR,'#'); InitStack(&OPND); c=getchar(); while(c!='#'||GetTop(*OPTR)!='#') { if(!In(c,OP)) {Push(OPND,c);c=getchar();} else switch(Precede(GetTop(*OPTR),c)) { case '<': Push(OPTR,c); c=getchar(); break; case '=': Pop(OPTR,&x); c=getchar(); break; case '>': Pop(OPTR,&theta); Pop(OPND,&b); Pop(OPND,&a); Push(OPND,Operate(a,theta,b)); break; } } c=GetTop(*OPND); DestroyStack(OPTR); DestroyStack(OPND); return c; } |
请看:表达式求值的C源程序
四、总结
栈的先进后出、后进先出的特性。
第十二课
本课主题： 实验二 循环链表实验
教学目的： 掌握单向链表的实现方法
教学重点： 单向链表的存储表示及操作
教学难点： 单向链表的操作实现
授课内容：
一、单向链表的存储表示
二、单向链表的基本操作
第十三课
本课主题： 队列
教学目的： 掌握队列的类型定义,掌握链队列的表示与实现方法
教学重点： 链队列的表示与实现
教学难点： 链队列的表示与实现
授课内容：
一、队列的定义:
队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。象日常生活中的排队，最早入队的最早离开。
在队列中，允许插入的的一端叫队尾，允许删除的一端则称为队头。
抽象数据类型队列:
ADT Queue{
数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
数据关系: R1={<ai-1,ai> | ai-1,ai(- D,i=2,...,n}
基本操作：
InitQueue(&Q) 构造一个空队列Q
Destroyqueue(&Q) 队列Q存在则销毁Q
ClearQueue(&Q) 队列Q存在则将Q清为空队列
QueueEmpty(Q) 队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE
QueueLenght(Q) 队列Q存在,返回Q的元素个数,即队列的长度
GetHead(Q,&e) Q为非空队列,用e返回Q的队头元素
EnQueue(&Q,e) 队列Q存在,插入元素e为Q的队尾元素
DeQueue(&Q,&e) Q为非空队列,删除Q的队头元素,并用e返回其值
QueueTraverse(Q,vivsit()) Q存在且非空,从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败
}ADT Queue
二、链队列－队列的链式表示和实现
用链表表示的队列简称为链队列。一个链队列显然需要两个分别指示队头和队尾的指针。
|
|
链队列表示和实现：
//存储表示
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
//操作说明
Status InitQueue(LinkQueue &Q)
//构造一个空队列Q
Status Destroyqueue(LinkQueue &Q)
//队列Q存在则销毁Q
Status ClearQueue(LinkQueue &Q)
//队列Q存在则将Q清为空队列
Status QueueEmpty(LinkQueue Q)
// 队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE
Status QueueLenght(LinkQueue Q)
// 队列Q存在,返回Q的元素个数,即队列的长度
Status GetHead(LinkQueue Q,QElemType &e)
//Q为非空队列,用e返回Q的队头元素
Status EnQueue(LinkQueue &Q,QElemType e)
//队列Q存在,插入元素e为Q的队尾元素
Status DeQueue(LinkQueue &Q,QElemType &e)
//Q为非空队列,删除Q的队头元素,并用e返回其值
Status QueueTraverse(LinkQueue Q,QElemType vivsit())
//Q存在且非空,从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败
//操作的实现
Status InitQueue(LinkQueue &Q) {
//构造一个空队列Q
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)exit(OVERFLOW);
Q.front->next=NULL;
return OK;}
Status Destroyqueue(LinkQueue &Q) {
//队列Q存在则销毁Q
while(Q.front){
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;}
Status EnQueue(LinkQueue &Q,QElemType e) {
//队列Q存在,插入元素e为Q的队尾元素
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;}
Status DeQueue(LinkQueue &Q,QElemType &e) {
//Q为非空队列,删除Q的队头元素,并用e返回其值
if(Q.front==Q.rear)return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)Q.rear=Q.front;
free(p);
return OK;}
三、总结
链队列的存储表示
链队列的操作及实现
第十四课
本课主题： 串的定义
教学目的： 掌握串的定义及作用
教学重点： 串的类型定义
教学难点： 串的类型定义
授课内容：
串（或字符串），是由零个或多个字符组成的有限序列。一般记为：
s='a1a2...an'(n>=0)
其中s是串的名，用单引号括起来的字符序列是串的值；串中字符的数目n称为串的长度。零个字符的串称为空串，它的长度为零。
串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常称字符在序列中的称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。
例：a='BEI',b='JING',c='BEIJING',d='BEI JING'
串长分别为3,4,7,8,且a,b都是c,d的子串。
称两个串是相等的，当且仅当这两个串的值相等。
二、串的抽象数据类型的定义：
ADT String{
数据对象：D={ai|ai(-CharacterSet,i=1,2,...,n,n>=0}
数据关系：R1={<ai-1,ai>|ai-1,ai(-D,i=2,...,n}
基本操作：
StrAssign(&T,chars)
chars是字符常量。生成一个其值等于chars的串T。
StrCopy(&T,S)
串S存在则由串S复制得串T
StrEmpty(S)
串S存在则若S为空串,返回真否则返回假
StrCompare(S,T)
串S和T存在,若S>T,则返回值大于0,若S=T,则返回值=0,若S<T,则返回值<0
StrLength(S)
串S存在返回S的元素个数称为串的长度.
ClearString(&S)
串S存在将S清为空串
Concat(&T,S1,S2)
串S1和S2存在用T返回由S1和S2联接而成的新串
SubString(&Sub,S,pos,len)
串S存在,1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1
Index(S,T,pos)
串S和T存在,T是非空,1<=pos<=StrLength(S),若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置,否则函数值为0
Replace(&S,T,V)
串S,T和V存在,T是非空串,用V替换主串S中出现的所有与T相等的不重叠的子串
StrInsert(&S,pos,T)
串S和T存在,1<=pos<=StrLength(S)+1,在串S的第pos个字符之前插入串T
StrDelete(&S,pos,len)
串S存在,1<=pos<=StrLength(S)-len+1从串中删除第pos个字符起长度为len的子串
DestroyString(&S)
串S存在,则串S被销毁
}ADT String
三、串操作应用举例:
1文字处理中常用的:串的查找(比较,定位)与替换
在TC集成环境中可用^QF快速查找变量 在WORD中可用搜索与替换批量改变文本
2串的截断与连接
可用求子串及串连接的方法进行文字处理
四、总结
找出几个自己亲自做过的串操作例子。
第十五课
本课主题： 串的表示和实现
教学目的： 掌握串的几种实现方法
教学重点： 定长顺序存储表示法 堆分配存储表示法
教学难点： 堆分配存储表示法
授课内容：
一、复习串的定义
二、定长顺序存储表示
类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列.
#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN+1] //0号单元存放串长
串的实际长度可在这予定义长度的范围内随意,超过予定义长度的串值则被舍去
串长可用下标为0的数组元素存储,也可在串值后设特殊标记
|
a[0] |
a[1] |
a[2] |
a[3] |
a[4] |
a[5] |
... |
a[n] |
|
3 |
a |
b |
c |
|
|
|
pascal |
|
a |
b |
c |
\0 |
|
|
|
c |
1串联接的实现Concat(&T,S1,S2)
假设S1,S2和T都是SString型的串变量,且串T是由串S1联结串S2得到的,即串T的值的前一段和串S1的值相等,串T的值的后一段和串S2的值相等,则只要进行相应的"串值复制"操作即可,对超长部分实施"截断"操作
以下是串联接可能出现的三种情况:
S1,S2串长和小于最大值 |
S1,S2串长和超过最大串长 |
S1串长已等于最大串长 |
算法描述如下:
Status Concat(SString &T,SString S1,SString S2){
if(S1[0]+S2[0]<=MAXSTRLEN){
T[1..S1[0]]=S1[1..S1[0]];
T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];
T[0]=S1[0]+S2[0]uncut=TRUE;
}
else if(S1[0]<MAXSTRSIZE){
T[1..S1[0]]=S1[1..S1[0]];
T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];
T[0]=MAXSTRLEN;uncut=FALSE;
}
else{
T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];
uncut=FALSE;
}
return uncut;
}
这种存储表示的特点是,仍以一组地址连续的存储单元存放串值字符序列,但它们的存储空间是在程序执行过程中动态分配而得
在C语言中,存在一个称之为堆的自由存储区,并由C语言的动态分配函数malloc()和free()来管理.利用函数malloc()为每个新产生的串分配一块实际串长所需存储空间,为处理方便,约定串长也作为存储结构的一部分
typedef struct{
char *ch;//若是非空串,则按串长分配存储区,否则ch为NULL
int length; //串长度
}HString
Status StrInsert(HString &S,int pos,HString T){
if(pox<1||pos>S.length+1) return ERROR;
if(T.length){
if(!(S.ch=(char *)realloc(S.ch,(S.length+T.length)*sizeof(char))))
exit(OVERFLOW);
for(i=S.length-1;i>=pos-1;--i)
S.ch[i+T.length]=S.ch[i];
S.ch[pos-1..pos+T.lenght-2]=T.ch[0..T.length-1];
S.length+=T.length;
}
return OK;
}
四、总结
思考两种存储表示方法的优缺点
第十六课
本课主题： 串操作应用举例
教学目的： 掌握文本编辑的基本原理及方法
教学重点： 简单文本编辑
教学难点： 串的存储管理
授课内容：
一、复习串的堆分配存储表示
二、文本编辑基本原理
|
图一 |
文本编辑可以用于源程序的输入和修改（如图一）,也可用于报刊和书籍的编辑排版以及办公室的公文书信的起草和润色（如图二）。
|
图二 |
可用于文本编辑的程序很多，功能强弱差别很大，但基本操作是一致的：都包括串的查找，插入和删除等基本操作。
对用户来讲，一个文本（文件）可以包括若干页，每页包括若干行，每行包括若干文字。
对文本编辑程序来讲，可把整个文本看成一个长字符串，称文本串，页是文本串的子串，行又是页的子串。为简化程序复杂程度，可简单地把文本分成若干行。
例：下面的一段源程序可以看成一个文本串，
|
main(){ float a,b,max; scanf("%f,%f",&a,&b); if (a>b) max=a; else max=b; }; |
这个文本串在内存中的存储映像可为：
|
m |
a |
i |
n |
( |
) |
{ |
\n |
|
|
f |
l |
o |
a |
t |
|
a |
, |
b |
, |
|
m |
a |
x |
; |
\n |
|
|
s |
c |
a |
n |
f |
( |
" |
% |
f |
, |
% |
f |
" |
|
, |
& |
a |
, |
& |
b |
) |
; |
\n |
|
|
i |
f |
|
a |
> |
b |
|
|
m |
|
a |
x |
= |
a |
; |
\n |
|
|
e |
l |
s |
e |
|
|
m |
a |
x |
= |
b |
; |
|
\n |
} |
\n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
在编辑时，为指示当前编辑位置，程序中要设立页指针、行指针、字符指针，分别指示当前页，当前行，当前字符。因此程序中要设立页表、行表便于查找。
三、简单行编辑程序例
第十七课
本课主题： 实验三：栈的表示与实现及栈的应用
教学目的： 掌握栈的存储表示方式和栈基本操作的实现方法
教学重点： 栈的基本操作实现方法，栈的应用
教学难点： 栈的存储表示
实验内容：
一、栈的实现
实现栈的顺序存储。
二、栈的应用
１、利用栈实现数制转换 ２、利用栈实现单行编辑
以上任选一题。
这里是实现栈的头文件
第十八课
本课主题： 数组的顺序表示与实现
教学目的： 掌握数组的定义,数组的顺序表示方法
教学重点： 数组的定义,数组的顺序表示方法
教学难点： 数组的顺序表示方法
授课内容：
一、数组的定义
几乎所有的程序设计语言都把数组类型设定为固有类型。
以抽象数据类型的形式讨论数组的定义和实现，可以让我们加深对数组类型的理解。
数组的定义：
ADT Array{
数据对象:ji=0,...,bi-1,i=1,2,...,n;
D={aj1j2...jn|n(>0)称为数组的维数,bi是数组第i维的长度,ji是数组元素的第i维下标,aj1j2...jn (-ElemSet}
数据关系:R={R1,R2,...Rn|
Ri={<aj1...ji...jn,aj1...ji+1 ...jn>|
0<=jk<=bk-1,1<=k<=n且k<>i,
0<=ji<=bi-2,aj1...ji...jn,
aj1...ji+1 ...jn(-D,i=2,...n}
基本操作:
InitArray(&A,n,bound1,...,boundn)
若维数和各维长度合法,则构造相应的数组A,并返回OK.
DestroyArray(&A)
操作结果:销毁数组A.
Value(A,&e,index1,...,indexn)
初始条件:A是n维数组,e为元素变量,随后是n个下标值.
操作结果:若各下标不超界,则e赋值为所指定的A的元素值,并返回OK.
Assign(&A,e,index1,...,indexn)
初始条件:A是n维数组,e为元素变量,随后是n个下标值.
操作结果:若下标不超界,则将e的值赋给 所指定的A的元素,并返回OK.
}ADT Array
列向量的一维数组: