迪丽热巴像日本艺人:数据结构教程7

第十七课

本课主题： 实验三：栈的表示与实现及栈的应用

教学目的： 掌握栈的存储表示方式和栈基本操作的实现方法

教学重点： 栈的基本操作实现方法，栈的应用

教学难点： 栈的存储表示

实验内容：

一、栈的实现

实现栈的顺序存储。

栈实现示例

二、栈的应用

１、利用栈实现数制转换 ２、利用栈实现单行编辑

以上任选一题。

数制转换示例

单行编辑示例

这里是实现栈的头文件

回目录 上一课 下一课

第十八课

本课主题： 数组的顺序表示与实现

教学目的： 掌握数组的定义,数组的顺序表示方法

教学重点： 数组的定义,数组的顺序表示方法

教学难点： 数组的顺序表示方法

授课内容：

一、数组的定义

几乎所有的程序设计语言都把数组类型设定为固有类型。

以抽象数据类型的形式讨论数组的定义和实现，可以让我们加深对数组类型的理解。

数组的定义：

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={|

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

列向量的一维数组:

a00

a01

a02

...

a0,n-1

a10

a11

a12

...

a1,n-1

...

...

...

...

...

am-1,0

am-1,1

am-1,2

...

am-1,n-1

行向量的一维数组:

把二维数组中的每一行看成是一个数据元素,这些数据元素组成了一个一维数组A.

A0

a00

a01

a02

...

a0,n-1

a10

a11

a12

...

a1,n-1

...

...

...

...

...

am-1,0

am-1,1

am-1,2

...

am-1,n-1

A1

...

Am

二、数组的顺序表示和实现

以行序为主序的存储方式:

a00

a01

a02

...

a0,n-1

a10

a11

a12

...

a1,n-1

...

am-1,0

am-1,1

am-1,2

...

am-1,n-1

数组的顺序存储表示和实现:

#include

#define MAX_ARRAY_DIM 8

typedef struct {

ElemType *base;

int dim;

int *bounds;

int *constants;

}Array;

Status InitArray(Array &A,int dim,...);

Status DestroyArray(Array &A);

Status Value(Array A,ElemType &e,...);

Status Assign(Array &A,ElemType e,...);

基本操作的算法描述:

Status InitArray(Array &A,int dim,...){

if(dim<1||dim>MAX_ARRAY_DIM) return ERROR;

A.dim=dim;

A.bounds=(int *)malloc(dim *sizeof(int));

if(!A.bounds) exit(OVERFLOW);

elemtotal=1;

va_start(ap,dim);

for(i=1;i

A.bounds[i]=va_arg(ap,int);

if(A.bounds[i]<0) return UNDERFLOW;

elemtotal*=A.bounds[i];

}

va_end(ap);

A.base=(ElemType *)malloc(elemtotal*sizeof(ElemType));

if(!A.base) exit(OVERFLOW);

A.constants=(int *)malloc(dim*sizeof(int));

if(!A.constants) exit(OVERFLOW);

A.constants[dim-1]=1;

for(i=dim-2;i>=0;--i)

A.constants[i]=A.bounds[i+1]*A.constants[i+1];

return OK;

}

Status DestoyArray(Array &A){

if(!A.base) return ERROR;

free(A.base); A.base=NULL;

if !(A.bounds) return ERROR;

free(A.bounds); A.bounds=NULL;

if!(A.constatns) return ERROR;

free(A.constants); A.constants=NULL;

return OK;

}

Status Locate(Array A,va_list ap,int &off){

off=0;

for(i=0;i

ind=va_arg(ap,int);

if(ind<0||ind>=A.bounds[i]) return OVERFLOW;

off+=A.constants[i]*ind;

}

return OK;

}

Status Value(Array A,ElemType &e,...){

va_start(ap,e);

if((result=Locate(A,ap,off))<=0 return result;

e=*(A.base+off);

return OK;

}

Status Assign(Array &A,ElemType e,...){

va_start(ap,e);

if((result=Locate(A,ap,off))<=0) return result;

*(A.base+off)=e;

return OK;

}

三、小结

数组的存储方式。

数组的基本操作种类。

回目录 上一课 下一课

第十九课

本课主题： 实验四 串的实现实验

教学目的： 掌握PASCAL串类型的实现方法

教学重点： 串的操作

教学难点： 串的联接操作

授课内容：

一、PASCAL串类型的存储表示:

#define MAXSTRLEN 255

typedef char SString[MAXSTRLEN+1];

二、串的操作：

１、串的联接

mystrcat(SString s1,SString s2,SString t);

２、求子串

mysubstr(SString t,int pos,int len,SString sub);

３、子串定位

mystrindex(SString t,SString sub,int *index);

回目录 上一课 下一课

第二十课

本课主题： 广义表

教学目的： 广义表的定义及存储结构

教学重点： 广义表的操作及意义

教学难点： 广义表存储结构

授课内容：

一、广义表的定义

广义表是线性表的推广，其表中的元素可以是另一个广义表,或其自身.

广义表的定义:

ADT GList{

数据对象:D={i=1,2,...,n>=0;ei(-AtomSet或ei(-GList,

AtomSet为某个数据对象}

数据关系:R1={|ei-1,ei(-D,2=

基本操作:

InitGlist(&L);

操作结果:创建空的广义表L

CreateGList(&L,S);

初始条件:S是广义表的书写形式串

操作结果:由S创建广义表L

DestroyGlist(&L);

初始条件:广义表L存在

操作结果:销毁广义表L

CopyGlist(&T,L);

初始条件:广义表L存在

操作结果:由广义表L复制得到广义表T

GListLength(L);

初始条件:广义表L存在

操作结果:求广义表L的长度,即元素个数

GListDepth(L);

初始条件:广义表L存在

操作结果:求广义表L的深度

GlistEmpty(L);

初始条件:广义表L存在

操作结果:判断广义表L是否为空

GetHead(L);

初始条件:广义表L存在

操作结果:取广义表L的头

GetTail(L);

初始条件:广义表L存在

操作结果:取广义表L的尾

InsertFirst_GL(&L,e);

初始条件:广义表L存在

操作结果:插入元素e作为广义表L的第一元素

DeleteFirst_GL(&L,&e);

初始条件:广义表L存在

操作结果:删除广义表L的第一元素,并用e返回其值

Traverse_GL(L,Visit());

初始条件:广义表L存在

操作结果:遍历广义表L,用函数Visit处理每个元素

}ADT GList

广义表一般记作:LS=(a1,a2,...,an)

其中LS是广义表的名称,n是它的长度,ai可以是单个元素也可是广义表,分别称为原子和子表,当广义表非空时,称第一个元素a1为LS的表头称其余元素组成的广义表为表尾.

二、广义表的存储结构

广义表的头尾链表存储表示

typedef emnu{ATOM,LIST} ElemTag;

typedef struct GLNode{

ElemTag tag;

union{

AtomType atom;

struct{struct GLNode *hp,*tp;}ptr;

}

}

有A、B、C、D、E五个广义表的描述如下：

A=() A是一个空表,它的长度为零

B=(e) 列表B只有一个原子e,B的长度为1.

C=(a,(b,c,d)) 列表C的长度为2,两个元素分别为原子a和子表(b,c,d)

D=(A,B,C) 列表D的长度为3,三个元素都是列表,显然,将子表的值代入后,则有D=((),(e),(a,(b,c,d)))

E=(a,E) 这是一个递归的表,它的长度为2,E相当于一个无限的列表E=(a,(a,(a,...)))

上述五个广义表用以上的存储结构的存储映像如下: