yuyunzhen的博客

原创 2019数据结构考研真题

原创 /*删除区间内元素*/

/*删除区间内元素*/算法设计思想：代码设计：#include<bits/stdc++.h>using namespace std;#define Max 50struct Sqlist{int a[Max]={1,2,3,3,4,5,6,7,7,7,8,9};int length=12;};void deletelist(Sqlist &L,int s,int v){if(s>=v||L.length==0) retu.

原创 /*删除数组中特定值的元素*/

/*删除数组中特定值的元素*/算法设计思想：代码设计：#include<bits/stdc++.h>using namespace std;#define Max 50struct Sqlist{int a[Max]={5,2,0,1,3,1,4,1,1,4};int length=10;};void deletelist(Sqlist &L,int x){int k=0;for(int i=0;i<L.length.

原创 逆置线性表

逆置线性表设计思想：从下标0开始只需遍历至中间，和顺序表对称位置交换交换。代码设计：#include<bits/stdc++.h>using namespace std;#define Max 50struct Sqlist{int a[Max]={1,4,6,3,2,8,7};int length=7;};void reverse(Sqlist &L){for(int i=0;i<L.length/2;i++){int v=

原创 /*从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补；若顺序表为空，则显示出错误信息并退出运行。*/

/*从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补；若顺序表为空，则显示出错误信息并退出运行。*/设计思路：代码：#include<bits/stdc++.h>using namespace std;#define Max 50struct Sqlist{int a[Max]={2,3,4,6,7,1,8,9};int length=8;};bool listdelete(Sqli.

原创 考研概率论真题

原创 【无标题】

设某二叉树中只有度为0和度为2的结点，如果此二叉树的高度为100，那么此二叉树包含的结点数最少（）100*2-1=199

原创 二叉树若采用顺序方法存储，则下列四种算法中运算时间复杂度最小的是（）

二叉树若采用顺序方法存储，则下列四种算法中运算时间复杂度最小的是（）（1）先序遍历二叉树（O(n)）（2）判断两个指定位置的结点是否在同一层上（O(1)）（3）层次遍历二叉树（O(n)）（4）根据结点的值查找其存储位置（O(n)）...

原创 设森林F对应的二叉树为B，它有m个结点，B的根p,p右子树结点个数n,森林F中第一棵树的结点个数（）

设森林F对应的二叉树为B，它有m个结点，B的根p,p右子树结点个数n,森林F中第一棵树的结点个数（）森林转二叉树（左孩子右兄弟），以第一棵树的根结点为树的根结点m个结点=第一颗子树结点数(m-n)+剩余子树节点数（n）...

原创 【无标题】

某二叉树的先根遍历序列为IJKLMNO,中根遍历序列为JLKINMO，则后根遍历序列是（）NLR(根左右)I J MK...

原创 栈，队列，循环队列的定义

栈，队列，循环队列的定义栈：逻辑结构：线性表物理结构：顺序存储，链式存储，哈希存储，索引存储运算：增删改查（操作受限进栈出栈只在一端进行）队列：逻辑结构：线性表物理结构：顺序存储，链式存储，哈希存储，索引存储运算：增删改查（操作受限进队出队在同一队列中不同位置进行）循环队列：逻辑结构：线性表物理结构：顺序存储，链...

原创 循环队列以数组Q【0,...,m-1】存储结构，rear表示循环队列中的队尾元素的实际位置，移动按rear=(rear+1)/MODm，length表示当前循环队列中的元素个数，循环队列队首实际位置。

若循环队列以数组Q【0,...,m-1】存储结构，变量rear表示循环队列中的队尾元素的实际位置，其移动按rear=(rear+1)/MODm，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是（(rear-length+1+m)/MODm）...

原创 栈和队列的主要区别

逻辑结构：线性结构，非线性结构（属于线性结构）物理结构：顺序存储，链式存储，哈希存储，index存储（都用）运算：增删改查主要区别在于插入和删除的限定不一样

原创 已知3个带头结点的线性链表A,B,C中的结点均依元素值自小至大非递减排列（可能存在两个或两个以上值相同的结点），编写算法对链表A进行如下操作：使操作后的链表A中仅留下3个表中均包含的数据元素的结点

/*已知3个带头结点的线性链表A,B,C中的结点均依元素值自小至大非递减排列（可能存在两个或两个以上值相同的结点），编写算法对链表A进行如下操作：使操作后的链表A中仅留下3个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O(m+n+p),其中m,n和p分别为三个表的长度。*/typedef struct LNode{ int data; struct LNode *next;}*Linkedlist;LinkedList Com...

原创 如果以单链表表示集合，设集合A用单链表LA表示，集合B用单链表LB表示，设计算法求两个集合的差即A-B.

