数据结构

#include <iostream>using namespace std;#define MAXSIZE 20 typedef struct{ int key; char *otherinfo;}ElemType; typedef struct{ ElemType *r; int length; }SqList; //筛选法调整堆void HeapAdjust(SqList &L,int s,int m){ ElemType rc; int j; rc=L.r[s]; for(j=2*s;j<=m;j*=2){ if(j<m&&L.r[j].key<L.r[j+1].key) ++j; if(rc.key>=L.r[j].key) break; L.r[s]=L.r[j]; s=j; } L.r[s]=rc; } void Create_Sq(SqList &L){ int i,n; cout<<"数据个数："; cin>>n; cout<<"待排序的数据："; for(i=1;i<=n;i++){ cin>>L.r[i].key; L.length++; }}//建初堆void CreatHeap(SqList &L){ int i,n; n=L.length; for(i=n/2;i>0;--i) HeapAdjust(L,i,n);} //堆排序void HeapSort(SqList &L){ int i; ElemType x; CreatHeap(L); for(i=L.length;i>1;--i){ x=L.r[1]; L.r[1]=L.r[i]; L.r[i]=x; HeapAdjust(L,1,i-1); }}void show(SqList L){ int i; for(i=1;i<=L.length;i++) cout<<L.r[i].key<<" ";}int main(){ SqList L; L.r=new ElemType[MAXSIZE+1]; L.length=0; Create_Sq(L); HeapSort(L); cout<<" 堆排序 ："; show(L);} ...

#include <iostream>using namespace std;#define MAXSIZE 20 typedef struct{ int key; char *otherinfo;}ElemType; typedef struct{ ElemType *r; int length; }SqList;//简略抉择排序 void SelectSort(SqList &L) { int i,j,k; ElemType t; for(i=1;i<L.length;++i){ k=i; for(j=i+1;j<=L.length;++j) if(L.r[j].key<L.r[k].key) k=j; if(k!=i) {t=L.r[i];L.r[i]=L.r[k];L.r[k]=t;} } } void Create_Sq(SqList &L){ int i,n; cout<<"数据个数："; cin>>n; cout<<"待排序的数据："; for(i=1;i<=n;i++){ cin>>L.r[i].key; L.length++; }}void show(SqList L){ int i; for(i=1;i<=L.length;i++) cout<<L.r[i].key<<" ";}int main(){ SqList L; L.r=new ElemType[MAXSIZE+1]; L.length=0; Create_Sq(L); SelectSort(L); cout<<"简略抉择排序："; show(L);}

#include <iostream>using namespace std;#define MAXSIZE 20 typedef struct{ int key; char *otherinfo;}ElemType; typedef struct{ ElemType *r; int length; }SqList; int Partition(SqList &L,int low,int high){ int pivotkey; L.r[0]=L.r[low]; pivotkey=L.r[low].key; while(low<high){ while(low<high&&L.r[high].key>=pivotkey) --high; L.r[low]=L.r[high]; while(low<high&&L.r[low].key<=pivotkey) ++low; L.r[high]=L.r[low]; } L.r[low]=L.r[0]; return low; }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); }} void QuickSort(SqList &L){ QSort(L,1,L.length);} void Create_Sq(SqList &L){ int i,n; cout<<"数据个数："; cin>>n; cout<<"待排序的数据："; for(i=1;i<=n;i++){ cin>>L.r[i].key; L.length++; }}void show(SqList L){ int i; for(i=1;i<=L.length;i++) cout<<L.r[i].key<<" ";}int main(){ SqList L; L.r=new ElemType[MAXSIZE+1]; L.length=0; Create_Sq(L); QuickSort(L); cout<<" 疾速排序 ："; show(L);} ...

#include <iostream>using namespace std;#define MAXSIZE 20 typedef struct{ int key; char *otherinfo;}ElemType; typedef struct{ ElemType *r; int length; }SqList; //一趟增量是dk的希尔插入排序void ShellInsert(SqList &L,int dk){ int i,j; for(i=dk+1;i<=L.length;++i) if(L.r[i].key<L.r[i-dk].key){ L.r[0]=L.r[i]; 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]; } }void show(SqList L){ int i; for(i=1;i<=L.length;i++) cout<<L.r[i].key<<" "; cout<<endl; }//t趟希尔排序void ShellSort(SqList &L,int dt[ ],int t){ int k; for(k=0;k<t;++k){ ShellInsert(L,dt[k]); show(L); } } void Create_Sq(SqList &L){ int i,n; cout<<"数据个数："; cin>>n; cout<<"待排序的数据："; for(i=1;i<=n;i++){ cin>>L.r[i].key; L.length++; }}int main(){ SqList L; L.r=new ElemType[MAXSIZE+1]; L.length=0; Create_Sq(L); int i,t; int *dt=new int[MAXSIZE]; cout<<"总趟数："; cin>>t; for(i=0;i<t;i++){ cout<<"第"<<i+1<<"趟增量："; cin>>dt[i]; } cout<<"希尔排序：\n"; ShellSort(L,dt,t);} ...

#include <iostream>using namespace std;#define MAXSIZE 20 typedef struct{ int key; char *otherinfo;}ElemType; typedef struct{ ElemType *r; int length; }SqList;//折半插入排序 void BInsertSort(SqList &L){ int i,j,low,high,m; for(i=2;i<=L.length;++i){ L.r[0]=L.r[i]; low=1; high=i-1; while(low<=high){ m=(low+high)/2; if(L.r[0].key<L.r[m].key) high=m-1; else low=m+1; } for(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0]; } } void Create_Sq(SqList &L){ int i,n; cout<<"数据个数："; cin>>n; cout<<"待排序的数据："; for(i=1;i<=n;i++){ cin>>L.r[i].key; L.length++; }}void show(SqList L){ int i; for(i=1;i<=L.length;i++) cout<<L.r[i].key<<" ";}int main(){ SqList L; L.r=new ElemType[MAXSIZE+1]; L.length=0; Create_Sq(L); BInsertSort(L); cout<<"折半插入排序："; show(L);} ...

#include <iostream>using namespace std;#define MAXSIZE 20 typedef struct{ int key; char *otherinfo;}ElemType; typedef struct{ ElemType *r; int length; }SqList; //间接插入排序void InsertSort(SqList &L){ int i,j; for(i=2;i<=L.length;++i) if(L.r[i].key<L.r[i-1].key){ L.r[0]=L.r[i]; L.r[i]=L.r[i-1]; for(j=i-2; L.r[0].key<L.r[j].key;--j) L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0]; } } void Create_Sq(SqList &L){ int i,n; cout<<"数据个数："; cin>>n; cout<<"待排序的数据："; for(i=1;i<=n;i++){ cin>>L.r[i].key; L.length++; }}void show(SqList L){ int i; for(i=1;i<=L.length;i++) cout<<L.r[i].key<<" ";}int main(){ SqList L; L.r=new ElemType[MAXSIZE+1]; L.length=0; Create_Sq(L); InsertSort(L); cout<<"间接插入排序："; show(L);}

#include <iostream>using namespace std;#define MVNum 100 #define MAXQSIZE 100 typedef char VerTexType; typedef int ArcType; bool visited[MVNum]; typedef struct{ VerTexType vexs[MVNum]; ArcType arcs[MVNum][MVNum]; int vexnum,arcnum; }Graph;typedef struct{ ArcType *base; int front; int rear; }sqQueue;void InitQueue(sqQueue &Q){ Q.base = new ArcType[MAXQSIZE]; if(!Q.base) exit(1); Q.front = Q.rear = 0;}void EnQueue(sqQueue &Q, ArcType e){ if((Q.rear + 1) % MAXQSIZE == Q.front) return; Q.base[Q.rear] = e; Q.rear = (Q.rear + 1) % MAXQSIZE;}bool QueueEmpty(sqQueue Q){ if(Q.rear == Q.front) return true; return false;}void DeQueue(sqQueue &Q, ArcType &u){ u = Q.base[Q.front]; Q.front = (Q.front + 1) % MAXQSIZE;} int LocateVex(Graph G , VerTexType v){ for(int i = 0; i < G.vexnum; ++i) if(G.vexs[i] == v) return i; return -1;}//创立无向图 void CreateUDG(Graph &G){ int i , j , k; cout <<"总顶点数 总边数："; cin >> G.vexnum >> G.arcnum; for(i = 0; i < G.vexnum; ++i){ cout << "第" << (i+1) << "个点的名称："; cin >> G.vexs[i]; } for(i = 0; i < G.vexnum; ++i) for(j = 0; j < G.vexnum; ++j) G.arcs[i][j] = 0; for(k = 0; k < G.arcnum;++k){ VerTexType v1 , v2; cout << "第" << (k + 1) << "条边附丽的顶点："; cin >> v1 >> v2; i = LocateVex(G, v1); j = LocateVex(G, v2); G.arcs[j][i] = G.arcs[i][j] = 1; }}int FirstAdjVex(Graph G , int v){ int i; for(i = 0 ; i < G.vexnum ; ++i){ if(G.arcs[v][i] == 1 && visited[i] == false) return i; } return -1;}int NextAdjVex(Graph G , int u , int w){ int i; for(i = w ; i < G.vexnum ; ++i){ if(G.arcs[u][i] == 1 && visited[i] == false) return i; } return -1;}//广度优先遍历void BFS (Graph G, int v){ sqQueue Q; ArcType u; ArcType w; cout << G.vexs[v]; visited[v] = true; InitQueue(Q); EnQueue(Q, v); while(!QueueEmpty(Q)){ DeQueue(Q, u); for(w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)){ if(!visited[w]){ cout << G.vexs[w]; visited[w] = true; EnQueue(Q, w); } } }}int main(){ Graph G; CreateUDG(G); cout << "遍历无向图的起始点："; VerTexType c; cin >> c; int i; for(i = 0 ; i < G.vexnum ; ++i){ if(c == G.vexs[i]) break; } cout << "广度优先搜寻遍历无向图："; BFS(G , i); return 0;} ...

#include <iostream>using namespace std;#define MVNum 100 typedef char VerTexType; typedef int ArcType; typedef struct{ VerTexType vexs[MVNum]; ArcType arcs[MVNum][MVNum]; int vexnum,arcnum; }Graph;bool visited[MVNum]; int LocateVex(Graph G , VerTexType v){ for(int i = 0; i < G.vexnum; ++i) if(G.vexs[i] == v) return i; return -1;}//创立无向图 void CreateUDG(Graph &G){ int i , j , k; cout <<"总顶点数 总边数："; cin >> G.vexnum >> G.arcnum; for(i = 0; i < G.vexnum; ++i){ cout << "第" << (i+1) << "个点的名称："; cin >> G.vexs[i]; } for(i = 0; i < G.vexnum; ++i) for(j = 0; j < G.vexnum; ++j) G.arcs[i][j] = 0; for(k = 0; k < G.arcnum;++k){ VerTexType v1 , v2; cout << "第" << (k + 1) << "条边附丽的顶点："; cin >> v1 >> v2; i = LocateVex(G, v1); j = LocateVex(G, v2); G.arcs[j][i] = G.arcs[i][j] = 1; }}//深度优先遍历 void DFS(Graph G, int v){ int w; cout << G.vexs[v]; visited[v] = true; for(w = 0; w < G.vexnum; w++) if((G.arcs[v][w] != 0)&& (!visited[w])) DFS(G, w); }int main(){ Graph G; CreateUDG(G); cout << "遍历无向图的起始点："; VerTexType c; cin >> c; int i; for(i = 0 ; i < G.vexnum ; ++i){ if(c == G.vexs[i]) break; } cout << "深度优先遍历无向图："; DFS(G , i); return 0;} ...

#include <iostream>using namespace std;#define MaxInt 32767 #define MVNum 100 #define OK 1 typedef char VerTexType; typedef int ArcType; typedef struct{ VerTexType vexs[MVNum]; ArcType arcs[MVNum][MVNum]; int vexnum,arcnum; }AMGraph;int LocateVex(AMGraph G , VerTexType v){ for(int i = 0; i < G.vexnum; ++i) if(G.vexs[i] == v) return i; return -1;}//创立无向网int CreateUDN(AMGraph &G){ int i , j , k; cout <<"总顶点数 总边数："; cin >> G.vexnum >> G.arcnum; for(i = 0; i < G.vexnum; ++i){ cout << "第" << (i+1) << "个点的名称："; cin >> G.vexs[i]; } for(i = 0; i < G.vexnum; ++i) for(j = 0; j < G.vexnum; ++j) G.arcs[i][j] = MaxInt; for(k = 0; k < G.arcnum;++k){ VerTexType v1 , v2; ArcType w; cout << "第" << (k + 1) << "条边附丽的顶点及权值:"; cin >> v1 >> v2 >> w; i = LocateVex(G, v1); j = LocateVex(G, v2); G.arcs[i][j] = w; G.arcs[j][i] = G.arcs[i][j]; } return OK; }int main(){ AMGraph G; int i , j; CreateUDN(G); for(i = 0 ; i < G.vexnum ; ++i){ for(j = 0; j < G.vexnum; ++j){ if(j != G.vexnum - 1){ if(G.arcs[i][j] != MaxInt) cout << G.arcs[i][j] << "\t"; else cout << "∞" << "\t"; } else{ if(G.arcs[i][j] != MaxInt) cout << G.arcs[i][j] <<endl; else cout << "∞" <<endl; } } } return 0;}` ...

#include<iostream>#include<string.h>using namespace std;typedef struct{ int weight; int parent,lchild,rchild;}HTNode,*HuffmanTree;void Select(HuffmanTree HT,int len,int &s1,int &s2){ int i,min1=0x3f3f3f3f,min2=0x3f3f3f3f; for(i=1;i<=len;i++){ if(HT[i].weight<min1&&HT[i].parent==0){ min1=HT[i].weight; s1=i; } } int temp=HT[s1].weight; HT[s1].weight=0x3f3f3f3f; for(i=1;i<=len;i++){ if(HT[i].weight<min2&&HT[i].parent==0){ min2=HT[i].weight; s2=i; } } HT[s1].weight=temp;}//结构赫夫曼树void CreatHuffmanTree(HuffmanTree &HT,int n){ int m,s1,s2,i; if(n<=1) return; m=2*n-1; HT=new HTNode[m+1]; for(i=1;i<=m;++i){ HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } cout<<"叶子结点权值："; for(i=1;i<=n;++i) cin>>HT[i].weight; for(i=n+1;i<=m;++i){ Select(HT,i-1,s1,s2); HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2 ; HT[i].weight=HT[s1].weight+HT[s2].weight; } } typedef char **HuffmanCode; //赫夫曼编码 void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n){ int i,start,c,f; HC=new char*[n+1]; char *cd=new char[n]; cd[n-1]='\0'; for(i=1;i<=n;++i){ start=n-1; c=i; f=HT[i].parent; while(f!=0){ --start; if(HT[f].lchild==c) cd[start]='0'; else cd[start]='1'; c=f; f=HT[f].parent; } HC[i]=new char[n-start]; strcpy(HC[i], &cd[start]); } delete cd; } void show(HuffmanTree HT,HuffmanCode HC,int n){ for(int i=1;i<=n;i++) cout<<HT[i].weight<<"赫夫曼编码为："<<HC[i]<<endl;} int main(){ HuffmanTree HT; int n; cout<<"叶子结点个数："; cin>>n; CreatHuffmanTree(HT,n); HuffmanCode HC; CreatHuffmanCode(HT,HC,n); show(HT,HC,n);} ...

#include<iostream>using namespace std;typedef struct BiNode{ char data; struct BiNode *lchild,*rchild;}BiTNode,*BiTree;//先序建设二叉链表void CreateBiTree(BiTree &T){ char ch; cin >> ch; if(ch=='#') T=NULL; else{ T=new BiTNode; T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); }}//链栈typedef struct StackNode{ BiTNode data; struct StackNode *next;}StackNode,*LinkStack;//结构空栈Svoid InitStack(LinkStack &S){ S=NULL;}bool StackEmpty(LinkStack S){ if(!S) return true; return false;}//入栈 void Push(LinkStack &S,BiTree e){ StackNode *p=new StackNode; p->data=*e; p->next=S; S=p;}//出栈 void Pop(LinkStack &S,BiTree e){ if(S!=NULL){ *e=S->data; StackNode *p=S; S=S->next; delete p; }} //中序遍历 void In(BiTree T){ LinkStack S; BiTree p; BiTree q=new BiTNode; InitStack(S); p=T; while(p||!StackEmpty(S)){ if(p){ Push(S,p); p=p->lchild; } else{ Pop(S,q); cout<<q->data; p=q->rchild; } } } //先序遍历 void Pre(BiTree T){ LinkStack S; BiTree p; BiTree q=new BiTNode; InitStack(S); p=T; while(p||!StackEmpty(S)){ if(p){ Push(S,p); cout<<p->data; p=p->lchild; } else{ Pop(S,q); p=q->rchild; } } }int main(){ BiTree tree; cout<<"先序建设二叉链表："; CreateBiTree(tree); cout<<"先序遍历的后果为："; Pre(tree); cout<<endl; cout<<"中序遍历的后果为："; In(tree); cout<<endl;} ...

#include<iostream>using namespace std;typedef struct BiNode{ char data; struct BiNode *lchild,*rchild;}BiTNode,*BiTree;//先序建设二叉链表void CreateBiTree(BiTree &T){ char ch; cin >> ch; if(ch=='#') T=NULL; else{ T=new BiTNode; T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); }}//先序遍历 void Pre(BiTree T){ if(T){ cout<<T->data; Pre(T->lchild); Pre(T->rchild); }}//中序遍历 void In(BiTree T){ if(T){ In(T->lchild); cout<<T->data; In(T->rchild); }}//后序遍历 void Post(BiTree T){ if(T){ Post(T->lchild); Post(T->rchild); cout<<T->data; }}int main(){ BiTree tree; cout<<"先序建设二叉链表："; CreateBiTree(tree); cout<<"先序遍历的后果为："; Pre(tree); cout<<endl; cout<<"中序遍历的后果为："; In(tree); cout<<endl; cout<<"后序遍历的后果为："; Post(tree); cout<<endl;}

线程池概念线程池就是首先创立一些线程，它们的汇合称为线程池。应用线程池能够很好的进步性能，线程池在系统启动时创立大量闲暇的线程，当工作池有工作时，线程池中的线程排队去支付工作池的工作，如果以后没有工作就阻塞期待。 工作机制在有线程池的状况下，工作是交给线程池而不是间接交给某个线程，在线程池拿到工作后，寻找是否有闲暇的线程，如果有就交付给该线程执行。一个线程，只能同时执行一个工作，执行结束后，线程重回闲暇状态，期待下一个工作。应用线程池的起因多线程运行工夫，零碎一直启动和敞开线程，老本很高，会适度耗费线程资源，以及适度切换线程的危险，从而导致系统资源的解体。 图解线程池 代码线程池构造typedef struct NMANAGER{ struct NWORKER *workers; // 治理的线程链表头节点 struct NJOBS *jobs; //工作池头节点 int totWorkers; // 以后一共领有多少线程 int idleWorkers; // 以后闲暇线程数量 pthread_mutex_t pool_mtx; // 线程池互斥锁 pthread_cond_t pool_cond; // 线程池条件锁，所有线程期待这个条件锁} nManager;线程构造typedef struct NWORKER{ pthread_t pthreadid; //该线程的线程id struct NMANAGER *pool; // 处于哪一个线程池 int terminate; // 是否被终止,1为销毁该线程，0则相同 struct NWORKER *next; //链表中的下一个线程 struct NWORKER *prev;//链表中的上一个线程} nWorker;工作池typedef struct NJOBS{ void (*func)(void *arg); //工作回调，线程执行该工作 void *user_data; // 工作的参数 struct NJOBS *next; //工作池的下一个工作 struct NJOBS *prev; // 工作池上一个工作} nJobs;线程池的创立int ThreadPoolCreate(threadpool *pool, int numsThread){ //1. 初始化线程池相干属性 //2. 创立肯定数量线程，扔进线程池 if (pool == NULL) { printf("create error\n"); return 1; } if (numsThread <= 0) numsThread = 1; memset(pool, 0, sizeof(nManager)); pool->totWorkers = 0; pool->idleWorkers = 0; pthread_mutex_init(&pool->pool_mtx, NULL); pthread_cond_init(&pool->pool_cond, NULL); //pool->pool_mtx = PTHREAD_MUTEX_INITIALIZER; pthread_t managerpid; pthread_create(&managerpid, NULL, ManagerThread, (void *)pool); pthread_detach(managerpid); int i = 0; for (i = 0; i < numsThread; i++) { nWorker *worker = (nWorker *)malloc(sizeof(nWorker)); if (worker == NULL) { printf("worker error\n"); return 1; } memset(worker, 0, sizeof(nWorker)); int ret = pthread_create(&worker->pthreadid, NULL, ThreadWorking, worker); if (ret) { perror("pthread create"); return 1; } pthread_detach(worker->pthreadid); worker->terminate = 0; worker->pool = pool; LIST_ADD(worker, pool->workers); // 扔进线程池 pthread_mutex_lock(&pool->pool_mtx); pool->totWorkers++; // 总共线程减少 pool->idleWorkers++; // 闲暇线程 pthread_mutex_unlock(&pool->pool_mtx); } return 0;}销毁线程池void ThreadPoolDestroy(threadpool *pool){ nWorker *w = pool->workers; for (w = pool->workers; w != NULL; w = w->next) { w->terminate = 1; // 令teminate = 1 ，在线程的执行函数中，会本人把本人给覆灭，耦合度低。 } pthread_mutex_lock(&pool->pool_mtx); pthread_cond_broadcast(&pool->pool_cond); // 告诉所有期待条件锁的线程，没有期待的线程执行完工作之后，会自行销毁 pthread_mutex_unlock(&pool->pool_mtx); free(pool);}线程池增加工作void ThreadPushJob(threadpool *pool, nJobs *job){ pthread_mutex_lock(&pool->pool_mtx); LIST_ADD(job, pool->jobs); // 向线程池增加工作 printf("add jobs in pool\n"); pthread_cond_signal(&pool->pool_cond); // 告诉一个线程来工作了 pthread_mutex_unlock(&pool->pool_mtx);}线程执行函数void *ThreadWorking(void *arg){ nWorker *worker = (nWorker *)arg; while (1) { pthread_mutex_lock(&worker->pool->pool_mtx); while (worker->pool->jobs == NULL) { printf("work waiting------\n"); if (worker->terminate == 1) { //该线程被销毁 break; } pthread_cond_wait(&worker->pool->pool_cond, &worker->pool->pool_mtx); //等到工作池有工作 ， //在这个函数之前解锁，而后阻塞在该条件变量上，该函数之后加上相应的互斥锁 } if (worker->terminate == 1) { pthread_mutex_unlock(&worker->pool->pool_mtx); break; } nJobs *jobs = worker->pool->jobs; LIST_DEL(jobs, worker->pool->jobs); //把该工作从工作池取下来 pthread_mutex_unlock(&worker->pool->pool_mtx); // 当初容许其余线程来工作池取工作啦 pthread_mutex_lock(&worker->pool->pool_mtx); worker->pool->idleWorkers--; // 闲暇线程减一 pthread_mutex_unlock(&worker->pool->pool_mtx); printf("working -------\n"); jobs->func(jobs->user_data); //执行该工作的回调函数 pthread_mutex_lock(&worker->pool->pool_mtx); worker->pool->idleWorkers++; //闲暇线程加一 pthread_mutex_unlock(&worker->pool->pool_mtx); free(jobs); // 开释该工作内存 } // 销毁该线程，同时批改与该线程相干的信息 pthread_mutex_lock(&worker->pool->pool_mtx); worker->pool->totWorkers--; worker->pool->idleWorkers--; LIST_DEL(worker, worker->pool->workers); // 从线程池中取出 pthread_mutex_unlock(&worker->pool->pool_mtx); free(worker); // 开释 pthread_exit(NULL);}剩下问题目前线程池不反对，动静的放大和扩张。个别闲暇线程过多的时候，咱们思考缩小线程池容量，忙线程多的时候，咱们思考减少线程。在线程池的构造体中曾经有了总共线程个数和休闲线程个数，能够应用这个两个进行编写相应程序。线程池大小问题，咱们能够应用一个线程：管理者线程来保护线程池的大小.

二叉树遍历算法的改良二叉树的深度优先遍历算法都是用递归函数实现的，这是很低效的，起因在于零碎帮你调用了一个栈并做了诸如爱护现场和复原现场等简单的操作，才使得遍历能够用十分简洁的代码实现。二叉树深度优先遍历算法的非递归实现用用户定义的栈来代替零碎栈，也就是用非递归的形式来实现遍历算法，能够失去不小的效率晋升。 二叉树深度优先遍历算法的非递归实现（1）先序遍历非递归算法要写出其遍历的非递归算法，其次要工作是用本人定义的栈来代替零碎栈的性能。 以图1所示的二叉树为例，过程为图二所示 初态栈空 结点1入栈。出栈，输入栈顶结点1，并将1的左、右孩子结点（2和4）入栈；右孩子先入栈，左孩子后入栈，因为对左孩子的拜访要先于右孩子，后入栈的会先出栈拜访。出栈，输入栈顶结点2，并将2的左、右孩子结点（3和5）入栈。出栈，输入栈顶结点3，3为叶子结点，无孩子，本步无结点入栈。出栈，输入栈顶结点5。出栈，输入栈顶结点4，此时栈空，进入终态。 遍历序列为1，2，3，5，4。 代码如下 void preorderNonrecursion(BTNode *bt){ if(bt != NULL) { BTNode *Stack[maxSize]; //定义一个栈 int top = -1; //初始化栈 BTNode *p; Stack[++top] = bt; //根结点入栈 while(top != -1) //栈空循环完结 { p = Stack[top--]; //出栈并输入栈顶结点 Visit(p); //Visit()为拜访p的函数 if(p->rchild != NULL) //栈顶结点的右孩子存在，则右孩子入栈 Stack[++top] = p->rchild; if(p->lchild != NULL) //栈顶结点的左孩子存在，则左孩子入栈 Stack[++top] = p->lchild; } }}（2）中序遍历非递归算法相似于先序遍历，对图1中的二叉树进行中序遍历，各个结点进栈、出栈过程如图3所示。 初态栈空。 结点1入栈，1左孩子存在。结点2入栈，2左孩子存在。结点3入栈，3左孩子不存在。出栈，输入栈顶结点3，3右孩子不存在。出栈，输入栈顶结点2，2右孩子存在，右孩子5入栈，5左孩子不存在。出栈，输入栈顶结点5，5右孩子不存在。出栈，输入栈顶结点1，1右孩子存在，右孩子4入栈，4左孩子不存在。出栈，输入栈顶结点4，此时栈空，进入终态。 遍历序列为3，2，5，1，4。 由以上步骤能够看出，中序非递归遍历过程如下： 开始根结点入栈循环执行如下操作：如果栈顶结点左孩子存在，则左孩子进栈；如果栈顶结点左孩子不存在，则出栈并输入栈顶结点，而后查看其右孩子是否存在，如果存在，则右孩子入栈。当栈空时算法完结。代码如下 void inorderNonrecursion(BTNode *bt){ if(bt != NULL) { BTNode *Stack[maxSize]; int top = -1; BTNode *p; p = bt; /*下边循环实现中序遍历。留神：图3进栈、出栈过程在7中会呈现栈空状态，然而这时遍历还没有完结，因根结点的右子树还没有遍历，此时p非空，依据这一点来维持循环的进行*/ while(top != -1 || p != NULL) { while(p != NULL) //左孩子存在，则左孩子入栈 { Stack[++top] = p; p = p->lchild; } if(top != -1) //在栈不空的状况下出栈并输入出栈结点 { p = Stack[top--]; Visit(p); p = p->rchild; } } }}（3）后序遍历非递归算法首先写出图1中二叉树进行先序遍历和后序遍历的序列。 ...

标签：二分 题目：x的平方根 题号：69 题干：实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。因为返回类型是整数，后果只保留整数的局部，小数局部将被舍去 示例1： 输出: 4输入: 2 示例2： 输出: 8 输入: 2 解释: 8的平方根是 2.82842..., 因为返回类型是整数，小数局部将被舍去 原题比较简单，因而这里做简略的变形，求x的平方根，要求能够获取指定精度的后果 示例：输出：8 0.000001输入：2.828427阐明：0.000001示意准确到小数点后六位思路： 要求x的平方根，最容易想到的就是从1到x，一个一个的试，这种办法的工夫复杂度是O(n)，这不是咱们想要的二分查找算法，显然是用来查找的算法，咱们的目标也算是查找。如果你看过我的上一篇二分查找的文章，里边有说到什么状况下会想到用二分查找，比方咱们要查找的一系列数是有序的等，咱们要求x的平方根，那必定在[1, x]这个区间找（x>1），它显然是有序的。这天然 会想到用二分来查找应用二分查找算法，须要两个游标low和high。须要思考他们的初始值是什么？以及当mid不满足时，low和hight如何变动？既然是求x的平方根，x的值有两种状况。第一种是x<1，这种状况，咱们要求的后果必定在[0, 1]这区间内，所以就能够初始化low = 0，hight=1，那mid就为(low+hight)/2x的第二种状况就很简略了，当x>1时，它的平方根的值必定在[1, n]区间内，所以low = 1， high=x，mid = (low+hight)/2不难想到，当x-mid*mid < 0时，阐明mid太大，那此时咱们就应该在[1, mid]之间找，即，此时让hight=mid-1如果x-midmid > 0，这时要思考x-midmid是否大于咱们要求的精度，如果大于这个精度，那此时low = mid+1有了以上这些条件，基本上这道题就进去了。如果你依照上边的思路把代码写进去之后会发现是有问题的，当x<1的时候程序就不能失常运行了。起因是low和high变动的时候，如果x<1的时候，后果必定是小于1的，如果间接让high或low为mid加1或减1必定就不对了因而，当x-mid*mid < 0时，应该让high=(mid+high)/2代码实现 func SolutionSqrt(num float64, precision float64) float64 { if num < 0 { fmt.Println("参数不非法") return -1.000 } var low,high float64 if num > 1 { low = 1 high = num } else { low = num high = 1 } return Sqrt(num, low, high, precision)}func Sqrt(num float64, low float64, high float64, precision float64) float64 { mid := (low+high) / 2 if num - (mid * mid) < 0 { return Sqrt(num, low, (mid+high)/2, precision) } else { if num - (mid * mid) > precision { return Sqrt(num, (low + mid)/2, high, precision) } return mid }}

二叉树遍历算法二叉树的存储构造typedef struct BTNode{ char data; //这里默认结点data为char型 struct BTNode *lchild; struct BTNode *rchild;}BTNode;二叉树的遍历算法1 先序遍历先序遍历的操作如下。 如果二叉树为空树，则什么都不做；否则： 1）拜访根节点 2）先序遍历左子树 3）先序遍历右子树 形容如下： void preorder(BTNode *p){ if(p != NULL) { visit(p); //假如拜访函数Visit()曾经定义过 preorder(p->lchild); //先序遍历左子树 preorder(p->rchild); //先序遍历右子树 }}2 中序遍历中序遍历的操作如下。 如果二叉树为空树，则什么都不做；否则： 1）中序遍历左子树 2）拜访根节点 3）中序遍历右子树 形容如下： void inorder(BTNode *p){ if(p != NULL) { inorder(p->lchild); visit(p); inorder(p->rchild); }}3 后序遍历后序遍历的操作如下。 如果二叉树为空树，则什么都不做；否则： 1）后序遍历左子树 2）后序遍历右子树 3）拜访根节点 形容如下： void postorder(BTNode *p){ if(p != NULL) { postorder(p->lchild); postorder(p->rchild); visit(p); }}4 档次遍历<img src="https://irabbit756.oss-cn-shanghai.aliyuncs.com/数据结构/二叉树遍历/1二叉树档次遍历.png" style="zoom: 67%;" /> ...

字符贮存在1~length的地位上 简略模式匹配 思路：从主串的第一个地位起和模式串的第一个字符开始比拟，如果相等，则持续逐个比拟后续字符；否则从主串的第二个字符开始，再从新用上一步的办法与模式串中的字符做比拟，以此类推，直到比拟完模式串中的所有字符。若匹配胜利，则返回模式串在主串中的地位；若匹配不胜利，则返回一个可区别于主串所有地位的标记，如“0”。 int index(Str str,Str substr){ int i = 1,j = 1,k = 1;//串从数组下标1地位开始存储，初值为1 while(i <= str.length && j <= substr.length) { if(str.ch[i] == substr[j]) { i++； j++; } else { j = 1; i = ++k;//匹配失败，i从主串的下一个地位开始匹配，k贮存了主串上一次的起始地位 } } if(j > substr.length) return k; else ruturn 0;}主串（ABABCABCACBAB)和模式串(ABCAC)匹配过程 KMP算法 设主串为s1s2...sn,模式串为p1p2...pm，在下面的匹配过程中，经常出现一个要害状态（表2），其中i和j别离为主串和模式串中以后参加比拟的两个字符的下标。 模式串的前部某子串P1P2...Pj-1与主串中的一个子串Si-j+1Si-j+2...Si-1匹配，而Pj与Si不匹配。每当呈现这种状态时，简略模式匹配算法的做法是:一律将i赋值为i-j+2，j赋值为1，从新开始比拟。这个过程反映到表2中能够形象地示意为模式串先向后挪动一个地位，而后从第一个字符P1开始一一和以后主串中对应的字符做比拟；当再次发现不匹配时，反复上述过程。这样做的目标是试图打消Si处的不匹配，进而开始Si+1及其当前字符的比拟，使得整个过程得以推动上来。 如果在模式串后移的过程中又呈现了其前部某子串P1P2…与主串中某子串…Si-2Si-1相匹配的状态，则认为这是一个提高的状态。因为通过模式串后移排除了一些不可能匹配的状态，来到了一个新的部分匹配状态，并且此时Si有了和模式串中对应字符匹配的可能性。为了不便表述，记表中形容的状态为Sk，此处的新状态为Sk+1，此时能够将简略模式匹配过程看成一个由Sk向Sk+1推动的过程。当由Sk来到Sk+1时有两种状况可能产生:其一，S处的不匹配被解决，从si+1持续往下比拟，若来到新的不匹配字符地位，则模式串后移寻找状态Sk+2；其二，Si处的不匹配依然存在，则模式串持续后移寻找状态Sk+2如此进行上来，直到失去最终后果。 阐明:为了使上边其一与其二的表述看起来清晰工整且抓住重点，此处省略了对匹配胜利与失败这两种容易了解的状况的形容。 阐明:模式串后移使P1挪动到Si+1，即模式串整个移过Si的状况也认为是Si处的不匹配被解决。试想，如果在匹配过程中能够省略掉模式串逐步后移的过程，而从Sk间接跳到Sk+1，则能够大大提高匹配效率。带着这个想法，咱们把Sk+1状态增加到表2中失去表3。 察看发现，P1P2...Pj-1和Si-j+1Si-j+2...Si-1是完全相同的，且咱们钻研的是从Sk跳到Sk+1，因而，删除表3对于主串的一行，失去表4。 由表4可知，P1P2...Pt-1和Pj-t+1Pj-t+2...Pj-1匹配。记P1P2..Pj-1为F，记P1P2...Pt-1为FL，记Pj-t+1Pj-t+2...Pj-1为FR。所以，只需将F后移到使得FL和FR重合的地位（上表有色部位），即可实现Sk间接跳到Sk+1。 ...

上一篇文章中分享了冒泡排序、插入排序、抉择排序这三种排序算法，它们的工夫复杂度都是O(n^2)，比拟高，适宜小规模数据的排序。这篇文章，分享两种工夫复杂度为O(nlogn)的排序算法，归并排序和疾速排序。这两种排序算法适宜大规模的数据排序，更加的罕用一些 归并排序归并排序思维归并排序核心思想：将待排序的数据分成前后两个局部，而后对前后两个局部的数据别离进行排序，再将前后两局部合并，失去的后果就是排好序的数据了 语言很形象，看图 归并排序应用的就是分治思维。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了 分治思维跟之前的一篇文章中的递归很像，然而，分治是一种解决问题的解决思维，递归是一种编程技巧。归并排序用的是分治思维，能够用递归来实现 归并排序实现如果你看过上一篇递归的文章，上边有介绍到，解递归问题，要剖析出递归公式，而后找到递归终止条件，有了这两个，基本上递归代码就进去了。有了上边的那个图，基本上能够失去下边的递推公式 递归公式MergeSort(start, end) = merge(MergeSort(start,(start+end)/2), MergeSort((start+end)/2 + 1, end))递归终止条件start >= endMergeSort(start, end)示意的是给下标start到end之间的数组中的数据进行排序，将这个这个排序分成了两个子问题，一个是MergeSort(start,(start+end)/2)，另一个是MergeSort((start+end)/2 + 1), end)，当把这两个子问题排好序之后，再将它们合并，就把下标start到end之间的数据排好序了 最外层的那个merge就是对两个曾经有序的数组进行合并，具体过程如下：用两个游标i和j，别离指向两个待merge数组(arr)的第一个元素（这两个数组各自是有序的），比拟游标对应地位元素的大小。如果arr[i]<arr[j]，则将arr[i]放入到一个新的数组中tmp，而后i向后挪动一位，否则，将a[j]放入tmp中，j向后一位。反复以上过程，直到有一个子数组空了，而后把另一个子数组中的数据追加到tmp的尾部，以上过程，即可将两个别离有序的数组合并成一个有序数组。具体过程如图： 代码实现 func MergeSort(arr []int) []int { if len(arr) <= 0 { fmt.Println("参数不非法") return nil } //递归终止条件，当拆分后的数组长度少于两个元素的时候 if len(arr) < 2 { return arr } midIndex := len(arr) / 2 leftArr := MergeSort(arr[0:midIndex]) rightArr := MergeSort(arr[midIndex:]) result := merge(leftArr, rightArr) return result}func merge(leftArr, rightArr []int) []int { var mergeRes []int leftIndex, rightIndex := 0, 0 leftLength, rightLength := len(leftArr), len(rightArr) for leftIndex < leftLength && rightIndex < rightLength { if leftArr[leftIndex] > rightArr[rightIndex] { mergeRes = append(mergeRes, rightArr[rightIndex]) rightIndex++ } else { mergeRes = append(mergeRes, leftArr[leftIndex]) leftIndex++ } } if leftIndex == leftLength{ for rightIndex < rightLength { mergeRes = append(mergeRes, rightArr[rightIndex]) rightIndex++ } } if rightIndex == rightLength { for leftIndex < leftLength { mergeRes = append(mergeRes, leftArr[leftIndex]) leftIndex++ } } return mergeRes}归并排序性能剖析首先归并排序是稳固排序算法，这个次要取决于merge操作，也就是将两个有序数组合并成一个有序数组。在合并的过程中，当两个数组中有雷同的元素时，先把前边那局部数组中元素放入到tmp中，这样就能够保障雷同的元素，在合并前后程序不变 ...

1. 特色不肯定是齐全二叉树肯定是温和二叉树叶子结点存储的是理论的值，非叶子结点存的是自定义的内容2. 工夫复杂度操作工夫复杂度查问O(logn)3. 线段树的图解 4. 代码<?php/** * content: 线段树（区间树） * create: 2020-11-12 */namespace HeapBundle;use ArrayBundle\BaseArray;class SegmentTreeHeap{ /** * 传入的数组对象 * @var BaseArray */ protected $array; /** * 数组 * @var array */ protected $tree = []; public function __construct(BaseArray $array) { $this->array = $array; $this->build(0, 0, $this->array->getSize() - 1); } /** * 构建线段树 * @param int $treeIndex * @param int $min * @param int $max * @throws \Exception */ public function build(int $treeIndex, int $min, int $max) { // 如果线段区间的最小值和最小值雷同，则示意为叶子结点 if ($min == $max) { $this->tree[$treeIndex] = $this->array->get($max); return; } // 四舍五入取两头值 最大值减最小值而后除以2拿到两头值，并加上最小值 $mid = floor(($max - $min) / 2) + $min; // 获取左儿子的索引值，并递归往下构建 $leftIndex = $this->leftChildIndex($treeIndex); $this->build($leftIndex, $min, $mid); // 获取右儿子的索引值，并递归往下构建 $rightIndex = $this->rightChildIndex($treeIndex); $this->build($rightIndex, $mid + 1, $max); // 非叶子结点的值保留的是它上面所有结点的相加值, 这里能够改为它上面结点的总和值 $this->tree[$treeIndex] = $this->tree[$leftIndex] . '+' . $this->tree[$rightIndex]; } /** * 打印线段树 */ public function varDump() { ksort($this->tree); print_r($this->tree); } /** * 获取线段树的长度 * @return int */ public function getSize(): int { return count($this->tree); } /** * 获取左儿子索引 * @param int $parentIndex * @return int * @throws \Exception */ public function leftChildIndex(int $parentIndex): int { if ($parentIndex < 0) throw new \Exception('父结点的索引不能小于0'); return $parentIndex * 2 + 1; } /** * 获取右儿子索引 * @param int $parentIndex * @return int * @throws \Exception */ public function rightChildIndex(int $parentIndex): int { if ($parentIndex < 0) throw new \Exception('父结点的索引不能小于0'); return $parentIndex * 2 + 2; }}5.示例<?phprequire_once __DIR__ . '/../../vendor/autoload.php';$array = new ArrayBundleBaseArray();for ($i = 0; $i < 10; $i++) { $array->addLast($i + 10);}$heap = new HeapBundleSegmentTreeHeap($array);$heap->varDump();Array( [0] => 10+11+12+13+14+15+16+17+18+19 [1] => 10+11+12+13+14 [2] => 15+16+17+18+19 [3] => 10+11+12 [4] => 13+14 [5] => 15+16+17 [6] => 18+19 [7] => 10+11 [8] => 12 [9] => 13 [10] => 14 [11] => 15+16 [12] => 17 [13] => 18 [14] => 19 [15] => 10 [16] => 11 [23] => 15 [24] => 16)

用数组实现最大/小堆，有两种形式，一种是Array[0]不存理论值，另一种是Array[0]存理论值。第一种的话，数组长度比堆结点数多1，因为[0]是没有存任何结点的,对于i的左右子结点为2i和2i + 1，父节点为(i - 1)/2;第二种的话，数组长度等于堆结点数，因为[0]是根结点的,对于i的左右子结点为2i + 1和2i + 2，父节点为i/2。这里以最大堆为例； C语言实现第一种：#include <stdio.h>#include <stdlib.h>typedef struct MaxHeap { int *data; //数据域 int size; //长度 int max;//最大长度} MaxHeap;//插入新结点void insert(struct MaxHeap *p, int item){ if (p->size == p->max) { printf(":\n"); return; } int i = ++p->size;//先加1再复制给int，这样第一个插入的数组下标就是1 for (; p->data[i/2] < item; i/=2)//上浮 { if (i <= 1) { break; } p->data[i] = p->data[i/2]; } p->data[i] = item;}//删除根节点，void delete(struct MaxHeap *p){ p->data[1] = p->data[p->size--]; int i = 1; int tmp; while(2*i <= p->size){ //如果有右节点 if (2*i + 1 <= p->size) { if (p->data[2*i + 1] > p->data[i] || p->data[2*i] > p->data[i]) { if (p->data[2*i + 1] > p->data[2*i]) { tmp = p->data[i]; p->data[i] = p->data[2*i + 1]; p->data[2*i + 1] = tmp; i = 2*i + 1; }else{ tmp = p->data[i]; p->data[i] = p->data[2*i]; p->data[2*i] = tmp; i = 2*i; } }else{ return; } }else{ //只有左节点 if (p->data[2*i] > p->data[i]) { tmp = p->data[i]; p->data[i] = p->data[2*i]; p->data[2*i] = tmp; i = 2*i; }else{ return; } } }}//遍历堆void TraverseArray(struct MaxHeap *p){ if (p != NULL) { printf("size:%d \n",p->size); for (int i = 1; i <= p->size; ++i) { printf("%d \n",p->data[i]); } }}//校验堆void checkMaxHeap(struct MaxHeap *p){ if (p != NULL) { for (int i = 1; i <= p->size; ++i) { if (2*i <= p->size) { if (p->data[i] < p->data[2*i]) { printf("error l %d \n",i); } } if (2*i +1 <= p->size) { if (p->data[i] < p->data[2*i +1]) { printf("error r %d \n",i); for (int j = 0; j <= 2*i +1; ++j) { printf("error r: %d \n",p->data[j]); } return; } } } }}C语言实现第二种：#include <stdio.h>#include <stdlib.h>typedef struct MaxHeap { int *data; //数据域 int size; //长度 int max;//最大长度} MaxHeap;void TraverseArray(struct MaxHeap *p){ if (p != NULL) { printf("size:%d \n",p->size); for (int i = 0; i < p->size; ++i) { printf("%d \n",p->data[i]); } }}void insert(struct MaxHeap *p, int item){ if (p->size == p->max) { printf("******:\n"); return; } int i = p->size++; for (; i > 0 && p->data[(i-1)/2] < item; i=(i-1)/2) { if (i < 1) { break; } p->data[i] = p->data[(i-1)/2]; } p->data[i] = item;}void delete(struct MaxHeap *p){ p->data[0] = p->data[--p->size]; int i = 0; int tmp = 0; while(2*i + 1 < p->size){ //如果有右节点 if (2*i + 2 < p->size) { if (p->data[2*i + 2] > p->data[i] || p->data[2*i + 1] > p->data[i]) { if (p->data[2*i + 2] > p->data[2*i + 1]) { printf("dele r max :%d \n",i); tmp = p->data[i]; p->data[i] = p->data[2*i + 2]; p->data[2*i + 2] = tmp; i = 2*i + 2; }else{ printf("dele l max :%d \n",i); tmp = p->data[i]; p->data[i] = p->data[2*i + 1]; p->data[2*i + 1] = tmp; i = 2*i + 1; } }else{ return; } }else{ //只有左节点 if (p->data[2*i + 1] > p->data[i]) { tmp = p->data[i]; p->data[i] = p->data[2*i + 1]; p->data[2*i + 1] = tmp; i = 2*i + 1; }else{ return; } } }}void checkMaxHeap(struct MaxHeap *p){ if (p != NULL) { for (int i = 1; i <= p->size; ++i) { if (2*i <= p->size) { if (p->data[i] < p->data[2*i + 1]) { printf("error l %d \n",i); } } if (2*i +1 <= p->size) { if (p->data[i] < p->data[2*i +1]) { printf("error r %d \n",i); for (int j = 0; j <= 2*i +1; ++j) { printf("error r: %d \n",p->data[j]); } return; } } } }}

一、布隆过滤器的应用价值有时候咱们须要判断一个元素是否在一个汇合中。比方，在字处理软件中，须要查看一个单词是否拼写正确（也就是要判断它是否在已知的字典里）；在警察零碎中，一个嫌疑人的名字是否呈现在嫌疑名单上；在网络爬虫里，一个网址是否曾经被拜访过，等等。 最间接的办法就是讲汇合中的元素存在计算机中，遇到一个新元素时，将它和汇合中的元素间接比拟即可。一般来讲，计算机中的汇合是用哈希表（Hash Table）来存储的。它的益处是疾速精确，毛病是消耗存储空间。 为什么说消耗存储空间呢？其根本原因是哈希表办法须要把实实在在的具备特定长度（每个Email地址对应成一个8字节的信息指纹）的元素的信息指纹存储在内存或硬盘中的哈希表中，这个存储量在理论利用中个别是相当大的。比方每存储一亿个Email地址，须要0.8G大小的数字指纹存储空间，思考到哈希表的存储空间利用率个别只有一半，所以须要1.6G的存储空间。如果存储几十亿上百亿的Email地址，那就须要百亿字节的内存存储空间。 而布隆过滤器只须要哈希表1/8到1/4的大小就能解决同样的问题，它实际上是一个很长的二进制向量和一系列的随机映射函数。 上面以WEB页面地址的存储为例来阐明布隆过滤器的工作原理。 假设存储一亿个WEB页面地址，先建设一个16亿二进制（比特），即2亿字节的向量，而后将这16亿个二进制位清零。对于每一个WEB页面地址X，用8个随机数产生器（f1,f2,...,f8）。再用一个随机数产生器G把这8个信息指纹映射到1-16亿中的8个自然数g1,g2,...g8。当初把这8个地位的二进制位都置为1。对着一亿个WEB页面地址都进行这样的解决后，一个针对WEB页面的布隆过滤器就建成了，见下图。 布隆迪过滤器的映射办法 当初，让咱们看看如何用布隆过滤器来检测一个WEB网页地址Y是否曾经被咱们收录。用雷同的8个随机数生成器（f1,f2,...,f8）对这个WEB网页地址产生8个信息指纹s1,s2,...s8，而后将这8个指纹对应到布隆过滤器的8个二进制位，别离是t1,t2,...,t8。如果Y已被收录，显然t1,t2,...,t8对应的8个二进制位肯定是1。通过这样的形式咱们可能很快地确定一个WEB页面是否已被咱们收录。 二、布隆过滤器的实现布隆过滤器实现代码： #encoding=UTF-8 '''Created on 2014年6月21日@author: jin'''import BitVector class MyHash():#哈希类，依据不同参数初始化后作为不同的哈希函数 def __init__(self, cap, seed): self.cap = cap self.seed = seed def hash(self, value): #计算哈希值得过程 ret = 0 for i in range(len(value)): ret += self.seed*ret + ord(value[i]) #ord()函数计算传入的url字符串中每一个字符在ASCII码表中对应的程序值 return (self.cap-1) & ret #返回哈希值，即在比特序列中的地位 class BloomFilter(): def __init__(self, BIT_SIZE=1<<31): self.BIT_SIZE = 1 << 31 #不拢过滤器的比特数, self.seeds = [5, 7, 11, 13,19, 31, 37, 61] #8个种子，用于产生hash函数 self.bitset = BitVector.BitVector(size=self.BIT_SIZE) self.hashFuncList = [] for i in range(len(self.seeds)): self.hashFuncList.append(MyHash(self.BIT_SIZE, self.seeds[i])) #对每个种子，创立一个MyHash对象，一共8个 def insert(self, value): #插入值，这里并非真正地插入并存储，而是把该值对应的8个地位的比特地位为1 for function in self.hashFuncList: locationBit = function.hash(value) #计算应该置为1的比特位 self.bitset[locationBit] = 1 def isContaions(self, value): if value == None: return False ret = True for f in self.hashFuncList: locationBit = f.hash(value) ret = ret & self.bitset[locationBit] #能够看出，对8个哈希函数，只有有一个为0，那么将返回0，即该值尚未存在 return ret def Main(): #主函数 fd = open("urls.txt") #有反复的网址 http://www.kalsey.com/tools/buttonmaker/ bloomfilter = BloomFilter() while True: url = fd.readline() if cmp(url, 'exit') == 0: print 'complete and exit now' break elif bloomfilter.isContaions(url) == False: bloomfilter.insert(url) else: print 'url :%s has exist' % url Main() url.txt外部存储有一系列网址，最初一行是‘exit’，内容如下： ...

1. 特色汇合内的元素不会反复，所以在增加的时候就须要判断是否有元素存在2. 工夫复杂度剖析操作工夫复杂度增加O(1)删除O(n)查问O(n)3. 代码元素结点/** * content: 汇合的元素结点 * create: 2020-11-03 */<?phpnamespace SetBundle;class Node{ /** * 尾指针 * @var Node|null */ protected $tail; /** * 该节点存储额值 * @var mixed */ protected $value; public function __construct($value = null, ?Node $tail = null) { $this->setTail($tail)->setValue($value); } /** * 设置尾结点 * @param Node|null $tail * @return $this */ public function setTail(?Node $tail): self { $this->tail = $tail; return $this; } /** * 获取尾结点 * @return Node|null */ public function getTail(): ?Node { return $this->tail; } /** * 设置值 * @param mixed $value * @return $this */ public function setValue($value): self { $this->value = $value; return $this; } /** * 获取结点里的值 * @return mixed */ public function getValue() { return $this->value; }}汇合的代码<?php/** * content: 汇合（链表实现） * auth: 俞佳明 * create: 2020-11-03 */namespace SetBundle;class LinkSet{ /** * @var Node|null */ protected $node; /** * 汇合大小 * @var int */ protected $size; public function __construct() { $this->node = null; $this->size = 0; } /** * 获取汇合中的元素 * @return int */ public function getSize(): int { return $this->size; } /** * 查问是否存在该值的结点 * @param $value * @return Node|null */ public function contains($value): ?Node { $node = $this->node; while (!is_null($node)) { if ($node->getValue() === $value) { return $node; } $node = $node->getTail(); } return null; } /** * 插入 * @param string|int $value * @return Node * @throws \Exception */ public function add($value): Node { $newNode = new Node($value, null); if (is_null($this->node)) { $this->node = $newNode; } else { if (!is_null($this->contains($value))) { throw new \Exception('插入的元素已存在！'); } $newNode->setTail($this->node); $this->node = $newNode; } $this->size++; return $newNode; } /** * 删除 * @param $value */ public function remove($value) { $node = $this->node; while (!is_null($node) && !is_null($node->getTail())) { if ($node->getTail()->getValue() === $value) { $node->setTail($node->getTail()->getTail()); $this->size--; return; } $node = $node->getTail(); } return; } public function varDump() { $node = $this->node; while (!is_null($node)) { echo $node->getValue(). PHP_EOL; $node = $node->getTail(); } }}4. 示例<?phprequire_once __DIR__ . '/../../vendor/autoload.php';$set = new SetBundleLinkSet();$set->add(1);$set->add(2);$set->add(3);$set->add(4);$set->add(5);$set->add(6);$set->varDump();654321

什么是数据机构？ 官网定义 ———— 数据机构是指相互之间存在着一种或者多种关系的汇合以及该汇合中数据元素之间的关系组成。看了之后脑袋大不？其实简略来讲就是一句话 ———— 数据和数据之间的关系。 一、数据的存储构造 数据的存储构造是指数据的逻辑构造在计算机中的示意。数据的存储构造分为顺序存储构造和链接存储构造两种。 1、顺序存储构造 顺序存储办法它是把逻辑上相邻的结点存储在物理地位相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由 此失去的存储示意称为顺序存储构造，的如下图： 2、链式存储构造 链接存储办法它不要求逻辑上相邻的结点在物理地位上亦相邻，结点间的逻辑关系是由附加的指针字段示意的。由此失去的存储示意 称为链式存储构造，链式存储构造通常借助于程序设计语言中的指针类型来实现.  二、数据的逻辑构造 零碎的逻辑构造是从思维的角度上对系du统分类，把零碎分成若干个逻辑单元，不同逻辑单元别离实现本人的性能。数据的逻辑构造是对数据之间关系的形容，有时就把逻辑构造简称为数据结构1、汇合构造：汇合构造的汇合中任何两个数据元素之间都没有逻辑关系，组织模式涣散。2、线性构造：数据结构中线性构造指的是数据元素之间存在着“一对一”的线性关系的数据结构。3、树状构造：树状构造是一个或多个节点的无限汇合。4、图形构造：网络结构是指通信零碎的整体设计，它为网络硬件、软件、协定、存取控制和拓扑提供规范

1. 遍历准则前序遍历：先遍历以后结点，再遍历以后结点的左儿子，最初遍历以后结点的右儿子中序遍历：先遍历以后结点的左儿子，再遍历以后结点，最初遍历以后结点的右儿子后续遍历：先遍历以后结点的左儿子，再遍历以后结点的右儿子，最初遍历以后结点2. 前序遍历示意图 3. 中序遍历示意图 4. 后序遍历示意图 5. 二分搜寻树的递归遍历实现<?phpnamespace TreeBundle;use ArrayBundle\BaseArray;use StackBundle\BaseStack;class BaseBinaryTree{ public function __construct() { $this->rootNode = null; $this->size = 0; } /** * 二叉树的根节点 * @var Node */ protected $rootNode; /** * 获取根节点 * @return Node */ public function getRootNode(): Node { return $this->rootNode; } /** * 二叉树的个数 * @var int */ protected $size; /** * 获取二叉树的元素个数 * @return int */ public function getSize(): int { return $this->size; } /** * 判断是否为空 * @return bool */ public function isEmpty(): bool { return $this->size == 0; } /** * 插入结点 * @param mixed $value * @return void */ public function add($value): void { // 如果不存在根节点就插入根节点 if (is_null($this->rootNode)) { $this->rootNode = new Node($value); $this->size; return; } else { $this->addChild($value, $this->rootNode); return; } } /** * 插入儿子结点 * @param mixed $value * @param Node|null $parentNode */ private function addChild($value, ?Node $parentNode): void { if (bccomp($parentNode->getValue(), $value) > 0) { // 左儿子 if (is_null($parentNode->getLeftChild())) { $parentNode->setLeftChild(new Node($value)); $this->size++; return; } else { $this->addChild($value, $parentNode->getLeftChild()); } } elseif (bccomp($parentNode->getValue(), $value) < 0) { // 右儿子 if (is_null($parentNode->getRightChild())) { $parentNode->setRightChild(new Node($value)); $this->size++; return; } else { $this->addChild($value, $parentNode->getRightChild()); } } else { return; } } const TRAVERSAL_PREORDER = 1; // 先序遍历 const TRAVERSAL_INORDER = 2; // 中序遍历 const TRAVERSAL_POSTORDER = 3; // 后序遍历 /** * 遍历二叉树 * @param int $traversalType * @return string */ public function traversal(int $traversalType = 1): string { $result = ''; switch ($traversalType) { case self::TRAVERSAL_PREORDER: $this->preorderTraversal($result, $this->rootNode); break; case self::TRAVERSAL_INORDER: $this->inorderTraversal($result, $this->rootNode); break; case self::TRAVERSAL_POSTORDER: $this->postorderTraversal($result, $this->rootNode); break; default: break; } return $result; } /** * 先序遍历 * @param string $result 后果值 * @param Node|null $node 结点 * @return void */ protected function preorderTraversal(string &$result, ?Node $node): void { if (is_null($node)) return; // 拼接 if ($result != '') $result .= ' -> '; // 先遍历以后节点 $result .= $node->getValue(); // 再遍历左儿子 $this->preorderTraversal($result, $node->getLeftChild()); // 在遍历右儿子 $this->preorderTraversal($result, $node->getRightChild()); return; } /** * 中序遍历 * @param string $result 后果值 * @param Node|null $node 结点 * @return void */ public function inorderTraversal(string &$result, ?Node $node): void { if (is_null($node)) return; // 先遍历左儿子 $this->inorderTraversal($result, $node->getLeftChild()); // 拼接 if ($result != '') $result .= ' -> '; // 再获取以后结点 $result .= $node->getValue(); // 在遍历右儿子 $this->inorderTraversal($result, $node->getRightChild()); return; } /** * 后序遍历 * @param string $result 后果值 * @param Node|null $node 结点 * @return void */ public function postorderTraversal(string &$result, ?Node $node): void { if (is_null($node)) return; // 先遍历左儿子 $this->postorderTraversal($result, $node->getLeftChild()); // 在遍历右儿子 $this->postorderTraversal($result, $node->getRightChild()); // 拼接 if ($result != '') $result .= ' -> '; // 再获取以后结点 $result .= $node->getValue(); return; }}6. demo<?php// composer主动加载require_once __DIR__ . '/../../vendor/autoload.php';// 获取一个二分搜寻树$tree = new TreeBundleBaseBinaryTree();// 插入结点$tree->add(10);$tree->add(5);$tree->add(15);$tree->add(1);$tree->add(0);$tree->add(2);$tree->add(9);$tree->add(8);$tree->add(11);$tree->add(12);$tree->add(19);$tree->add(18);$tree->add(29);$tree->add(16);$tree->add(17);// 前序遍历echo $tree->traversal(TreeBundleBaseBinaryTree::TRAVERSAL_PREORDER). PHP_EOL;// 中序遍历echo $tree->traversal(TreeBundleBaseBinaryTree::TRAVERSAL_INORDER). PHP_EOL;// 后续遍历echo $tree->traversal(TreeBundleBaseBinaryTree::TRAVERSAL_POSTORDER). PHP_EOL;打印后果： ...

1. 插入准则：第一个结点为根节点后续插入的结点值如果小于根节点，就成为根节点的左儿子后续插入的结点值如果大于根节点，就成为根节点的右儿子2. 示意图 3. 二分搜寻树的实现<?php/** * content: 二叉树的二分搜寻树的实现 * auth: yujiaming * create: 2020-10-25 */namespace TreeBundle;use ArrayBundle\BaseArray;use StackBundle\BaseStack;class BaseBinaryTree{ public function __construct() { $this->rootNode = null; $this->size = 0; } /** * 二叉树的根节点 * @var Node */ protected $rootNode; /** * 获取根节点 * @return Node */ public function getRootNode(): Node { return $this->rootNode; } /** * 二叉树的个数 * @var int */ protected $size; /** * 获取二叉树的元素个数 * @return int */ public function getSize(): int { return $this->size; } /** * 判断是否为空 * @return bool */ public function isEmpty(): bool { return $this->size == 0; } /** * 插入结点 * @param mixed $value * @return void */ public function add($value): void { // 如果不存在根节点就插入根节点 if (is_null($this->rootNode)) { $this->rootNode = new Node($value); $this->size; return; } else { $this->addChild($value, $this->rootNode); return; } } /** * 插入儿子结点 * @param mixed $value * @param Node|null $parentNode */ private function addChild($value, ?Node $parentNode): void { if (bccomp($parentNode->getValue(), $value) > 0) { // 左儿子 if (is_null($parentNode->getLeftChild())) { $parentNode->setLeftChild(new Node($value)); $this->size++; return; } else { $this->addChild($value, $parentNode->getLeftChild()); } } elseif (bccomp($parentNode->getValue(), $value) < 0) { // 右儿子 if (is_null($parentNode->getRightChild())) { $parentNode->setRightChild(new Node($value)); $this->size++; return; } else { $this->addChild($value, $parentNode->getRightChild()); } } else { return; } }}4. demo<?php// composer主动加载require_once __DIR__ . '/../../vendor/autoload.php';// 获取一个二分搜寻树$tree = new TreeBundleBaseBinaryTree();// 插入根节点$tree->add(10);$tree->add(5);$tree->add(15);$tree->add(1);$tree->add(9);

数据结构相互之间存在一种或多种定义关系的数据元素汇合(collection).逻辑构造是对数据之间关系的形容,它与存储构造,地位无关,同一种逻辑构造能够有多种物理存储构造.能够演绎为两大类: 线性构造是一个数据元素的有序汇合(一对一) 1):汇合之中必存在惟一一个第一元素.2):汇合之中必存在惟一一个最初元素.3):除最初一个元素,都有后继.4):除第一个元素,都有前驱.非线性构造是一个数据元素的关系汇合(一对多,多对多). 1)树2)图物理构造(存储构造)是数据的逻辑构造在物理存储中的映像.它包含数据与关系的示意.数据元素之间的关系在物理存储中有两种不同的示意办法:程序映像与非程序映像.对应的两种不同存储构造为顺序存储构造与链表存储构造.罕用4种存储办法: 顺序存储办法链式存储办法索引存储办法散列存储办法

本文已收录至我的 Github《算法图解》系列：https://github.com/vipstone/algorithm后面咱们介绍了栈（Stack），队列和栈是比拟像的一种数据结构。咱们能够设想有很多辆汽车正在通过单行道的隧道，所有车辆不能插队、不能掉头，先进来的车也先进来，咱们能够把这种特色的数据结构称之为队列。 队列也属于逻辑构造，所谓的物理构造是指能够将数据存储在物理空间中，比方数组和链表都属于物理数据结构；而逻辑构造则是用于形容数据间的逻辑关系的，它能够由多种不同的物理构造来实现，比方队列和栈都属于逻辑构造。 队列个性队列中的元素必须是先进先出（First In First Out，FIFO）的，它有两个重要的办法：入队（enqueue）和出队（dequeue）。队列的入口端叫队尾（rear），进口端叫队头（front），如下图所示： 手撸队列学习了队列的基本知识之后，接下来咱们将应用代码来实现一个队列。 首先咱们先应用数组来实现一个队列，它的构造如下图所示： 1.自定义队列—数组public class MyQueue<E> { private Object[] queue; // 存储容器 private int head; // 头部指针 private int tail; // 尾部指针 private int size; // 队列理论存储长度 private int maxSize; // 最大容量 public MyQueue() { // 无参构造函数，设置默认参数 this.maxSize = 10; this.head = 0; this.tail = -1; this.size = 0; this.queue = new Object[this.maxSize]; } public MyQueue(int initSize) { // 有参构造函数，设置参数 this.maxSize = initSize; this.head = 0; this.tail = -1; this.size = 0; this.queue = new Object[this.maxSize]; } /** * 查问队头元素 */ public E peek() throws Exception { if (size == 0) { throw new Exception("队列中暂无数据"); } return (E) this.queue[this.head]; } /** * 入列 */ public boolean offer(E e) throws Exception { if (tail >= (maxSize - 1)) { throw new Exception("增加失败，队列已满"); } this.queue[++tail] = e; size++; return true; } /** * 出列 */ public E poll() throws Exception { if (size == 0) { throw new Exception("删除失败，队列为空"); } size--; return (E) this.queue[head++]; } /** * 代码测试 */ public static void main(String[] args) throws Exception { MyQueue queue = new MyQueue(); queue.offer("Hello"); queue.offer("Java"); System.out.println(queue.peek()); queue.poll(); System.out.println(queue.poll()); }}以上代码的执行后果如下： ...

源码和课件下载方式在文末什么是数据结构与算法算法用来设计并实现一种用计算机来解决问题的办法。它满足下列性质： 输出：有零个或多个输入量 输入：产生至多一个输出量 确定性：算法的指令清晰、无歧义 有限性：算法的指令执行次数无限，执行工夫无限 咱们在应用计算机解决产问题的过程能够分为上面五个步骤： 问题的了解：搞清楚问题的输出、要求和输入。 数据结构设计：设计能解决问题中数据的数据结构，还要设计能反对算法策略的数据结构。 算法设计：抉择算法策略，用适当的形式形容和逐渐细化算法步骤。 算法剖析：发现有优化的中央，返回第二步，从新设计数据结构和算法  程序实现：用计算机编程，定义数据结构，编写代码实现，并高度和运行。 简介本次课程的亮点在于： 1、由MJ老师与名企算法大咖董甫耸单干独特研发，全程精心实力打造，保障课程的系统性，全面性，高含金量。 2、深刻摸索每一行代码的底层实现，让学习者更好地读懂每一个框架源码，更有效率地应用框架；并且在开发大型项目时，有能力达到性能的极致优化。 3、MJ老师亲自授课，联合大量企业实在案例解说，化繁入简，通俗易懂，同时又留神拓展解说和延长练习。 视频章节目录】 │  01.冒泡、抉择、堆排序.mp4 │  02.插入排序.mp4 │  03.归并排序.mp4 │  04.疾速、希尔排序.mp4 │  05.计数、基数、桶排序.mp4 │  06.并查集.mp4 │  07.图、BFS、DFS、拓扑排序.mp4 │  08.kruskal、prim.mp4 │  09.dijkstra、bellman-ford、floyd.mp4 │  10.KMP、BM、KR、Sunday.mp4 │  11.Dijkstra.mp4 │  12.Dijkstra欠缺、Bellman-Ford.mp4 │  13.递归、回溯.mp4 │  14.尾调用、尾递归、回溯.mp4 │  15.剪枝、N皇后问题（1）.mp4 │  16-1.贪婪、分治.mp4 │  16-2.贪婪、分治.mp4 │  17-1.大数乘法、动静布局初步.mp4 │  17-2.大数乘法、动静布局初步.mp4 │  18.最大间断子序列和，最长回升子序列.mp4 │  19-1.最长公共子序列.mp4 │  19-2.最长公共子序列.mp4 │  20-1.最长公共子串、0-1背包问题.mp4 │  20-2.最长公共子串、0-1背包问题.mp4 │  21-1.LIS二分搜寻实现_布隆过滤器.mp4 │  21-2.LIS二分搜寻实现_布隆过滤器.mp4 │  22-1.跳表的搜寻.mp4 │  22-2.跳表的搜寻.mp4 │  23.跳表的增加删除、BPlus树.mp4 4 如何获取视频、课件和源代码视频地址： https://www.bilibili.com/vide...下载源码、课件形式： 公众号首页回复【恋上数据结构】即可获取下载链接 公众号首页回复【恋上数据结构】即可获取下载链接

二叉查找树二叉查找树（二叉搜寻树，二叉排序树）若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也别离为二叉排序树。 二叉均衡树均衡二叉树也称作AVL树，AVL树实质还是一棵二叉查找树，只是在二叉查找树的根底上减少了“均衡”的要求。所谓均衡要求是指，对AVL树的任意结点来说，其左子树与右子树的高度之差的绝对值不超过1，其中左子树与右子树的高度因子之差称为均衡因子。

第 1 章：稠密数组和队列1、稠密数组1.1、理论需要编写的五子棋程序中，有存盘退出和续上盘的性能因为该二维数组的很多值是默认值 0 ，因而记录了很多没有意义的数据，咱们将其转为稠密数组进行存储 1.2、稠密数组利用1.2.1、稠密数组解决办法稠密数组把具备不同值的元素的行列及值记录在一个小规模的数组中，从而放大程序的规模稠密数组也是二维数组，行数由原数组的数据决定，列数个别为 3 列稠密数组的第一行记录原数组一共有几行几列，有多少个不为零的值 第一列：原数组的行数第二列：原数组的列数第三列：原数组有多少个不为零的值之后的行记录原数组中不为零（x）的值所在的行数、列数以及 x 的值 第一列：x 在原数组中的行数第二列：x 在原数组中的列数第三列：x 的值1.2.2、举例说明原始二维数组较大，压缩后占用空间缩小1.3、利用实例1.3.1、思路剖析应用稠密数组， 来保留相似后面的二维数组(棋盘、 地图等等)把稠密数组存盘， 并且能够从新复原原来的二维数组数 1.3.2、代码实现代码public class SparseArray { public static void main(String[] args) { // 创立一个原始的二维数组 11 * 11 // 0: 示意没有棋子， 1 示意 黑子 2 表蓝子 int chessArr1[][] = new int[11][11]; chessArr1[1][2] = 1; chessArr1[2][3] = 2; chessArr1[4][5] = 2; // 输入原始的二维数组 System.out.println("原始的二维数组~~"); for (int[] row : chessArr1) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } // 将二维数组 转 稠密数组的思 // 1. 先遍历二维数组 失去非0数据的个数 int sum = 0; for (int i = 0; i < chessArr1.length; i++) { for (int j = 0; j < chessArr1[i].length; j++) { if (chessArr1[i][j] != 0) { sum++; } } } // 2. 创立对应的稠密数组 int sparseArr[][] = new int[sum + 1][3]; // 给稠密数组赋值 sparseArr[0][0] = chessArr1.length; sparseArr[0][1] = chessArr1[0].length; sparseArr[0][2] = sum; // 遍历二维数组，将非0的值寄存到 sparseArr中 int count = 0; // count 用于记录是第几个非0数据 for (int i = 0; i < chessArr1.length; i++) { for (int j = 0; j < chessArr1[i].length; j++) { if (chessArr1[i][j] != 0) { count++; sparseArr[count][0] = i; sparseArr[count][1] = j; sparseArr[count][2] = chessArr1[i][j]; } } } // 输入稠密数组的模式 System.out.println(); System.out.println("失去稠密数组为~~~~"); for (int i = 0; i < sparseArr.length; i++) { System.out.printf("%d\t%d\t%d\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]); } System.out.println(); // 将稠密数组 --》 复原成 原始的二维数组 /* * 1. 先读取稠密数组的第一行，依据第一行的数据，创立原始的二维数组，比方下面的 chessArr2 = int [11][11] 2. * 在读取稠密数组后几行的数据，并赋给 原始的二维数组 即可. */ // 1. 先读取稠密数组的第一行，依据第一行的数据，创立原始的二维数组 int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]]; // 2. 在读取稠密数组后几行的数据(从第二行开始)，并赋给 原始的二维数组 即可 for (int i = 1; i < sparseArr.length; i++) { chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2]; } // 输入复原后的二维数组 System.out.println(); System.out.println("复原后的二维数组"); for (int[] row : chessArr2) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } }}程序运行后果原始的二维数组~~0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 失去稠密数组为~~~~11 11 31 2 12 3 24 5 2复原后的二维数组0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

概要线性表是一种线性构造，它是具备雷同类型的n(n≥0)个数据元素组成的无限序列。本文先介绍线性表的几个根本组成部分：数组、单向链表、双向链表；随后给出双向链表的Java语言的实现。 文章转载自： https://www.cnblogs.com/skywa... 数组数组是一种最罕用的线性数据结构，外面寄存的元素的类型是一样的，并且有序的。 数组的特点是：数据是间断的；随机访问速度快。 对于Java而言，Collection汇合中提供了ArrayList和Vector用于数组这种数据结构的实现。 单向链表单向链表(单链表)是链表的一种，它由节点组成，每个节点都蕴含下一个节点的指针。 单链表的示意图如下： 表头为空，表头的后继节点是"节点10"(数据为10的节点)，"节点10"的后继节点是"节点20"(数据为10的节点)，...单链表删除节点 删除"节点30"删除之前："节点20" 的后继节点为"节点30"，而"节点30" 的后继节点为"节点40"。删除之后："节点20" 的后继节点为"节点40"。单链表增加节点在"节点10"与"节点20"之间增加"节点15"增加之前："节点10" 的后继节点为"节点20"。增加之后："节点10" 的后继节点为"节点15"，而"节点15" 的后继节点为"节点20"。 单链表的特点是：节点的链接方向是单向的；绝对于数组来说，单链表的的随机访问速度较慢，然而单链表删除/增加数据的效率很高。 双向链表双向链表(双链表)是链表的一种。和单链表一样，双链表也是由节点组成，它的每个数据结点中都有两个指针，别离指向间接后继和间接前驱。所以，从双向链表中的任意一个结点开始，都能够很不便地拜访它的前驱结点和后继结点。个别咱们都结构双向循环链表。 双链表的示意图如下： 表头为空，表头的后继节点为"节点10"(数据为10的节点)；"节点10"的后继节点是"节点20"(数据为10的节点)，"节点20"的前继节点是"节点10"；"节点20"的后继节点是"节点30"，"节点30"的前继节点是"节点20"；...；开端节点的后继节点是表头。双链表删除节点删除"节点30"删除之前："节点20"的后继节点为"节点30"，"节点30" 的前继节点为"节点20"。"节点30"的后继节点为"节点40"，"节点40" 的前继节点为"节点30"。删除之后："节点20"的后继节点为"节点40"，"节点40" 的前继节点为"节点20"。 双链表增加节点在"节点10"与"节点20"之间增加"节点15"增加之前："节点10"的后继节点为"节点20"，"节点20" 的前继节点为"节点10"。增加之后："节点10"的后继节点为"节点15"，"节点15" 的前继节点为"节点10"。"节点15"的后继节点为"节点20"，"节点20" 的前继节点为"节点15"。

栈与队列和数组、链表、树这几种数据结构不太一样。栈与队列次要是做为程序员的工具来应用，它们次要做为构思算法的辅助工具，而不是齐全的数据存储工具。 它们的生命周期比数组那些要短得多，在程序执行期间它们才会被创立，工作执行完就会被销毁。 一 栈栈是一种只能在一端进行插入和删除数据的数据结构，这一端被称为栈顶（top）。其特点简略来讲就是先进后出。栈的次要机制能够用数组来实现，当然也能够用链表来实现。 用数组实现栈，并实现罕用操作——出栈、入栈、查看元素（只能查看栈顶元素）、判断栈是否为空等操作。 public class StackTest { private long[] arr; // 栈顶 private int top; public StackTest(){ arr = new long[10]; top = -1; } public StackTest(int maxsize){ arr = new long[maxsize]; top = -1; } /** * 增加数据 * @param value */ public void push(int value){ arr[++top] = value; } /** * 移除数据 * @return */ public long pop() { return arr[top--]; } /** * 查看数据 * @return */ public long peek(){ return arr[top]; } public boolean isEmpty(){ return top == -1; } /*** * 判断是否满了 * @return */ public boolean isFull(){ return top == arr.length-1; }}栈的所有操作复杂度都为O(1)，栈的操作不依赖栈中元素大小，栈不须要挪动和比拟操作。 ...

前言数据结构的实现有两种形式，一种是顺序存储，一种是链式存储顺序存储：应用一片间断的逻辑地址存放数据链式存储：不必间断地址，应用指针指向下个元素的地址 罕用数据结构有：线性表，栈，队列，树，图等等，二叉树是属于这外面的树。BST(Binary Search Tree)介绍BST 是一种树，他的个性是1.左子树上所有结点的值均小于或等于它的根结点的值。2.右子树上所有结点的值均大于或等于它的根结点的值。3.左、右子树也别离为BST BST的长处:BST 通常是应用链式构造存储实现的，应用顺序存储要么是(Full Binary Tree)或者靠近(Full Binary Tree)顺序存储最大的弊病是必须事后给出数组的存储空间大小插入删除比拟麻烦，长处是能够节俭空间，查找很快BST的毛病:抛开顺序存储和链式存储，BST数据结构自身存在的毛病是，在特定的时候，树的度会始终升高，导致查找效率变低 这个时候咱们就有新的树来解决他的毛病就是(AVL Tree) AVL TreeAVL树，实质上是带了均衡性能的BST，他多了个均衡因子概念即（每个结点的左右子树的高度之差的绝对值（均衡因子）最多为1），如果不满足就会旋转来满足这个条件。下面图一BST 在avl中旋转操作后失去如下，具体怎么旋转的能够在这个网站本人模仿https://www.cs.usfca.edu/~gal...那么AVL 有没有什么毛病呢?最大的毛病就是谋求完满的均衡导致插入和删除须要大量的均衡计算，这个在插入和删除大的状况导致开销较大，这个时候咱们就想着，有没有一种树，解决BST的毛病，同时又不要大量的计算均衡，于是RB-Tree就被创造了 RB-Tree 和 AVL 区别RB-Tree 的定义不介绍了，咱们记得这个区别就行删除node引起树的不均衡时，最坏状况下，AVL须要保护从被删node到root这条门路上所有node的平衡性，而RB-Tree最多只需3次旋转。 下图是解决图一不均衡RB-Tree的图

什么是数组？忘了在哪本书看见过一句话“了解了概念性的货色，你就学会了70%” 回到主题，什么是数组？数组（Array）是一种线性表数据结构。它用一组间断的内存空间，来存储一组具备雷同类型的数据 概念中有两个要害的中央： 数组是一种线性数据结构数组中存储的是间断的内存空间和雷同类型的数据什么是线性数据结构有数据结构根底的小伙伴都应该晓得，线性构造就是数据排成一条线一样的数据结构，也就意味着它仅有前后两个方向，比方队列、单链表、栈等，也是线性构造 与它绝对的就是非线性表，最典型的就是树和图。他们的特点就是并不是只有前后这种关系 间断的内存空间和雷同类型的数据正因为有了这个个性，使得数组能够进行“随机拜访”。尽管拜访数组中某个元素变得很快，但毛病就是在批改（删除、插入）数组的时候，操作会变得很麻烦，因为要保障数组内存空间的连续性，所以不得不进行繁琐的数据挪动 假如有一个长度为5的int类型的数组var a [5]int，假如给这个数组调配的内存空间首地址是1000，则这个数组调配的内存空间为1000~1019，看下图 操作系统会为每一个内存单眼调配一个地址，通过这个地址来拜访内存中的数据。当操作系统须要随机拜访数组中的某一个元素时，它会通过下边这个寻址公式来计算出某个元素的存储地址 a[i]_address = base_address + i * data_type_sizedata_type_size：示意数组中每个元素的大小。比方int类型，它占用的是4个字节，所以这里data_type_size就是4数组和链表的区别是什么通过上边对数组的介绍，能够看进去，数组适宜查找操作。然而查找的工夫复杂度并不为O(1)。即使是排好序的数组，你用二分查找，工夫复杂度也是O(logn)。所以，数组反对随机拜访，依据下标随机拜访的工夫复杂度为O(1) 数组相干操作插入元素数组头部插入元素 在数组的头部插入元素，为了保障空间的连续性，须要将数组中所有的元素向后移一位，而后将待插入元素放入到首部地位 代码实现 function insertIntoHead($elem, $arr) { echo "原始数组：".PHP_EOL; print_r($arr); $i = 0; $len = count($arr); while ($i < $len) { $arr[$len-$i] = $arr[$len-$i-1]; $i++; } $arr[0] = $elem; echo "头部插入元素之后后果：".PHP_EOL; print_r($arr); }数组两头插入元素 在数组的两头某个地位插入元素，须要将待插入地位当前的元素均向后挪动一位 代码实现 function insertIntoMid($elem, $position, $arr) { echo "原始数组：".PHP_EOL; print_r($arr); $len = count($arr); $i = $position-1; $value = $arr[$i]; $arr[$i] = $elem; $head = $i+1; $offset = $position-1; while ($i < $len) { $arr[$len-$i+$offset] = $arr[$len-$i-1+$offset]; $i++; } $arr[$head] = $value; echo "头部插入元素之后后果：".PHP_EOL; print_r($arr); }数组尾部插入元素 ...

一种非程序数据结构--树。树是一种分层数据的形象模型,一个树结构蕴含一系列存在父子关系的节点，每个节点都有一个父节点(除了顶部第一个节点)以及零个或多个子节点,位于树顶部的节点叫根节点。 二叉树和二叉搜寻树二叉树中的节点最多只能有两个节点,一个左侧的节点，一个右侧节点。二叉搜寻树（BST）是二叉树的一种，然而只容许在左侧贮存比父节点小的数据，在右侧贮存比父节点大的数据。 和链表一样，通过援用来示意节点之间的关系，在双向链表里，每个节点有俩援用，一个指向上一个节点，一个指向下一个节点，对于二叉搜寻树也应用同样形式，不同的中央是一个指向左侧节点，一个指向右侧节点（树中会称节点为键）。 insert(key) 树里插入键search(key) 树里查找一个键inOrderTraveres() 中序遍历所有preOrderTraveres() 先序遍历所有postOrderTraveres() 后序遍历所有min() 获取树最小值max() 获取树最大值remove(key) 删除树里某个键const Compare = { LESS_THAN:-1, BIGGER_THAN:1}function defultCompare(a,b){ if(a===b){ return 0; } return a<b?Compare.LESS_THAN:Compare.BIGGER_THAN;}class Node{ constructor(key){ this.key = key; this.left = null; this.right = null; }}class BinarySearchTree{ constructor(compareFn = defaultCompare){ this.compareFn = compareFn; this.root = null; } insert(key){ if(!this.root){ this.root = new Node(key); }else{ this.insertNode(this.root,key); } } insertNode(node,key){//查找比照键大小插入,最初生成构造如上图 if(this.compareFn(key,node.key)==Compare.LESS_THAN){ if(!node.left){ node.left = new Node(key); }else{ this.insertNode(node.left,key); } } else { if(!node.right){ node.right = new Node(key); }else{ this.insertNode(node.right,key); } } } search(key){ return this.searachNode(this.root,key); } searachNode(node,key){ if(!node){ return false; } if(this.compareFn(key,node.key)==Compare.LESS_THAN){ return this.searachNode(node.left,key); }else if(this.compareFn(key,node.key)==Compare.BIGGER_THAN){ return this.searachNode(node.right,key); }else{ return true;//能够依据本人须要返回 } }}做个笔记，该内容借鉴与学习javascript数据结构与算法 ...

本文源码：GitHub·点这里 || GitEE·点这里 一、队列构造1、根底概念队列是一种非凡的线性表，非凡之处在于它只容许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。 2、特点形容队列是一个有序列表，能够用数组或是链表来实现，遵循先进先出的准则。即:先进入队列的数据，会先取出；后进入队列的数据，要后取出；即FIFO准则。 入队列示意图： 出队列示意图： 通过上述两张图解，不难发现队列构造的一些特点： 先进入的数据先进来；数据从队尾进入，从队首进来；基于数组形容队列下标变更频繁；出队列算法能够基于容器大小取模；队列构造的外围是对容器内是否空、是否满标记的判断算法，即容器为空不可再取，容器已满无奈再存；该算法构造在仓储畛域的适应十分宽泛。 3、音讯队列音讯队列就是基于数据结构中的“先进先出”策略实现的，将音讯以排队的形式放入队列中，而后出队列被生产： 有时候某类音讯生产须要有顺序控制，即能够对音讯中的公共ID做取模解决，即把某类音讯都置于一个队列中即可。 4、API应用案例LinkedList类实现Queue队列接口，因而能够基于LinkedList模仿队列成果。 import java.util.LinkedList;import java.util.Queue;public class M01_Queue { public static void main(String[] args) { // 入队列 Queue<String> queue = new LinkedList<>(); queue.add("head") ; queue.add("middle") ; queue.add("tail") ; // 当队列出数据之后，size是一直变动的 int queueSize = queue.size() ; int loop = 0 ; // 依据队列大小，一直出队列 while (loop < queueSize) { System.out.println(queue.poll()); System.out.println(queue); loop ++ ; } }}二、栈构造1、根底概念栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，绝对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈(push)，它是把新元素放到栈顶元素的下面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈(pop)，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。 ...

前言笔者正在自学数据结构，深感书中的常识偏差实践和代码，而对逻辑自身有些漠视。 次要是图少，字多，以至于学者学习之后对于逻辑的了解不够，最终沦为大学中常见的后果——背书。（笔者接触过一些同学如何学习计算机，深感背书的危害） 为了帮忙他人也帮忙本人了解，我尝试着为常见的几种构造绘制一些动态图。因为工夫仓促，尚未全副实现。 逻辑构造和存储构造逻辑构造只思考数据元素之间的关系，不思考具体实现。存储构造思考在计算机中如何示意。 线性表 逻辑构造：所有数据按线性构造贮存参考元素后面的元素称为前驱参考元素前面的元素称为后继除第一个外，每个元素只有一个前驱处最初一个外，每个元素只有一个后继存储构造： 顺序存储： 提前申请出所有须要的内存地址逻辑地位相邻的数据元素物理地位也是相邻的插入数据时，插入地位之后的所有数据后移长处： 地址间断，查问速度快毛病： 长度固定，不能动静调整插入元素时须要挪动大量元素 链式构造： 应用不间断的内存地址将数据元素分为数据域和指针域数据域存放数据头指针指向第一个元素指针域指向下一个元素插入数据时，扭转插入地位的指针即可长处： 大小可变，灵便又节约空间插入不便毛病：遍历速度慢 栈逻辑构造： 后进先出仅能在栈顶进行操作存储构造： 程序栈： 和程序表相似，一次申请一段间断的地址容量不固定，当初始容量用完后，再按设定的增量进行裁减须要两个指针base和top，别离指向栈底和栈顶插入数据时，top上移；删除数据时，top下移插入数据的地位是top以后指向的地址 链栈 链栈与链表简直统一 应用不间断的内存地址将数据元素分为数据域和指针域数据域存放数据栈顶指针指向第一个元素指针域指向下一个元素不同之处在于： 插入数据时，栈顶指向新插入的元素，新元素的指针域指向原来的栈顶 队列（未完待续）逻辑构造：先进先出 总结本周最大的播种是，通过一番查找和比照，终于把握了超低老本的GIF制作方法动画制作是一门重要技能，再粗疏的语言形容也不如一张图片更活泼，再活泼的图片也不如一段动画更直观将来我会缓缓学残缺本数据结构，之后的每一个知识点都会做一个动画，敬请期待版权申明本文作者：河北工业大学梦云智开发团队 - 刘宇轩 新人经验不足，有倡议欢送交换，有谬误欢送轻喷

链表是一种常见的数据结构，链表是由一连串的结点组成，这个节点就是链结点，每个链结点都由数据域和指针域两局部组成。 应用链表构造能够克服数组构造须要事后晓得数据大小的毛病，链表构造能够充沛利用计算机内存空间，实现灵便的内存动静治理。然而链表失去了数组随机读取的长处，同时链表因为减少了结点的指针域，空间开销比拟大。 链表比拟好的一种了解是：将链表看成一个火车，每个车厢之间都是相互连接的，只有找到火车头，就能够找到具体的车身。链表也是，咱们只关怀它的头。 一 单向链表1.1 单向链表原理图单向链表的一个链结点蕴含数据域和下一个链结点的指针。头结点也蕴含数据域和指针域，然而个别为了不便查找，头节点不写数据，最初一个结点的指针指向空。 1.2 实现单向链表的存储等操作创立一个链结点的实体类 public class Node { // 数据域 public long data; // 指针域 public Node next; public Node(long value){ this.data = value; }}1.2.1 插入一个节点在头节点后插入一个结点，第一步须要将新插入的结点指向头结点指向的结点，第二部将头结点指向新插入的结点。插入结点只须要扭转一个援用，所以复杂度为O(1)。 public class LinkList { private Node head; /** * 在头节点之后插入一个节点 */ public void insertFirst(long value){ Node node = new Node(value); node.next = head; head = node; }}1.2.2 头结点后删除一个结点在头结点后删除一个结点，就是让头结点指向这个结点的下一个结点。复杂度也是O(1)。 public Node deleteFirst(){ Node tmp = head; head = tmp.next; return tmp;}1.2.3 依据数据域查找结点查找须要比对每个结点的数据，实践上查找一个结点均匀须要N/2次，所以复杂度为O(N)。 ...

数组做为一种根底的数据存储构造，利用非常宽泛。数组是用间断的内存空间来存储固定长度的、雷同数据类型的一种数据结构。数据结构是跟语言无关的，这里，应用java来进行数组的相干操作。数组的索引是从0开始的。 一 数组初始化创立数据有两种形式，一种是先申明一个固定长度的数据，而后再给数组赋值，另一种是间接赋值。 第一种： 数据类型[] 数组名称 = new 数据类型[长度];这里的[]标识这申明了一个数组，这个[]除了能够放在数据类型前面，也能够放在数组名词前面，成果一样。如果我申明一个长度为2的long类型的数组，并赋值： long[] arr = new long[2];arr[0] = 1;arr[1] = 2;第二种： 数据类型[] 数组名称 = {元素1,元素2, ...};这样在数组初始化的时候间接给数组赋值，数组的长度由元素的个数决定。 二 自定义类封装数组实现数据操作public class MyArray { // 自定义数组 private long[] arr; // 无效数据长度 private int element; public MyArray(){ arr = new long[9]; } public MyArray(int maxsize){ arr = new long[maxsize]; } /** * 显示数组元素 */ public void display(){ System.out.print("["); for (int i = 0; i < element; i++) { System.out.print(arr[i]+" "); } System.out.print("]"); }}2.1 增加元素数组是用间断的内存空间来存储数据的，则每次增加的时候会往以后数组的最初一个元素上增加元素，一次就能够加上元素，所以它的复杂度为O(1)，如果定义一个长度为9数组，数组中曾经有两个元素，则增加第三个元素如下： ...

本文来自OPPO互联网根底技术团队，转载请注名作者。同时欢送关注咱们的公众号：OPPO_tech，与你分享OPPO前沿互联网技术及流动。1. 背景随着业务的疾速倒退，对于很多公司来说，构建于单地区的技术体系架构，会面临诸如上面的多种问题： 基础设施的有限性限度了业务的可扩展性。业务扩充到单个数据中心撑不住，次要机房曾经不能再增加机器，但业务却一直要求扩大机房、城市级别的故障灾祸，影响服务的可持续性。整个机房级别的故障时有发生，每次都引起业务的不可用，对公司的形象与支出都造成重大的影响。如2015年杭州某数据中心光缆被挖断，造成某产品业务几个小时的中断，导致重大的损失跨地区的拜访，影响用户体验等。随着全球化脚步的迫近，试想用户客户端与服务一次交互，一次RTT起码须要10ms，若广州到北京网络提早个别为40ms，当用户客户端须要与服务器产生屡次交互时，对用户体验影响就很大，用户体验十分不敌对。OPPO互联网业务倒退疾速，曾经扩大到寰球，随之带来的是技术上的多机房架构，对数据的寰球多机房同步在一致性、响应工夫、吞吐等方面有更高要求。为了解决以上问题带来的影响，本文将从异地多活底层，数据层面摸索。如何给下层业务提供一个平安、牢靠、稳固的数据环境，让下层业务能够集中精力专一业务开发，缩小对数据多活的关注。 1.1 面临的挑战数据多地写入的抵触解决问题远距离两地传输网络问题同步过程中数据一致性问题数据同步的幂等性问题作为同步核心，对于数据复用问题基于上述挑战，调研比照相干的几个支流开源产品，均有其对应的优劣。如某局部产品针对业务场景变动频繁的业务，数据复用问题无奈解决，对源端数据造成微小的压力。某局部产品针对抵触解决方案无奈达成最终的统一状态等。最终咱们基于开源产品的根底上自研 JinS 数据同步框架，全面解决上述问题。 1.2 多活准则异地多活、同城双活、异地灾备等场景，下层业务有几个根本准则须要遵循： 业务内聚：每个残缺的业务流程，须要在一个机房中实现，不容许跨机房调用。只有保障这样一个前提，能力保证数据没有提早，业务数据的状态扭转足够快。可用性优先：当产生故障切换机房时，优先保证系统可用。需容忍无限时间段内的数据不统一，在预先做修复数据正确：在确保可用的根底下，须要防止数据出错，在产生切换或故障时，如果发现某些数据异样抵触导致无奈笼罩，会阻塞至人工染指，保证数据的正确（后续可间接针对数据锁定跳过操作）1.3 产品性能以后产品已实现性能： 双向同步：反对数据源间的增量实时同步，轻松实现异地多活等利用场景单向同步：反对MySQL的单向同步，MySQL -> Redis 异构同步等，帮忙业务简便实现异地灾备，异构同步等场景数据订阅：用于缓存告诉、业务异步解耦，异构数据源的数据实时同步以及复ETL等多种业务场景一致性校验：可实现MySQL端到端的数据一致性校验以及修复数据迁徙：可实现MySQL的数据迁徙，异构迁徙等场景2. 一致性保障摸索咱们将从三个维度的方向去摸索数据同步一致性。首先通过架构设计，保障系统的稳固、牢靠、可扩大。接着会通过以后业内通用的一致性计划，引出数据同步一致性的根本实现。最初通过具体计划施行的维度，来摸索施行过程中的细节。 2.1 架构设计 上图为数据同步的整体架构图。主流程中分为订阅模块和生产模块。订阅模块通过dump协定从源端MySQL 中拉取数据，生产端通过与订阅模块的通信，获取须要同步的数据，写入到指标端中。 订阅模块订阅模块蕴含parser（dump拉取）、sink（过滤）、store（存储）、registry（注册）、monitor（监控）、protocol（协定） 生产模块生产模块蕴含input（与订阅模块交互）、filter（过滤）、output（输入）、registry（注册）、monitor（监控） Manager治理平台模块，负责实现流程一体化。服务部署，分类，监控，告警等流程治理 Consul注册核心，负责实现订阅、生产节点的服务主动注册，与prometheus实现监控主动发现，并于Manager模块实现kv告警指标存储 Consul template通过consul kv实现告警规定文件生成，并交付至prometheus Prometheus、Granfa、AlertManager开源监控平台、开源监控平台可视化界面、开源告警平台 2.2 架构实际因为数据同步中，数据一致性是重中之重。而随着业务的倒退，软件须要一直的迭代。如何从架构层面均衡好其中的关系，使软件在疾速迭代中还要保持稳定、牢靠，是架构施行过程中须要思考的问题。 在理解数据同步架构实际前，先理解一下微内核架构。 2.2.1 微内核架构微内核架构，又称为插件化架构。例如Eclipse这类IDE软件、UNIX这类操作系统、淘宝APP客户端软件、甚至到Dubbo，采纳的都是微内核架构。 微内核架构的设计外围： 插件治理（如何加载插件以及插件加载机会等）插件连贯（如何连贯到外围零碎，如Spring中的依赖注入，eclipse中的OSGI）插件通信（如何实现数据的交互工作） 微内核架构，理论就是面向性能进行拆分的扩展性架构 外围零碎负责具体业务性能无关的通用性能（如插件加载、插件通信等）插件模块负责实现具体业务逻辑2.2.2 数据同步架构数据同步中，生产模块参考微内核架构，将各个模块插件化。registry、monitor、input、filter、output都实现插件可插拔性能。 以Output举例，参考Java SPI、Dubbo SPI机制，基于 “接口 + 策略模式 + 配置文件” 的模式，实现Output的扩大。 配置文件如下： 通过读取配置文件中name的类型，实现对应插件的初始化。主流程中只须要实现接口调用，即可实现插件的调用。 以后生产模块中，已全面实现插件化。订阅模块依然有一部分未实现插件化革新。 2.3 一致性模型摸索章节2.1，2.2中从架构的维度来保障整体的稳定性和扩展性，均衡了软件开发周期中的扩大与稳固之间的关系。上面从实现一致性的角度来摸索数据同步过程中如何达到数据的一致性。 2.3.1 分布式系统问题随着摩尔定律遇到瓶颈，越来越多状况下要依附分布式架构，能力实现海量数据处理能力和可扩大计算能力。如果分布式集群无奈保障处理结果统一的话，那任何建设于其上的业务零碎都无奈失常工作。一致性问题是分布式畛域最根底也是最重要的问题。 因为咱们面临多节点的分布式架构，不可避免会呈现上图中所形容的问题，而这些问题正是形成一致性问题的次要成因。 实现相对现实的严格一致性代价是很大的，通常分为程序一致性和线性一致性。 程序一致性，抽象的说就是保障一个过程内的程序性，多个节点之间的一致性线性一致性，难度更大，让一个零碎看起来像只有一个数据正本，所有操作都是原子性的，抽象说就是多个过程内也须要保障程序性相似Google Spanner，通过 原子时钟 + GPS 的 trueTime 计划，实现分布式数据库的线性一致性。一致性往往是指分布式系统中多个正本对外出现的数据状态，而共识算法，则是形容某一个状态达成统一后果的过程。因而咱们须要辨别，一致性形容的是后果的状态，共识只是实现某一状态统一的伎俩。分布式数据库在通过共识算法实现状态统一的前提下，还须要对多个状态进行程序辨认排序，这是一个相当简单的过程。 ...

单链表 双链表

作者：小傅哥博客：https://bugstack.cn 积淀、分享、成长，让本人和别人都能有所播种！????一、前言讲道理5年开发，没用过数据结构，你只是在做CRUD！ 很多时候大部分程序员????????头疼于，查问慢、效率低、一堆的关联SQL，次要起因是在程序设计上没有做出很好的数据结构。当然也还有一部分是因为老业务代码，或者没有用到一些大数据服务等。 数据结构、算法、设计模式，是每一个程序员成长过程中的内功心法修炼，而你的新技能用的再绚、多线程使的再6、加锁玩的再牛????，也只能阐明你这个人身材好，但身材好是不能抗住子弹的。只有身材+心法都好，都能纵横捭阖。 这一章节是联合HashMap的延展，在Jdk1.8中HashMap是应用桶数组+链表和红黑树实现，所以顺着上一章节的外围原理和API性能解说后，原本这一章节想间接进入到红黑树，但如果想把红黑树学明确，就须要理解他的前因后果，也就是它的前身2-3树????。 二、面试题谢飞机，考你几个简略的知识点???? 飞机，看你简历写理解数据结构，能够简略介绍下2-3树吗？这种树节点有什么特点，与你理解其余的树结构比照下？你看这个图，向外面插入和删除节点，要怎么操作？????飞机，回去等音讯吧！ 三、什么是2-3树日常的学习和一部分搭档的面试中，居然会听????到的是；从HashMap中文红黑树、从数据库索引为B+Tree，但问2-3树的状况就不是很多了。 1. 为什么应用树结构从最基本的起因来看，应用树结构就是为了晋升整体的效率；插入、删除、查找(索引)，尤其是索引操作。因为相比于链表，一个均衡树的索引工夫复杂度是O(logn)，而数组的索引工夫复杂度是O(n)。 从以下的图上能够比照，两者的索引耗时状况； 从上图能够看到，应用树结构无效的升高工夫复杂度，晋升数据索引效率。另外这个规范的树结构，是二叉搜寻树(Binary Search Tree)。除此之外树形构造还有；AVL树、红黑树、2-3树等2. 二叉搜寻树进化链表在树的数据结构中，最先有点是二叉查找树，也就是英文缩写BST树。在应用数据插入的过程中，现实状况下它是一个均衡的二叉树，但实际上可能会呈现二叉树都一边倒，让二叉树像列表一样的数据结构。从而树形构造的工夫复杂度也从O(logn)降级到O(n)，如下图； 二叉搜寻树的数据插入过程是，插入节点与以后树节点做比对，小于在左，大于在右。随着数据的插入程序不同，就会呈现齐全不同的数据结构。可能是一棵均衡二叉树，也极有可能进化成链表的树。当树结构进化成链表当前，整个树索引的性能也跟着进化成链表。综上呢，如果咱们心愿在插入数据后又放弃树的特点，O(logn)的索引性能，那么就须要在插入时进行节点的调整 3. 2-3树解决均衡问题2-3树是什么构造，它怎么解决均衡问题的。带着问题咱们持续????。 2-3树是一种十分奇妙的构造，在放弃树结构的根底上，它容许在一个节点中能够有两个元素，等元素数量等于3个时候再进行调整。通过这种形式呢，来保障整个二叉搜寻树的平衡性。 这样说可能还没有感觉，来看下图； 左侧是二叉搜寻树，右侧是2-3均衡树，别离插入节点4、5，察看树形构造变动。二叉搜寻树开始呈现偏移，节点一遍倒。2-3树通过一个节点中寄存2到3个元素，来调整树形构造，保持平衡。所谓的保持平衡就是从根节点，到每一个最底部的本人点，链路长度统一。2-3树曾经能够解决均衡问题那么，数据是怎么寄存和调整的呢，接下来咱们开始剖析。 四、2-3树应用1. 树结构定义和特点性质2-3树，读法；二三树，个性如下； 序号形容示意图12-，1个数据节点2个树杈23-，2个数据节点3个树杈3三叉与两叉的不同点在于，除了两边的节点，中间件还有一个节点。这个节点是介于2、4之间的值。4当随着插入数据，会呈现长期的一个节点中，有三个元素。这时会被调整成一个二叉树。综上咱们能够总结出，2-3树的一些性质； 2-3树所有子叶节点都在同一层1个节点能够有1到2个数据，如果有三个须要调整树结构1个节点1个数据时，则有两个子节点1个节点2个数据时，则有三个子节点，且两头子节点是介于两个节点间的值2. 数据插入接下来咱们就模仿在二叉搜寻树中进化成链表的数据，插入到2-3树的变动过程，数据包含；1、2、3、4、5、6、7，插入过程图如下； 以上，就是整个数据在插入过程中，2-3树的演化过程，接下来咱们具体解说每一步的变动； ，向节点1插入数据2，此时为了保持平衡，不会新产生分支，只会在一个节点中寄存两个节点。，持续插入数据3，此时这个节点有三数据，1、2、3，是一个长期区域。，把三个数据的节点，两头节点拉起来，调整成树形构造。，持续插入数据4，为了放弃树均衡，会插在节点3的右侧。，持续插入数据5，插入后3、4、5共用1个节点，当一个节点上有三个数据时候，则须要进行调整。，两头节点4向上⏫调整，调整后，1节点在左、3节点在两头、5节点在右。 ，持续插入数据6，在放弃树均衡的状况下，与节点5专用。 ，持续插入数据7，插入后，节点7会与以后的节点 5 6 共用。此时是一个长期寄存，须要调整。初步调整后，抽出6节点，向上寄存，变为2 4 6共用一个节点，这是一个长期状态，还须要持续调整。，因为根节点有三个数据2、4、6，则持续须要把两头节点上移，1、3和5、7 则别离成二叉落到节点2、节点6上。????????希腊字母：(阿尔法)、 (贝塔)、(伽马)、(德尔塔)、(伊普西隆)、(截塔)、(艾塔)、(西塔)、(约塔) 3. 数据删除有了下面数据插入的学习，在看数据删除其实就是一个逆向的过程，在删除的次要包含这样两种状况； 删除了3-节点，也就是蕴含两个数据元素的节点，间接删除即可，不会毁坏树均衡。删除了2-节点，此时会毁坏树均衡，须要将树高缩短或者元素合并，复原树均衡。承接下面????的例子，咱们把数据再从7、6、5、4、3、2、1程序删除，察看2-3树的构造变动，如下； ，删除节点7，因为节点7只有一个数据元素，删除节点5、6合并，但此时毁坏了2-3树的平衡性，须要缩短树高进行调整。，因为删除节点后，整个树结构不均衡，所以须要缩短树高，调整元素。节点2、4合并，节点1、3别离插入左侧和两头。，删除节点6，这个节点是3-节点(能够分出3个叉的意思)，删除后不会毁坏树均衡，放弃不变。，删除节点5，此时会毁坏树均衡，须要把跟节点4下放，与3合并。，删除节点4，这个节点仍旧是3-节点，所以不须要扭转树结构。，删除节点3，此时只有1、2节点，须要合并。 ，删除节点2，此时节点仍旧是3-节点，所以不须要扭转树结构。再看一个略微简单点2-3树删除： 下面????这张图，就一个略微简单点的2-3均衡树，树的删除过程次要包含； 删除4，其实须要将节点3、5合并，指向节点2，放弃树均衡。删除7，节点8、9合并。删除14，节点15上移，复原成3-叉树。????如果有时候不好了解删除，能够试想下，这个要删除的节点，在插入的时候是一个什么成果。 4. 数据索引相比于插入和删除，索引的过程还是比较简单的，不须要调整数据后果。根本准则就是； 小于以后节点值，左侧寻找大于以后节点值，右侧寻找始终到找到索引值，进行。????第一层寻找： ????第二层寻找： ????第三次寻找： 五、总结综上解说了2-3树????的核心内容，通过本章节的学习，能够理解2-3树是一种怎么的数据结构、如何插入数据、删除数据以及数据的索引，同时要晓得这是一种均衡树的构造，包含2-叉和3-叉节点以及数构造随着数据的增加删除调整。2-3树是红黑树的演变前身，通过这一章节的学习就很容易学习红黑树的相干常识，在红黑树中增加数据进行的渲染、旋转等来放弃树均衡。红黑树靠近均衡数据结构方面的常识学习起来，可能会比拟????烧脑，因为须要思考出那种模型构造和变动的过程，所以会感觉艰难。但这个烧脑的过程也是对学习十分有帮忙的，能够迅速建设常识凸起，当冲破不了解到了解，能够有十分多的播种。六、系列举荐面试官都问我啥HashMap外围常识，扰动函数、负载因子、扩容链表拆分，深度学习HashMap数据插入、查找、删除、遍历，源码剖析重学 Java 设计模式，内功心法修炼，22个互联网实在业务场景实战DDD畛域驱动设计实际，畛域层决策规定树服务设计

依据前序，中序结构二叉树1. 题目形容输出某二叉树的前序遍历和中序遍历的后果，请重建出该二叉树。假如输出的前序遍历和中序遍历的后果中都不含反复的数字。 2. 示例例如，给出 前序遍历 preorder = [3,9,20,15,7] 根， 左， 右 中序遍历 inorder = [9,3,15,20,7] 左， 根， 右 返回如下的二叉树： 3. 解题思路思路：前序的第一个元素是根结点的值，在中序中找到该值，中序中该值的右边的元素是根结点的左子树，左边是右子树，而后递归的解决右边和左边 具体来说，前序遍历的第一个值肯定为根节点，对应于中序遍历两头的一个点。在中序遍历序列中，这个点左侧的均为根的左子树，这个点右侧的均为根的右子树。这时能够利用递归，别离取前序遍历[1:i+1]和中序遍历的[:i]对应与左子树持续上一个过程，取前序遍历[i+1:]和中序遍历[i+1]对应于右子树持续上一个过程，最终得以重建二叉树。 Python解决会比较简单一些 4. Java实现/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ import java.util.Arrays; public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] tin) { if (pre.length == 0 || tin.length == 0){ return null; } TreeNode root = new TreeNode(pre[0]); // 找到 第一个元素在 tin 中的地位 int i = getIndex(tin, pre[0]); root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(tin, 0, i)); root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(tin, i+1, tin.length)); return root; } private int getIndex(int[] array, int value){ int index = 0; for (int i = 0; i < array.length; i++){ if (array[i] == value){ index = i; break; } } return index; }}5. Python实现'''输出某二叉树的前序遍历和中序遍历的后果，请重建出该二叉树。假如输出的前序遍历和中序遍历的后果中都不含反复的数字。例如输出前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。''' class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Noneclass Solution: # 返回结构的TreeNode根节点 def reConstructBinaryTree(self, pre, tin): if not pre or not tin: #只有一个数组为空，则退出函数 return if set(pre) != set(tin):#如果数组中有反复元素 return root = TreeNode(pre[0]) i = tin.index(pre[0]) root.left = self.reConstructBinaryTree(pre[1: i+1], tin[: i]) root.right = self.reConstructBinaryTree(pre[i+1: ], tin[i+1: ]) return root pre = [1, 2, 3, 5, 6, 4]tin = [5, 3, 6, 2, 4, 1]test = Solution()newTree = test.reConstructBinaryTree(pre, tin)print(newTree)#中序遍历def inorder(newTree): if newTree: inorder(newTree.left) print(newTree.val) inorder(newTree.right)inorder(newTree) ...

依据前序，中序结构二叉树1. 题目形容输出某二叉树的前序遍历和中序遍历的后果，请重建出该二叉树。假如输出的前序遍历和中序遍历的后果中都不含反复的数字。 2. 示例例如，给出 前序遍历 preorder = [3,9,20,15,7] 根， 左， 右 中序遍历 inorder = [9,3,15,20,7] 左， 根， 右 返回如下的二叉树： 3. 解题思路思路：前序的第一个元素是根结点的值，在中序中找到该值，中序中该值的右边的元素是根结点的左子树，左边是右子树，而后递归的解决右边和左边 具体来说，前序遍历的第一个值肯定为根节点，对应于中序遍历两头的一个点。在中序遍历序列中，这个点左侧的均为根的左子树，这个点右侧的均为根的右子树。这时能够利用递归，别离取前序遍历[1:i+1]和中序遍历的[:i]对应与左子树持续上一个过程，取前序遍历[i+1:]和中序遍历[i+1]对应于右子树持续上一个过程，最终得以重建二叉树。 Python解决会比较简单一些 4. Java实现/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ import java.util.Arrays; public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] tin) { if (pre.length == 0 || tin.length == 0){ return null; } TreeNode root = new TreeNode(pre[0]); // 找到 第一个元素在 tin 中的地位 int i = getIndex(tin, pre[0]); root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(tin, 0, i)); root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(tin, i+1, tin.length)); return root; } private int getIndex(int[] array, int value){ int index = 0; for (int i = 0; i < array.length; i++){ if (array[i] == value){ index = i; break; } } return index; }}5. Python实现'''输出某二叉树的前序遍历和中序遍历的后果，请重建出该二叉树。假如输出的前序遍历和中序遍历的后果中都不含反复的数字。例如输出前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。''' class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Noneclass Solution: # 返回结构的TreeNode根节点 def reConstructBinaryTree(self, pre, tin): if not pre or not tin: #只有一个数组为空，则退出函数 return if set(pre) != set(tin):#如果数组中有反复元素 return root = TreeNode(pre[0]) i = tin.index(pre[0]) root.left = self.reConstructBinaryTree(pre[1: i+1], tin[: i]) root.right = self.reConstructBinaryTree(pre[i+1: ], tin[i+1: ]) return root pre = [1, 2, 3, 5, 6, 4]tin = [5, 3, 6, 2, 4, 1]test = Solution()newTree = test.reConstructBinaryTree(pre, tin)print(newTree)#中序遍历def inorder(newTree): if newTree: inorder(newTree.left) print(newTree.val) inorder(newTree.right)inorder(newTree) ...

从尾到头打印单链表值1. 题目形容输出一个链表，按链表从尾到头的程序返回一个ArrayList。 2. 示例无 3. 解题思路此题比较简单 第一种办法：应用数组。先从头到尾读取链表数据，保留到一个数组a中。因为要获取从尾到头数据，新开一个数组b，从数组a尾部到头部开始读取，保留到数组b中。 第二种办法：应用栈。先从头到尾读取链表数据，保留到一个栈a中。利用栈先进后出的性质，pop到数组a中。 4. Java实现办法一：应用数组/*** public class ListNode {* int val;* ListNode next = null;** ListNode(int val) {* this.val = val;* }* }**/import java.util.ArrayList;public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> res = new ArrayList(); if (listNode == null){ return res; } while(listNode != null){ res.add(listNode.val); listNode = listNode.next; } ArrayList<Integer> ress = new ArrayList(); for(int i = res.size()-1; i >= 0; i--){ ress.add(res.get(i)); } return ress; }}办法二：应用栈/*** public class ListNode {* int val;* ListNode next = null;** ListNode(int val) {* this.val = val;* }* }**/import java.util.ArrayList;import java.util.Stack; public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { // 应用栈构造实现 ArrayList<Integer> res = new ArrayList(); if (listNode == null){ return res; } Stack<Integer> stack = new Stack(); while (listNode != null){ stack.push(listNode.val); listNode = listNode.next; } while (!stack.isEmpty()){ res.add(stack.pop()); } return res; }}5. Python实现第一种办法应用栈第二种间接数组头插法，代码简洁，然而复杂度较高 ...

从尾到头打印单链表值1. 题目形容输出一个链表，按链表从尾到头的程序返回一个ArrayList。 2. 示例无 3. 解题思路此题比较简单 第一种办法：应用数组。先从头到尾读取链表数据，保留到一个数组a中。因为要获取从尾到头数据，新开一个数组b，从数组a尾部到头部开始读取，保留到数组b中。 第二种办法：应用栈。先从头到尾读取链表数据，保留到一个栈a中。利用栈先进后出的性质，pop到数组a中。 4. Java实现办法一：应用数组/*** public class ListNode {* int val;* ListNode next = null;** ListNode(int val) {* this.val = val;* }* }**/import java.util.ArrayList;public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> res = new ArrayList(); if (listNode == null){ return res; } while(listNode != null){ res.add(listNode.val); listNode = listNode.next; } ArrayList<Integer> ress = new ArrayList(); for(int i = res.size()-1; i >= 0; i--){ ress.add(res.get(i)); } return ress; }}办法二：应用栈/*** public class ListNode {* int val;* ListNode next = null;** ListNode(int val) {* this.val = val;* }* }**/import java.util.ArrayList;import java.util.Stack; public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { // 应用栈构造实现 ArrayList<Integer> res = new ArrayList(); if (listNode == null){ return res; } Stack<Integer> stack = new Stack(); while (listNode != null){ stack.push(listNode.val); listNode = listNode.next; } while (!stack.isEmpty()){ res.add(stack.pop()); } return res; }}5. Python实现第一种办法应用栈第二种间接数组头插法，代码简洁，然而复杂度较高 ...

替换空格1. 题目形容请实现一个函数，将一个字符串中的空格替换成“%20”。 2. 示例例如，当字符串为We Are Happy.则通过替换之后的字符串为We%20Are%20Happy。 3. 解题思路此题比较简单 第一种办法：新开一个内存空间，遍历原字符串数组，如果碰到字符为空格，则append %20进新的空间 第二种办法：不开拓新的空间，首先统计空格数量，从而计算出新的空间大大小，从前面往前面挪动。 4. Java实现办法一：新开一个内存空间// 新开一个内存空间public class Solution { public String replaceSpace(StringBuffer str) { //创立一个新的空间 StringBuffer out = new StringBuffer(); for (int i = 0; i < str.length(); i++){ char a = str.charAt(i); if (a == ' '){ out.append("%20"); }else{ out.append(a); } } return out.toString(); }}办法二：不开拓新的空间，从前面往前面挪动public class Solution { public String replaceSpace(StringBuffer str) { // 计算空格的数量 int spaceNum = 0; for (int i = 0; i < str.length(); i++){ char a = str.charAt(i); if (a == ' '){ spaceNum ++; } } // 开拓空间 int oldIndex = str.length()-1; // 原字符串的下标 int newLength = str.length() + spaceNum * 2; int newIndex = newLength -1; str.setLength(newLength); // 从新设置字符串的长度 while(newIndex >= 0){ if (str.charAt(oldIndex) != ' '){ str.setCharAt(newIndex, str.charAt(oldIndex)); oldIndex --; newIndex --; }else{ str.setCharAt(newIndex--, '0'); str.setCharAt(newIndex--, '2'); str.setCharAt(newIndex--, '%'); oldIndex--; // 只进行一次减 1 } } return str.toString(); }}5. Python实现办法一：下列的字符串是 不可变对象，应用 + 操作时，会产生许多的对象，所以最好应用第二种办法class Solution(): def replaceSpace(self, s): if type(s) != str: return new_s = '' for sr in s: if sr == ' ': new_s += '%20' else: new_s += sr return new_s so = Solution()s = ' ab c d e 'print(so.replaceSpace(s))# %20ab%20c%20d%20e%20print(s.replace(' ', '%20'))办法二：转换成列表模式class Solution: def replaceSpace(self, s): if type(s) != str: return li = list(s) for i in range(len(li)): if li[i] == ' ': li[i] = '%20' res = "".join(li) return resso = Solution()s = ' ab c d e 'print(so.replaceSpace(s))如果您感觉本文有用，请点个“在看” ...

替换空格1. 题目形容请实现一个函数，将一个字符串中的空格替换成“%20”。 2. 示例例如，当字符串为We Are Happy.则通过替换之后的字符串为We%20Are%20Happy。 3. 解题思路此题比较简单 第一种办法：新开一个内存空间，遍历原字符串数组，如果碰到字符为空格，则append %20进新的空间 第二种办法：不开拓新的空间，首先统计空格数量，从而计算出新的空间大大小，从前面往前面挪动。 4. Java实现办法一：新开一个内存空间// 新开一个内存空间public class Solution { public String replaceSpace(StringBuffer str) { //创立一个新的空间 StringBuffer out = new StringBuffer(); for (int i = 0; i < str.length(); i++){ char a = str.charAt(i); if (a == ' '){ out.append("%20"); }else{ out.append(a); } } return out.toString(); }}办法二：不开拓新的空间，从前面往前面挪动public class Solution { public String replaceSpace(StringBuffer str) { // 计算空格的数量 int spaceNum = 0; for (int i = 0; i < str.length(); i++){ char a = str.charAt(i); if (a == ' '){ spaceNum ++; } } // 开拓空间 int oldIndex = str.length()-1; // 原字符串的下标 int newLength = str.length() + spaceNum * 2; int newIndex = newLength -1; str.setLength(newLength); // 从新设置字符串的长度 while(newIndex >= 0){ if (str.charAt(oldIndex) != ' '){ str.setCharAt(newIndex, str.charAt(oldIndex)); oldIndex --; newIndex --; }else{ str.setCharAt(newIndex--, '0'); str.setCharAt(newIndex--, '2'); str.setCharAt(newIndex--, '%'); oldIndex--; // 只进行一次减 1 } } return str.toString(); }}5. Python实现办法一：下列的字符串是 不可变对象，应用 + 操作时，会产生许多的对象，所以最好应用第二种办法class Solution(): def replaceSpace(self, s): if type(s) != str: return new_s = '' for sr in s: if sr == ' ': new_s += '%20' else: new_s += sr return new_s so = Solution()s = ' ab c d e 'print(so.replaceSpace(s))# %20ab%20c%20d%20e%20print(s.replace(' ', '%20'))办法二：转换成列表模式class Solution: def replaceSpace(self, s): if type(s) != str: return li = list(s) for i in range(len(li)): if li[i] == ' ': li[i] = '%20' res = "".join(li) return resso = Solution()s = ' ab c d e 'print(so.replaceSpace(s))如果您感觉本文有用，请点个“在看” ...

二分搜寻树什么是树？ 树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的构造，很象自然界中的树那样。二分搜寻树的每一个节点的值都大于左子树的所有节点的值，同时小于其右子树的所有节点的值，每一颗子树都是一颗二分搜寻树。 须要留神的是二分搜寻树并不一定每个节点都有子节点，并且存储的元素必须有可比拟值。 向二分搜寻树增加元素 如上图所示，咱们如果想插入28元素，咱们须要判断插入在根节点的左孩子还是右孩子，28比41小，所以要插入在左孩子里，而后比拟22，发现比22大所以要比拟22的右孩子，而后比拟33，发现比33小所以就比拟33的左孩子，然而发现33没有左孩子了，这个时候咱们就能够将28插入在33的左孩子地位。 应用递归实现增加操作 public class BST<E extends Comparable<E>> { private class Node { private E e; //定义左节点和右节点 private Node left, right; public Node(E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public int size() { return size; } public boolean isEmpty() { return size == 0; } public void add(E e) { root = add(root, e); } //向以node为根的二分搜寻树中插入元素E，递归算法 private Node add(Node node, E e) { if (node == null) { size++; return new Node(e); } if (e.compareTo(node.e) < 0) { node.left = add(node.left, e); } else if (e.compareTo(node.e) > 0) { node.right = add(node.right, e); } return node; }}二分搜寻树查问元素具体实现逻辑和增加相似，都是应用递归来实现。 ...

栈和队列栈也是一种线性构造相比数组，栈对应的操作是数组的子集只能从一端增加元素，也只能从一端取出元素这一端称为栈顶栈是一种后进先出的数据结构（LIFO） 举一个例子，咱们平时敲代码都常常撤销，而撤销操作的原理就是靠栈来实现的。 比方咱们先打出 "沉迷"、"学习"、"不法"，这个时候咱们发现打错了无奈两个字，而这个时候栈是这样的。 通过应用撤销性能，不法将从栈顶取出，而后删除不法两个字。这个时候栈中就只有两个元素。 再举一个深刻的例子：程序调用的零碎栈 假如咱们有三个函数。 咱们通过调用函数A，在执行第二行执行B函数的时候，暂停函数A。这个时候就会将暂停的函数A压入栈中。 而后调用函数B里的C函数时候，也会将函数B压入栈中， 当函数C执行完了当前，会首先取出栈中的B2，而后继续执行B2剩下的函数，执行实现当前执行A2。 栈的根本实现定义一个Stack接口和实现类 public interface Stack<E> { int getSize(); boolean isEmpty(); void push(E e); E pop(); E peek();} public class ArrayStack<E> implements Stack<E>{ private Array<E> array; public ArrayStack(){ array = new Array<>(); } public ArrayStack(int capacity){ array = new Array<>(capacity); } @Override public int getSize() { return array.getSize(); } @Override public boolean isEmpty() { return array.isEmpty(); } //增加到栈顶 @Override public void push(E e) { array.addLast(e); } //取出并移除栈顶元素 @Override public E pop() { return array.removeLast(); } //查看栈顶元素 @Override public E peek() { return array.get(array.getSize() - 1); } public int getCapacity(){ return array.getCapacity(); } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Stack: "); res.append("["); for (int i = 0; i < array.getSize(); i++) { res.append(array.get(i)); if (i != array.getSize() - 1) { res.append(", "); } } res.append("] top"); return res.toString(); }}创立测试类 ...

栈和队列栈也是一种线性构造相比数组，栈对应的操作是数组的子集只能从一端增加元素，也只能从一端取出元素这一端称为栈顶栈是一种后进先出的数据结构（LIFO） 举一个例子，咱们平时敲代码都常常撤销，而撤销操作的原理就是靠栈来实现的。 比方咱们先打出 "沉迷"、"学习"、"不法"，这个时候咱们发现打错了无奈两个字，而这个时候栈是这样的。 通过应用撤销性能，不法将从栈顶取出，而后删除不法两个字。这个时候栈中就只有两个元素。 再举一个深刻的例子：程序调用的零碎栈 假如咱们有三个函数。 咱们通过调用函数A，在执行第二行执行B函数的时候，暂停函数A。这个时候就会将暂停的函数A压入栈中。 而后调用函数B里的C函数时候，也会将函数B压入栈中， 当函数C执行完了当前，会首先取出栈中的B2，而后继续执行B2剩下的函数，执行实现当前执行A2。 栈的根本实现定义一个Stack接口和实现类 public interface Stack<E> { int getSize(); boolean isEmpty(); void push(E e); E pop(); E peek();} public class ArrayStack<E> implements Stack<E>{ private Array<E> array; public ArrayStack(){ array = new Array<>(); } public ArrayStack(int capacity){ array = new Array<>(capacity); } @Override public int getSize() { return array.getSize(); } @Override public boolean isEmpty() { return array.isEmpty(); } //增加到栈顶 @Override public void push(E e) { array.addLast(e); } //取出并移除栈顶元素 @Override public E pop() { return array.removeLast(); } //查看栈顶元素 @Override public E peek() { return array.get(array.getSize() - 1); } public int getCapacity(){ return array.getCapacity(); } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Stack: "); res.append("["); for (int i = 0; i < array.getSize(); i++) { res.append(array.get(i)); if (i != array.getSize() - 1) { res.append(", "); } } res.append("] top"); return res.toString(); }}创立测试类 ...

数组什么是数组？ 数组就是把数据码成一排进行寄存 须要留神的是数组的索引是从0开始应用Java中的数组public static void main(String[] args) { //定义数组以及长度为10 int[] arr = new int[10]; for (int i = 0; i < arr.length; i++) { arr[i] = i; } //定义数组以及数据 int[] scores = new int[]{100, 99, 98}; //批改第0个值为10 scores[0] = 10; for (int score : scores) { System.out.println(score); }}封装属于咱们的数组数组最大的长处：疾速查问。 scores[2]数组最好利用于"索引有语意"的状况。然而并非所有有语意的索引都实用于数组例如：身份证号，如果想用身份证号来当索引的话，咱们要开拓一个很大的空间。 索引没有语意的状况下，如何示意没有元素？ 如何增加元素？如何删除元素？ 基于Java的数组，二次封装属于咱们本人的数组类。 public class Array { private int[] data; private int size; //无参数的构造函数，默认的数组容量大小为10 public Array() { this(10); } //构造函数，传入数组的容量capacity结构Array public Array(int capacity) { data = new int[capacity]; size = 0; } //获取数组中的元素个数 public int getSize() { return size; } //获取数组的容量 public int getCapacity() { return data.length; } public boolean isEmpty() { return size == 0; } }向数组中增加元素 ...

栈是一个先入后出(FILO-FirstInLastOut)的有序列表。 栈是限度线性表中元素的插入和删除只能在线性表的同一端进行的一种非凡线性表。容许插入和删除的一端，为变动的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。依据栈的定义可知，最先放入栈中元素在栈底，最初放入的元素在栈顶，而删除元素刚好相同，最初放入的元素最先删除，最先放入的元素最初删除。 public class ArrayStackDemo { public static void main(String[] args) { ArrayStack stack = new ArrayStack(5); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); stack.list(); stack.pop(); stack.list(); }}//定义一个 ArrayStack 示意栈class ArrayStack { private int maxSize; // 栈的大小 private int[] stack; // 数组，数组模仿栈，数据就放在该数组 private int top = -1;// top示意栈顶，初始化为-1 //结构器 public ArrayStack(int maxSize) { this.maxSize = maxSize; stack = new int[this.maxSize]; } //栈满 public boolean isFull() { return top == maxSize - 1; } //栈空 public boolean isEmpty() { return top == -1; } //入栈-push public void push(int value) { //先判断栈是否满 if(isFull()) { System.out.println("栈满"); return; } top++; stack[top] = value; } //出栈-pop, 将栈顶的数据返回 public int pop() { //先判断栈是否空 if(isEmpty()) { //抛出异样 throw new RuntimeException("栈空，没有数据~"); } int value = stack[top]; top--; return value; } //显示栈的状况[遍历栈]， 遍历时，须要从栈顶开始显示数据 public void list() { if(isEmpty()) { System.out.println("栈空，没有数据~~"); return; } //须要从栈顶开始显示数据 for(int i = top; i >= 0 ; i--) { System.out.println(String.valueOf(stack[i])); } } }中断表达式实现计算器思路剖析：筹备两个栈，一个存数，一个存运算符1.通过一个index值遍历表达式2.如果发现以后是一个数字，间接入数栈3.如果发现以后是一个符号 ...

1.链表是以节点的形式来存储，是链式存储2.每个节点蕴含 data 域，next 域：指向下一个节点3.链表的各个节点不肯定是间断存储4.链表分带头节点的链表和没有头节点的链表，依据理论的需要来确定 单链表a.减少节点思路剖析借助辅助节点，找到最初一个节点的next指向新节点b.删除节点思路剖析借助辅助节点，找到删除节点的前一个节点temptemp.next = temp.next.nextc.批改节点思路剖析借助辅助节点，遍历找到该节点而后批改d.遍历链表思路剖析借助辅助节点，遍历e.获取到单链表的节点的个数遍历，累加f.查找单链表中的倒数第k个节点遍历至总长度-k的节点即为倒数第k个节点g.单链表的反转新建反转头节点reverseHead，遍历原链表，将节点一个个插入反转俩表的第一个节点，最初再把head.next = reverseHead.nexth.从头到尾打印单链表用栈先进后出个性 import java.util.Stack;public class SingleLinkedListDemo { public static void main(String[] args) { SingleLinkedList singleLinkedList = new SingleLinkedList(); Node node1 = new Node(1,"1"); Node node2 = new Node(2,"2"); Node node3 = new Node(3,"3"); Node node4 = new Node(4,"4"); singleLinkedList.add(node1); singleLinkedList.add(node2); singleLinkedList.add(node3); singleLinkedList.add(node4); singleLinkedList.list();// singleLinkedList.del("3");// singleLinkedList.list();// singleLinkedList.update(new Node(2,"10"));// singleLinkedList.list();// singleLinkedList.reversetList();// singleLinkedList.list(); singleLinkedList.reversePrint(); }}class SingleLinkedList { //先初始化一个头节点, 头节点不要动 private Node head = new Node(0,""); //增加节点到单向链表 //1. 找到以后链表的最初节点 //2. 将最初这个节点的next指向新的节点 public void add(Node Node) { //因为head节点不能动，因而咱们须要一个辅助遍历 temp Node temp = head; //遍历链表，找到最初 while (temp.next != null) { temp = temp.next; } //当退出while循环时，temp就指向了链表的最初 //将最初这个节点的next 指向新的节点 temp.next = Node; } //批改节点的信息, 依据no编号来批改 public void update(Node newNode) { //找到须要批改的节点, 依据no编号 //定义一个辅助变量 Node temp = head.next; while(temp != null) { if(temp.index == newNode.index) { temp.data = newNode.data; break; } temp = temp.next; } } //删除节点 //咱们在比拟时，是temp.next.data和须要删除的节点的data比拟 public void del(String data) { Node temp = head; while (temp.next != null) { if (temp.next.data.equals(data)) { temp.next = temp.next.next; break; } temp = temp.next; //temp后移，遍历 } } //显示链表[遍历] public void list() { Node temp = head.next; while (temp != null) { System.out.println(temp.data); //将temp后移 temp = temp.next; } } //获取到单链表的节点的个数,不统计头节点 public int getLength() { int length = 0; Node temp = head.next; while (temp != null) { length ++; //将temp后移 temp = temp.next; } return length; } //查找单链表中的倒数第k个结点 //1. 编写一个办法，一个k //2. k示意是倒数第k个节点 //3. 先把链表从头到尾遍历，失去链表的总的长度 getLength //4. 失去size后，咱们从链表的第一个开始遍历 (size-k)个，就能够失去 //5. 如果找到了，则返回该节点，否则返回null public Node findLastKNode( int k) { //判断如果链表为空，返回null if(head.next == null) { return null;//没有找到 } //第一个遍历失去链表的长度(节点个数) int size = getLength(); //第二次遍历 size-k 地位，就是咱们倒数的第K个节点 //先做一个k的校验 if(k <=0 || k > size) { return null; } //定义给辅助变量， for 循环定位到倒数的index Node temp = head.next; //3 // 3 - 1 = 2 for(int i =0; i< size-k; i++) { temp = temp.next; } return temp; } //将单链表反转 public void reversetList() { //如果以后链表为空，或者只有一个节点，无需反转，间接返回 if(head.next == null || head.next.next == null) { return; } //定义一个辅助的指针(变量)，帮忙咱们遍历原来的链表 Node cur = head.next; Node next = null;// 指向以后节点cur的下一个节点 Node reverseHead = new Node(0, ""); //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端 while(cur != null) { next = cur.next;//先临时保留以后节点的下一个节点，因为前面须要应用 cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的第一个节点 reverseHead.next = cur; //将cur 连贯到新的链表上 cur = next;//让cur后移 } //将head.next 指向 reverseHead.next , 实现单链表的反转 head.next = reverseHead.next; } //能够利用栈这个数据结构，将各个节点压入到栈中，而后利用栈的先进后出的特点，就实现了逆序打印的成果 public void reversePrint() { if(head.next == null) { return;//空链表，不能打印 } //创立要给一个栈，将各个节点压入栈 Stack<Node> stack = new Stack<Node>(); Node cur = head.next; //将链表的所有节点压入栈 while(cur != null) { stack.push(cur); cur = cur.next; //cur后移，这样就能够压入下一个节点 } //将栈中的节点进行打印,pop 出栈 while (stack.size() > 0) { System.out.println(stack.pop().data); //stack的特点是先进后出 } }}//定义Nodeclass Node { public int index;//序号 public String data;//数据 public Node next; //指向下一个节点 public Node(int index,String data) { this.index = index; this.data = data; }}双向链表双向链表的节点比单链表多一个pre节点a.减少节点思路剖析与单链表一样，借助辅助节点，找到最初一个节点的next指向新节点，但双向链表的新节点还需指向最初一个节点 ...

队列是一个有序列表，能够用数组或是链表来实现。遵循先入先出的准则，即：先存入队列的数据，要先取出。后存入的要后取出。 数组实现队列数组队列思路：front=-1 指向队列头的前一个地位rear=-1 指向队列尾的数据(即就是队列最初一个数据)判断队列是否满：front ==rear 判断队列是否空：rear == maxSize-1 class ArrayQueue { private int maxSize; // 示意数组的最大容量 private int front; // 队列头 private int rear; // 队列尾 private int[] arr; // 该数据用于存放数据, 模仿队列 // 创立队列的结构器 public ArrayQueue(int arrMaxSize) { maxSize = arrMaxSize; arr = new int[maxSize]; front = -1; // 指向队列头部，剖析出front是指向队列头的前一个地位. rear = -1; // 指向队列尾，指向队列尾的数据(即就是队列最初一个数据) } // 判断队列是否满 public boolean isFull() { return rear == maxSize - 1; } // 判断队列是否为空 public boolean isEmpty() { return rear == front; } // 增加数据到队列 public void addQueue(int n) { // 判断队列是否满 if (isFull()) { System.out.println("队列满，不能退出数据~"); return; } rear++; // 让rear 后移 arr[rear] = n; } // 获取队列的数据, 出队列 public int getQueue() { // 判断队列是否空 if (isEmpty()) { // 通过抛出异样 throw new RuntimeException("队列空，不能取数据"); } front++; // front后移 return arr[front]; } // 显示队列的所有数据 public void showQueue() { // 遍历 if (isEmpty()) { System.out.println("队列空的，没有数据~~"); return; } for (int i = 0; i < arr.length; i++) { System.out.printf("arr[%d]=%d\n", i, arr[i]); } }环形队列思路：front=0 指向队列第一个元素，也就是说arr[front]就是队列第一个元素rear=0 指向队列的最初一个元素的后一个地位，因为心愿空进去一个空间作为约定判断队列是否满：(rear + 1)% maxSize = front = 0 判断队列是否空：rear == front队列中无效数据个数：(rear + maxSize - front) % maxSize ...

红黑树在最坏状况下二叉查找树的性能非常蹩脚，咱们迫切需要一种可能所有操作都能在对数工夫内实现的数据结构。接下来咱们就来介绍一下一种十分罕用的动静保护的均衡二叉树——红黑树。 在引入红黑树之前，咱们须要理解一下2-3查找树。 2-3查找树2-3查找树的介绍 上图是一个简略的2-3查找树。能够看出，比起一般的二叉查找树，2-3查找树多了一个3-节点。3-节点的性质也是相似于2-节点的。因而，2-3查找树的查找算法与一般二叉查找树的查找算法也是相似的（只是要对3-节点探讨）。 那么，2-3树的插入算法又要怎么实现呢？何时插入2-节点，又要何时插入3-节点呢？ 发明者给出了答案： 2-3查找树的插入算法依据插入元素的大小，查找到插入的地位： 如果插入的地位是一个2-节点，那么就与该节点节点造成3-节点，如下图： 如果插入的地位是一个3-节点，那么就与该节点造成一个4-节点，再从4-节点成长出一个新的2-节点 这个过程咱们能够看出2-3查找树的成长过程： 向树的底部找到地位插入元素，如果插入的地位是2-节点。2-节点会与插入元素一起成长为3-节点。如果是3-节点，那么3-节点会与插入元素造成4-节点。4-节点会向上成长，即两头的元素会与父节点联合。如果父节点是2-节点，就会造成3-节点。如果父节点是3-节点，那么就会造成4-节点持续成长。2-3查找树的性质部分变换：这是与AVL二叉均衡树最大的区别，2-3查找树只须要在部分实现2-3-4节点的变换即可。全局有序，完满均衡：部分变换不会扭转2-3树的有序性与平衡性。这是因为在插入的过程保障有序。惟一一个扭转树高度的操作——4-节点的向上成长，也是左右子树同时高度+1。在一个大小为N的2-3树中，查找和插入操作的拜访的节点必然不超过lgN个。一颗含有N个节点的2-3树的高度在$[lgN,log_3N]$之间。 红黑二叉查找树前言：替换3-节点红黑二叉查找树的根本思维就是用规范的二叉查找树（齐全由2-节点形成）和一些额定的信息（替换3-节点）来示意2-3树。由此咱们将树中的链接分为两个品种：红链接将两个2-节点连接起来形成一个3-节点，黑链接则是2-3树中的一般链接。简略来说：咱们将原来的3-节点示意为一条左斜的红色链接。 基于2-3树的性质以及红黑树的根本思维，咱们能够给出红黑树的定义： 红链接均为左链接；没有任何一个节点同时和两条红链接相连，即不存在4-节点；该树是完满彩色均衡的，即任意空链接（即指向null的节点指针）到根节点的门路上的黑链接数量雷同。满足这些定义的红黑树和相应2-3树是一一对应的。如下图： 如上图：任意空链接到根节点的黑链接都是雷同的——2条。 咱们在Node类（节点）中增加color属性，代表与父节点指向它的链接的色彩： private static final boolean RED = true;private static final boolean BLACK = false;private Node root;private class Node{ Key key; //键 Value val; //相关联的值 Node left, right; //左右子树 int N; //子树中的节点总数 boolean color; //由其父节点指向它的链接的色彩 public Node(Key key, Value val, int n, boolean color) { this.key = key; this.val = val; this.N = n; this.color = color; }}/** * 判断是否是3-节点 */private boolean isRed(Node x){ if (x == null) { return false; } return x.color == RED;}插入操作因为红黑树是二叉树构造的2-3树，因而插入操作实际上是与2-3树一样的。当看到这里时，天然就想到了两个问题： ...

二叉查找树 (Binary Search Tree)概念 二叉查找树又称二叉搜索树，二叉排序树，特点如下: 左子树上所有结点值均小于根结点右子树上所有结点值均大于根结点结点的左右子树本身又是一颗二叉查找树二叉查找树中序遍历得到结果是递增排序的结点序列。BST 的操作代价分析：查找代价：任何一个数据的查找过程都需要从根结点出发，沿某一个路径朝叶子结点前进。因此查找中数据比较次数与树的形态密切相关。 当树中每个结点左右子树高度大致相同时，树高为logN。则平均查找长度与logN成正比，查找的平均时间复杂度在O(logN)数量级上。 当先后插入的关键字有序时，BST退化成单支树结构。此时树高n。平均查找长度为(n+1)/2，查找的平均时间复杂度在O(N)数量级上。 插入代价：新结点插入到树的叶子上，完全不需要改变树中原有结点的组织结构。插入一个结点的代价与查找一个不存在的数据的代价完全相同。 删除代价：当删除一个结点P，首先需要定位到这个结点P，这个过程需要一个查找的代价。然后稍微改变一下树的形态。如果被删除结点的左、右子树只有一个存在，则改变形态的代价仅为O(1)。如果被删除结点的左、右子树均存在，只需要将当P的左孩子的右孩子的右孩子的…的右叶子结点与P互换，在改变一些左右子树即可。因此删除操作的时间复杂度最大不会超过O(logN)。 BST效率总结 :查找最好时间复杂度O(logN)，最坏时间复杂度O(N)。 插入删除操作算法简单，时间复杂度与查找差不多。 平衡二叉查找树 ( Balanced Binary Search Tree )二叉查找树在最差情况下竟然和顺序查找效率相当，这是无法仍受的。事实也证明，当存储数据足够大的时候，树的结构对某些关键字的查找效率影响很大。当然，造成这种情况的主要原因就是BST不够平衡(左右子树高度差太大)。既然如此，那么我们就需要通过一定的算法，将不平衡树改变成平衡树。因此，AVL树就诞生了。 AVL 的操作代价分析：查找代价：AVL是严格平衡的BST（平衡因子不超过1）。那么查找过程与BST一样，只是AVL不会出现最差情况的BST(单支树)。因此查找效率最好，最坏情况都是O(logN)数量级的。 插入代价：AVL必须要保证严格平衡(|bf|<=1)，那么每一次插入数据使得AVL中某些结点的平衡因子超过1就必须进行旋转操作。事实上，AVL的每一次插入结点操作最多只需要旋转1次(单旋转或双旋转)。因此，总体上插入操作的代价仍然在O(logN)级别上(插入结点需要首先查找插入的位置)。 删除代价：AVL删除结点的算法可以参见BST的删除结点，但是删除之后必须检查从删除结点开始到根结点路径上的所有结点的平衡因子。因此删除的代价稍微要大一些。每一次删除操作最多需要O(logN)次旋转。因此，删除操作的时间复杂度为O(logN)+O(logN)=O(2logN) AVL 效率总结 :查找的时间复杂度维持在O(logN)，不会出现最差情况 AVL树在执行每个插入操作时最多需要1次旋转，其时间复杂度在O(logN)左右。 AVL树在执行删除时代价稍大，执行每个删除操作的时间复杂度需要O(2logN)。 红黑树 (Red-Black Tree )二叉平衡树的严格平衡策略以牺牲建立查找结构(插入，删除操作)的代价，换来了稳定的O(logN) 的查找时间复杂度。但是这样做是否值得呢？ 能不能找一种折中策略，即不牺牲太大的建立查找结构的代价，也能保证稳定高效的查找效率呢？ 答案就是：红黑树。 RBT 的操作代价分析：查找代价：由于红黑树的性质(最长路径长度不超过最短路径长度的2倍)，可以说明红黑树虽然不像AVL一样是严格平衡的，但平衡性能还是要比BST要好。其查找代价基本维持在O(logN)左右，但在最差情况下(最长路径是最短路径的2倍少1)，比AVL要略逊色一点。 插入代价：RBT插入结点时，需要旋转操作和变色操作。但由于只需要保证RBT基本平衡就可以了。因此插入结点最多只需要2次旋转，这一点和AVL的插入操作一样。虽然变色操作需要O(logN)，但是变色操作十分简单，代价很小。 删除代价：RBT的删除操作代价要比AVL要好的多，删除一个结点最多只需要3次旋转操作。 RBT 效率总结 :查找 效率最好情况下时间复杂度为O(logN)，但在最坏情况下比AVL要差一些，但也远远好于BST。 插入和删除操作改变树的平衡性的概率要远远小于AVL（RBT不是高度平衡的）。因此需要的旋转操作的可能性要小，而且一旦需要旋转，插入一个结点最多只需要旋转2次，删除最多只需要旋转3次(小于AVL的删除操作所需要的旋转次数)。虽然变色操作的时间复杂度在O(logN)，但是实际上，这种操作由于简单所需要的代价很小。 B~树/B+树 (B-Tree )对于在内存中的查找结构而言，红黑树的效率已经非常好了(实际上很多实际应用还对RBT进行了优化)。但是如果是数据量非常大的查找呢？将这些数据全部放入内存组织成RBT结构显然是不实际的。实际上，像OS中的文件目录存储，数据库中的文件索引结构的存储…. 都不可能在内存中建立查找结构。必须在磁盘中建立好这个结构。那么在这个背景下，RBT还是一种好的选择吗？ 在磁盘中组织查找结构，从任何一个结点指向其他结点都有可能读取一次磁盘数据，再将数据写入内存进行比较。大家都知道，频繁的磁盘IO操作，效率是很低下的(机械运动比电子运动要慢不知道多少)。显而易见，所有的二叉树的查找结构在磁盘中都是低效的。因此，B树很好的解决了这一个问题。 B-Tree的操作代价分析：查找代价：B-Tree作为一个平衡多路查找树(m-叉)。B树的查找分成两种：一种是从一个结点查找另一结点的地址的时候，需要定位磁盘地址(查找地址)，查找代价极高。另一种是将结点中的有序关键字序列放入内存，进行优化查找(可以用折半)，相比查找代价极低。而B树的高度很小，因此在这一背景下，B树比任何二叉结构查找树的效率都要高很多。而且B+树作为B树的变种，其查找效率更高。 插入代价：B-Tree的插入会发生结点的分裂操作。当插入操作引起了s个节点的分裂时，磁盘访问的次数为h(读取搜索路径上的节点)＋2s(回写两个分裂出的新节点)＋1（回写新的根节点或插入后没有导致分裂的节点）。因此，所需要的磁盘访问次数是h+2s+1，最多可达到3h+1。因此插入的代价是很大的。 删除代价：B-Tree的删除会发生结点合并操作。最坏情况下磁盘访问次数是3h＝（找到包含被删除元素需要h次读访问）+（获取第2至h层的最相邻兄弟需要h-1次读访问）+（在第3至h层的合并需要h-2次写访问）+（对修改过的根节点和第2层的两个节点进行3次写访问）。 定义：一颗m阶（m>=3，即一个结点包含的数据和子节点数），3阶B-树有如下特点： 1. 根结点之多3颗子树 2. 定义： define m 3                 /*B 树的阶*/ ...

R-B Tree，全称Red-Black Tree，又称为红黑树，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。红黑树的特性： 节点是红色或黑色。根节点是黑色。每个叶节点（NIL节点，空节点）是黑色的。每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

B-TreeB树中所有结点中孩子结点个数的最大值成为B树的阶，通常用m表示，从查找效率考虑，一般要求m>=3。一棵m阶B树或者是一棵空树，或者是满足以下条件的m叉树。 1）每个结点最多有m个分支（子树）；而最少分支数要看是否为根结点，如果是根结点且不是叶子结点，则至少要有两个分支，非根非叶结点至少有ceil(m/2)个分支，这里ceil代表向上取整。 2）如果一个结点有n-1个关键字，那么该结点有n个分支。这n-1个关键字按照递增顺序排列。 3）每个结点的结构为： n k1 k2 ... kn p0 p1 p2 ... pn 其中，n为该结点中关键字的个数；ki为该结点的关键字且满足ki<ki+1；pi为该结点的孩子结点指针且满足pi所指结点上的关键字大于ki且小于ki+1，p0所指结点上的关键字小于k1，pn所指结点上的关键字大于kn。 4）结点内各关键字互不相等且按从小到大排列。 5）叶子结点处于同一层；可以用空指针表示，是查找失败到达的位置。 B+ TreeB+树是B树的变体，也是一种多路搜索树，定义基本与B树同，除了： 1.非叶子结点的子树指针与关键字个数相同； 2.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B树是开区间）； 3.为所有叶子结点增加一个链指针； 4.所有关键字都在叶子结点出现； 为什么说B+树比B树更适合数据库索引1、 B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。 2、B+树的查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。 3、由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。

线性表线性表的基本概念 线性表的定义线性表是具有相同数据类型的n(n>=0)个元素的有限序列。 线性表的基本操作 什么时候要传入参数的引用“&”？一种是值类型，使用时会直接复制原值，修改参数不会影响原值 一种是引用类型，使用时操作的是原值，修改时直接修改原值！（C语言不支持这种引用类型！） 为什么要实现对数据结构的基本操作？团队合作编程，你定义的数据结构要让别人能够很方便的使用（封装）将常用的操作/运算封装称函数，避免重复工作，降低出错风险。总结 注意⚠️：位序是用1开始计算的！！！ 源码源码查看地址，点击 传送门 吧～如果你这个系列的文章有帮助到你的话，不妨给点个赞吧！那将给我莫大的动力！ 同系列其他文章目录[[数据结构]第一章绪论(1)——数据结构](https://blog.csdn.net/weixin_...[[数据结构]第一章绪论(2)——算法](https://blog.csdn.net/weixin_...[[数据结构]第二章线性表(1)——线性表](https://blog.csdn.net/weixin_...[[数据结构]第二章线性表(2)——顺序表](https://blog.csdn.net/weixin_...[[数据结构]第二章线性表(3)——单链表](https://blog.csdn.net/weixin_...[[数据结构]第二章线性表(4)——双链表](https://blog.csdn.net/weixin_...[[数据结构]第二章线性表(5)——循环链表](https://blog.csdn.net/weixin_...[[数据结构]第二章线性表(6)——静态链表](https://blog.csdn.net/weixin_...[[数据结构]第二章线性表(7)——章节反思](https://blog.csdn.net/weixin_...

算法基本概念 什么是算法？程序=数据结构+算法 算法的特性有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。注：算法必须是有穷的，二程序可以是无穷的。 确定性：算法每一条指令必须有确切的含义，对于相同的输入只能得出相同的输出可行性：算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。输入：一个算法有0个或多个输入，这些输入取自某个特定对象的集合。输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。五个特性，缺一不可 “好”算法的特质正确性：算法应能正确地解决求解问题。可读性：算法应具有良好的可读性，帮助人们理解。健壮性：输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。高效率与底存储量需求：执行速度快，时间复杂度低。不费内存，空间复杂度低。总结 算法效率的度量 如何评估算法时间开销？让算法先运行，事后统计运行时间？ 存在的问题？ 和机器性能有关，比如：超级计算机VS单片机和编程语言有关，越高级的语言执行效率越低，没错，就是越低和编译程序产生的机器指令质量有关有些算法是不能事后统计的，比如，导弹控制算法。评价一个算法优劣时，需要排除与算法本身无关的外界因素，能否事先估计？ 算法时间复杂度事前预估算法时间开销T(n)与问题规模n的关系（T 表示 time） 如何计算T，例子： 问题1:是否可以忽略表达式某些部分？ 加法规则：多项相加，只保留最高阶的项，且系数变为1 乘法规则：多项相乘，都保留 算法时间复杂度阶数顺序 如果有好几千行代码，需要一行一行数？顺序执行的代码只会影响常数项，可以忽略只需要挑循环中的一个基本操作，分析它的执行次数和n的关系就好如果有多层嵌套循环，只需要关注最深层的循环循环了几次小练习 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dQ6nwKRn-1592326001155)(https://tva1.sinaimg.cn/large...] 总结 算法的性能问题只有在n很大时才会暴露出来。 算法空间复杂度原地工作算法 分析空间复杂度时，只需关注与问题规模相关的变量就好（讲人话，就是，看程序中的变量就好） 加法法则 函数递归调用带来的内存开销 在这种情况下，空间复杂度等于递归调用的深度。 递归调用的过程中，每一次开辟的内存空间也可以不一致，如上例。 总结 源码源码查看地址，点击 传送门 吧～如果你这个系列的文章有帮助到你的话，不妨给点个赞吧！那将给我莫大的动力！ 同系列其他文章目录[[数据结构]第一章绪论(1)——数据结构](https://blog.csdn.net/weixin_...[[数据结构]第一章绪论(2)——算法](https://blog.csdn.net/weixin_...[[数据结构]第二章线性表(1)——线性表](https://blog.csdn.net/weixin_...[[数据结构]第二章线性表(2)——顺序表](https://blog.csdn.net/weixin_...[[数据结构]第二章线性表(3)——单链表](https://blog.csdn.net/weixin_...[[数据结构]第二章线性表(4)——双链表](https://blog.csdn.net/weixin_...[[数据结构]第二章线性表(5)——循环链表](https://blog.csdn.net/weixin_...[[数据结构]第二章线性表(6)——静态链表](https://blog.csdn.net/weixin_...[[数据结构]第二章线性表(7)——章节反思](https://blog.csdn.net/weixin_...

绪论第二节——算法基本概念 什么是算法？程序=数据结构+算法 算法的特性有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。注：算法必须是有穷的，二程序可以是无穷的。 确定性：算法每一条指令必须有确切的含义，对于相同的输入只能得出相同的输出可行性：算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。输入：一个算法有0个或多个输入，这些输入取自某个特定对象的集合。输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。五个特性，缺一不可 “好”算法的特质正确性：算法应能正确地解决求解问题。可读性：算法应具有良好的可读性，帮助人们理解。健壮性：输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。高效率与底存储量需求：执行速度快，时间复杂度低。不费内存，空间复杂度低。总结 算法效率的度量 如何评估算法时间开销？让算法先运行，事后统计运行时间？ 存在的问题？ 和机器性能有关，比如：超级计算机VS单片机和编程语言有关，越高级的语言执行效率越低，没错，就是越低和编译程序产生的机器指令质量有关有些算法是不能事后统计的，比如，导弹控制算法。评价一个算法优劣时，需要排除与算法本身无关的外界因素，能否事先估计？ 算法时间复杂度事前预估算法时间开销T(n)与问题规模n的关系（T 表示 time） 如何计算T，例子： 问题1:是否可以忽略表达式某些部分？ 加法规则：多项相加，只保留最高阶的项，且系数变为1 乘法规则：多项相乘，都保留 算法时间复杂度阶数顺序 如果有好几千行代码，需要一行一行数？顺序执行的代码只会影响常数项，可以忽略只需要挑循环中的一个基本操作，分析它的执行次数和n的关系就好如果有多层嵌套循环，只需要关注最深层的循环循环了几次小练习 总结 算法的性能问题只有在n很大时才会暴露出来。 算法空间复杂度原地工作算法 分析空间复杂度时，只需关注与问题规模相关的变量就好（讲人话，就是，看程序中的变量就好） 加法法则 函数递归调用带来的内存开销 在这种情况下，空间复杂度等于递归调用的深度。 递归调用的过程中，每一次开辟的内存空间也可以不一致，如上例。 总结

1.线性表[ 矩阵|数组|字符串|堆栈|队列 ] 1).概念 除首尾元素外,每个元素都有唯一一个直接前驱和唯一直接后继2).特点 同一性,有穷性,有序性3).存储方式 a.顺序存储(连续空间) b.链式存储 a).单链表(数据域+指针域) b).循环链表(首尾相接的链表) c).双向链表(前驱指针域+数据域+后驱指针域) d).静态链表(顺序存储数组模拟链表,设置游标模拟指针)4).栈|队列|串|数组 a.栈(限定性线性表) a).后进先出 b).栈顶入栈,出栈 c).顺序栈|链栈 b.队列(限定性线性表) a).先进先出 b).队尾入,队首出 c).链队列|循环队列 c.串(特定的线性表) a).定长顺序串|块链串 d.数组(线性表的扩充) a).三角矩阵| 带状矩阵 | 稀疏矩阵(三元组表示&十字链表) e.广义表(线性表的扩充) a).头尾链表(表结点(标志域+表头指针+表尾指针),元素结点(标志域+值域)) b).扩展线性链表(表结点(标志域+表头指针+表尾指针),原子结点(标志域+值域+表尾指针))2.树 1).表示法 a.倒置树结构 b.文氏图 c.广义表[嵌套括号](A(B(C,D)),E(F),G) d.陷入式2).二叉树 a.概念 每个结点的度都不大于2 & 每个结点的孩子结点次序不能任意颠倒 b.存储结构 a).顺序存储 | 链式存储([二叉链表]左孩子域+数据域+右孩子域) c.遍历顺序 a).先序(根左右) | 中序(左根右) | 后序(左右根)3).线索二叉树 a.结构(左孩子域+前驱结点指针+数据域+后继结点指针+右孩子域)4).哈夫曼树 a.概念 带权路径长度最短的二叉树 b.哈夫曼编码(左分支0右分支1)3.图 1).网状数据结构2).存储方法 a.邻接矩阵(数组) b.邻接表(稀疏图) a).表头结构(数据域+链域) b).弧结点结构(邻接点域+数据域+链域) c.邻接多重表 a).顶点结构(data+firstedge) b).边结点结构(mark+ivex+ilink+jvex+jlink+info) d.十字链表 a).顶点结构(data+firstin+firstout) b).弧结点结构(tailvex+headvex+hlink+tlink+info)3).遍历 a.深度优先 b.广度优先4.查找 ...

下面哪种排序方法是从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。（插入排序    ） 对序列15, 9, 7, 8, 20, -1, 4进行排序，若经一趟排序后的排列为9, 15, 7, 8, 20, -1, 4，则采用的是（   C  ）排序。A.选择B.堆C.直接插入D.冒泡选择排序是每次选择未排序子列中最大（最小）的放到最后，显然4不是最值，所以A不对；冒泡排序是相邻两两比较，把最大的顶上去（顶到最左边或者最右边），显然边上两个元素不是最值，所以B也不对；希尔排序是先分组，然后针对组内采取插入排序，如果是希尔排序，那么9和15颠倒，20和-1也应该颠倒，所以D也不对；插入排序是从第二项开始与前面每一项比较，如果小于那一项，则插入那一项前面，C中第二项9比15小，所以放到15前面，完成一趟 对初始状态为递增序列的数组按递增顺序排序，最省时间的是插入排序算法，最费时间的是算法（ 快速排序）堆排序：最好最坏都是nlogn快排：最好情况一趟比较可以划分两等份nlogn 最坏相对有序n*n插入：最好相对有序n  最坏n*n归并：最好最坏都是nlogn 将序列(Q, H, C, Y, P, A, M, S, R, D, F, X)中的关键字按升序排列，则（  F,H,C,D,P,A,M,Q,R,S,Y,X）是以第一个元素为枢轴的快速排序一趟扫描的结果。以Q为基准值,放到外面首先从后往前,到f比q小,填充到刚才q的位置 然后从前往后到y比q大,放到刚才的f的原始位置 再从后往前,d比q小,放到y原来的位置 再从前往后,到s比q大,放到d原来的位置 接下来,前后两个标志碰头了 将基准q放到刚才最后移动的s的原来位置上 快速排序方法在要排序的数据已基本有序情况下最不利于发挥其长处。快速排序的基本思想是以基准元素为中心，将待排序表分成两个子表，然后继续对子表进行划分，直到所有子表的长度为1。如果每次划分结果，两个子表长度相等，则效率最高，如果一个子表的长度为0则效率最低。对已基本有序的表以第1个为标准进行划分时，其中一个表长度将基本为0，效率最低。 设有5000个元素，希望用最快的速度挑选出前10个最大的，采用（    堆排序 ）方法最好。用堆排序最好，因为堆排序不需要等整个排序结束就可挑出前10个最大元素，而快速排序和基数排序都需等待整个排序结束才能知道前10个最大元素。何为堆？ 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（C）。快速排序堆排序归并排序直接插入排序 若要求尽可能快地对序列进行稳定的排序，则应选（ B   ）。A.快速排序 B.归并排序 C.冒泡排序“快些（希）选队（堆）”不稳定；稳定的排序算法：插入排序、冒泡排序、归并排序、基数排序直接插入，简单选择和冒泡排序都是比较慢的。 当待排序序列基本有序或个数较小的情况下，最佳的内部排序方法是（  直接插入排序   ）。当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需n-1趟排序，也即时间复杂度仍为O(n^2)。而对简单选择排序来说，其比较次数与待排序列的初始状态无关，都是每次选择未排序子列中最大（最小）的放到最后；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时间复杂度为O(n log2n)；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也即n-1趟比较的时间复杂度由O(n^2)降至O(n)。各种排序方法的选择:①就平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。当n较大时，归并排序较堆排序省，但归并排序所需的辅助空间最大。②简单排序方法中，直接插入排序最简单，当待排序的结点已按键值“基本有序”且n较小时，则应采用直接插入排序或冒泡排序，直接插入排序比冒泡排序更快些，因此经常将直接插入排序和其他的排序方法结合在一起使用。③当n很大且键值位数较小时，采用基数排序较好；而当键值的最高位分布较均匀时，可先按其最高位将待排序结点分成若干子表，而后对各子表进行直接插入排序。 ④从方法的稳定性来比较，直接插入排序、冒泡排序、归并排序和基数排序是稳定的排序方法；而直接选择排序、希尔排序、堆排序和快速排序都是不稳定的排序方法。 内部排序方法的选择:各种排序方法各有优缺点，故在不同情况下可作不同的选择。通常需考虑的因素有：待排序的记录个数；记录本身的大小；记录的键值分布情况等。若待排序的记录个数n较小时，可采用简单排序方法 若n 较大时，应采用快速排序或堆排序。 若待排序的记录已基本有序，可采用起泡排序。 链式基数排序采用的是LSD的方法而基数排序就是借助“分配”和“收集”对单逻辑关键字进行排序的方法 排序的时间复杂度和空间复杂度快速排序的时间复杂度为O(nlogn)，空间复杂度也是O(nlogn)。 归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。 堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。 选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。 在分配排序时,最高位优先分配法比最低位优先分配法简单(错，两者无直接关系)基数排序是桶排序的改进，改进空间复杂度。而基数排序中，只有最低位优先分配法才能取得正确结果，但是最高位和最低位的时间复杂度一样的。 进一步了解桶排序和基数排序桶排序和基数排序均属于分配排序。分配排序的基本思想：排序过程无须比较关键字，而是通过用额外的空间来"分配"和"收集"来实现排序，它们的时间复杂度可达到线性阶：O(n)。简言之就是：用空间换时间，所以性能与基于比较的排序才有数量级的提高！ 桶排序(Bucket Sort)，也称箱排序 基本思想：设置若干个箱子，依次扫描待排序的记录 array[0]，array[1]，…，array[n - 1]，把关键字等于 k 的记录全都装入到第 k 个箱子里(分配)，然后按序号依次将各非空的箱子里的记录收集起来，从而完成排序。 桶排序所需要的额外空间取决于关键字的个数，若 array[0..n - 1] 中关键字的取值范围是 0 到 m - 1 的整数，则必须设置 m 个箱子。因此箱排序要求关键字的类型是有限类型，否则可能要无限个箱子。一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的，故箱子的类型应设计成链表为宜。 ...

下面4张有向图中，哪个不属于强连通图。（ B）首先明确何为强连通图：对一个有向图，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。判定方法：任取有向图G的某结点S，从S开始进行深度优先搜索，若可以遍历G的所有结点；再将G的所有边反向，再次从S开始进行深度优先搜索，如果再次能够遍历G的所有结点，则G是强连通图，两次搜索有一次无法遍历所有结点，则G不是强连通图。此外，上述搜索可以换成广度优先搜索等其他方案。 某个无向图共有16条边，每个顶点的度均为2，则该无向图的顶点数为（  16  ）每条边有两个顶点，所以总度数为16*2=32；又因为每个点度数为2，所以一共16条边 若某无向图一共有16条边，并且有3个度为4的顶点，4个度为3的顶点，其余顶点的度均小于3，则该无向图至少有多少个顶点？至多有多少个节点每条边有两个顶点，16*2=32，所以总度数为32；32-34-43=8剩余节点度均小于3，则最大为2 所以至少的就是剩余节度点均为2，即8/2=4，则得到3+4+4=11最大的就是剩余节度点均为1，是3+4+8=15 求下图中顶点0到5的最短路径是（  012435  ）我们使用Dijkstra算法来求两点间最短路径： 第1 步：所有Wi初始化为无穷大∞；第2步：设0已访问；更新与0直接相连的所有结点的W；并将这些结点加入“待访问结点列表”。w1=1，w2=4;第3步：找出 中W最小的结点，设其“已访问”；即w1已访问。考察与它直接相连的未访问结点(若有与已访问节点相连的不再考察 )，累加并更新它们的W(若比所保存的W小才更新) ，并将它们加入“待访问结点列表”。w2=3,w3=8,w4=6第3步（重复此步）：找出待访问中W最小的结点，设其“已访问”；w2.考察与它直接相连的、未访问结点(若有与已访问节点相连的不再考察 )，累加并更新它们的W(若比所保存的W小才更新) ，并将它们加入“待访问结点列表” 。w4=4 下列关于AOE网的叙述中,不正确的是(B)关键活动不按期完成就会影响整个工程的完成时间任何一个关键活动提前完成,那么整个工程将会提前完成所有的关键活动提前完成,那么整个工程将会提前完成某些关键活动若提前完成,那么整个工程将会提前完成首先要知道何为关键活动和关键路径，关键路径是图中的最长路径，关键路径长度代表整个工期的最短完成时间；关键活动则组成了关键路径关键活动延期完成，必将导致关键路径长度增加，即整个工期的最短完成时间增加，因此A正确。关键路径并不唯一，当有多条关键路径存在时，其中一条关键路径上的关键活动时间缩短，只能导致本条关键路径变成非关键路径，而无法缩短整个工期，因为其他关键路径没有变化，因此B项不正确。对于A，B两项要搞懂的是，当关键路径不唯一时，任何一条关键路径上的关键活动变长，都会使这条关键路径变成更长的关键路径，并且导致其他关键路径变成非关键路径，因此整个工期延长。所以某些关键活动缩短则不一定缩短整个工期。理解了A,B两项，C,D就很容易理解了 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( 逆拓扑有序 )DFS是一个递归算法,在遍历的过程中,先访问的点被压入栈底。拓扑有序是指如果点U到点V有一条弧,则在拓扑序列中U一定在V之前.深度优先算法搜索路径恰恰是一条弧,栈的输出是从最后一个被访问点开始输出,最后一个输出的点是第一个被访问的点.所以是逆的拓扑有序序列 下面所示的有向图，其拓扑排序的结果序列是（   ）。 A.125634B.516234C.123456D. 521643第一种做法，排除法：按照拓扑排序的定义，若有向无环图中存在一条从i到j的边，则拓扑排序中i一定在j的前面。我们就看有没有j在i前边的第二种做法，每次选取极大顶点（入度为0的顶点），并把它跟它的出度一起从图中删掉 任一个有向无环图的拓扑序列的数量有（一个或多个 ）。有向无环图的拓扑排序可以看成图的层序遍历，每一层的顶点可以有不同的顺序，这就造成拓扑排序序列不唯一 一个n个顶点的连通无向图,其边的个数至少为(N-1)完全图是每对顶点之间都恰连有一条边的简单图，N个端点的完全图有 n(n−1)/2 条边。 而一个n个顶点的连通无向图,其边的个数至少为 n - 1 ，即最小生成树的边数 在用邻接表表示图时，拓扑排序算法时间复杂度为(  O(n＋e)  )。对有n个顶点和e条弧的有向图而言，建立求各顶点的入度的时间复杂度为O(e)；建零入度顶点栈的时间复杂度为O(n)；在拓扑排序过程中，若有向图无环，则每个顶点进一次栈、出一次栈，入度减1的操作在while语句中总共执行e次，所以总的时间复杂度为O(n+e)。 拓扑排序初始参数只有邻接表，所以第一步建立入度数组，因为每1入度对应一条弧，总共e条弧，建立入度数组的复杂度为O(e)。每个节点输出一次，n个节点遍历一次，时间复杂度为O(n)。（使用零入度节点栈的原因是，如果不把零入度节点入栈，每次输出时都要遍历节点。建立此栈，只需遍历一次。）然后节点入度减1的操作，也是一条弧对应一次，e条弧总共O(e)。以上总计O(n+2e)即O(n+e)。 即对每条弧要建立入度数组操作和删除操作，每个顶点要遍历一次并删除。故时间复杂度为O(n+e) 判断有向图是否存在回路，除了可以利用深度优先遍历算法，还可以利用拓扑排序深度优先搜索DFS（Depth First Search）：访问方式类似于树的前序访问； 广度优先搜索BFS（Breadth First Search）：访问方式类似于树的从树根出发的按层次遍历。

有 8 个结点的无向连通图最少有（7）条边无向连通图边最少的情况是生成树。n个顶点有n-1条边的无向图叫做生成树。权值最小的生成树是最小生成树。 用邻接表表示图进行深度优先遍历时，通常采用栈来实现算法，广度优先遍历使用队列。深度优先遍历：类似于树的前序遍历。从图中的某个顶点v出发，访问此顶点，然后从v的未被访问到的邻接点进行遍历，直到图中所有和v有路径相通的顶点都被访问到注：优先访问外层节点，访问到无新顶点时，会进行回退，访问未被访问过的分支顶点。广度优先遍历：类似于树的层序遍历。从图中的某个顶点w出发，让顶点w入队，然后顶点w再出队，并让所有和顶点w相连的顶点入队，然后再出队一个顶点t，并让所有和t相连但未被访问过的顶点入队……由此循环，指定图中所有元素都出队。 连通分量指的是有向图中的极大连通子图(错)有向图中称为强连通分量。连通图和连通分量都是针对无向图 图类型概念定义无向图连通图图中任意一对顶点都是连通的无向图连通分量非连通图的极大连通子图有向图强连通图任意一对顶点来回都是连通的有向图强连通分量非强连通图的极大强连通子图对于含有n个顶点e条边的连通图，利用prim算法求最小生成数的时间复杂度为（O(n²)）首先，以一个结点作为最小生成树的初始结点，然后以迭代的方式找出最小生成树中各结点权重最小的边，并加到最小生成树中。（加入之后如果产生回路了就要跳过这条边，选择下一个结点。）当所有的结点都加入到最小生成树中后，就找出了这个连通图的最小生成树。首先，初始化部分所需时间为(|V|+|E|)。其次，在|V|-1次循环过程中，一方面要遍历各个顶点的邻接边，一共需要(|E|)的时间；另一方面在每次循环中查找权重最轻的边需要对所有顶点遍历一遍，每次循环需时(|V|)。因此算法的时间复杂度T(n) =(|V|+|E|) +(|E|) + (|V|-1)(|V|) =(|V|^2+|E|) =(|V|^2)。 边数较多可以用Prim，因为它是每次加一个顶点，对边数多的适用。 任何一个无向连通图（有一棵或多棵）最小生成树。无向连通图，从每一个顶点出发都会得到一棵对应的最小生成树，所以可以有很多棵，但是只有一个顶点时，就只能有一棵。 拓扑排序算法把一个无向图中的顶点排成一个有序序列。（错 ）有向无环图才能进行拓扑排序。 求最短路径的 DIJKSTRA 算法的时间复杂度为 (O(n²)  )最短路径的迪杰斯特拉算法其实和最小生成树的普里姆算法相类似，原理是一样的，故时间复杂度为o(n^2). 一个活动的最早开始时间同该活动弧尾顶点的最早开始时间相同，一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的和。首先，做这题要注意几点概念：1）在AOE网络中，顶点表示事件，弧表示活动2）如果顶点A->B有弧，如果让弧表示为L，则A为L的弧尾，B为L的弧头，即有箭头的那一端叫头。 求关键路径是以拓扑排序为基础的。 (1). 求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；(2). 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3 ) ；（图用邻接矩阵表示）(3). Floyd 求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。上面正确的是（2）。(1)迪杰斯特拉（Dijkstra）最短路径算法中将所有的顶点分为两部分：已经确定的最短路程的顶点集合 P 和不能确定的最短路径的顶点集合 Q，每一次遍历都能最少确定一个顶点，也就是说每一次遍历至少有一个顶点进入集合P。归入P集合的节点的最短路径及其长度不再变更，如果边上的权值允许为负值，那么有可能出现当与P内某点（记为a）以负边相连的点（记为b）确定其最短路径时，它的最短路径长度加上这条负边的权值结果小于a原先确定的最短路径长度,而此时a在Dijkstra算法下是无法更新的，由此便可能得不到正确的结果.。 (2)求的是一对顶点，时间复杂度跟Floyd算法一样都是O(n^3)，如果求得是一个顶点到其他顶点的最短路径，时间复杂度才为O(n^2)。

