SDUT《数据结构与算法》专题训练 1顺序表 2链表 题解记录

前言:随着学习的深入,题目难度也水涨船高。《数据结构与算法》中的题目我打算在此完整的进行记录,以供自己和后人查询。

这一系列的语言均为C语言,其中大多数为gcc

顺序表应用1:多余元素删除之移位算法

Time Limit: 1000 ms Memory Limit: 650 KiB

Problem Description

一个长度不超过10000数据的顺序表,可能存在着一些值相同的“多余”数据元素(类型为整型),编写一个程序将“多余”的数据元素从顺序表中删除,使该表由一个“非纯表”(值相同的元素在表中可能有多个)变成一个“纯表”(值相同的元素在表中只保留第一个)。
要求:

   1、必须先定义线性表的结构与操作函数,在主函数中借助该定义与操作函数调用实现问题功能;
   2、本题的目标是熟悉顺序表的移位算法,因此题目必须要用元素的移位实现删除;

Input

第一行输入整数n,代表下面有n行输入;
之后输入n行,每行先输入整数m,之后输入m个数据,代表对应顺序表的每个元素。

Output

输出有n行,为每个顺序表删除多余元素后的结果

Sample Input

4
5 6 9 6 8 9
3 5 5 5
5 9 8 7 6 5
10 1 2 3 4 5 5 4 2 1 3

Sample Output

6 9 8
5
9 8 7 6 5
1 2 3 4 5

Reference Code

思路:先创建顺序表,把输入的内容全部存入数据表,之后再利用循环将重复元素删除。删除后,把被删除元素后面的所有元素依次前移一个即可。

#include <stdio.h>
#include <stdlib.h>
int t;
void del(int a[], int j)
{
    for (; j < t; j++)
    {
        a[j] = a[j + 1];
    }
    t--;
}

int main()
{
    int a[10001];
    int i, j, n;
    scanf("%d", &n);
    while (n--)
    {
        scanf("%d", &t);
        for (i = 0; i < t; i++)
        {
            scanf("%d", &a[i]);
        }
        for (i = 0; i < t - 1; i++)
        {
            for (j = i + 1; j < t; j++)
            {
                if (a[i] == a[j])
                {
                    del(a, j);
                    j--;
                }
            }
        }
        for (i = 0; i < t; i++)
        {
            if (i == t - 1)
            {
                printf("%d\n", a[i]);
            }
            else
            {
                printf("%d ", a[i]);
            }
        }
    }
    return 0;
}

顺序表应用2:多余元素删除之建表算法

Time Limit: 3 ms Memory Limit: 600 KiB

Problem Description

一个长度不超过10000数据的顺序表,可能存在着一些值相同的“多余”数据元素(类型为整型),编写一个程序将“多余”的数据元素从顺序表中删除,使该表由一个“非纯表”(值相同的元素在表中可能有多个)变成一个“纯表”(值相同的元素在表中只保留第一个)。
要求:

   1、必须先定义线性表的结构与操作函数,在主函数中借助该定义与操作函数调用实现问题功能;
   2、本题的目标是熟悉在顺序表原表空间基础上建新表的算法,要在原顺序表空间的基础上完成完成删除,建表过程不得开辟新的表空间;
   3、不得采用原表元素移位删除的方式。

Input

第一行输入整数n,代表下面有n行输入;
之后输入n行,每行先输入整数m,之后输入m个数据,代表对应顺序表的每个元素。

Output

输出有n行,为每个顺序表删除多余元素后的结果

Sample Input

4
5 6 9 6 8 9
3 5 5 5
5 9 8 7 6 5
10 1 2 3 4 5 5 4 2 1 3

Sample Output

6 9 8
5
9 8 7 6 5
1 2 3 4 5

Reference Code

思路:再将输入的元素依次存入顺序表的时候,对输入的元素进行判断,如果之前已经存入过顺序表,则无动作;否则再存入顺序表。

#include <stdio.h>
int create(int a[], int n)
{
    int x, i, len = 0;
    while (n--)
    {
        if (len == 0)
        {
            scanf("%d", &a[0]);
            len++;
        }
        else
        {
            scanf("%d", &x);
            for (i = 0; i < len; i++)
            {
                if (a[i] == x)
                    break;
            }
            if (i == len)
            {
                a[len] = x;
                len++;
            }
        }
    }
    return len;
}

int main()
{
    int i, t, n, len, a[10001];
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        len = create(a, n);
        for (i = 0; i < len - 1; i++)
        {
            printf("%d ", a[i]);
        }
        printf("%d\n", a[len - 1]);
    }
    return 0;
}

