无标题文档

指针链表

1.快排函数的应用：
#include <bits/stdc++.h>  
using namespace std;  
struct node{  
    int  c,r;  
};  
  
int cmp(const void *a,const void *b){  
    if((*(node*)a).c==(*(node*)b).c)  
        return (*(node*)b).r-(*(node*)a).r; //b-a为从大到小  
    else  
        return (*(node*)b).c-(*(node*)a).c;  
}  
int main(){  
    node q[5];  
    q[0].c=10;q[0].r=5;  
    q[1].c=10;q[1].r=2;  
    q[2].c=10;q[2].r=4;  
    q[3].c=12;q[3].r=2; 
	q[4].c=13;q[4].r=4;  
    qsort(q,5,sizeof(node),cmp);  
    
    for(int i=0;i<5;i++)  
        cout << q[i].c <<" " << q[i].r << endl;  
    return 0;
}

2.排序链表
输入描述:
输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。
输出描述:
可能有多组测试数据，对于每组数据，
将n个整数建立升序链表，之后遍历链表并输出。

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

typedef struct link{
    int data;
    link *next;
}link;

link *init(){//初始化，不要写成init(link *l)
    link *l;
    l=(link*)malloc(sizeof(link));//一定要先建立节点
    l->next=NULL;
    return l;
}

link *create(link *l,int x){
    link *p=l->next;
    link *prep=l;
    while(p){//试过if(p),发现不行，还是踏踏实实的用while---if  的结构吧
        if(p->data>x){
        break;
        }
        else{
        prep=p;
        p=p->next;
        }
    }
     link *s=(link*)malloc(sizeof(link));
    s->data=x;
    s->next=p;
    prep->next=s;
    return l;
}

void print(link *l){
    link *p=l->next;
    while(p){
        cout<<p->data<<" ";
        p=p->next;----->为什么我总是忘了这句！！！
    }
}
int main()
{
    int n,x;
    link *l;
    while(cin>>n){
    l=init();
        for(int i=0;i<n;i++){
            cin>>x;
            l=create(l,x);

}
       print(l);
    }
    return 0;
}

作业:
 1、合并珠子（merge.cpp）

【问题描述】
小小和乐乐各有一串珠子，每个人的珠子都是按照从大到小串起来的。结果在一次游戏中，小小赢到了乐乐的珠串。两个串珠子都很漂亮，小小想把他们重新串在一起，依然保持整串珠子是按照从大到小的顺序。

【输入格式(merge.in)】
第一行：空格分隔的两个整数n和m，分别表示小小和乐乐的珠串的长度。
第二行：n个用空格分隔的整数，表示小小的珠串中珠子从大到小的半径。
第三行：m个用空格分隔的整数，表示乐乐的珠串中珠子从大到小的半径。

【输出格式(merge.out)】
仅一行：n+m个整数，以空格分隔，表示新珠串中从大到小的珠子半径。

【输入样例】
2 3
4 2
8 3 1
【输出样例】
8 4 3 2 1

2、走出泥潭（route.cpp）

【问题描述】
探险队想穿越泥潭，必须选择可踩踏的落脚点。可是泥潭面积很大，落脚点又是在少得可怜，一不小心，就会深陷泥潭而无法脱身。侦查员费劲周折才从老乡手里搞到了一份地图，图中标出了落脚点的位置，而且令人震惊的是：泥潭只有一条穿越路线，而且对于n x m的地图，路线长度为n+m-1！现在请你帮探险队找出穿越路线吧。

【输入格式(joseph.in)】
第一行两个整数n和m，表示泥潭的长和宽。
下面n行，每行m个整数，分别是这一行上的地形，0是泥潭，1是落脚点。
【输出格式(joseph.out)】
用坐标表示的穿越路线，坐标之间用>分隔。

【输入样例】
6 9
1 1 1 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 1 1 0 0 0
0 0 0 0 0 1 1 1 1 
0 0 0 0 0 0 0 0 1 
【输出样例】
（1,1）>（1,2）>（1,3）>（2,3）>（2,4）>（2,5）>（3,5）>（4,5）>（4,6,）>（5,6）>（5,7）>（5,8）>（5,9）>（6,9）

3、祖玛游戏（zuma.cpp）

【问题描述】
祖玛是一个风摩全球的小游戏,它的主角是一只石青蛙。石青蛙会吐出颜色各异的珠子,与沿着一条轨道运行的一串珠子相接 。一旦三颗或三颗以上的同色珠子重新连在一起，那么这几颗珠子即刻消失，而剩下的珠子会自动沿着轨道聚成新的一串。如果新聚成的串接口两端珠子颜色一致且连续不少于三颗,这几颗珠子也会立即消失……游戏时,由玩家控制石青蛙所吐珠子的位置和颜色。
请编写一个程序,对于给定的布局、当前珠子的颜色，玩家打到的位置，求打完这颗珠子后布局的情况。题目用不同的字母代表不同的颜色。

【输入格式（zuma.in）】
分三行:分别表示当前的布局、当前珠子的颜色和玩家打到的位置(新珠子打在了第
几个珠子之后)
【输出格式（zuma.out）】
仅一行:表示打完这颗珠子后布局的情况

【输入样例】
daabbccbadbbb
c
5
【输出样例】
ddbbb

4、约瑟夫问题拓展（exjoseph.cpp）

【问题描述】
n个小孩按照1~n编号,现在他们围成一圈做游戏,从1号开始,1~m报数,报m的将表演节目。第1次顺时针报数,第2次逆时针报数,第3次再顺时针报数,第4次再逆时针报数……以此类推。问最后一个表演节目的孩子的编号

【输入格式（exjoseph.in）】
一行，两个整数空格隔开，分别表示n个小孩和报数m。
【输出格式（exjoseph.out）】
一行，一个整数，最后表演节目的孩子的编号。

【输入样例】
10 3
【输出样例】
2