首页 > 其他分享 >数据结构实验六

数据结构实验六

时间：2025-01-10 16:54:28浏览次数：1  
标签：int void elem high 实验 low SqList 数据结构

石 家 庄 铁 道 大 学
实 验 报 告

课程名称： 数据结构与算法设计 任课教师： 刘 丹 实验日期：2024.12.15
班 级： 信2305-3 姓 名： 徐戌 学 号： 20234316

实验项目名称：实验六
一、 实验目的
1.掌握插入排序的方法及效率分析
2.掌握选择排序的方法及效率分析
3.掌握交换排序的方法及效率分析
4.掌握归并排序的方法及效率分析
二、 实验内容

三、 设计文档

四、 源程序
6-4 快速排序

include<stdio.h>

include<stdlib.h>

typedef int KeyType;
typedef struct
{
KeyType elem; /elem[0]一般作哨兵或缓冲区/
int Length;
}SqList;
void CreatSqList(SqList L);/待排序列建立，由裁判实现，细节不表/
int Partition ( SqList L,int low, int high );
void Qsort ( SqList L,int low, int high );
int main()
{
SqList L;
int i;
CreatSqList(&L);
Qsort(L,1,L.Length);
for(i=1;i<=L.Length;i++)
printf("%d ",L.elem[i]);
return 0;
}
void Qsort ( SqList L,int low, int high )
{
int pivotloc;
if(low<high)
{
pivotloc = Partition(L, low, high ) ;
Qsort (L, low, pivotloc-1) ;
Qsort (L, pivotloc+1, high );
}
}
int Partition(SqList L, int low, int high) {
// 选择第一个元素作为基准值
KeyType pivot = L.elem[low];
while (low < high) {
// 从右往左找第一个小于基准值的元素
while (low < high && L.elem[high] >= pivot) {
high--;
}
// 将找到的元素放到左边合适位置（也就是low指向的位置）
L.elem[low] = L.elem[high];
// 从左往右找第一个大于基准值的元素
while (low < high && L.elem[low] <= pivot) {
low++;
}
// 将找到的元素放到右边合适位置（也就是high指向的位置）
L.elem[high] = L.elem[low];
}
// 把基准值放到最终正确的位置（也就是low和high相遇的位置）
L.elem[low] = pivot;
return low;
}
6-5 堆排序

include<stdio.h>

include<stdlib.h>

typedef int KeyType;
typedef struct {
KeyType elem; /elem[0]一般作哨兵或缓冲区/
int Length;
}SqList;
typedef SqList HeapType;
void CreatSqListHeapType L);/待排序列建立，由裁判实现，细节不表/
void HeapAdjust( HeapType H, int s, int m);
void HeapSort( HeapType H);
int main()
{
HeapType L;
int i;
CreatSqList(&L);
HeapSort(L);
for(i=1;i<=L.Length;i++)
{
printf("%d ",L.elem[i]);
}
return 0;
}
void HeapSort( HeapType H)
{ /堆顺序表H进行堆排序/
int i; KeyType rc;
/建立初始堆/
for( i=H.Length/2;i>0; i--)
{
HeapAdjust(H, i, H.Length);
}
for(i=H.Length;i>1;i--)
{
rc=H.elem[1];
H.elem[1]=H.elem[i];
H.elem[i]=rc;
HeapAdjust(H, 1, i-1);
}
}
void HeapAdjust(HeapType H, int s, int m) {
// 取出当前要调整的节点的值
KeyType temp = H.elem[s];
// 从当前节点的左孩子节点开始（数组下标表示，左孩子为2 * s）
for (int j = 2 * s; j <= m; j *= 2) {
// 如果有右孩子（下标为2 * s + 1）且右孩子比左孩子大，则选择右孩子
if (j < m && H.elem[j] < H.elem[j + 1]) {
j++;
}
// 如果当前节点已经大于等于子节点中的较大者，就不用调整了，直接break
if (temp >= H.elem[j]) {
break;
}
// 将较大的子节点值上移到当前节点位置
H.elem[s] = H.elem[j];
// 更新当前节点的下标，继续向下调整
s = j;
}
// 将之前取出的当前节点的值放到合适的位置
H.elem[s] = temp;
}
6-6 归并排序

include<stdio.h>

include<stdlib.h>

