数据结构重点代码总结（考研）

单链表定义

typedef struct LNode{			//因为结构体中包含了LNode，所以定义结构体时struct后面要加LNodeElemType data;struct LNode *next;
}LNode, *LinkList;

头插法

头插法建立单链表（天勤）

void List_HeadInsert(LNode *&C, int a[], int n){LNode *s;				//s用来指向新申请的结点int i;C=(LNode *)malloc(sizeof(LNode));	//申请C的头结点空间C->next=NULL;for(i=0; idata=a[i];s->next=C->next;	//新插入的s结点的next指向头结点C的nextC->next=s;			//头结点C的next指向新建的s结点}r->next=NULL;
}

尾插法

尾插法建立单链表（天勤）

void List_TailInsert(LNode *&C, int a[], int n){LNode *s, *r;int i;C=(LNode *)malloc(sizeof(LNode));C->next=NULL;r=C;for(i=0; idata=a[i];r->next=s;		//r所在的next指向新建的s结点r=r->next;}r->next=NULL;
}

合并链表

A，B是两个带头结点的单链表，其中元素递增有序，设计一个算法，将A，B归并成一个按元素值非递减有序的链表C，C由A和B中的结点组成。

void Merge(LNode *A, LNode *B, LNode *&C){LNode *p=A->next;LNode *q=B->next;LNode *r;			//r始终指向C的终端结点C=A;C->next=NULL;free(B);r=C;while(p!=NULL && q!=NULL){if(p->data<=q->data){r->next=p;p=p->next;r=r->next;}else{r->next=q;q=q->next;r=r->next;}}r->next=NULL;if(p!=NULL)			//将剩余结点链接在C的尾部r->next=p;if(q!=NULL)r->next=q;
}

栈与队列

基本概念

当n个元素以某种顺序进栈，并在任意时刻出栈，排列数目 N= 1 n + 1 \frac{1}{n+1} n+11​ KaTeX parse error: Undefined control sequence: \C at position 1: \̲C̲_{2n}^{n}= ( 2 n ) ! ( n + 1 ) ( n ! ) 2 \frac{(2n)!}{(n+1)(n!)^2} (n+1)(n!)2(2n)!​

栈：先进后出； 队列：先进先出；

当较大的数首先出栈时，较小的数都是降序压在栈内的。

循环队列：

​ 队空状态：qu.rear==qu.front;

​ 队满状态：(qu.rear+1)%maxSize==qu.front;

递归过程或者函数调用时，处理参数及返回地址要用栈。

串是一种特殊的线性表，其数据元素是一个字符。

树与二叉树

基本概念

结点数 = 度数 + 1

度为m的树第i层至多有 m^i-1 个结点

高度为h的m叉树至多有(m^h-1)/(m-1)个结点

具有n个结点的m叉树最小高度为 $\lceil$ log_m^(n(m-1)+1)$\rceil$

非空二叉树上叶子结点数等于双分支结点数加1

总结点数=n₀+n₁+···+n_m ①

总分支数=1n₁+2n₂+···+m*n_m ②

总分支数=总结点数-1 ③

由①②③得 n₀=1+n₂+2n₃+···+(m-1)n_m

二叉树的第i层上最多有 2^i-1个结点

高度为k的二叉树上最多有2^k-1个结点

具有n个结点的完全二叉树的深度为$\lfloor$log₂n$\rfloor$+1

在哈夫曼二叉树中任何一个序列都不是另一个序列的前缀，且树中不含单分支结点

二叉树链式存储结构定义

typedef struct BiTNode{ElemType data;struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

二叉树遍历

先序遍历递归（根左右）

void PreOrder(BiTree T){if(T!=NULL){visit(T);PreOrder(T->lchild);PreOrder(T->rchild);}
}

中序遍历递归（左根右）

void InOrder(BiTree T){if(T!=NULL){InOrder(T->lchild);visit(T);InOrder(T->rchild);}
}

后序遍历递归（左右根）

void PostOrder(BiTree T){if(T!=NULL){PostOrder(T->lchild);PostOrder(T->rchild);visit(T);}
}

先序遍历递归（根左右）

void PreOrder(BiTree T){InitStack(S);BiTree T;while(p||!IsEmpty(S)){		//栈不空或p不空时循环if(p){					//一路向左visit(p);Push(S,p);p=p->lchild;}else{Pop(S,p);p=p->rchild;}}
}

中序遍历非递归（左根右）

void InOrder(BiTree T){InitStack(S);BiTree p=T;while(p||!IsEmpty(S)){		//栈不空或p不空时循环if(p){Push(S,p);p=p->lchild;}else{Pop(S,p);visit(p);p=p->rchild;}}
}

后序遍历非递归（左右根）

void PostOrder(BiTree){InitStack(S);p=T;r=NULL;while(p||!IsEmpty(S)){if(p){								//走到最左边Posh(S,p);p=p->lchild;}else{								//向右GetTop(S,p);					//读栈顶结点（非出栈）if(p->rchild && p->rchild!=r){	//若左子树存在且未被访问过p=p->rchild;				//转向右Push(S,p);					//压栈p=p->lchild;				//再走到最左}else{							//否则，弹出结点并访问Pop(S,p);					//出栈visit(p->data);r=p;						//记录最近访问过的结点p=NULL;}}}
}

层次遍历

void LevelOrder(BiTree T){InitQueue(Q);		//初始化辅助队列BiTree T;EnQueue(Q,T);		//根节点入队while(!IsEmpty(Q)){DeQueue(p);		//队头结点出队visit(p);if(p->lchild!=NULL)		//若左子树不空，左子树根节点入队EnQueue(Q,p->lchild);if(p->rchild!=NULL)EnQueue(Q,p->rchild);}
}

图

基本概念

有向完全图：若有向图有n个顶点，则最多有n(n-1)条边，将具有n(n-1)条边的有向图成为有向完全图。

无向完全图：若无向图有n个结点，则最多有n(n-1)/2条边，将具有n(n-1)/2条边的有向图成为无向完全图。

连通图：如果图中任意两个顶点都连通，则称该图为连通图；否则，图中的极大连通子图称为连通分量。

强连通图：在有向图中，从v_i到v_j和从v_j到v_i都有路径，则称该图为强连通图；否则将其中的极大强连通子图称为强连通分量。

图的定义

邻接矩阵定义

#define MaxVertexNum 100		//顶点数目的最大值
typedef char VertexType;		//顶点的数据类型
typedef int EdgeType;			//带权图中边上权值的数据类型
typedef struct{VertexType Vex[MaxVertexMum];	//顶点表EdgeType Edge[MaxVertexMum][MaxVertexNum];	//邻接矩阵，边表int vexnum, arcnum;			//图当前的定点数和边数
}

邻接表存储结构定义

#define MaxVertexNum 100		//图中顶点数的最大值
typedef struct ArcNode{			//边表结点int adjvex;					//该弧指向的顶点的位置struct ArcNode *next;		//指向下一条弧的指针
}ArcNode;
typedef struct VNode{			//顶点表结点VertexType data;			//顶点信息ArcNode *first;				//指向第一条依附该顶点的弧的指针
}VNode, AdjList[MaxVertexNum];
typedef struct{					AdjList vertices;			//邻接表int vexnum; arcnum;			//图的顶点数和弧数
}ALGraph;						//ALGraph是以邻接表存储的图类型

图的遍历

图的广度优先遍历

bool visited[MAX_VERTEX_NUM];	//访问标记数组
void BFSTraverse(Graph G){		//对图G进行广度优先遍历for(i=0; i=0; w=NexNeighbor(G,v,w)){	//检测v所有邻接点if(!visited[w]){	//w为v的尚未访问的邻接顶点visit(w);visited[w]=TRUE;EnQueue(Q,w);}}}
}

图的深度优先遍历

bool visited[MAX_VERTEX_NUM];	//建立访问标记数组
void DFSTraverse(Graph G){		//对图G进行深度优先遍历for(v=0; v=0; w=NextNeighbor(G,v,w))if(!visited[w]){		//若w未被访问，则执行DFSDFS(G,w);}
}

拓扑排序

拓扑排序算法实现（17年考过一次）

bool TopologicalSort(Graph G){InitStack(S);				//初始化栈，存储入度为0的顶点for(int i=0; inextarc){//将所有i指向的顶点的入度减1，并且将入度为0的顶点压入栈Sv=p->adjvex;if(!(--indegree[v]))	//入度为0则入栈Push(S,v);}}if(count

typedef struct{			//查找表的数据结构ElemType *elem;		//元素存储空间基址，建表时按实际长度分配，0号单元留空int TableLen;		//表的长度
}SSTable;
int Search_Seq(SSTable ST, ElemType key){ST.elem[0]=key;		//“哨兵”for(i=ST.TableLen; ST.elem[i]!=key; --i);	//从后往前找return i;			//若表中不存在key，将查找到i为0时退出for循环
}

int Binary_Search(SeqList L, ElemType key){int low=0, high=L.TableLen-1, mid;while(low<=high){mid=(low+high)/2;if(L.elem[mid]==key)return mid;else if(L.elem[mid]>key)high=mid-1;elselow=mid+1;}return -1;
}

void BubbleSort(ElemType A[], int n){for(i=0; ii; --j){	//一趟冒泡过程if(A[j-1]>A[j]){	//若为逆序swap(A[j-1],A[j]);	//交换flag=true;}}if(flag==false)return 0;			//本趟遍历后没有发生交换，说明表已有序}
}

void QuickSort(ElemType A[], int low, int high){if(low=pivot)--high;A[low]=A[high];		//将比枢轴小的元素移动到左端while(low

void SelectSort(ElemType A[], int n){for(i=0; i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！