CrazyCatJack

CrazyCatJack

关注
发信
关注(28)粉丝(399)

《数据结构与算法分析》学习笔记-第三章-表、栈和队列

Hi, all!我自己实现了一个双向循环链表，发布在Github上。
叫QuickList，包含完整的链表模块源码和测试用例。。
大家可以去github上获取，如果觉得好用请帮我点个star，谢谢啦嘿嘿~
QuickList传送门

3.1 抽象数据类型

程序设计的基本法则之一是例程不应超过一页，可以通过把程序模块化实现。每个模块是一个逻辑单位并执行某个特定的任务，它通过调用其他模块而使本身保持很小。优点如下：

  1. 调试小程序比调试大程序容易得多
  2. 多个人同时对一个模块式程序编程要更容易
  3. 一个好的模块化程序把某些依赖关系只局限在一个历程中，这样修改起来会更容易
  4. 全局变量及其副作用是有害的观念也正是出于模块化是有益的想法

概念：抽象数据类型ADT是一些操作的集合。这种操作的实现只在程序中编写一次，而程序中任何其他部分需要在该ADT上运行起哄的一种操作时，可以通过调用合适的函数来进行。如果要改变操作的细节，那么只需要修改运行这些ADT操作的例程就很容易实现。

3.2 表ADT

  • 我们将处理一般的形如 A1, A2, A3, ... , AN的表，我们说这个表的大小是N，我们称大小为0的表为空表。对于除空表外的任何表，我们说Ai+1后继Ai（i < N），并称Ai-1前驱Ai(i > 1)。表中的第一个元素是A1，而最后一个元素是AN。我们将不定义A1的前驱元，也不定义AN的后继元。元素Ai在表中的位置为i
  • 与这些“定义”相关的是我们要在表ADT上进行的操作的集合。PrintList/MakeEmpty/Find/Insert/Delete/FindKth/Next/Previous等

3.2.1 表的简单数组实现

连续存储，访问很快，插入删除很慢，而且需要定义数组的大小，而这个大小通常要设的大一些浪费内存空间。所以简单数组一般不用来实现表这种结构

3.2.2 链表

指针变量就是包含存储另外某个数据地址的变量。因此，如果P被声明为指向一个结构的指针，那么存储在P中的值就被解释为主存中的一个位置，在该位置能够找到一个结构，该结构的一个域可以通过P->FieldNme访问。使用链表实现表，可以在线性时间内完成PrintList/Find（L, Key）。FindKth(L, i)需要花费O(i)时间。实践中这个界是保守的，因为调用FindKth常常以按i排序的方式进行。例如FindKth(L,2), FindKth(L,3)可以通过对表的一次扫描同时实现。删除命令可以通过一次free操作和一次指针的修改实现；插入命令可以通过一次malloc操作和两次指针修改实现

3.2.3 程序设计细节

使用HEAD节点实现一些在表的前面实现插入和删除操作。实现FindPrevious例程，来实现删除节点的操作。

  • IsEmpty
// 书上例程
int
IsEmpty(List L)
{
    return L->next == NULL;
}
  • IsLast
// 书上例程
int
IsLast(Position P, List L)
{
    return P->next == NULL;
}
  • Find
// 书上例程
Position
Find(Element X, List L)
{
    Position P;

    P = L->next;
    while (P != NULL && P->Element != X) {
        P = P->next;
    }

    return P;
}
  • Delete
// 书上例程
void
Delete(Element X, List L)
{
    Position P, TmpCell;
    P = FindPrevious(X, L);

    if (!IsLast(P, L)) {
        TmpCell = P->next;
        P->next = TmpCell->next;
        free(TmpCell);
    }
}
  • FindPrevious
// 书上例程
Position
FindPrevious(Element X, List L)
{
    Position P;
    P = L;

    while (P->Next != NULL && P->next->Element != X) {
        P = P->next;
    }
    return P;
}
  • Insert
// 书上例程
void
Insert(Element X, List L, Postion P)
{
    Position new = malloc(sizeof(Position));
    if (new == NULL) {
        printf("malloc failed!\n");
    }
    memset(new, 0, sizeof(Position));
    new->Element = X;
    new->next = P->next;
    P->next = new;
}

