main.cpp

//#include 
     
      #include "link_list.h"    /* run this program using the console pauser or add your own getch, system("pause") or input loop */int main(void) {    LinkList
      
        l;    int c = 0;    int position = 0;        while (c != 14){        cout << endl << "1. 创建线性表.";        cout << endl << "2. 线性表长度.";        cout << endl << "3. 判断是否为空.";        cout << endl << "4. 按位置获取元素值";        cout << endl << "5. 按位置修改元素值";        cout << endl << "6. 遍历线性表";        cout << endl << "7. 按值查找";        cout << endl << "8. 插入元素";        cout << endl << "9. 删除元素";        cout << endl << "10. 清空线性表";        cout << endl << "11. 销毁线性表";        cout << endl << "12. JosephLoop(Warming: will delete all data)";         cout << endl << "13. Circle";        cout << endl << "14. 退出";        cout << endl << "选择功能(1~13):";        cin >> c;        switch (c) {            case 1:l.CreateList(DEFAULT_SIZE);    break;                         case 2:cout << l.Length();    break;                        case 3:                    if(l.Empty()){                    cout << "empty";                }else{                    cout << "not empty";                }break;                            case 4:                int eDef;                cout << "position:";                cin >> position;                l.GetElem(position, eDef);                cout << "\nvalue:" << eDef;                break;                            case 5:                int eCha;                cout << "position:";                cin >> position;                cout << "\nvalue:";                cin >> eCha;                l.SetElem(position, eCha);                break;                            case 6:                l.Traverse();                 break;                            case 7:                int testLocate;                cin >> testLocate;                cout << l.Locate(testLocate);                break;                            case 8:                 int insVar;                 cout << "insert position:";                 cin >> position;                 cout << "\ninsert value:";                 cin >>  insVar;                 l.Insert(position, insVar);                 break;                             case 9:                int DelVar;                cout << "delete position:";                cin >> position;                l.Delete(position, DelVar);                break;                            case 10:                l.Clear();                cout << "\ncleared.\n";                break;                            case 11:                l.~LinkList();                cout << "\ndestoried.\n";                break;                            case 12:                l.JosephLoop();                                break;            case 13:                l.Circle();            default:                cout << "invail input, please input again.";                break;        }            }    return 0;}
      
     

 

link_list.h

