单链表合并降序

#include <iostream> using namespace std; class Node { friend class List; private: int data; Node *next; }; class List { public: List(); //创建链表 ~List(); //销毁链表 bool ListInsertHead(int); //在链表头结点插入元素(头插法） bool ListInsert(int i); //在第i个位置插入元素 bool ListDelete(int i); //在第i个位置删除元素 void ClearList(); //清空链表 int LocateElem(int); //查询 bool ListMerge(List &a,List &b); //合并 void ListBubble(); //降序 int Listlength(); //表长 void output(); //遍历链表 private: Node *m_pList; int m_iLength; }; List::List() { m_pList = new Node; m_pList->data=0; m_pList->next=NULL; m_iLength=0; } void List::ClearList() { Node *currentNode = m_pList->next; while(currentNode!=NULL) { Node *temp=currentNode->next; delete currentNode; currentNode=temp; } m_pList->next=NULL; } int List::Listlength() { return m_iLength; } List::~List() { ClearList(); delete m_pList; m_pList=NULL; } bool List::ListInsert(int i) { cout<<"选择要插入的数字"; int x; cin>>x; if(i<0||i>m_iLength) { return false; } Node *currentNode=m_pList; for(int k=0;k<i;k++) { currentNode=currentNode->next; } Node *newNode= new Node; if(newNode==NULL) { return false; } newNode->data=x; newNode->next=currentNode->next; currentNode->next=newNode; m_iLength++; return true; } bool List::ListDelete(int i) { if(i<0||i>=m_iLength) { return false; } Node *currentNode=m_pList; Node *currentNodeBefore=NULL; for(int k=0;k<=i;k++) { currentNodeBefore=currentNode; currentNode=currentNode->next; } currentNodeBefore->next=currentNode->next; i=currentNode->data; delete currentNode; currentNode=NULL; m_iLength--; return true; } bool List::ListInsertHead(int length) { int val; ClearList(); for(int n=0;n<length;n++) { cin>>val; Node *newNode=new Node; newNode->data=val; if(newNode==NULL) { return false; } newNode->next=m_pList->next; m_pList->next=newNode; m_iLength++; } return true; } int List::LocateElem(int x) { Node *currentNode=m_pList; int count=0; while(currentNode->next!=NULL) { currentNode=currentNode->next; if(currentNode->data==x) { return count; } count++; } return -1; } bool List::ListMerge(List &a,List &b) { Node *currentNode=new Node; currentNode=a.m_pList->next; while(currentNode->next!=NULL) { currentNode=currentNode->next; } currentNode->next=b.m_pList->next; b.m_pList=NULL; //若不置空的话L2将依旧存在 a.m_iLength+=b.m_iLength; a.output(); return true; } void List::ListBubble() { Node *temp=new Node; Node *currentNode=new Node; for(int k=0;k<m_iLength;k++) { currentNode=m_pList->next; while(currentNode->next!=NULL) { if((currentNode->next->data)>(currentNode->data)) { temp->data=currentNode->next->data; currentNode->next->data=currentNode->data; currentNode->data=temp->data; } currentNode=currentNode->next; } } } void List::output() { Node *currentNode=m_pList->next; while(currentNode!=NULL) { cout<<currentNode->data<<' '; currentNode=currentNode->next; } cout<<endl; } int main() { int i,x,y,z; List L1,L2; int length; cout<<"链表长度:"; cin>>length; cout<<"链表1号:"; L1.ListInsertHead(length); cout<<"链表2号:"; L2.ListInsertHead(length); L1.output(); L2.output(); cout<<"选择编辑链表1或2:"; cin>>x; if(x==1) { cout<<"选择插(1)还是删(2):"; cin>>y; if(y==1) { cout<<"插入节点:"; cin>>i; L1.ListInsert(i); } else if(y==2) { cout<<"删除结点:"; cin>>i; L1.ListDelete(i); } } else if(x==2) { cout<<"选择插(1)还是删(2):"; cin>>y; if(y==1) { cout<<"插入节点:"; cin>>i; L2.ListInsert(i); } else if(y==2) { cout<<"删除结点:"; cin>>i; L2.ListDelete(i); } } L1.ListMerge(L1,L2); L1.ListBubble(); cout<<"元素值递减排列:"; L1.output(); cout<<"输入需要定位的元素:"; cin>>z; cout<<"此元素所在第一个位置为"; cout<<L1.LocateElem(z)<<endl; cout<<"合并链表长度为:"; cout<<L1.Listlength(); return 0; }