当前位置导航:炫浪网>>网络学院>>编程开发>>C++教程>>C++进阶与实例

单链表的基础操作方法

/*
 单链表的基本操作
 具体操作包括:
  链表的初始化,清空
  3种插入方法:在第一个结点之前,最后一个结点之后,任位置插入
  2种查找方法:1.查找某一元素值的位置2.查找某一位置的元素
  2种删除方法:1.删除给定值的第一个结点 2.删除给定值的所有结点
  2种修改方法:1.修改给定值的第一个结点并赋其指定的新值 2.修改给定值的所有结点为其新值
  1种遍历方法:打印所有的元素值
*/
#include <iostream>
using namespace std;
typedef int T;//自定义数据类型
/*
 定义结点
*/
struct Node{
 T data;
 Node * next;
 Node(const T& n):data(n),next(NULL){}
};
/*
 定义链表
*/
class LinkList{
 private:
  Node* head;
  
 public:
  /*
   初始化一个带头结点的链表
  */
  LinkList(){
   head = new Node(0);
  }
  
  /*
   销毁该链表,并释放内存空间
  */
  ~LinkList(){
   Node *p = head;
   while(p != NULL){
    head = head->next;
    delete p;
    p = head;
   }
  }
  /*
   将链表置为空表,并释放原链表结点的内存空间
  */
  void clear(){
   Node *p = head->next;
   while(p != NULL){
    head->next = p->next;
    delete p;
    p = head->next;
   }
  }
  
  
  /*
   将无素插入到第一个结点之前
  */
  void insertFirst(const T &e){
   Node *p = new Node(e);
   p->next = head->next;
   head->next = p;
  }
  
  /*
   将无素插入到最后一个结点之后
  */
  void insertLast(const T &e){
   Node *s = new Node(e);
   Node *p= head;
   while(p->next != NULL){
    p = p->next;
   } 
   p->next = s;  [Page]
  }
  
  /*
   在链表的第i个位置之前插入元素e
   前置条件:i大于0,小于l.length()+1
  */
  void insert(int index,const T &e){
   if(index < 1 || index > length()+1){
    cout << \"invalid index:\" << index;
    return;
   }
   Node *s = new Node(e);
   Node *p = head;
   int j = 1;
   while(j < index){
    p = p->next;
    j++;
   }
   
   s->next = p->next;
   p->next = s;
 
  }
  
 
  /*
   查找第元素e在链表中的位置,不存在,则返回-1
  */
  int indexOf(const T &e){
   int i=0;
   Node *p = head->next;
   while(p != NULL){
    i++;
    if(e == p->data){
     return i;
    }
    p = p->next;
   }
   return -1;
  }
  
  /*
   返回元素第一个结点的值
  */
  T getFrist(){
   if(head->next == NULL){
    cout << \"this  is a empty LinkList\" << endl;
    return -1;
   }
   return head->next->data;
  }
  
  /*
   返回元素最后一个结点的值
  */
  T getLast(){
   Node *p = head;

共2页 首页 上一页 1 2 下一页 尾页 跳转到
相关内容
赞助商链接