数据结构大作业

一、找出湖景房

在湖边有一排东西向排列的房子。如果一个房子比它东边的所有房子都高，我们称之为湖景房。如图1-1所示，阴影的房子都是湖景房。一位旅行者从西往东走至湖景处，决定逗留几天。假设每栋房子的高度存放于数组 A[1…n] 中，请你帮他找出所有的湖景房。

1. 写出算法实现的步骤，要求用栈和队列实现，需要给出栈和队列的相关操作算法设计：

因为房子从左向右排列，但是找出湖景房需要将房子与其右侧的所有房子做比较，且最右方的房子必然为湖景房。可以利用栈后进先出的特性，先把房子高度数组元素正序压入栈S1，然后按照房子高度数组元素的逆序弹出栈顶元素，因为第一个栈顶元素对应最右侧湖边的房子，其必定为湖景房，所以直接压入栈S2中，然后按照题中对湖景房的定义，将每一个从栈S1弹出的栈顶元素放入h并与储存湖景房高度的S2中的栈顶元素进行比较，若弹出的栈顶元素h比S2中的栈顶元素大，则h为湖景房并压入栈S2。最后将栈S2进行遍历，输出所有的湖景房的高度。

2. 请用一个具体实例逐步演绎你的算法策略(n>=10)，并输出最后结果：

▶

Code

#include<stdio.h>
#include<stdlib.h>

#define MAX 50

// 顺序栈结构
typedef struct {
    int High[MAX];
    int top;
} stack;

// 栈初始化
void Init(stack *s) {
    s->top = -1;
}

// 插入栈顶元素
void Push(stack *s,int h) {
    s->top++;
    s->High[s->top] = h;
}

// 弹出栈顶元素
void Pop(stack* s, int *h) {
    h = s->High[s->top];
    s->top--;
}

// 由栈顶到栈底遍历元素
void Traverse(stack s) {
    int i;
    i = s.top;
    while (i >=0) {
        printf("%d", s.High[i]);
        printf(" ");
        i--;
    }
    printf("\n");
}

int main() {
    int A[25] = {266,86,69,110,120,218,90,177,33,168,99,87,63,134,66,34,100,51,92,71};  //储存房子高度的数组
    stack S1,S2;  //S1储存所有的房子高度，S2储存湖景房房子高度
    int h=0;

    Init(&S1);  //初始化栈
    Init(&S2);

    int i = 0;
    while (A[i]!=0) {  //将房子高度压入栈
        Push(&S1, A[i]);
        i++;
    }

    Pop(&S1, &h);  //最右方的房子必然为湖景房
    Push(&S2,h);

    for (int j = S1.top; j >=0; j--) {  //从S1中选出湖景房，并把高度压入S2
        Pop(&S1, &h);
        if (h>S2.High[S2.top]) {
            Push(&S2, h);
        }
        else {
            continue;
        }
    }
    Traverse(S2);  //遍历S2，输出湖景房高度
    return 0;
}

具体实例：

测试数据：A[25]={ 266,86,69,110,120,218,90,177,33,168,99,87,63,134,66,34,100,51,92,71 };
首先将储存房子高度的数组A[25]中的高度数据正序压入栈S1中，然后弹出第一个栈顶元素 71 ，因为第一个栈顶元素对应最右侧的必定为湖景房的房子，所以直接将 71 压入栈S2中。因为S2的栈顶元素为当前找到的最高的湖景房高度，之后的湖景房都要比这个湖景房高，所以可以直接用栈S1弹出的栈顶元素与S2的栈顶元素进行对比，确定其是否为湖景房。所以：

