【数据结构】实现单链表(c++)
头文件:
#pragma once #include <iostream> using namespace std; template<class Type> class List; // 结点类 template<class Type> class NodeList { friend class List<Type>; public: NodeList(); NodeList(Type d, NodeList<Type> *n = NULL); private: Type data; NodeList<Type>* next; }; // 链表类 template<class Type> class List { public: List(); ~List(); public: void show_list(); void tail_insert(Type const &x); void head_insert(Type const &x); void sort(); void head_delete(); void tail_delete(); void val_insert(Type const &x); NodeList<Type>* find(Type const &x); void val_delete(Type const &x); Type length(); void reverse(); void clear(); void destroy(); void quit_system(Type &x); protected: NodeList<Type>* BuyNode(Type x = Type()) { NodeList<Type>* p = new NodeList<Type>(x); return p; } private: NodeList<Type>* first; NodeList<Type>* last; }; // 结点类的构造函数 template<class Type> NodeList<Type>::NodeList() { data = Type(); next = NULL; } template<class Type> NodeList<Type>::NodeList(Type d, NodeList<Type> *n = NULL) { data = d; next = n; } // 链表类的构造函数 template<class Type> List<Type>::List() { first = last = BuyNode(); } // 链表类的析构函数 template<class Type> List<Type>::~List() { destroy(); } // 显示 template<class Type> void List<Type>::show_list() { NodeList<Type> *p = first->next; while (p != NULL) { cout << p->data << "->"; p = p->next; } cout << "NULL" << endl; } // 尾插 template<class Type> void List<Type>::tail_insert(Type const& x) { NodeList<Type> *p = BuyNode(x); last->next = p; last = p; first->data++; } // 头插 template<class Type> void List<Type>::head_insert(Type const &x) { NodeList<Type> *p = BuyNode(x); p->next = first->next; first->next = p; last = p; for (int i = 0; i < first->data; ++i) { last = last->next; } first->data++; } // 排序 template<class Type> void List<Type>::sort() { if (first->data == 0) { return; } if (first->data == 1) { show_list(); } NodeList<Type> *t = first->next; NodeList<Type> *p = t->next; NodeList<Type> *q = NULL; t->next = NULL; last = t; first->data = 1; while (p != NULL) { val_insert(p->data); q = p; p = p->next; delete q; } } // 头删 template<class Type> void List<Type>::head_delete() { if (first->data == 0) { cout << "the list is empty,cannot delete!" << endl; return; } NodeList<Type> *p = first->next; first->next = p->next; if (first->data == 1) last = first; delete p; first->data--; } // 尾删 template<class Type> void List<Type>::tail_delete() { if (first->data == 0) { cout << "the list is empty,cannot delete!" << endl; return; } NodeList<Type> *s = first; for (int i = 0; i < first->data - 1; ++i) { s = s->next; } s->next = NULL; last = s; delete s->next; first->data--; } // 按值插入 template<class Type> void List<Type>::val_insert(Type const &x) { if (first->data == 0) { tail_insert(x); return; } NodeList<Type> *p = first; NodeList<Type> *s = BuyNode(x); while (p->next->data < x && p->next->next != NULL) { p = p->next; } if (p->next->data>x) { s->next = p->next; p->next = s; first->data++; } else { tail_insert(x); } } // 查找 template<class Type> NodeList<Type>* List<Type>::find(Type const &x) { NodeList<Type> *s = first->next; while (s != NULL) { if (s->data == x) { return s; } s = s->next; } return NULL; } // 按值删除 template<class Type> void List<Type>::val_delete(Type const &x) { if (first->data == 0) { cout << "the list is empty,cannot delete!" << endl; return; } NodeList<Type> *s = find(x); if (s == NULL) { cout << "the number is not exist,can not delete!" << endl; return; } NodeList<Type> *p = first; while (p->next != s) { p = p->next; } if (s->next != NULL) { p->next = s->next; first->data--; delete s; } else { tail_delete(); } } // 求长度 template<class Type> Type List<Type>::length() { return first->data; } // 反转 template<class Type> void List<Type>::reverse() { if (first->data == 0) { return; } if (first->data == 1) { show_list(); } NodeList<Type> *t = first->next; NodeList<Type> *p =t->next; NodeList<Type> *q = NULL; t->next = NULL; last = t; first->data = 1; while (p != NULL) { head_insert(p->data); q = p; p = p->next; delete q; } } // 清空 template<class Type> void List<Type>::clear() { if (first->data == 0) { return; } while (first->next != NULL) { tail_delete(); } } // 摧毁 template<class Type> void List<Type>::destroy() { clear(); delete first; } // 退出系统 template<class Type> void List<Type>::quit_system(Type &x) { x = 0; }
主函数:
// 用c++实现单链表 #include "List.h" int main() { List<int> mylist; int input = 1; int insert; while (input) { cout << "*********************************************************************" << endl; cout << "* [1] show_list [2] tail_insert *" << endl; cout << "* [3] head_insert [4] sort *" << endl; cout << "* [5] head_delete [6] tail_delete *" << endl; cout << "* [7] val_insert [8] find *" << endl; cout << "* [9] val_delete [10] length *" << endl; cout << "* [11] reverse [12] clear *" << endl; cout << "* [13] destroy [14] quit_system *" << endl; cout << "*********************************************************************" << endl; cout << "please choose:"; cin >> input; switch (input) { case 1: mylist.show_list(); break; case 2: cout << "please enter the number want to insert(-1 end):"; while (cin >> insert, insert != -1) { mylist.tail_insert(insert); } break; case 3: cout << "please enter the number want to insert(-1 end):"; while (cin >> insert, insert != -1) { mylist.head_insert(insert); } break; case 4: mylist.sort(); break; case 5: mylist.head_delete(); break; case 6: mylist.tail_delete(); break; case 7: cout << "please enter the number want to insert:"; cin >> insert; mylist.val_insert(insert); break; case 8: cout << "please enter the number want to find:"; cin >> insert; if (mylist.find(insert) == NULL) { cout << "the number is not exist!" << endl; } else { cout << "the number at the " << mylist.find(insert) << endl; } break; case 9: cout << "please enter the number want to delete:"; cin >> insert; mylist.val_delete(insert); break; case 10: cout << "the length is" << " " << mylist.length() << endl; break; case 11: mylist.reverse(); break; case 12: mylist.clear(); break; case 13: mylist.destroy(); break; case 14: mylist.quit_system(input); break; default: break; } } return 0; }
清除:
查找:
头删:
头插:
求长度:
退出系统:
反转:
排序:
尾删:
尾插:
按值删除:
按值插入:
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。