全网最全【数据结构与算法】408真题实战（含代码+详解）—— 线性表专题（持续更新...）

线性表专题

每道题目均有对应的代码，大家自行查看哦！

顺序表

ADT：SeqList

文件名：SeqList.hpp

#include 
#include 
using namespace std;
// 以上是实际运行所需依赖，考试不用写

typedef int elemType;
struct SeqList
{
  elemType *data; // 利用数组存储数据元素
  int curLength=0;  // 当前顺序表中存储的元素个数
  int maxSize; // 顺序表的初始化最大长度
  SeqList(int size = 10){
    maxSize = size;
  }
};

/**
 * 以下为测试方法，考试不用写
 */

// 初始化数据
void init(SeqList *seqlist)
{
  seqlist->data = new elemType[seqlist->maxSize];
  for (int i = 1; i < 10; i++)
  {
    seqlist->data[i - 1] = i;
    seqlist->curLength++;
  }
}

// 自定义初始化数据
void initByCustom(SeqList *seqlist)
{
  seqlist->data = new elemType[seqlist->maxSize];
  elemType value;
  cout << "\ninput the SeqList's data (the maxSize is " << seqlist->maxSize <<"):"<< endl;
  for (int i = 0; i < seqlist->maxSize; i++)
  {
    cin >> value;
    seqlist->data[i] = value;
    seqlist->curLength++;
  }
}


// 输出结果
void output(SeqList *seqlist)
{
  cout << "\nThe SeqList's data is: " << endl;
  for (int i = 0; i < seqlist->curLength; i++)
  {
    cout << seqlist->data[i] << "  ";
  }
  cout << endl;
}

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

真题实战

2010年统考真题

1、题目详情

2、代码实现

文件名：SeqList_2010.cpp

#include "SeqList.hpp"

void reverse(SeqList *seqlist,int begin,int end)
{
  elemType temp;
  while (end>begin)
  {
    temp = seqlist->data[begin];
    seqlist->data[begin] = seqlist->data[end];
    seqlist->data[end] = temp;
    begin++;
    end--;
  }
}

void _2010(SeqList *seqlist, int p)
{
  reverse(seqlist, 0, seqlist->curLength - 1);
  reverse(seqlist, 0, seqlist->curLength - p - 1);
  reverse(seqlist, p+1, seqlist->curLength - 1);
}

int main()
{
  SeqList *seqlist = new SeqList();
  init(seqlist);
  output(seqlist);
  _2010(seqlist, 4);
  cout << "\nAfter rotating 4 bits to the left" << endl;
  output(seqlist);
  cout<< "\n==============================End==============================" << endl;
  system("pause");
  return 0;
}
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

运行结果：

3、答案解析

2011年统考真题

1、题目详情

2、代码实现

文件名：SeqList_2011.cpp

#include "SeqList.hpp"

elemType _2011(SeqList *s1, SeqList *s2)
{

  elemType result;
  for (int i = 0,j=0,count=0; count< s1->curLength; count++)
  {
    if(s1->data[i]<=s2->data[j])
      result = s1->data[i++];
    else
      result = s2->data[j++];
  }
  
  return result;
}

int main()
{
  SeqList *s1 = new SeqList(5);
  SeqList *s2 = new SeqList(5);
  initByCustom(s1);
  cout << "--------------------------" << endl;
  initByCustom(s2);
  cout << "\nThe median of S1 and S2 is " << _2011(s1, s2) << endl;
  cout << "\n==============================End==============================" << endl;
  system("pause");
  return 0;
}
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

运行结果：

3、答案解析

首先给出我自己的思路（也就是官方的另解）：

• 两个等长序列的中位数就是他们合在一起形成的有序序列（不使用排序算法，直接通过指针对比+最小值的记录即可）的中位数，因此通过L（s1/s2的长度）次循环，依次对比并记录两个数组的最小值，则最终记录的结果就是他们的中位数。

• 我这个算法的时间复杂度为O(L)，空间复杂度为O(1)

以下是官方解析：

2013年统考真题

1、题目详情

2、代码实现

文件名：SeqList_2013.cpp

