Question

谁告诉我c++里的链表是什么东西啊？

谁告诉我c++里的链表是什么东西啊？
链表的原理，写程序时的格式。
于其他类有什么区别~~
有哪些容易错的地方，和需要注意的地方。
不要太深，大二水平即可~~要自己总结的，不要大段大段复制粘贴的~~

Answer 1

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

Answer 2

我是一个大四的。就你的问题我可以从一下的几个方面来解释“
1 你c++基础怎么样？如果不好，那就没办法了，重新去看看那些基础的东西
2 如雨你的基础比较的好，那就没问题了。只要原理明白了就好了，原理主要：
其实链表从表面上的意思就很好理解。琏起来的一张表而已。就是把一些数据保存起来，分为几个独立的单元保存。你要去访问护着操作这些单元，你必须有个头，就是从什么地方去访问，一般就叫头连接。一般这个都是告诉你的，然后就是根据提示，你去访问其他的了，给的提示就是下一个单元的地址，你可以把这些单元看成你要去拜访的人，你只知道第一个人的地址，第二个人的地址可以从第一个那里得到，第三个人的地址可以第二个人那里得到，已次类推。。。。。。，所以一个单元包括了两个能容，一个是下个已人的地址，一个是你要拜访（访问）的能容，能容可以有多个。
其他的双向链表等都是在这个基础上加上的。。。。。。。
不知道明白了没有。。。。。。。。

Answer 3

链表算是种数据结构吧。
说白了就是内存里非连续的记录用指针给串联起来，主要注意的是第一个节点和最后个节点只有一个指针，中间的都有两个指针。像插入或者删除节点，其实就是修改指针的过程。
#include <stdlib.h>
#define MAX 10

struct List {
int number;
char name[MAX];
struct List *Next;
};

typedef struct List Node;

typedef Node *Link;

Link createList(Link Head) {
int newNumber;
char newName[MAX];

Link Pointer;
Link New;

int i;

printf("首节点内存分配\n");
Head = (Link)malloc(sizeof(Node));

if(Head == NULL) {
printf("首节点内存分配错误\n");
}
else {
newNumber = 1;

printf("输入首节点数据项2 ( <=10 char ) : ");
scanf("%s",newName);

printf("保存数据项到首节点\n");
Head->number = newNumber;
for(i=0;i<MAX;i++) {
Head->name[i] = newName[i];
}
Head->Next = NULL;

printf("建立指向首节点的节点\n");
Pointer = Head;

while(1) {
newNumber++;

printf("新节点分配内存\n");
New = (Link)malloc(sizeof(Node));

if(New == NULL) {
printf("新节点内存分配失败\n");
}
else {
printf("输入新节点数据项2 '0' 退出 : ");
scanf("%s",newName);

if(newName[0] == '0') {
printf("节点输入完毕\n");

break;
}

printf("保存数据项到节点\n");
New->number = newNumber;
for(i=0;i<MAX;i++) {
New->name[i] = newName[i];
}

New->Next = NULL;

printf("新节点作为当前节点的下一节点\n");
Pointer->Next = New;

printf("当前节点指向新节点，完成组链\n");
Pointer = New;
}
}

return Head;
}
}

void printList(Link Head) {
Link Pointer;
Pointer = Head;

printf("打印链表\n数据项1\t数据项2\n");
while(Pointer != NULL) {
printf("%d\t",Pointer->number);
printf("%s\n",Pointer->name);

Pointer = Pointer->Next;
}
}

void freeList(Link Head) {
Link Pointer;

while(Head != NULL) {
Pointer = Head;
Head = Head->Next;
printf("释放节点 %d\n",Pointer->number);
free(Pointer);
}
}

int main() {
Link Head;

Head = createList(Head);

if(Head != NULL) {
printList(Head);
freeList(Head);
}

return 0;

}

以上是链表的建立和释放
结果为
首节点内存分配
输入首节点数据项2 ( <=10 char ) : aaa
保存数据项到首节点
建立指向首节点的节点
新节点分配内存
输入新节点数据项2 '0' 退出 : bbb
保存数据项到节点
新节点作为当前节点的下一节点
当前节点指向新节点，完成组链
新节点分配内存
输入新节点数据项2 '0' 退出 : ccc
保存数据项到节点
新节点作为当前节点的下一节点
当前节点指向新节点，完成组链
新节点分配内存
输入新节点数据项2 '0' 退出 : ddd
保存数据项到节点
新节点作为当前节点的下一节点
当前节点指向新节点，完成组链
新节点分配内存
输入新节点数据项2 '0' 退出 : 0
节点输入完毕
打印链表
数据项1 数据项2
1 aaa
2 bbb
3 ccc
4 ddd
释放节点 1
释放节点 2
释放节点 3
释放节点 4

Answer 4

这两天我也一直在研究链表,下面是我自己写的一个头文件,实现了链表的创建,删除,查询等操作,希望对你有所帮助.
#ifndef MYLIST_H
#define MYLIST_H

#include <iostream>
#include <fstream>
using std::endl;

template <class T> //结点
class Node
{
public:
Node();
Node(T _data);
T GetData();
T data;
Node<T> *next;
};

template <class T>
Node<T>::Node()
{
next=0;
}

template <class T>
Node<T>::Node(T _data):data(_data),next(0){}

