链表结构
【存储方式的分类】 ：顺序存储结构和链式存储结构；
【顺序存储结构】 ：在（子）程序的说明部分就必须加以说明，以便分配固定大小的存储单 元，直到（子）程序结束，才释放空间。因此，这种存储方式又称为静态存储。所定义的变量相应的称为静态变量。
它的优缺点如下：
1、优点：可以通过一个简单的公式随机存取表中的任一元素，逻辑关系上相邻的两个元素在物理位置上也是相邻的，且很容易找到前趋与后继元素；
2、缺点：在线性表的长度不确定时，必须分配最大存储空间，使存储空间得不到充分利用，浪费了宝贵的存储资源；线性表的容量一经定义就难以扩充；在插入和删除线性表的元素时，需要移动大量的元素，浪费了时间；
【链式存储结构】 ：在程序的执行过程中，通过两个命令向计算机随时申请存储空间或随时释放存储空间，以达到动态管理、使用计算机的存储空间，保证存储资源的充分利用。这样的存储方式称为动态存储。所定义的变量称为动态变量。
它的优点如下：
可以用一组任意的存储单元（这些存储单元可以是连续的，也可以不连续的）存储线性表的数据元素，这样就可以充分利用存储器的零碎空间；
【概念】 ：为了表示任意存储单元之间的逻辑关系，对于每个数据元素来说，除了要存储它本身的信息（数据域、data）外，还要存储它的直接后继元素的存储位置（指针域、link 或 next）。我们把这两部分信息合在一起称为一个“结点 node”。
1、N 个结点链接在一起就构成了一个链表。N=0 时，称为空链表。
2、为了按照逻辑顺序对链表中的元素进行各种操作，我们需要定义一个变量用来存储 整个链表的第一个结点的物理位置，这个变量称为“头指针、H 或 head”。也可以把头指针定义成一个结点，称为“头结点”，头结点的数据域可以不存储任何信息，也可以存储线性表的长度等附加信息，头结点的指针域（头指针）存储指向第一个结点的指针，若线性表为 空表，则头结点的指针域为空（NIL）。由于最后一个元素没有后继，所以线性表中最后一个 结点的指针域为空（NIL）。
3、 由于此链表中的每个结点都只包含一个指针域，故称为“线性链表或单链表”。
（一）单链表的定义
1．类型和变量的说明
1. struct Node { 2. int data; 3. Node *next; 4. }; 5. Node *p;
2．申请存储单元
p=new Node; //动态申请、空间大小由指针变量的基类型决定
3．指针变量的赋值
指针变量名=NULL； //初始化，暂时不指向任何存储单元
如何表示和操作指针变量？不同于简单变量（如 A=0；），c++规定用“指针变量名->” 的形式引用指针变量（如 P->data=0；）。
（二）单链表的结构、建立、输出 由于单链表的每个结点都有一个数据域和一个指针域，所以，每个结点都可以定义成 一个记录。比如，有如下一个单链表，如何定义这种数据结构呢？
下面给出建立并输出单链表的程序，大家可以把它改成过程用在以后的程序当中。
1. #include<iostream> 2. using namespace std; 3. struct Node { 4. int data; 5. Node *next; 6. } ; 7. Node *head,*p,*r;//r指向链表的当前最后一个结点，可以称为尾指针 8. int x; 9. int main() 10. { 11. cin>>x; 12. head=new Node;//申请头结点 13. r=head; 14. while(x!=-1){//读入的数非-1 15. p=new Node;//否者申请一个新结点 16. p->data=x; 17. p->next=NULL; 18. r->next=p;//把新节点连接到前面的链表中，实际上r是p的直接前趋 19. r=p;//尾指针后移一个 20. cin>>x; 21. } 22. p=head->next;//头指针没有数据，从第一个结点开始就可以了 23. while(p->next!=NULL) 24. { 25. cout<<p->data<<" "; 26. p=p->next; 27. } 28. cout<<p->data<<endl;//最后一个结点数据单独输出 29. return 0; 30. }
（三）单链表的操作
1． 查找“数据域满足一定条件的结点”
1. p=head->next; 2. while((p->data!=x)&&(p->next!=NULL)) p=p->next; //找到第一个就结束 3. if(p->data==x) 4. 找到了处理; 5. else 6. 输出不存在;
如果想找到所有满足条件的结点，则修改如下：
1. p=head->next; 2. while(p->next!=NULL) { //一个一个判断 3. if(p->data==x) //找到一个处理一个 ; 4. p=p->next; 5. }
2． 取出单链表的第 i 个结点的数据域
1. void get(Node *head,int i) { 2. Node *p; 3. int j; 4. p=head->next; 5. j=1; 6. while((p!=NULL)&&(j<i)){ 7. p=p->next; 8. j=j+1; 9. } 10. if((p!=NULL)&&(j==i)) cout<<p->data; 11. else cout<<"i not exsit!"; 12. }
3． 插入一个结点在单链表中去
1. void insert(Node *head,int i,int x) //插入 X 到第 i 个元素之前 2. { 3. Node *p,*s; 4. int j; 5. p=head; 6. j=0; 7. while((p!=NULL)&&(j<i-1)) //寻找第 i-1 个结点,插在它的后面 8. { 9. p=p->next; 10. j=j+1; 11. } 12. if(p==NULL) cout<<"no this position!"; 13. else { //插入 14. s=new Node; 15. s->data=x; 16. s->next=p->next; 17. p->next=s; 18. } 19. }
4． 删除单链表中的第 i 个结点（如下图的“b”结点）
1. void delete(Node *head,int i) //删除第 i 个元素 2. { 3. Node *p,*s; 4. int j; 5. p=head; 6. j=0; 7. while((p->next!=NULL)&&(j<i-1)) { 8. p=p->next; 9. j=j+1; 10. } //p 指向第 i-1 个结点 11. if (p->next==NULL) cout<<"no this position!"; 12. else { //删除 p 的后继结点，假设为 s 13. s=p->next; 14. p->next=p->next->next; //或 p->next=s->next 15. free(s); 16. } 17. }
5． 求单链表的实际长度
1. int len(Node *head) { 2. int n=0; 3. p=head; 4. while(p!=NULL) { 5. n=n+1; 6. p=p->next; 7. } 8. return n; 9. }
（四）双向链表
每个结点有两个指针域和若干数据域，其中一个指针域指向它的前趋结点，一个指向它 的后继结点。它的优点是访问、插入、删除更方便，速度也快了。但“是以空间换时间”。
【数据结构的定义】
1. struct node{ 2. int data; 3. node *pre,*next;//pre 指向前趋，next指向后继 4. }; 5. node *head，*p,*q,*r;
下面给出双向链表的插入和删除过程。
1. void insert(node *head,int i,int x){//在双向链表的第i个结点之前插入x 2. node *s,*p; 3. int j; 4. s=new node; 5. s->data=x; 6. p=head; 7. j=0; 8. while((p->next!=NULL)&&(j<i)){ 9. p=p->next; 10. j=j+1; 11. }//p指向第i个结点 12. if(p==NULL) 13. cout<<"no this position!"; 14. else {//将s结点插入到结点p之前 15. s->pre=p->pre;//将s的前趋指向p的前趋 16. p->pre=s;//将s作为p新的前趋 17. s->next=p;//将s的后继指向p 18. p->pre->next=s;//将P的本来前趋结点的后继指向s 19. } 20. } 21. void delete(node *head,int i){//删除双向链表的第i个结点 22. int j; 23. node *p; 24. p=head; 25. j=0; 26. while((p->next!=NULL)&&(j<i)){ 27. p=p->next; 28. j=j+1; 29. }//p指向第i个结点 30. if(p==NULL) 31. cout<<"no this position!"; 32. else{ 33. p->pre->next=p->next;//p的前趋结点的后继赋值为p的后继 34. p->next->pre=p->pre;//p的后继结点的前趋赋值为p的前趋 35. } 36. }
（五）循环链表
单向循环链表：最后一个结点的指针指向头结点。如下图：
双向循环链表：最后一个结点的指针指向头结点，且头结点的前趋指向最后一个 结点。如下图：
（六）循环链表的应用举例
约瑟夫环问题
【问题描述】 有 M 个人，其编号分别为 1－M。这 M 个人按顺序排成一个圈（如图）。现在给定一个 数 N，从第一个人开始依次报数，数到 N 的人出列，然后又从下一个人开始又从 1 开始依次报数，数到 N 的人又出列．．．如此循环，直到最后一个人出列为止。
【输入格式】
输入只有一行，包括 2 个整数 M，N。之间用一个空格分开(0 < n <= m <= 100)。
【输出格式】
输出只有一行，包括 M 个整数
【样列输入】8 5
【样列输出】5 2 8 7 1 4 6 3
【参考程序】
1. #include<iostream> 2. using namespace std; 3. struct node{ 4. long d; 5. node *next; 6. }; 7. long n,m; 8. node *head,*p,*r; 9. int main() 10. { 11. long i,j,k,l; 12. cin>>n>>m; 13. head=new node; 14. head->d=1; 15. head->next=NULL; 16. r=head; 17. for(i=2;i<=n;i++){ 18. p=new node; 19. p->d=i; 20. p->next=NULL; 21. r->next=p; 22. r=p; 23. } 24. r->next=head; 25. r=head; 26. for(i=1;i<=n;i++){ 27. for(j=1;j<=m-2;j++) r=r->next; 28. cout<<r->next->d<<" "; 29. r->next=r->next->next; 30. r=r->next; 31. } 32. return 0; 33. }
