SDUT《数据结构与算法》专题训练7查找 8排序

期末考试马上就要来了，这是最后一次机测了！之前挖的坑终于要有时间填咯~这周末开始填坑，记录干货

数据结构实验之查找一：二叉排序树

Time Limit: 400 ms Memory Limit: 65536 KiB

Problem Description

对应给定的一个序列可以唯一确定一棵二叉排序树。然而，一棵给定的二叉排序树却可以由多种不同的序列得到。例如分别按照序列{3,1,4}和{3,4,1}插入初始为空的二叉排序树，都得到一样的结果。你的任务书对于输入的各种序列，判断它们是否能生成一样的二叉排序树。

Input

输入包含若干组测试数据。每组数据的第1行给出两个正整数N (n < = 10)和L，分别是输入序列的元素个数和需要比较的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列生成一颗二叉排序树。随后L行，每行给出N个元素，属于L个需要检查的序列。
简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。

Output

对每一组需要检查的序列，如果其生成的二叉排序树跟初始序列生成的二叉排序树一样，则输出"Yes"，否则输出"No"。

Sample Input

Sample Output

Yes
No
No

Reference Code

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

struct node
{
  struct node *l, *r;
  int data;
} node;

struct node *newNode()
{
  struct node *t;
  t = (struct node *)malloc(sizeof(node));
  t->l = t->r = NULL;
  return t;
}

struct node *build(struct node *t, int x)
{
  if (t == NULL)
  {
    t = newNode();
    t->data = x;
    return t;
  }
  if (x > t->data)
  {
    t->r = build(t->r, x);
    return t;
  }
  else
  {
    t->l = build(t->l, x);
    return t;
  }
}

int judge(struct node *t1, struct node *t2)
{
  if (t1 == NULL || t2 == NULL)
  {
    if (t1 == NULL && t2 == NULL)
      return 1;
    else
      return 0;
  }
  if (t1->data == t2->data && judge(t1->l, t2->l) && judge(t1->r, t2->r))
    return 1;
  return 0;
}

void del(struct node *t)
{
  if (t)
  {
    del(t->l);
    del(t->r);
    free(t);
  }
}

int main()
{
  struct node *t1, *t2;
  int m, n, i, x;
  while (scanf("%d", &n) != EOF && n)
  {
    scanf("%d", &m);
    t1 = NULL;
    for (i = 0; i < n; i++)
    {
      scanf("%d", &x);
      t1 = build(t1, x);
    }
    while (m--)
    {
      t2 = NULL;
      for (i = 0; i < n; i++)
      {
        scanf("%d", &x);
        t2 = build(t2, x);
      }
      if (judge(t1, t2))
        printf("Yes\n");
      else
        printf("No\n");
      del(t2);
    }
    del(t1);
  }
  return 0;
}

数据结构实验之查找二：平衡二叉树

Time Limit: 400 ms Memory Limit: 65536 KiB

Problem Description

根据给定的输入序列建立一棵平衡二叉树，求出建立的平衡二叉树的树根。

Input

输入一组测试数据。数据的第1行给出一个正整数N(n <= 20)，N表示输入序列的元素个数；第2行给出N个正整数，按数据给定顺序建立平衡二叉树。

Output

输出平衡二叉树的树根。

Sample Input

5
88 70 61 96 120

Sample Output

Reference Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
  int data;
  int deep;
  struct node *l, *r;
};

int n;

int max(int a, int b)
{
  if (a > b)
    return a;
  else
    return b;
}

int deept(struct node *root)
{
  if (root == NULL)
    return 0;
  return root->deep;
}

struct node *ll(struct node *p)
{
  struct node *q = p->l;
  p->l = q->r;
  q->r = p;
  p->deep = max(deept(p->l), deept(p->r)) + 1;
  q->deep = max(p->deep, deept(q->l)) + 1;
  p = q;
  return p;
}

struct node *rr(struct node *p)
{
  struct node *q = p->r;
  p->r = q->l;
  q->l = p;
  p->deep = max(deept(p->l), deept(p->r)) + 1;
  q->deep = max(deept(q->r), p->deep) + 1;
  p = q;
  return p;
}

struct node *lr(struct node *p)
{
  p->l = rr(p->l);
  return ll(p);
}

struct node *rl(struct node *p)
{
  p->r = ll(p->r);
  return rr(p);
}