一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（  条件不足，无法确定   ）必须是完全二叉树才能确定，如下图：当为完全二叉树时，为2i+1 下面几个符号串编码集合中，不是前缀编码的是（    B ）。A. {0,10,110,1111}B. {11,10,001,101,0001}C. {00,010,0110,1000}D. {b,c,aa,ac,aba,abb,abc}前缀编码：前缀编码，就是哈夫曼编码，即二叉树的一种应用，用来压缩文件体积。假设一篇文章里各种单词出现次数不同，那么用不同的编码表示不同单词，可以对文件体积进行压缩。哈夫曼编码也就是前缀编码，要求是尽量减缩某些出现频率高的文字符号的编码，但必须保证任一字符编码不是另一个字符的前缀—，否则会出错。比如abcd，如果用最后一个编写a=0，b=1，c=00，d=11，那么0011就不知道是aabb还是cd了。总之，前缀编码，在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ M2+M3    ）。 根据森林转换为二叉树的法则,二叉树的根结点通常是第一棵树的结点,二叉树的左子树是由第一棵树删去根后所得所有子树构成的,二叉树的右子树是由其它树(第二，第三棵树)构成的,故左子树结点个数是M1-1,右子树上的结点个数是M2+M3。 已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac ,  它的前序遍历是（   cedba  ）。首先看后序遍历，最后的c是二叉树的根节点，然后看中序遍历，最后一个又是c，所以这个二叉树根节点没有右子树。c的位置得到后，再看后序遍历，e在c前面，所以e是c的左孩子节点，e的位置得到。然后再看中序遍历，e前面只有一个d，所以d是e的左孩子节点，d的位置得到；剩下的b和a就在e的右子树。然后再看后序遍历，d是一个叶子节点，那么就还有一个叶子节点，那么这个节点就一定是a，那么b就是e的右孩子节点，最后再结合中序遍历就可得出所表示得二叉树。总之，先根据后序遍历确定根节点（最后一个位置），再到中序遍历中分开左右子树；然后从后序遍历中确定左右子树的根节点，以此类推 引入二叉线索树的目的是（ A ）A. 加快查找结点的前驱或后继的速度B. 为了能在二叉树中方便的进行插入与删除C. 为了能方便的找到双亲D. 使二叉树的遍历结果唯一首先明确，对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域。我们就是利用这些空链域，来存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树 在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ 完全相同）遍历方法中的先序、中序、后序指的是对根的访问顺序，而对于叶子结点都采用先遍历左子树，后遍历右子树。 一棵二叉树高度为h(根的高度为1),所有结点的度或为0或为2,则这棵二叉树最少有(2h-1)个结点首先明确，n0表示度为0的根节点，即叶子节点；如果我们想撑起来一个高度为h的就只能靠n2，由于高度为h，那么我们只要h-1层每层都有一个n2就可以撑起来h的高度；又因为n0=n2+1，所以总结点个数为h-1+h 一棵左右子树均不空的二叉树在前序线索化后,其中空的链域的个数是(1)首先明确，对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域。这是因为n个节点有2n个指针，而n个节点中有n-1条边（除了头结点没有边，其余节点都有一个父节点，相当于都有1条边，共n-1条），所以剩下的空链域就是2n-(n-1)=n+1，即n+1个空指针 。前序遍历最后一个结点的右指针为空；后序遍历第一个节点的左指针为空；中序遍历的第一个和最后一个节点为空。即前序和后序线索化之后，空链域为1；中序线索化后，空链域为2 利用二叉链表存储树,则根结点的右指针是(空)二叉链表又称为左孩子右兄弟存储法。根节点没有兄弟，所以为空 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ 501）跟这个同一深度的满二叉树的结点数为1023,其中最后一行512个；而这个1001个少了22个,少在了最后一行,所以这缺失的22个的父结点都是叶子,共22/2=11个；而这一行剩下512-22 = 490个叶子,所以总共490+11=501个叶子结点 给定一棵树,可以找到一棵二叉树与之对应二叉树的做成是按照左子女右兄弟的规则来的,这样的方式是为了保证一棵树做成二叉树之后可以还原成那棵树。 二叉树只是作为树的更高效率的存储方式,所以为了保证树结构不会被弄乱,按照上面的逻辑,一棵树只能对应一棵二叉树 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。(   错  )树的前根遍历和对应二叉树的前序遍历相同，树的后根遍历与对应二叉树的中序遍历相同。 中序遍历一棵二叉排序树的结点就可得到排好序的结点序列一棵空树，或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树；（4）没有键值相等的结点。这样的树称为二叉排序树。按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列。 用一维数组存储二叉树时,总是以前序遍历顺序存储结点(错)一维数组存储二叉树，总是以层次遍历的顺序存储。二叉树的存储结构分为顺序存储和链式存储。 顺序存储：即用一维数组存储二叉树中的结点。采用层次遍历，从上至下从左到右依次存储，根节点存储在下标为1的位置，对于任意位置i的结点，其左子树位于2i，右子树位于2i＋1，所以树结点的序号可以唯一反映出结点的逻辑关系。完全二叉树和满二叉树采用顺序存储比较合适。非完全二叉树需要添加空结点使之变成完全二叉树进行顺序存储，但是这样可能造成空间的浪费。 链式存储结构：用链表表示二叉树。每个结点存储自身的数据以及两个分别指向左孩子和右孩子结点的指针。（lchild, data, rchild） 对于有n个结点的二叉树,其高度为log2 n（错）我们先想一个极端的例子，每层只有一个结点，则深度为n。完全二叉树的高度为【logn】+1，（【】为向上取整），或者为log(2*n)，两者表示等价。

