数据结构进阶实训二 顺序表
算法C12 分钟 读完 (大约 1858 个字)  0次访问

数据结构进阶实训二 顺序表

Data structure advanced training course notes and algorithm exercises
数据结构进阶实训课程笔记和算法练习

Source Code: https://github.com/MysticalGuest/DataStructure/tree/master/AdvancedJuniorTraining

题目1

1
2
3
4
输入数字n,按顺序打印输出从1到最大的n位十进制数。比如输入3，则打印出1,2,3，一直到最大的3位数999。
  - 要考虑若n很大，我们求最大的n位数用int 或long long 也可能会溢出；
  - 考虑大数问题；
  - 提示：关于大数的表示和存储：用字符数组(取值为数字型字符)来表达大数

1.1 算法设计思想

这题主要解决大数问题。我用字符串来解决大数问题。
那么字符串中所有字符都是数字；
首先动态分配字符串空间为（n+1）*char，字符串最后要有一个结束符’\0’，初始化其他位为0；
然后每一次为字符串表示的数字加1，再打印出来；
方法print()会遍历字符串，直到遇到第一个非0字符后，打印后面的字符；
关键方法printRecursively()，每10个数，对具体位数加1，然后进位，递归。

1.2 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void printRecursively(char *number, int n, int index){
  int i;
  if(index == n){
    print(number, n);
    return;
  }
  for(i = 0; i<10; i++){
    number[index] = i + '0';
    // printf("NUMBER: %s\n", number);
    printRecursively(number, n, index + 1);
  }
}

void printToMaxOfNDigits(int n){
  if (n <= 0)
    return;
  char *number = (char *)malloc((n+1)*sizeof(char));	
  memset(number, '0', (n+1)*sizeof(char));    // 在一段内存块中填充某个给定的值,初始化为0   
  number[n] = '\0';
  printRecursively(number, n, 0);
  
  free(number);
}

1.3 运行情况截图

DS

题目2

1
2
3
4
5
6
已知一个顺序表L（整数）
实现一个函数将调整顺序表中的数字顺序，使得所有奇数位于表L的前半部分，所有偶数位于数组的后半部分。
  - 如果把题目改成把顺序表中的数按照大小分为两部分，负数都在非负数的前面，该怎么做？再定义一个函数？？
  - 或者再改为：把顺序表中的数分为两部分，
  能被3整除的数放在前面，不能被3整除的数放在后面；再定义一个函数？？
  - 是否有更好的办法？增加代码的可扩展性。

2.1 算法设计思想

定义一个规则rule方法，根据用户输入，确定排序规则，增加代码复用性；
三种排序规则思想一样：
（1）start=0从顺序表头开始往后，end从尾开始往前，
start遇到偶数停止，end遇到奇数停止，交换下标为start和下标为end的元素，然后继续前进；
（2）start=0从顺序表头开始往后，end从尾开始往前，
start遇到正数停止，end遇到负数停止，交换下标为start和下标为end的元素，然后继续前进；
（3）start=0从顺序表头开始往后，end从尾开始往前，
start遇到不能被3整除的数停止，end遇到能被3整除的数停止，交换下标为start和下标为end的元素，然后继续前进。

2.2 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/*宏定义*/
#define MAXSIZE 30

//宏定义布尔类型
#define BOOL int
#define TRUE 1
#define FALSE 0

typedef int ElemType;  /*顺序表中存放整型元素*/
typedef struct{
  ElemType elem[MAXSIZE];
  int last;
}SeqList;

/*函数声明*/
void initList(SeqList *L);
void printList(SeqList L);
BOOL rule(int elem, int select);
void sortList(SeqList *L, SeqList *L1, int select);

void main(){

  SeqList La, Lb;
  Lb.last=-1;   // 初始化Lb

  int select;

  initList(&La);
  // 给出一个顺序表La
  printf("Give a sequence table: \nLa = ");
  printList(La);

  /* 给出下列几种排序规则:
    奇数在前，偶数在后;
    负数在前，非负数在后;
    能被3整除的数在前面，不能被3整除的数在后面.
  */
  printf("\nGive the following sorting rules: \
  \n1.Odd number first, even number behind;\
  \n2.Negative numbers first, non-negative numbers last;\
  \n3.Numbers divisible by 3 are in the front, \
  and numbers that are not divisible by 3 are in the back.\
  \nPlease select the sorting rule you want and enter the rule number:");

  scanf("%d", &select);
  while(select != 1 && select != 2 && select != 3){
    printf("Please reselect: ");
    scanf("%d", &select);
  }
  sortList(&La, &Lb, select);
  printf("The adjusted sequence table is: \n");
  printList(Lb);

  system("pause");
}

/*函数定义*/
void initList(SeqList *L){
  L->last=-1;
  int i=0;
  for(i; i<MAXSIZE; i++){
    L->elem[i]=rand()%100 - 50;
  }
  L->last=MAXSIZE-1;
}

void printList(SeqList L){
  int i;

  printf("(");
  for(i=0; i<=L.last; i++)
    printf("%d ", L.elem[i]);

  printf(")\n");
}

void sortList(SeqList *L, SeqList *L1, int select){
  int i=0, end=L->last, start=0;
  for(i; i<=L->last; i++){
    if( rule(L->elem[i], select) == TRUE){    // 偶数尾插法
      L1->elem[end] = L->elem[i];
      end--;
    }
    else{   // 奇数前插法
      L1->elem[start] = L->elem[i];
      start++;
    }
  }
  L1->last=L->last;
}

