(完整版)C语言数据结构快速排序源码

快速排序算法c语言实验报告冒泡法和选择法排序C程序实验报告实验六：冒泡法排序物理学416班赵增月F12 2011412194日期：2013年10月31日一·实验目的 1.熟练掌握程序编写步骤；2.学习使用冒泡法和选择法排序；3.熟练掌握数组的定义和输入输出方法。

二·实验器材1.电子计算机；2.VC6.0三·实验内容与流程1.流程图（1）冒泡法(2)选择法 2.输入程序如下：（1）冒泡法#includestdio.h void main() { int a[10]; int i,j,t; printf(请输入10个数字：\n); for(i=0;i10;i++)scanf(%d,&a[i]); printf(\n); for(j=0;j9;j++)for(i=0;i9-j;i++) if(a[i]a[i+1]) { t=a[i]; a[i]=a[i+1]; a[i+1]=t; } printf(排序后如下：\n); for(i=0;i10;i++) printf(%d,a[i]); printf(\n); }（2）选择法#includestdio.h void main() { int a[10]; int i,j,t,k; printf(请输入10个数字：\n); for(i=0;i10;i++)scanf(%d,&a[i]);printf(\n); for(i=0;i9;i++) {k=i;for(j=i+1;j10;j++) if (a[k]a[j])k=j;t=a[i];a[i]=a[k];a[k]=t; }printf(排序后如下：\n); for(i=0;i10;i++)printf(%d,a[i]); printf(\n); }四．输出结果（1冒泡法）请输入10个数字：135****2468排序后如下：12345678910 （2）选择法输出结果请输入10个数字：135****6810排序后如下：12345678910五．实验反思与总结1.冒泡法和选择法是一种数组排序的方法，包含两层循环，写循环时，要注意循环变量的变化范围。

C语⾔⼋⼤排序算法C语⾔⼋⼤排序算法，附动图和详细代码解释！来源：C语⾔与程序设计、⽵⾬听闲等⼀前⾔如果说各种编程语⾔是程序员的招式，那么数据结构和算法就相当于程序员的内功。

想写出精炼、优秀的代码，不通过不断的锤炼，是很难做到的。

⼆⼋⼤排序算法排序算法作为数据结构的重要部分，系统地学习⼀下是很有必要的。

1、排序的概念排序是计算机内经常进⾏的⼀种操作，其⽬的是将⼀组“⽆序”的记录序列调整为“有序”的记录序列。

排序分为内部排序和外部排序。

若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。

反之，若参加排序的记录数量很⼤，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。

2、排序分类⼋⼤排序算法均属于内部排序。

如果按照策略来分类，⼤致可分为：交换排序、插⼊排序、选择排序、归并排序和基数排序。

如下图所⽰：3、算法分析1.插⼊排序*直接插⼊排序*希尔排序2.选择排序*简单选择排序*堆排序3.交换排序*冒泡排序*快速排序4.归并排序5.基数排序不稳定排序：简单选择排序，快速排序，希尔排序，堆排序稳定排序：冒泡排序，直接插⼊排序，归并排序，奇数排序1、插⼊排序将第⼀个和第⼆个元素排好序，然后将第3个元素插⼊到已经排好序的元素中，依次类推（插⼊排序最好的情况就是数组已经有序了）因为插⼊排序每次只能操作⼀个元素，效率低。

元素个数N，取奇数k=N/2，将下标差值为k的数分为⼀组（⼀组元素个数看总元素个数决定），在组内构成有序序列，再取k=k/2，将下标差值为k的数分为⼀组，构成有序序列，直到k=1，然后再进⾏直接插⼊排序。

3、简单选择排序选出最⼩的数和第⼀个数交换，再在剩余的数中⼜选择最⼩的和第⼆个数交换，依次类推4、堆排序以升序排序为例，利⽤⼩根堆的性质（堆顶元素最⼩）不断输出最⼩元素，直到堆中没有元素1.构建⼩根堆2.输出堆顶元素3.将堆低元素放⼀个到堆顶，再重新构造成⼩根堆，再输出堆顶元素，以此类推5、冒泡排序改进1：如果某次冒泡不存在数据交换，则说明已经排序好了，可以直接退出排序改进2：头尾进⾏冒泡，每次把最⼤的沉底，最⼩的浮上去，两边往中间靠16、快速排序选择⼀个基准元素，⽐基准元素⼩的放基准元素的前⾯，⽐基准元素⼤的放基准元素的后⾯，这种动作叫分区，每次分区都把⼀个数列分成了两部分，每次分区都使得⼀个数字有序，然后将基准元素前⾯部分和后⾯部分继续分区，⼀直分区直到分区的区间中只有⼀个元素的时候，⼀个元素的序列肯定是有序的嘛，所以最后⼀个升序的序列就完成啦。

算法与数据结构课程设计报告设计题目：专业班级学生学号指导教师2014年第1学期第一部分：需求分析1、系统名称：航空客运订票系统航空客运订票的业务活动包括：查询航线、客票预定和办理退票等。

要求在TC或VC环境下设计一个航空客运订票系统，以使上述业务可以借助计算机来完成。

2、要求：(1)每条航线所涉及的信息有：终点站名、航班号、飞机号、飞行日期(星期几)、乘员定额、余票量、已经订票的客户名单(包括姓名、订票量)以及等候替补的客户名单(包括姓名、所需票量)。

(2)作为模拟系统，全部数据可以只存放在内存中。

(3)通过此系统可以实现如下功能：①录入功能：可以录入航班情况②查询功能：根据客户提供的终点站名进行查询，可以输出以下信息：航班号、飞机号、星期几飞行和余票量等。

也可以根据航班号，查询飞机某个航线的情况。