哈夫曼树在一棵树中，从一个结点到另一个结点所经过的所有结点，被我们称为两个结点之间的路径。 上面的二叉树当中，从根结点A到叶子结点H的路径，就是A，B，D，H。 在一棵树中，从一个结点到另一个结点所经过的“边”的数量，被我们称为两个结点之间的路径长度。 仍然用刚才的二叉树举例子，从根结点A到叶子结点H，共经过了3条边，因此路径长度是3。 结点的带权路径长度，是指树的根结点到该结点的路径长度，和该结点权重的乘积。如上图，假设结点H的权重是3，从根结点到结点H的路径长度也是3，因此结点H的带权路径长度是 3 X 3 = 9。 树的带权路径长度（WPL），即在一棵树中，所有叶子结点的带权路径长度之和。仍然以这颗二叉树为例，树的路径长度是 3X3 + 6X3 + 1X2 + 4X2 + 8X2 = 53 哈夫曼树：哈夫曼树（Huffman Tree）是在叶子结点和权重确定的情况下，带权路径长度最小的二叉树，也被称为最优二叉树举个例子，给定权重分别为1，3，4，6，8的叶子结点，我们应当构建怎样的二叉树，才能保证其带权路径长度最小？原则上，我们应该让权重小的叶子结点远离树根，权重大的叶子结点靠近树根。 下图左侧的这棵树就是一颗哈夫曼树，它的WPL是46，小于之前例子当中的53： 以下说法错误的是（  A ）A. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。B. 若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。C. 已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点是哪一个。D. 在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。度为二的树就是二叉树。（  错 ）首先，我们明确一个概念，树的度数是按节点的最大度数来定义的。所以，度为 2 的树要求每个节点最多只能有两棵子树,并且至少有一个节点有两棵子树；这与二叉树的要求：度不超过 2,就是说度也可以是 1 或者 0相矛盾。其次，二叉树还有一个重要特点：左子树和右子树不一样；而普通的树不分左右子树. 二叉树共有5种基本形态(1)空二叉树；(2)只有一个根结点的二叉树；(3)只有左子树；(4)只有右子树；(5)左右子树都有的二叉树 霍夫曼树的结点个数不能是偶数首先，哈夫曼树只有度为0和2的节点。这是因为哈夫曼树的构造总是以两棵值最小的树合并，每次合并都是两棵子树，不会有度为1的节点。由二叉树性质，二叉树的节点关系n0=n2+1，也就是度为0的节点数总是比度为2的节点数多1.若其中一个为奇数那么另外一个就必然是偶数，加起来就还是奇数。 哈夫曼树的构造方法假设有6个叶子结点，权重依次是2，3，7，9，18，25，如何构建一颗哈夫曼树，也就是带权路径长度最小的树呢？ 第一步：构建森林 我们把每一个叶子结点，都当做树一颗独立的树（只有根结点的树），这样就形成了一个森林： 在上图当中，右侧是叶子结点的森林，左侧是一个辅助队列，按照权值从小到大存储了所有叶子结点。至于辅助队列的作用，我们后续将会看到。 第二步：选择当前权值最小的两个结点，生成新的父结点，不断重复至只有一个节点。 借助辅助队列，我们可以找到权值最小的结点2和3，并根据这两个结点生成一个新的父结点，父节点的权值是这两个结点权值之和： 此时，队列中仅有一个结点，说明整个森林已经合并成了一颗树，而这棵树就是我们想要的哈夫曼树：

模式串T= 'abcaabbcabcaabdab' ， T的next数组值及nextval数组值为（01112231123456712和01102131011021701）a b c a a b b c a b c a a b d a b maxl 0 0 0 1 1 2 0 0 1 2 3 4 5 6 0 1 2 next 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 nextval 0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1 ...

