C语言 表、栈和队列详解及实例代码

时间:2022-06-02 02:36:46

C语言 表、栈和队列详解

表ADT

  形如A1,A2,A3…An的表,这个表的大小为n,而大小为0的表称为空表,非空表中,Ai+1后继Ai,Ai-1前驱Ai,表ADT的相关操有PrintList打印表中的元素;CreateEmpty创建一个空表;Find返回关键字首次出现的位置;Insert和Delete从表的某个位置插入和删除某个关键字。

  对表的所有操作都可以通过使用数组来实现,但在这里使用链表的方式来实现。链表(linked list)由一系列不必在内存中相连的结构组成,每个结构均含有元素和指向包含该元素后继元的结构的指针。链表的结构有很多种,单向链表、双向链表、循环链表、有无表头的链表,这里以有表头结点的单向链表为例,其余几种的实现思路相同。

  首先定义链表的结构:

?
1
2
3
4
5
struct Node
{
 ElementType Element;
 Node *Next;
};

  表ADT的主要操作:

?
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
Node *CreateEmpty()
{
 Node *header = new Node;
 Header->Element = 0;
 Header->Next = NULL;
 return header;
}
void PrintList(Node *List)
{
 Node *p = List->Next;
 While (p)
 {
  std::cout << p->Element << “ “;
 }
}
Node *Find(Node *List, ElementType X)
{
 Node *p = List->Next;
 while(p && p->Element != X)
 {
  p = p->Next;
 }
 return p;
}
void Insert(Node *List, ElementType X)
{
 Node *p = List;
 while(p->Next)
 {
  p = p->Next;
 }
 p->Next = new Node;
 p = p->Next;
 p->Next = NULL;
 p->Element = X;
}
void Delete(Node *List, ElementType X)
{
 Node *p = List->Next;
 Node *d = p->Next;
 while(d->Element != X)
 {
p = p->Next;
d = p->Next;
 }
 p->Next = d->Next;
 delete d;
}

  以上是基本的几个操作,可以看到,操作中没有对链表是否为空进行检测,在删除操作中存在隐患。

栈ADT

  栈(stack)是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫做栈的顶(top)。对栈的基本操作有Push(进栈)和Pop(出栈),前者相当于插入,后者相当于删除最后插入的元素。

  栈的实现可以是指针,或者使用数组,数组的实现在笔者前面的已经介绍过了,今次使用单链表的方式实现。

  首先,栈的结构定义:

?
1
2
3
4
5
struct Stack
{
 ElementType Element;
 Stack *Next;
};

  栈ADT的主要操作:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Stack *CreateStack()
{
 Stack *S = new Stack;
 S->Next = NULL;
 return S;
}
void Push(Stack *S, ElementType X)
{
 Stack *p = new Stack;
 p->Next = S;
 S->Element = X;
 S = p;
}
ElementType Pop(Stack *S)
{
 Stack *p = S;
 if(S->Next)
 {
S = S->Next;
delete p;
 }
 return S->Element;
}

队列ADT

  像栈一样,队列也是一种表,然而,使用队列时插入在一端进行而删除则在另一端进行。队列的基本操作时Enqueue(入队)和Dequeue(出队),入队是指在表的末端rear插入一个元素,而出队是删除(或者返回)在表的开头front的元素。

  如同栈的情形一样,栈的实现可以用指针和数组的方式,数组的方式笔者同样在之前做过介绍,今次使用单链表的方式实现。

  首先,定义队列的结构:

?
1
2
3
4
5
struct Queue
{
 ElementType Element;
 Queue *Next;
};

  队列ADT的主要操作:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Queue *CreateQueue()
{
 Queue *p = new Queue;
 p->Next = NULL;
 return p;
}
void Enqueue(Queue *rear, ElementType X)
{
 Queue *p = new Queue;
 p->Element = X;
 rear->Next = p;
 rear = p;
}
ElementType Dequeue(Queue *front)
{
 Queue *p = front;
 ElementType e = front->Element;
 front = front->Next;
 delete p;
 return e;
}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

原文链接:http://blog.csdn.net/mr_avin/article/details/53398531