数据结构进阶实训七 链表，数组

Data structure advanced training course notes and algorithm exercises

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

---

---

题目1

判断两个链表是否相交？
  - 给定两个单链表，判断两个单链表是否相交？
  - 假设两个单链表均没有环

1.1 算法设计思想

如果链表有交点，那么他们一定有共同后缀，转化为共同后缀问题

1.2 源代码

LinkList commonSuffix(LinkList L1, LinkList L2){
  Node *p, *q;
  int len1, len2;
  len1=listlen(L1);
  len2=listlen(L2);
  if(lastChar(L1) != lastChar(L2)){
    return NULL;
  }
  else{
    for(p=L1; len1>len2; len1--){
      p=p->next;
    }
    for(q=L2; len2>len1; len2--){
      q=q->next;
    }
    while(p->next != NULL && p->next != q->next){
      p=p->next;
      q=q->next;
    }
    return p->next;
  }
}

1.3 运行情况截图

---

---

题目2

连续子数组的最大和。
输入一个整形数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。
求所有子数组的和的最大值。要求时间复杂度为O（n）
  - 例如输入数组为（1、-2、3、10、-4、7、2、-5）
  - 和最大的子数组为（ 3、10、-4、7、2 ）
  - 该子数组的和为18

2.1 算法设计思想

将第一个元素默认最大值，往后遍历，并相加；

如果此时和sum小于当前元素，就舍弃之前的元素；

如果当前sum大于记录的max值，将max值改为sum；

直到遍历结束数组所有元素

2.2 源代码

int MaxSum(int a[], int size, int *s, int *e){
  if(a == NULL || size == 0){
    //非法输入
    return -1;
  }

  int sum = 0;//初始和为0
  int i = 0;
  int max = a[i];//最大值最初必为数组第一个元素
  for(i; i < size; i++){
    sum = sum + a[i];//遍历一个元素，累加一次
    if(sum < a[i]){//如果加上当前元素之后的和比当前元素还小，则舍弃之前的元素，从当前元素开始累加
      *s = i;
      sum = a[i];
    }
    //如果加上当前元素之后的和比当前元素大
    //说明可以继续累加
    //如果当前和比最大值大，则更新最大值为当前和
    //否则，不做更新
    if(sum > max){
      *e = i;
      max = sum;
    }
  }
  return max;
}

2.3 运行情况截图

---

---

题目3

数组中的逆序对。
在数组中的两个数字，如果前面的数字大于后面的数字，则这两个数字组成一个逆序对。
  - 输入一个数组，输出逆序对、并求出这个数组中出现的逆序对的总数
  - 例如：数组中元素{7，5，6，4}，一共有5个逆序对分别是（7,6）、（7,5）（7,4）、（6,4）、（5,4）

3.1 算法设计思想

利用归并的思想；
在排序交换元素的时候就输出这两数，就是逆序对，并用计数器记录

3.2 源代码

#define MAX 32767

int merge(int *array, int p,int q,int r) { 
  //归并array[p...q] 与 array[q+1...r]
  int tempSum=0;
  int n1 = q-p+1;
  int n2 = r-q;
  int* left = NULL;
  int* right = NULL;
  int i, j, k, l;

  left = ( int *)malloc(sizeof(int) * (n1+1));
  right = ( int *)malloc(sizeof(int) * (n2+1));
  
  for(i=0; i<n1; i++)
    left[i] = array[p+i];

  for(j=0; j<n2; j++)
    right[j] = array[q+1+j];

  left[n1] = MAX; //哨兵，避免检查每一部分是否为空
  right[n2] = MAX;
  i=0;
  j=0;

  for(k=p; k<=r; k++) {
    if(left[i] <= right[j]) {
      array[k] = left[i];
      i++;
    }
    else {
      if(array[k]>right[j]){
        l=k+1;
        for(l; l<n1; l++)
          printf("(%d, %d)\t", array[l], right[j]);
      }
      printf("(%d, %d)\t", left[i], right[j]);
      array[k] = right[j];
      j++;
      tempSum += n1 - i;
    }
  }
  return tempSum;

}

int mergeSort(int *array, int start, int end ) {
  int sum=0;
  if(start < end) {
    int mid = (start + end) /2;
    sum += mergeSort(array, start, mid);
    sum += mergeSort(array, mid+1, end);
    sum += merge(array,start,mid,end);
  }
  return sum;
}

3.3 运行情况截图

---