某年研究生复试机试题

读入一批以负数为结束的正整数，数据为5，7，2，4，9，－1，建立一个带头结点的链表，链表的每个结点中包含有两个指针：一个用于链接输入的先后顺序，另一个用于链接输入整数从小到大的顺序。并分别按两个指针方向进行遍历输出。
====================
这个考的基础知识，一个是链表的东西，指针啊什么的
另外就是单向链表怎么排序
我能想到的方法嘛~其实排序这个东西，给定当前的数值value
如果存在x,使得 val <=x < MINVALUE，那么x就是当前节点的后继了
后面这个MINVALUE，就是选定了这个x之后，把MINVALUE设定为x，然后继续遍历输入次序，看看还有没有比x更适合的节点了
有点无限逼近的味道…要注意的是指针操作的时候别把自己跟自己来比，不然输入时如果有相同数就会玩完了~
时间复杂度是O(n^2)，不过嘛…这个节骨眼能想出方法就行
 
吐槽一句，VC6真他妈的太难用了！！！
=====================

#include
using namespace std;
struct Node
{
int val;
Node *ptrOrder;
Node *ptrSort;
Node()
{
ptrOrder = NULL;
ptrSort = NULL;
val = -1;
}
};
int main()
{
//const int MAX_SIZE = 100;
//int inputArray[MAX_SIZE];
//Initialize link head
Node root;
int input;
int arySize = 0;
Node *currNode = &root;
//Node *prevNode = NULL;
while(cin >> input)
{
if(input < 0 || arySize >= MAX_SIZE)
break;
Node *newNode = new Node;
newNode->val = input;
currNode -> ptrOrder = newNode;
currNode = newNode;
}
//Sort
currNode = &root;
while(currNode != NULL)
{
Node *nextNode = root.ptrOrder;
int min_val_max = 65535;
int currValue = currNode->val;
while(nextNode != NULL)
{
if(nextNode == currNode)
{
nextNode = nextNode->ptrOrder;
continue;
}
int nextValue = nextNode->val;
if(nextValue >= currValue && nextValue < min_val_max) { min_val_max = nextValue; currNode->ptrSort = nextNode;
}
nextNode = nextNode->ptrOrder;
}
currNode = currNode->ptrOrder;
}
//Output
currNode = root.ptrOrder;
while(currNode != NULL)
{
cout << currNode->val << " "; currNode = currNode -> ptrOrder;
}
cout << endl; currNode = root.ptrSort; while(currNode != NULL) { cout << currNode->val << " "; currNode = currNode -> ptrSort;
}
cout << endl; //Clear memory if you have enough time :) cin.get(); return 0; }