BOOL rule(int elem, int select){
  switch (select)
  {
  case 1:
    if(elem%2==0)
      return TRUE;
    return FALSE;
    break;
  case 2:
    if(elem>=0)
      return TRUE;
    return FALSE;
    break;
  case 3:
    if(elem%3!=0)
      return TRUE;
    return FALSE;
    break;
  default:
    return FALSE;
    break;
  }
}

2.3 运行情况截图

DS

题目3

1
给定一个整数数组，删除相邻的重复数字，结果数组中不能存在任何相邻的重复数字。

3.1 算法设计思想

将数组存入顺序表；
遍历顺序表，将下标为i和下标i+1的元素比较如果相等，进行判断：
如果下标为i和下标i+2的元素相等，所有元素往前移动1位；
如果下标为i和下标i+2的元素不相等，所有元素往前移动2位；
持续上述循环，结束的标志是遍历顺序表，没有相邻相同元素就结束循环。

3.2 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
while(flag==1){
  if(L.last==0)    // 代表顺序表中只有一个元素
    break;
  if(L.elem[i]==L.elem[j]){
    
    if(L.elem[i]==L.elem[j+1]){   // 判断是否3数相连
      for(k=i; k<L.last; k++){
        L.elem[k]=L.elem[k+1];    // 所有元素前移1位
      }
      L.last = L.last-1;
    }
    else{   // 不是3数相连，那就是2数相连
      for(k=i; k<L.last-1; k++){
        L.elem[k]=L.elem[k+2];    // 所有元素前移2位
      }
      L.last = L.last-2;
      if(j>L.last){
        i=0;
        j=1;
      }
    }
  }

  if(j==L.last){
    for(k=0; k<L.last; k++){
      if(L.elem[k]==L.elem[k+1]){
        flag=1;
        break;
      }
      else
        flag=0;
    }
    i=-1;
    j=0;
  }
  
  i++;
  j++;
}

3.3 运行情况截图

DS

题目4

1
2
3
已知顺序表L（数组表示即可），编写一个时间复杂度O(n)，空间复杂度为O（1）的算法
将表L中所有值为x 的元素删除。
  - 表中元素无序。

4.1 算法设计思想

遍历顺序表，将顺序表a的元素赋给顺序表b，遇到要删除的元素就跳过。

4.2 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
void deleteList(SeqList *LA, SeqList *LB, int n){
  int count=0, i=0, j=0;
  for(i; i<LA->last+1; i++){
    if(LA->elem[i]==n){
      count++;    // 记录删除元素的个数
    }
    else{
      LB->elem[j] = LA->elem[i];
      j++;
    }
  }
  LB->last = LA->last-count;
}

4.3 运行情况截图

DS

题目5

1
2
3
4
5
6
7
将n 个整数存入顺序表L，实现将L中的整数序列循环左移p(0<p<n)个位置，
即将L中的数据序列
(x0, x1, ... , xp-1, xp, xp+1, ... , xn-1)
变换为
(xp, xp+1, ... , xn-1, x0, x1, ... , xp-1)
  - 类似的实现循环右移K位；
  - 要求：时间复杂度为O(n)。空间复杂度为S(1)。

5.1 算法设计思想

将下标0到p的元素逆置；
将下标p+1到n 的元素逆置；
最后将整个顺序表逆置得到最终结果。

5.2 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
void main(){
  SeqList L = {{1,2,3,4,5,6,7,8,9,10},10};

  int n;
  int temp;
  char direction;

  printf("Give a sequence table: \n");
  printlist(L);

  printf("Please enter a positive integer n to cycle through the sequence: ");
  scanf("%d", &n);
  getchar();    // 吃掉回车
  printf("Please select the direction of movement (L for left, R for right): ");
  while(direction!='R' && direction!='L'){
    scanf("%c", &direction);
    getchar();
    if(direction=='L'){
      n = n%L.last;
    }
    else if(direction=='R'){    // 右移n格就是左移L.last-n格
      n = L.last - n%L.last;
    }
    else{
      printf("Wrong input, please re-enter: ");
    }
  }
  
  int i = 0, j = n-1;

  //将子表(X0,X1...,Xp-1)逆序为(Xp-1,...,X1,X0)
  reverse(&L, i, j);

  //将子表(Xp,Xp+1,...,Xn-1)逆序为(Xn-1,...,Xp+1,Xp)
  i = n;
  j = L.last-1;
  reverse(&L, i, j);

  //将整张表(Xp-1,...,X1,X0,Xn-1,...,Xp+1,Xp)逆序为(Xp,Xp+1,...,Xn-1,X0,X1...,Xp-1)
  i = 0;
  j = L.last-1;
  reverse(&L, i, j);

  printf("The sequence table after moving is: \n");
  printlist(L);

  system("pause");
}

void reverse(SeqList *L,int i, int j){
  int temp;
  while(i < j){
    temp = L->elem[i];
    L->elem[i] = L->elem[j];
    L->elem[j] = temp;

    ++i;
    --j;
  }
}

5.3 运行情况截图

DS

#

喜欢这篇文章？打赏一下作者吧

评论

关注我

链接

分类

标签

English1
主题1
前端1
原理4
基类1
复试1
搜索引擎1
数据库1
校招2
框架12
积累2
算法18
考研1
计算机基础7
课程5
配置7
面试题集2

订阅更新

×