注：用排序的方法大家可以看排序专题学习后自己实现（对比暴力算法的代码会多一点点，考试时用的话，要保证不要写错哦），最优解法大家可以看答案解析（比较难想，考试实在想不出就暴力吧），这里我写的是传统暴力解法：

#include "SeqList.hpp"

int _2013(SeqList *seqlist)
{
  int maxCount = 0,count=0;
  elemType result;
  for (int i = 0; i < seqlist->curLength; i++)
  {
    count = 0;
    for (int j = 0; j < seqlist->curLength; j++)
    {
      if (seqlist->data[i] == seqlist->data[j])
        count++;
    }

    if (count>=maxCount){
      maxCount = count;
      result = seqlist->data[i];
    }

  }

  // cout << "maxCount is: " << maxCount << endl;
  // cout << "result is: " << result << endl;

  if (maxCount > seqlist->curLength / 2)
    return result;
  else
    return -1;
}

int main()
{
  SeqList *seqlist = new SeqList(8);
  initByCustom(seqlist);
  // output(seqlist);
  int result = _2013(seqlist);
  if (result == -1)
    cout << "Main element not found!" << endl;
  else
    cout << "The main element is: " << result << endl;
  cout << "\n==============================End==============================" << endl;
  system("pause");
  return 0;
}

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

运行结果：

3、答案解析

2018年统考真题

1、题目详情

2、代码实现

我的方法是通过快排，将数组排好序后，依次查找最小正整数是否存在，时间复杂度为O（nlogn），空间复杂度为O（logn）。

文件名：SeqList_2018.cpp

#include "SeqList.hpp"

int partition(int *arr, int low, int high)
{
  int pivot = arr[low];
  while (low < high)
  {
    while (low < high && arr[high] >= pivot)
      high--;
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot)
      low++;
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}

// 快速排序
void quick_sort(int *arr, int low, int high)
{
  if (low < high)
  {
    int p = partition(arr, low, high);
    quick_sort(arr, low, p - 1);
    quick_sort(arr, p + 1, high);
  }
}

int _2018(SeqList *seqlist)
{
  quick_sort(seqlist->data, 0, seqlist->curLength - 1);

  int j = 0;
  while (seqlist->data[j] <= 0 && j < seqlist->curLength-1)
    j++;
  if(j==seqlist->curLength)
    return 1;
  int i;
  for (i = 1; j < seqlist->curLength; j++)
  {
    if(seqlist->data[j]>i)
      return i;
    if (seqlist->data[j] == i)
       i++;
  }
  return i;
}

int main()
{
  SeqList *seqlist = new SeqList(5);
  initByCustom(seqlist);
  cout << "The minimum positive number that does not appear is: " << _2018(seqlist) << endl;
  cout
      << "\n==============================End==============================" << endl;
  system("pause");
  return 0;
}
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

运行结果：

3、答案解析

2020年统考真题

1、题目详情

2、代码实现

暴力O（n^3）在考试实在不会就写吧，其实也行，毕竟这题还是挺难的/(ㄒoㄒ)/~~，暴力解法太简单了，这里就略了，大家可以自己实战一下，这里还是给出答案版代码：

文件名：SeqList_2020.cpp

#include "SeqList.hpp"
#define INT_MAX 0x7fffffff

int abs_(int a){
  if(a<0)
    return -a;
    else
      return a;
}

bool xls_min(int a,int b,int c){
  if(a<=b&&a<=c) return true;
    return false;
}

int _2020(SeqList *A, SeqList *B, SeqList *C ){
  int i = 0, j = 0, k = 0, D_min = INT_MAX, D;
  while (i<A->curLength&&j<B->curLength&&k<C->curLength&&D_min>0){
    D = abs_(A->data[i] - B->data[j]) + abs_(B->data[j] - C->data[k]) + abs_(C->data[k] - A->data[i]);
    if (D<D_min) D_min = D;
    if (xls_min(A->data[i], B->data[j], C->data[k]))
      i++;
    else if (xls_min(B->data[j], C->data[k], A->data[i]))
      j++;
    else
      k++;

  }

  return D_min;
}

    int main()
{
  SeqList *A = new SeqList(3);
  initByCustom(A);
  SeqList *B = new SeqList(4);
  initByCustom(B);
  SeqList *C = new SeqList(5);
  initByCustom(C);
  cout << "\nThe minimum distance of a triple is: " << _2020(A,B,C) << endl;
  cout
      << "\n==============================End==============================" << endl;
  system("pause");
  return 0;
}

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