struct node *creat(struct node *root, int x)
{
  if (root == NULL)
  {
    root = (struct node *)malloc(sizeof(struct node));
    root->data = x;
    root->deep = 1;
    root->l = NULL;
    root->r = NULL;
  }
  else if (x < root->data)
  {
    root->l = creat(root->l, x);
    if (deept(root->l) - deept(root->r) > 1)
    {
      if (x < root->l->data)
        root = ll(root);
      else
        root = lr(root);
    }
  }
  else if (x > root->data)
  {
    root->r = creat(root->r, x);
    if (deept(root->r) - deept(root->l) > 1)
    {
      if (x < root->r->data)
        root = rl(root);
      else
        root = rr(root);
    }
  }
  root->deep = max(deept(root->l), deept(root->r)) + 1;
  return root;
};

int main()
{
  scanf("%d", &n);
  struct node *root = NULL;
  while (n--)
  {
    int x;
    scanf("%d", &x);
    root = creat(root, x);
  }
  printf("%d\n", root->data);
  return 0;
}

数据结构实验之查找三：树的种类统计

Time Limit: 400 ms Memory Limit: 65536 KiB

Problem Description

随着卫星成像技术的应用，自然资源研究机构可以识别每一个棵树的种类。请编写程序帮助研究人员统计每种树的数量，计算每种树占总数的百分比。

Input

输入一组测试数据。数据的第1行给出一个正整数N (n <= 100000)，N表示树的数量；随后N行，每行给出卫星观测到的一棵树的种类名称，树的名称是一个不超过20个字符的字符串，字符串由英文字母和空格组成，不区分大小写。

Output

按字典序输出各种树的种类名称和它占的百分比，中间以空格间隔，小数点后保留两位小数。

Sample Input

2
This is an Appletree
this is an appletree

Sample Output

this is an appletree 100.00%

Reference Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
  char data[30];
  struct node *l, *r;
  int num;
};
char a[30];
int n;
struct node *creat(struct node *t)
{
  if (t == NULL)
  {
    t = (struct node *)malloc(sizeof(struct node));
    t->num = 1;
    t->l = NULL;
    t->r = NULL;
    strcpy(t->data, a);
  }
  else
  {
    if (strcmp(t->data, a) == 0)
    {
      t->num++;
    }
    else if (strcmp(t->data, a) > 0)
    {
      t->l = creat(t->l);
    }
    else
    {
      t->r = creat(t->r);
    }
  }
  return t;
};
void f(struct node *t)
{
  if (t)
  {
    f(t->l);
    printf("%s %.2lf%%\n", t->data, t->num * 1.0 * 100 / n);
    f(t->r);
  }
}
int main()
{

  scanf("%d ", &n);
  int i, j, len;
  struct node *t = NULL;
  for (i = 1; i <= n; i++)
  {
    gets(a);
    len = strlen(a);
    for (j = 0; j < len; j++)
    {
      if (a[j] >= 'A' && a[j] <= 'Z')
      {
        a[j] = a[j] + 32;
      }
    }
    t = creat(t);
  }
  f(t);
  return 0;
}

数据结构实验之查找四：二分查找

Time Limit: 30 ms Memory Limit: 65536 KiB

Problem Description

在一个给定的无重复元素的递增序列里，查找与给定关键字相同的元素，若存在则输出找到的位置,不存在输出-1。

Input

一组输入数据，输入数据第一行首先输入两个正整数n ( n < = 10^6 )和m ( m < = 10^4 )，n是数组中数据元素个数，随后连续输入n个正整数，输入的数据保证数列递增。
随后m行输入m个待查找的关键字key

Output

若在给定的序列中能够找到与关键字key相等的元素，则输出位序(序号从0开始)，否则输出-1。

Sample Input

8 3
4 6 8 9 13 20 21 22
6
8
17

Sample Output

1
2
-1

Reference Code

#include <stdio.h>
int a[1000000];

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

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

数据结构实验之查找五：平方之哈希表

Time Limit: 400 ms Memory Limit: 65536 KiB

Problem Description

给定的一组无重复数据的正整数，根据给定的哈希函数建立其对应hash表，哈希函数是H(Key)=Key%P，P是哈希表表长，P是素数，处理冲突的方法采用平方探测方法，增量di=±i^2,i=1,2,3,...,m-1

Input

输入包含多组测试数据，到 EOF 结束。

每组数据的第1行给出两个正整数N(N <= 500)和P(P >= 2N的最小素数)，N是要插入到哈希表的元素个数，P是哈希表表长；第2行给出N个无重复元素的正整数，数据之间用空格间隔。

