PTA-学校-数据结构（查找）

1-1 有序数组的插入

分数 8

作者 陈越

单位 浙江大学

本题要求将任一给定元素插入从大到小排好序的数组中合适的位置，以保持结果依然有序。

函数接口定义：

bool Insert( List L, ElementType X );

其中List结构定义如下：

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较，并且题目保证传入的数据是递减有序的。函数Insert要将X插入Data[]中合适的位置，以保持结果依然有序（注意：元素从下标0开始存储）。但如果X已经在Data[]中了，就不要插入，返回失败的标记false；如果插入成功，则返回true。另外，因为Data[]中最多只能存MAXSIZE个元素，所以如果插入新元素之前已经满了，也不要插入，而是返回失败的标记false。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10
typedef enum {false, true} bool;
typedef int ElementType;

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

List ReadInput(); /* 裁判实现，细节不表。元素从下标0开始存储 */
void PrintList( List L ); /* 裁判实现，细节不表 */
bool Insert( List L, ElementType X );

int main()
{
    List L;
    ElementType X;

    L = ReadInput();
    scanf("%d", &X);
    if ( Insert( L, X ) == false )
        printf("Insertion failed.\n");
    PrintList( L );

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例1：

5
35 12 8 7 3
10

输出样例1：

35 12 10 8 7 3
Last = 5

输入样例2：

6
35 12 10 8 7 3
8

输出样例2：

Insertion failed.
35 12 10 8 7 3
Last = 5

解析

bool Insert( List L, ElementType X ) {
    // 1. 检查数组是否已满（Last是最后一个元素位置，MAXSIZE-1是最大下标）
    if (L->Last >= MAXSIZE - 1) {
        return false;
    }
    
    // 2. 检查X是否已存在（数组有序，遍历即可，长度≤10，效率无压力）
    for (int i = 0; i <= L->Last; ++i) {
        if (L->Data[i] == X) {
            return false;
        }
    }
    
    // 3. 找到插入位置pos：第一个≤X的元素的前面（保持递减有序）
    Position pos = 0;
    // 当pos未越界且当前元素>X时，继续向后找（说明X应插在当前元素后面）
    while (pos <= L->Last && L->Data[pos] > X) {
        pos++;
    }
    
    // 4. 移动元素：从最后一个元素到pos位置，依次后移1位，腾出插入空间
    for (int i = L->Last; i >= pos; --i) {
        L->Data[i + 1] = L->Data[i];
    }
    
    // 5. 插入X并更新Last指针
    L->Data[pos] = X;
    L->Last++;
    
    return true;
}

1-2 二分查找

分数 8

作者 陈越

单位 浙江大学

本题要求实现二分查找算法。

函数接口定义：

Position BinarySearch( List L, ElementType X );

其中List结构定义如下：

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较，并且题目保证传入的数据是递增有序的。函数BinarySearch要查找X在Data中的位置，即数组下标（注意：元素从下标1开始存储）。找到则返回下标，否则返回一个特殊的失败标记NotFound。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

List ReadInput(); /* 裁判实现，细节不表。元素从下标1开始存储 */
Position BinarySearch( List L, ElementType X );

int main()
{
    List L;
    ElementType X;
    Position P;

    L = ReadInput();
    scanf("%d", &X);
    P = BinarySearch( L, X );
    printf("%d\n", P);

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例1：

5
12 31 55 89 101
31

输出样例1：

2

输入样例2：

3
26 78 233
31

输出样例2：

0

解析

Position BinarySearch(List L, ElementType X) {
    Position left = 1;          // 左边界：元素从下标1开始存储
    Position right = L->Last;   // 右边界：最后一个元素的位置
    while (left <= right) {     // 查找区间有效（左<=右）
        Position mid = (left + right) / 2;  // 计算中间位置
        if (L->Data[mid] == X) {
            return mid;         // 找到目标，返回下标
        } else if (L->Data[mid] < X) {
            left = mid + 1;     // 目标在右半区间，左边界右移
        } else {
            right = mid - 1;    // 目标在左半区间，右边界左移
        }
    }
    return NotFound;            // 未找到目标，返回失败标记
}

1-3 统计二分查找比较的次数

分数 9

作者 杨嫘

单位 桂林学院

在一个有序表中进行二分查找操作，要求查找元素x，统计查找过程中需要比较的次数。

例如：0 2 4 5 8 9
查找元素8，比较次数为2
查找元素9，比较次数为3
查找元素10，比较次数为3

函数接口定义：

int bi_searchSq(SqList L,ElemType x); 

其中 L 和 x 都是用户传入的参数。 L是顺序表； x 是要查找的元素值。函数须返回查找过程中比较的次数。

裁判测试程序样例：

typedef int ElemType;
typedef struct SqList{
    ElemType data[MAXSIZE];
    int len;
}SqList;
void createSq(SqList *L);  //输入函数，具体实现略 
void printSq(SqList L);   //输出函数，具体实现略 
int bi_searchSq(SqList L,ElemType x); 
int main() 
{
    SqList L;
    createSq(&L);
    int x;
    scanf("%d",&x);
    printf("you find %d times",bi_searchSq(L,x));
}

/* 请在这里填写答案 */

输入样例：

6
0 2 4 5 8 9
4

输出样例：

you find 1 times

解析

int bi_searchSq(SqList L, ElemType x) {
    int left = 0, right = L.len - 1;
    int cnt = 0;

    while (left <= right) {
        int mid = (left + right) / 2;
        cnt++;  // 与 data[mid] 比较一次

        if (L.data[mid] == x)
            return cnt;
        else if (L.data[mid] > x)
            right = mid - 1;
        else
            left = mid + 1;
    }

    return cnt; // 未找到也返回比较次数
}

1-4 是否二叉搜索树

分数 8

作者 DS课程组

单位 浙江大学

本题要求实现函数，判断给定二叉树是否二叉搜索树。

函数接口定义：

bool IsBST ( BinTree T );

其中BinTree结构定义如下：

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

函数IsBST须判断给定的T是否二叉搜索树，即满足如下定义的二叉树：

定义：一个二叉搜索树是一棵二叉树，它可以为空。如果不为空，它将满足以下性质：

• 非空左子树的所有键值小于其根结点的键值。
• 非空右子树的所有键值大于其根结点的键值。
• 左、右子树都是二叉搜索树。

如果T是二叉搜索树，则函数返回true，否则返回false。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;
typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

BinTree BuildTree(); /* 由裁判实现，细节不表 */
bool IsBST ( BinTree T );

int main()
{
    BinTree T;

    T = BuildTree();
    if ( IsBST(T) ) printf("Yes\n");
    else printf("No\n");

    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例1：如下图

输出样例1：

Yes

输入样例2：如下图

输出样例2：

No

解析

bool IsBST ( BinTree T ) {
    static int last;          // 记录上一节点值
    static bool first = true; // 是否为第一个节点

    if (!T) return true;

    // 检查左子树
    if (!IsBST(T->Left)) return false;

    // 与上一节点比较
    if (first) {
        last = T->Data;
        first = false;
    } else {
        if (T->Data <= last)   // 必须严格递增
            return false;
        last = T->Data;
    }

    // 检查右子树
    return IsBST(T->Right);
}

1-5 数据结构考题 - 二叉排序树

分数 8

作者 陈皓

单位 合肥师范学院

建立一个二叉排序树，根据给定值对其实施查找。

二叉排序树的二叉链表存储表示：

typedef int ElemType;
typedef  struct  BSTNode
{  
    ElemType  data;
    struct  BSTNode   *lchild,*rchild;
}BSTNode,*BSTree;

函数接口定义：

下面给出了 二叉排序树创建和搜索 函数的大部分内容，但缺少了一部分（以下划线____标识出来的部分）。

请先将以下代码中画横线的部分补充完整，然后将完整的函数BSTInsert,BSTCreate,BSTSearch提交系统，完成题目要求的功能。

void BSTInsert( BSTree &T, BSTree s)
{
    if(T==NULL)
        T=s;
    else if(s->data<T->data)
        BSTInsert( ____ ,s);
    else 
        BSTInsert( ____ ,s);
}

void BSTCreate(BSTree  &T)
{   
    ElemType x;  BSTree  s;
    T=NULL;
    cin>>x;
    while (x!=-1)
    {  
        s=new BSTNode;
        s->data=x;
        s->lchild=s->rchild=NULL;
        BSTInsert( ____ ,  ____ );
        cin>>x;
    }
}

BSTree BSTSearch(BSTree T, ElemType k)
{  
    if(!T || ____ )
        return ____ ;
    if(k<T->data)
        return  BSTSearch( ____ ,k);
    else
        return  BSTSearch ( ____ ,k);
}

该函数中的参数说明：

ElemType k 要搜索的值

顺序表中第一个数据元素存储在 T.R[1]

测试主程序样例：

int main ()
{    BSTree T,p; int x;
    BSTCreate(T);
    cin>>x;
    p=BSTSearch(T,x);
    if(p!=NULL)
    {  cout<<"have found!";
       cout<<" lchild:";
       if(p->lchild) cout<<p->lchild->data;
       else cout<<"NULL";
       cout<<" rchild:";
       if(p->rchild) cout<<p->rchild->data;
       else cout<<"NULL";
    }
    else
       cout<<"NOT FOUND!";
    return 0;
}

输入格式:

第一行输入二叉排序树中结点的值，以-1结束。用逐个插入的方式创建二叉排序树。

第二行输入一个要查找的值。

输出格式:

找到，输出have found!。接着空一格，输出该结点左孩子值，后再空一格，输出该结点右孩子的值。如果孩子为空，对应位置输出NULL。

如果没有找到，输出NOT FOUND!。

输入样例:

10 18 3 8 20 2 7 -1
3

输出样例:

have found! lchild:2 rchild:8

输入样例2:

10 18 3 8 20 2 7 -1
8

输出样例2:

have found! lchild:7 rchild:NULL

输入样例3:

10 18 3 8 20 2 7 -1
5

输出样例3:

NOT FOUND!

解析

void BSTInsert( BSTree &T, BSTree s)
{
    if(T==NULL)
        T=s;
    else if(s->data < T->data)
        BSTInsert(T->lchild, s);
    else 
        BSTInsert(T->rchild, s);
}

void BSTCreate(BSTree  &T)
{   
    ElemType x;  BSTree  s;
    T=NULL;
    cin >> x;
    while (x != -1)
    {  
        s = new BSTNode;
        s->data = x;
        s->lchild = s->rchild = NULL;
        BSTInsert(T, s);
        cin >> x;
    }
}

BSTree BSTSearch(BSTree T, ElemType k)
{  
    if(!T || T->data == k)
        return T;
    if(k < T->data)
        return BSTSearch(T->lchild, k);
    else
        return BSTSearch(T->rchild, k);
}

1-6 线性探测法的查找函数

分数 9

作者 DS课程组

单位 浙江大学

试实现线性探测法的查找函数。

函数接口定义：

Position Find( HashTable H, ElementType Key );

其中HashTable是开放地址散列表，定义如下：

#define MAXTABLESIZE 100000  /* 允许开辟的最大散列表长度 */
typedef int ElementType;     /* 关键词类型用整型 */
typedef int Index;           /* 散列地址类型 */
typedef Index Position;      /* 数据所在位置与散列地址是同一类型 */
/* 散列单元状态类型，分别对应：有合法元素、空单元、有已删除元素 */
typedef enum { Legitimate, Empty, Deleted } EntryType;

typedef struct HashEntry Cell; /* 散列表单元类型 */
struct HashEntry{
    ElementType Data; /* 存放元素 */
    EntryType Info;   /* 单元状态 */
};

typedef struct TblNode *HashTable; /* 散列表类型 */
struct TblNode {   /* 散列表结点定义 */
    int TableSize; /* 表的最大长度 */
    Cell *Cells;   /* 存放散列单元数据的数组 */
};

函数Find应根据裁判定义的散列函数Hash( Key, H->TableSize )从散列表H中查到Key的位置并返回。如果Key不存在，则返回线性探测法找到的第一个空单元的位置；若没有空单元，则返回ERROR。

裁判测试程序样例：

#include <stdio.h>

#define MAXTABLESIZE 100000  /* 允许开辟的最大散列表长度 */
typedef int ElementType;     /* 关键词类型用整型 */
typedef int Index;           /* 散列地址类型 */
typedef Index Position;      /* 数据所在位置与散列地址是同一类型 */
/* 散列单元状态类型，分别对应：有合法元素、空单元、有已删除元素 */
typedef enum { Legitimate, Empty, Deleted } EntryType;

typedef struct HashEntry Cell; /* 散列表单元类型 */
struct HashEntry{
    ElementType Data; /* 存放元素 */
    EntryType Info;   /* 单元状态 */
};

typedef struct TblNode *HashTable; /* 散列表类型 */
struct TblNode {   /* 散列表结点定义 */
    int TableSize; /* 表的最大长度 */
    Cell *Cells;   /* 存放散列单元数据的数组 */
};

HashTable BuildTable(); /* 裁判实现，细节不表 */
Position Hash( ElementType Key, int TableSize )
{
    return (Key % TableSize);
}

#define ERROR -1
Position Find( HashTable H, ElementType Key );

int main()
{
    HashTable H;
    ElementType Key;
    Position P;

    H = BuildTable(); 
    scanf("%d", &Key);
    P = Find(H, Key);
    if (P==ERROR)
        printf("ERROR: %d is not found and the table is full.\n", Key);
    else if (H->Cells[P].Info == Legitimate)
        printf("%d is at position %d.\n", Key, P);
    else
        printf("%d is not found.  Position %d is returned.\n", Key, P);

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例1：（注：-1表示该位置为空。下同。）

11
11 88 21 -1 -1 5 16 7 6 38 10
38

输出样例1：

38 is at position 9.

输入样例2：

11
11 88 21 -1 -1 5 16 7 6 38 10
41

输出样例2：

41 is not found.  Position 3 is returned.

输入样例3：

11
11 88 21 3 14 5 16 7 6 38 10
41

输出样例3：

ERROR: 41 is not found and the table is full.

解析

Position Find( HashTable H, ElementType Key )
{
    Position Pos, NewPos;
    int Count = 0;  

    Pos = Hash(Key, H->TableSize);   /* 初始散列位置 */
    NewPos = Pos;

    while (H->Cells[NewPos].Info != Empty && Count < H->TableSize) {
        if (H->Cells[NewPos].Info == Legitimate &&
            H->Cells[NewPos].Data == Key)
            return NewPos;  /* 找到 Key */

        /* 线性探测：向后移动 1 格 */
        NewPos = (NewPos + 1) % H->TableSize;
        Count++;
    }

    if (Count == H->TableSize)   /* 散列表满了，无空位 */
        return ERROR;

    return NewPos;   /* 返回第一个 Empty 或 Deleted 单元 */
}

2-1 悄悄关注

分数 10

作者 陈越

单位 浙江大学

新浪微博上有个“悄悄关注”，一个用户悄悄关注的人，不出现在这个用户的关注列表上，但系统会推送其悄悄关注的人发表的微博给该用户。现在我们来做一回网络侦探，根据某人的关注列表和其对其他用户的点赞情况，扒出有可能被其悄悄关注的人。

输入格式：

输入首先在第一行给出某用户的关注列表，格式如下：

人数N 用户1 用户2 …… 用户N

其中N是不超过5000的正整数，每个用户i（i=1, …, N）是被其关注的用户的ID，是长度为4位的由数字和英文字母组成的字符串，各项间以空格分隔。

之后给出该用户点赞的信息：首先给出一个不超过10000的正整数M，随后M行，每行给出一个被其点赞的用户ID和对该用户的点赞次数（不超过1000），以空格分隔。注意：用户ID是一个用户的唯一身份标识。题目保证在关注列表中没有重复用户，在点赞信息中也没有重复用户。

输出格式：

我们认为被该用户点赞次数大于其点赞平均数、且不在其关注列表上的人，很可能是其悄悄关注的人。根据这个假设，请你按用户ID字母序的升序输出可能是其悄悄关注的人，每行1个ID。如果其实并没有这样的人，则输出“Bing Mei You”。

输入样例1：

10 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao
8
Magi 50
Pota 30
LLao 3
Ammy 48
Dave 15
GAO3 31
Zoro 1
Cath 60

输出样例1：

Ammy
Cath
Pota

输入样例2：

11 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao Pota
7
Magi 50
Pota 30
LLao 48
Ammy 3
Dave 15
GAO3 31
Zoro 29

输出样例2：

Bing Mei You

解析

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXN 5000
#define MAXM 10000
#define IDLEN 5   // 4 chars + '\0'

char follow[MAXN][IDLEN];       // 关注列表
char likeID[MAXM][IDLEN];       // 点赞用户
int likeCnt[MAXM];              // 点赞次数

// 按字典序排序用
int cmp(const void *a, const void *b) {
    return strcmp((char*)a, (char*)b);
}

// 判断某 ID 是否在关注列表中（顺序查找即可，N<=5000）
int inFollow(char *id, int N) {
    for (int i = 0; i < N; i++) {
        if (strcmp(follow[i], id) == 0)
            return 1;
    }
    return 0;
}

int main() {
    int N, M;
    scanf("%d", &N);

    for (int i = 0; i < N; i++)
        scanf("%s", follow[i]);

    scanf("%d", &M);

    long long sum = 0;
    for (int i = 0; i < M; i++) {
        scanf("%s %d", likeID[i], &likeCnt[i]);
        sum += likeCnt[i];
    }

    double avg = (double)sum / M;

    // 记录可疑的“悄悄关注”对象
    char suspect[MAXM][IDLEN];
    int scnt = 0;

    for (int i = 0; i < M; i++) {
        // 条件：点赞次数 > 平均数 AND 不在关注列表
        if (likeCnt[i] > avg && !inFollow(likeID[i], N)) {
            strcpy(suspect[scnt++], likeID[i]);
        }
    }

    if (scnt == 0) {
        printf("Bing Mei You");
        return 0;
    }

    // 按字典序输出
    qsort(suspect, scnt, IDLEN, cmp);

    for (int i = 0; i < scnt; i++)
        printf("%s\n", suspect[i]);

    return 0;
}

2-2 整型关键字的平方探测法散列

分数 10

作者 陈越

单位 浙江大学

本题的任务很简单：将给定的无重复正整数序列插入一个散列表，输出每个输入的数字在表中的位置。所用的散列函数是 H(k**ey)=k**ey%TSize，其中 TSize 是散列表的表长。要求用平方探测法（只增不减，即H(Key)+i2）解决冲突。

注意散列表的表长最好是个素数。如果输入给定的表长不是素数，你必须将表长重新定义为大于给定表长的最小素数。

输入格式：

首先第一行给出两个正整数 MSize（≤104）和 N（≤MSize），分别对应输入的表长和输入数字的个数。随后第二行给出 N 个不重复的正整数，数字间以空格分隔。

输出格式：

在一行中按照输入的顺序给出每个数字在散列表中的位置（下标从 0 开始）。如果某个数字无法插入，就在其位置上输出 -。输出间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

4 4
10 6 4 15

输出样例：

0 1 4 -

解析

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

// 检查素数
bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0) return false;
    return true;
}

// 找大于等于 n 的最小素数
int nextPrime(int n) {
    while (!isPrime(n)) n++;
    return n;
}

int main() {
    int MSize, N;
    cin >> MSize >> N;
    int TSize = nextPrime(MSize);  // 修正表长为素数

    vector<int> hashTable(TSize, -1);
    vector<int> nums(N);
    for (int i = 0; i < N; i++) cin >> nums[i];

    for (int i = 0; i < N; i++) {
        int key = nums[i];
        int pos = key % TSize;
        int j = 0;
        bool inserted = false;

        while (j < TSize) {
            int newPos = (pos + j * j) % TSize;
            if (hashTable[newPos] == -1) {
                hashTable[newPos] = key;
                cout << newPos;
                inserted = true;
                break;
            }
            j++;
        }

        if (!inserted) cout << "-";

        if (i != N - 1) cout << " ";
    }

    return 0;
}

2-3 顺序表的顺序查找

分数 10

作者 陈越

单位 浙江大学

请编写程序，实现顺序表的顺序查找算法。

输入格式：

输入首先给出一个正整数 n（≤100），随后一行给出 n 个不超过 103 的正整数，为顺序表中的元素。最后一行给出若干正整数，为需要查找的元素，最后以 −1 结尾，这个数字不需要查找。
同行数字间以空格分隔。题目保证顺序表中无重复元素。

输出格式：

在一行中输出每个待查找元素在顺序表中的位序（从 1 开始）。若元素不在表中，则输出 0。为简化输出处理，每个数字后面跟一个空格。

输入样例：

9
3 7 9 1 4 6 2 5 8
3 8 2 9 10 -1

输出样例：

1 9 7 3 0 

解析

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

int main() {
    int n;
    cin >> n;
    vector<int> seq(n);
    for (int i = 0; i < n; i++) cin >> seq[i];

    int key;
    while (cin >> key && key != -1) {
        int pos = 0;  // 默认未找到，输出0
        for (int i = 0; i < n; i++) {
            if (seq[i] == key) {
                pos = i + 1; // 位序从1开始
                break;
            }
        }
        cout << pos << " ";
    }

    return 0;
}

2-4 折半查找

分数 10

作者 陈越

单位 浙江大学

请编写程序，实现有序顺序表的折半查找算法。

输入格式：

输入首先给出一个正整数 n（≤105），随后一行按升序给出 n 个不超过 108 的正整数，为顺序表中的元素。最后一行给出若干正整数，为需要查找的元素，最后以 −1 结尾，这个数字不需要查找。
同行数字间以空格分隔。题目保证顺序表中无重复元素。

输出格式：

在一行中输出每个待查找元素在顺序表中的位序（从 1 开始）。若元素不在表中，则输出 0。为简化输出处理，每个数字后面跟一个空格。

输入样例：

9
1 2 3 4 5 6 7 8 9
1 5 4 9 10 -1

输出样例：

1 5 4 9 0 

解析

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

// 折半查找函数，返回位序（从1开始），找不到返回0
int binarySearch(const vector<int>& arr, int key) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == key) return mid + 1; // 位序从1开始
        else if (arr[mid] < key) left = mid + 1;
        else right = mid - 1;
    }
    return 0; // 未找到
}