ADT中还有其他函数，书上未实现，这里我实现出来分享给大家。

  • MakeEmpty
List
MakeEmpty(List L)
{
    Position P, tmp;
    P = L;

    while (P->next != NULL) {
        tmp = P->next;
        P->next = tmp->next;
        free(tmp);
    }

    return L;
}
  • DeleteList
void
DeleteList(List L)
{
    MakeEmpty(L);
    free(L);
}
  • Header
Position
Header(List L)
{
    return L;
}
  • First
Position
First(List L)
{
    return L->next;
}
  • Retrieve
ElementType
Retrieve(Position P)
{
    return P->Element;
}

3.2.4 常见的错误

  1. 初始化变量失败或参数是否超出规定范围的。应该增加初始化检查或者参数检查，再进行相关操作
  2. 声明指向一个结构的指针，并不创建该结构。使用malloc库函数。它创建一个新的结构并返回指向该结构的指针。如果想让指针变量沿着表前进，则没必要创建新的结构。
  3. free(P)的结果是：P正在指向的地址没变，但是该地址处的数据此时已经无定义了
  4. 如果从未对一个链表进行过删除操作，那么调用malloc的次数应该等于表的大小，若有表头则再加1
  5. 删除节点，需要一个临时变量。因为节点被free之后，无法访问到原指针指向的地址
  6. malloc(sizeof(PtrToNode))只是给指针分配一个空间，并不给结构体分配足够的空间

3.2.5 双链表

需要在每个节点上增加一个指向前驱节点的指针，增加了空间的需求，使得插入和删除的空间开销增加一倍，但是删除速度加快了，因为前驱节点无需遍历寻找

3.2.6 循环链表

最后一个节点的next指针指向第一个节点，如果有头节点则指向头节点。如果是双向链表，则第一个节点的previous指针指向最后的节点

3.2.7 例子

多项式ADT

  1. 多项式结构体定义
//书上例程
typedef struct {
    int CoeffArray[MaxDegree + 1];
    int HighPower;
}
  1. 初始化多项式为0
//书上例程
void
ZeroPolynomial(Polynomial Poly)
{
    int i;

    for (i = 0; i <= MaxDegree; i++) {
        Poly.CoeffArray[i] = 0;
    }
    Poly.HighPower = 0;
}
  1. 多项式相加
//书上例程，时间复杂度O(N)
void
AddPolynomial(const Polynomial Poly1, const Polynomial Poly2, Polynomial PolySum)
{
    int i;
    ZeroPolynomial(PolySum);
    PolySum->HighPower = Max(Poly1->HighPower, Poly2->HighPower);

    for (i = 0; i < PolySum->HighPower; i++) {
        PolySum->CoeffArray[i] = Poly1->CoeffArray[i] + Poly2->CoeffArray[i];
    }
}
  1. 多项式相乘
//书上例程，时间复杂度O(N^2)
void
MultPolynomial(const Polynomial Poly1, const Polynomial Poly2, Polynomial PolyProd)
{
    int i, j;
    ZeroPolynomial(PolyProd);

    PolyProd->HighPower = Poly1->HighPower + Poly2->HighPower;

    if (PolyProd->HighPower > MaxDegree) {
        printf("Exceeded array size");
    } else {
        for (i = 0; i < Poly1->HighPower; i++) {
            for (j = 0; j < Poly2->HighPower; j++) {
                PolyProd->CoeffArray[i + j] += Poly1->CoeffArray[i] * Poly2->CoeffArray[j];
            }
        }
    }
}

另一种方法：单链表。多项式的每一项含在一个节点中，并且这些节点以次数递减的顺序排序。

  1. 节点结构体定义
//书上例程
struct Node {
    int Cofficient;
    int Exponent;
    PtrToNode Next;
}
typedef struct Node *PtrToNode;
typedef PtrToNode Polynomial;
  1. 创建并初始化节点