顺序表应用4-2:元素位置互换之逆置算法(数据改进)

Time Limit: 80 ms Memory Limit: 600 KiB

Problem Description

一个长度为len(1<=len<=1000000)的顺序表,数据元素的类型为整型,将该表分成两半,前一半有m个元素,后一半有len-m个元素(1<=m<=len),设计一个时间复杂度为O(N)、空间复杂度为O(1)的算法,改变原来的顺序表,把顺序表中原来在前的m个元素放到表的后段,后len-m个元素放到表的前段。
注意:交换操作会有多次,每次交换都是在上次交换完成后的顺序表中进行。

Input

第一行输入整数len(1<=len<=1000000),表示顺序表元素的总数;

第二行输入len个整数,作为表里依次存放的数据元素;

第三行输入整数t(1<=t<=30),表示之后要完成t次交换,每次均是在上次交换完成后的顺序表基础上实现新的交换;

之后t行,每行输入一个整数m(1<=m<=len),代表本次交换要以上次交换完成后的顺序表为基础,实现前m个元素与后len-m个元素的交换;

Output

输出一共t行,每行依次输出本次交换完成后顺序表里所有元素。

Sample Input

10
1 2 3 4 5 6 7 8 9 -1
3
2
3
5

Sample Output

3 4 5 6 7 8 9 -1 1 2
6 7 8 9 -1 1 2 3 4 5
1 2 3 4 5 6 7 8 9 -1

Reference Code

#include <stdio.h>

void reverse(int a[], int l, int r)
{
    int i, j, t;
    for (i = l, j = r; i < j; i++, j--)
    {
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

int main()
{
    int i, n, m, t;
    int a[100001];
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &m);
        reverse(a, 0, n - 1);
        reverse(a, 0, n - m - 1);
        reverse(a, n - m, n - 1);
        for (i = 0; i < n; i++)
        {
            if (i == n - 1)
                printf("%d\n", a[i]);
            else
                printf("%d ", a[i]);
        }
    }
    return 0;
}

顺序表应用5:有序顺序表归并

Time Limit: 100 ms Memory Limit: 880 KiB

Problem Description

已知顺序表A与B是两个有序的顺序表,其中存放的数据元素皆为普通整型,将A与B表归并为C表,要求C表包含了A、B表里所有元素,并且C表仍然保持有序。

Input

输入分为三行:
第一行输入m、n(1<=m,n<=10000)的值,即为表A、B的元素个数;
第二行输入m个有序的整数,即为表A的每一个元素;
第三行输入n个有序的整数,即为表B的每一个元素;

Output

输出为一行,即将表A、B合并为表C后,依次输出表C所存放的元素。

Sample Input

5 3
1 3 5 6 9
2 4 10

Sample Output

1 2 3 4 5 6 9 10

Reference Code

这道题实际上很简单,顺序表的链式存储结构,就是链表的归并,之前有记录过,为了连续性还是记录一下吧。

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

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

struct node * merge(struct node *head1,struct node *head2)
{
    struct node *p1,*p2,*tail;
    p1 = head1->next;
    p2 = head2->next;
    tail = head1;
    free(head2);
    while (p1&&p2)
    {
        if (p1->data < p2->data)
        {
            tail->next = p1;
            tail = p1;
            p1 = p1->next;
        }
        else
        {
            tail->next = p2;
            tail = p2;
            p2 = p2->next;
        }
    }
    if (p1)
    {
        tail->next = p1;
    }
    else
    {
        tail->next = p2;
    }
    return (head1);
}

void print(struct node *head)
{
    head = head->next;
    while (head)
    {
        if (head->next)
        {
            printf("%d ",head->data);
        }
        else
        {
            printf("%d\n",head->data);
        }
        head = head->next;
    }
}

int main()
{
    int m,n,x,i;
    struct node *head1,*head2,*p,*q,*tail,*head;
    scanf("%d %d",&m,&n);
    head1 = (struct node *)malloc(sizeof(struct node));
    head2 = (struct node *)malloc(sizeof(struct node));
    head1->next = NULL;
    head2->next = NULL;
    tail = head1;
    for (i=0;i<m;i++)
    {
        p = (struct node *)malloc(sizeof(struct node));
        scanf("%d",&p->data);
        p->next = NULL;
        tail->next = p;
        tail = p;
    }
    tail = head2;
    for (i=0;i<n;i++)
    {
        p = (struct node *)malloc(sizeof(struct node));
        scanf("%d",&p->data);
        p->next = NULL;
        tail->next = p;
        tail = p;
    }
    head = merge(head1,head2);
    print(head);
    return 0;
}