栈S1弹出92，比S2的栈顶元素71大，将92压入栈S2；
栈S1弹出51，比S2的栈顶元素92小，51不压入栈S2；
栈S1弹出100，比S2的栈顶元素92大，将100压入栈S2；
栈S1弹出34，比S2的栈顶元素100小，34不压入栈S2；
栈S1弹出66，比S2的栈顶元素100小，2不压入栈S2；
栈S1弹出134，比S2的栈顶元素100大，将134压入栈S2；
栈S1弹出63，比S2的栈顶元素134小，63不压入栈S2；
栈S1弹出87，比S2的栈顶元素134小，87不压入栈S2；
栈S1弹出99，比S2的栈顶元素134小，99不压入栈S2；
栈S1弹出168，比S2的栈顶元素134大，将168压入栈S2；
栈S1弹出33，比S2的栈顶元素168小，33不压入栈S2；
栈S1弹出177，比S2的栈顶元素168大，将177压入栈S2；
栈S1弹出90，比S2的栈顶元素177小， 90不压入栈S2；
栈S1弹出218，比S2的栈顶元素177大，将218压入栈S2；
栈S1弹出120，比S2的栈顶元素218小， 120不压入栈S2；
栈S1弹出110，比S2的栈顶元素218小，110不压入栈S2；
栈S1弹出69，比S2的栈顶元素218小，69不压入栈S2；
栈S1弹出86，比S2的栈顶元素218小，86不压入栈S2；
栈S1弹出266，比S2的栈顶元素218大，将266压入栈S2；
最后输出湖景房的高度：266 218 177 168 134 100 92 71。

3. 分析算法的时间复杂度和空间复杂度：

经过分析，该算法的时间复杂度为O（n），空间复杂度为O（n）。

二、学生数据管理

假设某大学某个专业共有N（<=1000）位学生，分为k个班。所有学生已完成前三学年的课程，并根据前三年的课程计算出了每个学生的绩点。学生信息包括学号、姓名、性别、专业、班级、绩点。所有学生的学号连续，同一个班的学号也连续。假设用顺序表存储这些信息，请完成以下任务：

1. 请用C语言表示学生信息的存储结构：

▶

Code

#include <stdio.h>
#include <stdlib.h>

#define MAX 1001

// 储存学生数据的结构体
typedef struct student {
    int num;
    char name[20];
    char genger[4];
    char major[20];
    int Class;
    double grade;
};

typedef struct {
    student data[MAX];
    int length;
} STUDENT;

// 初始化顺序表
void Init(STUDENT* S) {
    S->length = 0;
}

// 向顺序表中添加学生信息
void IN(STUDENT *S, int number) {
    for (int i = 0; i < number; i++) {
        printf("学号：\n");
        scanf_s("%d", &S.data[i].num);
        printf("姓名：\n");
        scanf_s("%s", &S.data[i].name);
        printf("性别：\n");
        scanf_s("%s", &S.data[i].genger);
        printf("专业：");
        scanf_s("%s", &S.data[i].major);
        printf("班级：\n");
        scanf_s("%d", &S.data[i].Class);
        printf("绩点：\n");
        scanf_s("%lf", &S.data[i].grade);
    }
}

// 对顺序表S中的数据进行遍历
void OUT(STUDENT S) {
    for (int i = 0; i < S.length; i++) {
        printf("%d ", S.data[i].num);
        printf("%c ", S.data[i].name);
        printf("%c ", S.data[i].genger);
        printf("%c ", S.data[i].major);
        printf("%d ", S.data[i].Class);
        printf("%d\n", S.data[i].grade);
    }
}

// 用s返回S中的第i个数据结构体
void Get(STUDENT S, int i, student* s) {
    *s = S.data[i - 1];
}

// 在S中第i个位置之前插入新的数据元素s
void Insert(STUDENT* S, int i, student s) {
    if (i <= S->length) {
        for (int j = S->length - 1; j >= i - 1; j--)
            S->data[j + 1] = S->data[j];
    }
    S->data[i - 1] = s;
    S->length++;
}

// 删除S的第i个数据元素，并用s返回其值
void Delete(STUDENT* S, int i, student* s) {
    *s = S->data[i - 1];
    if (i < S->length) {
        for (int j = i; j < S->length; j++)
            S->data[j - 1] = S->data[j];
    }
    S->length--;
}

2. 假设每个班的学生信息按学号顺序存储，设计一个算法找出该班绩点的中位数，要求不能对绩点完全排序，复杂度不高于O(NlogN)：

因为不能对绩点完全排序，且复杂度不得高于O（NlogN）。我用的是基于分治策略的中位数查找算法。首先在所有的学生数据中取中间学生的位次记为mid，绩点数据记为value。然后利用value这一值，将全班学生按照绩点分为三个组，大于value的分到Big，等于value的分到Middle，小于value的分到Small。如果Small组的长度大于mid，则中位数在Small组中；如果Small<mid<=Small+Middle,则中位数为value；如果mid>=Small+Middle,则中位数在Big组中。以下为代码实现：

▶

Code

