数据结构上机实验习题整理

发布于 / 笔迹 / 3 条评论

在数据结构实验考试之前,整理一下之前在Trustie平台上做过的习题。



实验一 顺序表的操作

题目

第一行是2个整数N和M。第二行是N个整数。再然后有M行,每行代表一个操作。操作格式如下:

  • 1 x y
  • 2 x
  • 3 x:
  • 4 x y: 表示将x位置上的数值修改为y

提示:位置从0开始。

任务:完成M个操作。且对于每一个“3操作”,输出一行为查询结果。

这个程序中出现的所有的数均为100以内的正整数。

输入输出样例

样例输入:
3 1
10 20 30
3 1
样例输出:
20

解析

按照题目要求完成相应操作即可,具体参见代码。详情请点击:数据结构笔记(一):线性表之顺序表的简单实现

数据结构笔记(一):线性表之顺序表的简单实现

使用C++简单实现顺序表,完成增删查改以及输出与合并功能。若文中存在错误,敬请指出,感谢阅读。 顺序表还是挺好理解的,相对于链表而言,实现起来也比 ...
https://taifua.com/arraylist.html

代码

//数据结构上机实验作业(一)
//时间:2017年9月27日
//Accepted by TaiFu_S

#include <iostream>
#include <cstdio>
using namespace std;
const int INIT_SIZE = 1010;

struct SqList
{
    int *elem;
    int length;
    int capacity;
};

int initList(SqList & list)
{
    list.elem = NULL;
    list.elem = new int [INIT_SIZE];
    if (!list.elem)
        return -1;
    list.capacity = INIT_SIZE;
    list.length = 0;
    return 0;
}

int destoryList(SqList & list)
{
    delete [] list.elem;
    list.elem = NULL;
    return 0;
}

int insertList(SqList & list, int pos, int value)
{
//  if (pos < 0 || pos > list.length)
//      return -1;
    for (int i = list.length - 1; i >= pos; --i)
        list.elem[i+1] = list.elem[i];
    list.elem[pos] = value;
    ++list.length;
    return 0;
}

int removeList(SqList & list, int pos)
{
//  if (pos < 0 || pos > list.length)
//      return -1;
    for (int i = pos; i < list.length-1; ++i)
        list.elem[i] = list.elem[i+1];
    --list.length;
    return 0;
}

int atList(SqList & list, int pos)
{
//  if (pos < 0 || pos > list.length)
//      return -1;
    return list.elem[pos];
}

int modifyList(SqList & list, int pos, int value)
{
//  if (pos < 0 || pos > list.length)
//      return -1;
    list.elem[pos] = value;
    return 0;
}

int mergeList(SqList const &a, Sqlist const &b, SqList & c)
{
//  if (a.length + b.length > c.capacity)
//      ;;;;
    for (int i = 0; i < a.length; ++i)
        c.elem[i] = a.elem[i];
    for (int i = 0; i < b.length; ++i)
        c.elem[i+a.length] = b.elem[i];
    c.length = a.length + b.length;
    return 0;
}

int main()
{
    int n, m;
    SqList list;
    initList(list);
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        cin >> list.elem[i];
        list.length++;
    }
//  for (int i = 0; i < n; ++i)
//      cout << list.elem[i];
    int idx, x, y;
    while (m--)
    {
        cin >> idx >> x;
        if (idx == 1)
        {
            cin >> y;
            insertList(list, x, y);
        }
        else if (idx == 2)
            removeList(list, x);
        else if (idx == 3)
            cout << atList(list, x) << endl;
        else if (idx == 4)
        {
            cin >> y;
            modifyList(list, x, y);
        }
    }
    return 0;
}

实验二 栈的使用

题目

给定一个字符串,由三种括号组成,分别是:圆括号、方括号和花括号。请判断该字符串中的括号是否匹配。匹配输出OK,否则输出Error。

输入输出样例

样例输入:
()
样例输出:
OK
样例输入:
}{
样例输出:
Error

解析

使用C++ STL栈的三种操作,s.top(); s.pop(); s.push()即可完成,此外,本题好像不用考虑空串,具体参见代码。详情请点击:数据结构笔记(三): 栈的顺序存储结构与链式存储结构实现

数据结构笔记(三): 栈的顺序存储结构与链式存储结构实现

使用顺序存储结构(顺序表)与链式存储结构(链表)来实现栈,完成栈的基本操作。若文中存在错误,敬请指出,感谢阅读。 基本知识 栈的简介:栈是后进 ...
https://taifua.com/stack.html

代码

//数据结构上机实验作业(二)
//时间:2017年10月11日
//Accepted by TaiFu_S

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
bool check(string s)
{
    stack<char>st;
    bool f = true;
    for (int i = 0; i < s.length() && f; ++i)
    {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{')
            st.push(s[i]);
        else if (!st.empty() && st.top() == '(' && s[i] == ')')
            st.pop();
        else if (!st.empty() && st.top() == '[' && s[i] == ']')
            st.pop();
        else if (!st.empty() && st.top() == '{' && s[i] == '}')
            st.pop();
        else
            f = false;
    }
    if (f && st.empty())
        return true;
    return false;
}
int main()
{
    string s;
    while (cin >> s)
    {
        if (check(s))
            cout << "OK" << endl;
        else
            cout << "Error" << endl;
    }
    return 0;
}

实验三 队列的模拟操作

题目

有如下一组模拟队列的操作:

  • PUSH x:表示将x入队,x是不超过100的非负整数。
  • POP:表示出队操作
  • FRONT:表示取队首操作(但队首并不出队)

完成操作,并对每一个FRONT操作,输出一行,为当时的队首。

输入输出样例:

样例输入:
PUSH 58
POP
PUSH 61
FRONT
样例输出:
61

解析

直接使用C++ STL 队列即可完成,具体参见代码。详情请点击:数据结构笔记(四): 队列的顺序存储结构与链式存储结构实现

数据结构笔记(四): 队列的顺序存储结构与链式存储结构实现

使用顺序存储结构(循环队列)与链式存储结构来实现队列,完成队列的基本操作。若文中存在错误,敬请指出,感谢阅读。 基本知识 队列的简介:元素先进 ...
https://taifua.com/queue.html

代码

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    queue <int> q;
    string s;
    while(cin >> s)
    {
        if (s == "PUSH")
        {
            cin >> x;
            q.push(x);
        }
        else if (s == "POP")
            q.pop();
        else if (s == "FRONT")
            cout << q.front() << endl;
    }
    return 0;
}

不能太水了,还是手写(复制)队列的具体实现代码。

//数据结构上机实验作业(三)
//时间:2017年10月18日
//Accepted by TaiFu_S

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define MAX_ARRAYQUEUE_SIZE 100
using namespace std;

struct node_t{
    int data;
    struct node_t *next;
};

typedef struct node_t Node;

struct LinkedQueue_Tag{
    Node *head;
    Node *rear;
};

typedef struct LinkedQueue_Tag* LinkedQueue;

LinkedQueue createLinkedQueue(){
    Node *pt = NULL;
    pt = (Node*)malloc(sizeof(Node));
    if (!pt) return NULL;

    LinkedQueue ret = NULL;
    ret = (LinkedQueue)malloc(sizeof(struct LinkedQueue_Tag));
    if (!ret) return NULL;

    ret->head = ret->rear = pt;
    return ret;
}

int pushLinkedQueue(LinkedQueue queue,int newValue){
    Node *pt = NULL;
    pt = (Node*)malloc(sizeof(Node));
    if (!pt) return -1;

    pt->data = newValue;
    pt->next = NULL;
    queue->rear->next = pt;
    queue->rear = pt;
    return 0;
}

int popLinkedQueue(LinkedQueue queue){
    if (queue->head == queue->rear) return -1;

    Node *pt = queue->head->next;
    if (pt==queue->rear) queue->rear = queue->head;
    queue->head->next = pt->next;
    free(pt);
    return 0;
}

int frontLinkedQueue(LinkedQueue const queue,int *pResult){
    if (queue->head == queue->rear) return -1;
    *pResult = queue->head->next->data;
    return 0;
}

int isEmptyLinkedQueue(LinkedQueue const queue){
    return queue->head == queue->rear;
}


int printLinkedQueue(LinkedQueue const queue){
    Node *pt;
    for(pt=queue->head->next;pt;pt=pt->next)printf("%d ",pt->data);
    printf("\n");
    return 0;
}

int destroyLinkedQueue(LinkedQueue *pt){
    while((*pt)->head!=(*pt)->rear) popLinkedQueue(*pt);
    free((*pt)->head);
    free(*pt);
    pt = NULL;
    return 0;
}

int main()
{
    LinkedQueue queue = createLinkedQueue();
    string s;
    int x;
    while(cin >> s)
    {
        if (s == "PUSH")
        {
            cin >> x;
            pushLinkedQueue(queue, x);
        }
        else if (s == "POP")
            popLinkedQueue(queue);
        else if (s == "FRONT")
        {
            int result = -1;
            frontLinkedQueue(queue, &result);
            cout << result << endl;
        }
    }
    destroyLinkedQueue(&queue);
    return 0;
}

实验四 数组

题目

模拟一个数组的操作。数组元素均为整型。第一行是若干个数,第1个数D表示数组的维度,然后还有D个数,分别表示各维的长度。初始时所有元素均为0。第二行是一个数N,表示其后有N个命令,每个命令一行。

一共有2种命令:

  • 1 d1 d2 d3 … 表示查询数组下标为d1,d2,d3,…的元素值
  • 2 x d1 d2 d3 … 表示将数组下标为d1,d2,d3,…的元素的值修改为x。

对每一个1操作,输出一行,为该元素的值。

输入输出样例

样例输入:
2 3 4
3
1 0 0
2 3 1 2
1 1 2
样例输出:
0
3

解析

多维数组的实现,有两种方式,具体参见代码,详情请点击:数据结构笔记(五): 多维数组的实现

数据结构笔记(五): 多维数组的实现

利用线性表(动态数组)实现多维数组,其实本质上就是操作一维数组,找到相应位置进行修改和查询操作。若文中存在错误,敬请指出,感谢阅读。 个人感觉 ...
https://taifua.com/array.html

代码

//数据结构上机实验作业(四)
//时间:2017年10月25日
//Accepted by TaiFu_S

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

struct Array_Tag{
    int *base;
    int dim;
    int *bounds;
    int *constants;
};

typedef struct Array_Tag *Array;

static int _offsetArray(Array const array, int a[]){
    int i, tmp, ret = 0;
    for(i=0;i<array->dim;++i){
        tmp = a[i];
        if ( tmp < 0 || tmp >= array->bounds[i] ) return -1;
        ret += array->constants[i] * tmp;
        cout << "array->constants[" << i << "] = " << array->constants[i] << ", tmp = " << tmp << endl;
    }
    //cout << "ret: " << ret << endl;
    return ret;
}

Array createArray(int dim, int a[]){
    if ( dim <= 0 ) return NULL;

    Array ret = NULL;
    ret = (Array)malloc(sizeof(struct Array_Tag));
    if (!ret) return NULL;

    ret->dim = dim;
    ret->bounds = NULL;
    ret->bounds = (int*)malloc(sizeof(int)*dim);
    if (!ret->bounds){
        free(ret);
        return NULL;
    }

    //获取各维长度
    int i,total = 1;

    for(i=0;i<dim;++i){
        ret->bounds[i] = a[i];
        total *= ret->bounds[i];
    }

    //分配真正存储数据的地方
    ret->base = NULL;
    ret->base = (int*)malloc(total*sizeof(int));
    if (!ret->base){
        free(ret->bounds);
        free(ret);
        return NULL;
    }

    //清零
    memset(ret->base,0,total*sizeof(int));

    //计算每一维所含有元素的数量
    ret->constants = NULL;
    ret->constants = (int*)malloc(dim*sizeof(int));
    if (!ret->constants){
        free(ret->bounds);
        free(ret->base);
        free(ret);
        return NULL;
    }

    ret->constants[dim-1] = 1;
    for(i=dim-2;i>=0;--i) {
        ret->constants[i] = ret->bounds[i+1] * ret->constants[i+1];
        cout << "constants "  << i << ": "<< ret->constants[i] << endl;
    }

    return ret;
}

int atArray(Array const array,int *pResult, int a[]){
    int offset = _offsetArray(array,a);
    if ( offset < 0 ) return -1;
    *pResult = *(array->base + offset);
    return 0;
}

int modifyArray(Array array,int newValue,int a[]){
    int offset = _offsetArray(array,a);
    if ( offset < 0 ) return -1;

    *(array->base + offset) = newValue;
    return 0;
}

int destroyArray(Array *pt){
    free((*pt)->base);
    free((*pt)->bounds);
    free((*pt)->constants);
    free(*pt);
    pt = NULL;
    return 0;
}

int main()
{
    int d, a[100];
    cin >> d;
    for (int i = 0; i < d; ++i)
        cin >> a[i];
    Array A = createArray(d, a);
    int n, idx, x, b[100];
    cin >> n;
    while (n--)
    {
        cin >> idx;
        if (idx == 1)
        {
            int ans = 0;
            for (int i = 0; i < d; ++i)
                cin >> b[i];
            atArray(A, &ans, b);
            cout << ans << endl;
        }
        else if (idx == 2)
        {
            cin >> x;
            for (int i = 0; i < d; ++i)
                cin >> b[i];
            modifyArray(A, x, b);
        }
    }
    destroyArray(&A);
    return 0;
}

实验五 二叉树的遍历

题目

给定一个字符串,表示一个使用顺序存储的二叉树。第一个字母表示树根,编号为1。空节点使用空格表示。要求输出该二叉树的层次遍历与中序遍历,分作两行输出。

输入输出样例

样例输入:
A B
样例输出:
AB
AB

解析

模拟操作即可,具体参见代码。

代码

//数据结构上机实验作业(五)
//时间:2017年11月1日
//Accepted by TaiFu_S

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
string s;
const int maxn = 1010;

void levelOrder() // 层次遍历
{
    queue<int>Q;
    int root = 1;
    Q.push(root);
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        cout << s[u];
        if (s[2*u] != ' ')
            Q.push(2*u);
        if (s[2*u+1] != ' ')
            Q.push(2*u+1);

    }
    cout << endl;
}

