数据结构期末考试 - TIPS

子串数目

字符串的长度为n,则子串的个数就是个，"software"中非空子串的个数就是8+7+....+1=36个。

二叉树叶节点个数

度为1的节点数为，度为2的节点数为。

叶节点数

共个点，条边。

线索二叉树

利用空余的指针，左前驱右后继

循环队列

队空：

队满：

DFS

/* 邻接表存储的图 - DFS */

void Visit( Vertex V )
{
    printf("正在访问顶点%d\n", V);
}

/* Visited[]为全局变量，已经初始化为false */
void DFS( LGraph Graph, Vertex V, void (*Visit)(Vertex) )
{   /* 以V为出发点对邻接表存储的图Graph进行DFS搜索 */
    PtrToAdjVNode W;

    Visit( V ); /* 访问第V个顶点 */
    Visited[V] = true; /* 标记V已访问 */

    for( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */
        if ( !Visited[W->AdjV] )    /* 若W->AdjV未被访问 */
            DFS( Graph, W->AdjV, Visit );    /* 则递归访问之 */
}

BFS

/* 邻接矩阵存储的图 - BFS */

/* IsEdge(Graph, V, W)检查<V, W>是否图Graph中的一条边，即W是否V的邻接点。  */
/* 此函数根据图的不同类型要做不同的实现，关键取决于对不存在的边的表示方法。*/
/* 例如对有权图, 如果不存在的边被初始化为INFINITY, 则函数实现如下:         */
bool IsEdge( MGraph Graph, Vertex V, Vertex W )
{
    return Graph->G[V][W]<INFINITY ? true : false;
}

/* Visited[]为全局变量，已经初始化为false */
void BFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) )
{   /* 以S为出发点对邻接矩阵存储的图Graph进行BFS搜索 */
    Queue Q;     
    Vertex V, W;

    Q = CreateQueue( MaxSize ); /* 创建空队列, MaxSize为外部定义的常数 */
    /* 访问顶点S：此处可根据具体访问需要改写 */
    Visit( S );
    Visited[S] = true; /* 标记S已访问 */
    AddQ(Q, S); /* S入队列 */

    while ( !IsEmpty(Q) ) {
        V = DeleteQ(Q);  /* 弹出V */
        for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
            /* 若W是V的邻接点并且未访问过 */
            if ( !Visited[W] && IsEdge(Graph, V, W) ) {
                /* 访问顶点W */
                Visit( W );
                Visited[W] = true; /* 标记W已访问 */
                AddQ(Q, W); /* W入队列 */
            }
    } /* while结束*/
}

冒泡

void BubbleSort(int a[], int n) {
    bool finished = 0;
    while (!finished) {
        finished = 1;
        for (int i = 0; i < n - 1; ++i)
            if (a[i + 1] < a[i]) swap(a[i], a[i + 1]), finished = 0;
    }
}

直接插入

void InsertSort(int a[], int n) {  // poke card
    for (int i = 1, j; i < n; ++i) {
        int tmp = a[i];
        for (j = i; j > 0 && a[j - 1] > tmp; --j) a[j] = a[j - 1];
        a[j] = tmp;
    }
}

选择排序

void SelectSort(int a[], int n) {
    for (int i = 0; i < n; ++i) {
        int minpos = i, minvalue = a[i];
        for (int j = i; j < n; ++j)  // Find the min element in unorder part
            if (minvalue > a[j]) minpos = j, minvalue = a[j];
        swap(a[i], a[minpos]);
    }
}

归并排序

void Merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1, n2 = right - mid;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j])
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}
void MergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        MergeSort(arr, l, m);
        MergeSort(arr, m + 1, r);
        Merge(arr, l, m, r);
    }
}

堆排序

void MaxHeapify(int a[], int start, int end) {
    int dad = start, son = dad * 2 + 1;
    while (son <= end) {
        if (son + 1 <= end && a[son] < a[son + 1]) ++son;
        if (a[dad] > a[son])
            return;
        else
            swap(a[dad], a[son]), dad = son, son = dad * 2 + 1;
    }
}
void HeapSort(int a[], int len) {
    for (int i = len / 2 - 1; i >= 0; --i) MaxHeapify(a, i, len - 1);
    for (int i = len - 1; i > 0; --i) swap(a[0], a[i]), MaxHeapify(a, 0, i - 1);
}

快速排序

void QuickSort(int s[], int l, int r) {
    if (l < r) {
        int i = l, j = r, x = s[l];
        while (i < j) {
            while (i < j && s[j] >= x) j--;  // 从右向左找第一个小于x的数
            if (i < j) s[i++] = s[j];
            while (i < j && s[i] < x) i++;  // 从左向右找第一个大于等于x的数
            if (i < j) s[j--] = s[i];
        }
        s[i] = x;
        QuickSort(s, l, i - 1);  // 递归调用
        QuickSort(s, i + 1, r);
    }
}

求二叉树深度

int getHeight(BinTreeNode *t){
    if(t=NULL)return 0;
    int L=getHeight(t->LChild);
    int R=getHeight(t->RChild);
    if(L>R)return L+1;
    else return R+1;
}

求二叉排序树最大关键字

int GetMaxNode(BinTreeNode *t){
    while(t->RChlid!=NULL)t=t->RChild;
    return t->data;
}