链表

定义（单链表）：

1.用一组地址任意的存储单元存放线性表中的数据元素。

数据元素（数据域） + 指针（指针域，指示后继元素存储位置） = 结点 

以“结点的序列”表示线性表——称作链表。

2.以线性表中第一个数据元素“1”的存储地址作为线性表的地址，称作线性

表的首地址。 有时为了操作方便，会在第一个结点之前虚加一个“头指针”。

 单链表的实现：

【题面描述】输入一行整数存入链表中，“-1”为结束标志，整数之间空格分开。
统计链表中数值为m的数的个数。

输入：

1 1 1 2 3 4 5 -1

1

输出：

3

#include<bits/stdc++.h>
using namespace std;
struct Node//定义链表结构 
{    int data;
    Node *next = NULL;
};  Node *head,*r,*p; //定义头指针/尾指针/操作指针
//2.查找链表中存在m的数,统计个数 
void search2(int xx){
       int cnt=0;
    Node *p;
    p=head->next; //定位第一个开始 
    while(p!=NULL){
           if(p->data==xx)
              cnt++;
        p=p->next;
    }
    cout<<cnt<<endl;
}
int main(){
    int x;  //每次要插入的数据 
    cin>>x;
    head=new Node;//创建新结点 并让head头指针指向
    r=head; //因为只有1个结点，尾指针也指向它
    while(x!=-1){ //读入非-1的数值
        p=new Node; //先申请新结点，后续再放数值
        p->data=x;
        p->next=NULL; //每次新结点作为最后1个^
        r->next=p;
        r=p;
        cin>>x;
    }
      int m; //查询m 
    cin>>m;
    search2(m);
    return 0;
}

【题面描述】输入一行整数存入链表中，“-1”为结束标志，整数之间空格分开。
在第k个数前面，插入数值m。插入后再输出该链表。

输入：

5 4 8 8 -1

3 1

输出：

5 4 1 8 8

#include<bits/stdc++.h>
using namespace std;
struct Node{//定义链表结构 
    int data;
    Node *next = NULL;
};Node *head,*r,*p; //定义头指针/尾指针/操作指针 
void insert(int i,int x){
    Node *p,*s;
    int j=0;
    p=head;
    while((p!=NULL)&&(j<i-1)){
         p=p->next;//寻找i-1个结点，插在它后面
          j=j+1;
    }
    if(p==NULL) cout<<"no this position!";
    else{
        s=new Node;
        s->data=x;  //新结点赋值 
        s->next=p->next;
        p->next=s;
    }
}
void print(){
    p=head->next;
    while(p->next!=NULL){
      cout<<p->data<<" ";//输出 
      p=p->next;
    }
    cout<<p->data<<endl; //最后一个结点 
}

int main(){
    int x;  //每次要插入的数据 
    cin>>x;
    head=new Node;//创建新结点 并让head头指针指向
    r=head; //因为只有1个结点，尾指针也指向它
    while(x!=-1){  //读入非-1的数值
        p=new Node; //先申请新结点，后续再放数值
        p->data=x;
        p->next=NULL; //每次新结点作为最后1个^
        r->next=p;
        r=p;
        cin>>x;
    }
    int k,m; //在第k个数前面，插入m结点 
    cin>>k>>m;
    insert(k,m); //插入操作 
    print();//输出查看
    return 0;
}

【题面描述】输入一行整数存入链表中，“-1”为结束标志，整数之间空格分开。
有Q次删除询问，每次删除第m个结点。最后输出询问后的链表链表删除操作。

输入：

5 4 1 1 8 8 8 -1

2 4 4

输出：

5 4 1 8 8

