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

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

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

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

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

Time Limit: 1000 ms Memory Limit: 650 KiB

Problem Description

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

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

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 arr[], int j)
{
  for (; j < t; j++)
  {
    arr[j] = arr[j + 1];
  }
  t--;
}
int main()
{
  int i, j, n;
  scanf("%d", &n);
  int arr[10000];
  while (n--)
  {
    scanf("%d", &t);
    for (i = 0; i < t; i++)
    {
      scanf("%d", &arr[i]);
    }
    for (i = 0; i < t - 1; i++)
    {
      for (j = i + 1; j < t; j++)
      {
        if (arr[i] == arr[j])
        {
          del(arr, j);
          j--;
        }
      }
    }
    for (i = 0; i < t; i++)
    {
      if (i != t - 1)
      {
        printf("%d ", arr[i]);
      }
      else
      {
        printf("%d\n", arr[i]);
      }
    }
  }
}


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

Time Limit: 3 ms Memory Limit: 600 KiB

Problem Description

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

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

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 len;
int arr[10001];
int main()
{
  int n;
  scanf("%d", &n);
  while (n--)
  {
    int m, i, l = 1, t, len = 0;
    scanf("%d", &m);
    while (m--)
    {
      scanf("%d", &t);
      if (len == 0)
      {
        arr[0] = t;
        len++;
      }
      else
      {
        for (i = 0; i < len; i++)
        {
          if (arr[i] == t)
          {
            break;
          }
        }
        if (i == len)
        {
          arr[i] = t;
          len++;
        }
      }
    }
    for (i = 0; i < len; i++)
    {
      if (i != len - 1)
      {
        printf("%d ", arr[i]);
      }
      else
      {
        printf("%d\n", arr[i]);
      }
    }
  }
}

