———初学链表———

*链表的管理
*出圈问题
*约瑟夫环问题（变种）
*用插入法建立有序链表
*链表中节点的查找与定位

链表的管理

#include<iostream> 
using namespace std; 
struct node 
{ 
  int data; 
  node *next; 
};//node 
node *head=NULL; 
void showList(){ 
   node *p; 
   p=head; 
   cout<<p->data; 
   p=p->next; 
   while(p){ 
      cout<<" "<<p->data; 
      p=p->next; 
   } 
   cout<<endl; 
} 
void creatList(){ 
   node *s,*p; 
   s=new node; 
   s->data=3; 
   head=s; 
   p=new node; 
   p->data=7; 
   head->next=p; 
   s=new node; 
   s->data=1; 
   p->next=s; 
   s->next=NULL; 
} 
void add(int temp){ 
  node *s,*p; 
  int i=0; 
  s=new node; 
  s->data=0; 
  p=head; 
  while(p) 
  { 
     i++; 
     if(i==temp){ 
         if(p->next==NULL){ 
           p->next=s; 
           s->next=NULL; 
         } 
        else { 
          s->next=p->next; 
          p->next=s; 
        } 
     } 
     else p=p->next; 
  } 
} 
void del(int temp){ 
    node *p,*s; 
   if(temp==1) 
   { 
     p=head; 
     head=head->next; 
     p->next=NULL; 
     delete p; 
     return; 
   } 
   else { 
     p=head; 
     int i=0; 
     while(p) 
     { 
       i++; 
       if(i==temp-1) 
       { 
          s=p->next; 
          p->next=p->next->next; 
          s->next=NULL; 
          delete s; 
       } 
       else p=p->next; 
     } 
   } 
} 
void addself(int temp){ 
   int i=0; 
   node *p; 
   p=head; 
   while(p){ 
      i++; 
      if(i==temp){ 
          p->data=p->data+1; 
          break; 
      } 
       else p=p->next; 
   } 
} 
int main() 
{  
    creatList(); 
    showList(); 
   int numa,numb; 
    while(cin>>numa) 
   { 
     if(numa==0) 
         break; 
     else if(numa==1) 
     { 
        cin>>numb; 
        add(numb); 
        showList(); 
     } 
     else if(numa==2) 
     { 
        cin>>numb; 
        addself(numb); 
        showList(); 
     } 
     else if(numa==3) 
     { 
        cin>>numb; 
        del(numb); 
        showList(); 
     } 
   } 
  return 0; 
} 

出圈问题

#include<iostream> 
using namespace std; 
struct node 
{ 
int data; 
node *next; 
}; 
node *list(int n) 
{ 
int i; 
node *s,*head; 
head=new node; 
s=head; 
for(i=1;i<=n;i++) 
{ 
s->data=i; 
if(i<n) 
{ 
s->next=new node; 
s=s->next; 
} 
} 
s->next=head; 
return head; 
} 
void out(node*head) 
{ 
node *s; 
s=head; 
do
{ 
cout<<s->data<<" "; 
s=s->next; 
}while(s!=head); 
} 
void de(node *&head,int m) 
{ 
node *p,*q; 
int k; 
p=head; 
while(p!=p->next) 
{ 
for(k=1;k<m;k++) 
{ 
q=p; 
p=p->next; 
} 
q->next=p->next; 
delete p; 
p=NULL; 
p=q->next; 
} 
cout<<p->data<<endl; 
delete p; 
p=NULL; 
} 
int main() 
{ 
int n,m; 
while(cin>>n>>m) 
{ 
node*head; 
head=NULL; 
head=list(n); 
de(head,m); 
} 
} 

约瑟夫环问题（变种）

include

using namespace std;
struct node
{
int data;
node *next;
};
node* list(int n)
{
int i;
node *s,*head;
head=new node;
s=head;
for(i=1;i<=n;i++)
{
s->data=i;
if(i

这里写代码片

用插入法建立有序链表

#include<iostream>
using namespace std;
struct node
{
    int data;
    node *next;
};
node * head;
void create(int num)
{
    node *s,*p,*q;
    s=new node;
    s->data=num;
    s->next=NULL;
    if(head==NULL)
    {
        head=s;
        return;
    }
    if(head->data>s->data)
    {
        s->next=head;
        head=s;
        return;
    }
    for(q=head,p=head->next;p;q=p,p=p->next)
        if(p->data>s->data)
        {
            s->next=p;
            q->next=s;
            return;
        }
        q->next=s;
        return;
}
void show()
{
    node *p=head;
    while(p)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
}
int main()
{
    int k;
    cin>>k;
    while(k!=0)
    {
    create(k);
    cin>>k;
    }
    show();
}

链表中节点的查找定位

#include<iostream>
using namespace std;
struct node
{
    int data;
    node *next;

};
int n;
void creat(node *&head)
{
    cin>>n;
    node *s,*p;
    s=new node;
    cin>>s->data;
    for(int i=0;i<n-1;i++)
    {
        if(head==NULL)
           head=s;
        else
            p->next=s;
        p=s;
        s=new node;
        cin>>s->data;
    }
    return;
}
void search(node *&head)
{
    node *p;
    int k,i=1;
    cin>>k;
    for(p=head;p;p=p->next)
    {
        if(p==NULL)
            break;
        if(p->data==k)
        { cout<<i<<endl;break;}
        else
            i++;

    }
 if(i==n)
        cout<<"0"<<endl;
}
int main()
{
    node *head=NULL;
    creat(head);
    search(head);
}