存儲(chǔ)方式的分類(lèi)：
順序存儲(chǔ)結(jié)構(gòu)：靜態(tài)存儲(chǔ)，很容易找到前驅(qū)和后續(xù)元素，但必須分配最大存儲(chǔ)空間，在插入和刪除時(shí)又會(huì)浪費(fèi)大量的時(shí)間。
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：動(dòng)態(tài)存儲(chǔ)，充分利用存儲(chǔ)器的零碎空間，通過(guò)兩個(gè)命令隨時(shí)向計(jì)算機(jī)申請(qǐng)存儲(chǔ)空間。
概念：為了表示任意存儲(chǔ)單元之間的邏輯關(guān)系，對(duì)于每個(gè)數(shù)據(jù)元素來(lái)說(shuō)，除了要存儲(chǔ)它本身的信息（數(shù)據(jù)域、data外），還要存儲(chǔ)它的直接后續(xù)元素的存儲(chǔ)位置（指針域，link或next）。我們把這兩部分信息合在一起稱(chēng)為一個(gè)結(jié)點(diǎn)node。
（1）N個(gè)結(jié)點(diǎn)鏈接在一起就構(gòu)成了一個(gè)鏈表，N=0時(shí)，稱(chēng)為空鏈表。
（2）定義頭指針。
（3）稱(chēng)之為線性鏈表或單鏈表。
建立并輸出單鏈表。
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *next;
};
Node *head,*p,*r;//r指向鏈表的當(dāng)前最后一個(gè)結(jié)點(diǎn)，可以稱(chēng)為尾指針
int x;
int main() {
cin>>x;
head=new Node;//申請(qǐng)頭結(jié)點(diǎn)
r=head;
while(x!=-1) {
p=new Node;//申請(qǐng)一個(gè)新結(jié)點(diǎn)
p->data=x;
p->next=NULL;
r->next=p;//把新結(jié)點(diǎn)鏈接到前面的鏈表中，實(shí)際上r是p的直接前驅(qū)
r=p;//尾指針后移一個(gè)
cin>>x;
}
p=head->next;//頭指針沒(méi)有數(shù)據(jù)，只要從第一個(gè)結(jié)點(diǎn)開(kāi)始就可以啦
while(p->next!=NULL) {
cout<<p->data<<' ';
p=p->next;
}
cout<<p->data<<endl;//最后一個(gè)結(jié)點(diǎn)單獨(dú)輸出，也可以改用do-while循環(huán)
return 0;
}
單鏈表的操作：
1.查找“數(shù)據(jù)域滿足一定條件的結(jié)點(diǎn)”
p=head->next;
while((p->data!=x)&&(p->next!=NULL))p=p->next;
//找到第一個(gè)就輸出
if(p->data==x)//找到了處理
else//輸出不存在，如果想找到所有點(diǎn)，如下：
p=head->next;
while(p->next!=NULL) {//一個(gè)一個(gè)判斷
if(p->data==x)//找到一個(gè)處理一個(gè)
p=p->next;
}
2.取出單鏈表第i個(gè)結(jié)點(diǎn)的數(shù)據(jù)域。
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.插入一個(gè)結(jié)點(diǎn)在單鏈表中去
void insert(Node *head,int i,int x){//插入x到第i個(gè)元素之前
Node *p,*s;int j;
p=head;
j=0;
while((p!=NULL)&&(j<i-1)){//尋找第i-1個(gè)結(jié)點(diǎn)，插在他后面
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個(gè)結(jié)點(diǎn)
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.求單鏈表的實(shí)際長(zhǎng)度
int len(Node *head){
int n=0;
p=head;
while(p!=NULL){
n=n+1;
p=p->next;
}
return n;
}
雙向鏈表：
每個(gè)結(jié)點(diǎn)有兩個(gè)指針域和若干數(shù)據(jù)域，其中一個(gè)指針域指向它的前驅(qū)結(jié)點(diǎn)，一個(gè)指針域指向它的后續(xù)結(jié)點(diǎn)，以空間換時(shí)間。
定義：
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;
}
}
循環(huán)鏈表：
例題：約瑟夫環(huán)問(wèn)題
#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;
}
}
