实现两个有序单链表的合并

实验二

1. 主函数：

#include<iostream>

#include<ctime>

#include<string>

using namespace std;

#include "d_node.h"

#include "function.h"

cout << "The state of list 1 after sorted:" << endl;

writeLinkedList(L1);

node<int> * L2 = initRandom();

cout << "The random list 2 as followed:" << endl;

writeLinkedList(L2);

sort(L2);

cout << "The state of list 2 after sorted:" << endl;

writeLinkedList(L2);

emerge(L1,L2); //合并二个有序链表 L1,L2

cout << "The state of list after emerged:" << endl;

{

srand(time(0));

node<int> *front = NULL, *newNode;

int number;

cout << "Enter the number of node your want to creat:";

cin >> number;

for(int i = 1; i <= number; i++)

front = newNode;

}

return front;

//输出链表

void writeLinkedList(node<int> *&front, const string& separator = " ")

{

// front points at first node. curr moves through the list

node<int> *curr;

curr = front; // set curr to front of the list

while (curr != NULL) // continue until and of list

{

// output node value and move to the next node

cout << curr->nodeValue << separator;

curr = curr->next;

if(front == NULL || front->next == NULL) //若原链表中只有一个节点则无需排序

return;

node<int> *curr = front->next; //用于标记未排好序的结点的首结点

node<int> *pre = front; //用于标记已排好序的结点中 nodeValue 最大的结点(排

好序的末结点)

node<int> *p , *q; //用于遍历已排好序的结点

int flag; //标记是否需要插入

while(curr !=NULL) //判断是否还有未排好序的结点

{

p = front;

flag = 0; //标记是否需要插入

while(p != curr)

{

if(pre->nodeValue <= curr->nodeValue) //如果结点的 nodeValue 大于排

q = p;

p = p->next;

continue;

}

else

{

}

curr = curr->next;

}