//自己写的
Polynomial
CreatePolynomial()
{
    Polynomial tmp;
    tmp = (Polynomial)malloc(sizeof(struct Node));
    memset(tmp, 0, sizeof(struct Node));
    return tmp;
}
  1. 销毁并释放节点
//自己写的
void
DestroyPolynomial(Polynomial P)
{
    free(P);
}
  1. 多项式相加
//自己写的。时间复杂度O(N^2)
void
AddPolynomial(const Polynomial Poly1, const Polynomial Poly2, Polynomial PolySum)
{
    int i, j;
    Polynomial P1, P2, Psum, Ptmp;

    Psum = PolySum;
    for (P1 = Poly1->next; P1 != NULL; P1 = P1->next) {
        for (P2 = Poly2->next; P2 != NULL; P2 = P2->next) {
            if (P1->Exponent == P2->Exponent) {
                break;
            }
        }

        Ptmp = CreatePolynomial();
        Ptmp->Exponent = P1->Exponent;

        if (P2 == NULL) {
            Ptmp->Cofficient = P1->Cofficient;
        } else {
            Ptmp->Cofficient = P1->Cofficient + P2->Cofficient;
        }

        Psum->next = Ptmp;
        Ptmp->next = NULL;
        Psum = Psum->next;
    }
}
  1. 多项式相乘
//自己写的。时间复杂度O(N^3)
void
MultPolynomial(const Polynomial Poly1, const Polynomial Poly2, Polynomial PolyProd)
{
    int i, j, exponentTmp;
    Polynomial P1, P2, Prod, Ptmp;

    Prod = PolyProd->next;
    for (P1 = Poly1->next; P1 != NULL; P1 = P1->next) {
        for (P2 = Poly2->next; P2 != NULL; P2 = P2->next) {
            exponentTmp = P1->Exponent + P2->Exponent;
            while (Prod != NULL) {
                if (Prod->Exponent == exponentTmp) {
                    Prod->Cofficient += P1->Cofficient * P2->Cofficient;
                    break;
                }
                Prod = Prod->next;
            }

            if (Prod == NULL) {
                Ptmp = CreatePolynomial();
                Ptmp->Exponent = exponentTmp;
                Ptmp->Cofficient = P1->Cofficient * P2->Cofficient;

                Prod = PolyProd->next;
                PolyProd->next = Ptmp;
                Ptmp->next = Prod;
            }
        }
    }
}

桶式排序

// 自己写的，时间复杂度O(N)
void
sortBucket(int *array, int num, int maxSize)
{
    int CountArraySize = maxSize + 1;
    int *Count = (int *)malloc(CountArraySize * sizeof(int));
    memset(Count, 0, CountArraySize * sizeof(int));

    int inputCnt;
    for (inputCnt = 0; inputCnt < num; inputCnt++) {
        Count[array[inputCnt]] = array[inputCnt];
    }

    for (inputCnt = 1; inputCnt < CountArraySize; inputCnt++) {
        if (Count[inputCnt] != 0) {
            printf("%d", Count[inputCnt]);
        }
    }
}

基数排序，我自己实现了并上传到了Github上，大家可以获得源码。
bucketSort2

// SPDX-License-Identifier: GPL-2.0-only
/*
 *	bucketSort2.c
 *
 * Copyright (C) 2020  xuri
 */

