C 语言程序设计:栈抽象数据类型

目录汇总:C 语言零基础入门教程

为了说明抽象数据类型怎样利用不完整类型进行封装,需要开发一个基于 C 语言程序设计:信息隐藏 中描述的栈模块的栈抽象数据类型(Abstract Data Type, ADT)。这一过程中将用三种不同的方法来实现栈。

一、为栈抽象数据类型定义接口

首先,需要一个定义栈抽象数据类型的头文件,并给出代表栈操作的函数原型。现在将该头文件命名为 stackADT.h。Stack 类型将作为指针指向 stack_type 结构,该结构存储栈的实际内容。这个结构是一个不完整类型,在实现栈的文件中信息将变得完整。该结构的成员依赖于栈的实现方法。下面是 stackADT.h 文件的内容:

stackADT.h (version 1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#ifndef STACKADT_H
#define STACKADT_H

#include <stdbool.h>     /* since C99 */

typedef struct stack_type *Stack;

Stack create(void);
void destroy(Stack s);
void make_empty(Stack s);
bool is_empty(Stack s);
bool is_full(Stack s);
void push(Stack s, int i);
int pop(Stack s);

#endif

包含头文件 stackADT.h 的客户可以声明 Stack 类型的变量,这些变量都可以指向 stack_type 结构。之后客户就可以调用在 stackADT.h 中声明的函数来对栈变量进行操作。但是客户不能访问 stack_type 结构的成员,因为该结构的定义在另一个文件中。

需要注意的是,每一个函数都有一个 Stack 参数或返回一个 Stack 值。C 语言程序设计:抽象数据类型 中的栈函数都具有 Stack * 类型的参数。导致这种差异的原因是,Stack 变量现在是指针,指向存放着栈内容的 stack_type 结构。如果函数需要修改栈,则改变的是结构本身,而不是指向结构的指针。

同样需要注意函数 createdestroy。模块通常不需要这些函数,但抽象数据类型需要。create 会自动给栈分配内存(包括 stack_type 结构需要的内存),同时把栈初始化为“空”状态。destroy 将释放栈的动态分配内存。

下面的客户文件可以用于测试栈抽象数据类型。它创建了两个栈,并对它们执行各种操作:

stackclient.c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
#include "stackADT.h"

int main(void)
{
  Stack s1, s2;
  int n;

  s1 = create();
  s2 = create();

  push(s1, 1);
  push(s1, 2);

  n = pop(s1);
  printf("Popped %d from s1\n", n);
  push(s2, n);
  n = pop(s1);
  printf("Popped %d from s1\n",n);
  push(s2, n);

  destroy(s1);

  while (!is_empty(s2))
    printf("Popped %d from s2\n", pop(s2));

  push(s2, 3);
  make_empty(s2);
  if (is_empty(s2))
    printf("s2 is empty\n");
  else
    printf("s2 is not empty\n");

  destroy(s2);

  return 0;
}

如果栈抽象数据类型的实现是正确的,程序将产生如下输出:

1
2
3
4
5
Popped 2 from s1
Popped 1 from s1
Popped 1 from s2
Popped 2 from s2
s2 is empty

二、用定长数组实现栈抽象数据类型

实现栈抽象数据类型有多种方法,这里介绍的第一种方法是最简单的。stackADT.c 文件中定义了结构 stack_type,该结构包含一个定长数组(记录栈中的内容)和一个整数(记录栈顶):

1
2
3
4
struct stack_type {
  int contents[STACK_SIZE];
  int top;
};

stackADT.c 程序如下所示:

stackADT.c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdio.h>
#include <stdlib.h>
#include "stackADT.h"

#define STACK_SIZE 100

struct stack_type {
  int contents[STACK_SIZE];
  int top;
};

static void terminate (const char *message)
{
  printf("%s\n", message);
  exit(EXIT_FAILURE);
}

Stack create(void)
{
  Stack s = malloc(sizeof(struct stack_type));
  if (s == NULL)
    terminate("Error in create: stack could not be created.");
  s->top = 0;
  return s;
}

void destroy(Stack s)
{
  free(s);
}

void make_empty(Stack s)
{
  s->top = 0;
}

bool is_empty(Stack s)
{
  return s->top == 0;
}

bool is_full(Stack s)
{
  return s->top == STACK_SIZE;
}

void push(Stack s, int i)
{
  if (is_full(s))
    terminate("Error in push: stack is full.");
  s->contents[s->top++] = i;
}

int pop(Stack s)
{
  if (is_empty(s))
    terminate("Error in pop: stack is empty.");
  return s->contents[--s->top];
}

这个文件中的函数最显眼的地方是,它们用 -> 运算符而不是 . 运算符来访问 stack_type 结构的 contentstop 成员。参数 s 是指向 stack_type 结构的指针,而不是结构本身,所以使用 . 运算符是非法的。

三、改变栈抽象数据类型中数据项的类型

现在我们已经有了栈抽象数据类型的一个版本,下面对其进行改进。首先,注意到栈里的项都是整数,太具有局限性了。事实上,栈中的数据项类型是无关紧要的,可以是其他基本类型(floatdoublelong 等),也可以是结构、联合或指针。

为了使栈抽象数据类型更易于针对不同的数据项类型进行修改,我们在 stackADT.h 中增加了一行类型定义。现在用类型名 Item 表示待存储到栈中的数据的类型。

stackADT.h(version 2)

#ifndef STACKADT_H
#define STACKADT_H

#include <stdbool.h>    /* since C99 */

typedef int Item;

typedef struct stack_type *Stack;

Stack create(void);
void destroy(Stack s);
void make_empty(Stack s);
bool is_empty(Stack s);
bool is_full(Stack s);
void push(Stack s, Item i);
Item pop (Stack s);

#endif

文件中改动的部分用粗体标注。除新增了 Item 类型外,pushpop 函数也做了修改。push 现在具有一个 Item 类型的参数,而 pop 则返回 Item 类型的值。从现在起我们将使用这一版本的 stackADT.h 来代替先前的版本。

为了跟 stackADT.h 匹配,stackADT.c 文件也需要做相应的修改,但改动很小。stack_type 结构将包含一个数组,数组的元素是 Item 类型而不是 int 类型:

struct stack_type {
  Item contents[STACK_SIZE];
  int top;
};

pushpop 的函数体部分没有改变,相应的改变仅仅是把 push 的第二个参数和 pop 的返回值改成了 Item 类型。

stackclient.c 文件可以用于测试新的 stackADT.h 和 stackADT.c,以验证 Stack 类型仍然可以很好地工作。(确实如此!)现在就可以通过修改 stackADT.h 中 Item 类型的定义来任意修改数据项类型了。(尽管我们不需要改变 stackADT.c 文件,但仍然需要对它进行重新编译。)

四、用动态数组实现栈抽象数据类型

栈抽象数据类型的另一个问题是,每一个栈的大小的最大值是固定的(目前设置为 100)。当然,这一上限值可以根据我们的意愿任意增加,但使用 Stack 类型创建的所有栈都会有同样的上限值。这样我们就不能拥有容量不同的栈了,也不能在程序运行的过程中设置栈的大小。

有两种方法可以解决这个问题。一种方法是把栈作为链表来实现,这样就没有固定的大小限制了。稍后我们将讨论这种方法,下面先来看看另一种方法——将栈中的数据项存放在动态分配的数组(C 语言动态分配数组)中。

这种方法的关键在于修改 stack_type 结构,使 contents 成员为指向数据项所在数组的指针,而不是数组本身:

struct stack_type {
  Item *contents;
  int top;
  int size;
};

我们还增加了一个新成员 size 来存储栈的最大容量(contents 指向的数组长度)。下面将使用这个成员检查“栈满”的情况。

create 函数有一个参数指定所需栈的最大容量:

Stack create(int size);

调用 create 函数时,它会创建一个 stack_type 结构和一个长度为 size 的数组。结构的 contents 成员将指向这个数组。

除了在 create 函数中新增 size 参数外,文件 stackADT.h 和之前的一致。(重新命名为 stackADT2.h。)但文件 stackADT.c 需要进行较多的修改,改动部分用粗体表示:

stackADT2.c

#include <stdio.h>
#include <stdlib.h>
#include "stackADT2.h"

struct stack_type {
  Item *contents;
  int top;
  int size;
};

static void terminate (const char *message)
{
  printf("%s\n", message);
  exit(EXIT_FAILURE);
}

Stack create(int size)
{
  Stack s = malloc(sizeof(struct stack_type));
  if (s == NULL)
    terminate("Error in create: stack could not be created.");
  s->contents = malloc(size * sizeof(Item));
  if (s->contents == NULL) {
    free(s);
    terminate("Error in create: stack could not be created.");
  }
  s->top = 0;
  s->size = size; 
  return s;
}

void destroy(Stack s)
{
  free(s->contents);
  free(s);
}

void make_empty(Stack s)
{
  s->top = 0;
}

bool is_empty(Stack s)
{
  return s->top == 0;
}

bool is_full (Stack s)
{
  return s->top == s->size;
}

void push(Stack s, Item i)
{
  if (is_full(s))
    terminate("Error in push: stack is full.");
  s->contents[s->top++] = i;
}

Item pop(Stack s)
{
  if (is_empty(s))
    terminate("Error in pop: stack is empty.");
  return s->contents[--s->top];
}

现在 create 函数调用 malloc 两次:一次是为 stack_type 结构分配空间,另一次是为包含栈数据项的数组分配空间。任意一处 malloc 失败都会导致调用 terminate 函数。destroy 函数必须调用 free 函数两次来释放由 create 分配的内存。

stackclient.c 文件可以再次用于测试栈抽象数据类型。但 create 函数的调用需要有所改变,因为现在的 create 函数需要参数。例如,可以将语句

1
2
s1 = create();
s2 = create();

改为

s1 = create(100);
s2 = create(200);

五、用链表实现栈抽象数据类型

使用动态分配数组实现栈抽象数据类型比使用定长数组更灵活,但客户在创建栈时仍然需要指定其最大容量。如果使用链表来实现栈,就不需要预先设定栈的大小了。

下面的实现与 C 语言程序设计:信息隐藏 中的 stack2.c 文件相似。链表中的结点用如下结构表示:

1
2
3
4
struct node {
  Item data;
  struct node *next;
};

data 成员的类型现在是 Item 而不是 int,但除此之外结构和之前是一样的。

stack_type 结构包含一个指向链表首结点的指针:

1
2
3
struct stack_type {
  struct node *top;
};

乍一看,这个结构似乎有点冗余:我们可以简单地把 Stack 定义为 struct node*,同时让 Stack 的值为指向链表首结点的指针。但是,我们仍然需要这个 stack_type 结构,这样可以使栈的接口保持不变。(如果不这样做,任何一个对栈进行修改的函数都需要 Stack * 类型的参数而不是 Stack 参数。)此外,如果将来想存储更多的信息,stack_type 结构的存在可以简化对实现的修改。例如,如果以后想给 stack_type 结构增加栈数据项的计数器,可以很容易地为 stack_type 结构增加一个成员来存储该信息。

我们不需要对 stackADT.h 做任何修改。(我们使用这个头文件,不用 stackADT2.h。)测试的时候仍然可以使用 stackclient.c 文件,但需要做一些改动,下面是新版本:

stackADT3.c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <stdio.h>
#include <stdlib.h>
#include "stackADT.h"

struct node {
  Item data;
  struct node *next;
};

struct stack_type {
  struct node *top;
};

static void terminate(const char *message)
{
  printf("%s\n", message);
  exit(EXIT_FAILURE);
}

Stack create(void)
{
  Stack s = malloc(sizeof(struct stack_type));
  if (s == NULL)
    terminate("Error in create: stack could not be created.");
  s->top = NULL;
  return s;
}

void destroy(Stack s)
{
  make_empty(s);
  free(s);
}

void make_empty(Stack s)
{
  while (!is_empty(s))
    pop(s);
}

bool is_empty(Stack s)
{
  return s->top == NULL;
}

bool is_full(Stack s)
{
  return false;
}

void push(Stack s, Item i)
{
  struct node *new_node = malloc(sizeof(struct node));
  if (new_node == NULL)
    terminate("Error in push: stack is full.");

  new_node->data = i;
  new_node->next = s->top;
  s->top = new_node;
}

Item pop(Stack s)
{
  struct node *old_top;
  Item i;
 
  if (is_empty(s))
    terminate("Error in pop: stack is empty.");

  old_top = s->top;
  i = old_top->data;
  s->top = old_top->next;
  free(old_top);
  return i;
}

注意,destroy 函数在调用 free 函数(释放 stack_type 结构所占的内存)前先调用了 make_empty(释放链表中结点所占的内存)。

请参阅

(完)

comments powered by Disqus