头像

卬岇昂


访客:5265

离线:8个月前



卬岇昂
2019-05-29 08:01
#include<bits/stdc++.h>
using namespace std;

int n;
int order[20];
bool chosen[20];

void calc(int k){
    if(k==n+1){
        for(int i=1;i<=n;i++)
            printf("%d ",order[i]);

        puts("");
        return;
    }

    for(int i=1;i<=n;i++){
        if(chosen[i])continue;
        order[k]=i;
        chosen[i]=1;

        calc(k+1);
        chosen[i]=0;
        order[k]=0;
    }
}

int main(){
    cin>>n;
    calc(1);
    return 0;
}



卬岇昂
2019-05-29 07:56
//递归实现组合型枚举

#include<bits/stdc++.h>
using namespace std;

int n,m;

void dfs(int u,int sum,int state){
    if(sum+n-u<m)return;
    if(u==n+1)return;

    if(sum==m){
        for(int i=0;i<n;i++)
            if(state>>i&1)
                cout<<i+1<<' ';

        cout<<endl;
        return;
    }

    dfs(u+1,sum+1,state|1<<u);
    dfs(u+1,sum,state);
}

int main(){
    cin>>n>>m;
    dfs(0,0,0);
    return 0;
}

//非递归实现组合型枚举

#include<bits/stdc++.h>
using namespace std;

int n,m;

struct State{
    int pos,u,sum,state;
}; 

int main(){
    cin>>n>>m;

    stack<State> stk;
    stk.push({0,0,0,0});

    while(stk.size()){
        auto t=stk.top();
        stk.pop();

        if(t.pos==0){
            if(t.sum+n-t.u<m)continue;
            if(t.sum==m){
                for(int i=0;i<n;i++)
                    if(t.state>>i&1)
                        cout<<i+1<<' ';

                    cout<<endl;
                    continue;
                }

                t.pos=1;
                stk.push(t);
                stk.push({0,t.u+1,t.sum+1,t.state|1<<t.u});
        }
        else if(t.pos==1){
            t.pos=2;
            stk.push(t);
            stk.push({0,t.u+1,t.sum,t.state});
        }
        else continue;
    }
    return 0;
}



卬岇昂
2019-05-29 06:53
#include<bits/stdc++.h>
using namespace std;

int n;
vector<int>chosen;

void dfs(int x){
    if(x==n+1){
        for(int i=0;i<chosen.size();i++)
            printf("%d ",chosen[i]);

        puts("");
        return;
    }
    dfs(x+1);
    chosen.push_back(x);

    dfs(x+1);
    chosen.pop_back();
}

int main(){
    cin>>n;
    dfs(1);
    return 0;
}



卬岇昂
2019-05-19 08:55

二分查找

二分查找有64种写法。

对其进行分类:
取整方式:向下取整,向上取整(共2种)
区间开闭:闭区间,左闭右开区间,左开右闭区间,开区间(共4种)
问题类型:
①对于不下降序列a,求最小的i,使得a[i]=key
②对于不下降序列a,求最大的i,使得a[i]=key
③对于不下降序列a,求最小的i,使得a[i]>key
④对于不下降序列a,求最大的i,使得a[i]<key
⑤对于不上升序列a,求最小的i,使得a[i]=key
⑥对于不上升序列a,求最大的i,使得a[i]=key
⑦对于不上升序列a,求最小的i,使得a[i]<key
⑧对于不上升序列a,求最大的i,使得a[i]>key(共8种)
  • 综上所述,二分查找共有64种写法。

对于不下降序列a,n为序列a元素的个数,key为关键字。

1.求最小的i,使得a[i]=key,若不存在,则返回-1

int search1(int a[],int n,int key){
    int m,l=0,r=n-1;//闭区间[0,n-1]
    while(l<r){
        m=l+((r-l)>>1);//向下取整
        if(a[m]<key)l=m+1;
        else r=m;
    }
    if(a[r]==key)return r;
    return -1;
}

2.求最大的i,使得a[i]=key,若不存在,则返回-1

int search2(int a[],int n,int key){
    int m,l=0,r=n-1;//闭区间[0,n-1]
    while(l<r){
        m=l+((r+1-l)>>1);//向上取整
        if(a[m]<=key)l=m;
        else r=m-1;
    }
    if(a[l]==key)return l;
    return -1;
}

3.求最小的i,使得a[i]>key,若不存在,则返回-1

