/*
单链表的基本操作
具体操作包括:
链表的初始化,清空
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;