Evo. G Tech Team Forum
Welcome to Evo. G Tech Team Forum. We have moved to a new website : www.evogtechteam.com

Thanks you.

by Evo. G Tech Team Management.

用C++写出自定义链表list[已更新]

View previous topic View next topic Go down

用C++写出自定义链表list[已更新]

Post by too wei on July 20th 2015, 01:24

为了简化,只写出了几项简单的功能,如发现任何遗漏之处或bug,欢迎留言
Code:
//list.h
#include <iostream>
using namespace std;


struct node
{
   int data;
   node * next;
   node * perior;
};

class list
{
private:
   node * current;
   node * head;
   int size;
public:
   list();
   ~list();

   void print();
   bool is_empty()const   {return size==0;}
   bool insert(const int & item,int pos = 0); //default insert at front
   bool Delete(const int & pos); //here use Delete not delete because delete is a keyword in c++
   const int find(const int & target);
   const int count(const int & target);
   const int & length()const   {return size;}
   const int & operator[](int pos);
};

/////////////////////////////////////////////////////////////////////////////////////////////////////

list::list():size(0)
{
   current = new node;
   head = new node;
}

list::~list()
{
   if(size != 0)
   {
      current = head->next;
  while(current->next != NULL)
      {
         current->perior->next = current->next;
         current->next->perior = current->perior;

         delete current;
         current = head->next;
      }
      delete current;
      delete head;
   }
}

void list::print()
{
   if(size != 0)   //if not empty
   {
      current = head;
      for(int i = 0;i<size;i++)
      {
         cout<<i<<". "<<current->data<<endl;
 current = current->next;
      }
   }
}

bool list::insert(const int  & item,int pos)
{
   node * thing = new node;
   thing->data = item;

   if(pos>size)   pos = size;

   if(pos ==0)
   {
      if(size == 0)
      {
         head = thing;
         head->perior = NULL;
         head->next = NULL;
      }
      else
      {
         thing->next = head;
         head->perior = thing;
         head = thing;
      }
      size++;
   }
   else
   {
      node * temp = new node;
      current = head;
      for(int i = 0;i<pos-1;i++)
         current = current->next;

      temp = current->next;
      
      current->next = thing;
      thing->next = temp;
      thing->perior = current;
      if(temp != NULL)   temp->perior = thing;

      size++;
   }

   return true;
}

bool list::Delete(const int & pos)
{  
   if(pos > size)   return false;

   node * temp = new node;  
   if(pos == 0)   //when delete the head
   {
      temp = head;
      head = head->next;
      head->perior = NULL;
      delete temp;
   }
   else
   {
  
      temp = head;
      for(int i = 0;i<pos;i++)
         temp = temp->next;   //go to the target

      current = temp->perior;
      current->next = temp->next;
      if(temp->next != NULL)   temp->next->perior = current;   //means we do not deleting last element
      delete temp;

   }
   size--;
   return true;
}

const int list::find(const int  & target)
{
   if(size != 0)
   {
      int pos = 0;
      for(current = head;current->next != NULL;current = current->next)
      {
         if(current->data == target)
            return pos;   //return the position
         pos++;
      }
   }
   return -1;   //return -1 if no found
};

const int list::count(const int & target)
{
   int count = 0;
   if(size != 0)
   {
      for(current = head;current != NULL;current = current->next)
      {
         if(current->data == target)
            count++;
      }
   }
   return count;
}

const int & list::operator[](int pos)
{
   if(pos > size) pos = size;
   current = head;
   if(pos != 0)
   {
   for(int i = 0;i<pos;i++)
   {
  current = current->next;
   }
   }
   return current->data;

}


这是一个拿来测试list的代码
Code:
int main()
{
 list li;
 if(li.is_empty())
 {
 for(int i = 0;i<8;i++)
 {
 li.insert(i*2);
 }
 }
 else
 {
 cout<<"The list is not empty!"<<endl;
 }

 cout<<"First print out"<<endl;
 li.print();
 cout<<"Integer 6 at position "<<li.find(6)<<endl;
 cout<<endl;

 cout<<"Deleting integer at position 3"<<endl;
 cout<<"Inserting an integer 6 at the last position of list"<<endl;
 li.Delete(3);//delete position 3
 li.insert(6,li.length()); //insert at last and now, got 2 interger 6
 cout<<"Second print out"<<endl;
 li.print();
 cout<<"There are "<<li.count(6)<<" integer 6"<<endl;
 cout<<"The length of list is "<<li.length()<<endl;
 cout<<"The li[1] is "<<li[1]<<endl;

 return 0;
}

too wei
Sponsor
Sponsor

Posts : 31
Points : 16571
Reputation : 0
Join date : 2015-04-21
Age : 18
Location : Johor

View user profile

Back to top Go down

View previous topic View next topic Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum