Node.h //第一个文件
#ifndef NODE_H #define NODE_H #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define NULL 0 #define flag -1 class Node { public: int data; Node *next; }; #endif //NODE_H
linklist.h //第二个文件
#ifndef LINKLIST_H #define LINKLIST_H #include "Node.h" class LinkList { public: LinkList( );//constructor LinkList(LinkList &L);//copy construtor LinkList &operator =(const LinkList &L);//overload operator '=' void Createlist(int n);//use the datas you put in to create a list void CleanList( );//clean the list bool IsListEmpty( )const;//determine whether the list is empty or not void InsertOfList(int i,int value);//insert value before i'th node void DeleteOfList(int pos);//delete the i'th node void SortList( );//sort the list int LenOfList( )const;//calculate the length of the list int GetElem(int pos);//get pos'th node data void ShowList( )const;//show the data of the list friend void Merge(LinkList &La,LinkList &Lb,LinkList &Lc);//merge two list into one ~LinkList( );//destructor private: Node *head; }; #endif //LINKLIST_H
linklist.cpp //第三个文件
#include <iostream> #include <iomanip> #include "linklist.h" using namespace std; LinkList::LinkList( ) //construtor of LinkList { head = new Node; //dynamic application memory space head->next = NULL; //it's pointer points to NULL cout <<endl<<"the constructor called"<<endl<<endl; } LinkList::LinkList(LinkList &L) //copy construtor { head = new Node; head->next = NULL; if(L.head) { Node *p = new Node; p = L.head->next; //use temporary node q to record L's node while(p) { Node *temp = new Node; //temporary node,used to record L's data temp->data = p->data; temp->next = head->next; //insert node temp into the list head->next = temp; p = p->next; } } } LinkList &LinkList::operator =(const LinkList &L) //overload operator '=' { head = new Node; head->next = NULL; Node *p = new Node; p = L.head->next; //use temporary node q to record L's node while(p) { Node *temp = new Node; //temporary node,used to record L's data temp->data = p->data; temp->next = head->next; head->next = temp; p = p->next; } return *this; } void LinkList::Createlist(int n) //use the datas you put in to create a list { head = new Node; head->next = NULL; if(n > 0) { cout <<"now please input "<<n<<" datas:"<<endl; for(int i = 0;i < n;i++) { Node *temp = new Node; //temporary node to save the data you put in cin >>temp->data; temp->next = head->next; head->next = temp; } } else if(n==0) { cout <<"no data to put in!"<<endl; } else { cout <<"Illegal length!"<<endl<<endl; exit(NULL); } } void LinkList::CleanList( ) //clean the list { cout <<"clear the list now!"<<endl; head->next = NULL; } bool LinkList::IsListEmpty( )const //determine whether the list is empty or not { if(head->next == NULL) { cout <<"the list is empty"<<endl<<endl; return TRUE; } else { cout <<"not an empty list"<<endl<<endl; return FALSE; } } void LinkList::InsertOfList(int i,int value) //insert value before i'th node { Node *p = new Node; p = head; int count = 0; while(p && count < i-1) //search for (i-1)'th node { p = p->next; count++; } if(!p || count > i-1) //i<1 or have been the end of the list { cout <<"one of the position to insert in is illegal!"<<endl; cout <<"the illegal position is: "<<i<<endl; exit(ERROR); } Node *temp = new Node; //use value to new a node temp->data = value; temp->next = p->next; //insert the node into the list p->next = temp; } void LinkList::DeleteOfList(int pos) //delete the i'th node { Node *p = new Node; p = head; int count = 0; while(p->next && count < pos-1) //search the i'th node,and put p points its precursor { p = p->next; count++; } if(!(p->next) || count > pos-1) { cout <<"one of the position to delete is illegal!"<<endl; cout <<endl<<"the illegal position is: "<<pos<<endl<<endl; exit(ERROR); } Node *temp = new Node; //temporary node used to record pos'th node temp = p->next; p->next = temp->next; //delete pos'th node and cout the data cout <<endl<<temp->data<<" has been delete from the list"<<endl<<endl; delete temp; } void LinkList::SortList( ) //sort the list { cout <<endl<<"now the list is beening sorting..."<<endl<<endl; Node *p = new Node; p = head->next; Node *temp1 = new Node; Node *temp2 = new Node; while(p) { temp1 = p; temp2 = p->next; while(temp2) { if(temp2->data < temp1->data) { int TempData = temp2->data; temp2->data = temp1->data; temp1->data = TempData; } temp2 = temp2->next; } p = p->next; } } int LinkList::LenOfList( )const //calculate the length of the list { int len = 0; Node *p = new Node; p = head->next; while(p) { len++; p = p->next; } return len; } int LinkList::GetElem(int pos) //get pos'th node data { int record; Node *p = new Node; p = head->next; int count = 1; while(p && count < pos) //search for i'th node,until p points to i'th node or NULL { p = p->next; count++; } if(!p || count > pos) exit(ERROR); record = p->data; return record; } void LinkList::ShowList( )const //show the data of the list { Node *p = new Node; p = head->next; if(IsListEmpty()==TRUE) cout <<endl<<"the list is null"<<endl<<endl; while(p) { cout <<setw(5)<<p->data; p = p->next; } cout <<endl<<endl; } void Merge(LinkList &La,LinkList &Lb,LinkList &Lc) //merge two list into one { Node *pa = new Node; pa = La.head->next; //use pa to record La's node Node *pb = new Node; pb = Lb.head->next; //use pb to record La's node Lc.head = new Node; Lc.head->next = NULL; while(pa!=NULL && pb!=NULL) //neither La nor Lb is NULL { Node *r= new Node; //temporary node,used to record the data if(pa->data < pb->data) //La's data < Lb's data { r->data = pa->data; pa = pa->next; } else //Lb's data < La's data { r->data = pb->data; pb = pb->next; } r->next = Lc.head->next; //insert node r into Lc Lc.head->next = r; } while(pa!=NULL) //La is not NULL { Node *r= new Node; r->data = pa->data; pa = pa->next; r->next = Lc.head->next; Lc.head->next = r; } while(pb!=NULL) //Lb is not NULL { Node *r= new Node; r->data =pb->data; pb = pb->next; r->next = Lc.head->next; Lc.head->next = r; } // delete r; } LinkList::~LinkList( ) //the destructor of LinkList { cout <<"the list is destroyed!"<<endl<<endl; delete head; }
testcode.cpp //测试代码
#include <iostream> #include "linklist.h" using namespace std; int main( ) { cout <<"how many element in list one?"; int n; cin >>n; LinkList L1,L2,L; L1.Createlist(n); cout <<"how many element in list two?"; int m; cin >>m; L2.Createlist(m); L1.SortList( ); L2.SortList( ); Merge(L1,L2,Ll); L.ShowList(); return 0; }
