SHARE
TWEET

LinkList.h

qaqwq Sep 22nd, 2019 110 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include<ctime>
  3. #include<cstdlib>
  4.  
  5. using namespace std;
  6. const int MaxSize = 100;
  7.  
  8. // 使用nullptr代替NULL
  9. template <typename DataType>
  10. struct Node {
  11.     DataType data;
  12.     Node<DataType> *next;
  13.     Node() {data = 0; next = nullptr; }
  14.     Node(DataType _code) { data = _code; next = nullptr; } // 添加了构造函数
  15.     Node(DataType _code, Node<DataType> *_next) { data = _code; next = _next; } // 添加了构造函数
  16. };
  17.  
  18. template <typename DataType>
  19. class LinkList {
  20.     public:
  21.         LinkList() {
  22.             first = new Node<DataType>;
  23.         }
  24.         ~LinkList() {
  25.             deleteAll();
  26.         }
  27.         int length() {
  28.             Node<DataType> *p = first -> next;
  29.             int count = 0;
  30.             for (; p != nullptr; count++)  p = p -> next;
  31.             return count;
  32.         }
  33.         void deleteAll(){
  34.             Node<DataType> *p = first -> next;
  35.             Node<DataType> *q = first -> next;
  36.             while (p != nullptr){
  37.                 p = p -> next;
  38.                 delete q;
  39.                 q = p;
  40.             }
  41.             first -> next = nullptr;
  42.         }
  43.  
  44.         //这个也不需要了
  45.         // int locate(DataType x) {
  46.         //     Node<DataType> *p = first -> next;
  47.         //     int count = 1;
  48.         //     while(p != nullptr) {
  49.         //         if(p -> data == x) return count;
  50.         //         p = p -> next;
  51.         //         count++;
  52.         //     }
  53.         //     return 0;
  54.         // }
  55.  
  56.         // 看下面
  57.         // void insert(int i, DataType x) {
  58.         //     Node<DataType> *p = first, *s = nullptr;
  59.         //     int count = 0;
  60.         //     while(p != nullptr && count < i - 1) {
  61.         //         p = p -> next;
  62.         //         count++;
  63.         //     }
  64.         //     if(p == nullptr) throw "插入位置错误";
  65.         //     else {
  66.         //         s = new Node<DataType>;
  67.         //         s -> data = x;
  68.         //         s -> next = p -> next;
  69.         //         p -> next = s;
  70.         //     }
  71.         // }
  72.  
  73.         //在头部添加一项, code是密码
  74.         void insertToStartByCode(DataType code) {
  75.             Node<DataType> *newItem = new Node<DataType> (code);
  76.             newItem -> next = first -> next;
  77.             first -> next = newItem;
  78.         }
  79.  
  80.         // 这里删除应该是以在链表里的顺序来的, 实际上不需要这样
  81.         // 好一点的处理方式是传入密码, 之后搜寻密码相符的项删掉
  82.         // 另外这里应该返回的是一个指向Node<DataType>类型的指针..而不是一个DataType类型的值
  83.         // DataType Delete(int i) {
  84.         //     DataType x;
  85.         //     Node<DataType> *p = first, *q = nullptr;
  86.         //     int count = 0;
  87.         //     while(p != nullptr && count < i - 1) {
  88.         //         p = p -> next;
  89.         //         count++;
  90.         //     }
  91.         // 另外如果p在链尾的话, 是有p -> next == nullptr满足的, 此时是不能抛出错误的.
  92.         //     if(p == nullptr || p -> next == nullptr) {
  93.         //         throw"删除位置错误";
  94.         //     }
  95.         //     else{
  96.         //         q = p -> next;
  97.         //         x = q -> data;
  98.         //         p -> next = q -> next;
  99.         //         delete q;
  100.         //         return x;
  101.         //     }
  102.         // }
  103.  
  104.         Node<DataType> *findFrontOneBySelfCode(DataType code){
  105.             Node <DataType> *p = first;
  106.             while (p -> next != nullptr) {
  107.                 if(p -> next -> data == code) break;
  108.                 p = p -> next;
  109.             }
  110.             // 如果可以找到节点, 此时该节点应为 p->next
  111.             return p;
  112.         }
  113.  
  114.  
  115.         Node<DataType> *deleteByCode(DataType code) {
  116.             Node <DataType> *p = findFrontOneBySelfCode(code);
  117.             if (p -> next == nullptr) return nullptr;
  118.             else {
  119.                 Node <DataType> *foundNode = p -> next;
  120.                 p -> next = foundNode -> next;
  121.                 return foundNode;
  122.             }
  123.         }
  124.  
  125.  
  126.  
  127.         void printList() {
  128.             Node<DataType> *p = first -> next;
  129.             cout << "All Items: ";
  130.             while(p != nullptr) {
  131.                 cout << p -> data << ", ";
  132.                 p = p -> next;
  133.             }
  134.             cout << "\b\b." << endl;
  135.         }
  136.  
  137.         // 不需要单独的查找函数, 功能已合并至删除操作内
  138.         // DataType get(int i) {
  139.         //     Node<DataType>*p=first->next;
  140.         //     int count =1;
  141.         //     while(p!=nullptr&&count<i)
  142.         //     {
  143.         //         p=p->next;
  144.         //         count++;
  145.         //     }
  146.         //     if(p==nullptr) throw"查找位置错误";
  147.         //     else return p->data;
  148.         // }
  149.     private:
  150.         Node<DataType> *first; // head node
  151. };
  152.  
  153.  
  154. // 注意下面几个函数的参数需要传地址的形式, 这也是一开始程序不正常的最直接原因
  155. void store(LinkList<int> &L) {
  156.     if(L.length() >= MaxSize) {
  157.         cout << "存包柜已满!";
  158.         return ;
  159.     }
  160.     int x, b = 9999, a = 1000; // 这里的变量命名.... x => code, b => maxRandomRange, a => minRandomRange
  161.     srand((int) time(0));
  162.     do { // 防止重复
  163.         //x = rand() % (b - a + 1) + b; 这里随机数范围写错了..而且ab均未初始化就拿来使用
  164.         x = (rand() % (b - a + 1)) + a;
  165.     } while(L.findFrontOneBySelfCode(x) -> next != nullptr);
  166.     L.insertToStartByCode(x);
  167.     cout << "存包密码为:" << x << endl;
  168.     L.printList();
  169. }
  170.  
  171. void get(LinkList<int> &L){
  172.     if(L.length() == 0) {
  173.         cout << "当前无包裹." << endl;
  174.         return;
  175.     }
  176.     int x = 0;
  177.     cout << " 请输入密码:";
  178.     cin >> x;
  179.     if(x == 0) return;
  180.     Node<int> *foundItem = L.deleteByCode(x);
  181.     if(foundItem == nullptr) {
  182.         cout << "取件码错误, 取件失败, 取消重试请输入0.\n";
  183.         get(L);
  184.     } else {
  185.         cout << "取件成功.";
  186.         delete foundItem;
  187.     }
  188.     L.printList();
  189. }
  190. void clearList(LinkList<int> &L) {
  191.     cout<<"当前存包柜使用数量:" << L.length() << endl;
  192.     L.deleteAll();
  193.     cout<<"用户删除完成。\n";
  194.     cout<<"当前存包柜使用数量:" << L.length() << endl;
  195. }
  196. void displayList(LinkList<int> &L) {
  197.     cout<<"当前存包柜使用数量:" << L.length() << endl;
  198.     L.printList();
  199. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top