Output

按输入数据的顺序输出各数在哈希表中的存储位置 (hash表下标从0开始)，数据之间以空格间隔，以平方探测方法处理冲突。

Sample Input

4 11
10 6 4 15
9 11
47 7 29 11 9 84 54 20 30

Sample Output

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

Reference Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
  int n, p;
  int Hash[5005], len[5005];
  int i, id, x, k;
  while (scanf("%d %d", &n, &p) != EOF)
  {
    k = 0;
    memset(Hash, -1, sizeof(Hash));
    for (i = 1; i <= n; i++)
    {
      scanf("%d", &x);
      id = x % p;
      if (Hash[id] == -1)
      {
        Hash[id] = x;
        len[k++] = id;
      }
      else
      {
        int mid = id;
        int f = 1;
        int l = 1;
        while (Hash[mid] != -1)
        {
          mid = (id + f * l * l) % p;
          f = f * -1;
          if (f == 1)
            l++;
        }
        Hash[mid] = x;
        len[k++] = mid;
      }
    }
    for (i = 0; i < k; i++)
    {
      if (i != k - 1)
        printf("%d ", len[i]);
      else
        printf("%d\n", len[i]);
    }
  }
  return 0;
}

数据结构实验之查找六：顺序查找

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

在一个给定的无序序列里，查找与给定关键字相同的元素，若存在则输出找到的元素在序列中的位序和需要进行的比较次数,不存在则输出"No"，序列位序从1到n,要求查找从最后一个元素开始,序列中无重复元素。

Input

连续多组数据输入，每组输入数据第一行首先输入两个整数 n (n <= 10^6) 和 k (1 <= k <= 10^7)，n是数组长度，k是待查找的关键字，然后连续输入n个整数 ai (1 <= ai <= 10^7)，数据间以空格间隔。

Output

若存在则输出元素在序列中的位序和比较次数,不存在则输出No。

Sample Input

5 9
4 6 8 9 13
7 4
-1 3 2 5 4 6 9 
20 90
4 6 8 9 13 17 51 52 54 59 62 66 76 78 80 85 88 17 20 21

Sample Output

4 2
5 3
No

Hint

本题数据量较大，如果你使用 C++ 的 cin 读入，建议在 main 函数开头加入一行 ios::sync_with_stdio(false); 以防止读入超时。

Reference Code

#include<stdio.h>
int main()
{
    int i,n,m,k,t;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        t=-1;
        for(i=0; i<n; i++)
        {
            scanf("%d",&k);
            if(k==m)
            {
                t=i;
            }
        }
        if(t==-1)
            printf("No\n");
        else
            printf("%d %d\n",t+1,n-t);
    }
}

数据结构实验之查找七：线性之哈希表

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

根据给定的一系列整数关键字和素数p,用除留余数法定义hash函数H(Key)=Key%p,将关键字映射到长度为p的哈希表中，用线性探测法解决冲突。重复关键字放在hash表中的同一位置。

Input

连续输入多组数据，每组输入数据第一行为两个正整数N(N <= 1500)和p(p >= N的最小素数)，N是关键字总数，p是hash表长度，第2行给出N个正整数关键字，数字间以空格间隔。

Output

输出每个关键字在hash表中的位置，以空格间隔。注意最后一个数字后面不要有空格。

Sample Input

5 5
21 21 21 21 21
4 5
24 15 61 88
4 5
24 39 61 15
5 5
24 39 61 15 39

Sample Output

Reference Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
  int n, p;
  int Hash[5005], len[5005];
  int i, id, x, k;
  while (scanf("%d %d", &n, &p) != EOF)
  {
    k = 0;
    memset(Hash, -1, sizeof(Hash));
    for (i = 1; i <= n; i++)
    {
      scanf("%d", &x);
      id = x % p;
      if (Hash[id] == -1 || Hash[id] == x)
      {
        Hash[id] = x;
        len[k++] = id;
      }
      else
      {
        while (!(Hash[id] == -1 || Hash[id] == x))
        {
          id = (id + 1) % p;
        }
        Hash[id] = x;
        len[k++] = id;
      }
    }
    for (i = 0; i < k; i++)
    {
      if (i != k - 1)
        printf("%d ", len[i]);
      else
        printf("%d\n", len[i]);
    }
  }
  return 0;
}

数据结构实验之排序一：一趟快排

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定N个长整型范围内的整数，要求输出以给定数据中第一个数为枢轴进行一趟快速排序之后的结果。