③订票功能：根据客户提出的要求(姓名、终点站名、订票数量)查询该航班的余票量情况。

如尚有足够的余票，则为客户办理订票手续；若已满员或余票量少于订票数量，则需要重新询问客户要求，如需要，可登记排队候补。

④退票功能：根据客户提供的情况(姓名、日期、航班号)，为客户办理退票手续，然后查询该航班是否有人排队候补，若有人排队，则为排在第一位的客户办理订票手续。

第二部分：系统设计图样一：设计说明1：添加航班：整个航班的信息保存在一个结构体flight中，采用结构体数组，每一个航班信息包含航班号、起飞时间、起飞城市、降落时间、降落城市、余票数量。

航班信息通过lulu（）函数进行添加。

添加的信息保存在航班flight结构体数组中。

2：查询航班：查询板块分为两个部分，按姓名查找和按站名查找。

按姓名查找：通过所输入的姓名和已定客户的姓名相匹配，匹配成功则查找成功。

按站名查找：通过所输入的起始站名和终点站名进行匹配，匹配成功则查找成功。

3：订票功能：根据用户的姓名和航班号进行订票，如果所查找的航班号的余票满足用户需要的票数，则订票成功，该信息保存在Customer中，才用结构体数组，包含已定客户的姓名、客户ID、订的票数、起飞时间、起飞城市、降落时间、降落城市、航班号。

递归算法#include<iostream>using namespace std;#define MAX 100int Partition(int R[],int s, int t){int i=s,j=t;int pivot,tmp1,tmp2; //pivot作为基准值if(s<t){pivot=R[s];while(i!=j) //从区间两端交替向中间扫描，直到i=j为止{while(j>i&&R[j]>pivot) //从右向左扫描，找第1个小于或等于pivot的元素j--;while (j>i&&R[i]<=pivot) //从左向右扫描，找第1个大于pivot的元素i++;if (i<j) //R[i]和R[j]进行交换{tmp1=R[i];R[i]=R[j];R[j]=tmp1;}}}tmp2=R[i]; //pivot和R[i]进行交换R[i]=R[s];R[s]=tmp2;return i;}void QuickSort(int R[],int s, int t){int i=Partition(R,s,t);QuickSort(R,s,i-1); //对左区间递归排序QuickSort(R,i+1,t); //对右区间递归排序}int main(){int R[MAX],m;cin>>m;for(int k=0;k<m;k++)cin>>R[k];int s,t;cout<<"输入s的值：\n";cin>>s;cout<<"输入t的值：\n";cin>>t;QuickSort(R,s,t);for(k=s;k<=t;k++)cout<<R[k]<<" ";cout<<endl;return 0;}非递归算法#include<iostream>using namespace std;#include<stack>#define MAX 100int Partition(int R[],int s, int t){int i=s,j=t;int pivot,tmp1,tmp2; //pivot作为基准值if(s<t){pivot=R[s];while(i!=j) //从区间两端交替向中间扫描，直到i=j为止{while(j>i&&R[j]>pivot) //从右向左扫描，找第1个<=pivot的元素j--;while (j>i&&R[i]<=pivot) //从左向右扫描，找第1个>pivot的元素i++;if (i<j) //R[i]和R[j]进行交换{tmp1=R[i];R[i]=R[j];R[j]=tmp1;}}}tmp2=R[i]; //pivot和R[i]进行交换R[i]=R[s];R[s]=tmp2;return i;}void QuickSort(int R[],int s, int t){stack<int> k;int pivot1=Partition(R,s,t);// 入栈k.push(pivot1+1); // 后半段k.push(t);k.push(s); // 前半段k.push(pivot1-1);while (!k.empty()){t=s.top();s.pop();s=s.top();s.pop();if (s<t){pivot1=Partition(s,t);// 入栈s.push(pivot1+1); // 后半段s.push(t);s.push(s); // 前半段s.push(pivot1-1);}}}int main(){int R[MAX],m;cin>>m;for(int k=0;k<m;k++)cin>>R[k];int s,t;cout<<"输入s的值：\n";cin>>s;cout<<"输入t的值：\n";cin>>t;QuickSort(R,s,t);for(k=s;k<=t;k++)cout<<R[k]<<" ";cout<<endl;return 0;}。

快速排序法c语言代码快速排序法是一种非常高效的排序算法，它能够在最好情况下实现O(NlogN)的时间复杂度。

下面是快速排序法的C语言代码实现： ```#include <stdio.h>void quicksort(int arr[], int left, int right) {int i, j, pivot, temp;if (left < right) {pivot = left;i = left;j = right;while (i < j) {while (arr[i] <= arr[pivot] && i < right)i++;while (arr[j] > arr[pivot])j--;if (i < j) {temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}temp = arr[pivot];arr[pivot] = arr[j];arr[j] = temp;quicksort(arr, left, j - 1);quicksort(arr, j + 1, right);}}int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);quicksort(arr, 0, n - 1);printf('Sorted array: ');for (int i = 0; i < n; i++)printf('%d ', arr[i]);return 0;}```在main函数中，我们首先定义一个整型数组arr，并初始化它。

然后通过计算数组的长度n，调用quicksort函数进行排序。

quicksort函数接收三个参数：待排序数组arr，左边界left和右边界right。

快速排序（C语⾔）-解析快速排序快速排序是⼀种排序算法，对包含 n 个数的输⼊数组，最坏情况运⾏时间为O（n2）。

虽然这个最坏情况运⾏时间⽐较差，但快速排序通常是⽤于排序的最佳的实⽤选择，这是因为其平均性能相当好：期望的运⾏时间为O（nlgn），且O（nlgn）记号中隐含的常数因⼦很⼩。

另外，它还能够进⾏就地排序，在虚存环境中也能很好的⼯作。

