2019年全国研究生入学考试计算机学科专业基础综合(408)数据结构编码题

概述本文章向大家介绍2019年全国研究生入学考试计算机学科专业基础综合(408)数据结构编码题，主要包括2019年全国研究生入学考试计算机学科专业基础综合(408)数据结构编码题使用实例、应用技巧、基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。

有一个带头节点的单向链表(a1,a2,…,an−1,an)(a_1,a_2,dots,a_{n-1},a_n)(a1​,a2​,an−1​,an​)，nnn为偶数，使用空间复杂度为O(1)O(1)O(1)的算法使其变成(a1,an,a3,an−2,a4,a2)(a_1,a_{n},a_3,a_{n-2},a_4,a_2)(a1​,an​,a3​,an−2​,a4​,a2​)。

struct Node {

int data;

Node *next;

}

普通模拟就好。因为要求空间复杂度为O(1)O(1)O(1)，有点复杂的可能就是指针间的 *** 作。

模拟步骤：

把单向链表分成两部分，(a1,an−1)(a_1,a_{n-1})(a1​,an−1​)和(a2,an)(a_2,a_{n})(a2​,an​)；

头插法逆转(a2,an​)，变成(an,a2)(a_n,a_{2})(an​,a2​)；

合并这两部分。

Node *reverse(Node *root)

{

// 少于等于2个结点直接返回

if (root == NulL || root->next == NulL || root->next->next == NulL)

return root;

Node *ListA = root,*ListB = root->next;

// 1 : 分离

Node *pa = ListA,*pb = ListB;

for (; pb->next != NulL; ) {

pa->next = pa->next->next;

pa = pa->next;

pb->next = pa->next;

pb = pb->next;

}

pa->next = NulL;

// 2 : 头插法

pb = ListB->next;

ListB->next = NulL;

for (Node *p = pb; p != NulL; ) {

Node *tn = p->next;

p->next = ListB;

ListB = p;

p = tn;

}

// 3 : 合并

pa = ListA,pb = ListB;

for ( ; pb != NulL; ) {

Node *ta = pa->next,*tb = pb->next;

pa->next = pb;

pb->next = ta;

pa = ta;

pb = tb;

}

return ListA;

}

测试代码如下：

int main()

{

Node head,*root = &head;

root->next = NulL;

for (int i = 1; i < 11; ++i) {

root->next = new Node;

root->next->data = i;

root = root->next;

root->next = NulL;

}

for (Node *p = head.next; p != NulL; p = p->next)

printf("%d ",p->data);

puts("");

head.next = reverse(head.next);

for (Node *p = head.next; p != NulL; p = p->next)

printf("%d ",p->data);

puts("");

return 0;

}

输出：

PS C:UsersFlushHipDesktopTTT> .a.exe

1 2 3 4 5 6 7 8 9 10

1 10 3 8 5 6 7 4 9 2

PS C:UsersFlushHipDesktopTTT>

这里就算不给出nnn是偶数这个条件也很好办，只不过结束的条件不一样，且结束后还有一两步 *** 作而已。

总结

以上是内存溢出为你收集整理的2019年全国研究生入学考试计算机学科专业基础综合(408)数据结构编码题全部内容，希望文章能够帮你解决2019年全国研究生入学考试计算机学科专业基础综合(408)数据结构编码题所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。