template<class T>
T Node<T>::GetData()
{
return data;
}

template<class T>
class Link
{
public:
Link();
Link(T _data); //构造链表时,建立一个带头结点的链表
~Link(); //析构函数,销毁对象时,把链表中的元素都删除
bool IsEmpty(); //链表是否为空
void InsertEnd(T item); //在表尾添加结点
void Print(); //打印链表中所有的元素
void Search(T key); //查寻链表中的某个元素,关键字为key
void Delete(T key); //删除结点,关键字为key
void DeleteAll(); //删除所有的结点
void SaveToFile(char *path); //将链表中的数据全部写入文件中
int GetCount() //返回count的值
{
return count;
}
void Modify(T old_data); //修改链表中的信息,查找数据old_data,找到后修改它
private:
Node<T> *head,*end; //链表的头指针和尾指针
Node<T> *currPtr,*prePtr; //遍历链表时,指向当前结点的指针和前一结点的指针
int count; //扫描链表时,记录结点的个数
};

template<class T>//构造链表时,建立一个带头结点的链表
Link<T>::Link()
{
head=end=new Node<T>;
count=0;

}

template<class T>//构造链表时,建立一个带头结点的链表
Link<T>::Link(T _data)
{
head=end=new Node<T>(_data);
count=0;
}

template<class T>
Link<T>::~Link() //析构函数,销毁对象时,把链表中的元素都删除
{
prePtr=head;
currPtr=head->next;
while(!IsEmpty()) //删除其他结点
{
prePtr->next=currPtr->next;
delete currPtr;
currPtr=prePtr->next;
}
delete head; //删除头结点
}

template<class T>
bool Link<T>::IsEmpty()
{
if(head->next==0)
return true;
else
return false;
}

template<class T>
void Link<T>::InsertEnd(T item)
{

end->next=new Node<T>(item);
end=end->next;
}

template<class T>
void Link<T>::Print()
{
if(IsEmpty())
{
cout<<"没有记录!"<<endl;
}
else
{
count=0;
currPtr=head->next;
while(currPtr)
{
cout<<currPtr->GetData()<<endl;
count++;
currPtr=currPtr->next;
}
cout<<"共查找到"<<count<<"条记录."<<endl;
}
}

template<class T>
void Link<T>::Search(T key)
{
if(IsEmpty())
{
cout<<"没有记录!"<<endl;
}
else
{
count=0;
currPtr=head->next;
while(currPtr)
{
if(currPtr->GetData()==key)
{
cout<<currPtr->GetData()<<endl;
count++;
}
currPtr=currPtr->next;
}
cout<<"共查找到"<<count<<"条记录."<<endl;
}
}

template<class T>
void Link<T>::Delete(T key) // 删除链表中,关键字为key的结点
{
if(IsEmpty())
{
cout<<"没有记录!"<<endl;
}
else
{
count=0;
do
{

currPtr=head->next;
prePtr=head;
while(currPtr)
{
if(currPtr->GetData()==key)
break;
prePtr=currPtr;
currPtr=prePtr->next;
}
if(currPtr)
{
prePtr->next=currPtr->next;
delete currPtr;
count++;
}
}while(currPtr);
if(count!=0)
{
cout<<"删除成功!此次共删除"<<count<<"个记录。"<<endl;
}
}
}

template<class T>
void Link<T>::DeleteAll() //删除所有的结点
{
if(IsEmpty())
{
cout<<"没有记录!"<<endl;
}
else
{
count=0;
currPtr=head->next;
while(currPtr)
{
head->next=currPtr->next;
delete currPtr; //依次删除head结点的下一个结点..直到删除完所有结点
count++;
currPtr=head->next;
}
end=head; //删除完后,链表只剩下头结点,所以要把end=head
if(count!=0)
{
cout<<"删除成功!此次共删除"<<count<<"个记录。"<<endl;
}
}
}

template<class T>
void Link<T>::SaveToFile(char *path)
{
ofstream outfile(path,ios::out);
if(outfile)
{
currPtr=head->next;
while(currPtr)
{
outfile<<currPtr->GetData();
currPtr=currPtr->next;
}
}
outfile.close();
}

template<class T>
void Link<T>::Modify(T old_data)
{
if(IsEmpty())
{
cout<<"没有记录!"<<endl;
}
currPtr=head->next;
while(currPtr)
{
if(currPtr->data==old_data)
{
cout<<"请输入新的值:"<<endl;
T new_data;
cin>>new_data;
currPtr->data=new_data;
}
currPtr=currPtr->next;
}

}
#endif
下面写个主函数来测试:
#include "stdafx.h"
#include "Mylist.h"
#include <iostream>
using namespace std;

int main(int argc, char* argv[])
{
int i;
Link<int> link1; //创建一个int型的链表
for(i=0;i<3;i++) //在链表的未尾添加数据
{
int a;
cout<<"input a:";
cin>>a;
link1.InsertEnd(a);
}
link1.Print();
Link<double> link2; //创建一个double型的链表
for(i=0;i<3;i++) //在链表的未尾添加数据
{
double b;
cout<<"input b:";
cin>>b;
link2.InsertEnd(b);
}
link2.Print();
return 0;
}

Answer 5

链表是指将若干个数据项按一定的规则连接起来的表，其中的数据项成为结点。链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量，以head表示，它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。因此，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。