数据结构实验题目及代码实现[更新中] • 小yo 博客

数据结构实验

1. 背包问题的求解

问题描述:

假设有一个能装入总体积为T的背包和n件体积分别为w1,w2,…wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+…+wm=T，要求找出所有满足上述条件的解.

例如：当T=10，各件物品的体积{1,8,4,3,5,2}时，可找到下列4组解:(1,4,3,2)、(1,4,5) 、(8,2) 、(3,5,2)。

2. 农夫过河问题的求解

问题描述:

一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请求出农夫将所有的东西运过河的方案。

3. 简易电子表格的设计

问题描述:

设计一个支持基本计算统计功能和其它一些表格管理/处理功能的软件，使用户可在该软件的支持下，用交互方式进行表格建立、数据输入、数据编辑及其它一些表格操作。即类似于简易Excel表格处理软件。

4. 八皇后问题

问题描述:

设在初始状态下在国际象棋的棋盘上没有任何棋子（这里的棋子指皇后棋子）。然后顺序在第1行，第2行……第8行上布放棋子。在每一行中共有8个可选择的位置，但在任一时刻棋盘的合法布局都必须满足3个限制条件（1）任意两个棋子不得放在同一行（2）任意两个棋子不得放在同一列上（3）任意棋子不得放在同一正斜线和反斜线上。

5. 约瑟夫环问题仿真

问题描述:

设编号为1，2，…，n(n>0)个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出一个报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1报数；如此下去直到所有人全部出列为止。

基本要求

设计一个程序模拟此过程，给出出列人的编号序列。

测试数据： N=7，七个人的密码依次为3，1，7，2，4，8，4. 初始报数上限值m=20。

算法思路

已知：N，各自密码。

数据结构选择：循环双链表

步骤：

S1：创建大小为N的循环链表，并读入各自的密码，p = head，count = 1;

S2：当p!= NULL时：{

S21：当count != m：{

p = p->next;

count ++;

}

S22：else{

print(p->number);

m = p->value;

p = destroy(p);

count = 1;

}

代码实现

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

typedef struct Node {
    int num;
    int data;
    struct Node* next;
    struct Node* prev;
} Node;

Node* CreateList(int n) {
    Node* head = (Node*)malloc(sizeof(Node));
    int x;
    scanf("%d", &x);
    head->data = x;
    head->num = 1;
    Node* p = head;
    for (int i = 1; i < n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        scanf("%d", &x);
        newNode->data = x;
        newNode->num = i + 1;
        newNode->prev = p;
        p->next = newNode;
        p = newNode;
    }
    p->next = head; //形成环
    head->prev = p;
    return head;
}

int Josephus(Node* head, int m) {
    Node* p = head;
    int count = 1;
    while (p->next != p) {
        if (count != m) {
            p = p->next;
            count++;
        }
        else {
            printf("%d ", p->num);
            m = p->data;
            Node* temp = p;//删除节点
            p->prev->next = temp->next;
            temp->next->prev = p->prev;
            p = temp->next;
            free(temp);
            count = 1;
        }
    }
    printf("%d\n", p->num);
}

int main() {
    int n, m;
    printf("请输入人数和初始报数值：");
    scanf("%d %d", &n, &m);
    printf("请输入每个人的密码：");
    Node* head = CreateList(n);
    printf("出列顺序为：");
    Josephus(head, m);
    return 0;
}

6. 教学计划编制问题

问题描述:

大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是固定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。

7. 二叉排序树与平衡二叉树的实现

问题描述:

分别采用二叉链表和顺序表作存储结构，实现对二叉排序树与平衡二叉树的操作。

8. 停车场模拟管理程序的设计与实现

问题描述:

设停车场只有一个可停放几辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达的先后顺序依次排列，若车场内已停满几辆汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车即可进入；当停车场内某辆车要离开时，由于停车场是狭长的通道，在它之后开入的车辆必须先退出车场为它让路，待该车辆开出大门，为它让路的车辆再按原次序进入车场。在这里假设汽车不能从便道上开走，试设计这样一个停车场模拟管理程序。

9. 学生成绩分析

问题描述:

录入、保存一个班级学生多门课程的成绩，并对成绩进行分析。

10. 一元稀疏多项式计算器

问题描述:

设计一个一元稀疏多项式简单计算器。

11. 哈夫曼压缩/解压缩算法（编译码器）

问题描述：

利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，要求在发送端通过一个编码系统对传输数据预先编码（压缩）；在接收端将传来的数据进行译码（解压缩复原）。试为这样的通信站编写一个哈夫曼编译码系统---哈夫曼压缩/解压缩算法。

12. 全国交通咨询模拟系统

问题描述：

处于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能地短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。

13. 迷宫问题

问题描述：

迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走迷宫的路线。