数据结构

Contents

3.5 数据结构 (Data Structures)

一个数据结构是组合到同一定义下的一组不同类型的数据,各个数据类型的长度可能不同。它的形式是:struct model_name {
type1 element1;
type2 element2;
type3 element3;
.
.
} object_name;

这里model_name 是一个这个结构类型的模块名称。object_name 为可选参数,是一个或多个具体结构对象的标识。在花括号{ }内是组成这一结构的各个元素的类型和子标识。

如果结构的定义包括参数model_name (可选),该参数即成为一个与该结构等价的有效的类型名称。例如:struct products {
char name [30];
float price;
};
products apple;
products orange, melon;

我们首先定义了结构模块products,它包含两个域:name 和 price,每一个域是不同的数据类型。然后我们用这个结构类型的名称 (products) 来声明了 3个该类型的对象:apple, orange 和melon。

一旦被定义,products就成为一个新的有效数据类型名称,可以像其他基本数据类型,如int, char或 short 一样,被用来声明该数据类型的对象(object)变量。

在结构定义的结尾可以加可选项object_name ,它的作用是直接声明该结构类型的对象。例如,我们也可以这样声明结构对象apple, orange和melon:struct products {
char name [30];
float price;
}apple, orange, melon;

并且,像上面的例子中如果我们在定义结构的同时声明结构的对象,参数model_name (这个例子中的products)将变为可选项。但是如果没有model_name,我们将不能在后面的程序中用它来声明更多此类结构的对象。

清楚地区分结构模型model和它的对象的概念是很重要的。参考我们对变量所使用的术语,模型model 是一个类型type,而对象object 是变量variable。我们可以从同一个模型model (type)实例化出很多对象objects (variables)。

在我们声明了确定结构模型的3个对象(apple, orange 和 melon)之后,我们就可以对它们的各个域(field)进行操作,这通过在对象名和域名之间插入符号点(.)来实现。例如,我们可以像使用一般的标准变量一样对下面的元素进行操作:apple.name
apple.price
orange.name
orange.price
melon.name
melon.price

它们每一个都有对应的数据类型:apple.name, orange.name 和melon.name 是字符数组类型char[30],而apple.price, orange.price 和 melon.price 是浮点型float。

下面我们看另一个关于电影的例子:

// example about structures
#include ‹iostream.h›
#include ‹string.h›
#include ‹stdlib.h›

struct movies_t {
char title [50];
int year;
}mine, yours;

void printmovie (movies_t movie);

int main () {
char buffer [50];
strcpy (mine.title, “2001 A Space Odyssey”);
mine.year = 1968;
cout << “Enter title: “;
cin.getline (yours.title,50);
cout << “Enter year: “;
cin.getline (buffer,50);
yours.year = atoi (buffer);
cout << “My favourite movie is:\n “;
printmovie (mine);
cout << “And yours:\n”;
printmovie (yours);
return 0;
}

void printmovie (movies_t movie) {
cout << movie.title;
cout << ” (” << movie.year << “)\n”;
}
Enter title: Alien
Enter year: 1979
My favourite movie is:
2001 A Space Odyssey (1968)
And yours:
Alien (1979)

这个例子中我们可以看到如何像使用普通变量一样使用一个结构的元素及其本身。例如,yours.year 是一个整型数据int,而 mine.title 是一个长度为50的字符数组。

注意这里 mine 和 yours 也是变量,他们是movies_t 类型的变量,被传递给函数printmovie()。因此,结构的重要优点之一就是我们既可以单独引用它的元素,也可以引用整个结构数据块。

结构经常被用来建立数据库,特别是当我们考虑结构数组的时候。

// array of structures
#include ‹iostream.h›
#include ‹stdlib.h›

#define N_MOVIES 5

struct movies_t {
char title [50];
int year;
} films [N_MOVIES];

void printmovie (movies_t movie);

int main () {
char buffer [50];
int n;
for (n=0; n<N_MOVIES; n++) {
cout << “Enter title: “;
cin.getline (films[n].title,50);
cout << “Enter year: “;
cin.getline (buffer,50);
films[n].year = atoi (buffer);
}

cout << “\nYou have entered these movies:\n”;
for (n=0; n<N_MOVIES; n++) {
printmovie (films[n]);
return 0;
}

void printmovie (movies_t movie) {
cout << movie.title;
cout << ” (” << movie.year << “)\n”;
}
Enter title: Alien
Enter year: 1979
Enter title: Blade Runner
Enter year: 1982
Enter title: Matrix
Enter year: 1999
Enter title: Rear Window
Enter year: 1954
Enter title: Taxi Driver
Enter year: 1975

You have entered these movies:
Alien (1979)
Blade Runner (1982)
Matrix (1999)
Rear Window (1954)
Taxi Driver (1975)

结构指针(Pointers to structures)

就像其它数据类型一样,结构也可以有指针。其规则同其它基本数据类型一样:指针必须被声明为一个指向结构的指针:struct movies_t {
char title [50];
int year;
};
movies_t amovie;
movies_t * pmovie;

这里 amovie 是一个结构类型movies_t 的对象,而pmovie 是一个指向结构类型movies_t 的对象的指针。所以,同基本数据类型一样,以下表达式正确的:pmovie = &amovie;

下面让我们看另一个例子,它将引入一种新的操作符:

// pointers to structures
#include ‹iostream.h›
#include ‹stdlib.h›

struct movies_t {
char title [50];
int year;
};

int main () {
char buffer[50];

movies_t amovie;
movies_t * pmovie;
pmovie = & amovie;

cout << “Enter title: “;
cin.getline (pmovie->title,50);
cout << “Enter year: “;

cin.getline (buffer,50);
pmovie->year = atoi (buffer);

cout << “\nYou have entered:\n”;
cout << pmovie->title;
cout << ” (” << pmovie->year << “)\n”;

return 0;
}
Enter title: Matrix
Enter year: 1999

You have entered:
Matrix (1999)

上面的代码中引入了一个重要的操作符:->。这是一个引用操作符,常与结构或类的指针一起使用,以便引用其中的成员元素,这样就避免使用很多括号。例如,我们用:pmovie->title

来代替:(*pmovie).title

以上两种表达式pmovie->title 和 (*pmovie).title 都是合法的,都表示取指针pmovie 所指向的结构其元素title 的值。我们要清楚将它和以下表达区分开:*pmovie.title

它相当于*(pmovie.title)

表示取结构pmovie 的元素title 作为指针所指向的值,这个表达式在本例中没有意义,因为title本身不是指针类型。

下表中总结了指针和结构组成的各种可能的组合:

表达式描述等价于
pmovie.title结构pmovie 的元素title
pmovie->title指针pmovie 所指向的结构其元素title 的值(*pmovie).title
*pmovie.title结构pmovie 的元素title 作为指针所指向的值*(pmovie.title)

结构嵌套(Nesting structures)

结构可以嵌套使用,即一个结构的元素本身又可以是另一个结构类型。例如:struct movies_t {
char title [50];
int year;
}

struct friends_t {
char name [50];
char email [50];
movies_t favourite_movie;
} charlie, maria;

friends_t * pfriends = &charlie;

因此,在有以上声明之后,我们可以使用下面的表达式:charlie.name
maria.favourite_movie.title
charlie.favourite_movie.year
pfriends->favourite_movie.year

(以上最后两个表达式等价)

本节中所讨论的结构的概念与C语言中结构概念是一样的。然而,在C++中,结构的概念已经被扩展到与类(class)相同的程度,只是它所有的元素都是公开的(public)。在后面的章节4.1“类”中, 我们将进一步深入讨论这个问题。