/*
 * This file show how bucket sort running, it based on QuickList module
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "QuickList.h"

#define ARRAY_NUM	10
#define BUCKET_NUM 10 //10 buckets
#define NUMBER_RANGE	3 // 0 - 999

void bucketSort2(int *inputArray, int num)
{
	int divisor = 1;
	int cnt;
	int *recvdata;
	int times = 0;
	QuickListNode_T *tmp = NULL, *tmp2 = NULL;
	QuickListNode_T *qlArray[BUCKET_NUM];


	/* initialize the qlArray */
	memset(qlArray, 0, BUCKET_NUM);
	for (cnt = 0; cnt < BUCKET_NUM; cnt++) {
		qlArray[cnt] = QuickListCreateList();
	}


	/* first time input array and create listnode add to qlArray */
	for (cnt = 0; cnt < num; cnt++) {
		tmp = QuickListCreateNode(&inputArray[cnt]);
		QuickListAddNodetoTail(qlArray[(inputArray[cnt] / divisor % 10)], tmp);
	}
	printf("after first time\n");

	/* finish bucket sort */
	while (times < NUMBER_RANGE - 1) {
		divisor *= 10;
		for (cnt = 0; cnt < BUCKET_NUM; cnt++) {
			tmp = NULL;
			tmp2 = NULL;
			QuickList_for_each_entry_safe(qlArray[cnt], tmp, tmp2) {
				recvdata = QuickList_entry(int, tmp);
				if ((*recvdata / divisor % 10) != cnt) {
					QuickListDetachNode(qlArray[cnt], tmp);
					QuickListAddNodetoTail(qlArray[(*recvdata / divisor % 10)], tmp);
				}
			}
		}
		times++;
	}

	/* print array after bucket sort */
	printf("Start print array after bucket sort:\n");
	for (cnt = 0; cnt < BUCKET_NUM; cnt++) {
		QuickList_for_each_entry(qlArray[cnt], tmp) {
			recvdata = QuickList_entry(int, tmp);
			printf("%d ", *recvdata);
		}
	}
	printf("\n");
}

多重表：节约空间，花费时间。也可以在每个节点中加入链表头指针，花费空间，节约时间。如图：

链表的游标实现

  • InitializeCursorSpace
struct node
{
    ElementType Element;
    Position Next;
}

typedef int PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
struct Node CursorSpace[SpaceSize];

void InitializeCursorSpace(void)
{
    int cnt;
    for (cnt = 0; cnt < SpaceSize; cnt++) {
        CursorSpace[cnt].Element = 0;
        if (cnt + 1 >= SpaceSize) {
            CursorSpace[cnt].Next = 0;
        } else {
            CursorSpace[cnt].Next = cnt + 1;
        }
    }
}
  • CursorAlloc & CursorFree
static Position
CursorAlloc()
{
    Position P;
    P = CursorSpace[0].Next;
    CursorSpace[0].Next = CursorSpace[P].Next;
    return P;
}

static void
CursorFree(Position X)
{
    CursorSpace[X].Next = CursorSpace[0].Next;
    CursorSpace[0].Next = X;
}
  • IsEmpty
int
IsEmpty(List L)
{
    return (CursorSpace[L].Next == 0);
}
  • IsLast
int
IsLast(Position P, List L)
{
    return (CursorSpace[P].Next == 0);
}
  • Find
Position
Find(ElementType X, List L)
{
    Position tmp;
    for(tmp = CursorSpace[L].Next; tmp != 0; tmp = CursorSpace[tmp].Next) {
        if (CursorSpace[tmp].Element == X) {
            break;
        }
    }

    return tmp;
}
  • Delete
void
Delete(ElementType X, List L)
{
    Position tmp, tmpNext;
    for (tmp = L; CursorSpace[tmp].Next != 0; tmp = CursorSpace[tmp].Next) {
        tmpNext = CursorSpace[tmp].Next;
        if (CursorSpace[tmpNext].Element == X) {
            CursorSpace[tmp].Next = CursorSpace[tmpNext].Next;
            CursorFree(tmpNext);
        }
    }
}
  • Insert
void
Insert(ElementType X, List L)
{
    Position P;
    P = CursorAlloc();
    if (P == 0) {
        printf("run out of memory\n");
        return;
    }
    CursorSpace[P].Element = X;
    CursorSpace[P].Next = CursorSpace[L].Next;
    CursorSpace[L].Next = P;
}

3.3 栈ADT

1） 单链表实现

节点定义

struct node;
typedef struct node *PtrToNode;
typede PtrToNode Stack;

struct node {
    ElementType Element;
    PtrToNode Next;
}
  • CreateStack
Stack
CreateStack(void)
{
    Stack s = NULL;
    s = (Stack)malloc(sizeof(struct node));
    if (s == NULL) {
        printf("stack malloc failed\n");
        return s;
    }
    memset(s, 0, sizeof(struct node));
    s->Next = NULL;
    return s;
}
  • MakeEmpty