顺序表应用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>
#include <stdlib.h>
void reverse(int l, int r, int arr[])
{
  int i, j, t;
  for (i = l, j = r; i < j; i++, j--)
  {
    t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
  }
}
int main()
{
  int i, n, m, arr[1000000];
  scanf("%d", &n);
  for (i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }
  scanf("%d", &m);
  while (m--)
  {
    int num;
    scanf("%d", &num);
    reverse(0, n - 1, arr);
    reverse(0, n - 1 - num, arr);
    reverse(n - num, n - 1, arr);
    for (i = 0; i < n; i++)
    {
      if (i != n - 1)
      {
        printf("%d ", arr[i]);
      }
      else
      {
        printf("%d\n", arr[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 *create(int n)
{
  struct node *head, *p, *tail;
  head = (struct node *)malloc(sizeof(struct node));
  head->next = NULL;
  tail = head;
  for (int i = 0; i < n; i++)
  {
    p = (struct node *)malloc(sizeof(struct node));
    scanf("%d", &p->data);
    p->next = NULL;
    tail->next = p;
    tail = tail->next;
  }
  return head;
}
struct node *merge(struct node *head1, struct node *head2)
{
  struct node *p1, *p2, *tail;
  p1 = head1->next;
  p2 = head2->next;
  tail = head1;
  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->next)
  {
    printf("%d ", head->data);
    head = head->next;
  }
  printf("%d\n", head->data);
}
int main()
{
  int i, m, n, t;
  scanf("%d %d", &m, &n);
  struct node *head1, *head2, *head;
  head1 = create(m);
  head2 = create(n);
  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 i, n, m, arr[100000], t, ans;
  scanf("%d", &n);
  for (i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }
  scanf("%d", &m);
  for (i = 0; i < m; i++)
  {
    scanf("%d", &t);
    ans = find(arr, 0, n - 1, t);
    if (ans == -1)
      printf("No Found!\n");
    else
      printf("%d\n", ans + 1);
  }
  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;
}

H - 数据结构上机测试1:顺序表的应用

Description

在长度为n(n<1000)的顺序表中可能存在着一些值相同的“多余”数据元素(类型为整型),编写一个程序将“多余”的数据元素从顺序表中删除,使该表由一个“非纯表”(值相同的元素在表中可能有多个)变成一个“纯表”(值相同的元素在表中只能有一个)。

Input

第一行输入表的长度n;
第二行依次输入顺序表初始存放的n个元素值。

Output

第一行输出完成多余元素删除以后顺序表的元素个数;
第二行依次输出完成删除后的顺序表元素。

Sample

Input
12
5 2 5 3 3 4 2 5 7 5 4 3
Output
5
5 2 3 4 7

Hint

用尽可能少的时间和辅助存储空间。

Reference Code

#include <stdio.h>
#include <stdlib.h>
int main()
{
  int i, j, k, n, m, flag;
  int a[1000], b[1000];
  scanf("%d", &n);
  for (i = 0; i < n; i++)
  {
    scanf("%d", &a[i]);
  }
  b[0] = a[0];
  m = 1;
  for (i = 0; i < n; i++)
  {
    flag = 1;
    for (j = 0; j < m; j++)
    {
      if (a[i] == b[j])
      {
        flag = 0;
        break;
      }
    }
    if (flag == 1)
    {
      b[m] = a[i];
      m++;
    }
  }
  printf("%d\n", m);
  for (i = 0; i < m - 1; i++)
  {
    printf("%d ", b[i]);
  }
  printf("%d\n", b[m - 1]);
  return 0;
}

I - 顺序表应用3:元素位置互换之移位算法

Description

一个长度为len(1<=len<=1000000)的顺序表,数据元素的类型为整型,将该表分成两半,前一半有m个元素,后一半有len-m个元素(1<=m<=len),借助元素移位的方式,设计一个空间复杂度为O(1)的算法,改变原来的顺序表,把顺序表中原来在前的m个元素放到表的后段,后len-m个元素放到表的前段。

注意:先将顺序表元素调整为符合要求的内容后,再做输出,输出过程只能用一个循环语句实现,不能分成两个部分。

Input

第一行输入整数n,代表下面有n行输入;

之后输入n行,每行先输入整数len与整数m(分别代表本表的元素总数与前半表的元素个数),之后输入len个整数,代表对应顺序表的每个元素。

Output

输出有n行,为每个顺序表前m个元素与后(len-m)个元素交换后的结果

Sample

Input
2
10 3 1 2 3 4 5 6 7 8 9 10
5 3 10 30 20 50 80
Output
4 5 6 7 8 9 10 1 2 3
50 80 10 30 20

Hint

注意:先将顺序表元素调整为符合要求的内容后,再做输出,输出过程只能在一次循环中完成,不能分成两个部分输出。

Reference Code

//待整理

J - 顺序表应用4:元素位置互换之逆置算法

Description

一个长度为len(1<=len<=1000000)的顺序表,数据元素的类型为整型,将该表分成两半,前一半有m个元素,后一半有len-m个元素(1<=m<=len),设计一个时间复杂度为O(N)、空间复杂度为O(1)的算法,改变原来的顺序表,把顺序表中原来在前的m个元素放到表的后段,后len-m个元素放到表的前段。

注意:先将顺序表元素调整为符合要求的内容后,再做输出,输出过程只能用一个循环语句实现,不能分成两个部分。

Input

第一行输入整数n,代表下面有n行输入;

之后输入n行,每行先输入整数len与整数m(分别代表本表的元素总数与前半表的元素个数),之后输入len个整数,代表对应顺序表的每个元素。

Output

输出有n行,为每个顺序表前m个元素与后(len-m)个元素交换后的结果

Sample

Input
2
10 3 1 2 3 4 5 6 7 8 9 10
5 3 10 30 20 50 80
Output
4 5 6 7 8 9 10 1 2 3
50 80 10 30 20

Hint

注意:先将顺序表元素调整为符合要求的内容后,再做输出,输出过程只能用一个循环语句实现,不能分成两个部分。

Reference Code

//待整理

华丽的分割线后,顺序表部分的题目结束,下面是专题训练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;
}

本文永久链接:https://blog.xmgspace.me/archives/sdut-experiments-data-structure-12.html
本文文章标题:SDUT《数据结构与算法》专题训练 1顺序表 2链表 题解记录
如文章内无特殊说明,只要您标明转载/引用自Xiaomage's Blog,您就可以自由的转载/引用文章。禁止CSDN/采集站采集转载。
授权协议:署名-非商业性使用-相同方式共享 4.0 国际(CC BY 4.0)
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