16-18真题
16-18真题1. 循环双链表，结点previous,data,next和访问频度域freq,初试为0，每当链表进行一次Locate(L,x)运算时，令x结点freq域的值加1，并使其链表结点频度按递减顺序排序，并实现Locate(L,x)。123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960//1. 找到指定结点 2. 访问频度+1 3. 进行排序#include<iostream>using namespace std;const int N=100010;struct DNode{ int data; int freq; struct DNode *next; struct DNode *prior;};DNode *h;void sort(DNode *h){//根据freq降序排列，写成一个函数 DNode *p,*q,*pre; ...
12-15真题
12-15真题求数列1-1/2+1/3-1/4+…1/n123456789101112131415161718192021222324/*1. 输入n，即为终止数列的数字2. 循环判定数字，分母为奇数时，系数为正，分母为偶数时，系数为负3. 最后在循环的过程中执行数字的累加，最后输出结果*/#include<iostream>using namespace std;int main(){ int n; double total; cin>>n; for(int i=0;i<n;i++){ double flag=0; if(i%2==0){ flag=1.0; }else{ flag=-1.0; } total+=(flag)/(i+1); } cout<<"total is"<<total...
数据结构第二次习题课
数据结构第二次习题课二叉树按二叉链表形式存储 建立完全二叉树的算法 12345678910111213141516171819typedef struct BTNode{ int data; struct BTNode *lchild,*rchild;}BTNode,*BiTree;//采用先序遍历构建二叉树BiTree CreateTree(){ int x; BiTree *bt; scanf("%d",&x); if(x==0) bt=NULL; else{ bt=(BiTree)malloc(sizeof(BTNode)); bt->data=x; bt->lchild=CreateTree(); bt->rchild=CreateTree(); } return bt;} 写一个判断给定的二叉树是否是完全二叉树的算法 1234567891011121...
数据结构第一次习题课
第一次习题课阶乘和123456789101112131415161718int cal(int x){ int cal=1; for(int i=2;i<=x;i++){ cal*=x; } return cal;}int fun(LinkList L){ LNode p=L->next; int ans=0; while(p){ ans+=cal(p->data); p=p->next; }} 数组在长度为N的数组arr中，将小于等于arr[0]的数放在数组的左半部分，大于arr[0]的放在右半部分， arr[0]介于中间，输出处理后的数组 123456789101112131415161718192021222324#include<iostream>using namespace std;const int N=100010;int arr[N];int main()...
第七章排序
七、排序1.时间复杂度 平均情况下，快排，希尔排序（复杂度了解即可）、归并排序和堆排序的复杂度为O(nlog²n)，其他都是O(n²)。一个特殊的是计数排序，其复杂度为O(n*k) 最坏情况下，快速排序的为O(n²)，其他都和平均情况下相同 2.空间复杂度 快排O(nlog²n)，归并O(n)，基数O(n+k)，其他都是O(1) 快排、希尔、简单选择、堆排序是不稳定的，其余均为稳定的。 插入排序时间复杂度：最好O(n) 最坏O(n²) 平均O(n²) 空间复杂度：O(1) 稳定 直接插入排序1234567891011void InsertSort(int arr[],int n){ for(int i = 1; i < n;i++){ int t = arr[i];//t等于当前元素 int j = i;//j从当前元素开始往前看 while(j&&t < arr[j-1]){//j>0且前一个元素也是大于t的时候 arr[j] = arr[j-1...
第六章查找
六、查找顺序查找123456int Search(int a[],int n,int k){ for(int i = 1;i <= n; ++i) if(a[i] == k) return 1; return 0;} 折半查找（二分查找）时间复杂度： 12345678910111213int BSearch(int a[],int l,int r,int k){ int mid; while(l < r){ mid = (l + r) / 2; if(a[mid] == k) return mid; if(a[mid] > k) r = mid - 1; else l = mid + 1; } return 0;} 分块查找时间复杂度： 123456789101112131415161718192021222...
第五章图
第五章图邻接矩阵基本思想：vexNum表示顶点数量，arcNum表示边数量，edges表示边（1或者权值） 1234struct MGraph{ int edge[Maxn][Maxn];//存储边 edge[i][j]=MAXN 表示两个顶点不通 int vexNum,arcNum;}; 邻接表123456789101112struct ArcNode{ //边结构 int adjvex;//顶点编号一条边里 被指向的那个顶点 ArcNode *next;//指针};struct VNode{ //顶点结构 int data;//顶点信息 ArcNode *firstarc;};struct AGraph{ //表 VNode adjlist[Maxn];//存储所有顶点链表 存了所有顶点 以及他们所指向的边 int vexNum,arcNum;}; 图的遍历图的深度优先遍历思想:1.首先，访问开始结点从起始结点开始任选一个相邻并未被访问的结点，访问； 2.接着，把找到的结点作为...
第四章树和二叉树
第四章树和二叉树二叉树的存储结构1234567891011121314151617181920212223typedef int ElemType;//顺序存储结构体定义描述#define MAX_SIZE 100typedef ElemType SqBitree[MAX_SIZE];SqBiTree bt;//链式存储结构//二叉链表形式：typedef struct BTNode { ElemType data; struct BTNode *lchild,*rchild;}BTNode,*BiTree;//三叉链表形式：typedef struct BTNode{ ElemType data; struct BTNode *lchild,*rchild,*parent;}BTNode,*BiTree;void visit(BiTree T){ cout<<T->data<<" ";} 二叉树的遍历递归写法1234567891011...