int search3(int a[],int n,int key){
    int m,l=0,r=n-1;//闭区间[0,n-1]
    while(l<r){
        m=l+((r-l)>>1);//向下取整
        if(a[m]<=key)l=m+1;
        else r=m;
    }
    if(a[r]>key)return r;
    return -1;
}

4.求最大的i,使得a[i]<key,若不存在,则返回-1

int search4(int a[],int n,int key){
    int m,l=0,r=n-1;//闭区间[0,n-1]
    while(l<r){
        m=l+((r+1-l)>>1);//向上取整
        if(a[m]<key)l=m;
        else r=m-1;
    }
    if(a[l]<key)return l;
    return -1;
}
  • 对于3、4,也可以先判断是否存在,再进行二分查找。



卬岇昂
2019-05-10 07:06

位运算及标准模版库

位运算

  • 1、位运算符

    这些位运算只能用于整型操作数,即只能用于带符号或无符号的char、short、int、与long类型。

①按位与(&)
②按位或(|)
③按位异或(^)
④取反(~)
⑤左移(<<)n<<1=2*n,1<<n=2^n
⑥右移(>>)n>>1=n/2
优先级:
加减   移位    比较大小     位与   异或   位或
+,-    <<,>>   >,<,==,!=     &      ^      | 
  • 2、位运算的应用举例
①高效代替布尔型数组
②表示集合、搜索算法中的状态判重(hash)
③动态规划算法中的状态压缩

vector

使用vector,需添加#include<vector>,同时要有using namespace std。

  • 1、定义
vector<typename> name;
vector<int> a;//长度不固定的一维整型数组
vector<double> b;//长度不固定的一维浮点型数组
vector<node> student;//node为已经定义了的结构体
vector<int> c[100];//一维长度固定为100,另一维长度不固定的二维数组,
vector<vector<int> > a;//一个两位长度都不固定的二维数组
  • 2、访问
①下标访问:对于vector<int> v,使用v[idx]访问它的第idx个元素
0<=idx<=v.size()-1,v.size()表示vector中元素个数

②迭代器访问:定义:
vector<typename>::iterator it;
可以通过*it来访问vector里的元素。迭代器也可以进行自加、自减操作。
v.begin()为取v的首元素地址,v.end()为取尾元素地址的下一个地址。
  • 3、常用函数
①push_back()
push_back(X)在vector后添加一个元素x。

②size()
一维:vector中元素个数
二维:vector中第二维元素个数
用resize(n)重设数组大小

③pop_back()
删除vector的尾元素

④clear(n)
清空vector中的所有元素

⑤insert()
insert(it,x)用来向vector任意迭代器it处插入一个元素x

⑥erase()
erase(it):删除it处元素
earse(left right):删除[left,right)内所有元素

stack

stack翻译为栈,是一个”后进先出“的容器。使用时需添加include<stack>,同时要有using namespace std。

  • 1、定义:
stack<typename> name;//typename可以是任何基本类型或者容器,name是栈的名字
  • 2、常用函数
①push()
push(x)用来将x压栈

②top()
获得栈顶元素

③pop()
弹出栈顶元素

④empty()
检测stack是否为空,空返回true,否则返回false

⑤size()
返回stack内元素个数
  • 只能通过函数top()pop()来访问栈顶元素。

queue和priority_queue

queue

queue翻译为队列,是一个”先进先出“的容器。使用时需添加include<queue>,同时要有using namespace std。

  • 1、定义
queue<typename> name;
  • 2、常用函数
①push()
push(x)用来将x入队

②front()
获得队首元素

③back()
获得队尾元素

④pop()
让队首元素出队

⑤empty()
检测queue是否为空

⑥size()
返回queue内元素的个数
  • queue只能通过函数front()来访问队首元素,或通过函数back()来访问队尾元素。一般应用在宽搜中。在使用front()pop()前,必须用empty()判断队列是否为空,否则可能因为队空而出现错误。

priority_queue

priority_queue翻译为优先队列,一般用来解决一些贪心问题,其底层是用“堆”来实现的。使用时需添加include<queue>,同时要有using namespace std。

  • 1、定义
priority_queue<typename> name;
  • 和queue不一样的是,priority_queue没有front()back(),而只能通过top()pop()访问队首元素(也称堆顶元素),也就是优先级最高的元素。
  • 2、常用函数
①push()
push(x)是将x加入优先队列

②top()
获得队首元素(堆顶元素)

