开源中文网

您的位置: 首页 > 编程开发 > 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; 

[NextPage] 

while(p->next != NULL){ 
p = p->next; 

return p->data; 

/* 
返回链表从工作出发第一个结点开始,第index位置的元素值 
*/ 
T getElement(int index){ 
if(index < 1 || index > length()+1){ 
cout << \"invalid index:\" << index; [Page] 
throw \"erro\"; 

Node *p = head->next; 
int j = 1; 
while(j < index){ 
p = p->next; 
j++; 

return p->data; 


/* 
删除所有结点值为e的所有结点 
*/ 
void removeAll(const T &e){ 
Node *p = head; 
Node *q = head; 
while(p != NULL && p->next != NULL){ 
q = p->next; 
if(e == q->data){ 
p->next = q->next; 
delete q; 
continue; 

p = p->next; 



/* 
将所有结点值为e的结点的值替换为一个新值 
*/ 
void updateAll(const T &e,const T &ne){ 
Node *p = head; 
Node *q = head; 
while(p != NULL && p->next != NULL){ 
q = p->next; 
if(e == q->data){ 
q->data = ne; 
continue; 

p = p->next; 



/* 
删除第一个值为e的结点 
*/ 
void remove(const T &e){ 
Node *p = head; 
Node *q = head; 
while(p != NULL && p->next != NULL){ 
q = p->next; 
if(e == q->data){ 
p->next = q->next; 
delete q; 
return; 

p = p->next; 


[Page] 

/* 
返回链表的长度 
*/ 
int length(){ 
Node *p = head; 
int i = 0; 
while(p->next != NULL){ 
p = p->next; 
i++; 

return i; 


/* 
打印链表的所有无素 
*/ 
void travel(){ 
Node *p = head->next; 
if(p == NULL){ 
cout<< \"has no items\" << endl; 

while(p != NULL){ 
cout << p->data << ’ ’; 
p = p->next; 

cout << endl; 

}; 
int main(){ 
LinkList l; 
for(int i=1;i<=20;i++){ 
//l.insertFirst(i); 
//l.insertLast(i); 
l.insert(i,i); 

l.insert(15,15); 
l.insert(17,15); 
l.insert(8,15); 
l.travel(); 
//cout << l.indexOf(15) << endl; 
// cout << l.getElement(0) << endl; 
l.updateAll(15,888); 
l.travel(); 
cout << l.getLast() << endl; 
l.clear(); 
l.travel(); 

return 0; 

Tags:基础 方法
关于开源中文网 - 联系我们 - 广告服务 - 网站地图 - 版权声明