运行结果：

3、答案解析

顺序表习题

• 题目源于王道

链表

ADT：LinkList

文件名：LinkList.hpp

#include 
#include 
#include 
using namespace std;
// 以上为实际运行所需依赖，考试不必填写

typedef int elemType;
struct LinkNode
{
  // 结点的数据域
  elemType data;
  // 结点的指针域，指向后继结点
  LinkNode *next;
  // 具有两个参数的LinkNode构造函数
  LinkNode(const elemType value, LinkNode *p = NULL)
  {
    data = value;
    next = p;
  }
  // 具有一个参数的LinkNode构造函数
  LinkNode(LinkNode *p = NULL) { next = p; }
};

// 遍历单链表
void traverse(LinkNode *head)
{
  LinkNode *p = head->next;
  cout << "\nYour created data is:\n";
  while (p != NULL)
  {
    cout << p->data << "  ";
    p = p->next;
  }
  cout << endl
       << endl;
}

// 带头节点的头插法初始化创建测试数据
int initNum = 10;
void init(LinkNode *head)
{
  LinkNode *p;
  elemType value, flag;
  // 系统生成测试数据
  srand((unsigned)time(NULL));
  for (int i = 0; i < initNum; i++)
  {
    //生成[0,100)的随机数
    value = rand() % 100;
    p = new LinkNode(value, head->next);
    // 结点p插入到头结点的后面
    head->next = p;
  }
}

// 尾插法自定义初始化数据
void initByCUstom(LinkNode *head)
{
  LinkNode *tail = head, *p;
  elemType value, flag;
  cout << "input the flag to end with: " << endl;
  cin >> flag;
  cout << endl;
  cout << "input the LinkList's data: " << endl;
  while (cin >> value, value != flag)
  {
    p = new LinkNode(value);
    // 结点p插入到尾结点的后面
    tail->next = p;
    tail = p;
  }
  cout << endl;
}

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

字符类型的链表测试ADT

文件名：LinkList_char.hpp

#include 
#include 
using namespace std;
// 以上是实际运行所需依赖，考试不用写

typedef char elemType;
struct LinkNode
{
  // 结点的数据域
  elemType data;
  // 结点的指针域，指向后继结点
  LinkNode *next;
  // 具有两个参数的LinkNode构造函数
  LinkNode(const elemType value, LinkNode *p = NULL)
  {
    data = value;
    next = p;
  }
  // 具有一个参数的LinkNode构造函数
  LinkNode(LinkNode *p = NULL) { next = p; }
};

/**
 * 以下为测试方法，考试不用写
 */

// 遍历单链表
void traverse(LinkNode *head)
{
  LinkNode *p = head->next;
  cout << "\nYour created data is:\n";
  while (p != NULL)
  {
    cout << p->data << "  ";
    p = p->next;
  }
  cout << endl
       << endl;
}

// 尾插法初始化数据
void initByCUstom(LinkNode *head)
{
  LinkNode *tail = head,*p;
  elemType value, flag;
  cout << "input the flag to end with: " << endl;
  cin >> flag;
  cout << endl;
  cout << "input the LinkList's data: " << endl;
  while (cin >> value, value != flag)
  {
    p = new LinkNode(value);
    // 结点p插入到尾结点的后面
    tail->next = p;
    tail = p;
  }
  cout << endl;
}

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

真题实战

2009年统考真题

1、题目详情

2、代码实现

文件名：LinkList_2009.cpp

#include "LinkList.hpp"

int _2009(LinkNode *head, int k)
{
  LinkNode *q= head->next;
  LinkNode *p = q;
  int count = 0;
  while (p!=NULL)
  {
    if (count<k) count++;   
    else q = q->next;
    p = p->next;
    }
    if (count < k)
      return 0;
      else{
        cout << q->data << endl;
        return 1;
      }
}