void preOrder(int u)
{
    if (' ' == s[u])
        return;
    preOrder(2*u);
    cout << s[u];
    preOrder(2*u+1);
}

void preOrder2(int u)
{
    if (s[u] != ' ')
    {
        preOrder(2*u);
        cout << s[u];
        preOrder(2*u+1);
    }
}

int main()
{
    getline(cin, s);
    s.insert(0, " ");
    string _s(maxn, ' ');

    s.insert(s.length()-1, _s); // 换行有bug, 需要减1
    levelOrder();
    preOrder2(1);
    return 0;
}

实验六 图的深度遍历和广度遍历

题目

给定一个无向无权图,输出图的深度优先遍历和广度优先遍历。

输入首先是一行,包含2个非负整数N和M,其中N表示图的顶点的数量,M表示边的数量。N不超过100。其后一行,一共有M对数,每一对数a、b表示顶点a和顶点b之间有一条边,a和b显然都在[1, N]之间。
输出2行,第一行为深度优先遍历,第二行为广度优先遍历。任何时候,当有多种选择时,都优先选择顶点编号更小的点进行遍历。另外,每输出一个数,就紧跟着输出一个空格。

特别提示,图可能是不连通的。参考样例。

输入输出样例

样例输入:
2 1
1 2
样例输出:
1 2
1 2
样例输入:
4 2
1 4
4 2
样例输出:
1 4 2 3
1 4 2 3

