数据结构实训——查找

声明：  以下是我们学校在学习数据结构时进行的实训，如涉及侵权马上删除文章

声明：本文主要用作技术分享，所有内容仅供参考。任何使用或依赖于本文信息所造成的法律后果均与本人无关。请读者自行判断风险，并遵循相关法律法规。

一、实训类型

   验证性实训

二、实训目的与任务

1．掌握顺序查找、折半查找算法的基本思想；

2. 掌握顺序查找、折半查找算法的实现方法；

3. 验证顺序查找、折半查找算法的时间性能。

4. 掌握二叉排序树定义和特性；

5. 掌握二叉排序树的建立方法，并实现基于二叉排序树的查找技术。

6. 掌握散列查找的基本思想；

7. 掌握闭散列表的构造方法；

8. 掌握散列技术的查找性能。

三、实训基本原理

1.顺序查找

顺序查找又称线性查找，是最基本的查找技术之一。

其基本思想为：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。

顺序查找在每次比较后都要判断查找是否越界，降低了查找速度。

将顺序查找算法改进：设置“哨兵”。哨兵就是待查值，将它放在查找方向的“尽头”处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。

2.折半查找

折半查找技术的使用前提：

·线性表中的记录必须按关键码有序；

·线性表必须采用顺序存储。

折半查找的基本思想为：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。

3.二叉排序树

是一种可以较快速地使得记录的插入、删除与查找操作很快地完成一种存储数据的方法。

二叉排序树（Binary Sort Tree）又称二叉查找树，它或者是一棵空的二叉树，或者是具有下列性质的二叉树：

⑴ 若它的左子树不空，则左子树上所有结点的值均小于根结点的值；

⑵ 若它的右子树不空，则右子树上所有结点的值均大于或等于根结点的值；

⑶ 它的左右子树也都是二叉排序树。

4.散列表的查找技术

散列技术是在记录的存储位置和它的关键码之间建立一个确定的对应关系H，使得每个关键码key和唯一的一个存储位置H(key)相对应。在查找时，根据这个确定的对应关系找到给定值k的映射H(k)，若查找集合中存在这个记录，则必定在H(k)的位置上。采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表（Hash Table），将关键码映射为散列表中适当存储位置的函数称为散列函数（Hash Function），所得的存储位置址称为散列地址。

散列既是一种存储方法，也是一种查找方法。但是散列不是一种完整的存储结构，因为它只是通过记录的关键码定位该记录，很难完整地表达记录之间的逻辑关系，所以，散列主要是面向查找的存储结构。

一般来说，散列技术的查找速度要比前面介绍的基于关键码比较的查找技术的查找速度高。但是，散列方法一般不适用于允许多个记录有同样关键码的情况。

四、实训设备

1．计算机

五、实训内容

1. 输入10个不同的实型数据，利用顺序查找方法完成给定值的查找。

2. 输入10个有序整型数据，利用折半查找方法完成给定值的查找。

3. 输入10个整型数据，构造一棵二叉排序树，并执行数据删除与数据插入操作。

4. 输入10个整型数据，构造一棵二叉排序树，完成该二叉树的前序、中序、后序遍历，并分析遍历结果。（设计实训选做）

5. 针对自己的班集体中的“学生姓名”设计一个哈希表，使得平均查找长度不超过2，完成相应的建表和查表程序。基本要求：假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构照，用链表法处理冲突。

1. 输入10个不同的实型数据，利用顺序查找方法完成给定值的查找。

#include <stdio.h>

#define M  100          /*顺序表的表长*/

typedef int KeyType;           /*关键字类型为int型*/

typedef struct

{   KeyType key; /*存放关键字，KeyType为关键字类型*/

}SearchL;

int SeqSearch(SearchL  r[],int n,KeyType k)

{  /*顺序查找算法函数，表中元素下标为1到n*/  

    int i=n;  

    r[0].key=k; /*设元素r[o]为要查找的关键字k（即监视哨）*/  

    while (r[i].key!=k)  /*从后向前顺序比较*/     

         i--;  

    return(i); /*返回查找元素下标，当为0时表示查找失败*/

}

int main()

{

    SearchL A[M];

    int i,n,m,k;

    printf("请输入查找表的长度\n");

    scanf("%d",&n);

    printf("请输入查找表的数据\n");

    for(i=1;i<=n;i++)

      scanf("%d",&A[i].key);

      printf("请输入待查的数据\n");

        scanf("%d",&k);

       m=SeqSearch(A,n,k);

    if(m==0)

    printf("表中没有此数据");

    else

    printf("表中此数据在%d位置\n",m);

    return 0;

}

2. 输入10个有序整型数据，利用折半查找方法完成给定值的查找。

#include <stdio.h>

#define M  100          /*顺序表的表长*/

typedef int KeyType;           /*关键字类型为int型*/

typedef struct

{   KeyType key; /*存放关键字，KeyType为关键字类型*/

}SearchL;

int BinarySearch(SearchL  r[], int n, KeyType k)

{ 

    int low = 1, high = n, mid;

    while (low <= high)

    {

        mid = (low + high) / 2;

        if (r[mid].key == k)

            return mid;

        else if (r[mid].key < k)

            low = mid + 1;

        else

            high = mid - 1;

    }

    return 0;  // 未找到返回 0

}

int main()

{

    SearchL A[M];

    int i,n,m,k;

    printf("请输入查找表的长度\n");

    scanf("%d",&n);

    printf("请输入查找表的数据\n");

    for(i=1;i<=n;i++)

        scanf("%d",&A[i].key);

    printf("请输入待查的数据\n");

    scanf("%d",&k);

    m = BinarySearch(A,n,k);

    if(m==0)

        printf("表中没有此数据");

    else

        printf("表中此数据在%d位置\n",m);

    return 0;

}