// 利用分治策略进行中位数查找
void median(STUDENT S) {
    int mid = S.length / 2;
    int value = S.data[mid]->grade;
    STUDENT Big, Middle, Small;

    Init(&Big);
    Init(&Middle);
    Init(&Small);

    for (int i = 0; i < S.length; i++) {
        if (S.data[i]->grade < value) {
            Small.data[Small.length] = S.data[i]->grade;
            Small.length++;
        }
        else if (S.data[i]->grade == value) {
            Middle.data[Middle.length] = S.data[i]->grade;
            Middle.length++;
        }
        else {
            Big.data[Big.length] = S.data[i]->grade;
            Big.length++;
        }
    }
    if (mid<=Small.length) {
        return median(Small);
    }
    else if (mid>Middle.length+Small.length) {
        return median(Big);
    }
    else {
        return mid;
    }
}

3. 设计一个算法对一个班的学生按绩点进行升序排序，绩点相同的学生按学号升序排序，要求算法时间复杂度为O(NlogN)：

时间复杂度为O（NlogN）的排序算法有希尔排序、堆排序、快速排序和归并排序。这里我使用的是快速排序，同样利用分治策略，先取一个基准值，然后将比基准值的大的元素放到基准值右边，比基准值小的放到左边，然后多次重复直到各区间只有一个数。以下为代码实现：

▶

Code

// 绩点升序排序
void grade_sort(STUDENT* S, int begin, int end) {
    int pivot;
    int left = begin, right = end;
    if (begin < end) {
        struct student stand = S->data[left];
        while (left < right) {
            while (left < right && (S->data[right].grade > stand.grade || (S->data[right].grade == stand.grade && S->data[right].num > stand.num))) {
                right--;
            }
            if (left < right) {
                S->data[left++] = S->data[right];
            }
            while (left < right && (S->data[left].grade < stand.grade || (S->data[left].grade == stand.grade && S->data[right].num > stand.num))) {
                left++;
            }
            if (left < right) {
                S->data[right--] = S->data[left];
            }
        }
        S->data[left] = stand;
        pivot = left;
        grade_sort(S, begin, pivot - 1);
        grade_sort(S, pivot + 1, end);
    }
}

4. 假设每个班的同学都已按绩点排好序（升序），设计一个算法把该专业所有同学按绩点进行升序排序，要求算法复杂度为O(N)：

因为各班成绩已经排好序，可以将每个班绩点最低的学生拿出来进行比较，找到年级绩点最低的学生并转到年级绩点排名顺序表中，如此循环，完成排序。以下为代码实现：

▶

Code

// 各班绩点排序，输入总的学生数据的顺序表S和班级数K
STUDENT Class(STUDENT* S, int K) {
    STUDENT Subject;  // 储存年级学生数据
    Init(&Subject);
    student Class[K][50];  // 用于储存各班学生的数据

    int num[K + 1];  // 储存每个班级最低成绩学生在Class[][]中的位置
    int people_class = S->length / K;  // 单个班级人数
    int flag1=0,flag2=0;

    // 数组置空
    for (int p = 0; p < K+1; p++) {
        num[p] = 0;
    }
    // 将顺序表中的数据转到二维数组
    for (int q = 0; q < K; q++) {
        for (int r = 0; r < people_class;r++) {
            Class[K][r] = S->data[r];
        }
    }
    int i = 0, j = 0;
    flag1 = Class[j][num[j]]->grade;
    flag2 = j;
    // 将各班绩点最低的学生进行对比，找出年级绩点最低，并转移到顺序表中
    for (i=0; i < S->length; i++) {
        for (j=0; j < K;j++) {
            if (Class[j+1][num[j+1]]->grade<flag1) {
                flag1 = Class[j + 1][num[j + 1]]->grade;
                flag2 = j + 1;
            }
        }
        num[flag2]++;
        Insert(Subject,i, Class[flag2][flag2]);
        flag1 = Class[0][num[0]]->grade;
        flag2 = 0;
    }
    return Subject;
}

5. 假设学生信息按学号顺序存储，设计一个按学号查询绩点的算法，要求算法复杂度为O(logN)：

因为要求时间复杂度为O（logn），所以采用二分搜索算法。代码实现如下：

▶

Code

int num_search(STUDENT S, int num) {
    int left = 0,right = S.length;
    int mid = (left + right) / 2;
    for (; left <= right;) {
        if (S.data[mid].num > num) {
            left = mid + 1;
            mid = (left + right) / 2;
        }
        else if (S.data[mid].num == num) {
            return mid;
        }
        else {
            right = mid - 1;
            mid = (left + right) / 2;
        }
    }
}