void
MakeEmpty(Stack s)
{
    PtrToNode p = NULL, tmp = NULL;
    p = s->Next;
    while (p != NULL) {
        tmp = p->Next;
        free(p);
        p = tmp;
    }
}
  • Push
int
Push(ElementType X, Stack s)
{
    PtrToNode tmp = NULL;
    tmp = (PtrToNode)malloc(sizeof(struct node));
    if (tmp == NULL) {
        return -1;
    }
    memset(tmp, 0, sizeof(struct node));
    tmp->Element = X;
    tmp->Next = s->Next;
    s->Next = tmp;
    return 0;
}
  • Pop
void
Pop(Stack s)
{
    if (s == NULL || s->Next == NULL) {
        return NULL;
    }
    PtrToNode tmp = NULL;
    tmp = s->Next;
    s->Next = tmp->Next;
    free(tmp);
}
  • Top
ElementType
Top(Stack s)
{
    return s->Next.Element;
}
  • IsEmtpy
int
IsEmpty(Stack s)
{
    if (s == NULL) {
        return -1;
    }
    return (s->Next == NULL);
}

2） 栈的数组实现

一个影响栈的执行效率的问题是错误检测。除非在错误处理极其重要的场合（如在操作系统中），惯用手法是在栈例程中省去错误检测。当编写程序时，忽略错误检测一般是不妥的，应该随时编写错误检测的代码，如果它们冗长，当它们确实耗费太多时间时，可以将它们去掉。

  • 栈定义
struct StackRecord;
typedef struct StackRecord *Stack;

#define EmptyTOS (-1)
#define MinStackSize (5)

struct StackRecord
{
    int Capacity;
    int TopOfStack;
    ElementType *Array;
}
  • CreateStack
Stack
CreateStack(int MaxElement)
{
    if (MaxElement < MinStackSize) {
        return NULL;
    }
    Stack s = NULL;
    s = (Stack)malloc(sizeof(struct StackRecord));
    if (s == NULL) {
        return NULL;
    }
    memset(s, 0, sizeof(struct StackRecord));
    s->Capacity = MaxElement;
    s->TopOfStack = EmptyTOS;
    s->Array = (ElementType *)malloc(sizeof(ElementType) * MaxElement);
    if (s->Array == NULL) {
        free(s);
        return NULL;
    }
    memset(s->Array, 0, sizeof(ElementType) * MaxElement);
    return s;
}
  • DisposeStack
void
DisposeStack(Stack s)
{
    if (s->Array != NULL) {
        free(s->Array);
        s->Array = NULL;
    }
    if (s != NULL) {
        free(s);
    }
}
  • IsEmpty
int
IsEmpty(Stack s)
{
    return (s->TopOfStack == EmptyTOS);
}
  • MakeEmpty
void
MakeEmtpy(Stack s)
{
    memset(s->Array, 0, sizeof(ElementType) * s->Capacity);
    s->TopOfStack = EmptyTOS;
}
  • IsFull
int
IsFull(Stack s)
{
    return (s->TopOfStack + 1 == s->Capacity);
}
  • Push
void
Push(Stack s, ElementType X)
{
    if (IsFull(s)) {
        printf("stack s is full\n");
        return;
    }
    s->array[++s->TopOfStack] = X;
}
  • TopAndPop
ElementType
TopAndPop(Stack s)
{
    if (s->TopOfStack == EmptyTOS) {
        return EmptyTOS;
    }
    return s->array[s->TopOfStack--];
}
  • Pop
void
Pop(Stack s)
{
    if (IsEmpty(s)) {
        printf("stack s is empty\n");
    }
    s->TopOfStack--;
}
  • Top
ElementType
Top(Stack s)
{
    return s->Array[s->TopOfStack];
}

3) 应用

平衡符号

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "stackADT.h"

#define BRACKET_TYPE 3
#define TEST_STR	"(abcd}[ef])"
char bracketOpen[BRACKET_TYPE] = {'{', '(', '['};
char bracketClose[BRACKET_TYPE] = {'}', ')', ']'};