3. 输入10个整型数据，构造一棵二叉排序树，并执行数据删除与数据插入操作。

#include <stdio.h>

#include <stdlib.h>

// 二叉树节点结构体

typedef struct TreeNode {

    int data;

    struct TreeNode *left;

    struct TreeNode *right;

} TreeNode;

// 创建新节点

TreeNode* createNode(int data) {

    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));

    newNode->data = data;

    newNode->left = NULL;

    newNode->right = NULL;

    return newNode;

}

// 插入节点

TreeNode* insert(TreeNode* root, int data) {

    if (root == NULL) {

        return createNode(data);

    }

    if (data < root->data) {

        root->left = insert(root->left, data);

    } else if (data > root->data) {

        root->right = insert(root->right, data);

    }

    return root;

}

// 中序遍历

void inorderTraversal(TreeNode* root) {

    if (root!= NULL) {

        inorderTraversal(root->left);

        printf("%d ", root->data);

        inorderTraversal(root->right);

    }

}

// 查找最小节点

TreeNode* findMin(TreeNode* root) {

    while (root->left!= NULL) {

        root = root->left;

    }

    return root;

}

// 删除节点

TreeNode* deleteNode(TreeNode* root, int data) {

    if (root == NULL) {

        return root;

    }

    if (data < root->data) {

        root->left = deleteNode(root->left, data);

    } else if (data > root->data) {

        root->right = deleteNode(root->right, data);

    } else {

        if (root->left == NULL) {

            TreeNode* temp = root->right;

            free(root);

            return temp;

        } else if (root->right == NULL) {

            TreeNode* temp = root->left;

            free(root);

            return temp;

        }

        TreeNode* temp = findMin(root->right);

        root->data = temp->data;

        root->right = deleteNode(root->right, temp->data);

    }

    return root;

}

int main() {

    TreeNode* root = NULL;

    int data;

    printf("输入 10 个整型数据：\n");

    for (int i = 0; i < 10; i++) {

        scanf("%d", &data);

        root = insert(root, data);

    }

    printf("初始二叉排序树的中序遍历结果：\n");

    inorderTraversal(root);

    int delData, insData;

    printf("\n输入要删除的数据：");

    scanf("%d", &delData);

    root = deleteNode(root, delData);

    printf("删除后二叉排序树的中序遍历结果：\n");

    inorderTraversal(root);

    printf("\n输入要插入的数据：");

    scanf("%d", &insData);

    root = insert(root, insData);

    printf("插入后二叉排序树的中序遍历结果：\n");

    inorderTraversal(root);

    return 0;

}

4. 输入10个整型数据，构造一棵二叉排序树，完成该二叉树的前序、中序、后序遍历，并分析遍历结果。（设计实训选做）

#include <stdio.h>

#include <stdlib.h>

// 二叉树节点结构体

typedef struct TreeNode {

    int data;

    struct TreeNode *left;

    struct TreeNode *right;

} TreeNode;

// 创建新节点

TreeNode* createNode(int data) {

    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));

    newNode->data = data;

    newNode->left = NULL;

    newNode->right = NULL;

    return newNode;

}

// 插入节点

TreeNode* insert(TreeNode* root, int data) {

    if (root == NULL) {

        return createNode(data);

    }

    if (data < root->data) {

        root->left = insert(root->left, data);

    } else if (data > root->data) {

        root->right = insert(root->right, data);

    }

    return root;

}

// 前序遍历

void preorderTraversal(TreeNode* root) {

    if (root!= NULL) {

        printf("%d ", root->data);

        preorderTraversal(root->left);

        preorderTraversal(root->right);

    }

}

// 中序遍历

void inorderTraversal(TreeNode* root) {

    if (root!= NULL) {

        inorderTraversal(root->left);

        printf("%d ", root->data);

        inorderTraversal(root->right);

    }

}

// 后序遍历

void postorderTraversal(TreeNode* root) {

    if (root!= NULL) {

        postorderTraversal(root->left);

        postorderTraversal(root->right);

        printf("%d ", root->data);

    }

}

int main() {

    TreeNode* root = NULL;

    int data;

    printf("输入 10 个整型数据：\n");

    for (int i = 0; i < 10; i++) {

        scanf("%d", &data);

        root = insert(root, data);

    }

    printf("前序遍历结果：\n");

    preorderTraversal(root);

    printf("\n");

    printf("中序遍历结果：\n");

    inorderTraversal(root);

    printf("\n");

    printf("后序遍历结果：\n");

    postorderTraversal(root);

    printf("\n");

    // 分析遍历结果

    printf("分析：\n");

    printf("前序遍历首先访问根节点，然后递归遍历左子树和右子树，输出顺序反映了构建树的顺序。\n");

    printf("中序遍历先递归遍历左子树，然后访问根节点，再递归遍历右子树，输出结果是有序的（对于二叉排序树）。\n");

    printf("后序遍历先递归遍历左子树和右子树，最后访问根节点，常用于释放二叉树的内存等操作。\n");

    return 0;

}

六、实训注意事项

1．题目自选，至少要完成三个题目。

2．若完成题目个数多或设计的算法效率高，予以加分。

七、预习与思考题

1.各种查找方法比较

八、实训报告要求

1．书写算法或完整程序。

2．若调试程序时程序出错，请分析出错原因及修改方法。