解析

模拟操作即可,具体参见代码。注意图可能是不联通的,所以遍历的时候加一个循环即可。详情请点击:数据结构笔记(六): 图的存储与遍历

数据结构笔记(六): 图的存储与遍历

分别使用邻接矩阵与邻接表存储图来实现图的深度优先遍历和广度优先遍历。若文中存在错误,敬请指出,感谢阅读。 这次先上代码后讲基础知识,给定一个无 ...
https://taifua.com/graph-traverse.html

代码

//数据结构上机实验作业(六)
//时间:2017年11月8日
//Accepted by TaiFu_S

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 1100;
int a[maxn][maxn];
int n, m;
bool f[maxn];
bool vis[maxn];

void dfs(int u)
{
    if (!f[u])
        cout << u <<  " ";
    f[u] = true;
    for (int j = 1; j <= n; ++j)
    {
        if (a[j][u] && !f[j])
            dfs(j);
    }
}

void bfs(int i)
{
    queue <int> q;
    int now = i;
    q.push(now);
    while (!q.empty())
    {
        now = q.front();
        if (!vis[now])
            cout << now << " ";
        vis[now] = true;
        q.pop();
        for (int i = 1; i <= n; ++i)
        {
            if (!vis[i] && a[i][now])
            {
                q.push(i);
            }
        }
    }
}

int main()
{
    int x, y;
    cin >> n >> m;
    memset(a, 0, sizeof(a));
    memset(f, 0, sizeof(f));
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= m; ++i)
        a[i][i] = 1;
    for (int i = 1; i <= m; ++i)
    {
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    for (int i = 1; i <= n; ++i)
        dfs(i);
    cout << endl;
    for (int i = 1; i <= n; ++i)
        bfs(i);
    cout << endl;
    return 0;
}

实验七 最小生成树

题目

给定一个无向带权连通图,求最小生成树的权值总和。

第一行是N和M,表示点数和边数。顶点的数量不超过100个。以下M行,每一行三个整数,分别为a、b、w,表示a、b之间有条边,权值为w。a和b均在1到N之间取值。输出一行为答案。

输入输出样例

样例输入:
3 2
1 2 3
1 3 2
样例输出:
5

解析

最小生成树算法的实现,可以选择Kruskal算法与Prim算法,我写的是Prim算法。

代码

//数据结构上机实验作业(七)
//时间:2017年11月15日
//Accepted by TaiFu_S

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 110;
bool vis[maxn];
int Map[maxn][maxn];
int lowcost[maxn];

int Prim(int n)
{
    int ans = 0;
    memset(vis, false, sizeof(vis));
    vis[1] = true;
    for (int i = 2; i <= n; ++i)
        lowcost[i] = Map[1][i];
    for (int i = 2; i <= n; ++i)
    {
        int minc = inf;
        int p = -1;
        for (int j = 1; j <= n; ++j)
            if (!vis[j] && minc > lowcost[j])
            {
                minc = lowcost[j];
                p = j;
            }
        if (minc == inf)
            return -1;
        ans += minc;
        vis[p] = true;
        for (int j = 1; j <= n; ++j)
            if (!vis[j] && lowcost[j] > Map[p][j])
                lowcost[j] = Map[p][j];
    }
    return ans;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            Map[i][j] = (i==j) ? 0 : inf;
    int u, v, w;
    for (int i = 0; i < m; ++i)
    {
        cin >> u >> v >> w;
        Map[u][v] = Map[v][u] = w;
    }
    cout << Prim(n) << endl;
    return 0;
}

实验八 最短路径

题目

给定一个无向带权图,求最短路径。

第一行为N和M,分别表示点数和边数,N不超过100。此后M行,每行三个整数a、b、w。a、b表示点,范围从1到N;w为权值,范围从1到100。最后还有两行,分别为A、B、C、D,为4个顶点。输出两行,分别是A到B的最短距离,C到D的最短距离。如果两个点之间不连通,输出-1。

输入输出样例

样例输入:
2 1
1 2 100
1 2
2 1
样例输出:
100
100

解析

最短路径算法实现,考虑Dijkstra算法和Floyd算法(简单)。但是要注意题目是求AB最短路径和CD之间最短路径,所以要跑两遍。

代码

//数据结构上机实验作业(八)
//时间:2017年11月22日
//Accepted by TaiFu_S

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define debug printf("bug\n");
using namespace std;
const int maxn = 110;
const int inf = 0x3f3f3f3f;
int Map[maxn][maxn];
int dist[maxn];
bool vis[maxn];

