数据结构例题

区分函数中引用变量和指针的用法

1.定义整型a，b，分别输入他们的值，再交换之后输出。

输入：1 2          输出：a=2,b=1

错误1：输出为a=1,b=2,只是形参值改变

#include <stdio.h>
#include <stdlib.h>
 
void swap(int p,int q)
{
    int t;
    t=p;
    p=q;
    q=t;
}
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    swap(a,b);
    printf("a=%d,b=%d",a,b);
    return 0;
}

 错误2：输出为a=1,b=2，只是地址交换了，实参未改变

#include <stdio.h>
#include <stdlib.h>
 
void swap(int *p,int *q)
{
    int *t;
    t=p;
    p=q;
    q=t;
}
 
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    swap(a,b);
    printf("a=%d,b=%d\n",a,b);
    return 0;
}

 错误3：输出为a=2,b=2

#include <stdio.h>
#include <stdlib.h>
 
void swap(int *p,int *q)
{
    int *t;
    t=p;
    *p=*q;
    q=t;
}
 
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    swap(a,b);
    printf("a=%d,b=%d\n",a,b);
    return 0;
}

 正确1：直接对指针所指的值进行修改

#include <stdio.h>
#include <stdlib.h>
 
void swap(int *p,int *q)
{
    int t;
    t=*p;
    *p=*q;
    *q=t;
}
 
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    swap(a,b);
    printf("a=%d,b=%d\n",a,b);
    return 0;
}

 正确2：引用变量必须用c++

#include<cstdio>
#include<iostream>
using namespace std;
 
void swap(int &p,int &q)
{
    int t;
    t=p;
    p=q;
    q=t;
}
 
int main()
{
    int a,b;
    cin>>a>>b;
    swap(a,b);
    count<<"a="<<a<<","<<"b="<<b<<endl;
    return 0;
}

 二分查找法（时间效率的问题）

举例:数组a中存放从小到大排好序的n个整数，查找给定值k在数组中下标;若查找失败，返回-1

//函数部分
int BitSearch(int a[],int n,int k)
{
    int low=0,high=n-1,mid,found=0;
    while((low<=high)&&(found==0))
    {
        mid=(low+high)/2;
        if(k>a[mid])
        low=mid+1;
        else if(k==a[mid])
        found=1;
        else 
        high=mid-1;
    }
    if(found==1)
    return (mid);
    else
    return(-1);
}

 若n=15，此方法最多找四次（树的结构），而若一个一个数据对比需要找15次，对比之下，二分查找法时间效率会快很多。