C++实现链表基本操作

前几天找实习的时候，一个面试官给我留了一个题，做一个链表demo，要求实现创建、插入、删除等操作。

链表是一种常见的数据结构，它是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

我是用C++代码来写的。首先，定义一个linklist.h文件，该文件定义了链表的结点和链表支持的方法。如下所示：

//linklist.h：定义链表结点和方法。 #include 
  
    using namespace std; struct Info { string name; //姓名 int id; //学号 }; //链表定义 struct Node { Info val; Node *next; Node(Info x):val(x),next(NULL) {} }; class LinkList { public: //构造函数 LinkList(); //在链表头部插入结点 void InsertHead(Info val); //插入结点 void Insert(Info val,int pos); //删除结点 void Remove(Info val); //得到链表长度 int Length(); //链表反序 void Reverse(); //查找结点位置 int Find(Info val); //打印链表 void Print(); //析构函数 ~LinkList(); private: Node *head; int length; }; 
  

然后，定义一个linklist.cpp文件，是链表方法的实现。如下所示：

//linklist.cpp：链表方法的实现。 #include "stdafx.h" #include 
  
    #include "linklist.h" using namespace std; //构造函数 LinkList::LinkList() { head = NULL; length = 0; } //析构函数 LinkList::~LinkList() { Node *temp; for(int i=0;i 
   
     next; delete temp; } } //得到链表长度 int LinkList::Length() { return length; } //在链表头部插入结点 void LinkList::InsertHead(Info val) { Insert(val,0); } //插入结点 void LinkList::Insert(Info val,int pos) { if(pos<0) { cout<<"pos must be greater than zero"< 
    
      next = temp; head = node; length++; return; } while(temp!=NULL && index 
     
       next; index++; } if(temp == NULL) { cout<<"Insert failed"< 
      
        next = temp->next; temp->next = node; length++; } //删除结点 void LinkList::Remove(Info val) { int pos = Find(val); if(pos == -1) { cout<<"Delete failed"< 
       
         next; length--; return; } int index = 2; Node *temp = head; while(index < pos) temp = temp->next; temp->next = temp->next->next; length--; } //查找结点位置 int LinkList::Find(Info val) { Node *temp = head; int index = 1; while(temp!=NULL) { if(temp->val.name == val.name && temp->val.id == val.id) return index; temp = temp->next; index ++; } return -1; //不存在返回-1 } //链表反序 void LinkList::Reverse() { if(head==NULL) return; Node *curNode=head,*nextNode=head->next,*temp; while(nextNode!=NULL) { temp=nextNode->next; nextNode->next=curNode; curNode=nextNode; nextNode=temp; } head->next=NULL; head=curNode; } //打印链表 void LinkList::Print() { if(head == NULL) { cout<<"LinkList is empty"< 
        
          val.name<<","< 
         
           val.id< 
          
            next; } cout< 
            
           
          
         
        
       
      
     
    
  

最后，定义一个main.cpp，用来测试链表功能，如下所示：

// main.cpp : 测试链表功能。 #include "stdafx.h" #include 
  
    #include 
   
     #include "linklist.h" using namespace std; int _tmain(int argc, _TCHAR* argv[]) { LinkList head; Info val1,val2,val3,val4; val1.id =1,val1.name="Kevin",val2.id=2,val2.name="Cathy",val3.id=3,val3.name="Lucy",val4.id=4,val4.name="Gravin"; //测试插入功能 cout<<"Insert test:"< 
     
    
  

测试结果如下图：