void Dijkstra(int n, int src)
{
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; ++i)
        dist[i] = inf;
    dist[src] = 0;
    for (int j = 1; j <= n; ++j)
    {
        int k = -1, Min = inf;
        for (int i = 1; i <= n; ++i)
            if (!vis[i] && dist[i] < Min)
            {
                Min = dist[i];
                k = i;
            }
        if (k == -1)
            break;
        vis[k] = true;
        for (int i = 1; i <= n; ++i)
        {
            if (!vis[i] && dist[k] + Map[k][i] < dist[i])
                dist[i] = dist[k] + Map[k][i];
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    int u, v, w;
    int A, B, C, D;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            Map[i][j] = (i == j) ? 0 : inf;
    for (int i = 0; i < m; ++i)
    {
        cin >> u >> v >> w;
        Map[u][v] = Map[v][u] = w;
    }
    cin >> A >> B >> C >> D;
    Dijkstra(n, A);
    if (dist[B] != inf)
        cout <<  dist[B] << endl;
    else
        cout << "-1" << endl;
    Dijkstra(n, C);
    if (dist[D] != inf)
        cout << dist[D] << endl;
    else
         cout << "-1" << endl;
    return 0;
}

//Floyd算法

const int inf = 0x3f3f3f3f;

for (int i = 1; i <= n; ++i)
    for (int i = 1; i <= n; ++i)
        G[i][j] = (i == j) ? 0 :inf;

for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            G[i][j] = min(G[i][j], G[i][k] + G[k][j]);


实验九 二分查找

题目

给定一个升序排序数组,再给定一个数,问数组中包含多少个同样值的元素。

输入共二行,第一行为N、x。第二行为N个整数。问这N个数中有多少个数等于x。所有数均不超过1000的正整数。

输入输出样例

样例输入:
3 2
1 2 3
样例输出:
1

解析

数据范围小,可以直接暴力实现,用二分查找的话,就是找到大于等于x的第一个数的位置pos1,找到最后一个小于等于x的数的位置pos2,答案就是pos2-pos1+1,详情请点击:数据结构笔记(七):线性表的查找之顺序查找与二分查找

数据结构笔记(七):线性表的查找之顺序查找与二分查找

本文简单介绍查找线性表(顺序表)中元素时常用的顺序查找与二分查找,若文中存在错误,敬请指出,感谢阅读。 查找(Searching)的定义是:给定一个值Key ...
https://taifua.com/arraylist-search.html

代码

//数据结构上机实验作业(九)
//时间:2017年11月29日
//Accepted by TaiFu_S

#include <iostream>
using namespace std;
const int maxn = 1010;
int a[maxn];

// 下标从1开始,找到第一个大于等于x的值的位置
int Binary_search1(int a[], int n, int x)
{
    int l = 1, r = n;
    while (l <= r)
    {
        int m = (l+r) >> 1;
        if (a[m] < x)
            l = m + 1;
        else
            r = m - 1;
    }
    return r + 1;
}

// 下标从1开始,找到最后一个小于等于x的值的位置
int Binary_search2(int a[], int n, int x)
{
    int l = 1, r = n;
    while (l <= r)
    {
        int m = (l+r) >> 1;
        if (a[m] <= x)
            l = m + 1;
        else
            r = m - 1;
    }
    return l - 1;
}

int main()
{
    int n, x;
    cin >> n >> x;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    cout << Binary_search2(a, n, x) - Binary_search1(a, n, x) + 1 << endl;
    return 0;
}

整理小结

  • 线性表:增删查改基本实现,可用C++ STL vector
  • 栈与队列:增删查实现及其应用(括号匹配),使用C++ STL stackqueue
  • 多维数组:查改实现
  • 树:二叉树的遍历(层次遍历与前序中序后序遍历)
  • 图论:存储与深度广度遍历,最短路径与最小生成树
  • 顺序表查找:二分查找的应用
  • 排序算法:相关应用(使用结构体验证稳定性)

此外,书上的还有拓扑排序以及平衡二叉排序树和各种排序算法,也包括字符串和广义表

如果运气好的话

那么。

The end.
2017-12-25 星期一

考试情况(更新)

  • 顺序表增查改(数组/vector)
  • 简单排序(sort)
  • 简单排序升级(同sort排序结构体加cmp)
  • 解一元四次方程(二分查找应用)

简单讲一下解一元四次方程这道题。

题目

给定一个4次方程,再给定一个定义域,求在该定义域上方程的解。保证定义域内有唯一解且对应的4次函数单调。方程形式为:a0+a1x+a2x^2+a3x^3+a4x^4 = 0

Input
输入只有一行,一共7个绝对值不超过10的整数。前五个数分别是a0, a1, a2, a3, a4,表示相应项的系数,后两个数是x1, x2,表示定义域[x1, x2]。
Output
输出一行为结果。保留3位小数。
Sample Input
0 0 0 0 1 0 1
Sample Output
0.000

分析

直接使用二分查找即可,但是要注意两个问题:

  • 判断单调递增还是递减
  • 精度控制

代码

  • 实现一,注意精度范围,必须调到足够小,不然连样例都过不了。
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
const double eps = 1e-15; // 精度
int a0, a1, a2, a3, a4;

double f(double x)
{
    return a0*1.0 + a1*x + a2*x*x + a3*x*x*x + a4*x*x*x*x;
}

double solve(double l, double r)
{
    double mid = l;
    while (l <= r)
    {
        mid = (l+r)*0.5;
        if (fabs(f(mid)) <= eps) // 精度控制
            break;
        if (f(l) > f(r)) // 单调递减
        {
            if (f(mid) > 0)
                l = mid;
            else
                r = mid;
        }
        else if (f(l) < f(r)) // 单调递增
        {
            if (f(mid) > 0)
                r = mid;
            else
                l = mid;
        }
    }
    return mid;
}

int main()
{
    int x1, x2;
    cin >> a0 >> a1 >> a2 >> a3 >> a4 >> x1 >> x2;
    double l = x1*1.0, r = x2*1.0;
    double ans = solve(l, r);
    cout << fixed << setprecision(3) << ans << endl;
    return 0;
}
  • 实现二,不多说,具体看代码。
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
const double eps = 1e-4;
int a0, a1, a2, a3, a4;

double f(double x)
{
    return a0*1.0 + a1*x + a2*x*x + a3*x*x*x + a4*x*x*x*x;
}

void solves(double x1, double x2)
{
    double l = x1*1.0;
    double r = x2*1.0;
    double mid = 0;
    while (r - l > eps) // 精度控制
    {
        mid = (l + r) / 2.0;
        if (f(mid)*f(l) < 0.0) // 左区间
            r = mid;
        else // 右区间
            l = mid;
    }
    cout << fixed << setprecision(3) << mid << endl;
}

int main()
{
    int x1, x2;
    cin >> a0 >> a1 >> a2 >> a3 >> a4 >> x1 >> x2;
    solves(x1, x2);
    return 0;
}

除了以上两种二分查找实现外,我还测试了暴力,在主席(感谢)的帮助之下,终于找到了唯一的控制好精度和运行时间的情况。

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
const double eps = 1e-4; // 精度
const double e = 1e-6; // 时间
int a0, a1, a2, a3, a4;

double f(double x)
{
    return a0*1.0 + a1*x + a2*x*x + a3*x*x*x + a4*x*x*x*x;
}

int main()
{
    int x1, x2;
    cin >> a0 >> a1 >> a2 >> a3 >> a4 >> x1 >> x2;
    double l = x1*1.0, r = x2*1.0;
    double ans = x1;
    double tmp;
    for (double i = l; i <= r; i += e)
    {
        if (fabs(f(i)) <= eps) // 精度误差
        {
            tmp = fabs(f(i));
            if (fabs(f(i+e)) < tmp) // 更新
                ans = i+e;
        }
    }
    cout << fixed << setprecision(3) << ans << endl;
    return 0;
}

感觉这次考试很坑啊,迅哥竟然没出图论的题,期末也不会考最短路径和最小生成树,过分了啊!?!


The end.
2017-12-28 星期四

转载原创文章请注明,转载自: 太傅 » 数据结构上机实验习题整理
  1. TaiFu_S

    对于不考图论中最短路径和最小生成树, 开心就好!

  2. 楠尘

    新年快乐呀,愣是没找到留言页面

    1. TaiFu_S
      @楠尘

      就是在关于页面留言!哈哈?