③pop()
让队首元素(堆顶元素)出队
  • 使用top()必须用empty()判断优先队列是否为空,否则有可能出错。
  • 2、元素优先级的设置
    优先队列对它们的优先级设置一般是数字越大的优先级越高(对于char,则是字典序最大的)。
以下两种优先队列的定义是等价的:
priority_queue<int> q;
priority_queue<int,vector<int>,less<int>> q;

map和pair

map

map翻译为映射。使用时需添加include<map>,同时要有using namespace std。

map的用途有以下情形:
①需要建立字符(串)与整数之间的映射,使用map可以减少的代码量。
②判断大整数(比如几千位)或者其他类型数据是否存在,可以把map当布尔型数组使用(哈希表)。
③字符串与字符串之间的映射。

定义一个map的方法如下:

map<typename1,typename2> name;//typename1是映射前的类型(键key),typename2是映射后的类型(值value),name为映射的名字。
map<int,int> a;
map<string,int> a;//不能使用char
map<set<int>,string>mp;
  • 1、访问
    ①通过下标访问:
先定义“map<char,int> mp”,然后就可以通过mp['c']的方式来访问它对应的元素。
  • 2、常用函数
①find()
find(key)是返回键为key的映射的迭代器。

②size()
size()获得map中映射的对数。

③erase()
删除单个元素:
erase(it):it为要删除的元素的迭代器
erase(key):key为要删除的映射的键
删除一个区间的所有元素:
erase(left,right):删除[left,right)内所有元素

④clear()
清空map

pair

pair是“二元结构体”的替代品。使用时需添加include<utility>,同时要有using namespace std。

  • 定义
pair<typename1,typename2> name;

相当于:

struct pair{
    typename1 first;
    typename2 second;
}
pair<string,int> p;make_pair("haha",5);
pair<string,int> p("haha",5);
  • pair可以直接做比较运算,比较规则是先以first的大小作为标准,只有当first相等时才去判断second的大小。
  • 所以,pair可以作为map的键值对来插入(排序)。

set

set翻译为集合,是一个内部自动有序且不含重复元素的容器。使用时需添加include<set>,同时要有using namespace std。

  • 1、定义
set<typename> name;
set<int> st;
set<int> st[100];

set只能通过迭代器访问。

定义迭代器:
set<typename>::iterator it;
然后使用*it来访问set中的元素。
set不支持*(it+i),it<st.end()的访问方式。
  • 2、常用函数
①insert()
insert(x)用来将x插入到set中,并自动递增排序和去重。

②size()
获得set中的元素个数

③find()
find(value)是返回set中对应值为value的迭代器

④clear()
清空set中的所有元素

④erase()
删除单个元素:
erase(it):it为要删除元素的迭代器
earse(value):value为要删除的元素的值
删除一个区间的所有元素:
erase(left,right):删除[left,right)内所有元素

string

使用时需添加include<string>,同时要有using namespace std。
* 定义

string name;
  • 1、访问
①像普通字符数组一样操作
②通过迭代器
定义迭代器:
string::iterator it;
然后就可以通过*it来访问string里的每一个元素。
  • 2、运算
加法:把两个字符串直接拼接起来。
关系:按照字典序比较两个string类型的大小。
  • 3、常用函数
①length()
返回string的长度(字符个数)

②size()
与length()一样

③clear()
用来清空string中的所有元素

④substr()
substr(pos,len)返回从pos号位置开始、长度为len的子串

⑤insert()
insert(pos,string):在pos号位置插入字符串string
insert(it,it2,it3):it为原字符串的欲插入位置;it2和it3为待插入字符串的首尾迭代器(左毕右开区间)

⑥erase()
删除单个元素:
erase(it):it为要删除元素的迭代器
删除一个区间内的所有元素:
erase(left,right):删除[left,right)中的所有元素
erase(pos,length):pos为需要删除的字符串起始位置;length为要删除的字符个数

⑦find()
str.find(str2):当str2是str的子串时,返回其在str中第一次出现的位置;否则,返回string::npos
string::npos是一个常数,其本身的值等于-1
str.find(str2,pos):从str的pos号位开始匹配str2,返回值同上

⑧replace()
str.replace(pos,len,str2):把str从pos号位开始、长度为len的子串替换为str2
str.replace(it1,it2,str2):把str的迭代器it1~it2范围内(左闭右开区间)的子串替换为str2

algorithm

algoriyhm翻译为算法提供了大量基于迭代器的非成员模版函数。要使用这些函数,需要添加#include<algorithm>,必须要有using namespace std。

  • 1、max(),min(),abs(),swap()
  • 2、reverse():reverse(it,it2)可以将数组指针在it~it2(左闭右开区间)之间的元素,或容器的迭代器在it~it2范围内的所有元素进行反转。
  • 3、next_permutation():求出一个序列在全排列中的下一个序列。
  • 4、fill():可以把数组或容器的某一段区间赋值为某个相同的值
fill(a,a+5,123);//将a[0]到a[4]均赋值为123
  • 5、sort():实现排序的函数
sort(首元素地址,尾元素地址的下一地址,比较函数);//前两个必填,没有比较函数表示堆区间元素进行递增排序

如果要实现递减排序,或者对结构体(本身没有大小关系)等进行排序,就需要用到比较函数,一般写成cmp()函数。
递减排序:

bool cmp(int a,int b){
    return a>b;
}

结构体按照x从大到小排列:

bool cmp(node a,node b){
    return a.x>b.x;
}
  • 在STL标准容器中,只有vector、string、deque是可以用sort()的。



卬岇昂
2019-05-07 06:26

深搜

  • 1、算法模版【一】
int dfs(int k){
    for(int i=1;i<=算符种数;i++)
        if(满足条件){
            保存结果
            if(到目的地)输出解;
            else dfs(k+1);
            恢复:保存结果之前的状态{回溯一步}
        }
}
  • 2、算法模版【二】
int dfs(int k){
    if(到目的地)输出解;
    else
        for(int i=1;i<=算符种数;i++)
            if(满足条件){
                保存结果
                dfs(k+1);
                恢复:保存结果之前的状态{回溯一步}
            }
}

宽搜

  • 实现框架
int bfs(){
    初始化,初始状态存入队列;
    队列首指针head=0;尾指针tail=1;
    while(head<tail){//队列为空
        指针head后移一位,指向待扩展结点;
        for(int i=1;i<=max;i++){//max为产生子结点的规则数
            if(子结点符合条件){
                tail指针增1,把新结点存入队尾;
                if(新结点与原已产生结点重复)删去该节点(取消入队,tail减1);
                else if(新结点是目标结点)输出并退出;
            }
        }
    }
}

贪心

  • 实现框架
从问题的某一初始解出发;
while(能朝给定总目标前进一步){
    利用可行的决策,求出可行解的一个解元素;
}
由所有解元素组合成问题的一个可行解;
}

二分

  • 1、整数定义域上的二分
int erfen(int l,int r){
    int l=1,r=n,ans;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid))ans=mid,l=mid+1;//若满足要求,记下答案,并根据题意缩减范围
        else r=mid-1;
    }
    return ans;
}
  • 2、实数域上的二分
double erfen(double l,double r){//dlt=0.001(根据题目要求决定精度)
    double mid;
    while(fabs(l-r)>dlt){
        mid=(l+r)/2.0;
        if(check(mid))r=mid;
        else l=mid;
    }

    return l;
}
  • 3、三分
double l=0,r=1e9;
while(r-l>=1e-3){
    double m1=l+(r-l)/3,m2=r-(r-l)/3;
    if(f(m1)<f(m2))l=m1;
    else r=m2;
}



卬岇昂
2019-05-04 07:46

大整数开方

出自NOIP2011提高组初赛完善程序第一题

  • 输入一个正整数n(1<=n<=10^100),试用二分法计算它的平方根的整数部分。
#include<bits/stdc++.h>
using namespace std;

const int SIZE=200;
struct hugeint{
    int len,num[SIZE];
};//其中len表示大整数的位数;num[1]表示个位,num[2]表示十位,以此类推

hugeint times(hugeint a,hugeint b)//计算大整数a和b的乘积
{
    int i,j;
    hugeint ans;
    memset(ans.num,0,sizeof(ans.num));

    for(i=1;i<=a.len;i++)
        for(j=1;j<=b.len;j++)
            ans.num[i+j-1]+=a.num[i]*b.num[j];

    for (i=1;i<=a.len+b.len;i++){
        ans.num[i+1]+=ans.num[i]/10;
        ans.num[i]=ans.num[i]%10;
    }

    if (ans.num[a.len+b.len]>0)
        ans.len=a.len+b.len;
    else
        ans.len=a.len+b.len-1;

    return ans;
}

