顺序表和链表的编写以及测试-白红宇

顺序表和链表的编写以及测试

阅读量：6913 次

发布时间：2019-06-27

本文共 5680 字，大约阅读时间需要 18 分钟。

1 #include 
     
       2 using namespace std; 3 int  defaultSize; 4 template 
      
        5 class AList{ 6     private: 7         int maxsize; 8         int listsize; 9         int curr;10         E *listArray;11     public:12         AList(int size=defaultSize){13             maxsize = size;14             listsize = curr = 0;15             listArray = new E[maxsize];16         }17         void clear(){18             delete [] listArray;19             listsize=curr=0;20             listArray =new E [maxsize];21         }22 23         void insert(const E &it){24            if(listsize>maxsize)  cout<<"List capacity exceed";25             for(int i=listsize;i>curr;i--){26                 listArray[i] = listArray[i-1];}27             listArray[curr]=it;28             listsize++;29         }30 31         void append(const E &it){32             if(listsize>maxsize)  cout<<"List capacity exceed";33             listArray[listsize++]=it;34         }35 36         E remove(){37             if(curr<0 || curr>listsize)  cout<<"wrong number";38             E it=listArray[curr];39             for(int i=curr;i
       
        (listsize+1) || i<0)   cout<<"wrong number";51             return listArray[i-1];52          }53          int locate(const E &it){54              curr=0;55              while(listArray[curr]!=it){56                  curr++;57              }58              return curr+1;59          }60          void merge(AList L,AList L1){61             L1.curr=0;62             while(L1.listsize!=0){63                 L.append(L1.listArray[L1.curr]);64                 L1.curr++;65                 L1.listsize--;66             }67             L.display();68          }69          void display(){70              int curr=0;71              while(curr!=listsize){     72              cout<
        
         <<" ";73              curr++;74              }75          };76 };77 void main(){78     AList
         
           L(100),L1(100);79     L.append('a');L.append('b');L.append('c');L.append('d');80     cout<<"创建顺序表1: ";81     L.display();82     int ans=L.locate('a');83     cout<
          
           <<"值为a在表中的位置: "<

1 #include 
     
        2 using namespace std;  3 template 
      
         4 class Link{  5 public:  6     E data;  7     Link *next;  8     Link(const E& elemval,Link* nextval=NULL){data=elemval;next=nextval;}  9     Link(Link* nextval=NULL){next=nextval;} 10 }; 11 template 
       
         12 class LList{ 13     private: 14         Link
        
          *head; 15         Link
         
           *tail; 16         Link
          
            *curr; 17 int cnt; 18 void create(){ 19 curr=head=tail=new Link
           
            ; 20 cnt=0; 21 } 22 void removeall(){ 23 while(head!=NULL){ 24 curr=head; 25 head=head->next; 26 delete curr; 27 } 28 } 29 public: 30 LList(E* A,int n){ 31 create(); 32 for(int i=0;i
            
             next=new Link
             
              (it,curr->next); 39 if(tail==curr){ tail=curr->next;} 40 cnt++; 41 } 42 43 void append(const E it){ 44 tail=tail->next=new Link
              
               (it,NULL); 45 cnt++; 46 } 47 48 E remove(){ 49 if(curr->next==NULL) cout<<"NO element"; 50 E it=curr->next->element; 51 Link
               
                * temp=curr->next; 52 if(tail==curr->next){tail=curr;} 53 curr->next=curr->next->next; 54 delete temp; 55 cnt--; 56 return it; 57 } 58 void movetostart(){ curr=head;} 59 int currPos() const{ 60 Link
                
                  *temp=head; 61 for(int i=0;temp!=curr;i++){ 62 temp=temp->next; 63 } 64 return i; 65 } 66 const E getvalue(int i){ 67 Link
                 
                   *temp=head; 68 for(int j=0;j
                  
                   next;} 70 return temp->data; 71 } 72 int locate(E it){ 73 curr=head; 74 for(int i=0;curr->next!=NULL;i++){ 75 if(curr->data==it) return i+1; 76 curr=curr->next; 77 } 78 } 79 void sort(){ 80 Link
                   
                     *p=head,*q; 81 for(p->next;p-next!=NULL;p = p->next){ 82 for(q=p->next;q;q = q->next){ 83 if(p->data>q->data){ 84 E temp; 85 temp=q->data; 86 q->data=p->data; 87 p->data=temp; 88 } 89 } 90 } 91 92 } 93 void display(){ 94 curr=head; 95 while(curr->next!=NULL){ 96 cout<
                    
                     data<<" "; 97 curr=curr->next; 98 } 99 };100 };

约瑟夫问题：

1 #include
     
       2 using namespace std; 3  4 class Node{ 5     public: 6         Node(int data):data(data),link(NULL){} 7         int data; 8         Node *link; 9 };10 class Josephus{11 public:12     Josephus(int N, int K, int M):N(N),K(K),M(M)13     {14         createList();15         outputList();16     }17 protected:18      void createList();19     void outputList();20 private:21     Node *m_pHead;//循环链表的头节点22     int    N;     //链表节点个数23     int    K;     //第一个报数猴子的序号24     int    M;     //报数出局的数25 };26 void Josephus::createList(){27     Node *pre = NULL;28     Node *cur = NULL;29     Node *p = new Node(1);  30     m_pHead = p;31     cur = p;32     for (int i=2; i<=N; i++)33     {34         p = new Node(i);35         pre = cur;36         cur = p;37         pre->link = cur;38     }39     cur->link = m_pHead;40     int n=N;41     p = m_pHead;42 }43 void Josephus::outputList()44 {45     Node *pre = NULL;46     Node *cur = m_pHead;47     K--;48     while (K--)          49     {50         pre = cur;51         cur = cur->link;52     }53     cout<<"依次出列的猴子编号：";54     while (N--)            55     {56         int s = M-1;57         while (s--)          58         {59             pre = cur;60             cur = cur->link;61         }62         Node *p = cur;63         if(N>=1)64         cout << p->data << ",";65         if(N==0)66         {67             cout<
      
       data<
       
        data<
        
         link;    71         pre->link = cur;72         delete p;73         p=NULL;74     }75 }76 void main(){77     Josephus(5,2,3);78     system("pause");79 }