若串 S=’software’,其子串的数目是（ 36）。1+2+...+8=8*9/2=36，但是值得注意的是，software没有重复字符，若有重复字符，要注意去除重复字符的情况 下面说法不正确的是(1)广义表的表头总是一个广义表广义表的表尾总是一个广义表广义表难以用顺序存储结构广义表可以是一个多层次的结构广义表第一个元素是表头，其余的元素组成的表为表尾。因此表头head可以是原子或者一个表，但表尾tail一定是一个表（即使是空表） 数组与一般线性表的区别主要是( D)。A.存储方面B. 元素类型方面C.逻辑结构方面D.不能进行插入和删除运算线性表和数组的区别：从概念上来看，线性表是一种抽象数据类型；数组是一种具体的数据结构。线性表与数组的逻辑结构不一样，线性表是元素之间具有1对1的线性关系的数据元素的集合，而数组是一组数据元素到数组下标的一一映射。并且从物理性质来看，数组中相邻的元素是连续地存储在内存中的；线性表只是一个抽象的数学结构，并不具有具体的物理形式，需要通过其它具有物理形式的数据结构来实现。在存储方面，数组中相邻的元素是连续地存储在内存中的；线性表中相邻的元素则不一定存储在连续的内存空间中，除非表是用数组来实现。对于数组，可以利用其下标在一个操作内随机存取任意位置上的元素；对于线性表，除非通过数组实现，否则只能根据当前元素找到其前驱或后继，因此要存取需要为i的元素，一般不能在一个操作内实现线性表可以动态分配元素，数组不行，不能进行插入和删除运算 常对数组进行的两种基本操作是（C ）A. 建立与删除B. 索引与修改C. 查找与修改D. 查找与索引查找与索引的区别：一般查找可能要遍历所有记录，而如果建立了索引就相当为记录创建了一个目录，查找时只要到目录中搜索即可，数据量非常大的时候速度快。打个比方：如果有一本1000页的书，如果要找书中的某个内容时，在没有目录的情况下，你是否要一页一页的去翻书找呢；而如果对书建一个目录的话你只要查找目录就可以找到了。道理是一样的，对一本没有目录的书进行查找就相当于一般查找，而建了目录就相当于建了索引的记录，索引查找时只要查找索引目录就可。 串 S=‘aaab’的 Next 数组值为1123. （ 错）序号：1 2 3 4数组：a a a bnext：0 1 2 3首先注意上边序号、数组和next的对应关系求next值的过程：前两位：next数组值前两位一定为01，即aaab中的前两位aa对应01，如上表中next第1，2位为0和1.其实这就可以得出答案了.第三位：3a前面是2a（2a表示序号为2的a），2a的next数组值为1，找到序号为1的字符, 即1a,将2a和1a相比，两者相同，都是a，则3a的next值为2a的next值加1，即2；第四位：4b前3a的next为2，找到序号为2的字符, 即2a, 将3a与2a相比，二者相同，则其next值为3a的next加1，为3.结果为0123如果比较的时候碰到与前一位字符“不同”怎么办？如求下列序号4的next值序号: 1 2 3 4数组: a a b anext: 0 1 2 1以前一位的next值为序号，找到这个序号对应的字符，再进行比较，4a前一位是3b, next值为2, 找到序号2对应的2a, 比较3b和2a, 两者不同, 再重复这一步骤, 找到2a的next值是1，比较3b和1a, 不同, 那么所求的4a的next就是1, 如果相同就是2a的next值加1，为2。做个练习：xyxyyxxyx,求它的next数组？答案是011231223，你做对了吗？ 串是一种数据对象和操作都特殊的线性表串的逻辑结构和线性表相似，不同之处在于串针对的是字符集，也就是串中的元素都是字符；对于串的基本操作与线性表有很大的差别。线性表更关注单个元素的操作，比如说查找一个元素，插入或者删除一个元素；但串中更多关注一部分元素的操作，如查找子串位置，得到指定子串，替换子串等操作。 在进行字符初始化时，char s[] = {’H’,’e’,’l’,’l’,’o’,’!’}是不合法的。因为没有加入字符串结束符。这个字符串的长度同样是不确定的，如果你在初始化s时变为char s[]={'h','e','l','l','o'，' \0'}; 那么，他的长度应该就是5（字符串结束符不算） 数组是同类型值的集合。(错 )首先要注意概念性的错误，集合中的元素不能重复，而数组中的元素可以重复，所以，数组不能简单的说成是集合其次，虽然java，c、C++中必须要同类，但是像JS，Python，PHP这样的脚本语言大多不需要同类。 稀疏矩阵压缩存储后,必会失去随机存取功能特殊矩阵压缩后不失去随机存取功能，稀疏矩阵必定失去： 特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元素分配单元（对值相同元素只分配一个单元），将非零元素存储在向量中，元素的下标i和j和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小（t＜＜m*n），且分布没有规律。用十字链表作存储结构自然失去了随机存取的功能。即使用三元组表的顺序存储结构，存取下标为i和j的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为O(1)，最差情况下是O(n)，因此也失去了随机存取的功能。

设计一个判别表达式中括号是否配对出现的算法，采用（ 栈  ）数据结构最佳。解析：依次判断表达式中的每个字符，若是左括号就入栈，若是右括号则出栈，出栈的时候判断是否为空，如果为空，则说明不匹配；最后读到表达式末尾没有字符了，再判断一下栈是否为空，如果为空，则说明匹配，不为空，说明不匹配。 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个（1≤j≤i）输出元素是（ 不能确定 ）。解析：不能确定是一次性全进完、全出完,只知道进入的序列不变。当一次性弄完时，答案为i-j+1；当边进边出时，元素难以确定。 修改一下此题目，若一个栈的输入序列为1，2，3，.....，n，输回出序列的第一个元素是n，则第i个输出元素（一定是n-i+1）。因为暗含的意思就是，从1到n-1已经全部入栈，输出的顺序就是从n到1的唯一顺序，第i个输出元素就为n-i+1 栈在（ 递归调用、子程序调用、表达式求值 ）中应用。解析：栈就是一个先进后出的结构；队列就是一个先进先出的结构。一般只要满足这个特点就可以称之为栈或队列。栈的应用：非常广泛，一般在计算机中，只要数据的保存满足先进后出的原理，都优先考虑使用栈，是计算机中不可缺的机制。在CPU内部就有提供栈这个机制。主要用途：函数调用和返回，数字转字符，表达式求值，走迷宫，子程序调用和返回，中断时数据保存和返回。在编程语言中主要用来进行函数的调用和返回。队列的应用：队列主要用在和时间有关的地方，特别是操作系统中，队列是实现多任务的重要机制。windows中的消息机制也是通过队列来实现的。进程调度也是使用队列来实现，所以队列也是一个重要的机制。只要满足数据的先进先出原理就可以使用队列。 向一个顺序栈插入一个元素时，首先把待插入元素写入到这个位置上，然后使栈顶后移一个位置。 （ 错 ）解析：插入先判满，弹出先判空。1、进栈（PUSH）算法①若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；②置TOP=TOP+1（栈指针加bai1，指向进栈地址）；③S(TOP)=X，结束（X为新进栈的元du素）；2、退栈（POP）算法①若TOP≤0，则给出下溢信息，作zhi出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)；②X=S(SOP)，（退栈后的元素赋给X）；③TOP=TOP-1，结束（栈dao指针减1，指向栈顶）。 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（  （rear – front + m）% m  ）解析：首先注意，rear指向最后一个元素的下一个元素，所以rear-front即可，不需要+1；其次+m是为了避免当rear 已经转了一圈后，rear的值小于 front的值的情况，保证分子大于0 用链接方式存储的队列，在进行删除运算时(  头、尾指针可能都要修改   )。在有头结点的链队列的出队操作中，一般只需修改队头指针；但当原队列中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改队尾指针，使其指向头结点，且删去此结点后队列变空 在一个循环队列Q中，判断队空的条件为Q.rear+1 == Q.front，队满的条件为（Q.rear+1)%MAXSIZE==Q.front每次从队列中取出的应是具有最高优先权的元素，这种队列就是优先级队列。队列是一种特征为FIFO的数据结构，每次从队列中取出的是最早加入队列中的元素。但是，许多应用需要另一种队列，每次从队列中取出的应是具有最高优先权的元素，这种队列就是优先级队列(Priority Queue)，也称为优先权队列。优先级队列是0个或多个元素的集合，每个元素都有一个优先权或值。当给每个元素分配一个数字来标记其优先级时，可设较小的数字具有较高的优先级，这样更方便地在一个集合中访问优先级最高的元素，并对其进行查找和删除操作。对优先级队列，执行的操作主要有：(1)查找，(2)插入，(3)删除。在最小优先级队列(min Priority Queue)中，查找操作用来搜索优先权最小的元素，删除操作用来删除该元素。在最大优先级队列(max Priority Queue)中，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。插入操作均只是简单地把一个新的元素加入到队列中 消除递归不一定需要使用栈不是所有的递归转化为非递归都要用到栈。转化为非递归主要有两种方法：对于尾递归或单向递归，可以用循环结构算法代替；其余的使用栈的方法。例如求阶乘的，是单向递归，直接用循环去替代从1乘到n就是结果了；斐波那契数列亦然 任何一个递归过程都可以转换成非递归过程即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作,所得的输出序列也一定相同(错)解释一下题目的意思：对于同一个输入序列（序列中元素各不相同），使用两种不同的入栈和出栈组合操作，所得到的输出序列一定相同。 解析：对于栈来说，由于输入序列中元素各不相同，所以输出序列肯定不同；如果是使用两种不同的（合法）的入队和出队组合操作，则其输出序列一定是相同的。

什么是栈？ 数据结构图入栈出栈图JavaScript中的Array与栈 在js中，如何发现出栈LIFO的特性？如何实现一个最小栈？leetcode 栈 解法题目 20.有效的括号（easy）67.二进制求和（easy）905.按奇偶排序数组（easy）56.合并区间（medium）75.颜色分类（medium）228.汇总区间（medium）739.每日温度（medium）面试题 栈 解法题目 实现一个BigInt什么是栈？栈是一种后入先出（LIFO）的数据结构栈通常使用DFS（Depth First Search）遍历通常可以通过top/bottom来代表栈的顶部和底部数据结构图 入栈出栈图 JavaScript中的Array与栈在js中，如何发现出栈LIFO的特性？下面这个结构大家都熟悉，瞬间体现出栈LIFO的特性。 // 定义一个栈let stack = [1,2,3];// 入栈stack.push(4); // stack [1,2,3,4]// 出栈stack.pop(); // 4 stack [1,2,3]如何实现一个最小栈？设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) —— 将元素 x 推入栈中。pop() —— 删除栈顶的元素。top() —— 获取栈顶元素。getMin() —— 检索栈中的最小元素。var MinStack = function() { this.stack = [];};MinStack.prototype.push = function(x) { this.stack.push(x);};MinStack.prototype.pop = function() { return this.stack.pop();};MinStack.prototype.top = function() { return this.stack[this.stack.length - 1];};MinStack.prototype.getMin = function() { return Math.min(...this.stack);};题目：https://leetcode-cn.com/probl...解法：https://github.com/FrankKai/l... ...

本文是重新数据结构系列文章的第二篇，本文和大家一起探讨链表的相关知识。@[toc] 链表是怎么样的数据结构链表，不需要连续的内存空间，通过“指针(引用)”将一组零散的内存块串联起来的数据结构。内存块在链表中也叫“结点”，每个结点除了存储数据，还需要记录链上的下一个或者上一个结点的地址。 链表的特点1.插入、删除数据效率高O(1)级别（只需更改指针指向即可），随机访问效率低O(n)级别（需要从链头至链尾进行遍历）。2.和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。 常见的链表结构单链表1.只有一个方向，每个结点只存储下一个结点的地址,记录下一个结点的指针成为后继指针(next)2.有两个特殊结点，头结点和尾结点。头结点用来记录链表的基地址；尾结点指向一个空地址NULL，表示链表的最后一个结点3.链表的插入和删除操作，因为不考虑内存空间的连续性，只需要关注相邻结点的指针变化，所以时间复杂度为O(1)4.链表的随机访问操作，因为内存空间的不连续性，需要指针一个结点一个结点的依次访问，直到找到对应的结点，所以时间复杂度为O(n) 双向链表1.有两个方向，每个结点既有指向后面结点的后继指针next，也有指向前面结点的前驱指针prev, 因为需要同时存储前后两个指针，因此双向链表占用更多的内存存储空间2.首节点的前驱指针prev和尾节点的后继指针均指向空地址。3.对于删除、插入操作可以实现比单链表更加高效的O(1)。对于删除操作，一般就是如下两种情况： a.删除结点中“值等于某个给定值”的结点；b.删除给定指针指向的结点。对于第一种情况，无论单链表还是双向链表，都需要从头结点开始每个结点依次进行遍历，直到找到值等于某个给定值对应结点，进行删除，对于单纯的删除操作，时间复杂度为O(1)，但是对于遍历查找结点的操作时间负责就是O(n)，所以根据时间复杂度分析中的加法法则，第一种情况下链表操作的总时间复杂度为 O(n)。 而对于第二种情况，双向链表结点存储了前驱指针prev，直接就可以找到对应结点进行指针操作删除，所以其时间复杂度为O(1);而单链表因为没有前驱指针，依然需要从头开始遍历结点，直到p->next=q。说明p是q的前结点，因此这种情况下单链表的删除操作时间复杂度为O(n) 4.对于查询操作，双线链表也比单链表高效，因为我们可以记录上次上次的位置，再查询时只需要查询一半即可 5.LinkedHashMap的底层实现就是用的双向链表结构。 循环链表1.循环链表是一种特殊的单链表，2.尾结点指针是指向链表的头结点3.处理环形结构数据时，使用用循环链表，比如注明的约瑟夫问题。 链表or数组从时间复杂度分析性能数组因为其需要内存空间的连续性，符合CPU的缓存机制，所以访问效率更高。数组的缺点：1.大小固定，申请需要整块的连续空间，如果空间不足，可能申请失败2.无法动态扩容，如果申请空间不够，需要申请更大的空间，需要数据复制拷贝进入新的数组，非常耗时；而链表天然支持动态扩容，因为他不要内存空间的连续性链表的缺点：1.需要更多的内存空间来存储指向下一节点的指正2.频繁的插入、删除操作，会导致内存的频繁申请和释放，容易造成内存碎片，Java中容易触发系统GC(Garbage Collection，垃圾回收)机制 链表的应用链表的经典应用场景就是LRU 缓存淘汰算法。缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。缓存大小是有限制的，在缓存空间满的时候，就需要使用一下策略进行清理，常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used)。如何基于链表实现LRU 缓存淘汰算法？首先，维护一个有序的单链表，规定越靠近尾部的数据时间越早，处理数据时：1.如果数据已存在链表中，遍历结点，找到对应结点的数据进行删除，插入链表头部，时间复杂度为O(n)2.如果数据不再链表中，分两种情况 如果此时缓存未满，则将此结点直接插入到链表的头部，时间复杂度为O(1)；如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部，时间复杂度为O(1)。正确写出链表的6个技巧理解指针或引用的含义警惕指针丢失和内存泄漏利用哨兵简化实现难度重点留意边界条件处理举例画图、辅助思考多写多练觉得文章不错的，给我点个赞哇，关注一下呗！ 技术交流可关注微信公众号【君伟说】，加我好友一起探讨 微信交流群：加好友（备注技术交流）邀你入群，抱团学习共进步

用数组实现环形队列的特点是高效。 能快速判断队列是否 满/空；能快速存取数据。因为简单高效，所以甚至在硬件中都实现了环形队列。        环形队列广泛应用于网络数据的收发，和不同应用间数据交换（内核和应用程序大量交换数据，从硬件接受大量数据） 内存上没有环形结构，因此环形队列实际上用数组的线性空间来实现。       但是当数据到了尾部如何处理呢？它将转回到0位置来处理。这个转回是通过取模操作来执行的。       因此，环形队列是逻辑上将数组元素q[0]和q[maxSize - 1]连接，形成一个存放队列的环形空间。 为了方便读写，还要用数组下标来指明队列的读写位置。head/tail.其中head指向可以读的位置，tail指向可以写的位置。 环形队列的关键是判断队列为空，还是为满。当tail追上head时，队列为满时，当head追上tail时，队列为空。但如何知道谁追上谁。还需要一些辅助的手段来判断.    如何判断环形队列为空，为满有两种判断方法。 一.附加一个标志位tag 当head赶上tail，队列空，则令tag=0,当tail赶上head，队列满，则令tag=1,二.限制tail赶上head，即队尾结点与队首结点之间至少留有一个元素的空间。 队列空：   head==tail队列满：   (tail+1)% MAXN ==headpackage ds.queue;/** * 用数组实现环形队列 * 附加标志位法 */public class ArrayCircleQueue { private int[] arr; private int maxSize; private int rear; private int front; // 当front赶上rear，说明队列满，令flag=0； // 当rear赶上front，说明队列空，令flag=1 private int flag; public ArrayCircleQueue(int size) { maxSize = size; arr = new int[maxSize]; front = 0; rear = 0; flag = 1; } public boolean isFull() { return front == rear && flag == 0; } public boolean isEmpty() { return front == rear && flag == 1; } public int peek() { if (isEmpty()) throw new RuntimeException("queue is empty!!!"); return arr[front]; } public void offer(int v) { if (isFull()) { System.out.println("queue is full, could not add."); return; } arr[rear] = v; rear = (rear + 1) % maxSize; if (rear == front) flag = 0; } public int poll() { if (isEmpty()) throw new RuntimeException("queue is empty!"); int res = arr[front]; front = (front + 1) % maxSize; if (front == rear) flag = 1; return res; } public void show() { if (isEmpty()) { System.out.println("The queue is empty!!!"); return; } System.out.println("front -> rear"); for (int i = front; i < front + size(); i++) { System.out.print(arr[i % maxSize] + " "); } System.out.println(); } public int size() { if (rear > front) return rear - front; return rear + maxSize - front; }}package ds.queue;/** * 数组实现环形队列 * -预留空间法 */public class ArrayCircleQueue2 { private int maxSize; private int front; // 指向队列的第一个元素，arr[front]就是队列的第一个元素。初始值0 private int rear; // 指向队列的最后一个元素的后一个位置，希望空出一个空间作为约定。初始值0 private int[] arr; public ArrayCircleQueue2(int size) { maxSize = size; arr = new int[size]; } public boolean isFull() { return (rear + 1) % maxSize == front; } public boolean isEmpty() { return front == rear; } public void offer(int v) { if (isFull()) { System.out.println("queue is full!!!"); return; } arr[rear] = v; rear = (rear + 1) % maxSize; } public int poll() { if (isEmpty()) throw new RuntimeException("queue is empty!!!"); int res = arr[front]; front = (front + 1) % maxSize; return res; } public int size() { return (rear + maxSize - front) % maxSize; } public int peek() { if (isEmpty()) throw new RuntimeException("queue is empty"); return arr[front]; } public void show() { if (isEmpty()) { System.out.println("queue is empty!!!"); return; } System.out.println("Front -> rear"); for (int i = front; i < front + size(); i++) { System.out.print(arr[i % maxSize]); } System.out.println(); }}测试代码 ...

二分查找[toc] 最基本的二分查找int binarySearch(int[] nums, int target) { int left = 0; int right = nums.length - 1; // 注意 while(left <= right) { int mid = left + (right - left) / 2; //注意：如果用(right + left) / 2 会出现数值过大溢出现象 if(nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1; // 注意 else if (nums[mid] > target) right = mid - 1; // 注意 } return -1;}边界问题为什么 while 循环的条件中是 <=，而不是 <？因为初始化 right 的赋值是 nums.length - 1，即最后一个元素的索引，而不是 nums.length。这二者可能出现在不同功能的二分查找中，区别是：前者相当于两端都闭区间 [left, right]，后者相当于左闭右开区间 [left, right)，因为索引大小为 nums.length 是越界的。 ...

前言：单链表是一种常见、重要的数据结构，并且随着时间飞逝，也衍生出了诸多针对单链表的操作算法，例如，今天本文中即将会聊到的单链表的反转操作 。下面会结合一些图片详细讲解下单链表的数据结构，以及通过三种方式（递归、双指针法、循环遍历）进行单链表的反转。 数据结构：1、单链表的数据结构：单链表是一种线性结构，它是由一个个节点（Node）组成的。并且每个节点（Node）是由一块数据域（data）和一块指针域（next）组成的。      ①、节点（Node）结构图如下： 节点的数据域：data数据域一般就是用来存放数据的 。（注：data域需要指定类型，只能存放指定类型的数据，不能什么东西都放，是不是呀； 那代码中是怎么实现的呢？ 使用 泛型 。）节点的指针域：next指针域一般就是存放的指向下一个节点的指针；这个指针其实是一个内存地址，因为Node节点对象是存放在JVM中的堆内存中，所以节点的next指针域中存放就是下一个节点在堆内存中的地址；而在代码中对象的内存地址是赋值给其引用变量了，所以指针域中存放的是下一个节点对象的引用变量。 ②、单链表结构图如下：（下图是由三个节点构成的单链表） 若有所思，en en en . . . . . . 好像单链表的知识在脑海中清晰了些呀；那要不我们快马加鞭，赶紧把单链表的数据结构代码弄出来，然后再思索下怎么进行反转， en en en. . . .. . . 嘿嘿！ 代码：1、Node节点类：创建Node节点类，节点类中并且额外提供了两个方法（单链表的创建方法、单链表的遍历放歌）；注意：单链表的创建方法 createLinkedList( )：Node节点的插入方式为 尾插法 ， 其实还有 头插法 方式； 扩展：链表中节点的插入方式还在 HashMap 中使用到了，在 JDK 1.7 时是头插法，JDK 1.8时是尾插法； /** * @PACKAGE_NAME: com.lyl.linklist * @ClassName: Node 节点类 * @Description: 单链表的组成元素：Node节点 * @Date: 2020-05-30 16:18 **/public class Node<T> { // 节点的数据域 public T data; // 节点的指针域 public Node next; /** * 构造方法 * @param data 数据域值 */ public Node(T data) { this.data = data; } /** * 创建 单链表 （尾插法） * @return 返回头结点 */ public static Node createLinkedList(){ // 头节点 Node<String> head; Node<String> n = new Node<String>("111"); Node<String> n1 = new Node<String>("222"); Node<String> n2 = new Node<String>("333"); // 指定头节点 head = n; n.next = n1; n1.next = n2; // 返回头结点 return head; } /** * 链表遍历 * @param node */ public static void traverse(Node node) { while (node != null) { System.out.print(node.data + " --> "); node = node.next; } System.out.print("null"); System.out.println(); }}2、单链表反转：①、递归实现反转：/** * @PACKAGE_NAME: com.lyl.linklist * @ClassName: ReverseByRecursiveTest * @Description: 使用递归实现单链表反转 * @Date: 2020-05-30 17:01 **/public class ReverseByRecursiveTest { /** * 使用 递归 实现单链表反转 * @param head 链表的 头节点 * @return 返回反转后的 head 头结点 */ public static Node reverse(Node head) { if (head == null || head.next == null) { return head; } // 获取头结点的下个节点，使用temp临时节点存储 Node temp = head.next; // 递归调用 Node node = reverse(head.next); // 将头节点的下一个节点的指针域指向头节点 temp.next = head; // 将头节点的指针域置为null head.next = null; return node; } // test public static void main(String[] args) { // 创建单链表 Node head = Node.createLinkedList(); // 遍历新创建的单链表 System.out.print("新创建的单链表： "); Node.traverse(head); // 递归反转单链表 Node newHead = reverse(head); // 遍历反转后的单链表 System.out.print("反转后的单链表： "); Node.traverse(newHead); }}运行输出：新创建的单链表： 111 --> 222 --> 333 --> null反转后的单链表： 333 --> 222 --> 111 --> null ...

作者 谢恩铭，公众号「程序员联盟」。转载请注明出处。原文：https://www.jianshu.com/p/149...《数据结构和算法》全系列内容简介算法的正确性算法的复杂度“渐近”度量第一部分第四课预告1. 算法的正确性上一课 数据结构和算法 | 第一部分第二课：小鸭子们去旅行 中，我们讲了一个有趣的小故事，就是为了引出算法复杂度。 算法复杂度非常重要，要讲的内容也很多，所以我们分为上下两课。当程序员需要解决计算机科学相关的问题时，他们（通常）会编写一个程序。这个程序包含一个实现，也就是说需要把算法用一种编程语言来实现。 我们知道，算法只是对解决问题的步骤的一种精确描述，它并不依赖于程序员所用的编程语言或工作环境。 我们在 数据结构和算法 | 第一部分第一课：什么是数据结构和算法 里介绍了一个“煮方便面”的食谱，这份食谱虽然简单，但可以说是一个算法。 我们是用中文来描述这份食谱的，如果我现在把这份食谱翻译成一门外语（比如 英语），但食谱的内容还是不变，只不过换了一种语言来说明罢了。换个英国人来照着这份英文食谱煮方便面，跟我做出来的会是一样的。 那么，当程序员需要把算法用一种编程语言来实现时，需要做什么呢？ 像农夫 Oscar 一样，他必须首先验证他的算法是正确的，也就是说它产生了预期的结果，解决了所涉及的问题。这非常重要（如果算法不正确，那我们根本没有选择和优化它的必要），有时验证算法正确性是非常难的一步。 算法正确性，英语是 Algorithm Correctness（algorithm 表示“算法”，correctness 表示“正确性”）。要证明算法的正确性，有许多方法，我们本课程就不详述了，因为这不是我们的重点。大家有兴趣可以去网上搜索一下。 当然，算法正确了，并不能保证实现这个算法的程序就没有错误（bug）。 一旦有了一个正确的算法，我们用编程语言去实现它（通过编写一个执行它的程序）。但我们可能会写出有很多小错误的程序，这些小错误也许和所使用的编程语言有关，可能在编写程序的过程中被引入。因为算法中一般不会描述如何避免犯错，例如如何管理程序的内存，如何检查段错误（Segmentation Fault），等等，但这些都是程序员实现算法时需要考虑的问题。 2. 算法的复杂度一旦程序员确信他的算法是正确的，他将尝试评估其效率，比如他会想知道“这个算法快不快”。 有人可能会认为，要知道算法快不快的最佳方式是实现该算法并在电脑上进行测试。 有趣的是，通常情况并非如此。例如，如果两个程序员实现了两种不同的算法，并在各自的电脑上测试程序运行的快慢。那么拥有更快速度的电脑的那个程序员可能会错误地认为他的算法更快，但其实并不一定。 而且，要实现一个算法并测试，有时候并不容易。且不说有时候根据一个算法来写出实现的代码很难，如果要实现的算法涉及到一枚火箭的发射，难道每次用一枚真的火箭来发射一下去测试算法快不快吗？我们又不像钢铁侠那么有钱可以任性。 出于这些原因，计算机科学家们发明了一个非常方便而强大的概念，也就是我们接下来要学习的：算法的复杂度。 “复杂度”（Complexity，表示“复杂”，是一个名词。它对应的形容词是 complex，表示“复杂的”）这个词有点误导人，因为我们这里不是强调“理解起来有困难”（很复杂，很难），而是指效率（efficiency）。 “复杂度”并不意味着“复杂的程度”。有的算法理解起来很难（很复杂），它的复杂度却可以非常低。 如果要用一句话来简单说明算法复杂度，那可以是：“如果给实现了这个算法的程序一个大小为 N 的输入，那么这个程序将执行的操作的数目的数量级是 N 的一个怎么样的函数（ f(N) ）呢？” f(N) 中的 f 是 function（函数）的意思，相信以前数学课的时候，大家都学过（比如我们以前很常见的 y = f(x) ）。f(N) 表示“N 的函数”。 上面那句话基于以下事实：解决问题的程序取决于问题的起始条件。如果起始条件改变，程序执行的时间也会变长或变短。 复杂度可以量化（通过数学公式）起始条件与算法执行的时间之间的关系。上面这几句话乍看有点难以理解。什么是操作？什么是操作的数目，什么是操作的数目的数量级？ 不用担心，我们慢慢讲解： 复杂度的学习中会涉及一些数学的概念。所以嘛，学好数学对编程还是很有帮助的，英语同样很重要。如果你英语和数学比较好，学起编程来会轻松很多。可以参看我以前的一篇文章：对于程序员, 为什么英语比数学更重要? 如何学习 。 数量级是指数量的尺度或大小的级别，每个级别之间保持固定的比例。通常采用的比例有 10，2，1000，1024， e（欧拉数，大约等于 2.71828182846 的超越数，即自然对数的底）。-- 摘自 百度百科为了“计算操作的数目”，我们必须首先定义什么是操作。操作其实不难理解，比如第一部分第一课中，我们讲了一个“煮方便面”的算法，其中的步骤是这样的： ...