#include<bits/stdc++.h>
using namespace std;
struct Node{     //定义链表结构 
    int data;
    Node *next = NULL;
};
Node *head,*r,*p; //定义头指针/尾指针/操作指针 
void del(int m){//删除链表中第m个结点 
    Node *p,*s;
    int j=0;
    p=head;
    while((p->next!=NULL)&&(j<m-1))
    { //先让p定位到m的前一个位置 
        p=p->next;
        j=j+1;
    }
    if(p->next==NULL)
      cout<<"no this position!";
    else
     { s=p->next;
       p->next=p->next->next;
     //上面也可：p->next=s->next 
       free(s);
    }
}
 void print(){
    p=head->next;
    while(p->next!=NULL){
        cout<<p->data<<" ";//输出 
        p=p->next;
    }
    cout<<p->data<<endl; //最后一个结点 
}
int main(){
    int x;  //每次要插入的数据 
    cin>>x;
    head=new Node;//创建新结点 并让head头指针指向
    r=head; //因为只有1个结点，尾指针也指向它
    while(x!=-1){  //读入非-1的数值
        p=new Node; //先申请新结点，后续再放数值
        p->data=x;
        p->next=NULL; //每次新结点作为最后1个^
        r->next=p;
        r=p;
        cin>>x;
    }
    int Q;
    cin>>Q; //删除Q次 
    while(Q--){
        int m; //删除链表中第m个结点 
        cin>>m;
        del(m); //删除操作 
    }
    print();//输出查看
    return 0;
}

【题面描述】输入一行整数存入链表中，“-1”为结束标志，整数之间空格分开。
请编写程序删除表中所有数值为m的结点。最后输出链表的长度。链表删除操作

输入：

5 4 1 8 8 2 2 -1

2

输出：

5

#include<bits/stdc++.h>
using namespace std;
struct Node     //定义链表结构 
{    int data;
    Node *next = NULL;
};
Node *head,*r,*p; //定义头指针/尾指针/操作指针 
void del(int m){//删除链表中数字m
    Node *p,*s;
    p=head;
    if(p->next->data==m)   //P在m前面找到m 
        p->next = p->next->next; //跨过m 

    while(p->next!=NULL){ //先让p定位到m的前一个位置 
        while(p->next!=NULL&&p->next->data == m ){
           s=p->next;
           p->next=p->next->next;
           if( p->next == NULL ) break;
           free(s);
        }
        if( p->next == NULL ) break;
        p=p->next;
    }
}
int len( ){//现存的链表长度 
    int n=0;
    p=head;
    while(p->next!=NULL){
        n=n+1;
        p=p->next;
    }
    return n;
}
int main(){
    int x;  //每次要插入的数据 
    cin>>x;
    head=new Node;//创建新结点 并让head头指针指向
    r=head; //因为只有1个结点，尾指针也指向它
    while(x!=-1){  //读入非-1的数值
        p=new Node; //先申请新结点，后续再放数值
        p->data=x;
        p->next=NULL; //每次新结点作为最后1个^
        r->next=p;
        r=p;
        cin>>x;
    }
    int m; //删除链表中第m个结点 
    cin>>m;
    del(m); //删除操作 

    cout << len();//输出查看
    return 0;
}

 例题：

原题传送门

P1996 约瑟夫问题

题目描述

　　n 个人围成一圈，从第一个人开始报数,数到 m 的人出列，再由下一个人重新从 11 开始报数，数到 mm 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

注意：本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 n-1 名小朋友，而该题是全部出圈。

输入格式

输入两个整数 n,m。

输出格式

输出一行 n 个整数，按顺序输出每个出圈人的编号。

输入输出样例

输入 #1

10 3

输出 #1

3 6 9 2 7 1 8 5 10 4

说明/提示

1≤m,n≤100

#include<bits/stdc++.h>//万能头. 
using namespace std;
int m,n;
struct Node{//定义头指针，尾指针，操作指针. 
    int data;
    Node *next;
} *head,*p,*tail,*temp;
int main(){
    scanf("%d%d",&m,&n);
    head=new Node;
    head->next=NULL;
    tail=head;
    for(int i=1;i<=m;i++){
        p=new Node;
        p->data=i;
        p->next=NULL;
        tail->next=p;
        tail=p;
    }
    p=head->next;/
    tail->next=head->next;//链表首尾相连形成循环链表. 
    for(int i=1;i<=m;i++){
        for(int j=1;j<n-1;j++){
            p=p->next;
        }
        cout<<p->next->data<<" ";
        temp=p->next;
        p->next=temp->next;//连接要删除那个结点上下结点
        p=p->next;//更新
        free(temp);//释放空间
    }
    return 0;
}

---

链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表链表