顺序表应用6:有序顺序表查询

Time Limit: 1000 ms Memory Limit: 4096 KiB

Problem Description

顺序表内按照由小到大的次序存放着n个互不相同的整数,任意输入一个整数,判断该整数在顺序表中是否存在。如果在顺序表中存在该整数,输出其在表中的序号;否则输出“No Found!"。

Input

第一行输入整数n (1 <= n <= 100000),表示顺序表的元素个数;
第二行依次输入n个各不相同的有序非负整数,代表表里的元素;
第三行输入整数t (1 <= t <= 100000),代表要查询的次数;
第四行依次输入t个非负整数,代表每次要查询的数值。

保证所有输入的数都在 int 范围内。

Output

输出t行,代表t次查询的结果,如果找到在本行输出该元素在表中的位置,否则本行输出No Found!

Sample Input

10
1 22 33 55 63 70 74 79 80 87
4
55 10 2 87

Sample Output

4
No Found!
No Found!
10

Reference Code

呃...这不就是二分查找换了个皮吗...当时想了很久,实际上并不难。

#include<stdio.h>
#include<stdlib.h>
int find(int a[],int left,int right,int x)
{
    if (left<=right)
    {
        int mid=(left+right)/2;
        if (a[mid]==x) return mid;
        if (a[mid]<x) return find(a,mid+1,right,x);
        if (a[mid]>x) return find(a,left,mid-1,x);
    }
    else return -1;
}

int main()
{
    int n,t,x,i,a[100001];
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d",&x);
        int ans = find(a,1,n,x);
        if (ans!=-1) printf("%d\n",ans);
        else printf("No Found!\n");
    }
    return 0;
}

顺序表应用7:最大子段和之分治递归法

Time Limit: 10 ms Memory Limit: 400 KiB

Problem Description

给定n(1<=n<=50000)个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0,依此定义,所求的最优值为: Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n。 例如,当(a[1],a[2],a[3],a[4],a[5],a[6])=(-2,11,-4,13,-5,-2)时,最大子段和为20。

注意:本题目要求用分治递归法求解,除了需要输出最大子段和的值之外,还需要输出求得该结果所需的递归调用总次数。

递归调用总次数的获得,可以参考以下求菲波那切数列的代码段中全局变量count的用法:

#include
int count=0;
int main()
{
    int n,m;
    int fib(int n);
    scanf("%d",&n);
    m=fib(n);
    printf("%d %d\n",m,count);
    return 0;
}
int fib(int n)
{
    int s;
    count++;
    if((n==1)||(n==0)) return 1;
    else s=fib(n-1)+fib(n-2);
    return s;
}

Input

第一行输入整数n(1<=n<=50000),表示整数序列中的数据元素个数;

第二行依次输入n个整数,对应顺序表中存放的每个数据元素值。

Output

一行输出两个整数,之间以空格间隔输出:

第一个整数为所求的最大子段和;

第二个整数为用分治递归法求解最大子段和时,递归函数被调用的总次数。

Sample Input

6
-2 11 -4 13 -5 -2

Sample Output

20 11

Reference Code

#include<stdio.h>
int a[50001],count = 0,ans=0;
int max(int a,int b)
{
    int c;
    c = a>b?a:b;//三目运算符
    return c;
}

int findMax(int l,int r)
{
    int i,sum=0;
    count++;
    if (l==r)
    {
        if (a[l]>=0) sum=a[l];
        else sum=0;
    }
    else
    {
        int mid = (l+r)/2;
        int leftsum = findMax(l,mid);
        int rightsum = findMax(mid+1,r);
        int s1,s2,s;
        s1=s=0;
        for (i=mid;i>=l;i--)
        {
            s += a[i];
            if (s>s1) s1=s;
        }
        s2=s=0;
        for (i=mid+1;i<=r;i++)
        {
            s+=a[i];
            if (s>s2)
            {
                s2=s;
            }
        }
        sum=s1+s2;
        sum=max(sum,leftsum);
        sum=max(sum,rightsum);
    }
    return sum;
}

int main()
{
    int i,n,ans;
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    ans = findMax(1,n);
    printf("%d %d\n",ans,count);
    return 0;
}

顺序表应用8:最大子段和之动态规划法

Time Limit: 5 ms Memory Limit: 500 KiB

Problem Description

给定n(1<=n<=100000)个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0,依此定义,所求的最优值为: Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n。 例如,当(a[1],a[2],a[3],a[4],a[5],a[6])=(-2,11,-4,13,-5,-2)时,最大子段和为20。