/*如果以单链表表示集合，设集合A用单链表LA表示，集合B用单链表LB表示，设计算法求两个集合的差即A-B.*/void Difference(LinkList *LA,LinkList *LB){ Node *pre,*p,*r; pre=LA; p=LA->next; while(p!=NULL){ q=LB->next; //遍历LB表，判断LA中元素是否在LB中 while(q!=NULL&a...

原创 【无标题】链表按结点数据域的值的大小，将其从小到大依次重新链接，在链接过程中不得使用该链表以外的任何链结点空间

/*有一个不带头结点的单链表list,链表中结点都两个域：数据域data和指针域Link。已知初始时该单链表无序，请设计一个算法将该链表按结点数据域的值的大小，将其从小到大依次重新链接，在链接过程中不得使用该链表以外的任何链结点空间。要求：（1）：给出算法的基本设计思想。（2）： 根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。*/typedef struct LNode{ int data; struct LNode *link;}*linkedli...

原创 【无标题】频度递减排序

/*设有一个双链表L,每个结点中除有prior,data和next这三个域外，还有一个访问频度域freq,在链表被启用之前，其值初始化为零。当在链表进行一次LocateNode(L,x)运算时，令元素值为x的结点中freq域的值加1，表调整表中结点的次序，事前访问频度的递减排列，以便使访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。*/p=h->next;q=p->next;while(q&&p){ if(q->data&...

原创 【无标题】

/*线性表（a1,a2,a3,...,an）中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容：（1）用最少的时间在表中查找数值为x的元素。（2）若找到将其与元素位置相交换。（3）若找不到将其插入表中并使表中元素仍递增有序。*//*二分查找算法*/int m=0,l=0,r=n;while(l<=r){ m=(l+r)/2; if(a[m]==x&&m<n) { t=a[m]; a[...

原创 【无标题】

已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min且小于max的结点（若表中有这样的结点），同时释放被删除结点的空间，这里min和max是两个给定的参数。/*已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min且小于max的结点（若表中有这样的结点），同时释放被删除结点的空间，这里min和max是两个给定的参数。*/pointer p,q,s;p=h->next;q=h;while(p!=null){ if(p->data<max...

原创 【无标题】

顺序表奇数位放到偶数位前

原创 【无标题】线性表（a1,a2,a3,...,an）中元素递增有序顺序存储于计算机内。设计算法用最少时间在表中查找数值为x的元素，并将其与后继元素位置相交换。如表中未找到该元素，将其放合适位使表有序。

线性表（a1,a2,a3,...,an）中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍然递增有序。（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出解释。（3）分别给出算法各部分的时间复杂度。/*二分查找算法*//*时间复杂度(以空间换时间)*/int l=1,r=n,m=0,t=0,flag=0;whi

原创 【无标题】合并A和B链表

有两个集合A和B，利用带头结点链表表示，设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法，将A和B合并，合并后仍然保持整个链表中的元素依次递增。不得利用额外的节点空间，只能在A和B的原有结点空间上完成。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。（3）分别给出算法各部分的时间复杂度。void conlink(&la,&lb){pointer p,q,f,w=la;...

原创 链表逆序代码（c++/c）

单链表reverse

原创 计数排序

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。算法描述找出待排序的数组中最大和最小的元素；统计数组中每个值为i的元素出现的次数，存入数组C的第i项；对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。#include<stdio.h>int c=..

原创 堆排序

堆排序堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。算法描述O(nlogn)建堆的时间复杂度O(n)heapify的时间复杂度为O(logn)将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]

原创 归并排序

归并排序把长度为n的输入序列分成两个长度为n/2的子序列；对这两个子序列分别采用归并排序；将两个排序好的子序列合并成一个最终的排序序列。速度仅次于快速排序，为稳定排序算法归并排序是建立在归并操作上的一种有效的排序算法,该算法采用经典的分治策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序，若将两个有序表合并成一个有序表，称为二路归并1、归并排序的基本

原创 希尔排序

希尔排序希尔排序是插入排序的一种，又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。#include<stdio.h>#include<math.h>#defineMAXNUM10voidmain(){voidshellSort(in...

原创 快速排序

#include <stdio.h>#include <stdlib.h>#define M 6//基准函数int depart(int arr[], int low, int high){ int key; key = arr[low];//以key值作为基准值进行划分 while(low<high)//直到下标相遇 { while(low <high && arr[high]>= k...

原创 插入排序c语言实现

插入排序算法思想：细心的同学会发现，我们把打扑克牌过程放慢，从获得第一张牌开始接下来我们按照从大到下（小到大）进行排序，我们当前获得一张牌如何在已排好序的的牌中按大小占据合适位置。这就需要依次与之前排好序的扑克牌进行比较，直到找到比之大或比之小的牌我们就将其放置此处。//插入排序#include<stdio.h>#include<stdlib.h>int main(){ int a[10]={0,2,1,6,8,7,3,5,4,9}; int i...

原创 c语言实现选择排序

选择排序是一种简单直观的排序算法工作原理：每一次从待排序的数据元素中选出最小或最大的一个元素存放到序列的起始位置，然后再从剩余的未排元素中继续寻找最小或最大元素，然后放到已排序序列的末尾，以此类推，直到全部待排序的数据元素排完。算法思想：从第一个开始，然后从下一个开始遍历一遍找到最小的，然后跟第一个进行交换，这样就完成一轮，然后选择第二个，开始第二轮，直到num_len-1轮//选择排序#include<stdio.h>#include<stdlib.h>

原创 C语言实现冒泡排序

算法思想：从第一个开始，相邻两个数进行比较，如果前1个数大于后一个数，则进行调换，这样换到最后，最大的那个就会在最后面，重复这个过程，较大的就会逐个累积在后面，本质思想就是大的在一轮中会逐渐冒泡到后排。//冒泡排序#include<stdio.h>#include<stdlib.h>int main(){int a[10]={2,1,3,5,4,6,7,9,8};int i,j,t,k;for (i=0;i<9;i++)//比较n-1趟{

原创 线性表的顺序表示与实现

#include <stdio.h>#include <stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1 //不能实行#define OVERFLOW -2#define LIST_INIT_SIZE 100 //顺序表初始分配空间#define LISTINCREMENT 10 //顺序表存储空间分配增量typedef int S...