Input

连续输入多组数据，每组输入数据第一行给出正整数N(N < = 10^5)，随后给出N个长整型范围内的整数，数字间以空格分隔。

Output

输出一趟快速排序后的结果，数字间以一个空格间隔，行末不得有多余空格。

Sample Input

8
49 38 65 97 76 13 27 49

Sample Output

27 38 13 49 76 97 65 49

Reference Code

#include <stdio.h>
void qsort(int a[], int l, int r)
{
  int x = a[l], i = l, j = r;
  if (l >= r)
    return;
  while (i < j)
  {
    while (i < j && a[j] >= x)
      j--;
    a[i] = a[j];
    while (i < j && a[i] <= x)
      i++;
    a[j] = a[i];
  }
  a[i] = x;
}

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

数据结构实验之排序二：交换排序

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

冒泡排序和快速排序都是基于"交换"进行的排序方法，你的任务是对题目给定的N个（长整型范围内的）整数从小到大排序，输出用冒泡和快排对这N个数排序分别需要进行的数据交换次数。

Input

连续多组输入数据，每组数据第一行给出正整数N(N ≤ 10^5)，随后给出N个整数，数字间以空格分隔。

Output

输出数据占一行，代表冒泡排序和快速排序进行排序分别需要的交换次数，数字间以1个空格分隔，行末不得有多余空格。

Sample Input

8
49 38 65 97 76 13 27 49

Sample Output

15 9

Hint

注意：数据相等时不做交换

Reference Code

#include <stdio.h>
int count1 = 0, count2 = 0;
void qsort(int a[], int l, int r)
{
  int x = a[l], i = l, j = r;
  if (l >= r)
    return;
  while (i < j)
  {
    while (i < j && a[j] >= x)
      j--;
    if (a[i] != a[j])
    {
      count2++;
    }
    a[i] = a[j];
    while (i < j && a[i] <= x)
      i++;
    if (a[i] != a[j])
    {
      count2++;
    }
    a[j] = a[i];
  }
  a[i] = x;
  qsort(a, l, i - 1);
  qsort(a, i + 1, r);
}

int main()
{
  int n, i, j, temp, t;
  while (~scanf("%d", &n))
  {
    count1 = count2 = 0;
    int a[100001], a1[100001];
    for (i = 0; i < n; i++)
    {
      scanf("%d", &t);
      a[i] = t;
      a1[i] = t;
    }
    qsort(a, 0, n - 1);
    for (i = 0; i < n - 1; i++)
    {
      for (j = 0; j < n - i - 1; j++)
      {
        if (a1[j] > a1[j + 1])
        {
          temp = a1[j];
          a1[j] = a1[j + 1];
          a1[j + 1] = temp;
          count1++;
        }
      }
    }
    printf("%d %d\n", count1, count2);
  }
  return 0;
}

数据结构实验之排序三：bucket sort

Time Limit: 250 ms Memory Limit: 65536 KiB

Problem Description

根据人口普查结果，知道目前淄博市大约500万人口，你的任务是帮助人口普查办公室按年龄递增的顺序输出每个年龄有多少人，其中不满1周岁的按0岁计算，1到2周岁的按1岁计算，依次类推，大于等于100岁的老人全部按100岁计算。

Input

输入第一行给出一个正整数N(<=5000000)，随后连续给出N个整数表示每个人的年龄，数字间以空格分隔。

Output

按年龄递增的顺序输出每个年龄的人口数，人口数为0的不输出，每个年龄占一行，数字间以一个空格分隔，行末不得有多余空格或空行。

Sample Input

10
16 71 17 16 18 18 19 18 19 20

Sample Output

Reference Code

#include <stdio.h>
#include <string.h>
int main()
{
  int i, n, a[105];
  double x;
  int x1;
  while (~scanf("%d", &n))
  {
    if (n == 0)
      continue;
    memset(a, 0, sizeof(a));
    for (i = 0; i < n; i++)
    {
      scanf("%lf", &x);
      if (x < 1.0)
      {
        a[0]++;
      }
      else if (x > 100.0)
      {
        a[100]++;
      }
      else
      {
        x1 = (int)x;
        a[x1]++;
      }
    }
    for (i = 0; i < 101; i++)
    {
      if (a[i] != 0)
      {
        printf("%d %d\n", i, a[i]);
      }
    }
  }
  return 0;
}

数据结构实验之排序四：寻找大富翁

Time Limit: 200 ms Memory Limit: 512 KiB