6. 假设学生信息按学号顺序存储，设计一个查询某个绩点都有那些学生的算法，给出算法的复杂度分析：

因为学生信息采用顺序表储存，可以采用直接查找的方式找出相同绩点的学生。时间复杂度和空间复杂度均为O（n）。代码实现如下：

▶

Code

void people_search(STUDENT* S,int Grade) {
    STUDENT S1;
    Init(S1);
    for (int i = 0; i < S->length; i++) {
        if (S->data[i].grade==Grade) {
            S1.data[S1.length].grade = S->data[i].grade;
            S1.length++;
        }
    }
    OUT(S1);
}

三、请阅读以下材料，并分析和思考疫情管控期间物流配送路径规划问题，根据题目要求撰写报告

自2004年开始，网络购物作为时代的产物不断改变着人们的购物方式，成为生活必不可少的一部分。如图3-1所示，截至2021年12月，中国网购用户已达8.4亿人。当我们在享受网络购物便利性的同时，不得不承认快递物流起到的重要作用。消费者选购的商品从商家仓库出发，基于物流系统寄往全国各地，3至5天即可到达消费者手中，享受在家“逛商场”的便利。
但是从2019年开始，新冠疫情反复多点爆发，中高风险区为控制疫情外泄风险，出台交通管制政策，因此“封路+停运”成为了物流面临的常态化问题。如图3-2所示，截至5月23日，引自“中国邮政速递物流”网，受疫情管控措施影响，多达40多个城市网点收寄业务遭到停发或时效风险。在后疫情背景下，物流系统经过两年多的发展，逐渐成熟，“中心仓+云仓分仓”经营模式应运而生，即：商家可以将库存交给拥有智慧云仓的物流服务商，建立多级的仓储体系，及时进行智慧调拨，云仓多仓发货，不仅快速高效，而且在后疫情时代帮助商家有效降低依靠商家单一仓储带来的停发风险，保障了全国物流系统的稳定运行。目前我国如京东云仓，菜鸟云仓，中通云仓等发展迅速，图3-3展示中通云仓科技在全国范围内覆盖60个仓库，实现全国多仓库智慧发货。
请运用数据结构知识，从以下几个方面思考并分析疫情管控期间全国多仓发货是如何降低电商物流受阻乃至停发风险的？
所用参数说明：城市数量 𝒏，疫情管控城市数量 𝒎，全国云仓发货仓数量𝒕，要求 𝒏≥𝟏𝟎, 𝒎≥𝟑, 𝒕≥𝟑。

1. 传统商家单一仓发货模式下，物流如何规划最短路径将商品送达：

测试数据：顶点数：10个边数：20条
边的权值：
[0][1] = 1; [0][2] = 5; [1][2] = 3; [1][3] = 7; [1][4] = 5;
[2][4] = 1; [2][5] = 7; [3][4] = 2; [3][6] = 3; [4][5] = 3;
[4][6] = 6; [4][7] = 9; [4][9] = 7; [5][7] = 5; [5][8] = 3;
[6][7] = 2; [6][8] = 7; [6][9] = 10; [7][8] = 4; [7][9] = 3;
实例输出结果：商家仓 a 到买家 e 的最短路径长度为: 12

▶

Code

#include <stdio.h>
#include <stdlib.h>

#define MAX 50
#define Graph_Max 3000

typedef struct {
    int vertex[MAX];    // 顶点
    int side[MAX][MAX]; // 边
    int Vertex_Num;     // 顶点数
    int Side_Num;       // 边数
} Graph;

// 创建图
void Create(Graph* G) {
    int i, j;
    // 储存边数和结点数
    G->Side_Num = 20;
    G->Vertex_Num = 10;
    for (i = 0; i < G->Vertex_Num; i++) {
        G->vertex[i] = i;
    }
    for (i = 0; i < G->Vertex_Num; i++) {
        for (j = 0; j < G->Vertex_Num; j++) {
        if (i == j)
            G->side[i][j] = 0;
        else
            G->side[i][j] = G->side[j][i] = Graph_Max;
        }
    }

    //储存边的权值
    G->side[0][1] = 1;
    G->side[0][2] = 5;
    G->side[1][2] = 3;
    G->side[1][3] = 7;
    G->side[1][4] = 5;

    G->side[2][4] = 1;
    G->side[2][5] = 7;
    G->side[3][4] = 2;
    G->side[3][6] = 3;
    G->side[4][5] = 3;

    G->side[4][6] = 6;
    G->side[4][7] = 9;
    G->side[4][9] = 7;
    G->side[5][7] = 5;
    G->side[5][8] = 3;

    G->side[6][7] = 2;
    G->side[6][8] = 7;
    G->side[6][9] = 10;
    G->side[7][8] = 4;
    G->side[7][9] = 3;

    for (i = 0; i < G->Vertex_Num; i++) {
        for (j = i; j < G->Vertex_Num; j++) {
            G->side[j][i] = G->side[i][j];
        }
    }
}