int symbolCheck(char *inputStr)
{
	int strLen = strlen(inputStr);
	int cnt, cnt2;
	char tmp;
	int ret = -1;

	Stack s = CreateStack();
	if (s == NULL) {
		return ret;
	}

	for (cnt = 0; cnt < strLen; cnt++) {
		for (cnt2 = 0; cnt2 < BRACKET_TYPE; cnt2++) {
			if (inputStr[cnt] == bracketOpen[cnt2]) {
				Push(inputStr[cnt], s);
			}

			if (inputStr[cnt] == bracketClose[cnt2]) {
				tmp = Top(s);
				if (tmp != bracketOpen[cnt2]) {
					goto __exit;
				}
				Pop(s);
			}
		}
	}
	if (!IsEmpty(s)) {
		goto __exit;
	}

	ret = 0;

__exit:
	DistroyStack(s);
	return ret;
}

void main()
{
	char *p = TEST_STR;
	if (0 == symbolCheck(p)) {
		printf("check success\n");
	} else {
		printf("check fail\n");
	}
}
  • 后缀表达式：时间复杂度O(N)，因为对输入中每个元素的处理都是由一些栈操作组成并花费常熟时间，该算法的计算是非常简单的。当一个表达式以后缀记号给出时，没有必要知道任何优先规则，这是一个明显的优点
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "stackADT.h"

#define OPERATOR_TYPE 4
char Operator[OPERATOR_TYPE] = {'+', '-', '*', '/'};
char *Expression = "12+3*85-/";

void suffixExpression(char *inputStr)
{
	int cnt, cnt2;
	int operateNum1, operateNum2;
	Stack s = CreateStack();
	for (cnt = 0; inputStr[cnt] != '\0'; cnt++) {
		if ((inputStr[cnt] >= '0') && (inputStr[cnt] <= '9')) {
			printf("Push %d\n", (inputStr[cnt] - '0'));
			Push((inputStr[cnt] - '0'), s);
		}

		for (cnt2 = 0; cnt2 < OPERATOR_TYPE; cnt2++) {
			if (inputStr[cnt] == Operator[cnt2]) {
				operateNum2 = Top(s);
				Pop(s);
				operateNum1 = Top(s);
				Pop(s);
				printf("operator=%c, num1=%d, num2=%d\n", Operator[cnt2], operateNum1, operateNum2);

				switch (cnt2) {
					case 0: {
						Push((operateNum1 + operateNum2), s);
						printf("Push %d\n", operateNum1 + operateNum2);
						break;
					}
					case 1: {
						Push((operateNum1 - operateNum2), s);
						printf("Push %d\n", operateNum1 - operateNum2);
						break;
					}
					case 2: {
						Push((operateNum1 * operateNum2), s);
						printf("Push %d\n", operateNum1 * operateNum2);
						break;
					}
					case 3: {
						Push((operateNum1 / operateNum2), s);
						printf("Push %d\n", operateNum1 / operateNum2);
						break;
					}
					default:
						break;
				}
			}
		}
	}

	operateNum1 = Top(s);
	Pop(s);
	DistroyStack(s);
	printf("result=%d\n", operateNum1);
}