typedef int KeyType;
typedef struct {
KeyType elem; /elem[0]一般作哨兵或缓冲区/
int Length;
}SqList;
void CreatSqList(SqList L);/待排序列建立，由裁判实现，细节不表/
void MergeSort(SqList L,int low,int high);
void Merge(SqList L,int low,int m,int high);
int main()
{
SqList L;
int i;
CreatSqList(&L);
MergeSort(L,1,L.Length);
for(i=1;i<=L.Length;i++)
{
printf("%d ",L.elem[i]);
}
return 0;
}
void MergeSort(SqList L,int low,int high)
{
/用分治法进行二路归并排序/
int mid;
if(low<high) /区间长度大于1/
{
mid=(low+high)/2; /分解/
MergeSort(L,low,mid); /递归地对low到mid序列排序 /
MergeSort(L,mid+1,high); /递归地对mid+1到high序列排序 /
Merge(L,low,mid,high); /归并/
}
}
// 归并操作函数
void Merge(SqList L, int low, int m, int high) {
// 计算两个子序列的长度
int n1 = m - low + 1;
int n2 = high - m;

// 创建两个临时数组来存储两个子序列
KeyType left[n1];
KeyType right[n2];

// 将原数组中的两个子序列分别复制到临时数组中
for (int i = 0; i < n1; i++) {
    left[i] = L.elem[low + i];
}
for (int j = 0; j < n2; j++) {
    right[j] = L.elem[m + 1 + j];
}

// 初始化索引，分别用于遍历两个临时数组以及原数组归并后的位置
int i = 0, j = 0, k = low;
// 比较两个临时数组中的元素，将较小的放入原数组相应位置
while (i < n1 && j < n2) {
    if (left[i] <= right[j]) {
        L.elem[k++] = left[i++];
    } else {
        L.elem[k++] = right[j++];
    }
}

// 将left数组中剩余的元素复制到原数组（如果有）
while (i < n1) {
    L.elem[k++] = left[i++];
}

// 将right数组中剩余的元素复制到原数组（如果有）
while (j < n2) {
    L.elem[k++] = right[j++];
}

}
6-7 直接插入排序

include<stdio.h>

include<stdlib.h>

typedef int KeyType;
typedef struct {
KeyType elem; /elem[0]一般作哨兵或缓冲区/
int Length;
}SqList;
void CreatSqList(SqList L);/待排序列建立，由裁判实现，细节不表/
void InsertSort(SqList L);
int main()
{
SqList L;
int i;
CreatSqList(&L);
InsertSort(L);
for(i=1;i<=L.Length;i++)
{
printf("%d ",L.elem[i]);
}
return 0;
}
void InsertSort(SqList L) {
for (int i = 2; i <= L.Length; i++) { // 从第二个元素开始，将其插入前面已排好序的序列中
KeyType temp = L.elem[i]; // 取出当前要插入的元素
int j = i - 1;
// 在已排序的序列中查找合适的插入位置
while (j >= 1 && L.elem[j] > temp) {
L.elem[j + 1] = L.elem[j]; // 向后移动元素，腾出插入位置
j--;
}
L.elem[j + 1] = temp; // 将元素插入合适的位置
}
}
6-8 希尔排序的实现

include<stdio.h>

include<stdlib.h>

typedef int KeyType;
typedef struct {
KeyType elem; /elem[0]一般作哨兵或缓冲区/
int Length;
}SqList;
void CreatSqList(SqList L);/待排序列建立，由裁判实现，细节不表/
void ShellInsert(SqList L,int dk);
void ShellSort(SqList L);

int main()
{
SqList L;
int i;
CreatSqList(&L);
ShellSort(L);
for(i=1;i<=L.Length;i++)
{
printf("%d ",L.elem[i]);
}
return 0;
}
void ShellSort(SqList L)
{
/按增量序列dlta[0…t-1]对顺序表L作Shell排序,假设规定增量序列为5,3,1/
int k;
int dlta[3]={5,3,1};
int t=3;
for(k=0;k<t;++k)
ShellInsert(L,dlta[k]);
}
void ShellInsert(SqList L, int dk) {
for (int i = dk + 1; i <= L.Length; i++) {
KeyType temp = L.elem[i];
int j = i - dk;
while (j > 0 && L.elem[j] > temp) {
L.elem[j + dk] = L.elem[j];
j -= dk;
}
L.elem[j + dk] = temp;
}
}
五、 个人体会
在数据结构实验排序过程中，遇到诸多问题。首先，代码实现冒泡排序时，内层循环条件出错，导致排序结果混乱，经过仔细对比算法逻辑，纠正循环边界得以解决。其次，对于快速排序的递归部分理解困难，函数调用栈频频溢出，通过绘制递归展开图深入剖析，优化了递归终止条件。还有，使用系统自带排序函数与自定义排序对比测试时，数据类型不匹配引发报错，仔细检查数据类型转换后正常运行。
实验感想：这次实验让我深知理论与实践差距，编码中一个小疏忽就全盘皆错。但攻克难题后，对排序算法理解通透许多，编程能力、调试技巧都显著提升，也更有信心面对后续复杂的数据结构挑战。

