数据结构进阶实训课程笔记和算法练习

题目1

输入数字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 源代码

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 运行情况截图

题目2

已知一个顺序表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 源代码

/*宏定义*/
#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 运行情况截图

题目3

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

3.1 算法设计思想

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

3.2 源代码

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 运行情况截图

题目4

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

4.1 算法设计思想

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

4.2 源代码

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 运行情况截图

题目5

将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 源代码

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;
  }
}

数据结构进阶实训二

目录

题目1

1.1 算法设计思想

1.2 源代码

1.3 运行情况截图

题目2

2.1 算法设计思想

2.2 源代码

2.3 运行情况截图

题目3

3.1 算法设计思想

3.2 源代码

3.3 运行情况截图

题目4

4.1 算法设计思想

4.2 源代码

4.3 运行情况截图

题目5

5.1 算法设计思想

5.2 源代码

5.3 运行情况截图