[数据结构与算法]数据结构编程题

#include <iostream>
using namespace std;
typedef int Keytype;
typedef char Infotype;
typedef int Elemtype;

typedef struct 
{
    Keytype key;
    Infotype data;
}Rectype;

typedef struct 
{
    Keytype key;
    int link;
}Idxtype;

int Binsearch(Rectype R[], int n, Keytype k)
{
    int low = 0, high = n-1, mid;
    mid = (low + high)/2;
    while(low <= high){
        if(R[mid].key == k){
            return mid+1;
        }
        if(R[mid].key > k){
            high = mid-1;
        }else{
            low = mid+1;
        }
    }
    return 0;
}

int Idxsearch(Idxtype I[], int b, Rectype R[], int n, Keytype k)
{
    int low = 0, high = n-1, mid;
    mid = (low + high)/2;
    int s = (n+b-1)/b;
    while(low <= high){
        if(R[mid].key >= k){
            high = mid-1;
        }else{
            low = mid+1;
        }
    }
    int i = I[high+1].link;
    while(i <= I[high+1].link+s-1 && R[i].key != k){
        i++;
    }
    if(i < I[high+1].link+s-1){ 
        return i+1;
    }else{
        return 0;
    }
}

void Insertsort(Rectype R[], int n)
{
    int i, j;
    Rectype temp;
    for(i = 1; i < n; i++){
        temp = R[i];
        j = n-1;
        while(j > 0 && temp.key < R[j].key){
            R[j+1] = R[j];
            j--;
        }
        R[j+1] = temp;
    }
}

void Bubblesort(Rectype R[], int n)
{
    for(int i = 0; i < n-1; i++){
        bool exchange = true;
        for(int j = n-1; j > i; j--){
            if(R[j].key < R[j-1].key){
                swap(R[j], R[j-1]);
                exchange = false;
            }
        }
        if(exchange){
            return;
        }
    }
}

//顺序表
typedef struct
{
    Elemtype data;
    int length;
}SqList;

//单链表
typedef struct LNode
{
    Elemtype data;
    struct LNode *next;
}LinkNode;

//双链表
typedef struct DNode
{
    Elemtype data;
    struct DNode *prior;
    struct DNode *next;
}DLinkNode;

//顺序栈
typedef struct 
{
    Elemtype data;
    int top;
}SqStack;

//链栈
typedef struct linknode
{
    Elemtype data;
    struct linknode *next;
}LinkStNode;

//顺序队
typedef struct 
{
    Elemtype data;
    int front, rear;
}SqQueue;

//链队
typedef struct qnode
{
    Elemtype data;
    struct qnode *next;
}DataNode;
typedef struct
{
    DataNode *front;
    DataNode *rear;
}LinkQuNode;