hugeint add(hugeint a,hugeint b)//计算大整数a和b 的和
{
    int i;
    hugeint ans;
    memset(ans.num,0,sizeof(ans.num));

    if(a.len>b.len)
        ans.len=a.len;
    else
        ans.len=b.len;

    for(i=1;i<=ans.len;i++){
        ans.num[i]+=a.num[i]+b.num[i];
        ans.num[i+1]+=ans.num[i]/10;
        ans.num[i]%=10;
    }

    if(ans.num[ans.len+1]>0)
        ans.len++;
    return ans;
}

hugeint average(hugeint a, hugeint b)//计算大整数a和b的平均数的整数部分
{
    int i;
    hugeint ans;
    ans=add(a,b);

    for (i=ans.len;i>=2;i--){
        ans.num[i-1]+=(ans.num[i]%2)*10;
        ans.num[i]/=2;
    }

    ans.num[1]/=2;

    if (ans.num[ans.len]==0)
        ans.len--;

    return ans;
}

hugeint plustwo(hugeint a)//计算大整数a加2之后的结果
{
    int i;
    hugeint ans;
    ans=a;
    ans.num[1]+=2;
    i=1;

    while((i<=ans.len)&&(ans.num[i]>=10)){
        ans.num[i+1]+=ans.num[i]/10;
        ans.num[i]%=10;
        i++;
    }

    if(ans.num[ans.len+1]>0)
        ans.len++;

    return ans;
}

bool over(hugeint a,hugeint b)//若大整数a>b则返回true,否则返回false
{
    int i;

    if(a.len<b.len)
        return false;

    if (a.len>b.len)
        return true;

    for (i=a.len;i>=1;i--){
        if(a.num[i]<b.num[i])
            return false;
        if(a.num[i]>b.num[i])
            return true;
    }

    return false;
}

int main( ) {
    string s;
    int i;
    hugeint target,left,middle,right;

    cin>>s;
    memset(target.num,0,sizeof(target.num));
    target.len=s.length( );

    for(i=1;i<=target.len;i++)
        target.num[i]=s[target.len-i]-'0';

    memset(left.num,0,sizeof(left.num));
    left.len=1;
    left.num[1]=1;
    right=target;

    do{
        middle=average(left,right);
        if(over(times(middle,middle),terget))
            right=middle;
        else
            left=middle;
    }while(!over(plustwo(left),right));

    for(i=left.len;i>=1;i--)
        cout<<left.num[i];

    return 0;
}

这道题目主要考察高精度。高精度最需要注意的是进位、借位处理。

加法进位:c[i]=a[i]+b[i];
        if(c[i]>=10){c[i]%=10;++c[i+1];}
减法借位:if(a[i]<b[i]){--a[i+1];a[i]+=10;}
        c[i]=a[i]-b[i];
乘法进位:c[i+j-1]+=a[i]*b[j]+x;
        x=c[i+j-1]/10;
        c[i+j-1]%10;



卬岇昂
2019-05-04 07:05

链表结构

  • 1、单链表的定义
    ①类型和变量的说明
struct Node{
    int data;
    Node *next;
};
Node *p;

②申请存储单元

p=new Node;//动态申请、空间大小由指针变量的基本类型决定

③指针变量的赋值

指针变量名=NULL;//初始化,暂时不指向任何存储单元
  • 2、单链表的结构、建立、输出
    1.png
    下面是建立并输出单链表的程序。
#include<bits/stdc++.h>
using namespace std;

struct Node{
    int data;
    Node *next;
};
Node *head,*p,*r;

int x;

int main(){
    cin>>x;
    head=new Node;//申请头结点
    r=head;

    while(x!=-1){//读入的数非-1
        p=new Node;//否则,申请一个新节点

        p->data=x;
        p->next=NULL;
        r->next=p;//把新节点链接到前面的链表中,实际上r是p的直接前趋

        r=p;//尾指针后移一个
        cin>>x;
    }

    p=head->next;//头指针没有数据,只要从第一个结点开始就可以了

    while(p->next!=NULL){
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<p->data<<endl;//最后一格结点的数据单独输出,也可以改用do-while循环

    system("pause");
}
  • 3、单链表的操作
    ①查找“数据域满足一定条件的结点”
p=head->next;
while((p->data!=x)&&(p->next!=NULL))
    p=p->next;//找到第一个就结束
if(p->data==x)
    找到了就处理;
else
    输出不存在;

如果想找到所有满足条件的结点,则修改如下:

p=head->next;
while(p->next!=NULL){//一个一个判断
    if(p->data==x)//找到一个处理一个
    p=p->next;
}

②取出单链表的第i个结点的数据域

void get(Node *head,int i){
    Node *p;int j;
    p=head->next;
    j=1;

    while((p!=NULL)&&(j<i)){
        p=p->next;
        j++;
    }

    if((p!=NULL)&&(j==i))
        cout<<p->data;
    else 
        cout<<"i not exsit!";
}

③插入一个结点在单链表中去
2.png

void insert(Node *head,int i,int x){//插入x到第i个元素之前
    Node *p,*s;int j;
    p=head;j=0;

    while((p!=NULL)&&(j<i-1)){//寻找i-1个结点,插在它的后面
        p=p->next;
        j++;
    }

    if(p==NULL)
        cout<<"no this position!";
    else{//插入
        s=new Node;

        s->data=x;
        s->next=p->next;
        p->next=s;
    }
}

④删除单链表中的第i个结点
3.png

void delete(Node *head,int i){//删除第i个元素
    Node *p,*s;int j;
    p=head;j=0;

    while((p->next!=NULL)&&(j<i-1)){
        p=p->next;
        j++;
    } //p指向第i-1个结点

    if(p->next==NULL)
        cout<<"no this position!";
    else{
        s=p->next;
        p->next=p->next->next;//或p->next=s->next
        free(s);
    }
}

⑤求单链表的实际长度

int len(Node *head){
    int n=0;
    p=head;

    while(p!=NULL){
        n++;
        p=p->next;
    }

    return n;
}
  • 4、双向链表
    【数据结构的定义】
struct node{
    int data;
    node *pre,*next;//pre指向前趋,next指向后继
}
node *head,*p,*q,*r;

下面是双向链表的插入和删除过程
4.png
5.png

void insert(node *head,int i,int x){//在双向链表的第i个结点之前插入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++;
    }//p指向第i个结点

    if(p==NULL)
        cout<<"no this position!";
    else{//将结点s插入到结点p之前
        s->pre=p->pre;//将s的前趋指向p的前趋
        p->pre=s;//将s作为p的新前趋
        s->next=p;//将s的后继指向p
        p->pre->next=s;//将p的本来前趋结点的后继指向s
    }
}
void delete(node *head,int i){//删除双向链表的第i个结点
    int j;node *p;
    p=head;j=0;

    while((p->next!=NULL)&&(j<i)){
        p=p->next;
        j++;
    }//p指向第i个结点

    if(p==NULL)
        cout<<"no this position!";
    else{//将结点p删除
        p->pre->next=p->next;//p的前趋结点的后继赋值为p的后继
        p->next->pre=p->pre;//p的后继结点的前趋赋值为p的前趋
    }
}
  • 5、循环链表
    单项循环链表:最后一个结点的指针指向头结点。
    6.png
    7.png
    双向循环链表:最后一个结点的指针指向头结点,且头结点的前趋指向最后一个结点。
    8.png
    10.png
  • 6、循环链表的应用举例
    例:约瑟夫环问题
#include<bit/stdc++.h>
using namespace std;

struct node{
    int d;
    node *next;
};

int n,m;
node *head,*p,*r;

int main(){
    int i,j,k,l;
    cin>>n>>m;
    head=new node;
    hesd->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;
    }
}
输入:8 5
输出:5 2 8 7 1 4 6 3



卬岇昂
2019-05-04 01:26

指针与数组

  • 1、指针与数组的关系

设有数组a,指向a的指针变量为pa,则有以下关系:pa+i,a+i,&a[i]指向i号元素a[i]。pa是变量,而a,a[i]是常量,应予以注意。

  • 2、指向数组的指针
数组指针变量说明的一般形式为:
类型说明符 *指针变量名

例1:scanf使用数组名,用数组名或指针访问数组。

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a[5],i,*pa=a;//定义整型数组和指针,*pa=a可以在下一行为pa=a

    for(i=0;i<5;i++)
        scanf("%d",a+i);//可写成pa+i和&a[i]

    for(i=0;i<5;i++)
        printf("a[%d]=%d\n",i,*(a+i));//指针访问数组,可写成*(pa+i)或pa[i]或a[i]

    return 0;
}
输入:1 2 3 4 5
输出:a[0]=1
a[1]=2
a[2]=3
a[3]=4
a[4]=5
说明:
①a+i是指向数组的第i个元素的指针。
②指针变量pa可以变,数组a不可以变。例如p=p+2;合法,a=a+2;非法。
③对于数组,可以直接用数组名当指针。
  • 3、指针也可以看成数组名
    例2:动态数组,计算前缀和数组