#ifndef __LINK_LIST_H__#define __LINK_LIST_H__#define DEFAULT_SIZE 3#include 
     
       //#include "node.h"                // 结点类模板using namespace std;template 
      
       struct Node{            // 数据成员:    ElemType data, password;            // 数据域    Node
       
         *next;    // 指针域};/*template 
        
         struct CIRCLE{    //数据成员    ElemType heart, half;    CIRCLE
         
           *next; }; */template 
          
           class LinkList { private: // 链表实现的数据成员: Node
           
             *head; // 头结点指针 int length; //单链表表长，即结点数 public: //线性链表方法声明: void Init(); // 初始化线性表 void CreateList( int num); void CreateListPlus(int num); void Clear(); // 将线性表清空 virtual ~LinkList( ); //void DestoryList() // 销毁线性表 int Length() ; // 求线性表长度 bool Empty(); // 判断线性表是否为空 bool SetElem(int position, ElemType e); bool GetElem(int position, ElemType &e); int Locate(ElemType e); bool Insert(int position, ElemType e);// 插入元素 bool Delete (int position, ElemType &e); void Traverse(); // 遍历线性表 void JosephLoop(); //joseph环 void Circle(); //圆类型操作 /*任务：编号是1，2，……，n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。要求：利用单向循环链表（单链表）存储结构模拟此过程，按照出列的顺序=输出各个人的编号。测试数据：m的初值为20，n=7 ，7个人的密码依次为3，1，7，2，4，7，4，首先m=6，则正确的输出是什么？要求：输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。输出形式：建立一个输出函数，将正确的输出序列数据结构：typedef struct Node{ int data; int password; struct Node *next;}Node, *LinkList;基本操作： //初始化单链表//给每个人赋密码//确定需要处理的人数//确定开始的上限值//得到正确的顺序//输出结果 */ //int GetPrior(ElemType e, ElemType &x); //int GetNext(ElemType e, ElemType &x); //Node
            
              *GetElemPtr(int position);};template 
             
              void LinkList
              
               ::Init(){ head = new Node
               
                ; // 构造头指针 head -> next = NULL;}template 
                
                 void LinkList
                 
                  ::CreateList(int num){ Node
                  
                    *p = head, *q; //if(length>0) Clear(); /*******加入此句会崩溃 cout<<"请依次输入"<
                   
                    <<"个元素值："<
                    
                      ; cin >> q -> data; //生成新节点 p -> next = q; p = q; } q -> next = NULL; length = num; return;}template 
                     
                      void LinkList
                      
                       ::CreateListPlus(int num){ Node
                       
                         *p = head, *q; //if(length>0) Clear(); /*******加入此句会崩溃 cout<<"请依次输入"<
                        
                         <<"个元素值和内容值："<
                         
                           ; cout << "请输入第" << i << "个元素值："; cin >> q -> data; //生成新节点 cout << "\n请输入第" << i << "个内容值"; cin >> q -> password; p -> next = q; p = q; } q -> next = NULL; length = num; return;}template 
                          
                           int LinkList
                           
                            ::Length() { return length;}template 
                            
                             bool LinkList
                             
                              ::Empty() {// 如线性表为空，则返回true，否则返回false return head->next == NULL; // return length==0; }template 
                              
                               bool LinkList
                               
                                ::GetElem(int position, ElemType &e){// 将线性表的第position个位置的元素赋值为e, // position范围错 if (position < 1 || position > length) { return false; }else{ // position合法 Node
                                
                                  *tmpPtr = head -> next; int j=1; while( j< position ){ tmpPtr = tmpPtr -> next; j++; } e = tmpPtr -> data; return true; }}template 
                                 
                                  bool LinkList
                                  
                                   ::SetElem(int position, ElemType e){// 将线性表的第position个位置的元素赋值为e if (position < 1 || position > length) { // position范围错 return false; }else{ // position合法 Node
                                   
                                     *tmpPtr = head -> next; int j = 1; while( j< position ){ tmpPtr = tmpPtr -> next; j++; } tmpPtr -> data = e; return true; }}template 
                                    
                                     void LinkList
                                     
                                      ::Traverse() { if(length == 0){ cout << "is Empty\n"; return; } for (Node
                                      
                                        *tmpPtr = head->next; tmpPtr != NULL; tmpPtr = tmpPtr->next){ // 用tmpPtr依次指向每个元素 cout << tmpPtr -> data << '\t'; } cout << endl; return ;}template 
                                       
                                        int LinkList
                                        
                                         ::Locate(ElemType e){ int position = 1; Node
                                         
                                           *p = head -> next; //p指向首元素 while(p != NULL && p -> data != e){ p = p -> next; position++; } if(p == NULL) return 0; else return position;}template 
                                          
                                           bool LinkList
                                           
                                            ::Insert(int position, ElemType e){ if (position < 1 || position > length+1){ // position范围错 return false; // 位置不合法 } Node 
                                            
                                              *newp, *pp; pp = head -> next; //前驱指针 int j; for(j = 1; j < position-1; j++){ pp = pp -> next; } newp = new Node 
                                             
                                              ; //分配新节点 newp -> data = e; //新元素赋值 newp -> next = pp -> next; pp -> next = newp; length++; return true;}template 
                                              
                                               bool LinkList
                                               
                                                ::Delete( int position, ElemType &e){ if(position < 1||position > length) return false; Node
                                                
                                                  *pp, *cp; pp = head; //pp指向头节点 cp = pp -> next; //cp指向首元素 for(int j = 1; j < position; j++){ pp = cp; cp = cp -> next; } pp -> next = cp -> next; //cp指向pos元素，pp指向其前驱 delete cp; //删除pos元素 length--; return true; }template 
                                                 
                                                  void LinkList
                                                  
                                                   ::Clear(){ Node
                                                   
                                                     *p = head -> next; while(p != NULL){ head -> next = p -> next; delete p; //删除节点 p = head -> next; } length = 0; return;} template 
                                                    
                                                     LinkList
                                                     
                                                      ::~LinkList(){ Clear(); delete head; //删除头结点 //return;}template 
                                                      
                                                       void LinkList
                                                       
                                                        ::JosephLoop(){ if(length == 0){ cout << "is Empty\n"; return; } Node
                                                        
                                                          *tmpPtr = head -> next, *tmpQtr = head; cout << "input password:"; for (; tmpPtr -> next != NULL; tmpPtr = tmpPtr -> next){ // 用tmpPtr依次指向每个元素 //cout<
                                                         
                                                          data<<'\t'; cin >> tmpPtr -> password; continue; cout << "I love you."; } cin >> tmpPtr -> password; tmpPtr -> next = head -> next; //将尾节点指向头节点，实现循环 tmpPtr = tmpPtr -> next; cout << "\ninput maxcount:"; int MaxCount; cin >> MaxCount; while(length > 1){ for(int tag = 0; tag < MaxCount; ++tag){ tmpQtr = tmpQtr -> next; //要删除元素节点的前驱 tmpPtr = tmpPtr -> next; //tmpPtr即为要删除元素的节点 } tmpQtr -> next = tmpPtr -> next; cout << tmpPtr->password; MaxCount = tmpPtr -> password; delete tmpPtr; tmpPtr = tmpQtr -> next; length--; } cout<
                                                          
                                                           data; tmpPtr -> next = NULL; delete tmpPtr; head -> next = NULL; length--; cout << "\nall done"; /*********test code cout<
                                                           
                                                            data; for(int i = 0; i < Length()+3; ++i){ cout << tmpPtr->data; tmpPtr = tmpPtr->next; } */ return;} /*任务：编号是1，2，……，n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。要求：利用单向循环链表（单链表）存储结构模拟此过程，按照出列的顺序=输出各个人的编号。测试数据：m的初值为20，n=7 ，7个人的密码依次为3，1，7，2，4，7，4，首先m=6，则正确的输出是什么？要求：输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。输出形式：建立一个输出函数，将正确的输出序列数据结构：typedef struct Node{ int data; int password; struct Node *next;}Node, *LinkList;基本操作： //初始化单链表//给每个人赋密码//确定需要处理的人数//确定开始的上限值//得到正确的顺序//输出结果 */template 
                                                            
                                                             void LinkList
                                                             
                                                              ::Circle(){ LinkList
                                                              
                                                                CI_1; CI_1.CreateListPlus(DEFAULT_SIZE); return;}#endif