Problem Description

2015胡润全球财富榜调查显示，个人资产在1000万以上的高净值人群达到200万人，假设给出N个人的个人资产值，请你快速找出排前M位的大富翁。

Input

首先输入两个正整数N( N ≤ 10^6)和M(M ≤ 10)，其中N为总人数，M为需要找出的大富翁数目，接下来给出N个人的个人资产，以万元为单位，个人资产数字为正整数，数字间以空格分隔。

Output

一行数据，按降序输出资产排前M位的大富翁的个人资产值，数字间以空格分隔，行末不得有多余空格。

Sample Input

6 3
12 6 56 23 188 60

Sample Output

188 60 56

Hint

请用堆排序完成。

Reference Code

#include <stdio.h>
#include <stdlib.h>
int a[15];
void sort(int s, int m) //建立一个小顶堆
{
  int key = s;
  int l = s * 2;     //左孩子；
  int r = s * 2 + 1; //右孩子；
  if (s <= m / 2)    //从m/2的小开始
  {
    if (l <= m && a[key] > a[l])
    //如果根比左子树根节点大，将左子树根节点让key保存
    {
      key = l;
    }
    if (r <= m && a[key] > a[r])
    //右子树根节点也是一样的
    {
      key = r;
    }
    //以上得到l,r中的最小值
    if (s != key) //说明key变成了别的
    {
      int t = a[s];
      a[s] = a[key];
      a[key] = t;
      //根节点与左或右节点进行交换
      sort(key, m);
      //调整的是以s为根的整棵子树
    }
  }
}

int main()
{
  int n, m, i, d, x;
  scanf("%d %d", &n, &m);
  for (i = 1; i <= m; i++)
  {
    scanf("%d", &a[i]);
  }
  for (i = m / 2; i > 0; i--)
  {
    sort(i, m);
  }
  for (i = m + 1; i <= n; i++)
  {
    scanf("%d", &x);
    if (x > a[1])
    //更新小顶堆
    {
      a[1] = x;
      sort(1, m);
    }
  }
  //以上为建初始堆
  //以下为使堆中元素完全有序
  for (i = m; i >= 1; i--) //将堆顶元素和当前未经排序子序列的最后一个元素交换
  {
    d = a[1];
    a[1] = a[i];
    a[i] = d;
    sort(1, i - 1);
  }
  //顶堆只能保证顶的都比孩子子孙的大或者小，而不能保证完全二叉树按照序列是有有序的
  //相当于每次把最小的移动到最后
  for (i = 1; i <= m; i++)
  {
    if (i == m)
    {
      printf("%d\n", a[i]);
    }
    else
    {
      printf("%d ", a[i]);
    }
  }
  return 0;
}

数据结构实验之排序五：归并求逆序数

Time Limit: 100 ms Memory Limit: 65536 KiB

Problem Description

对于数列a1,a2,a3…中的任意两个数ai,aj (i < j)，如果ai > aj,那么我们就说这两个数构成了一个逆序对；在一个数列中逆序对的总数称之为逆序数，如数列 1 6 3 7 2 4 9中，(6,4)是一个逆序对，同样还有(3,2),(7,4),(6,2)，(6,3)等等，你的任务是对给定的数列求出数列的逆序数。

Input

输入数据N(N <= 100000)表示数列中元素的个数，随后输入N个正整数，数字间以空格间隔。

Output

输出逆序数。

Sample Input

10
10 9 8 7 6 5 4 3 2 1

Sample Output

Reference Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long long int cnt;
int a[1000000], b[1000000];
void fx(int l, int m, int r)
{
  int i, j;
  i = l;
  j = m + 1;
  int ct = 0;
  while (i <= m && j <= r)
  {
    if (a[i] <= a[j])
      b[ct++] = a[i++];
    else
    {
      b[ct++] = a[j++];
      cnt += m - i + 1;
    }
  }
  while (i <= m)
    b[ct++] = a[i++];
  while (j <= r)
    b[ct++] = a[j++];
  ct = 0;
  for (i = l; i <= r; i++)
    a[i] = b[ct++];
}
void f(int l, int r)
{
  if (l < r)
  {
    int m = (l + r) / 2;
    f(l, m);
    f(m + 1, r);
    fx(l, m, r);
  }
}
int main()
{
  int n, i;
  scanf("%d", &n);
  for (i = 0; i < n; i++)
  {
    scanf("%d", &a[i]);
  }
  cnt = 0;
  f(0, n - 1);
  printf("%lld\n", cnt);
  return 0;
}

