C++數(shù)據(jù)結構之單鏈表
作者：2012 Silvester
線性表包含數(shù)據(jù)域和指針域。單鏈表用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。
線性表包含 數(shù)據(jù)域和指針域 其中，data存儲數(shù)據(jù)本身的值，next存儲后繼元素的地址 下面的圖表示的是一個數(shù)據(jù)節(jié)點
單鏈表的結構示意圖（包括空的單鏈表）：
單鏈表的節(jié)點類:
- template<classT>
- classNode
- {
- public:
- T data;//數(shù)據(jù)
- Node<T> *next;//next指針
- Node()
- {
- this->next=NULL;//構造空的節(jié)點
- }
- Node(T data,Node<T> *next=NULL)//構造一個節(jié)點
- {
- this->data=data;
- this->next=next;
- }
- };
單鏈表類聲明如下：
- #include<iostream>
- #include "Node.h"//單鏈表節(jié)點類
- template<classT>
- classSinglyLinkedList //單鏈表類
- {
- public:
- Node<T> *head;//單鏈表的頭指針。
- SinglyLinkedList();//構造空的單鏈表。
- SinglyLinkedList(T value[], intn);//構造由指定的數(shù)組提供的單鏈表
- ~SinglyLinkedList();//析構
- boolisEmpty();//判斷是否為空。
- intlength();//獲取長度
- Node<T>* getNode(inti);//返回第i(i>=0)個節(jié)點指針
- T get(inti);//返回第i個元素
- boolset(inti,T x);//設置第i個元素為x
- template<classT> friend std::ostream& operator<<(std::ostream& out,SinglyLinkedList<T> &list);
- Node<T>* insert(inti,T x);//插入第I個節(jié)點并返回第i個節(jié)點的指針
- boolremove(inti,T& old);//刪除第i個元素，將刪除的元素存放到old
- voidclear();//清空單鏈表
- voidconcat(SinglyLinkedList<T> &list);//將List鏈接在當前單鏈表之后
- };
單鏈表部分如構造空的鏈表對象，析構，判斷為空的實現(xiàn)，沒有要講的算法，實現(xiàn)如下：
- template<classT>
- SinglyLinkedList<T>::SinglyLinkedList()//構造空的單鏈表
- {
- this->head=NULL;
- }
- template<classT>
- SinglyLinkedList<T>::~SinglyLinkedList()//析構
- {
- clear();
- }
- template<classT>
- boolSinglyLinkedList<T>::isEmpty()//判斷鏈表是否為空
- {
- returnthis->head==NULL;
- }
單鏈表的遍歷操作，遍歷單鏈表是指從第一個節(jié)點開始訪問，沿著節(jié)點的Next可依次訪問單鏈表中的各個節(jié)點，并且各個節(jié)點只被訪問一次。實現(xiàn)的單鏈表遍歷的基本算法如下：
- intj=0;
- Node<T> *p=head;
- while(p!=NULL&&j<i)
- {
- j++;
- p=p->next;
- }
單鏈表的length(),get(),set(),clear()和輸出等操作都基于以上算法。
- template<classT>
- intSinglyLinkedList<T>::length()
- {
- inti=0;
- Node<T> *p=head;//創(chuàng)建一個用于遍的變量
- while(p!=NULL)
- {
- i++;
- std::cout<<p->data;
- p=p->next;
- }
- returni;
- }
- template<classT>
- Node<T>* SinglyLinkedList<T>::getNode(inti)
- {
- if(i<0)
- returnNULL;
- intj=0;
- Node<T> *p=head;
- while(p!=NULL&&j<i)
- {
- j++;
- p=p->next;
- }
- returnp;
- }
- template<classT>
- T SinglyLinkedList<T>::get(inti)
- {
- Node<T> *p=getNode(i);
- if(p!=NULL)
- returnp->data;
- T d;
- returnd;
- //throw "單鏈表為空或者參數(shù)指定的元素不存在";
- }
- template<classT>
- boolSinglyLinkedList<T>::set(inti,T x)
- {
- Node<T> *p=getNode(i);
- if(p!=NULL)
- {
- p->data=x;
- returntrue;
- }
- returnfalse;
- }
- template<classT>
- std::ostream& operator<<(std::ostream& out,SinglyLinkedList<T> &list)
- {
- Node<T> *p=list.head;
- out<<"(";
- while(p!=NULL)
- {
- out<<p->data;
- p=p->next;
- if(p!=NULL)
- out<<",";
- }
- out<<") ";
- returnout;
- }
- template<classT>
- voidSinglyLinkedList<T>::clear()
- {
- Node<T> *p=head;
- while(p!=NULL)
- {
- Node<T> *q=p;
- p=p->next;
- delete q;
- }
- head=NULL;
- }
單鏈表的插入操作，單鏈表不像順序表，對與表的插入和刪除很簡單：
空表插入/頭插入
- Node<T> *q=NULL;
- if(head==NULL||i<0)//頭插入(單鏈表為空或者)
- {
- q=newNode<T>(x,head);
- head=q;
- }
- 中間插入/尾插入
- p->next=newNode<T>(x,p->next);
- 單鏈表insert()以及參數(shù)構造函數(shù)：
- template<classT>
- Node<T>* SinglyLinkedList<T>::insert(inti,T x)
- {
- Node<T> *q=NULL;
- if(head==NULL||i<0)//頭插入(單鏈表為空或者)
- {
- q=newNode<T>(x,head);
- head=q;
- }
- else
- {
- intj=0;
- Node<T> *p=head;
- while(p->next!=NULL&&j<i-1)
- {
- j++;
- p=p->next;
- }
- q=newNode<T>(x,p->next);
- p->next=q;
- }
- returnq;
- }
- template<classT>
- SinglyLinkedList<T>::SinglyLinkedList(T table[],intn)
- {
- head=NULL;
- if(n>0)
- {
- head=newNode<T>(table[0]);//創(chuàng)建節(jié)點
- Node<T> *rear=head;//創(chuàng)建一個指向頭節(jié)點的指針
- inti=1;
- while(i<n)
- {
- rear->next=newNode<T>(table[i++]);
- rear=rear->next;
- }
- }
- }
單鏈表的刪除操作也分兩類：
頭刪除
- Node<T> *q=head;
- head=head->next;
- delete q;
中間/尾刪除
- Node<T> *q=p->next;
- if(q!=NULL)//判斷刪除節(jié)點
- {
- p->next=q->next;//讓刪除節(jié)點的前驅(qū)Next指針下一節(jié)點
- delete q;//刪除該節(jié)點
- }
單鏈表的刪除函數(shù)remove（）實現(xiàn)：
- template<classT>
- boolSinglyLinkedList<T>::remove(inti,T &old)
- {
- if(i<0||head==NULL)
- {
- Node<T> *q=head;
- old=q->data;
- head=head->next;
- delete q;
- }
- else
- {
- Node<T> *p=getNode(i-1);//獲取刪除節(jié)點的前驅(qū)
- if(p!=NULL&&p->next!=NULL)//判斷刪除節(jié)點和刪除節(jié)點是否為空
- {
- Node<T> *q=p->next;//新建一個節(jié)點指針，將刪除接點復制過去
- old=q->data;
- p->next=q->next;//讓刪除節(jié)點的前驅(qū)Next指針下一節(jié)點
- delete q;//刪除該節(jié)點
- returntrue;
- }
- }
- returnfalse;
- }
- 單鏈表的鏈接函數(shù)：concat()
- template<classT>
- voidSinglyLinkedList<T>::concat(SinglyLinkedList<T> &list)
- {
- if(this->head==NULL)
- {
- this->head=list->head;
- }
- else
- {
- Node<T> *p=head;
- while(p->next!=NULL)
- {
- p=p->next;
- }
- p=list->head;
- }
- list->head=NULL;//設置單鏈表為空，否則運行出錯
- }
以上對C++單鏈表的分析 添加一個學生結構和一個測試函數(shù)：
- Student.h
- structStudent
- {
- charnumber[10]; //學號
- charname[20]; //姓名
- doublescore; //得分
- friend std::ostream& operator<<(std::ostream& out,Student &stu)
- {
- out<<"學號："<<stu.number<<"姓名："<<stu.name<<"得分："<<stu.score;
- returnout;
- }
- };
- 主函數(shù)：
- #include<iostream>
- #include "SinglyLinkedList.h"
- #include "Student.h"
- void_TestToSinglyLinkedList()
- {
- Student data[]={{"090313018","Silvester",45.4},{"090313018","捐贈",45.4},{"090313018","版主",45.6}};
- SinglyLinkedList<Student> m(data,3);
- Student t;
- std::cout<<(m.isEmpty()?"不為空！":"該鏈表為空！")<<std::endl;
- std::cout<<"長度："<<m.length()<<std::endl;
- std::cout<<"移除2個學生"<<m.remove(1,t)<<std::endl;
- std::cout<<"t:"<<t<<std::endl;
- std::cout<<"2個學生信息"<<m.getNode(1)<<std::endl;
- Student s={"415646","fdsfs",453.1};
- std::cout<<m.get(1)<<m.set(1,s)<<m.insert(5,s)<<std::endl;
- }
- voidmain()
- {
- _TestToSinglyLinkedList();
- system("pause");
- }
提供源代碼下載地址：http://39327.42la.com.cn/DataFile/Code/C++/SinglyLinkedList.zip
原文地址：http://www.cnblogs.com/Arrays/archive/2012/02/01/2335164.html
【編輯推薦】
責任編輯：彭凡
來源：
博客園
