[C++知识库] 【NEFU锐格】数据结构实验一线性表的有关操作

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> 【NEFU锐格】数据结构实验一线性表的有关操作 -> 正文阅读

[C++知识库]【NEFU锐格】数据结构实验一线性表的有关操作

8559

c++可以直接swap，不需要第三量或者+--对换；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 1e8;

int main()
{
    int n;
    int a[N];
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        printf("%d ",a[i]);
    }
    printf("\n");
    for(int i=1;i<=n/2;i++)
    {
        swap(a[i],a[n+1-i]);
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

8553

cin的EOF返回值为0，所以可以直接使用while(cin>>g){}，而不必像while(scanf("%d",g)!=-1){}；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 1e8;
struct lknd{
    int v;
    lknd* n;
};
int main()
{
    int g;
    lknd *h=(lknd*)malloc(sizeof(lknd)),*t;
    h->n=0;
    t=h;
    while(cin>>g&&g)
    {
        lknd *now=(lknd*)malloc(sizeof(lknd));
        now->v=g;
        now->n=0;
        t->n=now;
        t=now;
    }
    lknd *now=h;
    while(now->n)
    {
        printf("%d ",now->n->v);
        now=now->n;
    }
    return 0;
}

8554

首先定位到首末节点的前一个结点，之后对换前一个结点和首末结点的next指针；
再定位到次首和次末结点的前一个结点，重复以上过程；

PS：这个代码看不懂的可以去看看鱼竿大佬的代码，他的过程更清晰；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 1e8;
struct lknd
{
    int v;
    lknd *n;
};
int main()
{
    int g;
    lknd *h = (lknd *)malloc(sizeof(lknd)), *t;
    h->n = 0;
    t = h;
    while (cin >> g && g)
    {
        lknd *now = (lknd *)malloc(sizeof(lknd));
        now->v = g;
        now->n = 0;
        t->n = now;
        t = now;
    }
    lknd *fr = h, *ed = h;
    while (ed->n != t)
    {
        ed = ed->n;
    }
    while (1)
    {
        if (fr == ed || ed->n == fr)
            break;
        else
        {
            swap(fr->n, ed->n);
            swap(ed->n->n, fr->n->n);
            t = ed;
            ed = h;
            while (ed->n != t)
            {
                ed = ed->n;
            }
            fr = fr->n;
        }
    }
    fr = h;
    while (fr->n)
    {
        printf("%d ", fr->n->v);
        fr = fr->n;
    }
    return 0;
}

8555

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 1e8;
struct lknd
{
    int v;
    lknd *n;
};
lknd *lt(int n, lknd *h)
{
    lknd *now = h;
    while (now->n && now->n->v < n)
    {
        now = now->n;
    }
    return now;
}
int main()
{
    int g;
    lknd *h = (lknd *)malloc(sizeof(lknd));
    h->n = 0;
    while (cin >> g && g)
    {
        lknd *now = (lknd *)malloc(sizeof(lknd)), *la = lt(g, h);
        now->v = g;
        now->n = la->n;
        la->n = now;
    }
    lknd *fr = h;
    while (fr->n)
    {
        printf("%d ", fr->n->v);
        fr = fr->n;
    }
    return 0;
}

8556

下面的做法比较正经，当然可以直接不把偶数加入链表

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 1e8;
struct lknd{
    int v;
    lknd* n;
};
int main()
{
    int g;
    lknd *h=(lknd*)malloc(sizeof(lknd)),*t;
    h->n=0;
    t=h;
    while(cin>>g&&g)
    {
        lknd *now=(lknd*)malloc(sizeof(lknd));
        now->v=g;
        now->n=0;
        t->n=now;
        t=now;
    }
    lknd *now=h;
    while(now->n)
    {
        while(now->n&&(((now->n->v)&1)==0))
        {
            //printf("*");
            lknd* tmp=now->n;
            now->n=now->n->n;
            free(tmp);
        }
        if(!(now->n))break;
        printf("%d ",now->n->v);
        now=now->n;
    }
    return 0;
}

8557

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 1e8;
struct lknd
{
    int v;
    lknd *n;
};
lknd *lt(int n, lknd *h)
{
    lknd *now = h;
    while (now->n && now->n->v < n)
    {
        now = now->n;
    }
    return now;
}
lknd *gt(int n, lknd *h)
{
    lknd *now = h;
    while (now->n && now->n->v > n)
    {
        now = now->n;
    }
    return now;
}
int main()
{
    int g;
    lknd *h1 = (lknd *)malloc(sizeof(lknd));
    lknd *h2 = (lknd *)malloc(sizeof(lknd));
    lknd *h3 = (lknd *)malloc(sizeof(lknd));
    h1->n = 0;
    h2->n = 0;
    h3->n = 0;
    while (cin >> g && g)//建立链表1
    {
        lknd *now = (lknd *)malloc(sizeof(lknd)), *la = lt(g, h1);
        now->v = g;
        now->n = la->n;
        la->n = now;
    }
    while (cin >> g && g)//建立链表2
    {
        lknd *now = (lknd *)malloc(sizeof(lknd)), *la = lt(g, h2);
        now->v = g;
        now->n = la->n;
        la->n = now;
    }
    lknd *fr = h1;
    while (fr->n)//将链表1按要求插入链表3
    {
        lknd *now = (lknd *)malloc(sizeof(lknd)), *la = gt(fr->n->v, h3);
        now->v = fr->n->v;
        now->n = la->n;
        la->n = now;
        fr = fr->n;
    }
    fr=h2;
    while (fr->n)//将链表2按要求插入链表3
    {
        lknd *now = (lknd *)malloc(sizeof(lknd)), *la = gt(fr->n->v, h3);
        now->v = fr->n->v;
        now->n = la->n;
        la->n = now;
        fr = fr->n;
    }
    fr=h3;
    while (fr->n)//输出链表3
    {
        printf("%d ",fr->n->v);
        fr = fr->n;
    }
    return 0;
}

8558

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 1e8;
struct lknd{
    int v;
    lknd* n;
};
int main()
{
    int g;
    lknd *h1 = (lknd *)malloc(sizeof(lknd)),*t1;
    lknd *h2 = (lknd *)malloc(sizeof(lknd)),*t2;
    lknd *h3 = (lknd *)malloc(sizeof(lknd)),*t3;
    h1->n = 0,t1=h1;
    h2->n = 0,t2=h2;
    h3->n = 0,t3=h3;
    while(cin>>g&&g)
    {
        lknd *now=(lknd*)malloc(sizeof(lknd));
        now->v=g;
        now->n=0;
        t1->n=now;
        t1=now;
    }
    lknd *now=h1->n;
    while(now)
    {
        lknd *tmp=now;
        now=now->n;
        if((tmp->v)&1)
        {
            tmp->n=t2->n;
            t2->n=tmp;
            t2=tmp;
        }
        else
        {
            tmp->n=t3->n;
            t3->n=tmp;
            t3=tmp;
        }
    }
    now=h2;
    while(now->n)
    {
        printf("%d ",now->n->v);
        now=now->n;
    }
    printf("\n");
    now=h3;
    while(now->n)
    {
        printf("%d ",now->n->v);
        now=now->n;
    }
    return 0;
}

8560

找到对应的项，系数相加即可；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 1e8;
struct lknd
{
    int x, z;
    lknd *n;
};
lknd *lt(int n, lknd *h)
{
    lknd *now = h;
    while (now->n && now->n->z <= n)
    {
        now = now->n;
    }
    return now;
}
int main()
{
    int gx, gz, n;
    lknd *h1 = (lknd *)malloc(sizeof(lknd)), *t1;
    lknd *h2 = (lknd *)malloc(sizeof(lknd)), *t2;
    lknd *h3 = (lknd *)malloc(sizeof(lknd)), *t3;
    h1->n = 0, t1 = h1;
    h2->n = 0, t2 = h2;
    h3->n = 0, t3 = h3;
    int mx = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d,%d", &gx, &gz);
        mx = max(mx, gz);
        lknd *now = (lknd *)malloc(sizeof(lknd));
        now->x = gx;
        now->z = gz;
        now->n = t1->n;
        t1->n = now;
        t1 = now;
    }
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d,%d", &gx, &gz);
        mx = max(mx, gz);
        lknd *now = (lknd *)malloc(sizeof(lknd));
        now->x = gx;
        now->z = gz;
        now->n = t2->n;
        t2->n = now;
        t2 = now;
    }
    //printf("*");
    int i = 0;
    while (i <= mx)
    {
        lknd *now = (lknd *)malloc(sizeof(lknd));
        now->x = 0;
        now->z = i++;
        now->n = t3->n;
        t3->n = now;
        t3 = now;
    }
    //printf("*");
    t1 = h1;
    t2 = h2;
    t3 = h3;
    while (t1->n)
    {
        lknd *tmp = lt(t1->n->z, h3);
        tmp->x += t1->n->x;
        t1 = t1->n;
    }
    while (t2->n)
    {
        lknd *tmp = lt(t2->n->z, h3);
        tmp->x += t2->n->x;
        t2 = t2->n;
    }
    //printf("*");
    while(t3->n)
    {
        if(t3->n->x)
        {
            printf("%d*x^%d ",t3->n->x,t3->n->z);
        }
        t3=t3->n;
    }
    return 0;
}