学数据结构(一)绪论(2)(抽象数据类型、参数传递和函数结果带出方式)-爱代码爱编程
目录
一 抽象数据类型
1.抽象数据类型与问题求解方法
抽象数据类型(简称ADT)是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。
一个抽象数据类型确定了一个模型,但将模型的实现细节隐藏起来;它定义了一组运算,但将运算的实现过程隐藏起来。
用抽象数据类型的概念来指导问题的求解过程:
2.数据的抽象
汇编语言中十进制表示的数据98.65、9.6E3等, 它们是二进制数据的抽象;
高级语言中,给出更高一级的数据抽象,如整型、实型、字符型等, 还可以进一步定义更高级的数据抽象,如各种表、队、栈、树、图、窗口、管理器等复杂的抽象数据类型。
3.抽象数据类型
ADT Linear_list
数据元素 所有ai属于同一数据对象,i=1,2,……,n n≥0;
逻辑结构 所有数据元素ai(i=1,2,…,n-1)存在次序关系
<ai, ai+1>,ai无前趋,an无后继;
操作 设L为Linear_list
Initial(L)初始化空线性表;
Length(L)求线性表的表长;
Get(L,i)取线性表的第i个元素;
Insert(L,i,b)在线性表的第i个位置插入元素b;
Delete(L,i)删除线性表的第i个元素;
4.抽象数据类型实现
实现的三种方法:
传统的面向过程的程序设计
“包”、“模型”的设计方法
面向对象的程序设计(Object Oriented Programming,简称OOP)
5.ADT的表示与实现
ADT的定义:
ADT <ADT名>
{ 数据对象:<数据对象的定义>
关系:<结构关系的定义>
基本操作:<基本操作的定义>
}ADT <ADT名>
基本操作的定义格式为:
<操作名称> (参数表)
操作前提:<操作前提描述>
操作结果:<操作结果描述>
关于参数传递:
参数表中的参数有值参和变参两种。
用标准C语言表示和实现ADT描述时,主要有两个方面:
一、通过结构体将int、float等固有类型组合到一起,构成一个结构类型,再用typedef为该类型或该类型指针重新起一个名字。
二、用C语言函数实现各操作。
6.算法描述规范与设计风格
(1)算法表示格式与函数模块化
算法表示格式:
[函数返回值类型] 函数名([形式参数及说明])
{ 内部数据说明;
执行语句组;
} /*函数名*/
函数模块化
[包含文件语句]
[宏定义语句]
[自定义类型语句]
[所有子函数的原型说明]
[子函数1定义]
.
.
.
[子函数n定义]
[主函数定义]
(2) 算法描述要点
>加上必要的注释:注释形式可以用/*字符串*/
>避免函数返回值隐含说明
>预定义常量和类型
# define TRUE 1
# define FALSE 0
# define MAXSIZE 100
# define OK 1
# define ERROR 0
return <表达式>或return:用于函数结束。
break语句:可用在循环语句或switch语句中结束循环过程或跳出情况语句。
continue语句:可用在循环语句中结束本次循环过程,进入下一次循环过程。
exit语句:表示出现异常情况时,控制退出函数。
二 参数传递
7. 与参数传递的相关技术
变量的作用域
全局变量:程序中所有函数都可以访问的量
局部变量:只能在该函数中访问的量。
参数传递方式
参数传递是函数之间进行信息通讯的重要渠道。其参数传递的主要方式有传值和传地址两类。函数参数表中的参数有两种:第一种参数只为操作提供待处理数据,又称值参;第二种参数既能为操作提供待处理数据,又能返回操作结果,也称变量参数
8关于参数传递示例源程序:
#include <stdio.h>
viod swap1(int a,int b)
{ int c;
c=a; a=b; b=c;
printf(“swap1中的a= %d,b=%d”,a,b);
}
viod swap2(int *a,int *b)
{ int c;
c=*a, *a=*b, *b=c;
}
void main()
{ int x=100,y=800;
swap1(x,y); /*调用函数swap1()*/
printf(“\n调用swap1后x= %d,y=%d”,x,y); /*输出调用swap1后的数据*/
x=100;y=800;
swap2(&x,&y); /*调用函数swap2()*/
printf(“\n调用swap2后x=%d,y=%d”,x,y); /*输出调用swap2后的数据*/
}
三 函数结果带出方式
9.函数结果的带出方式
三种带出方式:全程量、函数返回值、传址参数
通过参数表的参数传递是一种参数显式传递方式,而通过全局变量是一种隐式参数传递,一个函数中对全局变量的改变会影响其它程序的调用,使用全局变量必须注意这个问题。
若函数结果需要带出多个值,该怎样实现?
可以采用①全局变量方式带出,②通过地址传递带出(数组方式、结构体方式、指针方式)两类方式之一来实现。
一个全局变量方式带出的例子
int MIN; /* 全局变量 */
int fun1(int a[], int n)
/*通过函数return返回最大值,通过全局变量MIN带回最小值*/
{ int i,max;
max=MIN=a[0]; //给最大值最小值赋初值
for (i=0;i<n;i++)
{
if(a[i]>max) max=a[i];
if (a[i]<MIN) MIN=a[i];
}
return(max);
}
一个全局变量方式带出的例子
int *fun2(int a[],int n)
/*将最大、最小值放到数组b中,通过return返回*/
{ static int b[2];
b[0]=b[1]=a[0]; //给最大值最小值赋初值
int i;
for (i=1;i<n;i++)
{
if (a[i]>b[0])
b[0]=a[i];
if (a[i]<b[1])
b[1]=a[i];
}
return(b);
}
结构体方式带出的例子:
Data *fun3(int a[],int n)
/*将最大、最小值放到结构体指针p中,通过return返回*/
{ Data *p;
int i;
p=(Data *)malloc(sizeof(Data *)); //指针初始化
p->max=p->min=a[0]; //给最大值最小值赋初值
for(i=1;i<n;i++)
{
if (a[i]>p->max)
p->max=a[i];
if (a[i]<p->min)
p->min=a[i];
}
return(p);
}
指针方式带出的例子
Data fun4(int a[],int n)
/*将最大、最小值放到结构体p中,通过结构体p带回返回值*/
{ Data p;
int i;
p.max=p.min=a[0]; //给最大值最小值赋初值
for(i=1;i<n;i++)
{
if (a[i]>p.max)
p.max=a[i];
if (a[i]<p.min)
p.min=a[i];
}
return(p);
}