void main()
{
	suffixExpression(Expression);
}
  • 中缀到后缀的转换: 当读到一个操作数的时候，立即把它放到输出中，操作符不立即输出，从而必须先存在某个地方。正确的做法是将已经见到过的操作符放到栈中，而不是放到输出中。当遇到左圆括号时我们也要将其推入栈中，从一个空栈开始计算。如果见到一个右括号，那么就将栈元素弹出，将弹出的符号写出直到我们遇到一个左括号，但是这个左括号和右括号只是弹出，并不输出。如果见到其他任何操作符号，那么就从栈中弹出栈元素，直到发现优先级更低的元素则不弹出，将读取到的操作符入栈(若优先级相同则出栈)。有一个例外，除非是在处理一个）的时候，否则我们绝不从栈中移走（。因此，当从栈弹出元素的工作完成后，再将操作符压入栈中。最后，如果读到输入的末尾，我们将栈元素弹出直到该栈变成空栈。将符号写道输出中。
  • 函数调用: 函数的嵌套调用过程中，主调例程的所有局部变量和返回地址要被保存起来（入栈），在被调例程结束后进行恢复（出栈）。因此全部工作均可由一个栈来完成。当前环境是由栈顶描述的。因此，一条返回语句就可给出前面的环境。实际计算机中的栈，常常时从内存分区的高端向下增长。而在许多系统中是不检测栈溢出的，但是用尽栈空间的情况总是可能发生的。栈溢出的后果是严重的：程序崩溃，数据错误。在正常情况下不应该越出栈空间，发生这种情况通常是由失控递归的指向引起的（忘记基准情形），也有可能是某些表面上正确的程序，但是递归了N次（数量巨大），导致栈溢出。例如尾递归。
  • 尾递归完全可由goto语句改造出来。例如可以goto到顶部。递归总能够被彻底除去（编译器是在转变成汇编语言时完成的）虽然非递归程序一般说来确实比等价的递归程序要快，但是代价时使得程序的清晰性变得不足

3.4 队列

数组实现

  • 节点定义
#define CAPACITY 10
struct QueueRecord {
    int Capacity;
    int Front;
    int Rear;
    int Size;
    ElementType *Array;
}

typedef struct QueueRecord *Queue;
  • CreateQueue
Queue
CreateQueue(int MaxElements)
{
    if (MaxElements <= 0) {
        return NULL;
    }
    Queue q = NULL;
    q = (Queue)malloc(sizeofstruct QueueRecord(struct QueueRecord));
    if (q == NULL) {
        printf("queue malloc failed\n");
        return NULL;
    }
    memset(q, 0, sizeof(struct QueueRecord));
    q->Capacity = CAPACITY;
    q->Front = 1;
    q->Rear = 0;
    q->Size = 0;
    q->Array = (ElementType *)malloc(sizeof(ElementType) * CAPACITY);
    if (q->Array == NULL) {
        return NULL;
    }
    memset(q->Array, 0, sizeof(ElementType) * CAPACITY);
    return q;
}
  • DisposeQueue
void
DisposeQueue(Queue Q)
{
    if (Q == NULL) {
        return;
    }
    if (Q->Array != NULL) {
        free(Q->Array);
    }
    free(Q);
}
  • IsEmpty
int
IsEmpty(Queue Q)
{
    if (Q == NULL) {
        return -1;
    }
    return (Q->Size == 0);
}
  • IsFull
int
IsFull(Queue Q)
{
    if (Q == NULL) {
        return -1;
    }
    return (Q->Size == Q->Capicity);
}
  • Enqueue
int
Enqueue(Queue Q, Element X)
{
    if (Q == NULL) {
        return -1;
    }
    if (IsFull(Q)) {
        printf("Queue Q is full\n");
        return -1;
    }

    if (++(Q->Rear) >= Q->Capicity) {
        Q->Rear -= Q->Capicity;
    }
    Q->Array[Q->Rear] = X;
    Q->Size++;
    return 0;
}
  • Dequeue
int
Dequeue(Queue Q)
{
    if (Q == NULL) {
        return -1;
    }
    if (IsEmpty(Q)) {
        printf("Queue Q is empty\n");
        return -1;
    }

    if (++(Q->Front) >= Q->Capicity) {
        Q->Front -= Q->Capicity;
    }
    Q->Size--;
    return 0;
}
  • FrontAndDequeue
ElementType
FrontAndDequeue(Queue Q)
{
    if (Q == NULL) {
        return -1;
    }
    if (IsEmpty(Q)) {
        printf("Queue Q is empty\n");
        return -1;
    }

    ElementType ret = Q->Array[Q->Front];
    if (++(Q->Front) >= Q->Capicity) {
        Q->Front -= Q->Capicity;
    }
    Q->Size--;
    return ret;
}

链表实现

  • 节点定义
typedef struct Queue {
    ElementType Element;
    struct Queue *Pre;
    struct Queue *Next;
} Queue_T;