int main()
{
  LinkNode *head = new LinkNode();
  init(head);
  traverse(head);

  cout << "Find end with 3 data is: "
       << _2009(head, 3);

  cout << "\n==============================End==============================" << endl;
  system("pause");
  return 0;
}

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

运行结果：

3、答案解析

2012年统考真题

1、题目详情

2、代码实现

文件名：LinkList_2012.cpp

#include "LinkList_char.hpp"

int getLength(LinkNode *str){
  LinkNode *p = str->next;
  int count = 0;
  while (p)
  {
    count++;
    p = p->next;
  }

  return count;
}


elemType _2012(LinkNode *head1, LinkNode *head2)
{
  int len1 = getLength(head1);
  int len2 = getLength(head2);
  LinkNode *str1 = head1->next;
  LinkNode *str2 = head2->next;
  int count = 0;
  if (len1>len2){
    while (count<len1-len2)
    {
      str1 = str1->next;
      count++;
    }
  }else
  {
    while (count < len2 - len1)
    {
      str2 = str2->next;
      count++;
    }
  }

  while (str1&&str2)
  {
    if(str1->data==str2->data)
      return str1->data;
    str1 = str1->next;
    str2 = str2->next;
  }
  
  return NULL;
}

int main()
{

  LinkNode *str1 = new LinkNode();
  initByCUstom(str1);
  LinkNode *str2 = new LinkNode();
  initByCUstom(str2);

  cout << "\nThe common suffix starts with :" << _2012(str1, str2)
  << endl;

  cout << "\n==============================End==============================" << endl;
  system("pause");
  return 0;
}

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

运行结果：

3、答案解析

2015年统考真题

1、题目详情

2、代码实现

这里我给出传统的暴力解法，利用辅助空间可以看答案解析的方法，优化还可以考虑散列表哦！

文件名：LinkList_2015.cpp

#include "LinkList.hpp"

void _2015(LinkNode *head)
{
  LinkNode *p = head->next;
  LinkNode *q;
  LinkNode *t;
  while (p)
  {
    elemType value = p->data;
    q = p;
    while (q->next)
    {
      if (value == q->next->data || value == (-1) * q->next->data)
      {
        t = q->next;
        q->next = q->next->next;
        delete t;
      }
      else q = q->next;
    }
    p = p->next;
    }
}

int main()
{
  LinkNode *head = new LinkNode();
  initByCUstom(head);
  _2015(head);
  cout << "\nAfter deleting nodes with equal absolute values, the data is: " << endl;
  traverse(head);
  cout << "\n==============================End==============================" << endl;
  system("pause");
  return 0;
}
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

运行结果：

3、答案解析

2019年统考真题

1、题目详情

2、代码实现

文件名：LinkList_2019.cpp

#include "LinkList.hpp"

void _2019(LinkNode *head)
{
  
  LinkNode *p = head->next;
  LinkNode *q =p;
  // 找到中间位置
  while (q&&q->next)
  {
    q = q->next->next;
    p = p->next;
  }
  LinkNode *tail = head->next;

  // 将链表一分为二
  while (tail->next!=p)
    tail = tail->next;

  // 后半段链表进行逆置
  LinkNode *head2 = new LinkNode();
  while (p)
  {
    tail->next = p->next;
    p->next =head2->next;
    head2->next = p;
    p = tail->next;
  }

  p = head->next;

  // 后半段链表依次拆分节点按要求间接拼接到原来的链表后
  while (p)
  {
    q = head2->next;
    head2->next = q->next;
    q->next = p->next;
    p->next = q;
    p = q->next;
    }

    // 处理奇数个数时，余留的最后一个数
    if (head2->next != NULL)
    {
      q->next = head2->next;
  }
  
}

int main()
{
  LinkNode *head = new LinkNode();
  initByCUstom(head);
  _2019(head);
  cout << "\nThe result after rearrangement is: " << endl;
  traverse(head);
  cout << "\n==============================End==============================" << endl;
  system("pause");
  return 0;
}
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

运行结果：

3、答案解析

链表习题

• 题目来源于王道

线性表专题训练

• 题目源于算法与数据结构考研试题精析

后续更新

等后面有时间会把上面题目的完整代码+运行示例补充更新完善，大家尽情期待！