数据结构与算法分析(三)
这一次,我们说一说三种比较简单的数据结构,是一维的,分别是:
1.表
2.栈
3.队列
1.表
对于表而言,当然可以用数组来实现,插入和删除的时候会带来巨大的开销,因此更多的时候,我们都是采用"链表(linked list)"这种形式.
链表有很多变种,但是最基础的,基本功能是相似的,通常为了方便,链表的头(header)我们会放一个哑节点.
我们用ADT的方式实现.
Linked.h
#ifndef LIST_H#define LIST_H#includeusing namespace std;struct ListNode;typedef int ElementType;typedef struct ListNode *PtrToNode;typedef PtrToNode List;typedef PtrToNode Position;List CreateList();int IsEmpty(List L);int IsLast(Position P, List L);Position Find(ElementType X, List L);void Delete(ElementType X, List L);Position FindPrevious(ElementType X, List L);void Insert(ElementType X, List L, Position P);void DeleteList(List L);Position Header(List L);Position First(List L);void Print(List L);struct ListNode{ ElementType Element; Position Next;};List CreateList(){ Position P = new ListNode; P->Next = nullptr; return P;}int IsEmpty(List L){ return L->Next == nullptr;}int IsLast(Position P, List L){ return P->Next == nullptr;}Position Find(ElementType X, List L){ Position P = L->Next; while(P != nullptr && P->Element != X){ P = P->Next; } return P;}void Delete(ElementType X, List L){ Position P = L->Next, tmpCell; P = FindPrevious(X, L); if(!IsLast(P, L)){ tmpCell = P->Next; P->Next = tmpCell->Next; delete tmpCell; }}Position FindPrevious(ElementType X, List L){ Position P = L; while(P->Next != nullptr && P->Next->Element != X){ P = P->Next; } return P;}void Insert(ElementType X, List L, Position P){ Position tmpCell = new ListNode; tmpCell->Element = X; tmpCell->Next = P->Next; P->Next = tmpCell;}void DeleteList(List L){ Position P, tmpCell; P = L->Next; L->Next = nullptr; while(P != nullptr){ tmpCell = P->Next; delete P; P = tmpCell; }}Position Header(List L){ return L;}Position First(List L){ return L->Next;}void Print(List L){ Position P = L->Next; while(P != nullptr){ cout << P->Element << "->"; P = P->Next; } cout << "nullptr" << endl;;}#endif // LIST_H
我们将所有的操作都放在Linked.h头文件里,如果在程序中想要引用,直接 #include就好.
ADT可分为"数据集"和"操作集",很符合"面向对象"的思想.
数据集:
存放数据,以及下一个结点的地址,
struct Node{
ElementType Element; Position Next; };操作集:
1.创建链表CreateList
2.元素插入Insert
3.元素删除Delete
4.查找元素位置Find
5.删除链表DeleteList
特地增加了一个Print(List L)函数,方便测试时候使用.
2.栈
栈也是一种非常常见的数据结构,应用广泛.它的最大特点,在于它的后进先出特性,因此栈通常也被叫做'LIFO'表.栈的实现有两种,可以用链表,也可以用数组,两种方法我都会写,但我更倾向于选择链表这种实现方式,不仅节约空间,而且使用起来比较灵活.
相较于普通的链表,栈无疑具有一些特殊的操作,主要是两个:
进栈(Push)
出栈(Pop)
所谓Push就是把元素压入到栈的顶端,Pop操作就是把栈顶的元素取出来,并返回.
链表实现
Stack.h
#ifndef STACK_H#define STACK_H#includeusing namespace std;struct StackNode;typedef struct StackNode *PtrToNode;typedef PtrToNode Stack;typedef int ElementType;int IsEmpty(Stack S);Stack CreateStack();void MakeEmpty(Stack S);void Push(ElementType X, Stack S);ElementType Top(Stack S);ElementType Pop(Stack S);void DisposeStack(Stack S);void Print(Stack S);struct StackNode{ ElementType Element; PtrToNode Next;};int IsEmpty(Stack S){ return S->Next == nullptr;}Stack CreateStack(){ Stack S = new StackNode; S->Next = nullptr; return S;}void MakeEmpty(Stack S){ if(S == nullptr){ return; }else{ while(!IsEmpty(S)){ Pop(S); } }}void Push(ElementType X, Stack S){ PtrToNode tmpCell = new StackNode; tmpCell->Element = X; tmpCell->Next = S->Next; S->Next = tmpCell;}ElementType Top(Stack S){ if(!IsEmpty(S)){ return S->Next->Element; } return -1;}ElementType Pop(Stack S){ if(!IsEmpty(S)){ ElementType tmp; PtrToNode firstCell = S->Next; tmp = firstCell->Element; S->Next = firstCell->Next; delete firstCell; return tmp; } return -1;}void DisposeStack(Stack S){ PtrToNode P = S->Next, tmp; S->Next = nullptr; while(P != nullptr){ tmp = P->Next; delete P; P = tmp; }}void Print(Stack S){ PtrToNode P = S->Next; while(P != nullptr){ cout << P->Element << "->"; P = P->Next; } cout << "nullptr" << endl;}#endif // STACK_H
这里我依旧添加了一个Print()的函数,方便测试.
数组实现
StackArray.h
#ifndef STACKARRAY_H#define STACKARRAY_H#includeusing namespace std;typedef int ElementType;struct StackRecord;typedef struct StackRecord *Stack;int IsEmpty(Stack S);int IsFull(Stack S);Stack CreateStack(int MaxElements);void DisposeStack(Stack S);void MakeEmpty(Stack S);void Push(ElementType X, Stack S);ElementType Top(Stack S);ElementType Pop(Stack S);void Print(Stack S);struct StackRecord{ int Capacity; int TopOfStack; ElementType *Array;};int IsEmpty(Stack S){ return S->TopOfStack == -1;}int IsFull(Stack S){ return S->TopOfStack == S->Capacity - 1;}Stack CreateStack(int MaxElements){ Stack S = new StackRecord; S->Capacity = MaxElements; S->Array = new ElementType[MaxElements]; MakeEmpty(S); return S;}void DisposeStack(Stack S){ delete S->Array; delete S;}void MakeEmpty(Stack S){ S->TopOfStack = -1;}void Push(ElementType X, Stack S){ if(IsFull(S)){ return; }else{ S->Array[++S->TopOfStack] = X; }}ElementType Top(Stack S){ if(IsEmpty(S)){ return -1; }else{ return S->Array[S->TopOfStack]; }}ElementType Pop(Stack S){ if(IsEmpty(S)){ return -1; }else{ return S->Array[S->TopOfStack--]; }}void Print(Stack S){ if(!IsEmpty(S)){ for(int i = 0; i <= S->TopOfStack; ++i){ cout << S->Array[i] << "->"; } } cout << endl;}#endif // STACKARRAY_H
3.队列
与栈有所不同,队列是一种"先进先出"的数据结构,可以理解为排队:谁先到.就先为谁服务.队列会有一些跟高级的用法,这些后面才会涉及到,这里我们仅仅实现最基础的部分,同样可以分两种形式实现:数组和链表,具体应用中如何使用因人而异,如果数据量不是特别大的话,用数组实现也许会更加清楚直接一些.
ADT这种形式对于数据结构的封装,无疑减轻了我们调用时的难度.QueueArray.h
#ifndef QUEUEARRAY_H#define QUEUEARRAY_H#includeusing namespace std;typedef int ElementType;struct QueueRecord;typedef struct QueueRecord *Queue;int IsEmpty(Queue Q);int IsFull(Queue Q);Queue CreateQueue(int MaxElements);void DisposeQueue(Queue Q);void MakeEmpty(Queue Q);ElementType Dequeue(Queue Q);ElementType Front(Queue Q);void Enqueue(ElementType X, Queue Q);static int Succ(int Value, Queue Q);void Print(Queue Q);struct QueueRecord{ int Capacity; int Front; int Rear; int Size; ElementType *Array;};int IsEmpty(Queue Q){ return Q->Size == 0;}int IsFull(Queue Q){ return Q->Size == Q->Capacity;}Queue CreateQueue(int MaxElements){ Queue Q = new QueueRecord; Q->Capacity = MaxElements; Q->Array = new ElementType[MaxElements]; MakeEmpty(Q); return Q;}void MakeEmpty(Queue Q){ Q->Size = 0; Q->Front = 0; Q->Rear = -1;}static int Succ(int Value, Queue Q){ if(++Value == Q->Capacity){ Value = 0; } return Value;}void Enqueue(ElementType X, Queue Q){ if(IsFull(Q)){ return; }else{ Q->Rear = Succ(Q->Rear, Q); Q->Array[Q->Rear] = X; ++Q->Size; }}ElementType Dequeue(Queue Q){ ElementType temp; if(IsEmpty(Q)){ return -1; }else{ temp = Q->Array[Q->Front]; Q->Front = Succ(Q->Front, Q); --Q->Size; } return temp;}ElementType Front(Queue Q){ if(IsEmpty(Q)){ return -1; }else{ return Q->Array[Q->Front]; }}void DisposeQueue(Queue Q){ delete Q->Array; delete Q;}void Print(Queue Q){ int i, j = Q->Front; for(i = 0; i < Q->Size; ++i){ cout << Q->Array[j] << "->"; j = Succ(j, Q); } cout << endl;}#endif // QUEUEARRAY_H
Queue.h
#ifndef QUEUE_H#define QUEUE_H#includeusing namespace std;typedef int ElementType;struct QueueNode;typedef struct QueueNode *PtrToNode;typedef PtrToNode Queue;typedef PtrToNode Position;int IsEmpty(Queue Q);Queue CreateQueue();void DisposeQueue(Queue Q);void MakeEmpty(Queue Q);ElementType Dequeue(Queue Q);ElementType Front(Queue Q);void Enqueue(ElementType X, Queue Q);void Print(Queue Q);struct QueueNode{ ElementType Element; Position Next;};int IsEmpty(Queue Q){ return Q->Next == nullptr;}Queue CreateQueue(){ Queue Q = new QueueNode; Q->Next = nullptr; return Q;}void Enqueue(ElementType X, Queue Q){ Position P = Q, tmpCell; while(P->Next != nullptr){ P = P->Next; } tmpCell = new QueueNode; tmpCell->Element = X; tmpCell->Next = P->Next; P->Next = tmpCell;}ElementType Dequeue(Queue Q){ if(IsEmpty(Q)){ return -1; }else{ Position P = Q->Next; ElementType temp; temp = P->Element; Q->Next = P->Next; delete P; return temp; }}ElementType Front(Queue Q){ if(IsEmpty(Q)){ return -1; }else{ return Q->Next->Element; }}void DisposeQueue(Queue Q){ Position P = Q->Next, tmpCell; Q->Next = nullptr; while(P != nullptr){ tmpCell = P->Next; delete P; P = tmpCell; }}void Print(Queue Q){ Position P = Q->Next; while(P != nullptr){ cout << P->Element << "->"; P = P->Next; } cout << endl;}#endif // QUEUE_H