#include<bits/stdc++.h>
using namespace std;

int n;
int *a;//定义指针变量a,后面直接当数组名使用

int main(){
    scanf("%d",&n);
    a=new int[n+1];//向操作系统申请了连续的n+1个int型的空间

    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);

    for(int i=2;i<=n;i++)
        a[i]+=a[i-1];

    for(int i=1;i<=n;i++)
        printf("%d",a[i);

    return 0;
}
输入:5
1 2 3 4 5
输出:1 3 6 10 15
说明:
动态数组的优点:可以确定小数据没问题的前提下,尽量满足大数据的需求。

指针与字符串

  • 1、字符串的表示形式
①用字符数组存放一个字符串,然后输出该字符串。
int main(){
    char str[]="I love China!";
    printf("%s\n",str);
}
②用字符指针指向一个字符串。可以不定义字符数组,而定义一个字符数组。用字符指针指向字符串中的字符。
int main(){
    char *str="I love China!";
    printf("%s\n",str);
}
  • 2、字符串指针作函数参数
    例3:输入一个长度最大为100的字符串,以字符数组的方式储存,再将字符串倒序储存,输出倒序储存后的字符串。(这里以字符指针为函数参数)
#include<bits/stdc++.h>
using namespace std;

void swapp(char &a,char &b){//交换两个字符的位置
    chat t;
    t=a;a=b;b=t;
}

void work(char *str){
    int len=strlen(str);

    for(int i=0;i<=len/2;i++)
        swapp(str[i),sre[len-i-1]);
}

int main(){
    char s[110];
    char *str=s;
    gets(s);

    work(str);
    printf("%s",s);

    return 0;
}
输入:! anihC evol I
输出:I love China!

指针与函数

  • 1、指针作为函数参数
    我们可以编写以下一个函数,用于将两个整型变量的值交换.
void swap(int *x,int *y){
    int t=*x;
    *x=*y;
    *y=t;
}

这时,我们在其他函数中可以使用这个函数;

int a=5,b=3;
swap(&a,&b);
printf("a=%d,b=%d",a,b);
输出:a=3,b=5
  • 2、函数返回指针
返回指针值的函数的一般定义形式为:
类型名 *函数名(参数列表)
例如:
int *a(int x,int y)
  • 3、函数指针和函数指针数组
    例4:使用函数指针调用函数示例。
#include<bits/stdc++.h>
using namespace std;

int t(int a){
    return a;
}

int main(){
    cout<<t<<endl;//显示函数地址

    int (*p)(int a);//定义函数指针变量p
    p=t;//将函数t的地址赋给函数指针p
    cout<<p(5)<<','<<(*p)(10)<<endl;//输出p(5)是C++的写法,(*p)(10)是兼容C,这是使用p来调节函数的两种方法。

    return 0;
}
输出:
1
5,10
函数指针的基本操作有三个:
①声明函数指针
②获取函数的地址
③使用函数指针来调用函数

例5:使用typedef定义函数指针示例。

#include<bits/stdc++.h>
using namespace std;

int sum(int a,int b){
    return a+b;
}

typedef int (*LP)(int ,int);//定义了一个函数指针变量类型LP

int main(){
    LP p=sum;定义了一个LP类型的函数指针LP,并赋值为sum
    cout<<p(2,5);//使用p来调用函数,实参为2和5,调用sum函数,输出返回值7

    return 0;
}
输出:7

例6:使用函数指针数组,模拟菜单功能实现方法示例。

#include<bits/stdc++.h>
using namespace std;

void t1(){cout<<"test1";}
void t2(){cout<<"test2";}
void t3(){cout<<"test3";}
void t4(){cout<<"test4";}
void t5(){cout<<"test5";}

typedef void(*LP)();//定义了一个函数指针变量类型LP

int main(){
    LP a[]={t1,t2,t3,t4,t5};//定义了一个LP类型的函数指针数组a,并初始化
    int x;
    cin>>x;

    a[x]();//使用a[x]()来调用选择的函数

    return 0;
}
输入:2
输出:test3

