数据结构中的排序和查找

100以内的10到20个随机数的排序,查找,用C语言写出代码

2个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
数据结构内部排序实验报告

一、实验目的 1、掌握排序的有关概念和特点。 2、熟练掌握直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序等算法的基本思想。。 3、关键字序列有序与无序,对于不同的排序方法有不同的影响,通过该实验进一步加深理解。 二、实验内容 设有关键字序列k={ 12 , 45 , 21 , 12 , 30 , 2 , 68 , 33 },试用各种排序算法进行排序。 三、实验环境 TC或VC++ 四、实验步骤 1、从键盘输入上述8个整数,存放在数组quick[8]中,并输出值。 2、输出各种排序算法每一趟排序的结果,观察关键字次序的变化。 (1)直接插入排序算法如下: void InsertionSort ( SqList &L ) { // 对顺序表 L 作直接插入排序。 for ( i=2; i<=L.length; ++i ) if (L.r[i].key < L.r[i-1].key) { L.r[0] = L.r[i]; // 复制为监视哨 for ( j=i-1; L.r[0].key < L.r[j].key; -- j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[j+1] = L.r[0]; // 插入到正确位置 } } // InsertSort (2)希尔排序算法如下: void ShellInsert ( SqList &L, int dk ) { for ( i=dk+1; i<=n; ++i ) if ( L.r[i].key< L.r[i-dk].key) { L.r[0] = L.r[i]; // 暂存在R[0] for (j=i-dk; j>0&&(L.r[0].key<L.r[j].key); j-=dk) L.r[j+dk] = L.r[j]; // 记录后移,查找插入位置 L.r[j+dk] = L.r[0]; // 插入 } // if } // ShellInsert void ShellSort (SqList &L, int dlta[], int t) { // 增量为dlta[]的希尔排序 for (k=0; k<t; ++t) ShellInsert(L, dlta[k]); //一趟增量为dlta[k]的插入排序 } // ShellSort (3)冒泡排序算法如下: void BubbleSort(Elem R[ ], int n) { i = n; while (i >1) { lastExchangeIndex = 1; for (j = 1; j < i; j++) if (R[j+1].key < R[j].key) { Swap(R[j], R[j+1]); lastExchangeIndex = j; //记下进行交换的记录位置 } //if i = lastExchangeIndex; } // while } // BubbleSort (4)快速排序算法如下: int Partition (RedType R[], int low, int high) { R[0] = R[low]; pivotkey = R[low].key; // 枢轴 while (low<high) { while(low<high&& R[high].key>=pivotkey) -- high; // 从右向左搜索 R[low] = R[high]; while (low<high && R[low].key<=pivotkey) ++ low; // 从左向右搜索 R[high] = R[low]; } R[low] = R[0]; return low; }// Partition void QSort (RedType & R[], int s, int t ) { // 对记录序列R[s..t]进行快速排序 if (s < t) { // 长度大于1 pivotloc = Partition(R, s, t); // 对 R[s..t] 进行一次划分 QSort(R, s, pivotloc-1); QSort(R, pivotloc+1, t); } } // QSort (5)简单选择排序的算法描述如下: void SelectSort (Elem R[], int n ) { // 对记录序列R[1..n]作简单选择排序。 for (i=1; i<n; ++i) { // 选择第 i 小的记录,并交换到位 j = SelectMinKey(R, i); // 在 R[i..n] 中选择关键字最小的记录 if (i!=j) R[i]←→R[j]; // 与第 i 个记录交换 } } // SelectSort (6)堆排序算法描述如下: void HeapSort ( HeapType &H ) { // 对顺序表 H 进行堆排序 for ( i=H.length/2; i>0; --i ) HeapAdjust ( H.r, i, H.length ); // 建大顶堆 for ( i=H.length; i>1; --i ) { H.r[1]←→H.r[i]; HeapAdjust(H.r, 1, i-1); // 对 H.r[1] 进行筛选 } } // HeapSort void HeapAdjust (RcdType &R[], int s, int m) { rc = R[s]; // 暂存 R[s] for ( j=2*s; j<=m; j*=2 ) { // j 初值指向左孩子 if ( j<m && R[j].key<R[j+1].key ) ++j; if ( rc.key >= R[j].key ) break; R[s] = R[j]; s = j; } R[s] = rc; } // HeapAdjust (7)归并排序算法描述如下: void Msort ( RcdType SR[], RcdType &TR1[], int s, int t ) { // 将SR[s..t] 归并排序为 TR1[s..t] if (s= =t) TR1[s]=SR[s]; else { m = (s+t)/2; Msort (SR, TR2, s, m); // 递归地将SR[s..m]归并为有序的TR2[s..m] Msort (SR, TR2, m+1, t); Merge (TR2, TR1, s, m, t); } } // Msort 3、如果上述8个整数按照升序输入,即k1={ 2 , 12 , 12 , 21 , 30 , 33 , 45 , 68 },输出各种排序算法每一趟排序的结果,观察关键字次序的变化。 4、如果上述8个整数按照降序输入,即k2={ 68 , 45 , 33 , 30 , 21 , 12 , 12 , 2},输出各种排序算法每一趟排序的结果,观察关键字次序的变化。 5、随机产生3万个数,对其进行排序,观察其结果,并测试各排序算法的执行时间,比较执行效率。 五、问题讨论 1、直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序中哪些是稳定的排序方法,哪些是不稳定的? 2、直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序中哪些排序方法比较次数与初始序列有关,那些无关? 3、在初始序列基本有序的前提条件下,哪种排序方法效率最高? 六、实验报告内容 1、实验目的 2、实验内容和具体要求 3、完成情况和实验记录,实验记录为实验过程中遇到的问题及解决方法 4、程序清单 5、所输入的数据及相应的运行结果 6、问题回答 7、实验心得

数据结构 算法 c语言 二叉排序树

RT ![CSDN移动问答][1] ![CSDN移动问答][2] [1]: http://xiangce.baidu.com/picture/detail/52f17c306a64dafeb7d5c9ed8d1747dfe6d32eb2 [2]: http://xiangce.baidu.com/picture/detail/768a1a97282ecbab4fbad883d5f3008601d609b3 注意关键字X所代表的含义

数据结构直接插入排序

直接插入排序时间复杂度如何算?可分为正序和倒序两种情况?需要计算过程和思路,

数据结构顺序表查找操作

``` Status LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)) { ElemType *p; int i=1; p = L.elem ; while(i<=L.length &&!compare(*p++,e)) ++i; if(i<=L.length) return i; else return Error; } ``` ``` Status(*compare)(ElemType,ElemType) ``` 这个是什么意思,要执行这个子函数要怎么传值?

在查找方面二叉排序树效率与顺序查找的效率谁高(这里一般二叉排序树 不是指平衡二叉树)

写二叉排序树 ,它的作用是查找,过程是 一个值一个值插入创建二叉树,这样就顺带排序了,然后查找,,,可是为什么不直接在插入时候每一个节点和key.value比较一下呢,,,创建完二叉树还要递归查找多麻烦,那样的话似乎和直接用线性表顺序查找 有个p区别。。。 **顺序查找的时间复杂度是O(n),创建二叉排序树的时间复杂度是O(nlog2n),然后二叉排序树查找是O(log2n)** **O(nlog2n)+O(log2n) 怎么看都比O(n)大的样子啊。**

10W级数据频繁查询修改与排序问题,如何提高效率

现有10w级的数据量,需求频繁的查询,频繁排序,该如何设计好的数据结构?因为数据变化频繁,初步考虑用map映射表索引查询,修改数据,但是修改之后数据又要根据一定的规则重新排序,显然map又不适用。如果采用vector容器可以解决排序,但查询修改数据的效率太过低下了,现在纠结该如何提高效率?用list不知道如何?大概的数据结构如下:由于学艺不清,在此请教各位前辈。 struct { int index; std::string name; //........... }

求解一道数据结构题,实现归并排序和基数排序

MySort.h /** * 归并排序,要求对arr进行归并排序,数组长度为len @name mergeSort(int*, int); @param arg1 需要排序对数组 @param arg2 数组的长度 @return */ void mergeSort(int* arr, int len); /** * 基数排序,要求对arr进行基数排序,数组长度为len @name cardSort(int*, int); @param arg1 需要排序对数组 @param arg2 数组的长度 @return */ void cardSort(int* arr, int len); MySort.cpp #include "MySort.h" void mergeSort(int *arr, int len){ } void cardSort(int* arr, int len){ } main.cpp #include <iostream> #include <cstdio> #include <ctime> #include <cstdlib> #include "MySort.h" void shuffle(int* arr, int len){ srand(time(0)); for(int i = 0; i < len; i++){ int randn = rand() % len; std::swap(arr[i], arr[randn]); } } int main() { int i; int len = 100; int res[100] = {0}; int arr[100] = {0}; for(int i = 1; i < len; i++){ arr[i] = arr[i - 1] + rand() % 100; res[i] = arr[i]; } shuffle(arr, len); mergeSort(arr, len); for(i = 0; i < len; i++){ if(arr[i] != res[i]) break; } if(i == len) printf("Pass check point 1!"); shuffle(arr, len); cardSort(arr, len); for(i = 0; i < len; i++){ if(arr[i] != res[i]) break; } if(i == len) printf("Pass check point 2!"); return 0; }

求解数据结构课程设计问题

学生成绩管理系统 设计目的: 1 掌握线性链表的建立。 2 掌握线性链表的基本操作。 3 掌握查找的基本算法。 设计内容:   利用线性链表实现学生成绩管理系统,具体功能:输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出,并能在屏幕上输出操作前后的结果。 设计要求: 1 写出系统需求分析,并建模。 2 编程实现,界面友好。 3 输出操作前后的结果。

平衡二叉树的操作 数据结构课程设计

山东建筑大学计算机学院 数据结构课程设计任务书 设计题目 二叉树操作的演示 指导教师 汤晓兵 班 级 计本03 学 生 已知技术参数和设计要求 [问题描述] 利用平衡二叉树实现一个动态查找表。 [基本要求] 实现动态查找表的三种基本功能:查找、插入和删除。 设计内容与步骤 [实现提示] 主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性,如,正序、逆序和不同程度的乱序。注意采用分块调试的方法。 设计工作计划与进度安排 1、课程设计按照教学要求需要两周时间完成, 2、两周中每天(按每周5天)至少要上机6小时来调试程序。 3、总共至少要上机调试程序60小时。 设计考核要求 1、考勤20% 2、课程设计说明书50%。 3、答辩30% 计算机科学与技术学院制

查找二叉树BST的简单实现问题

问题描述 利用二叉查找树(BST)实现一个动态查找表。 基本要求 使用二叉树(BST)来实现。 二叉树使用链式结构(二叉链表)实现。 实现BST的构建,查找两个功能。 实现提示 输入: 8//BST的节点个数 34, 76, 45, 18, 26, 54, 92, 65 //8个数据 45//查找 45 输出:查找成功 3 //返回成功和查找时比较的次数 34//查找 34 输出:查找成功 1 //返回成功和查找时比较的次数 100//查找 100 输出:查找不成功 3 //返回成功和查找时比较的次数 选作内容 实现二叉树(BST)的插入和删除功能。 查找不成功时,被查找的数据插入到BST中。 求各位大神帮忙写写代码

[C++数据结构]自己按书中代码打了一个二叉查找树模板类,发现不能在树上正常插入元素

以下代码分为一个头文件和一个.cpp文件,可复制粘贴直接运行,头文件记得命名为BST.h 我的运行环境是vs2017,编译没有出错,插入函数也是照书中代码一点点打的,保证没有抄错。但是无法正常插入,麻烦大佬们花两分钟帮忙看看,是不是代码的错,在下C++才学一年,希望能大家能多指教,非常感谢! 代码出自《数据结构与算法分析 C++语言描述 第2版》Larry Nyhoff著 清华大学出版社 第600页 ``` /* 头文件名字如下: BST.h 这是一个二叉查找树模板类,我只定义了元素插入二叉树的函数 代码出自《数据结构与算法分析 C++语言描述 第2版》Larry Nyhoff著 第600页 保证没有抄错,大佬们可以直接复制粘贴到编译器中执行 后面有测试的test.cpp文件,也可以直接复制粘贴 */ #include <iostream> #include <new>//我不知道该头文件的用处,书上是这么写的 using namespace std; #ifndef BINARY_SEARCH_TREE_H #define BINARY_SEARCH_TREE_H template <typename DataType> class BinarySearchTree { private: /*节点类*/ class BinNode { public: DataType data; BinNode * left; BinNode * right; BinNode() :left(0),right(0){} BinNode(DataType item) :data(item), left(0), right(0) {} };//节点类声明结束 typedef BinNode * BinNodePointer;//用BinNodePointe来代替BinNode * //类成员 BinNode * myRoot; public: BinarySearchTree();//构造 void insert(const DataType & item)const;//插入 private: void insertAux(BinNodePointer subtreeRoot, const DataType & item)const;//插入辅助函数 };//模板类声明结束 //以下是函数定义 //构造 template <typename DataType> inline BinarySearchTree<DataType>::BinarySearchTree():myRoot(0){} //插入 template<typename DataType> inline void BinarySearchTree<DataType>::insert(const DataType & item) const { insertAux(myRoot, item); } //插入辅助函数定义,用了递归 template<typename DataType> void BinarySearchTree<DataType>::insertAux( BinarySearchTree<DataType>::BinNodePointer subtreeRoot, const DataType & item) const { if (subtreeRoot == 0){ subtreeRoot = new BinarySearchTree<DataType>::BinNode(item); cout<<"xxx\n";//之后用for循环测试是否插入成功,如果成功只显示一次,失败显示n次。 } else if (item < subtreeRoot->data)//左子树 insertAux(subtreeRoot->left, item); else if (subtreeRoot->data)//右子树 insertAux(subtreeRoot->right, item); else cerr << "Item already in the tree\n"; } #endif ``` 下面是测试用的main函数 ``` #include <iostream> #include "BST.h" using namespace std; int main() { BinarySearchTree<int> bst; //测试插入函数 int number; for (number=0;;) { number++; if (number == 999)break; bst.insert(number); }//如果一直是空树的话会不断的输出"xxx" return 0; } ```

数据结构单链表的插入与删除

设单链表某一节点为p,怎样在p节点前插入一个结点?怎样删除p节点自身?(要求:用Java语言写出具体程序语言)

数据结构课程设计用C语言做

据结构课程设计。包含word,或txt文档阅读。 读的“内容”,请保存到任意一门课上所讲的表中。可以是sqlist,LinkList,sqstack,queue等要求能用逗号句号分行显示并且输入1 2 3 4 可以对应显示每行的内容

关于通讯录,数据结构的一道习题

编程实现如下功能: (1)构建一个通讯录类型,包含<姓名>、<电话>数据项。 (2)根据输入顺序表的长度n和各个数据元素值建立一个顺序表,并输出顺序表中各元素值,观察输入的内容与输出的内容是否一致。 (3)在顺序表的第i个元素之前插入一个值为x的元素,并输出插入后的顺序表中各元素值。 (4)删除顺序表中第i个元素,并输出删除后的顺序表中各元素值。 (5)在顺序表中查找值为e的数据元素,如果查找成功,则显示“查找成功”和该元素在顺序表中的位置,否则显示“查找失败”。 (6)采用链表实现以上顺序表的相应功能。 老师要求用C语言,然而我们并不会- -

实验是数据结构中做一个学生成绩管理系统,在网上找到了相应代码,但是不知道怎么插入学生信息,希望大佬帮助完成这个课题

#include<stdio.h> #include<stdlib.h> #include<string.h> char top[50]; //成绩文件顶部的标题用top保存 typedef struct student //单个学生成绩的记录 { char name[10]; //姓名 int number; //学号 int chinese; //语文 int math; //数学 int english; //英语 struct student *next; }student,*gradelist; gradelist fileread(char *adress) //读取成绩文件 { FILE * fp; if((fp=fopen(address,"r"))==NULL) //打开文件 { printf("文件打开出错"); exit(0); } gradelist file=(student *)malloc(sizeof(student)); //申请空间 file->next=NULL; student * p=file; //操作指针 int n=0; //循环标记,具体作用是在第一次循环时方便处理标题 while(!feof(fp)) { if(n==0) { fgets(top,50,fp); //处理标题,并且文件指针移到第二行 } if(n==1) //申请空间 { (p->next)=(student *)malloc(sizeof(student)); p=p->next; p->next=NULL; } fscanf(fp,"%s%d%d%d%d",p->name,&p->number,&p->chinese,&p->math,&p->english); //将文件的数据输入到链表中 n=1; } if(fclose(fp)) //关闭文件 { printf("文件关闭失败"); exit(0); } return file; } void FilePrint(gradelist file) //将成绩文件打印到屏幕上 { student *p=file; printf("%s\n",top); //打印标题 while(p->next!=NULL) { printf("%6s %2d %d %d %d\n",p->name,p->number,p->chinese,p->math,p->english); //循环打印 p=p->next; } } void merger() //合并文件 { char * address1="1.txt",*address2="2.txt",*address3="3.txt"; gradelist file1=fileread(address1),file2=fileread(address2); FILE *fp; if((fp=fopen("3.txt","w+"))==NULL) //先新建一个3.txt,然后将1.txt和2.txt的内容输入到里面 { printf("合并成绩文档失败,原因:建立文档出错"); exit(0); } student *p1=file1,*p2=file2; fprintf(fp,"%s",top); //先输入标题 while(p1->next!=NULL) { fprintf(fp,"%6s %2d %d %d %d\n",p1->name,p1->number,p1->chinese,p1->math,p1->english); //输入1.txt p1=p1->next; } while(p2->next!=NULL) { fprintf(fp,"%6s %2d %d %d %d\n",p2->name,p2->number,p2->chinese,p2->math,p2->english); //输入2.txt p2=p2->next; } if(fclose(fp)) { printf("文件关闭失败"); exit(0); } } void extract() //抽取补考的成绩记录 { char * address4="4.txt",*address3="3.txt"; FILE *fp; if((fp=fopen("4.txt","w+"))==NULL) //新建文件4.txt { printf("抽取补考学生成绩记录建立新文件失败"); exit(0); } gradelist file3=fileread(address3); student *p=file3; fprintf(fp,"%s",top); //先输入标题 while(p->next!=NULL) { if((p->chinese)<60||(p->math)<60||(p->english)<60) //补考条件 { fprintf(fp,"%6s %2d %d %d %d\n",p->name,p->number,p->chinese,p->math,p->english); } p=p->next; } if(fclose(fp)) { printf("文件关闭失败"); exit(0); } } void sort(int i) { char * address3="3.txt"; gradelist file3=fileread(address3); //先将3.txt读入链表 student *p=file3; if(remove("3.txt")) //由于排序后的内容也要保存到3.txt,故删除3.txt { printf("删除文件出错"); exit(0); } int n=0; //学生个数 FILE *fp; if((fp=fopen("3.txt","w+"))==NULL) //新建一个空的3.txt { printf("新建文件出错"); exit(0); } fprintf(fp,"%s",top); //标题先输入 while(p->next!=NULL) { n++; p=p->next; } typedef struct //链表不容易操作,故而新建一个结构数组 { int totalgrade; char name[10]; int number; int chinese; int math; int english; }gradenote; //成绩记录 typedef struct { gradenote r[100]; //只初始化了100了空间,学生人数超过100就不能了,懒得动态分配了 }grade_list; //待排序成绩表 grade_list L; p=file3; int t; for(t=1;t<=n;t++,p=p->next) //将链表的内容复制到结构数组里 { strcpy(L.r[t].name,p->name); L.r[t].number=p->number; L.r[t].chinese=p->chinese; L.r[t].math=p->math; L.r[t].english=p->english; L.r[t].totalgrade=p->chinese+p->math+p->english; } if(i==1) //直接插入排序 { int k; for(k=2;k<=n;++k) { if(L.r[k].totalgrade<L.r[k-1].totalgrade) { L.r[0]=L.r[k]; L.r[k]=L.r[k-1]; int j; for(j=k-2;L.r[0].totalgrade<L.r[j].totalgrade;--j) { L.r[j+1]=L.r[j]; } L.r[j+1]=L.r[0]; } } } if(i==2) //折半插入排序 { int m; int k; for(k=2;k<=n;++k) { L.r[0]=L.r[k]; int low=1,high=k-1; while(low<=high) { m=(low+high)/2; if(L.r[0].totalgrade<L.r[m].totalgrade) high=m-1; else low=m+1; } int j; for(j=k-1;j>=high+1;--j) L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0]; } } int q; for(q=n;q>=1;q--) //将排序好的内容输入到3.txt { fprintf(fp,"%6s %2d %d %d %d\n",L.r[q].name,L.r[q].number,L.r[q].chinese,L.r[q].math,L.r[q].english); } if(fclose(fp)) { printf("文件关闭失败"); exit(0); } } void search(char *name) //按姓名查找 { gradelist file=fileread("3.txt"); student * p=file; while(p->next!=NULL) { if(strcmp(name,p->name)==0) { printf("%6s %2d %d %d %d\n",p->name,p->number,p->chinese,p->math,p->english); return; } p=p->next; } printf("查无此人,请确定名字输入正确\n"); exit(0); } void main(void) // { int chioce; gradelist file1=fileread("1.txt"),file2=fileread("2.txt"); printf("现有成绩记录文件1\n"); printf("*********************************************************\n"); FilePrint(file1); printf("*********************************************************\n"); printf("现有成绩记录文件2\n"); printf("*********************************************************\n"); FilePrint(file2); printf("*********************************************************\n"); printf("第一步,合并成绩记录文件\n"); merger(); printf("合并成功\n"); system("PAUSE"); printf("现有合并后的成绩记录文件3\n"); printf("*********************************************************\n"); gradelist file3=fileread("3.txt"); FilePrint(file3); printf("*********************************************************\n"); printf("第二步,抽取补考成绩记录\n"); extract(); system("PAUSE"); printf("现有补考成绩记录文件4\n"); printf("*********************************************************\n"); gradelist file4=fileread("4.txt"); FilePrint(file4); printf("*********************************************************\n"); printf("第三步,对文件3进行排序\n"); printf("请输入排序方式(1/2)\n1:直接插入排序\n2:折半插入排序\n"); scanf("%d",&chioce); if(chioce==1) sort(1); else if(chioce==2) sort(2); else { printf("输入不合理,程序默认采用1方式\n"); sort(1); } file3=fileread("3.txt"); printf("现有按总分降序的成绩记录3\n"); printf("*********************************************************\n"); FilePrint(file3); printf("*********************************************************\n"); printf("第四步,查找学生信息\n"); char name[100]; printf("请输入学生姓名\n"); scanf("%s",name); search(name); printf("按任意键结束程序\n"); getchar(); } 姓名 学号 语文 数学 英语 张明明 01 67 78 82 李成友 02 78 91 88 张辉灿 03 68 82 56 王露 04 56 45 77 陈东明 05 67 38 47 姓名 学号 语文 数学 英语 陈果 31 57 68 82 李华明 32 88 90 68 张明东 33 48 42 56 李明国 34 50 45 87 陈道亮 35 47 58 77

数据结构 算法 插入问题

有没有大神知道p前面插入s的4条语句怎么写?谢谢……………………![图片说明](https://img-ask.csdn.net/upload/201703/22/1490165098_370385.png)

题目:学生顺序表的处理

在一个数据文件中存放若干学生数据记录,每条记录都有如下数据项:学号,姓名,性别,成绩。 编一个程序,采用 顺序存储结构 存储这批数据,并对该数据进行排序。要求:数组前部为男同学,后部为女同学,并且男女同学都按成绩递减排序,分别计算男生合格率、女生合格率、全班的成绩平均分,并把排序后的学生数据记录及计算结果存入另一个数据文件中。

C语言数据结构的模拟银行存钱取钱的算法,采用C语言程序的编写

Problem Description Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The idea behind is simple. Whenever some ACM member has any small money, he takes all the coins and throws them into a piggy-bank. You know that this process is irreversible, the coins cannot be removed without breaking the pig. After a sufficiently long time, there should be enough cash in the piggy-bank to pay everything that needs to be paid. But there is a big problem with piggy-banks. It is not possible to determine how much money is inside. So we might break the pig into pieces only to find out that there is not enough money. Clearly, we want to avoid this unpleasant situation. The only possibility is to weigh the piggy-bank and try to guess how many coins are inside. Assume that we are able to determine the weight of the pig exactly and that we know the weights of all coins of a given currency. Then there is some minimum amount of money in the piggy-bank that we can guarantee. Your task is to find out this worst case and determine the minimum amount of cash inside the piggy-bank. We need your help. No more prematurely broken pigs! Input The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing two integers E and F. They indicate the weight of an empty pig and of the pig filled with coins. Both weights are given in grams. No pig will weigh more than 10 kg, that means 1 <= E <= F <= 10000. On the second line of each test case, there is an integer number N (1 <= N <= 500) that gives the number of various coins used in the given currency. Following this are exactly N lines, each specifying one coin type. These lines contain two integers each, Pand W (1 <= P <= 50000, 1 <= W <=10000). P is the value of the coin in monetary units, W is it's weight in grams. Output Print exactly one line of output for each test case. The line must contain the sentence "The minimum amount of money in the piggy-bank is X." where X is the minimum amount of money that can be achieved using coins with the given total weight. If the weight cannot be reached exactly, print a line "This is impossible.". Sample Input 3 10 110 2 1 1 30 50 10 110 2 1 1 50 30 1 6 2 10 3 20 4 Sample Output The minimum amount of money in the piggy-bank is 60. The minimum amount of money in the piggy-bank is 100. This is impossible.

二叉查找树 删除结点

/*包含头文件*/ #include "stdio.h" #include "stdlib.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 typedef int Status; /* 二叉树的二叉链表结点结构定义 */ typedef struct BiTNode /* 结点结构 */ { int data; /* 结点数据 */ struct BiTNode *lchild, *rchild; /* 左右孩子指针 */ } BiTNode, *BiTree; /**BiTree等价于typedef BiTNode *BiTree*/ /*查找二叉排序树T中是否存在key(递归查找)*/ Status Search(BiTree T, int key, BiTree f, BiTree *p) { if (!T) /* 查找不成功 */ { *p = f; return FALSE; } else if (key==T->data) /* 查找成功 */ { *p = T; return TRUE; } else if (key<T->data) return Search(T->lchild, key, T, p); /* 在左子树中继续查找 */ else return Search(T->rchild, key, T, p); /* 在右子树中继续查找 */ } /* 当二叉排序树T中不存在关键字等于key的数据元素时, */ /* 插入key并返回TRUE,否则返回FALSE */ Status Insert(BiTree *T, int key) { BiTree p,s; if (!Search(*T, key, NULL, &p)) /* 查找不成功 */ { s = (BiTree)malloc(sizeof(BiTNode)); s->data = key; s->lchild = s->rchild = NULL; if (!p) *T = s; /* 插入s为新的根结点 */ else if (key<p->data) p->lchild = s; /* 插入s为左孩子 */ else p->rchild = s; /* 插入s为右孩子 */ return TRUE; } else return FALSE; /* 树中已有关键字相同的结点,不再插入 */ } /* 从二叉排序树中删除结点p,并重接它的左或右子树。 */ Status DeleteBST(BiTree &p) { BiTree q,s; if(p->rchild==NULL) /* 右子树空则只需重接它的左子树(待删结点是叶子也走此分支) */ { **_ q=p; p=p->lchild; free(q);_** } else if(p->lchild==NULL) /* 只需重接它的右子树 */ { _** q=p; p=p->rchild; free(q);**_ } else /* 左右子树均不空 */ { q=p; s=p->lchild; while(s->rchild) /* 转左,然后向右到尽头(找待删结点的前驱) */ { q=s; s=s->rchild; } p->data=s->data; /* s指向被删结点的直接前驱(将被删结点前驱的值取代被删结点的值) */ if(q!=p) q->rchild=s->lchild; /* 重接q的右子树 */ else q->lchild=s->lchild; /* 重接q的左子树 */ free(s); } return TRUE; } /* 若二叉排序树T中存在关键字等于key的数据元素时,则删除该数据元素结点, */ /* 并返回TRUE;否则返回FALSE。 */ Status Delete(BiTree &T,int key) { if(!T) /* 不存在关键字等于key的数据元素 */ return FALSE; else { if (key==T->data) /* 找到关键字等于key的数据元素 */ return DeleteBST(T); else if (key<T->data) return Delete(T->lchild,key); else return Delete(T->rchild,key); } } /*二叉树中序遍历*/ void LDR(BiTree T) { if (T!=NULL) { LDR(T->lchild); printf("%d ",T->data); LDR(T->rchild); } } #define N 10 void main() { int i,j; BiTree T=NULL; //定义数组和初始化SeqList int d[N]={62,88,58,47,35,73,51,99,37,93}; for (i=0;i<N;i++) { Insert(&T,d[i]); } printf("***************二叉排序树查找(C版)***************\n"); printf("初始化二叉排序树\n中序遍历数据:"); LDR(T); printf("\n***************删除节点1***************\n"); Delete(T,93); printf("删除叶节点93\n中序遍历后:"); LDR(T); printf("\n***************删除节点2***************\n"); Delete(T,47); printf("删除双孩子节点47\n中序遍历后:"); LDR(T); printf("\n***************删除节点3***************\n"); Delete(T,58); printf("删除单孩子节点58\n中序遍历后:"); LDR(T); getchar(); } 删除结点的部分 if(p->rchild==NULL) /* 右子树空则只需重接它的左子树(待删结点是叶子也走此分支) */ { q=p; p=p->lchild; free(q); } else if(p->lchild==NULL) /* 只需重接它的右子树 */ { q=p; p=p->rchild; free(q); } 要删除p指向的结点,那么应该把p->lchild或p->rchild赋给p指向结点的双亲啊,为什么要给p呢?

如果能重来,我不会选择北漂——初见北京

一个人走的路

技术大佬:我去,你写的 switch 语句也太老土了吧

昨天早上通过远程的方式 review 了两名新来同事的代码,大部分代码都写得很漂亮,严谨的同时注释也很到位,这令我非常满意。但当我看到他们当中有一个人写的 switch 语句时,还是忍不住破口大骂:“我擦,小王,你丫写的 switch 语句也太老土了吧!” 来看看小王写的代码吧,看完不要骂我装逼啊。 private static String createPlayer(PlayerTypes p...

副业收入是我做程序媛的3倍,工作外的B面人生是怎样的?

提到“程序员”,多数人脑海里首先想到的大约是:为人木讷、薪水超高、工作枯燥…… 然而,当离开工作岗位,撕去层层标签,脱下“程序员”这身外套,有的人生动又有趣,马上展现出了完全不同的A/B面人生! 不论是简单的爱好,还是正经的副业,他们都干得同样出色。偶尔,还能和程序员的特质结合,产生奇妙的“化学反应”。 @Charlotte:平日素颜示人,周末美妆博主 大家都以为程序媛也个个不修边幅,但我们也许...

我说我不会算法,阿里把我挂了。

不说了,字节跳动也反手把我挂了。

2020年大厂Java面试前复习的正确姿势(800+面试题答案解析)

前言 个人觉得面试也像是一场全新的征程,失败和胜利都是平常之事。所以,劝各位不要因为面试失败而灰心、 丧失斗志。也不要因为面试通过而沾沾自喜,等待你的将是更美好的未来,继续加油! 本篇分享的面试题内容包括:Java、MyBatis、ZooKeeper、Dubbo、Elasticsearch、Redis、MySQL、Spring、SpringBoot、SpringCloud、RabbitMQ...

抖音上很火的时钟效果

反正,我的抖音没人看,别人都有几十万个赞什么的。 发到CSDN上来,大家交流下~ 主要用到原生态的 JS+CSS3。 具体不解释了,看注释: &lt;!DOCTYPE html&gt; &lt;html lang="en"&gt; &lt;head&gt; &lt;meta charset="UTF-8"&gt; &lt;title&gt;Title&lt;/tit...

记录下入职中软一个月(外包华为)

我在年前从上一家公司离职,没想到过年期间疫情爆发,我也被困在家里,在家呆着的日子让人很焦躁,于是我疯狂的投简历,看面试题,希望可以进大公司去看看。 我也有幸面试了我觉得还挺大的公司的(虽然不是bat之类的大厂,但是作为一名二本计算机专业刚毕业的大学生bat那些大厂我连投简历的勇气都没有),最后选择了中软,我知道这是一家外包公司,待遇各方面甚至不如我的上一家公司,但是对我而言这可是外包华为,能...

又出事了?网站被攻击了?高中生?

北京时间2020年3月27日9点整,如往常一样来到公司,带开电脑,正准备打开Github网站看一会源代码,再开始手头的工作。哟吼,一直打不开,一直出现如下页面: 我想很多网友也尝到了甜头,各大技术群炸开了锅,据网友反馈有攻击者正在发起大规模的中间人挟持,京东和Github等网站等网站都受到了影响。 什么是中间中间人挟持呢? 简而言之,就是攻击者在数据网络传输的过程中,截获传输过程中的数据并篡改...

培训班出来的人后来都怎么样了?(二)

接着上回说,培训班学习生涯结束了。后面每天就是无休止的背面试题,不是没有头脑的背,培训公司还是有方法的,现在回想当时背的面试题好像都用上了,也被问到了。回头找找面试题,当时都是打印下来天天看,天天背。 不理解呢也要背,面试造飞机,上班拧螺丝。班里的同学开始四处投简历面试了,很快就有面试成功的,刚开始一个,然后越来越多。不知道是什么原因,尝到胜利果实的童鞋,不满足于自己通过的公司,嫌薪水要少了,选择...

面试了一个 31 岁程序员,让我有所触动,30岁以上的程序员该何去何从?

最近面试了一个31岁8年经验的程序猿,让我有点感慨,大龄程序猿该何去何从。

大三实习生,字节跳动面经分享,已拿Offer

说实话,自己的算法,我一个不会,太难了吧

程序员垃圾简历长什么样?

已经连续五年参加大厂校招、社招的技术面试工作,简历看的不下于万份 这篇文章会用实例告诉你,什么是差的程序员简历! 疫情快要结束了,各个公司也都开始春招了,作为即将红遍大江南北的新晋UP主,那当然要为小伙伴们做点事(手动狗头)。 就在公众号里公开征简历,义务帮大家看,并一一点评。《启舰:春招在即,义务帮大家看看简历吧》 一石激起千层浪,三天收到两百多封简历。 花光了两个星期的所有空闲时...

工作八年,月薪60K,裸辞两个月,投简历投到怀疑人生!

近日,有网友在某职场社交平台吐槽,自己裸辞两个月了,但是找工作却让自己的心态都要崩溃了,全部无果,不是已查看无回音,就是已查看不符合。 “工作八年,两年一跳,裸辞两个月了,之前月薪60K,最近找工作找的心态崩了!所有招聘工具都用了,全部无果,不是已查看无回音,就是已查看不符合。进头条,滴滴之类的大厂很难吗???!!!投简历投的开始怀疑人生了!希望 可以收到大厂offer” 先来看看网...

我把华为小米年报放一起,发现华为才是真·手机公司,小米确实不靠卖手机赚钱...

郭一璞 发自 凹非寺量子位 报道 | 公众号 QbitAI国产手机界的两大玩家,华为&amp;小米,昨天在同一天前后脚发布了2019年财报。同行冤家,发财报也碰在了同一天。那我们就对比...

大牛都会用的IDEA调试技巧!!!

导读 前天面试了一个985高校的实习生,问了他平时用什么开发工具,他想也没想的说IDEA,于是我抛砖引玉的问了一下IDEA的调试用过吧,你说说怎么设置断点...

97年世界黑客编程大赛冠军作品(大小仅为16KB),惊艳世界的编程巨作

这是世界编程大赛第一名作品(97年Mekka ’97 4K Intro比赛)汇编语言所写。 整个文件只有4095个字节, 大小仅仅为16KB! 不仅实现了3D动画的效果!还有一段震撼人心的背景音乐!!! 内容无法以言语形容,实在太强大! 下面是代码,具体操作看最后! @echo off more +1 %~s0|debug e100 33 f6 bf 0 20 b5 10 f3 a5...

不要再到处使用 === 了

我们知道现在的开发人员都使用 === 来代替 ==,为什么呢?我在网上看到的大多数教程都认为,要预测 JavaScript 强制转换是如何工作这太复杂了,因此建议总是使用===。这些都...

什么是a站、b站、c站、d站、e站、f站、g站、h站、i站、j站、k站、l站、m站、n站?00后的世界我不懂!

A站 AcFun弹幕视频网,简称“A站”,成立于2007年6月,取意于Anime Comic Fun,是中国大陆第一家弹幕视频网站。A站以视频为载体,逐步发展出基于原生内容二次创作的完整生态,拥有高质量互动弹幕,是中国弹幕文化的发源地;拥有大量超粘性的用户群体,产生输出了金坷垃、鬼畜全明星、我的滑板鞋、小苹果等大量网络流行文化,也是中国二次元文化的发源地。 B站 全称“哔哩哔哩(bilibili...

十个摸鱼,哦,不对,是炫酷(可以玩一整天)的网站!!!

文章目录前言正文**1、Kaspersky Cyberthreat real-time map****2、Finding Home****3、Silk – Interactive Generative Art****4、Liquid Particles 3D****5、WINDOWS93****6、Staggering Beauty****7、Ostagram图片生成器网址****8、全历史网址*...

终于,月薪过5万了!

来看几个问题想不想月薪超过5万?想不想进入公司架构组?想不想成为项目组的负责人?想不想成为spring的高手,超越99%的对手?那么本文内容是你必须要掌握的。本文主要详解bean的生命...

毕业5年,我熬夜整理出了这50个优质的电子书网站,吐血推荐!

大家好,我是武哥,最近经常有小伙伴问我要电子书,都什么年代了,还找不到电子书吗?如果要说原因,那就是你还没遇到武哥我(手动滑稽~)!我今天把这么多年我经常看的电子书网站整理一下给大家,基本上能解决大家的需求。不管是在校生还是已经工作了,相信肯定对你有所帮助! 1.鸠摩搜书 首先给大家推荐的网站是:鸠摩搜书 地址:https://www.jiumodiary.com/ 这个网上非常棒,上面有很多优质...

MySQL性能优化(五):为什么查询速度这么慢

前期回顾: MySQL性能优化(一):MySQL架构与核心问题 MySQL性能优化(二):选择优化的数据类型 MySQL性能优化(三):深入理解索引的这点事 MySQL性能优化(四):如何高效正确的使用索引 前面章节我们介绍了如何选择优化的数据类型、如何高效的使用索引,这些对于高性能的MySQL来说是必不可少的。但这些还完全不够,还需要合理的设计查询。如果查询写的很糟糕,即使表结构再合理、索引再...

大厂的 404 页面都长啥样?最后一个笑了...

每天浏览各大网站,难免会碰到404页面啊。你注意过404页面么?猿妹搜罗来了下面这些知名网站的404页面,以供大家欣赏,看看哪个网站更有创意: 正在上传…重新上传取消 腾讯 正在上传…重新上传取消 网易 淘宝 百度 新浪微博 正在上传…重新上传取消 新浪 京东 优酷 腾讯视频 搜...

自从喜欢上了B站这12个UP主,我越来越觉得自己是个废柴了!

不怕告诉你,我自从喜欢上了这12个UP主,哔哩哔哩成为了我手机上最耗电的软件,几乎每天都会看,可是吧,看的越多,我就越觉得自己是个废柴,唉,老天不公啊,不信你看看…… 间接性踌躇满志,持续性混吃等死,都是因为你们……但是,自己的学习力在慢慢变强,这是不容忽视的,推荐给你们! 都说B站是个宝,可是有人不会挖啊,没事,今天咱挖好的送你一箩筐,首先啊,我在B站上最喜欢看这个家伙的视频了,为啥 ,咱撇...

代码注释如此沙雕,会玩还是你们程序员!

某站后端代码被“开源”,同时刷遍全网的,还有代码里的那些神注释。 我们这才知道,原来程序员个个都是段子手;这么多年来,我们也走过了他们的无数套路… 首先,产品经理,是永远永远吐槽不完的!网友的评论也非常扎心,说看这些代码就像在阅读程序员的日记,每一页都写满了对产品经理的恨。 然后,也要发出直击灵魂的质问:你是尊贵的付费大会员吗? 这不禁让人想起之前某音乐app的穷逼Vip,果然,穷逼在哪里都是...

总结了Mybatis,原来知识点也没多少嘛

看完这篇Mybatis,感觉你三天就会用了。

爬虫(101)爬点重口味的

小弟最近在学校无聊的很哪,浏览网页突然看到一张图片,都快流鼻血。。。然后小弟冥思苦想,得干一点有趣的事情python 爬虫库安装https://s.taobao.com/api?_ks...

疫情后北上广深租房价格跌了吗? | Alfred数据室

去年3月份我们发布了《北上广深租房图鉴》(点击阅读),细数了北上广深租房的各种因素对租房价格的影响。一年过去了,在面临新冠疫情的后续影响、城市尚未完全恢复正常运转、学校还没开学等情况下...

面试官给我挖坑:a[i][j] 和 a[j][i] 有什么区别?

点击上方“朱小厮的博客”,选择“设为星标”后台回复&#34;1024&#34;领取公众号专属资料本文以一个简单的程序开头——数组赋值:int LEN = 10000; int[][] ...

在拼多多上班,是一种什么样的体验?我心态崩了呀!

之前有很多读者咨询我:武哥,在拼多多上班是一种什么样的体验?由于一直很忙,没抽出时间来和大家分享。上周末特地花点时间来写了一篇文章,跟大家分享一下拼多多的日常。 1. 倒时差的作息 可能很多小伙伴都听说了,拼多多加班很严重。这怎么说呢?作息上确实和其他公司有点区别,大家知道 996,那么自然也就能理解拼多多的“11 11 6”了。 所以当很多小伙伴早上出门时,他们是这样的: 我们是这样的: 当...

相关热词 c# cad插入影像 c#设计思想 c#正则表达式 转换 c#form复制 c#写web c# 柱形图 c# wcf 服务库 c#应用程序管理器 c#数组如何赋值给数组 c#序列化应用目的博客园
立即提问