// Dijkstra算法求最短路径
void Short_Path(Graph G, int v0, int P[], int D[]) {
    int i, j;
    int k, min;
    int final[MAX];
    for (i = 0; i < G.Vertex_Num; i++) {
        final[i] = 0;
        D[i] = G.side[v0][i];
        P[i] = -1;
    }
    D[v0] = 0;
    final[v0] = 1;
    for (i = 1; i < G.Vertex_Num; i++) {
        min = Graph_Max;
        for (j = 0; j < G.Vertex_Num; j++) {
            if (!final[j] && D[j] < min) {
                k = j;
                min = D[j];
            }
        }
        final[k] = 1;
        for (j = 0; j < G.Vertex_Num; j++) {
            if (!final[j] && (min + G.side[k][j] < D[j])) {
                D[j] = min + G.side[k][j];
                P[j] = k;
            }
        }
    }
}

int main(void) {
    int v0=0;
    Graph G;
    int P[MAX];
    int D[MAX];
    Create(&G);
    Short_Path(G, v0, P, D);
    printf("商家仓 a 到买家 e 的最短路径长度为:\n");
    printf("%d\n", D[9]);
    return 0;
}

2. 传统商家单一仓发货模式下，若最短路径中有道路管控，如何选取不含该管控点的最短路径：

▶

Code

1	`// 欸嘿，没写捏，自己试试吧？`

3. 全国多仓发货模式下，如何智慧选取发货仓，并构建最短路径将商品送达：

▶

Code

1	`// 欸嘿，没写捏，自己试试吧？`

附录

文件列表
- 2022年-数据结构-大作业.pdf
下载地址
- 蓝奏云链接：https://wwrl.lanzn.com/iafNa2spfkzg
- 蓝奏云提取密码：3afc

课程报告

#河北工业大学 #数据结构

数据结构大作业

https://flowerdown.org/posts/20220612-105226.html

作者

Unrealfeather

发布于

2022年6月12日

许可协议

向量分析与场论复变函数与积分变换复习与提高上一篇

数据结构实验报告-6 下一篇

数据结构 大作业

一、找出湖景房

1. 写出算法实现的步骤，要求用栈和队列实现，需要给出栈和队列的相关操作算法设计：

2. 请用一个具体实例逐步演绎你的算法策略(n>=10)，并输出最后结果：

具体实例：

3. 分析算法的时间复杂度和空间复杂度：

二、学生数据管理

1. 请用C语言表示学生信息的存储结构：

2. 假设每个班的学生信息按学号顺序存储，设计一个算法找出该班绩点的中位数，要求不能对绩点完全排序，复杂度不高于O(NlogN)：

3. 设计一个算法对一个班的学生按绩点进行升序排序，绩点相同的学生按学号升序排序，要求算法时间复杂度为O(NlogN)：

4. 假设每个班的同学都已按绩点排好序（升序），设计一个算法把该专业所有同学按绩点进行升序排序，要求算法复杂度为O(N)：

5. 假设学生信息按学号顺序存储，设计一个按学号查询绩点的算法，要求算法复杂度为O(logN)：

6. 假设学生信息按学号顺序存储，设计一个查询某个绩点都有那些学生的算法，给出算法的复杂度分析：

三、请阅读以下材料，并分析和思考疫情管控期间物流配送路径规划问题，根据题目要求撰写报告

1. 传统商家单一仓发货模式下，物流如何规划最短路径将商品送达：

2. 传统商家单一仓发货模式下，若最短路径中有道路管控，如何选取不含该管控点的最短路径：

3. 全国多仓发货模式下，如何智慧选取发货仓，并构建最短路径将商品送达：

附录

数据结构大作业