int main() {
    int n;
    cin >> n;
    vector<int> seq(n);
    for (int i = 0; i < n; i++) cin >> seq[i];

    int key;
    while (cin >> key && key != -1) {
        cout << binarySearch(seq, key) << " ";
    }

    return 0;
}

2-5 开放定址法

分数 10

作者 陈越

单位 浙江大学

请编写程序，实现采用开放定址法的散列查找算法。

输入格式：

输入首先在第一行给出散列表表长 L，为不超过 100 的素数；随后一行给出将要插入表中的元素个数 n（≤L）；下一行给出 n 个元素的键值，均为不超过 104 的正整数。

输出格式：

按序号（从 0 开始）升序输出散列表中非空元素，格式为：

ht[i] = x

其中 i 为序号，x 为元素键值。

输入样例：

11
6
11 22 1 10 21 22

输出样例：

ht[0] = 11
ht[1] = 22
ht[2] = 1
ht[3] = 21
ht[10] = 10

解析

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

int main() {
    int L, n;
    cin >> L >> n;
    vector<int> keys(n);
    for (int i = 0; i < n; i++) cin >> keys[i];

    vector<int> ht(L, -1); // -1表示空位

    for (int i = 0; i < n; i++) {
        int key = keys[i];
        int pos = key % L;
        int j = 0;
        bool inserted = false;

        while (j < L) {
            int idx = (pos + j) % L;
            if (ht[idx] == -1) { // 空位，插入
                ht[idx] = key;
                inserted = true;
                break;
            } else if (ht[idx] == key) { // 已存在，跳过
                inserted = true;
                break;
            }
            j++;
        }

        // 如果探测满表仍未插入，则忽略（本题保证n <= L，不会出现）
        if (!inserted) continue;
    }

    // 输出非空元素
    for (int i = 0; i < L; i++) {
        if (ht[i] != -1)
            cout << "ht[" << i << "] = " << ht[i] << endl;
    }

    return 0;
}