存储方式的分类：
顺序存储结构：静态存储，很容易找到前驱和后续元素，但必须分配最大存储空间，在插入和删除时又会浪费大量的时间。
链式存储结构：动态存储，充分利用存储器的零碎空间，通过两个命令随时向计算机申请存储空间。
概念：为了表示任意存储单元之间的逻辑关系，对于每个数据元素来说，除了要存储它本身的信息（数据域、data外），还要存储它的直接后续元素的存储位置（指针域，link或next）。我们把这两部分信息合在一起称为一个结点node。
（1）N个结点链接在一起就构成了一个链表，N=0时，称为空链表。
（2）定义头指针。
（3）称之为线性链表或单链表。
建立并输出单链表。
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *next;
};
Node *head,*p,*r;//r指向链表的当前最后一个结点，可以称为尾指针
int x;
int main() {
cin>>x;
head=new Node;//申请头结点
r=head;
while(x!=-1) {
p=new Node;//申请一个新结点
p->data=x;
p->next=NULL;
r->next=p;//把新结点链接到前面的链表中，实际上r是p的直接前驱
r=p;//尾指针后移一个
cin>>x;
}
p=head->next;//头指针没有数据，只要从第一个结点开始就可以啦
while(p->next!=NULL) {
cout<<p->data<<' ';
p=p->next;
}
cout<<p->data<<endl;//最后一个结点单独输出，也可以改用do-while循环
return 0;
}
单链表的操作：
1.查找“数据域满足一定条件的结点”
p=head->next;
while((p->data!=x)&&(p->next!=NULL))p=p->next;
//找到第一个就输出
if(p->data==x)//找到了处理
else//输出不存在，如果想找到所有点，如下：
p=head->next;
while(p->next!=NULL) {//一个一个判断
if(p->data==x)//找到一个处理一个
p=p->next;
}
2.取出单链表第i个结点的数据域。
void get(Node *head,int i){
Node *p;int j;
p=head->next;
j=1;
while((p!=NULL)&&(j<i)){
p=p->next;
j+=1;
}
if((p!=NULL)&&(j==i))
cout<<p->data;
else
cout<<"i not exsit";
}
3.插入一个结点在单链表中去
void insert(Node *head,int i,int x){//插入x到第i个元素之前
Node *p,*s;int j;
p=head;
j=0;
while((p!=NULL)&&(j<i-1)){//寻找第i-1个结点，插在他后面
p=p->next;
j=j+1;
}
if(p==NULL)
cout<<"no this position!";
else{
s=new Node;//插入
s->data=x;
s->next=p->next;
p->next=s;
}
}
4.删除单链表中的第i个结点
void delete(Node *head,int i){
Node *p,*s;int j;
p=head;
j=0;
while((p->next!=NULL)&&(j<i-1)){
p=p->next;
j=j+1;
}
if(p->next==NULL)
cout<<"no this position!";
else{
s=p->next;
p->next=p->next->next;
free(s);/*记住free一定要放到最后!还有每次最好free后清零。
free(str);
str=NULL;*/
}
}
5.求单链表的实际长度
int len(Node *head){
int n=0;
p=head;
while(p!=NULL){
n=n+1;
p=p->next;
}
return n;
}
双向链表：
每个结点有两个指针域和若干数据域，其中一个指针域指向它的前驱结点，一个指针域指向它的后续结点，以空间换时间。
定义：
struct node{
int data;
node *pre,*next;
}
node *head,*p,*q,*r;
插入：
void insert(node *head,int i,int x){
node *s,*p;
int j;
s=new node;
s->data=x;
p=head;
j=0;
while((p->next!=NULL)&&(j<i)){
p=p->next;
j=j+1;
}
if(p==NULL)
cout<<"no this position!";
else{
s->pre=p->pre;
p->pre=s;
s->next=p;
p->pre->next=s;
}
}
删除：
void delete(node *head,int i){
int j;
node *p;
p=head;
j=0;
while((p->next!=NULL)&&(j<i)){
p=p->next;
j=j+1;
}
if(p==NULL)
cout<<"no this position";
else{
p->pre->next=p->next;
p->next->pre=p->pre;
}
}
循环链表：
例题：约瑟夫环问题
#include<bits/stdc++.h>
using namespace std;
struct node {
long d;
node *next;
};
long n,m;
node *head,*p,*r;
int main() {
int i,j,k,l;
cin>>n>>m;
head=new node;
head->d=1;
head->next=NULL;
r=head;
for(i=2; i<=n; i++) {
p=new node;
p->d=i;
p->next=NULL;
r->next=p;
r=p;
}
r->next=head;
r=head;
for(i=1; i<=n; i++) {
for(j=1; j<=m-2; j++)
r=r->next;
cout<<r->next->d<<' ';
r->next=r->next->next;
r=r->next;
}
}