标签：int,void,elem,high,实验,low,SqList,数据结构
From： https://www.cnblogs.com/-Xuxu/p/18664254

相关文章

  • 【西南科技大学计算机学院、智能计算与系统结构实验室主办 | ACM独立出版 | 往届均已
    ACM独立出版|往届均已成功检索，最快刊后1个月内实现EI检索征稿主题范围广：计算机网络安全、软件工程、信号处理、程序分析等领域主办单位：西南科技大学计算机学院、智能计算与系统结构实验室第五届计算机网络安全与软件工程国际学术会议（CNSSE2025）20255thInternational......
  • 数据结构(红黑树)
    问题的起源学习一个知识模块，一般先要厘清学习的目的，一个技术分支的出现必然是应对某个具体问题而产生的解决方案，搞清楚了问题的起源，对解决问题的思路就有了根本性的理解，来龙去脉把握清楚了学习起来就既有动力又有目标了。回归到红黑树的问题，红黑树其实也是一种平衡树，之前......
  • JSP开放实验室预约管理系统2118f--（程序+源码+数据库+调试部署+开发环境）
    本系统（程序+源码+数据库+调试部署+开发环境）带论文文档1万字以上，文末可获取，系统界面在最后面。系统程序文件列表开题报告内容一、研究背景与意义随着教育和科研的不断发展，实验室资源的有效管理和开放共享成为重要议题。传统的人工管理方式存在效率低、资源浪费等问题，无法满......
  • 数据结构全书简答题汇总（期末、考研）三万多字
    第一章：绪论-灰灰考研汇总1.数据：数据是信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并 被计算机程序处理的符号的集合。2.数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。3.数据项：数据项是数据结构中讨论的最小单位。 是数据......
  • 从上千份大厂面经呕心沥血整理：大厂高频手撕面试题（数据结构和算法篇 ，C++实现亲试可跑）
    目录 怎么判断两个链表是否相交？怎么优化？（字节跳动、货拉拉）手撕冒泡排序（美团）手撕快速排序（作业帮）手撕堆排序（美团）手撕归并排序（美团）手撕二分查找(VIVO)字符串的全排列（要求去重）（字节跳动）求一个字符串中最长不重复子串的长度（字节跳动） 反转字符串的单词：如何在原字符串上翻转......
  • 数据结构真难
    在期末周算是被数据结构狠狠折磨了，当然自己在之前在数据结构方面的学习还存在着欠缺，自己往后得多加上心，总的来说呢，数据结构是一门具有一定难度的课程，在复习过程中难免会遇到各种困难和挫折，如复杂的算法理解、难以调试的代码等。但是，只要保持克服困难的毅力和决心，不断地尝试和探索，......
  • [数据结构学习笔记10] 哈希表（Hashtable）
    哈希表也叫Hashmap或者Dictionary，它存储和检索都非常快，所以常用于缓存数据供后续快速访问。哈希函数，是这样的一个函数，你提供一个input，它会返回一个唯一的值（hashcode）。只要你的input是相同的，这个哈希函数会返回同样的output。从哈希函数到哈希表哈希表底层是一个数组结构，这意味......
  • Report -「概率数据结构」随机化骗分？我们是专业的！
    \[\mathscr{Lorain~y~w~la~Lora~blea.}\newcommand{\DS}[0]{\displaystyle}%operatorsalias\newcommand{\opn}[1]{\operatorname{#1}}\newcommand{\card}[0]{\opn{card}}\newcommand{\lcm}[0]{\opn{lcm}}\newcommand{\char}[0]{\opn{char}}\newc......
  • AHU计组（5）数据表示实验
    【设计题目】      数据表示实验                    【设计目的】深入理解数据表示原理掌握海明编码的设计原理，理解其检错纠错性能掌握CRC校验码的基本原理，理解其检错、纠错性能熟悉流水同步传输机制，理解流水清空、暂停原理【设计内容】汉......
  • 美国实验室新型激光技术突破，引领芯片制造质的飞跃
    1月5日，美国劳伦斯利弗莫尔国家实验室（LLNL）在激光技术领域取得了重大进展。该实验室正在全力研发一种基于铥元素的拍瓦（petawatt）级激光技术，这一技术犹如一颗璀璨的新星，在芯片制造领域引发了广泛的关注和期待。目前，极紫外光刻（EUV）工具在芯片制造中扮演着至关重要的角色，其中二氧化......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99