Question

怎样更好的理解C++中的链表的使用？

最好举例说明，用头插法、尾插法以及删除结点等。用的是VC++6.0。拒绝垃圾回答，悬赏100分请高手，回答好的话追加悬赏。

Answer 1

我简单的用比喻来说明。剩下的还是得靠自己对编程的悟性了。

声明：可以把向前挂车厢想象成把后一节车厢的地址赋值给前一车厢的next指针。

首先，我们把链表的节点比喻成火车的车厢。每节车厢的前面都有一个钩子，我们把这想想成指针，他用来连接上一节车厢。

接着，使用尾插法的话，也就是先要找到火车尾，即链表的尾指针。然后把自己要加进去的车厢挂到火车的最后面。最后标记这节车厢为火车尾（把地址赋值给尾指针）。

使用头插法的话，就是先找到火车头，即链表的头指针。然后把头指针后面的那节车厢挂到你要插入链表的那节车厢的后面。最后在把插入链表的那节车厢挂到火车头去（把地址赋值给头指针）。

举例：
（火车车厢）
struct node
{
int num;
node* next;
};
(火车头)node* Head;
(火车尾)node* End;
(车厢1）node* m1;
(车厢2）node* m2;

//开始前链表只有火车头，后面没有车厢，车头也是车尾。

Head=End=NULL;

//1.头插法

//申请车厢1

m1=new node;
m1->next=NULL;

if(Head==NULL) //如果只有火车头执行这里面的
{
Head=m1; //把第一节车厢先挂到车头先
End=m1; //现在只有这节车厢，所以他是尾车厢
}else //如果除了火车头还有其他车厢执行这里面的
{
m1->next=Head; //先把火车头后面的车厢挂到第一节车厢后面先
Head=m1; //再把整串火车挂回车头
}

//2.尾插法

//申请车厢2

m2=new node;
m2->next=NULL;

if(Head==NULL) //如果只有火车头执行这里面的
{
Head=m2; //把第一节车厢先挂到车头先
End=m2; //现在只有这节车厢，所以他是尾车厢
}else //如果除了火车头还有其他车厢执行这里面的
{
End->next=m2; //把车厢挂到车尾去
End=m2; //标记这节车厢是车尾
}

Answer 2

链表是一种有序的列表，链表的内容通常是存储与内存中分散的位置上。
链表的方式有两种1：一种是利用数组结构串连的有序列表。
例如；两个数组，一个存放数据，另一个存放连接的关系。这种缺乏弹性。
2：以动态内存配置的链表，（通常指的链表是一动态内存分配的链表）动态内存配置的链表，
是由许许多多的（node）所链接而成的，每一个结点，包含了数据部分和指向下一个结点的指针（Pointer）。
以动态内存配置的链表，在插入和删除元素的时候，只需要将指针改变指向就可以。
链表和数组一样是一种数据结构，如何使用完全基于你的应用需求。
链表和C++语言本身没有任何联系。很多语言都可以实现链表数据结构。
我讲一下数据和链表的区别有可能帮助你对链表的使用有个感觉。
数组是将元素在内存中连续存放，由于每个元素占用内存相同，所以你可以通过下标迅速访问数组中任何元素。但是如果你要在数组中增加一个元素，你需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果你想删除一个元素，你同样需要移动大量元素去填掉被移动的元素。
链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果你要访问链表中一个元素，你需要从第一个元素开始，一直找到你需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了， 只要修改元素中的指针就可以了。
从上面的比较你可以看出，如果你的应用需要快速访问数据，很少或不插入和删除元素，你就应该用数组；相反， 如果你的应用需要经常插入和删除元素你就需要用链表数据结构了。然后你自己可以想一想什么样的应用用链表合适。
另外，建议你找一本好一点的关于数据结构的书，里面应该关于链表和其上算法的详细介绍。链表本身是一个复杂的数据结构，而且包括很多种类，比如单向链表，双向链表，树，图等，不是一篇文章可以介绍得清楚的。

Answer 3

struct list
{
int number;
list* next;
};
链表其实是一种数据结构。一种逻辑链式存储数据的方式。它由很多的节点连接组成的方式。
简单的如上面定义，number表示内容，next表示指向下一个节点的指针。通过这个指针就可以将很多的节点相连起来。简单的说就是通过这个指针知道当前节点下一个节点连接到什么地方去。如此把所有的节点都连接到一起。并给出一个头节点，也就是链表的第一个节点的指针方便你的操作。
list *Head = NULL;
头上添加一个节点函数：
void AddNodeToHead()
{
// 创建要加入的节点
list *data;
data = new list;
data.number = 10;
data.next = NULL;

//加入
data.next = Head;
Head.next = data;
}

在尾部添加一个节点
void AddNodeToEnd()
{
// 创建要加入的节点
list *data;
data = new list;
data.number = 10;
data.next = NULL;

// 找到尾节点
list* pEnd = Head;
while(pEnd.next != NULL)
{
pEnd = pEnd.next;
}

// 加入
pEnd.next=data;

}

删除一个节点其实就是在链表中查询内容等于要删除节点内容的节点，然后删除。
在查找待删除节点data时，记录它的前一个节点predata.
则关键语句为：
predata.next = data.next;
delete data;// 删除当前节点的空间

Answer 4

我要说的都说了

Answer 5

#include <iostream>
using namespace std;
template <class T>
struct Node{

T data;
Node <T>*next;
};
template <class T>
class LinkList
{
private:
Node <T>*first;
public:
LinkList();
~LinkList();
void Display();
void Insert(int i,T x);
void Invert();
void InsertF(T x);
void InsertR(T x);
void DeleteAll();
};
template <class T>
void LinkList<T>::InsertF(T x)
{
Node <T>*s;
s=new Node<T>;
s->data=x;
s->next=first->next;
first->next=s;
}
template <class T>
void LinkList<T>::InsertR(T x){
Node<T>*r,*s;
for(r=first;r->next!=NULL;r=r->next);
s=new Node<T>;
s->data=x;
s->next=r->next;
r->next=s;
}
template <class T>
LinkList<T>::LinkList(){
first=new Node<T>;
first->next=NULL;
}
template <class T>
LinkList<T>::~LinkList(){
}
template <class T>
void LinkList<T>::Display(){
Node<T> *p;
for(p=first->next;p!=NULL;p=p->next)
cout<<p->data<<" ";
cout<<endl;
}
template <class T>
void LinkList<T>::Insert(int i,T x)
{
int count=0;
Node<T>*p;
for(p=first;p->next!=NULL;p=p->next)
{
if(count=i-1)break;
count++;
}
if(count=i-1)
{
Node<T>*s;
s=new Node<T>;
s->data=x;
s->next=p->next;
p->next=s;
}
else throw"Illegal position";
}
template <class T>
void LinkList<T>::Invert(){
Node<T>*p,*s;
p=first->next;
first->next=NULL;
while(p)
{
s=p;
p=p->next;
s->next=first->next;
first->next=s;
}
}
template <class T>
void LinkList<T>::DeleteAll(){
Node <T>*s,*p;
p=first;
while(p->next)
if(p->next->data>='0'&&p->next->data<='9')
{
s=p->next;
p->next=s->next;
delete s;
}else p=p->next;
}int main()
{
LinkList<char>A;
while(1)
{
char ch;
cin>>ch;
if(ch='#')break;
try{
A.InsertR(ch);
}
catch(const char*message)
{
cout<<message<<endl;
}
}
A.Display();
A.Insert(10,'a');
A.Invert();
A.Display();
A.DeleteAll();
A.Display();
return 0;
}