快速排序（Quicksort）是对的⼀种改进。

快速排序由C. A. R. Hoare在1962年提出。

它的基本思想是：通过⼀趟排序将要排序的数据分割成独⽴的两部分，其中⼀部分的所有数据都⽐另外⼀部分的所有数据都要⼩，然后再按此⽅法对这两部分数据分别进⾏快速排序，整个排序过程可以进⾏，以此达到整个数据变成有序。

像合并排序⼀样，快速排序也是采⽤分治模式的。

下⾯是对⼀个典型数组A[p……r]排序的分治过程的三个步骤：分解：数组 A[p……r]被划分为两个（可能空）⼦数组 A[p……q-1] 和 A[q+1……r] ，使得 A[p……q-1] 中的每个元素都⼩于等于 A(q) , ⽽且，⼩于等于 A[q+1……r] 中的元素。

⼩标q也在这个划分过程中进⾏计算。

解决：通过递归调⽤快速排序，对于数组 A[p……q-1] 和 A[q+1……r] 排序。

合并：因为两个⼦数组是就地排序的，将它们的合并不需要操作：整个数组 A[p……r] 已排序。

下⾯的过程实现快速排序(伪代码)：QUICK SORT（A，p，r）1if p<r2 then q<-PARTITION(A,p,r)3 QUICKSORT(A,p,q-1)4 QUICKSORT(A,q+1,r)为排序⼀个完整的数组A，最初的调⽤是QUICKSORT（A，1，length[A]）。

数组划分： 快速排序算法的关键是PARTITION过程，它对⼦数组 A[p……r]进⾏就地重排(伪代码)：PARTITION（A，p，r）1 x <- A[r]2 i <- p-13for j <- p to r-14do if A[j]<=x5 then i <- i+16 exchange A[i] <-> A[j]7 exchange A[i + 1] <-> A[j]8return i+1排序演⽰⽰例假设⽤户输⼊了如下数组：下标012345数据627389创建变量i=0（指向第⼀个数据）, j=5(指向最后⼀个数据), k=6(为第⼀个数据的值)。

c语言排序方法C语言是一种高效的编程语言，其基础算法和数据结构内容是必备的知识。

排序算法是其中一种重要的基础算法，是C语言程序开发中常用的一种技能，可以帮助我们对数据进行有序处理，更好地解决问题。

在C语言中，排序算法分为内部排序和外部排序。

内部排序是指将需要排序的数据都放在内存中进行排序，主要适用于数据量较小的情况。

而外部排序则是指需要对大数据集进行排序，需要借助外部存储器进行排序。

在此我们主要讨论内部排序算法。

内部排序可以分为以下几类：1. 插入排序插入排序包括直接插入排序、希尔排序等。

直接插入排序是将一个记录插入到有序表中形成一个新的有序表；而希尔排序是通过缩小元素间的间隔，并对每个子序列分别进行插入排序来完成整个排序过程。

插入排序方法简单，适用于小数组或部分有序的数组，是稳定排序方法。

2. 选择排序选择排序包括简单选择排序、堆排序等。

简单选择排序是通过不断的在剩余元素中找到最小元素，并将其放在已排好序的数组末尾进行排序，是不稳定排序方法；而堆排序则是通过将待排序数组看作一个完全二叉树，不断将根节点放到其正确位置上进行排序，是不稳定排序方法。

3. 交换排序交换排序包括冒泡排序、快速排序等。

冒泡排序是通过不断比较相邻的两个数，将较小(或较大)数向前(或向后)交换，在每一次外循环中确定一个元素的位置的排序方法，是稳定排序方法；而快速排序则是通过不断地将待排序数组分成两部分，分别进行递归排序，再将两部分合并成一个有序的数组，是不稳定排序方法。

4. 合并排序合并排序是将待排序数组分成若干个子数组，将每个子数组排好序，再将排好序的子数组合并成最终有序的数组。

合并排序是稳定排序方法，主要优化点在于合并有序数组的过程中需要有额外的空间存放有序的数据。

在实际开发中，我们需要选择适合当前情况的排序方法，优化算法的实现，提高算法的效率。

另外，在使用排序算法的过程中，我们还需要注意以下几点：1. 数据量的大小决定了排序算法的选择。

快速排序算法快速排序快速排序（Quicksort）是对冒泡排序的一种改进。

由C. A. R. Hoare在1962年提出。

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法过程设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

一趟快速排序的算法是：1）设置两个变量I、J，排序开始的时候：I=0，J=N-1；2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值A[J]，并与A[I]交换；4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的A[I]，与A[J]交换；5）重复第3、4、5步，直到I=J；(3,4步是在程序中没找到时候j=j-1，i=i+1。

找到并交换的时候i，j指针位置不变。

另外当i=j这过程一定正好是i+或j+完成的最后另循环结束)例如：待排序的数组A的值分别是：（初始关键数据：X=49）注意关键X永远不变，永远是和X进行比较，无论在什么位子，最后的目的就是把X放在中间，小的放前面大的放后面。