数据结构实验之排序六：希尔排序

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

我们已经学习了各种排序方法，知道在不同的情况下要选择不同的排序算法，以期达到最好的排序效率；对于待排序数据来说，若数据基本有序且记录较少时，直接插入排序的效率是非常好的，希尔排序就是针对一组基本有序的少量数据记录进行排序的高效算法。你的任务是对于给定的数据进行希尔排序，其中增量dk=n/(2^k)(k=1,2,3……)

Input

连续输入多组数据，每组输入数据的第一行给出一个正整数N(N <= 10000)，随后连续给出N个整数表示待排序关键字，数字间以空格分隔。

Output

输出dk=n/2和dk=1时的结果。

Sample Input

10
10 9 8 7 6 5 4 3 2 1
10
-5 9 7 -11 37 -22 99 288 33 66

Sample Output

5 4 3 2 1 10 9 8 7 6
1 2 3 4 5 6 7 8 9 10
-22 9 7 -11 37 -5 99 288 33 66
-22 -11 -5 7 9 33 37 66 99 288

Reference Code

#include <stdio.h>
int a[10000];
int n;
void ShellSort()
{
  int i, j, dk, k = 2, tmp;
  dk = n / k; //增量赋初值
  while (dk > 0)
  {
    for (i = dk; i < n; i++) //对所有间隔dk位置的元素组采用直接插入排序
    {
      tmp = a[i];
      j = i - dk;
      while (j >= 0 && tmp < a[j]) //对间隔dk位置的元素组排序
      {
        a[j + dk] = a[j];
        j -= dk;
      }
      a[j + dk] = tmp;
    }
    if (dk == n / 2 || dk == 1)
    {
      for (i = 0; i < n; i++)
      {
        printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
      }
    }
    k *= 2;
    dk = n / k;
  }
}
int main()
{
  while (~scanf("%d", &n))
  {
    for (int i = 0; i < n; i++)
    {
      scanf("%d", &a[i]);
    }
    ShellSort();
  }
  return 0;
}

数据结构实验之排序七：选课名单

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

随着学校规模的扩大，学生人数急剧增加，选课名单的输出也成为一个繁重的任务，我校目前有在校生3万多名，两千多门课程，请根据给定的学生选课清单输出每门课的选课学生名单。

Input

输入第一行给出两个正整数N( N ≤ 35000)和M(M ≤ 2000)，其中N是全校学生总数，M是课程总数，随后给出N行，每行包括学生姓名拼音+学号后两位(字符串总长度小于10)、数字S代表该学生选课的总数，随后是S个课程编号，约定课程编号从1到M，数据之间以空格分隔。

Output

按课程编号递增的顺序输出课程编号、选课总人数以及选课学生名单，对选修同一门课程的学生按姓名的字典序输出学生名单。数据之间以空格分隔，行末不得有多余空格。

Sample Input

5 3
Jack01 2 2 3
Jone01 2 1 3
Anni02 1 1
Harry01 2 1 3
TBH27 1 1

Sample Output

1 4
Anni02
Harry01
Jone01
TBH27
2 1
Jack01
3 3
Harry01
Jack01
Jone01

Reference Code

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

struct node
{
  char name[15];
  struct node *next;
};
struct node *nlist[2010];
int slist[2010];
int main()
{
  int n, m;
  while (~scanf("%d%d", &n, &m))
  {
    memset(slist, 0, sizeof(slist));
    for (int i = 0; i < 2010; i++)
    {
      nlist[i] = (struct node *)malloc(sizeof(struct node));
      nlist[i]->next = NULL;
    }
    for (int i = 0; i < n; i++)
    {
      char name0[15];
      int sclass;
      scanf("%s%d", name0, &sclass);
      while (sclass--)
      {
        int t;
        scanf("%d", &t);
        slist[t]++;
        struct node *q = (struct node *)malloc(sizeof(struct node));
        q->next = NULL;
        strcpy(q->name, name0);
        struct node *p = nlist[t];
        while (p->next)
        {
          if (strcmp(q->name, p->next->name) < 0)
            break;
          p = p->next;
        }
        q->next = p->next;
        p->next = q;
      }
    }
    for (int i = 1; i <= m; i++)
    {
      printf("%d %d\n", i, slist[i]++);
      struct node *j = nlist[i]->next;
      while (j)
      {
        printf("%s\n", j->name);
        j = j->next;
      }
    }
  }
}