typedef Queue_T *QueuePtr
typedef QueuePtr QueueHead
#define MaxSize 10
#define EMPTY -1
  • IsEmpty
int
IsEmpty(QueueHead Q)
{
    if (Q == NULL) {
        return -1;
    }
    return (Q->Next == Q);
}
  • IsFull
int
IsFull(QueueHead Q)
{
    if (Q == NULL) {
        return -1;
    }

    int queueCnt = 0;
    QueuePtr tmp = NULL;
    tmp = Q->Next;
    while (tmp != Q) {
        queueCnt++;
        tmp = tmp->Next;
    }

    return (queueCnt == MaxSize);
}
  • CreateQueue
QueueHead
CreateQueue()
{
    QueueHead Q = NULL;
    Q = (QueuePtr)malloc(sizeof(struct Queue));
    if (Q == NULL) {
        return NULL;
    }
    memset(Q, 0, sizeof(struct Queue));
    Q->Next = Q;
    Q->Pre = Q;
    return Q;
}
  • DisposeQueue
int
DisposeQueue(QueueHead Q)
{
    if (Q == NULL) {
        return -1;
    }

    MakeEmpty(Q);
    free(Q);
    return 0;
}
  • MakeEmpty
int
MakeEmpty(QueueHead Q)
{
    if (Q == NULL) {
        return -1;
    }

    QueueHead tmp = NULL, tmpNext = NULL;
    tmp = Q->Next;
    while (tmp != Q) {
        if (tmp) {
            tmpNext = tmp->Next;
            free(tmp);
            tmp = tmpNext;
        }
    }
    return 0;
}
  • Enqueue
int
Enqueue(QueueHead Q, ElementType Element)
{
    if (Q == NULL) {
        return -1;
    }
    if (IsFull(Q)) {
        return -1;
    }

    QueuePtr qAdd = NULL;
    qAdd = (QueuePtr)malloc(sizeof(struct Queue));
    if (qAdd == NULL) {
        return -1;
    }
    memset(qAdd, 0, sizeof(struct Queue));
    qAdd->Element = Element;
    qAdd->Pre = Q->Pre;
    qAdd->Next = Q;
    Q->Pre->Next = qAdd;
    Q->Pre = qAdd;
    return 0;
}
  • Front
ElementType
Front(QueueHead Q)
{
    if (Q == NULL) {
        return EMPTY;
    }
    if (IsEmpty(Q)) {
        return EMPTY;
    }

    return Q->Next->Element;
}
  • Dequeue
int
Dequeue(QueueHead Q)
{
    if (Q == NULL) {
        return -1;
    }
    if (IsEmpty(Q)) {
        return -1;
    }

    QueuePtr tmp = NULL;
    tmp = Q->Next;
    Q->Next = tmp->Next;
    tmp->Next->Pre = Q;
    if (tmp != NULL) {
        free(tmp);
    }
    return 0;
}
  • FrontAndDequeue
ElementType
FrontAndDequeue(QueueHead Q)
{
    if (Q == NULL) {
        return EMPTY;
    }
    if (IsEmpty(Q)) {
        return EMPTY;
    }

    ElementType ret;
    QueuePtr tmp = NULL;
    tmp = Q->Next;
    ret = tmp->Element;
    Q->Next = tmp->Next;
    tmp->Next->Pre = Q;
    if (tmp != NULL) {
        free(tmp);
    }
    return ret;
}

3.4.3 队列的应用

排队论：问题取决于用户加入队列的频率，以及一旦用户得到服务时处理服务的时间。
递归非常强大，但它并不是完全随意的操作；递归的误用和乱用可能导致程序崩溃。

参考文献

  1. Mark Allen Weiss.数据结构与算法分析[M].America, 2007

本文作者: CrazyCatJack

本文链接: https://www.cnblogs.com/CrazyCatJack/p/13321878.html

版权声明:本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

关注博主:如果您觉得该文章对您有帮助，可以点击文章右下角推荐一下，您的支持将成为我最大的动力！

02-19 03:13
Powered by LMLPHP ©2024 CrazyCatJack 0.079563