注意:本题目要求用动态规划法求解,只需要输出最大子段和的值。

Input

第一行输入整数n(1<=n<=100000),表示整数序列中的数据元素个数;

第二行依次输入n个整数,对应顺序表中存放的每个数据元素值。

Output

输出所求的最大子段和

Sample Input

6
-2 11 -4 13 -5 -2

Sample Output

20

Reference Code

#include <stdio.h>
int main()
{
    int i, t = 0, n, a[100001], max = 0;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (i = 1; i <= n; i++)
    {
        if (t > 0)
            t += a[i];
        else
            t = a[i];
        if (t > max)
            max = t;
    }
    printf("%d\n", max);
    return 0;
}

华丽的分割线后,顺序表部分的题目结束,下面是专题训练2 链表中的题目。

训练2中有大量题目跟之前的C语言实验记录重合,重复的就不在此记录了(小声bb,本来打算完整记录的,到这里,因为大量重复放弃了QAQ)

原记录链接:https://blog.xmgspace.me/archives/sdut-experiments-c-2-12.html


数据结构实验之链表八:Farey序列

Time Limit: 10 ms Memory Limit: 600 KiB

Problem Description

Farey序列是一个这样的序列:其第一级序列定义为(0/1,1/1),这一序列扩展到第二级形成序列(0/1,1/2,1/1),扩展到第三极形成序列(0/1,1/3,1/2,2/3,1/1),扩展到第四级则形成序列(0/1,1/4,1/3,1/2,2/3,3/4,1/1)。以后在每一级n,如果上一级的任何两个相邻分数a/c与b/d满足(c+d)<=n,就将一个新的分数(a+b)/(c+d)插入在两个分数之间。对于给定的n值,依次输出其第n级序列所包含的每一个分数。

Input

输入一个整数n(0<n<=100)

Output

依次输出第n级序列所包含的每一个分数,每行输出10个分数,同一行的两个相邻分数间隔一个制表符的距离。

Sample Input

6

Sample Output

0/1   1/6   1/5   1/4   1/3   2/5   1/2   3/5   2/3   3/4
4/5   5/6   1/1

Reference Code

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

struct node
{
    int a, b;
    struct node *next;
};

void create(struct node *head, int n)
{
    struct node *t, *p, *q;
    t = head->next;
    while (t->next)
    {
        p = t->next;
        if (t->b + p->b <= n)
        {
            q = (struct node *)malloc(sizeof(struct node));
            q->a = p->a + t->a;
            q->b = p->b + t->b;
            t->next = q;
            q->next = p;
        }
        t = t->next;
    }
}

void print(struct node *head)
{
    head = head->next;
    int count = 0;
    while (head)
    {
        count++;
        if (count % 10 != 0)
            printf("%d/%d\t", head->a, head->b);
        else
            printf("%d/%d\n", head->a, head->b);
        head = head->next;
    }
}

int main()
{
    int i, n;
    scanf("%d", &n);
    struct node *head, *p, *q;
    head = (struct node *)malloc(sizeof(struct node));
    p = (struct node *)malloc(sizeof(struct node));
    q = (struct node *)malloc(sizeof(struct node));
    p->a = 0;
    p->b = 1;
    q->a = 1;
    q->b = 1;
    head->next = p;
    p->next = q;
    q->next = NULL;
    for (i = 2; i <= n; i++)
    {
        create(head, i);
    }
    print(head);
    return 0;
}
~~End Of File~~

本文永久链接:https://blog.xmgspace.me/archives/sdut-experiments-data-structure-12.html

本文文章标题:SDUT《数据结构与算法》专题训练 1顺序表 2链表 题解记录

本站欢迎转载与引用~但您需要注明文章标题与链接,并表明转载/引用自Xiaomage's Blog。

授权协议:署名-非商业性使用-相同方式共享 4.0 国际(CC BY 4.0)

标签:数据结构 , 顺序表 , 链表

还没有人评论哦,还不快抢沙发~

添加新评论

i_f01.pngi_f02.pngi_f03.pngi_f04.pngi_f05.pngi_f06.pngi_f07.pngi_f08.pngi_f09.pngi_f10.pngi_f11.pngi_f12.pngi_f13.pngi_f14.pngi_f15.pngi_f16.pngi_f17.pngi_f18.pngi_f19.pngi_f20.pngi_f21.pngi_f22.pngi_f23.pngi_f24.pngi_f25.pngi_f26.pngi_f27.pngi_f28.pngi_f29.pngi_f30.pngi_f31.pngi_f32.pngi_f33.png