A[0] 、A[1]、A[2]、A[3]、A[4]、A[5]、A[6]：49 38 65 97 76 13 27进行第一次交换后：27 38 65 97 76 13 49( 按照算法的第三步从后面开始找)进行第二次交换后：27 38 49 97 76 13 65( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时：I=3 )进行第三次交换后：27 38 13 97 76 49 65( 按照算法的第五步将又一次执行算法的第三步从后开始找进行第四次交换后：27 38 13 49 76 97 65( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时：J=4 ) 此时再执行第三步的时候就发现I=J，从而结束一趟快速排序，那么经过一趟快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。

/*顺序表的操作#include<iostream>#include<stdlib.h>using namespace std;Release 13.12 rev 9501 (2013/12/25 19:25:45) gcc 4.7.1 Windows/unicode - 32 bit #define MAX_SIZE 100typedef struct{int *emel;int lenth;}Sq;void init(Sq &l);void create(Sq &l);void trval(Sq &l);void find_value(Sq &l);void find_position(Sq &l);void insert(Sq &l);void dele(Sq &l);int main(){Sq l;init(l);create(l);trval(l);find_value(l);find_position(l);insert(l);trval(l);dele(l);trval(l);return 0;}void init(Sq &l){l.emel =new int[MAX_SIZE];if(l.emel ==NULL){cout<<"\t申请空间失败！"<<endl;exit(1);}l.lenth=0;cout<<"\t成功申请空间！该顺序表的长度目前为:"<<l.lenth<<endl; }void create(Sq &l){cout<<"\t请输入你想输入元素的个数：";int x;cin>>x;if((x<1)&&(x>MAX_SIZE)){cout<<"\t你说输入的数不在范围里"<<endl;return;}int i;for(i=0;i<x;i++){cin>>l.emel[i];}l.lenth=x;cout<<"\t成功赋值！"<<endl;}void trval(Sq &l){int i;cout<<"l(";for(i=0;i<l.lenth;i++){cout<<l.emel[i]<<" ";}cout<<")"<<" 该顺序表现在的长度为："<<l.lenth<<endl;}void find_value(Sq &l){int x,t=0;cout<<"\t请输入你要查找的值：";cin>>x;int i;for(i=0;i<l.lenth;i++){if(l.emel[i]==x){t=1;cout<<"\t成功找到该元素，它是顺序表的第"<<i+1<<"个元素！"<<endl;}}if(t==0){cout<<"\t无该元素！"<<endl;}}void find_position(Sq &l){int x;cout<<"\t请输入你要查找的位置：";cin>>x;int i;if((x<1)||(x>l.lenth)){cout<<"\t输入的值不在范围内！"<<endl;return;}for(i=1;i<=l.lenth;i++){if(i==x){cout<<"\t成功找到该元素，该值是"<<l.emel[i-1]<<endl;}}}void insert(Sq &l){int i,x,y;cout<<"\t请输入你要插入的位置";cin>>x;cout<<"\t请输入你要插入的值";cin>>y;if((x<1)||(x>l.lenth)){cout<<"\t输入的值不在范围内！"<<endl;return;}if(x==l.lenth){l.emel[l.lenth]=y;l.lenth=l.lenth+1;return;}for(i=l.lenth;i>=x;i--){l.emel[i]=l.emel[i-1];}l.emel[x-1]=y;l.lenth=l.lenth+1;}void dele(Sq &l){int i,x;cout<<"\t请输入你要删除位置：";cin>>x;if((x<1)||(x>l.lenth)){cout<<"\t输入的值不在范围内！"<<endl;return;}for(i=x-1;i<=l.lenth;i++){l.emel[i]=l.emel[i+1];}l.lenth=l.lenth-1;}成功申请空间！该顺序表的长度目前为:0请输入你想输入元素的个数：3852成功赋值！l(8 5 2 ) 该顺序表现在的长度为：3请输入你要查找的值：5成功找到该元素，它是顺序表的第2个元素！请输入你要查找的位置：3成功找到该元素，该值是2请输入你要插入的位置3请输入你要插入的值10l(8 5 2 10 ) 该顺序表现在的长度为：4请输入你要删除位置：3l(8 5 10 ) 该顺序表现在的长度为：3--------------------------------Process exited with return value 0Press any key to continue . . .*//*#include<stdio.h>#include<stdlib.h>typedef struct Link{int num;struct Link *next;}L;L* creat(L* head){head=(L *)malloc(sizeof(L));if(head==NULL){printf("头节点申请失败！\n");exit(-1);}head->next=NULL;return head;}void insert(L* head){int x,i;printf("请输入你想输入数据的个数：");scanf("%d",&x);L *p,*q;p=head;for(i=0;i<x;i++){q=(L *)malloc(sizeof(L));if(q==NULL){printf("新点申请失败！\n");exit(-1);}printf("请输入值：");scanf("%d",&q->num);q->next=NULL;p->next=q;p=q;}}void print(L* head){L *p;p=head->next;while(p!=NULL){printf("值为：%d\n",p->num);p=p->next;}}int main(){L *head;head=creat(head);printf("成功创建头节点！！！\n");insert(head);printf("成功输入数据！！！\n");print(head);return 0;}*//*线性表的操作#include<stdio.h>#include<stdlib.h>typedef struct Link{int num;struct Link *next;}L;L* creat(L* head){head=(L *)malloc(sizeof(L));if(head==NULL){printf("头节点申请失败！\n");exit(-1);}head->next=NULL;return head;}void init(L* head){int x,i;printf("请输入你想输入数据的个数：");scanf("%d",&x);L *p,*q;p=head;for(i=0;i<x;i++){q=(L *)malloc(sizeof(L));if(q==NULL){printf("新点申请失败！\n");exit(-1);}printf("请输入值：");scanf("%d",&q->num);q->next=p->next;p->next=q;}}int print(L* head){L *p;int lenth=0;p=head->next;printf("\t\tL(");while(p!=NULL){lenth++;printf("%d ",p->num);p=p->next;}printf(")\n");return lenth;}int insert(L *head,int lenth){printf("\t\t请输入你要插入的元素的位置:");int in;scanf("%d",&in);if(in<1 || in>lenth){printf("\t\t输入值不在范围内！");return -1;}L *p,*q;p=head->next;q=(L *)malloc(sizeof(L));if(q==NULL){printf("新点申请失败！\n");return -1;}printf("\t\t请为新节点输入值：");scanf("%d",&q->num);int i=0;while(p!=NULL){i++;if(i==in-1){q->next=p->next;p->next=q;}p=p->next;}lenth++;return lenth;}int dele(L *head,int lenth){printf("\t\t请输入你要删除的元素的位置:");int out;scanf("%d",&out);if(out<1 || out>lenth){printf("\t\t输入值不在范围内！");return -1;}L *p,*q;p=head->next;q=head;int i=0;while(p!=NULL){i++;if(i==out){q->next=p->next;}q=p;p=p->next;}lenth--;return lenth;}void find(L *head,int lenth){printf("\t\t请输入你要查找的元素的位置:");int finder;scanf("%d",&finder);if(finder<1 || finder>lenth){printf("\t\t输入值不在范围内！");return ;}L *p;p=head->next;int i=0;while(p!=NULL){i++;if(i==finder){printf("\t\t你要找的该位置所对应的值为：%d\n",p->num);}p=p->next;}}int main(){L *head;head=creat(head);printf("成功创建头节点！！！\n");init(head);printf("成功输入数据！！！\n");int len;len=print(head);printf("\t\t该线性表的长度为:%d\n",len);len=insert(head,len);len=print(head);printf("\t\t插入后线性表的长度为:%d\n",len);len=dele(head,len);len=print(head);printf("\t\t删除后该线性表的长度为:%d\n",len);find(head,len);return 0;}*//*顺序表的合并#include<iostream>using namespace std;struct LA{int *pa;int lenth;};struct LB{int *pb;int lenth;};struct LC{int *pc;int lenth;};void mergelist(LA la,LB lb,LC &lc);int main(){int x,y;LA la;LB lb;cout<<"\t\t请给线性表LA和LB指定长度：";cin>>x>>y;la.pa =new int(sizeof(int)*x);lb.pb =new int(sizeof(int)*y);int i;for(i=0;i<x;i++){cout<<"请输入表LA的值:";cin>>la.pa[i];}cout<<endl;la.lenth=x;for(i=0;i<y;i++){cout<<"请输入表LB的值:";cin>>lb.pb[i];}lb.lenth=y;cout<<"LA(";for(i=0;i<x;i++){cout<<la.pa[i]<<" ";}cout<<")"<<endl;cout<<"LB(";for(i=0;i<y;i++){cout<<lb.pb[i]<<" ";}cout<<")"<<endl;LC lc;mergelist(la,lb,lc);return 0;}void mergelist(LA la,LB lb,LC &lc){lc.lenth=la.lenth+lb.lenth;lc.pc=new int(sizeof(int)*lc.lenth);int *pa=la.pa,*pb=lb.pb,*pc=lc.pc;int *pa_last=la.pa+la.lenth-1;int *pb_last=lb.pb+lb.lenth-1;while(pa<=pa_last && pb<=pb_last){if(*pa <= *pb){*pc++=*pa++;}else{*pc++=*pb++;}}while(pa<=pa_last){*pc++=*pa++;}while(pb<=pb_last){*pc++=*pb++;}cout<<"LC(";int i=0;for(i=0;i<lc.lenth;i++){cout<<lc.pc[i]<<" ";}cout<<")"<<endl;}*///栈/*#include<iostream>using namespace std;#include<stdlib.h>#define MAXSIZE 100typedef struct{int *base;int *top;int stacksize;}Sqstack;int Initstack(Sqstack &s);void Push(Sqstack &s,int e);void StackTraverse(Sqstack &s);void Gettop(Sqstack &s);void Pop(Sqstack &s);int main(){Sqstack s;Initstack(s);cout<<"\t\t初始化栈成功！"<<endl;Push(s,2);cout<<"\t\t2入栈成功！"<<endl;Push(s,4);cout<<"\t\t4入栈成功！"<<endl;Push(s,6);cout<<"\t\t6入栈成功！"<<endl;Push(s,8);cout<<"\t\t8入栈成功！"<<endl;cout<<"\n由栈底至栈顶的元素为：";StackTraverse(s);Gettop(s);Pop(s);Gettop(s);return 0;}int Initstack(Sqstack &s){s.base=new int[MAXSIZE];if(s.base==NULL){exit(1);}s.top=s.base;s.stacksize=MAXSIZE;}void Push(Sqstack &s,int e){if(s.top-s.base==s.stacksize){exit(1);}*s.top++=e;}void StackTraverse(Sqstack &s){int *p=s.base,i=0;while(p<s.top){i++;cout<<*p++<<" ";}cout<<"\t\t栈的长度是"<<i<<endl;}void Gettop(Sqstack &s){if(s.base==s.top){exit(1);}cout<<"栈顶元素是："<<*(s.top-1)<<endl; }void Pop(Sqstack &s){if(s.top==s.base){exit(1);}cout<<"出栈的第一个元素是:";cout<<*--s.top<<" "<<endl;}*///队列例题：/*#include<iostream>#include<stdlib.h>using namespace std;#define MAXQSIZE 100typedef struct{int *base;int front;int rear;}SqQueue;int InitQueue(SqQueue &q);int EnQueue(SqQueue &q,int x);int DeQueue(SqQueue &q);int main(){SqQueue q;InitQueue(q);EnQueue(q,1);EnQueue(q,3);EnQueue(q,5);EnQueue(q,7);DeQueue(q);DeQueue(q);DeQueue(q);DeQueue(q);return 0;}int InitQueue(SqQueue &q){q.base=new int[MAXQSIZE];if(q.base==NULL){exit(1);}q.front=0;q.rear=0;return 0;}int EnQueue(SqQueue &q,int x){if((q.rear+1)%MAXQSIZE==q.front){exit(0);}q.base[q.rear]=x;q.rear=(q.rear+1)%MAXQSIZE;return 0;}int DeQueue(SqQueue &q){if(q.front==q.rear){exit(0);}int x=q.base[q.front];q.front=(q.front+1)%MAXQSIZE;cout<<x<<endl;}*//*#include<iostream>#include<stdlib.h>using namespace std;typedef struct Qnode{int date;struct Qnode *next;}Qnode,*Queueptr;typedef struct{Queueptr front; //队头指针Queueptr rear; //队尾指针}LinkQueue;int InitQueue(LinkQueue &Q);void EnQueue(LinkQueue &Q,int e);void TrvalQueue(LinkQueue Q);void DeQueue(LinkQueue &Q);int main(){LinkQueue Q;InitQueue(Q);EnQueue(Q,1);cout<<"\t元素1入队成功！"<<endl;EnQueue(Q,3);cout<<"\t元素3入队成功！"<<endl;EnQueue(Q,5);cout<<"\t元素5入队成功！"<<endl;EnQueue(Q,7);cout<<"\t元素7入队成功！"<<endl;cout<<"\t队列的元素分别是："<<endl;TrvalQueue(Q);cout<<"\t第一个出队的元素是："<<endl;DeQueue(Q);cout<<"\n\t第一个元素出队完成之后队列中从队头至队尾的元素为：";TrvalQueue(Q);return 0;}int InitQueue(LinkQueue &Q){Q.rear=new Qnode;Q.front=Q.rear;if(Q.front==NULL){exit(0);}Q.front->next=NULL;return 0;}void EnQueue(LinkQueue &Q,int e){Qnode *p=new Qnode;if(!p){exit(1);}p->date=e;p->next=NULL;Q.rear->next=p; //连接Q.rear=p; //修改队尾指针}void TrvalQueue(LinkQueue Q){Qnode *p=Q.front->next;//队头元素while(Q.front!=Q.rear){cout <<p->date<<" ";Q.front=p;p=p->next;}cout<<endl;}void DeQueue(LinkQueue &Q){if(Q.front==Q.rear){return;}Qnode *p=Q.front->next;cout<<"\t"<<p->date<<endl;Q.front->next=p->next;if(Q.rear==p){Q.rear=Q.front;delete p;}}*//*//表达式求值#include<iostream>#include<stdlib.h>#include<stdio.h>using namespace std;#define MAXSIZE 100typedef struct{char *base;char *top;char num;}OPND; //数据栈typedef struct{char *base;char *top;char c;}OPTR; //符号栈int Initstack(OPND &op_n,OPTR &op_t);void Pushstack(OPND &op_n,char ch);void Pushstack(OPTR &op_t,char ch);char Popstack(OPND &op_n,char ch);char Popstack(OPTR &op_t,char ch);char Gettop(OPTR op_t);char Gettop(OPND op_n);int In(char ch);char Precede(char x,char y);char operate(char z,char x,char y);int main(){OPND op_n;OPTR op_t;Initstack(op_n,op_t);Pushstack(op_t,'#');char ch;char p;cin>>ch;while(ch!='#' || Gettop(op_t)!='#'){if(!In(ch)){Pushstack(op_n,ch);cin>>ch;}else{switch( Precede(Gettop(op_t),ch) ){case '<':Pushstack(op_t,ch);cin>>ch;break;case '>':char x,y,z;x=Popstack(op_t,x);y=Popstack(op_n,y);z=Popstack(op_n,z);Pushstack(op_n,operate(z,x,y));break;case '=':p=Popstack(op_t,p);cin>>ch;break;}}}cout<<"\t表达式结果是："<<Gettop(op_n)<<endl;return 0;}int Initstack(OPND &op_n,OPTR &op_t){op_n.base=new char[MAXSIZE];op_t.base=new char[MAXSIZE];if((op_n.base==NULL) || (op_t.base==NULL)){exit(1);}op_n.top=op_n.base;op_t.top=op_t.base;op_n.num=MAXSIZE;op_t.c=MAXSIZE;return 0;}void Pushstack(OPND &op_n,char ch){if(op_n.top-op_n.base==op_n.num){return;}*op_n.top++=ch;cout<<ch<<" 入数字栈"<<endl;}void Pushstack(OPTR &op_t,char ch){if(op_t.top-op_t.base==op_t.c){return;}*op_t.top++=ch;cout<<ch<<" 入操作符"<<endl;}char Popstack(OPND &op_n,char ch)if(op_n.top==op_n.base){exit(1);}ch=*--op_n.top;cout<<ch<<" 出数字栈"<<endl;return ch;}char Popstack(OPTR &op_t,char ch){if(op_t.top==op_t.base){exit(1);}ch=*--op_t.top;cout<<ch<<" 出字符栈"<<endl;return ch;}char Gettop(OPTR op_t){char x;if(op_t.top==op_t.base){exit(1);}x=*(op_t.top-1);cout<<"得到操作符栈顶"<<x<<endl;return x;}char Gettop(OPND op_n){char x;if(op_n.top==op_n.base){exit(1);}x=*(op_n.top-1);cout<<"得到操作数栈顶"<<x<<endl;return x;}int In(char ch)if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#') {return 1;}else{return 0;}}char Precede(char x,char y){if(x=='+' || x=='-'){if(y=='+' || y=='-' || y==')' || y=='#'){return '>';}else{return '<';}}if(x=='*'||x=='/'){if(y=='('){return '<';}else{return '>';}}if(x=='('){if(y==')'){return '=';}else if(y=='+'||y=='-'||y=='*'||y=='/'||y=='('){return '<';}}if(x==')'){if(y!='('){return '>';}}if(x=='#'){if(y=='#'){return '=';}else if(y!=')'){return '<';}}}char operate(char z,char x,char y) {if(x=='+'){return (z-'0') + (y-'0')+48;}if(x=='-'){return (z-'0') - (y-'0')+48;}if(x=='*'){return (z-'0')* (y-'0')+48;}if(x=='/'){return (z-'0')/ (y-'0')+48;}}*//*#include<iostream>using namespace std;int main(){char a[10];char *b[10];char **c[10];return 0;}*//*#include<iostream>using namespace std;char f(char x,char y){return (x-'0') * (y-'0')+48;}int main(){char a='3',b='5';char p=f(a,b);cout<<p<<endl;return 0;}*///数列出队/*#include<iostream>#include<stdlib.h>using namespace std;typedef struct Qnode{int num;struct Qnode *next;}Qnode,*Queueptr;typedef struct{Queueptr front;Queueptr rear;}LinkQueue;int InitQueue(LinkQueue &Q);void EnQueue(LinkQueue &Q,int x); int DeQueue(LinkQueue &Q,int p); int main(){LinkQueue Q;InitQueue(Q);int x,i,y,num=0,e;cout<<"请输入总人数:";cin>>x;for(i=1;i<=x;i++){EnQueue(Q,i);}cout<<"请输入第几个数淘汰:";cin>>y;{for(i=0;i<y;i++){if(i!=y-1){e=DeQueue(Q,e);EnQueue(Q,e);}else{DeQueue(Q,e);num++;}}if(num==x-1){break;}}e=DeQueue(Q,e);cout<<"最后剩下的是："<<e<<endl;return 0;}int InitQueue(LinkQueue &Q){Q.front=new Qnode;Q.rear=Q.front;if(Q.front==NULL){exit(1);}Q.front->next=NULL;}void EnQueue(LinkQueue &Q,int x){Qnode *p=new Qnode;if(!p){exit(1);}p->num=x;p->next=NULL;Q.rear->next=p;}int DeQueue(LinkQueue &Q,int e) {Qnode *p;if(Q.rear==Q.front){exit(0);}p=Q.front->next;e=p->num;Q.front->next=p->next;if(Q.rear==p){Q.front=Q.rear;}delete p;return e;}*//*二叉树#include<iostream>#include<stdlib.h>using namespace std;typedef struct BiTNode{char date;struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;void CreateBiTree(BiTree &T);int Depth(BiTree T);int NodeCount(BiTree T);int LeavesNodeCount(BiTree T);int PreOrderTraverse(BiTree T);int InOrderTraverse(BiTree T);int PostOrderTraverse(BiTree T); int main(){BiTree T;CreateBiTree(T);cout<<"二叉树的深度为："<<Depth(T)<<endl;cout<<"二叉树中结点个数为："<<NodeCount(T)<<endl;cout<<"二叉树中叶子结点个数为："<<LeavesNodeCount(T)<<endl;cout<<"先序遍历：";PreOrderTraverse(T);cout<<"\n中序遍历：";InOrderTraverse(T);cout<<"\n后序遍历：";PostOrderTraverse(T);cout<<endl;return 0;}void CreateBiTree(BiTree &T){cout<<"请为该节点赋值:";char ch;cin>>ch;if(ch=='#'){T=NULL;}else{T =new BiTNode;T->date=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}}int Depth(BiTree T){int m,n;if(T==NULL){return 0;}else{m=Depth(T->lchild);n=Depth(T->rchild);if(m>n){return m+1;}else{return n+1;}}}int NodeCount(BiTree T){if(T==NULL){return 0;}else{return NodeCount(T->lchild)+NodeCount(T->rchild)+1;}}int LeavesNodeCount(BiTree T){if(T==NULL){return 0;}else if(T->lchild==NULL && T->rchild==NULL){return 1;}else{return LeavesNodeCount(T->lchild)+LeavesNodeCount(T->rchild);}}int PreOrderTraverse(BiTree T){if(T!=NULL){cout<<T->date;PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}int InOrderTraverse(BiTree T){if(T!=NULL){InOrderTraverse(T->lchild);cout<<T->date;InOrderTraverse(T->rchild);}}int PostOrderTraverse(BiTree T){if(T!=NULL){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);cout<<T->date;}}请为该节点赋值:-请为该节点赋值:+请为该节点赋值:a请为该节点赋值:#请为该节点赋值:#请为该节点赋值:*请为该节点赋值:b请为该节点赋值:#请为该节点赋值:#请为该节点赋值:-请为该节点赋值:c请为该节点赋值:#请为该节点赋值:#请为该节点赋值:d请为该节点赋值:#请为该节点赋值:#请为该节点赋值:/请为该节点赋值:e请为该节点赋值:#请为该节点赋值:#请为该节点赋值:f请为该节点赋值:#请为该节点赋值:#二叉树的深度为：5二叉树中结点个数为：11二叉树中叶子结点个数为：6先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d-e/f后序遍历：abcd-*+ef/-Process returned 0 (0x0) execution time : 76.214 s Press any key to continue.*//*#include<iostream>#include<stdlib.h>#include<string.h>using namespace std;typedef struct{int weiget;int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef char** HuffmanCode;void creat(HuffmanTree &HT,int n);void Select(HuffmanTree HT,int k,int &min1,int &min2); void creatcode(HuffmanTree HT,HuffmanCode &HC,int n); int min(HuffmanTree HT,int k);int main(){int n;cout<<"请输入叶子节点的个数:";cin>>n;HuffmanTree HT;creat(HT,n);HuffmanCode HC;creatcode(HT,HC,n);return 0;}void creat(HuffmanTree &HT,int n){if(n<1){exit(1);}int m=2*n-1,i;HT=new HTNode[m+1];for( i=1;i<=m;i++){HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(i=1;i<=n;i++){cout<<"请输入权值:";cin>>HT[i].weiget;}int s1,s2;for(i=n+1;i<=m;i++) //通过n-1次选择来合并创建{Select(HT,i-1,s1,s2);HT[s1].parent=i; //赋值，作为删除的标记HT[s2].parent=i;cout<<"s1:"<<s1<<" s2:"<<s2<<endl;HT[i].lchild=s1; //生成新节点HT[i].rchild=s2;HT[i].weiget=HT[s1].weiget+HT[s2].weiget;}}void Select(HuffmanTree HT,int k,int &min1,int &min2){min1=min(HT,k);min2=min(HT,k);}int min(HuffmanTree HT,int k){int i=0;int min;//存放weight最小且parent为-1的元素的序号int min_wei;//存放权值while(HT[i].parent!=0){i++;}min_wei=HT[i].weiget;min=i;for(;i<=k;i++){if(HT[i].weiget<min_wei && HT[i].parent==0){min_wei=HT[i].weiget;min=i;}}HT[min].parent=1;return min;}void creatcode(HuffmanTree HT,HuffmanCode &HC,int n){HC =new char *[n+1];char *cd=new char[n];cd[n-1]='\0';int i,start;//start指向最后，即编码结束符的位置int current,father;for(i=1;i<=n;i++){start=n-1;current=i;father=HT[i].parent;while(father!=0){--start;if(HT[father].lchild==current){cd[start]='0';}else{cd[start]='1';}current=father;father=HT[father].parent;}HC[i]=new char[n-start];strcpy(HC[i],&cd[start]);cout<<HT[i].weiget<<"对应的编码是："<<HC[i]<<endl;}delete cd;}请输入叶子节点的个数:5请输入权值:1请输入权值:2请输入权值:3请输入权值:4请输入权值:5s1:1 s2:2s1:3 s2:6s1:4 s2:5s1:7 s2:81对应的编码是：0102对应的编码是：0113对应的编码是：004对应的编码是：105对应的编码是：11Process returned 0 (0x0) execution time : 4.003 s Press any key to continue.*///折半查找#include<iostream>#include<stdio.h>using namespace std;#define ENDFLAG 10000typedef int KeyType;typedef char* InfoType;typedef struct{KeyType key;InfoType otherinfo;}ElemType;typedef struct{ElemType *R;int length;}SSTable;void CreateSTable(SSTable &ST,int n){int i;ST.R=new ElemType[n+1];for(i=1;i<=n;i++){cout<<"请输入"<<i<<"个测试数据：";cin>>ST.R[i].key;}ST.length=n;}int Search_Bin1(SSTable ST,KeyType key){int low,high,mid;low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(key==ST.R[mid].key){return mid;}else if(key<ST.R[mid].key){high=mid-1;}else{low=mid+1;}}return 0;}int Search_Bin2(SSTable ST,int low,int high,KeyType key) {int mid;if(low>high){return 0;}mid=(low+high)/2;printf("%d+++++",key==ST.R[mid].key);if(key==ST.R[mid].key){return mid;}else if(key<ST.R[mid].key){return Search_Bin2(ST,low,mid-1,key);}else{return Search_Bin2(ST,mid+1,high,key);}}int main(){int n;KeyType key;SSTable ST;cout<<"请输入静态查找表长：";cin>>n;CreateSTable(ST,n);cout<<"请输入待查记录的关键字：";cin>>key;cout<<"Search_Bin1算法计算的位置为："<<Search_Bin1(ST,key)<<endl;cout<<"Search_Bin2算法计算的位置为："<<Search_Bin2(ST,1,ST.length,key)<<endl;return 0;}/*请输入静态查找表长：5请输入1个测试数据：1请输入2个测试数据：2请输入3个测试数据：3请输入4个测试数据：4请输入5个测试数据：5请输入待查记录的关键字：3Search_Bin1算法计算的位置为：3Search_Bin2算法计算的位置为：3Process returned 0 (0x0) execution time : 8.620 sPress any key to continue.*//*#include<iostream>using namespace std;typedef struct{int key;}ElemType;typedef struct BSTNode{ElemType date;struct BSTNode *lchild,*rchild;}BSTNode,*BSTree;void Create(BSTree &T);void Insert(BSTree &T,ElemType e);int InOrderTraverse(BSTree T);int main(){BSTree T;Create(T);InOrderTraverse(T);cout<<"\n中序遍历：";return 0;}void Create(BSTree &T){T=NULL;ElemType e;cout<<"请为节点赋值:(0为结束条件)";cin>>e.key;while(e.key!=0){Insert(T,e);cout<<"请为节点赋值:(0为结束条件)";cin>>e.key;}}void Insert(BSTree &T,ElemType e){if(!T){BSTree S;S=new BSTNode;S->date=e;S->lchild=NULL;S->rchild=NULL;T=S;}else if(e.key<T->date.key){Insert(T->lchild,e);}else{Insert(T->rchild,e);}}int InOrderTraverse(BSTree T){if(T!=NULL){InOrderTraverse(T->lchild);cout<<T->date.key<<" ";InOrderTraverse(T->rchild);}return 0;}请为节点赋值:(0为结束条件)12请为节点赋值:(0为结束条件)7请为节点赋值:(0为结束条件)17请为节点赋值:(0为结束条件)11请为节点赋值:(0为结束条件)16请为节点赋值:(0为结束条件)2请为节点赋值:(0为结束条件)13请为节点赋值:(0为结束条件)9请为节点赋值:(0为结束条件)21请为节点赋值:(0为结束条件)4请为节点赋值:(0为结束条件)02 4 7 9 11 12 13 16 17 21中序遍历：Process returned 0 (0x0) execution time : 23.808 s Press any key to continue.*/。