数据结构题

Author： MixZou
发布时间：September 19, 2021
1139views
No comments
3477 words
Categories：笔记学习

数据结构习题

未整理，只是记录问题

需要重看的部分：快速排序，直接插入排序，哈夫曼树构造，图，堆排序

选择填空知识点

数据结构有三方面的内容：数据运算，存储结构，逻辑结构
算法的五个特点：有穷性、确定性、可行性、0个或多个输入、一个或多个输出

线性表

栈是抽象数据类型，只表示逻辑结构
共享栈是两个栈共用一块存储空间，节省存储空间以外，栈的插入删除都在栈顶，只可能发生上溢，所以共享栈可以降低发生上溢的可能
线性表既可以用顺序存储方式实现又可以用链式存储实现
$O(1)<O(log_2n)<O(n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$
线性表（逻辑结构）定义：相同数据类型的有限序列
存取方式指读写方式，顺序表支持随机存取
顺序表和链表是根据线性表的存储结构来划分概念，而有序表只描述元素之间的逻辑关系
执行图的广度优先遍历需要使用队列作为辅助存储空间
有序单链表上做顺序查找，查找成功的平均查找长度与在无序顺序表或有序顺序表上做顺序查找的平均查找长度相同，都是$(n+1) / 2$
选择排序算法的比较次数始终为$n(n-1)/2$，与序列状态无关
对n阶对称矩阵压缩存储时，需要表长为$n^2+1$的顺序表
N阶三角矩阵存储的元素个数为n(n+1)/2

查找

折半查找过程所对应的判定树是一棵平衡二叉树
散列表查找中，评判一个散列函数优劣的两个主要条件是：值均匀分布于表空间以减少冲突；函数尽可能简单以方便计算
在hash查找方法中，要解决的两个问题是：构造散列函数；处理冲突

树

二叉树转化为森林的方法：从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树，若其根节点的右孩子存在，则连线删除…直到所有这些根节点与右孩子的连线都删除为止
先序序列为a，b，c，d的不同二叉树的个数为$\frac{1}{n+1}C_{2n}^{n}$这里n=4
一棵二叉树中，度为2的结点个数是$n^2$
满二叉树结点数$n^2-1$
$N_0=N_2+1$
一棵完全二叉树从0开始节点的编号，并按此顺序存储到一位数组A中，A[i]元素的左孩子元素为A[2i+1]，右孩子为A[2i+2]，双亲元素为A[(i-1)/2(向下取整)]

图

执行图的广度优先遍历需要使用队列作为辅助存储空间
具有n个顶点的无向图至少有$(n-1)(n-2)/2+1$条边才能确保是一个连通图，最少是$n-1$条
一个有x条边的非连通无向图至少有n个顶点，满足$n(n-1)=x$
一个图的生成树是一个极小连通子图，无环
一个图的极大联通子图称为连通分量
邻接表存储空间，顶点n，每一条边储存2次，一共n+2e；邻接矩阵只和顶点数有关
关键路径上的活动称为关键活动，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径
无向图若任意两顶点之间都存在边，则称该图为完全无向图，有n个顶点，有n（n-1）/2条边
有向图，若任意两顶点之间都存在方向相反的两条弧，则称为有向完全图，n个顶点，n（n-1）条有向边
n个顶点构成的图，强连通分量最多有n(n-1)条边，最少有n条边

排序

时间复杂度不受数据初始状态影响而恒定为$O(nlog_2n)$的是归并排序
直接插入排序，最好、最坏、平均查找时间为：$O(n)$、$O(n^2)$、$O(n^2)$
希尔排序不稳定，在插入步长不为1时，有可能把相等元素前后顺序弄乱
对排序，对任意分支结点进行筛运算的时间复杂度为$O(log_2n)$，整个对排序$O(nlog_2n)$

代码题

线性表

顺序表删除唯一最小值并由最后一个元素补空

bool Del_Min(SqList &L, ElemType &value){
    if(L.length==0)
        return false;
    value = L.data[0];
    int position = 0;
    for(int i=1;i<L.length;i++){
        if(L.data[i]<value){
            value = L.data[i];
            positon = i;
        }
    }
    L.data[postiton] = L.data[L.length-1];
    L.length--;
    return true;
}

空间复杂度O(1)，将顺序表元素逆置

void Reverse(SqList &L){
    ElemType temp;
    for(int i=0; i<L.length/2; i++){
        temp = L.data[i];
        L.data[i] = L.data[L.length-i-1];
        L.data[L.length-i-1] = temp;
    }
}

长度为n顺序表L，时间复杂度O(n)、空间复杂度O(1)。删除所有值为x的元素

void DelX(SqList &L, ElemType x){
    int k = 0;
    for(int i=0; i<L.length; i++){
        if(L.data[i]!=x){
            L.data[k] = L.data[i];
            k++;
        }
    }
    L.length = k;
}

有序表删除给定值s与t之间所有元素，要求s<t

bool DelRange(SqList &L, ElemType s ElmeType t){
    int i, j;
    if(L.length==0 || s>=t)
        return false;
    for(i=0; i<L.length && L.data[i]<s; i++);
    if(i>L.length)
        return false;
    for(j=i; j<L.length && L.data[j]>t; j++);
    for(j<L.length; i++; j++)
        L.data[i] = L.data[j];
    L.length = i;
    return true;
}

顺序表删除在定值s到t之间的所有值，包含s和t，要求s<t

bool DelRange(SqList &L, ElemType s ElmeType t){
    int i,k=0;
    if(L.length==0 || s>=t)
        return false;
    for(i=0; i<L.length; i++){
        if(L.data[i]>=s && L.data[i]<=t)
            k++;
        else
            L.data[i-k] = L.data[i];
    }
    L.length -= k;
    return true;
}

有序表删除所有值重复的元素

bool Delete_Same(SeqList &L){
    if(L.length==0)
        return false;
    int i,j;
    for(i=0, j=1; j<L.length; j++)
        if(L.data[i]!=L.data[j])
            L.data[++i] = L.data[j];
    L.length = i+1;
    return true;
}
//因为有序表相同值的数一定在连续位置上

将两个有序表合并成新的有序顺序表

bool Merge(SeqList A, SeqList B, SeqList &C){
    if(A.length+B.length > C.maxSize)
        return false;
    int i=0, j=0, k=0;
    while(i<A.length && j<B.length){
        if(A.data[i]≤B.data[j])
            C.data[k++] = A.data[i++];
        else
            C.data[K++] = B.data[j++];
    }
    while(i<A.length)
        C.data[k++] = A.data[i++];
    while(j<B.length)
        C.data[k++] = B.data[j++];
    C.length=k;
    return true;
}

线性表元素递增且有序按顺序存储，寻找数值为x的元素，找到后与后继元素交换位置，若找不到将其插入表中，使表中元素仍递增有序

void SearchExchangeInsert(ElemType A[], ElemType x, ElemType temp){
    int low=0, high=n-1, mid;
    while(low<=high){
        mid = (low+high)/2;
        if(A[mid]==x)
            break;
        else if(A[mid]<x)
            low = mid + 1;
        else
            high = mid - 1;
    }
    if(A[mid]==x && mid!=n-1){
        temp = A[mid];
        A[mid] = A[mid+1];
        A[mid+1] = temp;
    }
    if(low>high){
        for(int i=n-1; i>high; i--)
            A[i+1] = A[i];
        A[i+1] = x;
    }
}

已知一维数组[m+n]中依次存放两个线性表，将数组中两个线性表位置互换

typedef int DataType;

void Reverse(DataType A[], int left, int right, int arraySize){
    //逆置
    if(left>=right || right>=arraySize)
        return;
    int mid = (left+right)/2;
    for(int i=0; i<=mid-left; i++){
        DataType temp = A[left+i];
        A[left+i] = A[right-i];
        A[right-i] = temp;
    }
}

void Exchange(DataType A[], int m, int n, int arraySize){
    /*
    数组A[m+n]中，从0到m-1存放顺序表a1，a2.。。am，从m到m+n+-1存放顺序表b1.。。bn，将这两个表的位置互换
    */
    Reverse(A, 0, m+n-1, arraySize);
    Reverse(A, 0, n-1, arraySize);
    Reverse(A, n, m+n-1, arraySize);
}

将n(n>1)个整数存放到一维数组R中，设计一个在空间时间尽可能高效的算法，将R中保存的序列循环左移p个位置0<p<n

/*
基本思路：将一个数组按p分成a、b两个数组；a是前p个元素，b是余下n-p个，先后将a、b逆置，再将整个数组逆置
*/
void Reverse(int R[], int from, int to){
    int i, temp;
    for(i=0; i<(to-from+1)/2; i++){        //在一半的时候就可以对应逆置
        temp = R[from+i];
        R[from+i] = R[to-i];
        R[to-i] = temp;
    }
}

void Converse(int R[], int n, int p){
    Reverse(R, 0, p-1);                    //O(p/2)
    Reverse(R, p, n-1);                    //O((n-p)/2)
    Reverse(R, 0, n-1);                    //O(n-1)
}

/*
另解：借助辅助数组思想：创建大小为p的辅助数组S，将R中前p个整数依次暂存在S中，同时将R中后n-p个整数左移，然后将S中暂存的p个数依次放回R中的后续单元。时间复杂度O(n),空间复杂度O(p)
*/

一个长度为L(L≥1)的升序序列S，S1和S2的中位数是11，现在两个等长升序序列A和B，找出它们的中位数

/*
思路；设A、B中位数分别为a、b；若a=b，即为所求中位数；a<b，舍弃A中较小的一半，B中较大的一半，要求舍弃长度相等；a>b，舍弃A中较大的一半，B中较小的一半，要求舍弃长度相等；在保留的两个升序序列中，重复以上三个步骤，直到两个序列中均只剩下一个元素为止，较小的为中位数；O(log_2 n)，空间复杂度O(1)
*/

int M_Search(int A[], int B[], int n){
    int s1=0, d1=n-1, m1, s2=0, d2=n-1, m2;        //首位数、末位数、中位数
    while(s1!=d1 || s2!=d2){
        m1 = (s1+d1)/2;
        m2 = (s2+d1)/2;
        if(A[m1] == B[m2])
            return A[m1];
        if(A[m1]<B[m2]){
            if((s1+d1)%2==0){
                s1 = m1;
                d2 = m2;
            }
            else{
                s1 = m1 + 1;
                d2 = m2;
            }
        }
        else{
            if((s1+d1)%2==0){
                d1 = m1;
                s2 = m2;
            }
            else{
                d1 = m1 + 1;
                s2 = m2;
            }
        }
    }
    return A[s1]<B[s2]?A[S1]:B[s2];
}

已知整数序列$A=(a_0,a_1,...,a_{n-1})，其中0≤a_i<n(0≤i<n)。若存在a_{p1}=a_{p2}=...a_{pm}=x，且m>n/2(0≤p_k<n,1≤k≤m),则称x为A的主元素。$假设A中的n个元素保存在一维数组中，找出A的主元素并输出

int Majority(int A[], int n){
    int i, c, count=1;
    c = A[0];                //c保存候选主元素
    for(i=0; i<n; i++){
        if(A[i] == c)
            count++;
        else{
            if(count>0)
                count--;
            else{            //更换候选主元素，重新技术
                c = A[i];
                count = 1;
            }
        }      
    }
    if(count>0){            //统计候选元素实际出现次数
        for(i=count=0; i<n; i++){
            if(A[i]==c)
                count++;
        }
    }
    if(count>n/2)
        return c;
    else
        return -1;
}

/*
思路：选取候选的主元素；依次扫描所给数组每一个整数，将第一个遇到的整数保存到c中，记录次数1；若遇到下一个整数仍为它则计数加1，否则减1；当计数等于0时，将遇到的下一个整数保存到c中，重新计数为1；重复，直到扫描完整个数组元素。
判断c中元素是否为真正的主元素，再次扫描整个数组，统计c出现次数，若大于n/2，则为主元素。
*/

给定n(n>1)个整数的数组，找出数组中未出现的最小正整数，例如数组{-5,3,2,3}中未出现的最小正整数是1

int findMissMin(int A[], int n){
    int i, *B;
    B = (int *)malloc(sizeof(int)*n);    //B为标记数组
    memset(B, 0, sizeof(int)*n);        //初始化赋值为0
    for(i=0; i<n; i++){
        if(A[i]>0 && A[i]<=n)            //小于等于n的数出现，标记在B中
            B[A[i]-1] = 1;
    }
    for(i=0; i<n; i++)                    //寻找第一个未被标记的
        if(B[i]==0)
            break;
    return i+1;
}

/*
要求时间高效则采用空间换时间的办法。数组B记录A中是否出现了1～n中的正整数，B[0]对应正整数1，B[n-1]对应正整数n，初始化B数组元素全部为0.由于A中含有n个整数，因此可能返回的值在1～n+1，当A中n个数恰好为1～n时，返回n+1；
当A中出现小于0或大于n的数时，导致1～n中出现空位，返回的结果必然在1～n，所以，当A中出现前面所述的值时，不采取任何操作；
空间复杂度n，时间复杂度n
*/

定义三元组abc，均为正数。它们的距离D=｜a-b｜+｜b-c｜+｜c-a｜。给定3个非空整数集合，安升序分别存在3个数组中，计算并输出所有可能的三元组中的最小距离

#define INT_MAX 0x7fffffff
/*
F的二进制码为 1111
7的二进制码为 0111
这样一来，整个整数 0x7FFFFFFF 的二进制表示就是除了首位是 0，其余都是1
就是说，这是最大的整型数 int（因为第一位是符号位，0 表示他是正数）
*/

//获取绝对值
int abs_(int){
    if(a<0)
        return -a;
    else
        return a;
}

//判断是否三者最小
bool xls_min(int a, int b, int c){
    if(a<=b && a<=c)
        return true;
    return false;
}

int findMinofTrip(int A[], int n, int B[], int m, int C[], int p){
    //D_min用于记录三元组的最小距离，初值赋为INT_MAX
    int i=0, j=0, k=0, D_min=INT_MAX, D;
    while(i<n && j<m && k<p && D_min>0){
        D = abs_(A[i]-B[j])+abs_(B[j]-C[k])+abs_(C[k]-A[i]);
        if(D<D_min)
            D_min = D;
        if(xls_min(A[i],B[j],C[k]))
            i++;
        else if(xls_min(B[j],C[k]),A[i])
            j++;
        else
            k++;
    }
    return D_min;
}

不带头结点，递归

void delete_x(LinkList &L, DataType x){
    LNode *p;    //指向待删除结点
    if(L==NULL)
        return;
    if(L->data==x){
        p=L;
        L=L->next;
        free(p);
        delete_x(L,x);
    }
    else
        delete_x(L->next,x);
}

带头结点单链表L中，删除所有值为x的结点，并释放空间，x不唯一

链表

递增有序链表二合一，不允许重复数据，在原空间

void MergeList(LinkList &La, LinkList &Lb){
    LNode *r, *pa = La->next, pb = Lb->next;
    La->next = NULL;
    
    while (pa && pb){
        if(pa-data <= pb->data){
            r = pa->next;
            pa-next = La-next;
            La-next = pa;
            pa = r;
        }
        else{
            r = pb->next;
            pb-next = Lb-next;
            La-next = pb;
            pb = r;
        }
        
        if(pa){
            pb = pa;
        }
        while(pb){
            r = pb-next;
            pb-next = La-next;
            La->next = pb;
            pb = r;
        }
        free(Lb);
    }
    
}

单链表带头节点，递增次序输出链表中的数据元素，并释放节点的空间

void Min_Delete(LinkList head){
    LinkNode *pre_min, *pre;
    LinkNode *r;
    while(head->next){
        pre_min = head;
        pre = head->next;
        while(pre->next){
            if(pre->next->data > pre_min->next->data)
                pre_min = pre;
        }
        printf("%d\n", pre_min->data);
        r = pre_min->next;
        pre_min->next = pre_min->next->next;
        free(r);
    }
    free(head);
}

带头节点单链表，元素无序排列，写出单链表带类型定义及相应函数，删除表中所有大于Min小于Max的元素

void Delete_min_to_max(LinkList L, ElemType min_value, ElemType max_value){
    LNode *p = L;
    LNode *q;
    while(p->next!=NULL){
        if(p->next->data > min_value && p->next-data<value){
            q = p->next;
            p->next = p->next->next;
            free(q);
        }
        p = p->next;
    }
}

求新链表集合C=A-B，然后释放A，B多余的结点

LinkList A_sub_B(LinkList A, LinkList B){
    LinkList pa = A;
    while(pa->next != NULL){
        bool flag = false;    //标记pa的后一个元素是否被删除
        LinkList pb = B;
        while(pb->next != NULL){    //删除A中A、B共有元素
            if(pb->next->data == pa->next->data){
                LinkList q;
                q = pa->next;
                pa->next = pa->next->next;
                flag = true;
                free(q);
            }
            pb = pb-next;  
        }
        if(!flag)
            pa = pa->next;
    }
    return A;
}

排序

双向冒泡排序，在正反方向交替进行扫描，第一趟把关键字最大的元素放在序列的最后面，第二趟把关键字最小的元素放在序列最前，如此反复

void BubbleSort(ElemType A[], int n){
    //交替进行正反向排序
    int low = 0, high = n-1;
    bool flag = true;            //一趟冒泡后记录是否交换
    while(low<high && flag){    //循环跳出条件，当flag为false说明无逆序
        flag = false;
        for(i=low;i<high;i++)    //从前向后起泡
            if(a[i]>a[i+1]){
                swap(a[i],a[i+1]);
                flag = true;
            }
        high--;
        for(i=high;i>low;i--)
            if(a[i]<a[a-1]){
                swap(a[i], a[i-1]);
                flag = false;
            }
        low++;
    }
}

线性表按顺序存储，每个元素不相同的整数型，设计把所有奇数移动到偶数前面的算法

void move(ElemType A[], int len){
    //按奇偶进行一趟划分
    int i =0, j = len-1;
    while(i < j){
        while(i < j && A[i]%2 != 0)        //从前向后找到第一个偶数
            i++;
        while(i < j && A[j]%2 != 1)        //从后向前找到第一个奇数
            j++;
        if(i<j)
            swap(A[i], A[j]);
        i++;
        j--;
    }
}

快排，每次选取的枢轴都是随机从当前子表中选择

int Partition2(ElemType A[], int low, int high){
    int rand_Index = low + rand()%(high-low+1);
    swap(A[rand_Index],A[low]);
    ElemType pivot = A[low];
    int i = low;
    for(int j=low+1; j<=high; j++)
        if(A[j]<pivot)
            swap(A[++i],A[j]);
    swap(A[i],A[low]);
    return i;
}

编写算法，在数组L[1..n]中找出第k小的元素，即从小到大排序后处于第k个位置的元素

int kth_elem(int a[], int low, int high, int k){
    int pivot = a[low];
    int low_temp = low;
    int high_temp = high;
    while(low<high){
        while(low<high && a[high]>=pivot)
            --high;
        a[low] = a[high];
        while(low<high && a[high]<=pivot)
            ++low;
        a[high] = a[low];
    }
    a[low] = pivot;
    // 划分
    //本题
    if(low==k)
        return a[low];
    else if(low>k)
        return kth_elem(a, low_temp, low-1, k);
    else
        return kth_elem(a, low+1, high_temp, k);
    
}

设有一个仅由红白蓝三色的条块组成的条块序列，请编写一个时间复杂度为O（n）的算法，使这些条块按红白蓝顺序排好

typedef enum{RED, WHITE, BLUE} color;    //设置枚举数组

void Flag_Arrange(color a[], int n){
    int i=0, j=0, k=n-1;
    while(j<=k)
        switch(a[j]){
            case RED: swap(a[i],a[j]);i++;j++;break;
            case WHITE: j++;break;
            case BLUE: swap(a[j],a[k]);k--;
            //蓝色，则和k交换；这里没有j++语句以防止交换后a[j]仍为蓝色的情况
        }
}

/**
顺序扫描线性表，将红色条块交换到线性表的最前面
**/

树

判断二叉树是否平衡

void Judge_AVL(BiTree bt, int &balance, int &h){
    int bl = 0, br = 0, hl = 0, hr = 0;
    if(bt==NULL){
        h = 0;
        balance = 1;
    }
    else if(bt->lchild==NULL && bt->rchild == NULL){
        h = 1;
        balance = 1;
    }
    else{
        Judge_AVL(bt->lchild, bl, hl);
        Judge_AVL(bt->rchild, br, hr);
        h=(hl>hr?hl:hr)+1;
        if(abs(hl-hr) < 2)
            balance = bl&&br;
        else
            balance = 0;
    }
}

设计算法将二叉树叶节点从左往右顺序连成单链表，表头指针为head，二叉树安二叉链表的方式存储，链接时用右节点的右指针域来存放单链表指针

LinkedList head;
LinkNode *pre = NULL;
LinkedList InOrder(BiTree bt){
    if(bt){
        InOrder(bt->lchild);
        if(bt->lchild==NULL && bt->rchild==NULL)
            head->next = bt;
        else
            pre-right = bt;
        pre = bt;
    }
    InOder(bt->rchild);
    if(pre)
        pre->rchild=NULL;    //tail of linklist
    return head;
}

二叉链表作为二叉树的有序存储表示，递归交换每一个节点的左右子节点，写出二叉树的类型定义及相应函数

typedef struct BiTNode{
    ElemType data;
    BiTNode *lchild;
    BiTNode *rchild;
}*BiTree, BiTNode;

void Exchange(BitTree t){
    if(t==NULL){
        return;
    }
    Exchange(t->lchild);
    Exchange(t->rchild);
    
    BiTNode *temp = t->lchild;
    t->lchild = t->rchild;
    t->rchild = temp;
}

图

判断一个无向图是否为一棵树，是则返回true

/**
一个无向图G是一棵树的条件是，G必须是无回路的连通图或有n-1条边的连通图
**/
bool isTree(Granph &G){
    for(i=1; i<=G.vexnum; i++){
        visited[i] = FALSE;
    }
    int Vnum = 0, Enum = 0;
    DFS(G, 1, Vnum, Enum, visited);
    if(Vnum==G.vexnum && Enum==2*(G.vexnum-1))
        return true;
    else
        return false;
}

void DFS(Graph &G, int v, &Vnum, int &Enum, int visited[]){
    //深度优先遍历，统计访问过的顶点数和边数
    visited[v] = TRUE;Vnum++;
    int w = FirstNeighbor(G,v);
    while(w!=-1){
        Enum++;
        if(!visited[w])
            DFS(G, w, Vnum, Enum, visited);
        w = NextNeighbor(G,v,w);
    }
    
}

图的DFS非递归算法，采用邻接表形式

void DFS_Non_RC(AGraph &G, int v){
    int w;            //顶点序号
    InitStack(S);    //初始化栈
    for(i=0; i<G,vexnum; i++)
        visited[i] = FALSE;        //初始化visited
    Push(S,v);                    //v入栈
    visited[v] = TRUE;
    while(!IsEmpty(S)){
        k = Pop(S);                //栈中推出一个顶点
        visit(k);                //先访问再将其子节点入栈
        for(w=FirstNeighbor(G,k); w>=0; w=NextNeighbor(G,k,w)){
            if(!visited[w]){
                Push(S,w);
                visited[w] = true;
            }
        }
    }
}
//由于使用了栈，遍历方式是从右到左，不同于常规左到右，仍然是深度优先遍历

分别采用基于BFS和DFS判别以邻接表方式存储的有向图中是否存在顶点vi到顶点vj到路径i≠j

int visted[MAXSIZE] = {0};
void DFS(AlGraph G, int i, int j, bool &can_reach){
    if(i==j){
        can_reach = true;
        return;                //i就是j
    }
    visited[i] = 1;
    for(int p = FirstNeighbor(G,i); p>=0; p=NextNeighbor(G,i,p))
        if(!visited[p]&&!can_reach)
            DFS(G,p,j,can_reach);
}

int BFS(AlGraph G, int i, int j){
    InitQueue(Q);
    EnQueue(i);
    while(!isEmpty(Q)){
        DeQueue(Q);
        visited[u] = 1;
        if(u==j)
            return 1;
        for(int p=FirstNeighbor(G,i); p; P=NextNeighbor(G,u,p)){
            if(p==j)
                return 1;
            if(!visited[p]){
                EnQueue(Q,p);
                visited[p] = 1;
            }
        }
    }
}

图以邻接表表示，输出从顶点vi到vj的所有简单路径

void FindPath(AGraph *G, int u, int v, int path[], intd){
    int w,i;
    ArcNode *p;
    d++;
    path[d] = u;
    visited[u] = 1;        //已访问
    if(u==v)
        print(path[]);
    p=G->adjlist[u].firstarc;    //p指向u到第一个相邻点
    while(!p=NULL){
        w=p->adjvex;    //若w未访问，递归访问他
        if(visited[w]==0)
            FindPath(G, w, V, path, d);
        p = p->nextarc;
    }
    visited[u] = 0;
}

BFS求解单源最短路径

void BFS_MIN_Distance(Graph G, int u){
    //d[i]:the distance from u to i
    for(int i=0; i<G.vexnum; ++i)
        d[i] = 9999;
    visited[u] = true;
    d[u] = 0;
    EnQueue(Q, u);
    while(!isEmpty(Q)){
        //BFS
        DeQueue(Q,u);    //head u out
        for(w=FirstNeighbor(G,u); w>=0; w=NextNeighbor(G,u)){
            if(!visited[w]){
                visited[w] = true;
                d[w] = d[u]+1;
                EnQueue(Q,w);
            }
        }
    }
}

狄杰斯特拉算法，Dijkstra，单源点最短路径

//Min is the shortest distance from start to others
bool closed[N] = {FALSE};    //initial closed
int Min[N] = {INF};
closed[start] = true;
Min[start] = 0;
for(int i=1; i<N; ++i){        //将剩余的N-1个顶点距离start的最短距离算出
    int k = -1;        //存放每轮循环距离离start最近的点
    for(int j=1; j<N; ++j){
        if(!closed[j] && (k==-1 || Min[k]>Min[j]))
            k = j;
    }
    closed[k] = true;
    for(int j=0; j<N; ++j){        //更新未求得最短路径的结点到start的最短距离
        if(!visited[j]){
            if(Min[j]>Min[k]+G[k][j])
                Min[j] = Min[k]+G[k][j];
        }
    }
}

Last modification：March 4th, 2022 at 10:22 pm

如果觉得我的文章对你有用，请随意赞赏

END

本文作者： MixZou
文章标题：数据结构题
本文地址：http://feiqiuz.com/index.php/archives/14/
版权说明：若无注明，本文皆MixZou的小窝原创，转载请保留文章出处。

数据结构题

MixZou • 2021 年 09 月 19 日

数据结构习题

未整理，只是记录问题

需要重看的部分：快速排序，直接插入排序，哈夫曼树构造，图，堆排序

选择填空知识点

数据结构有三方面的内容：数据运算，存储结构，逻辑结构
算法的五个特点：有穷性、确定性、可行性、0个或多个输入、一个或多个输出

线性表

栈是抽象数据类型，只表示逻辑结构
共享栈是两个栈共用一块存储空间，节省存储空间以外，栈的插入删除都在栈顶，只可能发生上溢，所以共享栈可以降低发生上溢的可能
线性表既可以用顺序存储方式实现又可以用链式存储实现
$O(1)<O(log_2n)<O(n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$
线性表（逻辑结构）定义：相同数据类型的有限序列
存取方式指读写方式，顺序表支持随机存取
顺序表和链表是根据线性表的存储结构来划分概念，而有序表只描述元素之间的逻辑关系
执行图的广度优先遍历需要使用队列作为辅助存储空间
有序单链表上做顺序查找，查找成功的平均查找长度与在无序顺序表或有序顺序表上做顺序查找的平均查找长度相同，都是$(n+1) / 2$
选择排序算法的比较次数始终为$n(n-1)/2$，与序列状态无关
对n阶对称矩阵压缩存储时，需要表长为$n^2+1$的顺序表
N阶三角矩阵存储的元素个数为n(n+1)/2

查找

折半查找过程所对应的判定树是一棵平衡二叉树
散列表查找中，评判一个散列函数优劣的两个主要条件是：值均匀分布于表空间以减少冲突；函数尽可能简单以方便计算
在hash查找方法中，要解决的两个问题是：构造散列函数；处理冲突

树

二叉树转化为森林的方法：从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树，若其根节点的右孩子存在，则连线删除…直到所有这些根节点与右孩子的连线都删除为止
先序序列为a，b，c，d的不同二叉树的个数为$\frac{1}{n+1}C_{2n}^{n}$这里n=4
一棵二叉树中，度为2的结点个数是$n^2$
满二叉树结点数$n^2-1$
$N_0=N_2+1$
一棵完全二叉树从0开始节点的编号，并按此顺序存储到一位数组A中，A[i]元素的左孩子元素为A[2i+1]，右孩子为A[2i+2]，双亲元素为A[(i-1)/2(向下取整)]

图

执行图的广度优先遍历需要使用队列作为辅助存储空间
具有n个顶点的无向图至少有$(n-1)(n-2)/2+1$条边才能确保是一个连通图，最少是$n-1$条
一个有x条边的非连通无向图至少有n个顶点，满足$n(n-1)=x$
一个图的生成树是一个极小连通子图，无环
一个图的极大联通子图称为连通分量
邻接表存储空间，顶点n，每一条边储存2次，一共n+2e；邻接矩阵只和顶点数有关
关键路径上的活动称为关键活动，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径
无向图若任意两顶点之间都存在边，则称该图为完全无向图，有n个顶点，有n（n-1）/2条边
有向图，若任意两顶点之间都存在方向相反的两条弧，则称为有向完全图，n个顶点，n（n-1）条有向边
n个顶点构成的图，强连通分量最多有n(n-1)条边，最少有n条边

排序

时间复杂度不受数据初始状态影响而恒定为$O(nlog_2n)$的是归并排序
直接插入排序，最好、最坏、平均查找时间为：$O(n)$、$O(n^2)$、$O(n^2)$
希尔排序不稳定，在插入步长不为1时，有可能把相等元素前后顺序弄乱
对排序，对任意分支结点进行筛运算的时间复杂度为$O(log_2n)$，整个对排序$O(nlog_2n)$

代码题

线性表

顺序表删除唯一最小值并由最后一个元素补空

bool Del_Min(SqList &L, ElemType &value){
    if(L.length==0)
        return false;
    value = L.data[0];
    int position = 0;
    for(int i=1;i<L.length;i++){
        if(L.data[i]<value){
            value = L.data[i];
            positon = i;
        }
    }
    L.data[postiton] = L.data[L.length-1];
    L.length--;
    return true;
}

空间复杂度O(1)，将顺序表元素逆置

void Reverse(SqList &L){
    ElemType temp;
    for(int i=0; i<L.length/2; i++){
        temp = L.data[i];
        L.data[i] = L.data[L.length-i-1];
        L.data[L.length-i-1] = temp;
    }
}

长度为n顺序表L，时间复杂度O(n)、空间复杂度O(1)。删除所有值为x的元素

void DelX(SqList &L, ElemType x){
    int k = 0;
    for(int i=0; i<L.length; i++){
        if(L.data[i]!=x){
            L.data[k] = L.data[i];
            k++;
        }
    }
    L.length = k;
}

有序表删除给定值s与t之间所有元素，要求s<t

bool DelRange(SqList &L, ElemType s ElmeType t){
    int i, j;
    if(L.length==0 || s>=t)
        return false;
    for(i=0; i<L.length && L.data[i]<s; i++);
    if(i>L.length)
        return false;
    for(j=i; j<L.length && L.data[j]>t; j++);
    for(j<L.length; i++; j++)
        L.data[i] = L.data[j];
    L.length = i;
    return true;
}

顺序表删除在定值s到t之间的所有值，包含s和t，要求s<t

bool DelRange(SqList &L, ElemType s ElmeType t){
    int i,k=0;
    if(L.length==0 || s>=t)
        return false;
    for(i=0; i<L.length; i++){
        if(L.data[i]>=s && L.data[i]<=t)
            k++;
        else
            L.data[i-k] = L.data[i];
    }
    L.length -= k;
    return true;
}

有序表删除所有值重复的元素

bool Delete_Same(SeqList &L){
    if(L.length==0)
        return false;
    int i,j;
    for(i=0, j=1; j<L.length; j++)
        if(L.data[i]!=L.data[j])
            L.data[++i] = L.data[j];
    L.length = i+1;
    return true;
}
//因为有序表相同值的数一定在连续位置上

将两个有序表合并成新的有序顺序表

bool Merge(SeqList A, SeqList B, SeqList &C){
    if(A.length+B.length > C.maxSize)
        return false;
    int i=0, j=0, k=0;
    while(i<A.length && j<B.length){
        if(A.data[i]≤B.data[j])
            C.data[k++] = A.data[i++];
        else
            C.data[K++] = B.data[j++];
    }
    while(i<A.length)
        C.data[k++] = A.data[i++];
    while(j<B.length)
        C.data[k++] = B.data[j++];
    C.length=k;
    return true;
}

线性表元素递增且有序按顺序存储，寻找数值为x的元素，找到后与后继元素交换位置，若找不到将其插入表中，使表中元素仍递增有序

void SearchExchangeInsert(ElemType A[], ElemType x, ElemType temp){
    int low=0, high=n-1, mid;
    while(low<=high){
        mid = (low+high)/2;
        if(A[mid]==x)
            break;
        else if(A[mid]<x)
            low = mid + 1;
        else
            high = mid - 1;
    }
    if(A[mid]==x && mid!=n-1){
        temp = A[mid];
        A[mid] = A[mid+1];
        A[mid+1] = temp;
    }
    if(low>high){
        for(int i=n-1; i>high; i--)
            A[i+1] = A[i];
        A[i+1] = x;
    }
}

已知一维数组[m+n]中依次存放两个线性表，将数组中两个线性表位置互换

typedef int DataType;

void Reverse(DataType A[], int left, int right, int arraySize){
    //逆置
    if(left>=right || right>=arraySize)
        return;
    int mid = (left+right)/2;
    for(int i=0; i<=mid-left; i++){
        DataType temp = A[left+i];
        A[left+i] = A[right-i];
        A[right-i] = temp;
    }
}

void Exchange(DataType A[], int m, int n, int arraySize){
    /*
    数组A[m+n]中，从0到m-1存放顺序表a1，a2.。。am，从m到m+n+-1存放顺序表b1.。。bn，将这两个表的位置互换
    */
    Reverse(A, 0, m+n-1, arraySize);
    Reverse(A, 0, n-1, arraySize);
    Reverse(A, n, m+n-1, arraySize);
}

将n(n>1)个整数存放到一维数组R中，设计一个在空间时间尽可能高效的算法，将R中保存的序列循环左移p个位置0<p<n

/*
基本思路：将一个数组按p分成a、b两个数组；a是前p个元素，b是余下n-p个，先后将a、b逆置，再将整个数组逆置
*/
void Reverse(int R[], int from, int to){
    int i, temp;
    for(i=0; i<(to-from+1)/2; i++){        //在一半的时候就可以对应逆置
        temp = R[from+i];
        R[from+i] = R[to-i];
        R[to-i] = temp;
    }
}

void Converse(int R[], int n, int p){
    Reverse(R, 0, p-1);                    //O(p/2)
    Reverse(R, p, n-1);                    //O((n-p)/2)
    Reverse(R, 0, n-1);                    //O(n-1)
}

/*
另解：借助辅助数组思想：创建大小为p的辅助数组S，将R中前p个整数依次暂存在S中，同时将R中后n-p个整数左移，然后将S中暂存的p个数依次放回R中的后续单元。时间复杂度O(n),空间复杂度O(p)
*/

一个长度为L(L≥1)的升序序列S，S1和S2的中位数是11，现在两个等长升序序列A和B，找出它们的中位数

/*
思路；设A、B中位数分别为a、b；若a=b，即为所求中位数；a<b，舍弃A中较小的一半，B中较大的一半，要求舍弃长度相等；a>b，舍弃A中较大的一半，B中较小的一半，要求舍弃长度相等；在保留的两个升序序列中，重复以上三个步骤，直到两个序列中均只剩下一个元素为止，较小的为中位数；O(log_2 n)，空间复杂度O(1)
*/

int M_Search(int A[], int B[], int n){
    int s1=0, d1=n-1, m1, s2=0, d2=n-1, m2;        //首位数、末位数、中位数
    while(s1!=d1 || s2!=d2){
        m1 = (s1+d1)/2;
        m2 = (s2+d1)/2;
        if(A[m1] == B[m2])
            return A[m1];
        if(A[m1]<B[m2]){
            if((s1+d1)%2==0){
                s1 = m1;
                d2 = m2;
            }
            else{
                s1 = m1 + 1;
                d2 = m2;
            }
        }
        else{
            if((s1+d1)%2==0){
                d1 = m1;
                s2 = m2;
            }
            else{
                d1 = m1 + 1;
                s2 = m2;
            }
        }
    }
    return A[s1]<B[s2]?A[S1]:B[s2];
}

int Majority(int A[], int n){
    int i, c, count=1;
    c = A[0];                //c保存候选主元素
    for(i=0; i<n; i++){
        if(A[i] == c)
            count++;
        else{
            if(count>0)
                count--;
            else{            //更换候选主元素，重新技术
                c = A[i];
                count = 1;
            }
        }      
    }
    if(count>0){            //统计候选元素实际出现次数
        for(i=count=0; i<n; i++){
            if(A[i]==c)
                count++;
        }
    }
    if(count>n/2)
        return c;
    else
        return -1;
}

/*
思路：选取候选的主元素；依次扫描所给数组每一个整数，将第一个遇到的整数保存到c中，记录次数1；若遇到下一个整数仍为它则计数加1，否则减1；当计数等于0时，将遇到的下一个整数保存到c中，重新计数为1；重复，直到扫描完整个数组元素。
判断c中元素是否为真正的主元素，再次扫描整个数组，统计c出现次数，若大于n/2，则为主元素。
*/

给定n(n>1)个整数的数组，找出数组中未出现的最小正整数，例如数组{-5,3,2,3}中未出现的最小正整数是1

int findMissMin(int A[], int n){
    int i, *B;
    B = (int *)malloc(sizeof(int)*n);    //B为标记数组
    memset(B, 0, sizeof(int)*n);        //初始化赋值为0
    for(i=0; i<n; i++){
        if(A[i]>0 && A[i]<=n)            //小于等于n的数出现，标记在B中
            B[A[i]-1] = 1;
    }
    for(i=0; i<n; i++)                    //寻找第一个未被标记的
        if(B[i]==0)
            break;
    return i+1;
}

/*
要求时间高效则采用空间换时间的办法。数组B记录A中是否出现了1～n中的正整数，B[0]对应正整数1，B[n-1]对应正整数n，初始化B数组元素全部为0.由于A中含有n个整数，因此可能返回的值在1～n+1，当A中n个数恰好为1～n时，返回n+1；
当A中出现小于0或大于n的数时，导致1～n中出现空位，返回的结果必然在1～n，所以，当A中出现前面所述的值时，不采取任何操作；
空间复杂度n，时间复杂度n
*/

#define INT_MAX 0x7fffffff
/*
F的二进制码为 1111
7的二进制码为 0111
这样一来，整个整数 0x7FFFFFFF 的二进制表示就是除了首位是 0，其余都是1
就是说，这是最大的整型数 int（因为第一位是符号位，0 表示他是正数）
*/

//获取绝对值
int abs_(int){
    if(a<0)
        return -a;
    else
        return a;
}

//判断是否三者最小
bool xls_min(int a, int b, int c){
    if(a<=b && a<=c)
        return true;
    return false;
}

int findMinofTrip(int A[], int n, int B[], int m, int C[], int p){
    //D_min用于记录三元组的最小距离，初值赋为INT_MAX
    int i=0, j=0, k=0, D_min=INT_MAX, D;
    while(i<n && j<m && k<p && D_min>0){
        D = abs_(A[i]-B[j])+abs_(B[j]-C[k])+abs_(C[k]-A[i]);
        if(D<D_min)
            D_min = D;
        if(xls_min(A[i],B[j],C[k]))
            i++;
        else if(xls_min(B[j],C[k]),A[i])
            j++;
        else
            k++;
    }
    return D_min;
}

不带头结点，递归

void delete_x(LinkList &L, DataType x){
    LNode *p;    //指向待删除结点
    if(L==NULL)
        return;
    if(L->data==x){
        p=L;
        L=L->next;
        free(p);
        delete_x(L,x);
    }
    else
        delete_x(L->next,x);
}

带头结点单链表L中，删除所有值为x的结点，并释放空间，x不唯一

链表

递增有序链表二合一，不允许重复数据，在原空间

void MergeList(LinkList &La, LinkList &Lb){
    LNode *r, *pa = La->next, pb = Lb->next;
    La->next = NULL;
    
    while (pa && pb){
        if(pa-data <= pb->data){
            r = pa->next;
            pa-next = La-next;
            La-next = pa;
            pa = r;
        }
        else{
            r = pb->next;
            pb-next = Lb-next;
            La-next = pb;
            pb = r;
        }
        
        if(pa){
            pb = pa;
        }
        while(pb){
            r = pb-next;
            pb-next = La-next;
            La->next = pb;
            pb = r;
        }
        free(Lb);
    }
    
}

单链表带头节点，递增次序输出链表中的数据元素，并释放节点的空间

void Min_Delete(LinkList head){
    LinkNode *pre_min, *pre;
    LinkNode *r;
    while(head->next){
        pre_min = head;
        pre = head->next;
        while(pre->next){
            if(pre->next->data > pre_min->next->data)
                pre_min = pre;
        }
        printf("%d\n", pre_min->data);
        r = pre_min->next;
        pre_min->next = pre_min->next->next;
        free(r);
    }
    free(head);
}

带头节点单链表，元素无序排列，写出单链表带类型定义及相应函数，删除表中所有大于Min小于Max的元素

void Delete_min_to_max(LinkList L, ElemType min_value, ElemType max_value){
    LNode *p = L;
    LNode *q;
    while(p->next!=NULL){
        if(p->next->data > min_value && p->next-data<value){
            q = p->next;
            p->next = p->next->next;
            free(q);
        }
        p = p->next;
    }
}

求新链表集合C=A-B，然后释放A，B多余的结点

LinkList A_sub_B(LinkList A, LinkList B){
    LinkList pa = A;
    while(pa->next != NULL){
        bool flag = false;    //标记pa的后一个元素是否被删除
        LinkList pb = B;
        while(pb->next != NULL){    //删除A中A、B共有元素
            if(pb->next->data == pa->next->data){
                LinkList q;
                q = pa->next;
                pa->next = pa->next->next;
                flag = true;
                free(q);
            }
            pb = pb-next;  
        }
        if(!flag)
            pa = pa->next;
    }
    return A;
}

排序

双向冒泡排序，在正反方向交替进行扫描，第一趟把关键字最大的元素放在序列的最后面，第二趟把关键字最小的元素放在序列最前，如此反复

void BubbleSort(ElemType A[], int n){
    //交替进行正反向排序
    int low = 0, high = n-1;
    bool flag = true;            //一趟冒泡后记录是否交换
    while(low<high && flag){    //循环跳出条件，当flag为false说明无逆序
        flag = false;
        for(i=low;i<high;i++)    //从前向后起泡
            if(a[i]>a[i+1]){
                swap(a[i],a[i+1]);
                flag = true;
            }
        high--;
        for(i=high;i>low;i--)
            if(a[i]<a[a-1]){
                swap(a[i], a[i-1]);
                flag = false;
            }
        low++;
    }
}

线性表按顺序存储，每个元素不相同的整数型，设计把所有奇数移动到偶数前面的算法

void move(ElemType A[], int len){
    //按奇偶进行一趟划分
    int i =0, j = len-1;
    while(i < j){
        while(i < j && A[i]%2 != 0)        //从前向后找到第一个偶数
            i++;
        while(i < j && A[j]%2 != 1)        //从后向前找到第一个奇数
            j++;
        if(i<j)
            swap(A[i], A[j]);
        i++;
        j--;
    }
}

快排，每次选取的枢轴都是随机从当前子表中选择

int Partition2(ElemType A[], int low, int high){
    int rand_Index = low + rand()%(high-low+1);
    swap(A[rand_Index],A[low]);
    ElemType pivot = A[low];
    int i = low;
    for(int j=low+1; j<=high; j++)
        if(A[j]<pivot)
            swap(A[++i],A[j]);
    swap(A[i],A[low]);
    return i;
}

编写算法，在数组L[1..n]中找出第k小的元素，即从小到大排序后处于第k个位置的元素

int kth_elem(int a[], int low, int high, int k){
    int pivot = a[low];
    int low_temp = low;
    int high_temp = high;
    while(low<high){
        while(low<high && a[high]>=pivot)
            --high;
        a[low] = a[high];
        while(low<high && a[high]<=pivot)
            ++low;
        a[high] = a[low];
    }
    a[low] = pivot;
    // 划分
    //本题
    if(low==k)
        return a[low];
    else if(low>k)
        return kth_elem(a, low_temp, low-1, k);
    else
        return kth_elem(a, low+1, high_temp, k);
    
}

设有一个仅由红白蓝三色的条块组成的条块序列，请编写一个时间复杂度为O（n）的算法，使这些条块按红白蓝顺序排好

typedef enum{RED, WHITE, BLUE} color;    //设置枚举数组

void Flag_Arrange(color a[], int n){
    int i=0, j=0, k=n-1;
    while(j<=k)
        switch(a[j]){
            case RED: swap(a[i],a[j]);i++;j++;break;
            case WHITE: j++;break;
            case BLUE: swap(a[j],a[k]);k--;
            //蓝色，则和k交换；这里没有j++语句以防止交换后a[j]仍为蓝色的情况
        }
}

/**
顺序扫描线性表，将红色条块交换到线性表的最前面
**/

树

判断二叉树是否平衡

void Judge_AVL(BiTree bt, int &balance, int &h){
    int bl = 0, br = 0, hl = 0, hr = 0;
    if(bt==NULL){
        h = 0;
        balance = 1;
    }
    else if(bt->lchild==NULL && bt->rchild == NULL){
        h = 1;
        balance = 1;
    }
    else{
        Judge_AVL(bt->lchild, bl, hl);
        Judge_AVL(bt->rchild, br, hr);
        h=(hl>hr?hl:hr)+1;
        if(abs(hl-hr) < 2)
            balance = bl&&br;
        else
            balance = 0;
    }
}

设计算法将二叉树叶节点从左往右顺序连成单链表，表头指针为head，二叉树安二叉链表的方式存储，链接时用右节点的右指针域来存放单链表指针

LinkedList head;
LinkNode *pre = NULL;
LinkedList InOrder(BiTree bt){
    if(bt){
        InOrder(bt->lchild);
        if(bt->lchild==NULL && bt->rchild==NULL)
            head->next = bt;
        else
            pre-right = bt;
        pre = bt;
    }
    InOder(bt->rchild);
    if(pre)
        pre->rchild=NULL;    //tail of linklist
    return head;
}

二叉链表作为二叉树的有序存储表示，递归交换每一个节点的左右子节点，写出二叉树的类型定义及相应函数

typedef struct BiTNode{
    ElemType data;
    BiTNode *lchild;
    BiTNode *rchild;
}*BiTree, BiTNode;

void Exchange(BitTree t){
    if(t==NULL){
        return;
    }
    Exchange(t->lchild);
    Exchange(t->rchild);
    
    BiTNode *temp = t->lchild;
    t->lchild = t->rchild;
    t->rchild = temp;
}

图

判断一个无向图是否为一棵树，是则返回true

/**
一个无向图G是一棵树的条件是，G必须是无回路的连通图或有n-1条边的连通图
**/
bool isTree(Granph &G){
    for(i=1; i<=G.vexnum; i++){
        visited[i] = FALSE;
    }
    int Vnum = 0, Enum = 0;
    DFS(G, 1, Vnum, Enum, visited);
    if(Vnum==G.vexnum && Enum==2*(G.vexnum-1))
        return true;
    else
        return false;
}

void DFS(Graph &G, int v, &Vnum, int &Enum, int visited[]){
    //深度优先遍历，统计访问过的顶点数和边数
    visited[v] = TRUE;Vnum++;
    int w = FirstNeighbor(G,v);
    while(w!=-1){
        Enum++;
        if(!visited[w])
            DFS(G, w, Vnum, Enum, visited);
        w = NextNeighbor(G,v,w);
    }
    
}

图的DFS非递归算法，采用邻接表形式

void DFS_Non_RC(AGraph &G, int v){
    int w;            //顶点序号
    InitStack(S);    //初始化栈
    for(i=0; i<G,vexnum; i++)
        visited[i] = FALSE;        //初始化visited
    Push(S,v);                    //v入栈
    visited[v] = TRUE;
    while(!IsEmpty(S)){
        k = Pop(S);                //栈中推出一个顶点
        visit(k);                //先访问再将其子节点入栈
        for(w=FirstNeighbor(G,k); w>=0; w=NextNeighbor(G,k,w)){
            if(!visited[w]){
                Push(S,w);
                visited[w] = true;
            }
        }
    }
}
//由于使用了栈，遍历方式是从右到左，不同于常规左到右，仍然是深度优先遍历

分别采用基于BFS和DFS判别以邻接表方式存储的有向图中是否存在顶点vi到顶点vj到路径i≠j

int visted[MAXSIZE] = {0};
void DFS(AlGraph G, int i, int j, bool &can_reach){
    if(i==j){
        can_reach = true;
        return;                //i就是j
    }
    visited[i] = 1;
    for(int p = FirstNeighbor(G,i); p>=0; p=NextNeighbor(G,i,p))
        if(!visited[p]&&!can_reach)
            DFS(G,p,j,can_reach);
}

int BFS(AlGraph G, int i, int j){
    InitQueue(Q);
    EnQueue(i);
    while(!isEmpty(Q)){
        DeQueue(Q);
        visited[u] = 1;
        if(u==j)
            return 1;
        for(int p=FirstNeighbor(G,i); p; P=NextNeighbor(G,u,p)){
            if(p==j)
                return 1;
            if(!visited[p]){
                EnQueue(Q,p);
                visited[p] = 1;
            }
        }
    }
}

图以邻接表表示，输出从顶点vi到vj的所有简单路径

void FindPath(AGraph *G, int u, int v, int path[], intd){
    int w,i;
    ArcNode *p;
    d++;
    path[d] = u;
    visited[u] = 1;        //已访问
    if(u==v)
        print(path[]);
    p=G->adjlist[u].firstarc;    //p指向u到第一个相邻点
    while(!p=NULL){
        w=p->adjvex;    //若w未访问，递归访问他
        if(visited[w]==0)
            FindPath(G, w, V, path, d);
        p = p->nextarc;
    }
    visited[u] = 0;
}

BFS求解单源最短路径

void BFS_MIN_Distance(Graph G, int u){
    //d[i]:the distance from u to i
    for(int i=0; i<G.vexnum; ++i)
        d[i] = 9999;
    visited[u] = true;
    d[u] = 0;
    EnQueue(Q, u);
    while(!isEmpty(Q)){
        //BFS
        DeQueue(Q,u);    //head u out
        for(w=FirstNeighbor(G,u); w>=0; w=NextNeighbor(G,u)){
            if(!visited[w]){
                visited[w] = true;
                d[w] = d[u]+1;
                EnQueue(Q,w);
            }
        }
    }
}

狄杰斯特拉算法，Dijkstra，单源点最短路径

//Min is the shortest distance from start to others
bool closed[N] = {FALSE};    //initial closed
int Min[N] = {INF};
closed[start] = true;
Min[start] = 0;
for(int i=1; i<N; ++i){        //将剩余的N-1个顶点距离start的最短距离算出
    int k = -1;        //存放每轮循环距离离start最近的点
    for(int j=1; j<N; ++j){
        if(!closed[j] && (k==-1 || Min[k]>Min[j]))
            k = j;
    }
    closed[k] = true;
    for(int j=0; j<N; ++j){        //更新未求得最短路径的结点到start的最短距离
        if(!visited[j]){
            if(Min[j]>Min[k]+G[k][j])
                Min[j] = Min[k]+G[k][j];
        }
    }
}

数据结构题

数据结构习题

选择填空知识点

线性表

查找

树

图

排序

代码题

线性表

链表

排序

树

图

Leave a Comment Cancel reply

C语言数据结构

数据结构题

春招所遇到的笔试代码题

About Me

C++实现的基础算法练习

春招所遇到的笔试代码题

数据结构题

C语言数据结构

C++实现的基础算法练习

收集的面试经验

数据结构题

数据结构习题

选择填空知识点

线性表

查找

树

图

排序

代码题

线性表

链表

排序

树

图