结构体指针

  • 1、结构体指针的定义与使用

    当一个指针变量用来指向一个结构体变量时,称之为结构体指针变量。

结构体指针变量定义的一般形式:
结构体名 *结构体指针变量名
struct student{
    char name[20];
    char sex;
    float score;
}*p;
也可写成
struct student{
    char name[20];
    char sex;
    float score;
};
student *p;

引用结构体指针变量指向的结构体变量的成员方式如下:

①指针名->成员名
②(*指针名).成员名
例如:(*p).score与p->score是等价的。

例7:结构体指针运用举例。

#include<bits/stdc++.h>
using namespace std;

struct student{
    char name[20];
    char sex;
    int score;
}s[3]={{"xiaoming",'f,'356},
    {"xiaoliang",'f',350},
    {"xiaohong",'m',0}};

int main(){
    student *p;
    printf("Name    Sex Score\n");
    for(p=s;p<s+3;p++)
        printf("%-9s%3c%7d\n",p->sex,p->score);

    return 0;
}
输出:
Name     Sex Score
xiaoming  f   356
xiaoliang f   350
xiaohong  m     0
说明:
这里p++起到移动指针的作用,随着p的变化,输出数组不同元素内容。
  • 2、自引用结构
struct stu{
    char name[20];
    int age,score;
    stu *p;
};

下面的定义可以在实际操作中建立起一个链表。

struct node{
    int x,y;
    node *next;
}point;



卬岇昂
2019-05-03 03:03

指针变量

  • 1、指针的概念

指针是一个变量。和普通变量不同的是,指针变量里存储的数据是一个内存地址,就好像一个指示器,指引着你去该内存地址开始的一块内存区域存取数据。

  • 2、指针的定义和使用
指针变量的定义格式为:
数据类型 *指针变量
1. 普通变量定义:int a=3;
2. 指针变量定义:int *p=NULL;(其实就是0,表示特殊的空地址)
3. 给指针变量p赋值:P=&a;(*p等价于a)

QQ图片20190503092403.png

设有指向整型变量p,如要把整型变量a的地址赋予p可以有以下两种方式:

1、指针变量初始化的方法
int a;int *p=&a;
2、赋值语句的方法
int a;int *p;p=&a;

QQ图片20190503094149.png

例1:输入两个不同的数,通过指针对两个数进行相加和相乘,并输出。

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a,b,s,t;
    int *pa,*pb;

    pa=&a;pb=&b;

    a=10;b=20;

    s=*pa+*pb;
    t=*pa**pb;

    printf("a=%d,b=%d\n",*pa,*pb);
    printf("s=%d,t=%d\n",s,t);

    return 0;
}
输出:
a=10,b=20
s=30,t=200
  • 3、指针的引用与运算
    一般的,我们可以这样看指针(int *p)与普通变量(int a)的对应关系
p——&a
*p——a
*p=3——a=3

①指针变量的初始化
QQ图片20190503100949.png
②指针变量的+、-运算
例2:输入n个数,使用指针变量访问输出。

#include<bits/stdc++.h>
using namespace std;
int a[101],n;

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);

    int p=&a[1];//定义指针变量int p,初始化为数组开始元素的地址,即a[i];
    for(int i=1;i<=n;i++){
        printf("%d",*p);
        p++;//p指向下一个数
    }

    return 0;
}
输入:4
2 1 6 0
输出: 2 1 6 0
说明:
①“p+ +”即刚好“跳过”一个整数的空间,达到下一个整数。
②“p- -”即向前“跳过”一个整数的空间,达到前一个整数。
③(p+3)就是指向后面第3个整数的地址。

③无类型指针
例3:无类型指针运用举例。

#include<bits/stdc++.h>
using namespace std;

int a=10;
double b=3.5;
void *p;

int main(){
    p=&a;//p的地址赋值
    cout<<*(int *)p<<endl;//必须明确p指向的空间的数据类型

    p=&b;
    cout<<*(double *)p<<endl;

    return 0;
}

输出:10
      3.5

④多重指针
例4:双重指针运用举例

#include<bits/stdc++.h>
using namespace std;l

int a=10;
int *p;
int **p;//定义双重指针

int main(){
    p=&a;//将p指向a
    pp=&p;//将pp指向a
    printf("%d=%d=%d\n",a,*p,**p);//**pp通过2次间接访问了a的变量的值10

    return 0;
}
输出:
10=10=10