#include<iostream>using namespace std;class ListNode{private: int data; ListNode *link;public: ListNode(int newdata) { data=newdata; link=NULL; } int getData() { return data; } void setData(int newdata) { this->data=data; } void setLinkNode(ListNode *newlink) { link=newlink; } ListNode *getNode() { return link; }};class List{private: ListNode *first,*check,*last; int NodeNumbers;public: List() { first=NULL; check=first; last=first; NodeNumbers=0; } List(int newdata) { first=new ListNode(newdata); last = first; check = first; NodeNumbers = 1; } void addNode(int data) { if(this->first!=NULL) { ListNode *link=new ListNode(data); (*last).setLinkNode(link); last=link; } else { first=new ListNode(data); last=first; check=first; } NodeNumbers++; } void addNodeFirst(int data) { ListNode *link=new ListNode(data); (*link).setLinkNode(first); first=link; check=first; NodeNumbers++; } void setFirst(ListNode *first) { this->first=first; } void setLast(ListNode *last) { this->last=last; } ListNode* getFirst() { return first; } ListNode* getLast() { return last; } int getMin() { int minNumber=(*first).getData(); ListNode* link=first; while(!link==NULL) { if((*link).getData()<minNumber) { minNumber=(*link).getData(); } link=(*link).getNode(); } return minNumber; } bool contain(int value) { ListNode* link=first; while(!link==NULL) { if((*link).getData()==value) { return true; } link=(*link).getNode(); } return false; } bool containRecursively(int value) { ListNode* link=check; if(!link==NULL) { if((*link).getData()==value) { check=first; return true; } else { check=(*check).getNode(); return this->containRecursively(value); } } check=first; return false; } List reverse() { List newList; ListNode *link=first; while(!link==NULL) { newList.addNodeFirst((*link).getData()); link=(*link).getNode(); } return newList; } void coutList() { if(!first==NULL) { ListNode *link=first; cout<<"链表元素是："<<endl; while(!link==NULL) { cout<<(*link).getData()<<" "; link=(*link).getNode(); } cout<<endl; } else { cout<<"链表为空"<<endl; } } int Length() { return this->NodeNumbers; }};
int main(){ List list; while(true) { cout<<"***************************************"<<endl; cout<<"0. 自动初始化链表"<<endl; cout<<"1. 手动初始化链表"<<endl; cout<<"2. 打印链表长度"<<endl; cout<<"3. 打印链表最小元素"<<endl; cout<<"4. 打印链表元素"<<endl; cout<<"5. 打印倒序链表元素"<<endl; cout<<"6. 查找链表元素(非递归)"<<endl; cout<<"7. 查找链表元素(递归)"<<endl; cout<<"8. 退出按其他数字键"<<endl; cout<<"***************************************"<<endl; cout<<"请选择菜单："; int choice = 0; cin>>choice; switch(choice) { case 0: { cout<<"请输入链表的长度"<<endl; int number=0; cin>>number; for(int i=0;i<number;i++) { list.addNode(i+1); } list.coutList(); break; } case 1: { char level = 'N'; while(level=='N'||level=='n') { int number = 0; cout<<"请输入存入链表的数据（int型）："; cin>>number; list.addNode(number); cout<<"结束（N/Y）:"; cin>>level; } system("cls"); list.coutList(); break; } case 2: { cout<<"链表长度为："<<list.Length()<<endl; break; } case 3: { cout<<"最小元素为："<<list.getMin()<<endl; break; } case 4: { list.coutList(); break; } case 5: { cout<<"倒序链表"; list.reverse().coutList(); break; } case 6: { int number = 0; cout<<"请输入要查找的元素："; cin>>number; if(list.contain(number)==0) { cout<<"不存在元素"<<number<<endl; } else { cout<<"存在元素"<<number<<endl; } break; } case 7: { int number = 0; cout<<"请输入要查找的元素："; cin>>number; if(list.containRecursively(number)==0) { cout<<"不存在元素"<<number<<endl; } else { cout<<"存在元素"<<number<<endl; } break; } default: { cout<<"您选择了退出程序..."<<endl; break; } } } return 0;}
