数据结构相关专题
树
1.树的有关定义和术语
1.术语
1.树(tree):
树是n(n≥0)个结点的有限集T,
当n=0时,T为空树;
当n>0时,
(1)有且仅有一个称为T的根的结点,
(2)当n>1时,余下的结点分为m(m>0)个互不相交的有限集,
,…,
,每个Ti(1≤i≤m)也是一棵树,且称为根的子树。
这个定义是递归的,是一层套一层的

2.结点的度(degree):
结点的子树数目
3.树的度:
树中各结点的度的最大值
4.n度树: 度为n的树
//注意这里度和图的度之间的区别
//2度树一定是二叉树,二叉树不一定是二度树
5.叶子(终端结点): 度为0的结点
6.分枝结点(非终端结点,非叶子):
度不为0的结点
7.双亲(父母,parent)和孩子(儿子,child) :
若结点C是结点P的子树的根,称P是C的双亲,C是P的孩子。
8.结点的层(level):
规定树T的根的层为1,其余任一结点的层等于其双亲的层加1。
9.树的深度(depth,高度):
树中各结点的层的最大值。
10.兄弟(sibling):
同一双亲的结点之间互为兄弟。
11.堂兄弟:
同一层号的结点互为堂兄弟。
12.祖先: 从树的根到某结点所经分枝上的所有结点为该结点的祖先。
13.子孙: 一个结点的所有子树的结点为该结点的子孙。
14.有序树:若任一结点的各棵子树,规定从左至右是有次序的,即不能互换位置,则称该树为有序树。 二叉树一般是有序的
15.无序树: 若任一结点的各棵子树,规定从左至右是无次序的,即能互换位置,则称该树为无序树。普通的树一般是无序的
16.森林: m(m≥0)棵互不相交的树的集合。
2.其他表现形式
1.广义表表现形式

2.Venn图嵌套集合
3.书目表
2.二叉树
1.二叉树的递归定义
二叉树是有限个结点的集合,它或者为空集;或者是由一个根结点和两棵互不相交的,且分别称为根的左子树和右子树的二叉树所组成。

2、二叉树的一些性质
(1)二叉树的第层最多有
个结点,
(2)深度为k的二叉树最多有个结点
//这个性质可以由等比数列的前n项和推出来
(3)叶子的数目=度为2的结点数目+1
(4)满二叉树:深度为k,且结点数目为的二叉树,这个时候满二叉树的深度为
对于满二叉树的每一个结点,有以下性质

5.完全二叉树(full binary tree):
深度为k的有n个结点的二叉树,当且仅当每一个结点都与同深度的满二叉树中编号从1至n的结点一一对应,称之为完全二叉树

6.二叉树的存储结构
(1)、对于完全二叉树,我们会使用数组来处理
//不是完全二叉树的话,内存就不能充分的利用,尽量不要选择,如果不得不选择就在缺失的位置补上不存在的标志

(2)、链表(二叉和三叉的)

三叉链表:多了一个指向父亲结点的指针
(3)、静态链表
就是用一个结构体数组,存入数据,左边的结构序号和右边的结构序号
3.二叉树的遍历
1.遍历顺序
前序:根结点-左-右
中序:左-根结点-右
后序:左-右-根结点
层序遍历:一层一层地遍历
2.递归算法实现
void InorderTraversal( BinTree BT ) { if( BT ) { InorderTraversal( BT->Left ); /* 此处假设对BT结点的访问就是打印数据 */ printf("%d ", BT->Data); /* 假设数据为整型 */ InorderTraversal( BT->Right ); } } void PreorderTraversal( BinTree BT ) { if( BT ) { printf("%d ", BT->Data ); PreorderTraversal( BT->Left ); PreorderTraversal( BT->Right ); } } void PostorderTraversal( BinTree BT ) { if( BT ) { PostorderTraversal( BT->Left ); PostorderTraversal( BT->Right ); printf("%d ", BT->Data); } } void LevelorderTraversal ( BinTree BT ) { Queue Q; BinTree T; if ( !BT ) return; /* 若是空树则直接返回 */ Q = CreatQueue(); /* 创建空队列Q */ AddQ( Q, BT ); while ( !IsEmpty(Q) ) { T = DeleteQ( Q ); printf("%d ", T->Data); /* 访问取出队列的结点 */ if ( T->Left ) AddQ( Q, T->Left ); if ( T->Right ) AddQ( Q, T->Right ); } } //source:ZJU
3.中序遍历的非递归实现
void Midorder(struct BiTNode *t) //t为根指针 { struct BiTNode *st[maxleng];//定义指针栈 int top=0; //置空栈 do{ while(t) //根指针t表示的为非空二叉树 { if (top==maxleng) exit(OVERFLOW);//栈已满,退出 st[top++]=t; //根指针进栈 t=t->lchild; //t移向左子树 } //循环结束表示以栈顶元素的指向为 //根结点的二叉树的左子树遍历结束 if (top) //为非空栈 { t=st[--top]; //弹出根指针 printf("%c",t->data); //访问根结点 t=t->rchild; //遍历右子树 } } while(top||t); //父结点未访问,或右子树未遍历 } source:HUST
思路就是先找到最左的结点,把经过的根结点都保存了,后来左子树遍历完了就找上面根结点的右子树,再把右子树看成个树遍历,遍历完了就返回上一级(退栈),相当于更大的左子树访问完了



4.先序遍历的非递归实现

一样的,只不过不同的是,这里入栈就输出
5.后序遍历的非递归实现
注意,由于后序遍历需要遍历一遍左子树,在遍历一遍右子树,所以说保存根结点是十分必要的,所以说这里退栈就不会真退,仅仅是访问而已,如果右子树能能和之前访问过的结点匹配的话,就说明已经回到了根结点了!
核心:一个结点需要弹出两次,第一次弹出的时候还需要放回原位(左子树遍历完毕),第二次弹出的时候才输出其值(右子树遍历完毕); Status PostOrder2(BTree *BT) { Stack s,s2; BTree *T; int flag[MaxSize]; s.top=0; T=BT; while(s.top!=0||T){ while(T) { s.data[s.top++]=T; flag[s.top-1]=0; T=T->lchild; } while(s.top!=0&&flag[s.top-1]==1){ T=s.data[--s.top]; printf("%3d",T->data); } if(s.top!=0){ flag[s.top-1]=1; T=s.data[s.top-1]; T=T->rchild; } else break; } return OK; source:博客园
这里规定了访问次数这个量,被访问了两次就是要输出了 while (p != nullptr || !s.empty()) { // 入栈 if (p != nullptr) { s.push(p); p = p->left; } // 出栈 if (p == nullptr) { p = s.top(); s.pop(); p->times++; //遍历右子树 if (p->times == 1) { s.push(p); p = p->right; } //p.times==2; 继续弹栈 else { cout << p->data; p = nullptr; // 回溯的关键步骤 } } }
6.输入一组先序序列,构建二叉树

BiTree CreatBiTree2() { char ch; BiTree root; //二叉链表根结点指针 scanf(“%c”,&ch); //输入一个结点 if (ch ==' ') root=NULL; else { root=(BiTree) malloc(leng); //生成根结点 root->data=ch; root->lchild=CreatBiTree2(); //递归构造左子树 root->rchild=CreatBiTree2(); //递归构造右子树 } return root; }
当然,传指针传引用都是可以的
7.线索二叉树
二叉树一共有2n个指针域,占用了n-1和,剩下n+1个就会被利用

中序和后序都是一样的



当然了,带个头指针在指向二叉树本身的操作也是被允许的

8.表达式二叉树

9.中序+前序&后序表达式唯一确定二叉树zhon

3.树和森林
1.数组(双亲表示法) 数组里面存的是结构体,结构体两个元素,存数据和双亲
2.孩子表示法(链表)


3.孩子链表表示法
链Hash(bushi)

4.带双亲的孩子链表表示法:每一个结构体加一个双亲
5.树与二叉树的转换




树的遍历:
前根遍历:根——第一个儿子——……
后跟遍历:第一个儿子——第二个儿子——……——根
4.Huffman树
1.路径长度—-路径上分枝的数目(连线的数目)
2.树T的路径长度—-从树T的根到其余每个结点的路径长度之和,记作PL(T)
当n个结点的二叉树为完全二叉树时,PL(T)具有最小值:
当n个结点的二叉树为单枝树时,PL(T)具有最大值:
PL(T) = 1+2+…+(n-1) = n(n-1)/2
树T的带权路径长度—-每个叶子的权与根到该叶子的路径长度的乘积之和,记作WPL(T)=
n:叶子数 w_k叶子k的权 l_k路径长度

构建的方式用代码实现:
其实树可以表示成父母孩子表示法,每次合并的时候就找最小的两个数,标记已合并,构建新结点,新结点是没合并过的


Huffman编码的构建:就从自己开始找反序列,在调转即可
图
1.图的定义和术语
1.图
图G由顶点集V和关系集E组成,记为:G=(V,E),V是顶点(元素)的有穷非空集,E是两个顶点之间的关系的集合。
若图G任意两顶点a,b之间的关系为有序对,∈E, 则称为从a到b的一条弧/有向边;其中: a是的弧尾,b是的弧头;称该图G是有向图。
若图G的任意两顶点a,b之间的关系为无序对(a,b), 则称(a,b)为无向边(边),称该图G是无向图。 无向图可简称为图。
2.完全图
3.网:带权的图
4.子图:对图 G=(V,E)和G’=(V’,E’),
若V’V 且 E’
E,则称G’是G的一个子图
5.度:与顶点x相关联的边(x,y)的数目,称为x的度,记作TD(x) 或D(x)
以顶点x为弧尾的弧的数目,称为x的出度,记作OD(x)。
以顶点x为弧头的弧的数目,称为x的入度,记作ID(x)。
6.图的连通性质
对无向图G:
● 若从顶点vi到vj有路径,则称vi和vj是连通的。
● 若图G中任意两顶点是连通的,则称G是连通图。
● 若图G’是G的一个极大连通子图,则称G’是G的一个连通分量。(连通图的连通分量是自身)
对有向图G
● 若在图G中,每对顶点vi和vj之间, 从vi到vj,且从 vj到vi都存在路径,则称G是强连通图。
● 若图G’是G的一个极大强连通子图,则称G’是G的一个强连通分量。(强连通图的强连通分量是自身)
●设G=(V,E),G’=(V’,E’),V=V’,若G是连通图,G’是G的一个极小连通子图, 则G’是G的一棵生成树。
● 若有向图G有且仅有一个顶点的入度为0,其余顶点的入度
为1,则G是一棵有向树。
2.图的存储形式
1.数组表示法/邻接矩阵
顶点数组—用一维数组存储顶点(元素)
邻接矩阵—用二维数组存储顶点(元素)之间的关系(边或弧)
无向图的邻接矩阵是对称的由0-1构成


对于网来说道理亦同

2.邻接表:
无向图:把与头结点相连的所有元素都存进对应的链表里
有向图的邻接表:它指向的元素存进链表
有向图的逆邻接表:指向它的元素存进链表



如果把图改成了网,那就把每个指向的结点加上一个权重空间

3.有向图的十字链表
其实也很简单,每一个边结点加上弧尾和弧头,第一个指针下一个弧头一样的结点,第二个指针指向下一个弧尾一样结点
点结点就是两个指针:第一个指针指向第一个弧头为该结点的边结点;第二个指针就指向第一个弧尾为该结点的边结点

4.邻接多重表
点结点:就是data和第一个含有这个顶点的边
边结点,mark—-标志域,可用以标记该条边是否被搜索过;
vi和vj—-该条边依附的两个顶点在图中的位置;
vilink—-指向下一条依附于顶点vi的边;
vjlink—-指向下一条依附于顶点vj的边。

3.图的遍历
1.深度优先搜索:一直往下走,如果没有没被搜索到的结点,就搜索上一个被搜索的结点(Stack)

2.广度优先搜索:无论如何先把该结点的每个儿子先遍历了(队列)

4.最小生成树
1.DFS和BFS的生成树


生成森林:对图的每个联通分枝进行生成树搜索
5.网的最小生成树:
在网G的各生成树中,其中各边的权之和最小的生成树称为G的最小生成树
MST性质:设G=(V,E)是一个连通图,通过某种算法构造其最小生成树,T=(U,TE)是正在构造的最小生成树。如果边(u,v)是G中所有一端在U中(即u∈U)而另一端在V-U中(即v∈V-U)具有最小值的一条边,则必存在一棵包含边(u,v)的最小生成树。
6.Prim算法:
对n个顶点的连通网,初始时, T=(U,TE),U为一个开始顶点,TE=φ,以后根据MST性质,每次增加一个顶点和一条边,重复n-1次。U不断增大,V-U不断减小直到为空。


接着遍历与C连接的的点,更新V-U中各顶点到U的最短直接路径,我们发现C到F的距离为8,比无穷大小,更新值为8,把F中的相邻结点记为C




/* 邻接矩阵存储 - Prim最小生成树算法 */ Vertex FindMinDist( MGraph Graph, WeightType dist[] ) { /* 返回未被收录顶点中dist最小者 */ Vertex MinV, V; WeightType MinDist = INFINITY; for (V=0; V<Graph->Nv; V++) { if ( dist[V]!=0 && dist[V]<MinDist) { /* 若V未被收录,且dist[V]更小 */ MinDist = dist[V]; /* 更新最小距离 */ MinV = V; /* 更新对应顶点 */ } } if (MinDist < INFINITY) /* 若找到最小dist */ return MinV; /* 返回对应的顶点下标 */ else return ERROR; /* 若这样的顶点不存在,返回-1作为标记 */ } int Prim( MGraph Graph, LGraph MST ) { /* 将最小生成树保存为邻接表存储的图MST,返回最小权重和 */ WeightType dist[MaxVertexNum], TotalWeight; Vertex parent[MaxVertexNum], V, W; int VCount; Edge E; /* 初始化。默认初始点下标是0 */ for (V=0; V<Graph->Nv; V++) { /* 这里假设若V到W没有直接的边,则Graph->G[V][W]定义为INFINITY */ dist[V] = Graph->G[0][V]; parent[V] = 0; /* 暂且定义所有顶点的父结点都是初始点0 */ } TotalWeight = 0; /* 初始化权重和 */ VCount = 0; /* 初始化收录的顶点数 */ /* 创建包含所有顶点但没有边的图。注意用邻接表版本 */ MST = CreateGraph(Graph->Nv); E = (Edge)malloc( sizeof(struct ENode) ); /* 建立空的边结点 */ /* 将初始点0收录进MST */ dist[0] = 0; VCount ++; parent[0] = -1; /* 当前树根是0 */ while (1) { V = FindMinDist( Graph, dist ); /* V = 未被收录顶点中dist最小者 */ if ( V==ERROR ) /* 若这样的V不存在 */ break; /* 算法结束 */ /* 将V及相应的边<parent[V], V>收录进MST */ E->V1 = parent[V]; E->V2 = V; E->Weight = dist[V]; InsertEdge( MST, E ); TotalWeight += dist[V]; dist[V] = 0; VCount++; for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */ if ( dist[W]!=0 && Graph->G[V][W]<INFINITY ) { /* 若W是V的邻接点并且未被收录 */ if ( Graph->G[V][W] < dist[W] ) { /* 若收录V使得dist[W]变小 */ dist[W] = Graph->G[V][W]; /* 更新dist[W] */ parent[W] = V; /* 更新树 */ } } } /* while结束*/ if ( VCount < Graph->Nv ) /* MST中收的顶点不到|V|个 */ TotalWeight = ERROR; return TotalWeight; /* 算法执行完毕,返回最小权重和或错误标记 */ }
2.克鲁斯卡尔:
需要将边按递增次序排列以供选择。选择权重最小的边,然后保证没有环
怎么保证没有环?度!
4.有向无环图应用
一个无环的有向图称为有向无环图(directed acycline graph), 简称DAG图。
1.拓扑排序:
AOV网(Activity On Vertex network:以顶点表示活动,弧表示活动之间的优先关系的DAG图。


拓扑排序算法思想:重复下列操作,直到所有顶点输出完。
(1)在有向图中选一个没有前驱的顶点输出(选择入度为0的顶点);
(2)从图中删除该顶点和所有以它为尾的弧(修改其它顶点入度) 。
2.AOE网
AOE网研究的问题:
(1) 完成整项工程至少需要多少时间;
(2) 哪些活动是影响工程进度的关键。
1.(顶点)事件vi的最早发生时间ve(vi):从开始点到vi的最长路径长度。(ve(v1)=0),既表示事件vi的最早发生时间,也表示所有以vi为尾的弧所表示的活动ak的最早发生时间e(k)。
如果结点只有一个前驱结点:那就是前驱结点ve+到这个结点的边
有多个前驱结点:前驱结点ve+到这的边求最大值
2.活动最早开始时间ee(e)=所连接的弧尾的标记值
3.(顶点)事件vi允许的最迟开始时间vl(vi) = 完成点(汇点)vn的的最早发生时间ve(vn)减去vk到vn的最长路径长度。
如果有多个后继结点,对每个结点的值求最小即可
4.确定了顶点vi的最迟开始时间后,确定所有以vi为弧头的活动ak的最迟开始时间l(k):表示在不推迟整个工程完成的前提下,活动ak最迟必须开始的时间。
l(ak)=vl(ak弧头对应顶点)-活动ak的持续时间

5 最短路径
算法1(Dijkstra算法):
以每一个顶点为源点,重复执行Dijkstra算法n次,即可求出每一对顶点之间的最短路径。

/* 邻接矩阵存储 - 有权图的单源最短路算法 */ Vertex FindMinDist( MGraph Graph, int dist[], int collected[] ) { /* 返回未被收录顶点中dist最小者 */ Vertex MinV, V; int MinDist = INFINITY; for (V=0; V<Graph->Nv; V++) { if ( collected[V]==false && dist[V]<MinDist) { /* 若V未被收录,且dist[V]更小 */ MinDist = dist[V]; /* 更新最小距离 */ MinV = V; /* 更新对应顶点 */ } } if (MinDist < INFINITY) /* 若找到最小dist */ return MinV; /* 返回对应的顶点下标 */ else return ERROR; /* 若这样的顶点不存在,返回错误标记 */ } bool Dijkstra( MGraph Graph, int dist[], int path[], Vertex S ) { int collected[MaxVertexNum]; Vertex V, W; /* 初始化:此处默认邻接矩阵中不存在的边用INFINITY表示 */ for ( V=0; V<Graph->Nv; V++ ) { dist[V] = Graph->G[S][V]; if ( dist[V]<INFINITY ) path[V] = S; else path[V] = -1; collected[V] = false; } /* 先将起点收入集合 */ dist[S] = 0; collected[S] = true; while (1) { /* V = 未被收录顶点中dist最小者 */ V = FindMinDist( Graph, dist, collected ); if ( V==ERROR ) /* 若这样的V不存在 */ break; /* 算法结束 */ collected[V] = true; /* 收录V */ for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */ /* 若W是V的邻接点并且未被收录 */ if ( collected[W]==false && Graph->G[V][W]<INFINITY ) { if ( Graph->G[V][W]<0 ) /* 若有负边 */ return false; /* 不能正确解决,返回错误标记 */ /* 若收录V使得dist[W]变小 */ if ( dist[V]+Graph->G[V][W] < dist[W] ) { dist[W] = dist[V]+Graph->G[V][W]; /* 更新dist[W] */ path[W] = V; /* 更新S到W的路径 */ } } } /* while结束*/ return true; /* 算法执行完毕,返回正确标记 */ } Source:ZJU
算法2(Floyd算法):
算法思想:
假设求Vi到Vj的最短路径,如果从Vi到Vj有弧,则存在一条长度为arcs[i][j]的路径,该路径不一定是最短路径,尚需进行n次试探。
首先考虑(Vi,V0,Vj)是否存在(即判断(Vi,V0)和( V0,Vj)是否存在),如果存在,比较(Vi, Vj)和(Vi,V0)+( V0,Vj),取长度较短的为从Vi到Vj的中间顶点序号不大于0的最短路径。
再考虑路径上再增加一个顶点V1,如果考虑(Vi,…V1)和(V1,….Vj), (Vi,…V1)和(V1,….Vj)都是中间顶点序号不大于0的最短路径。 (Vi,…V1,….Vj)可能是从Vi到Vj的中间顶点序号不大于1的最短路径。
比较Vi到Vj的中间顶点序号不大于0的最短路径和(Vi,…V1)+(V1,….Vj),取长度较短的为从Vi到Vj的中间顶点序号不大于1的最短路径。
bool Floyd( MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum] ) { Vertex i, j, k; /* 初始化 */ for ( i=0; i<Graph->Nv; i++ ) for( j=0; j<Graph->Nv; j++ ) { D[i][j] = Graph->G[i][j]; path[i][j] = -1; } for( k=0; k<Graph->Nv; k++ ) for( i=0; i<Graph->Nv; i++ ) for( j=0; j<Graph->Nv; j++ ) if( D[i][k] + D[k][j] < D[i][j] ) { D[i][j] = D[i][k] + D[k][j]; if ( i==j && D[i][j]<0 ) /* 若发现负值圈 */ return false; /* 不能正确解决,返回错误标记 */ path[i][j] = k;/*记录I和j之间的中间结点*/ } return true; /* 算法执行完毕,返回正确标记 */ }
查找
查找表: 由同一类型的数据元素(记录)组成的集合。
记作:ST={a1,a2,…,an}
● 关键字: 可以标识一个记录的数据项
● 主关键字: 可以唯一地标识一个记录的数据项
● 次关键字: 可以识别若干记录的数据项
查找—-根据给定的某个关键字值,在查找表中确定一个其关键字等于给定值的记录或数据元素。
设k为给定的一个关键字值,R[1..n]为n个记录的表,若存在R[i].key=k,1≤i≤n,称查找成功;否则称查找失败。
静态查找: 查询某个特定的元素,检查某个特定的数据元素的属性,不插入新元素或删除元素(记录) 。
动态查找: 在查找过程中,同时插入查找表中不存在的数据元素(记录)。
1 顺序查找
typedef struct node
{ keytype key ; //关键字类型
char name[6]; //姓名
…… //其它
} ElemType;
typedef struct
{
ElemType elem[maxsize+1];//maxsize+1个记录,
//elem[0]为监视哨
int length;
} SSTable;
SSTable ST1,ST2;
不使用监视哨的判断语句:i>=1 && k!=ST.elem[i].key
监视哨:将数组第0个元素设置为要查找的元素
含有监视哨的查找表是肯定能找到的,如果在0找到就是没找到,就符合相等的直接返回下标即可
查找算法的性能分析:

● 考虑查找失败: 使用监视哨elem[0],为 n+1
不使用监视哨elem[0],为 n
假定查找成功和失败的机会相同,对每个记录的查找概率相等, Pi=1/(2*n), 则 ASL=3(n+1)/4
2 二分查找
int binsrch(SSTable ST,keytype k) { int low,mid,hig; low=1; hig=ST.length; while (low<=hig) { mid=(low+hig)/2; //计算中间记录的地址 if (k<ST.elem[mid].key) hig=mid-1; //查左子表 else if (k==ST.elem[mid].key) return mid; //查找成功,退出循环 else low=mid+1; //查右子表 } return 0;
小了,往小了猜,大了,往大了猜
判定树

插入方法:右子树最右,左子树最右,递归排序
ASL计算:每一个结点所在的层数求和/总的结点个数
满二叉树:公式:
3 索引顺序表

● 条件
(1)分块表”按块有序”, 索引表”按key有序”
(2)设n个记录分为b个块,每块的记录数s=n/b
● 查找方法
(1)顺序查找(或折半查找)索引表
确定k值所在的块号或块的首地址
(2)在某一块中顺序查找
● 最佳分块
s=√n b=√n
4 二叉排序树
(1) 二叉排序树的定义
如果二叉树的任一结点大于其非空左子树的所有结点,而小于其非空右子树的所有结点,则这棵二叉树称为二叉排序树。对一棵二叉排序树进行中序遍历,所得的结点序列一定是递增有序的。

ASL计算:同查找树
存储结构:跟二叉树一样
查找算法:大的往右,小的往左,找到了返回,遇到NULL就失败
插入算法:
删除算法:在二叉排序树中删除一个结点时,必须将因删除结点而断开的二叉链表重新链接起来,同时确保二叉排序树的性质不会失去。
为保证在删除节点后二叉排序树的性质不会丢失:
1、删除叶结点,只需将其双亲结点指向它的指针置空,再释放它即可。
2、被删结点缺左子树(或右子树),可以用被删节点的右子树(或左子树)顶替它的位置,再释放它。
3、被删结点左、右子树都存在,可以在它的右子树中寻找中序下的第一个结点(关键值最小),用它的值填补到被删结点中,再来处理这个结点的删除问题。
这个中序下的第一个结点就是右子树最左,交换结点域之后删除右子树最左的地方

BinTree Insert( BinTree BST, ElementType X ) { if( !BST ){ /* 若原树为空,生成并返回一个结点的二叉搜索树 */ BST = (BinTree)malloc(sizeof(struct TNode)); BST->Data = X; BST->Left = BST->Right = NULL; } else { /* 开始找要插入元素的位置 */ if( X < BST->Data ) BST->Left = Insert( BST->Left, X ); /*递归插入左子树*/ else if( X > BST->Data ) BST->Right = Insert( BST->Right, X ); /*递归插入右子树*/ /* else X已经存在,什么都不做 */ } return BST; } BinTree Delete( BinTree BST, ElementType X ) { Position Tmp; if( !BST ) printf("要删除的元素未找到"); else { if( X < BST->Data ) BST->Left = Delete( BST->Left, X ); /* 从左子树递归删除 */ else if( X > BST->Data ) BST->Right = Delete( BST->Right, X ); /* 从右子树递归删除 */ else { /* BST就是要删除的结点 */ /* 如果被删除结点有左右两个子结点 */ if( BST->Left && BST->Right ) { /* 从右子树中找最小的元素填充删除结点 */ Tmp = FindMin( BST->Right ); BST->Data = Tmp->Data; /* 从右子树中删除最小元素 */ BST->Right = Delete( BST->Right, BST->Data ); } else { /* 被删除结点有一个或无子结点 */ Tmp = BST; if( !BST->Left ) /* 只有右孩子或无子结点 */ BST = BST->Right; else /* 只有左孩子 */ BST = BST->Left; free( Tmp ); } } } return BST; } Source:ZJU
ASL:
最好情况(为满二叉树)
ASL= = O(log2 n)
最坏情况(为单枝树): ASL=(1+2+…+n)/n=(n+1)/2
平均值: ASL≈O(log2 n)
5 平衡二叉树(AVL树)
AVL树:由G.M.Adelson-Velskii和E.M.Landis提出。
结点的平衡因子:结点的左右子树的深度之差。
平衡二叉树:任意结点的平衡因子的绝对值小于等于1的二叉树。
存储类型:
typedef int DataType; //结点数据类型
typedef struct node { //AVL树结点定义
DataType data; //结点数据域
int balance; //结点平衡因子域
struct node *leftChild, *rightChild;
//结点左、右子树指针域
} AVLNode;
typedef AVLNode * AVLTree; //AVL树
如果在某一结点发现高度不平衡,停止回溯。从发生不平衡的结点起,沿刚才回溯的路径取直接下两层的结点。
如果这三个结点处于一条直线上,则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转, 其中一个是另一 个的镜像,其方向与不平衡的形状相关。
如果这三个结点处于一条折线上,则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。
我们看:不平衡的发现者是A,麻烦结点(让A发现不平衡的结点)在A的右边的右边,就需要做左单旋转

我们看:不平衡的发现者是A,麻烦结点(让A发现不平衡的结点)在A的左边的左边,就需要做右单旋转

需要变换的子树都是含有麻烦结点子树的兄弟
我们看:不平衡的发现者是A,麻烦结点(让A发现不平衡的结点)在A的左边的右边,就需要做左右旋转



我们看:不平衡的发现者是A,麻烦结点(让A发现不平衡的结点)在A的右边的左边,就需要做右左旋转



ZJU给出了一个更加直接的结论,可以下载文档查看:


代码:
typedef struct AVLNode *Position; typedef Position AVLTree; /* AVL树类型 */ struct AVLNode{ ElementType Data; /* 结点数据 */ AVLTree Left; /* 指向左子树 */ AVLTree Right; /* 指向右子树 */ int Height; /* 树高 */ }; int Max ( int a, int b ) { return a > b ? a : b; } AVLTree SingleLeftRotation ( AVLTree A ) { /* 注意:A必须有一个左子结点B */ /* 将A与B做左单旋,更新A与B的高度,返回新的根结点B */ AVLTree B = A->Left; A->Left = B->Right; B->Right = A; A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1; B->Height = Max( GetHeight(B->Left), A->Height ) + 1; return B; } AVLTree DoubleLeftRightRotation ( AVLTree A ) { /* 注意:A必须有一个左子结点B,且B必须有一个右子结点C */ /* 将A、B与C做两次单旋,返回新的根结点C */ /* 将B与C做右单旋,C被返回 */ A->Left = SingleRightRotation(A->Left); /* 将A与C做左单旋,C被返回 */ return SingleLeftRotation(A); } /*************************************/ /* 对称的右单旋与右-左双旋请自己实现 */ /*************************************/ AVLTree Insert( AVLTree T, ElementType X ) { /* 将X插入AVL树T中,并且返回调整后的AVL树 */ if ( !T ) { /* 若插入空树,则新建包含一个结点的树 */ T = (AVLTree)malloc(sizeof(struct AVLNode)); T->Data = X; T->Height = 0; T->Left = T->Right = NULL; } /* if (插入空树) 结束 */ else if ( X < T->Data ) { /* 插入T的左子树 */ T->Left = Insert( T->Left, X); /* 如果需要左旋 */ if ( GetHeight(T->Left)-GetHeight(T->Right) == 2 ) if ( X < T->Left->Data ) T = SingleLeftRotation(T); /* 左单旋 */ else T = DoubleLeftRightRotation(T); /* 左-右双旋 */ } /* else if (插入左子树) 结束 */ else if ( X > T->Data ) { /* 插入T的右子树 */ T->Right = Insert( T->Right, X ); /* 如果需要右旋 */ if ( GetHeight(T->Left)-GetHeight(T->Right) == -2 ) if ( X > T->Right->Data ) T = SingleRightRotation(T); /* 右单旋 */ else T = DoubleRightLeftRotation(T); /* 右-左双旋 */ } /* else if (插入右子树) 结束 */ /* else X == T->Data,无须插入 */ /* 别忘了更新树高 */ T->Height = Max( GetHeight(T->Left), GetHeight(T->Right) ) + 1; return T; }
排序
1.插入排序
算法基本思想
将待排序的记录插入到已排序的子文件中去,使得插入之后得到的子文件仍然是有序子文件。插入一个记录,首先要对有序子文件进行查找,以确定这个记录的插入位置。按查找方式的不同,插入排序又可以分为线性插入排序和折半插入排序,前者使用顺序查找,后者使用折半查找。
1.1 简单插入排序
插入排序:设待排序的文件为:(r[1],r[2],…,r[n])
关键字为:(r[1].key,r[2].key,…,r[n].key)
首先,将初始文件中的记录r[1]看作有序子文件;
第1遍:将r[2]插入有序子文件中,若:
r[2].key<r[1].key,
则r[2]插在r[1]之前;否则,插在r[1]的后面。
第2遍:将记录r[3]插入前面已有2个记录的有序子文件中,得到3个记录的有序子文件。
以此类推,依次插入r[4],…,r[n],最后得到n个记录的递增有序文件。
就是找到最好的插入位置

void InsertSort(RecType r[],int n)
// 对数组r[1..n]中的n个记录作插入排序
{ int i,j;
for (i=2;i<=n;i++){
r[0]=r[i]; //待插记录r[i]存入监视哨中
j=i-1; //以排序的范围1-i-1
//从r[i-1]开始向左扫描
while(r[0].key<r[j].key)
{
r[j+1]=r[j]; //记录后移
j–; //继续向左扫描
}
r[j+1]=r[0]; //插入记录r[0],即原r[i]
}
}
(1)最好情况,原n个记录递增有序:比较关键字n-1次,移动记录2(n-1)次,(将数据复制到r[0]后又复制回来)
(2)最坏情况:$O(n^2)$
1.2.折半插入排序(二分插入排序)
(a)由于插入排序的基本思想是在一个有序序列中插入一个新的记录,因此可以利用“折半查找”查询插入位置,由此得到的插入排序算法为“折半插入排序”,又被称为二分法插入排序。
(b)直接插入排序的算法简单易行,对长度(n)很大的记录序列宜采用性能更好的插入排序算法。
(c)折半插入排序过程中的折半查找的目的是查询插入点,因此不论是否存在和给定值相同的关键字,结束查找过程的条件都是high<low,并且插入位置为low指示的地方。

void BInsertSort (SqList &L) { // 对顺序表L作折半插入排序 for ( i=2; i<=L.length; ++i ) { //假定第一个记录有序 L.r[0] = L.r[i]; // 将L.r[i]暂存到L.r[0] low = 1; high = i-1; while (low<=high) { // 在r[low..high]中折半查找有序插入的位置 m = (low+high)/2; // 折半 if (L.r[0].key < L.r[m].key)) high = m-1; // 插入点在低半区 else low = m+1; // 插入点在高半区 } // while for ( j=i-1; j>=low; - -j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[high+1] = L.r[0]; // 插入 } //for } // BInsertSort
1.3.希尔(shell)排序 (缩小增量排序)
(a)是插入排序中效率最高的一种排序方法。又称“缩小增量排序”,是由D.L.Shell在1959年提出来的。
(b)基本思想是,先对待排序列进行“宏观调整”,待序列中的记录“基本有序”时再进行直接插入排序。注:所谓“ 基本有序” 是指,在序列中的各个关键字之前,只存在少量关键字比它大的记录。
(c)做法是:先取定一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组,所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序;然后,到第二个增量d2<d1重复上述分组和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
例如·:3 2 1
1 4 5 3 2 6
3:三类:14 25 36
1 2 5 3 4 6
2:2类:135 246
1 2 4 3 5 6
1:一类:123456
1 2 3 4 5 6
2 交换排序
2.1 冒泡排序
基本思想: 设待排序的文件为r[1..n]
第1趟(遍):从r[1]开始,依次比较两个相邻记录的关键字r[i].key和r[i+1].key,若r[i].key>r[i+1].key,则交换记录r[i]和r[i+1]的位置;否则,不交换。(i=1,2,…n-1)
第1趟之后,n个关键字中最大的记录移到了r[n]的位置上。
第2趟:从r[1]开始,依次比较两个相邻记录的关键字r[i].key和r[i+1].key,若r[i].key>r[i+1].key,则交换记录r[i]和r[i+1]的位置;否则,不交换。(i=1,2,…n-2)
第2趟之后,前n-1个关键字中最大的记录移到了r[n-1]的位置上。
……
作完n-1趟,或者不需再交换记录时为止。
void bubble1(int a[],int n) { int i,j,temp; for(i=0;i<n-1;i++) //作n-1趟排序 for(j=0;j<n-1-i;j++) if (a[j]>a[j+1]) { temp=a[j]; //交换记录 a[j]=a[j+1]; a[j+1]=temp; } for(i=0;i<n;i++) printf("%d",a[i]); //输出排序后的元素 }
可以加一个swap变量,如果一次排序没换过元素,那就是
● 最好情况: 待排序的文件已是有序文件,只需要进行1趟
排序,共计比较关键字的次数为 n-1 不交换记录。
● 最坏情况: 要经过n-1趟排序,所需总的比较关键字的次数为
(n-1)+(n-2)+…+1=n(n-1)/2
交换记录的次数最多为
(n-1)+(n-2)+…+1=n(n-1)/2
移动记录次数最多为
3n(n-1)/2 。
● 只需要少量中间变量作为辅助空间。 O(1)
● 算法是稳定的。
2.2 快速排序
基本思想:首先在r[1..n]中,确定一个r[i],经过比较和移动,将r[i]放到”中间”某个位置上,使得r[i]左边所有记录的关键字小于等于r[i].key,r[i]右边所有记录的关键字大于等于r[i].key。以r[i]为界,将文件划分为左、右两个子文件。
用同样的方法分别对这两个子文件进行划分, 得到4个更小的子文件。继续进行下去,使得每个子文件只有一个记录为止,便得到原文件的有序文件。
设置两个指针:一个大区域,一个小区域
void quksort(RecType r[],int low,int high) { RecType x;int i,j; if (low<high) //有两个以上记录 { i=low;j=high;x=r[i]; //保存记录到变量x中 do { //此时i指示位置可用 while (i<j && r[j].key>=x.key) j--; //j从右向左端扫描通过key不小于x.key的元素 if (i<j) //i,j未相遇 { r[i]=r[j]; i++; //此时j指示位置可用 while(i<j && r[i].key<=x.key) i++; //i从左向右端扫描通过key不大于x.key的元素 if (i<j) { r[j]=r[i];j--;} } } while (i!=j); //i,j未相遇 }
在上一级的函数就分治即可



就平均速度而言,快速排序是已知内部排序方法中最好的一种排序方法,其时间复杂度为$O(nlog_2n)$。
但是,在最坏情况下(基本有序时),快速排序所需的比较次数和冒泡排序的比较次数相同,其时间复杂度为$O(n^2)$。
快速排序需要一个栈空间来实现递归。若每次划分均能将文件均匀分割为两部分,则栈的最大深度为$|log_2n|+1$,所需栈空间为$O(log_2n)$,即空间复杂度 $S(n)= O (log2n)$
快速排序是不稳定的。
ElementType Median3( ElementType A[], int Left, int Right ) { int Center = (Left+Right) / 2; if ( A[Left] > A[Center] ) Swap( &A[Left], &A[Center] ); if ( A[Left] > A[Right] ) Swap( &A[Left], &A[Right] ); if ( A[Center] > A[Right] ) Swap( &A[Center], &A[Right] ); /* 此时A[Left] <= A[Center] <= A[Right] */ Swap( &A[Center], &A[Right-1] ); /* 将基准Pivot藏到右边*/ /* 只需要考虑A[Left+1] … A[Right-2] */ return A[Right-1]; /* 返回基准Pivot */ } void Qsort( ElementType A[], int Left, int Right ) { /* 核心递归函数 */ int Pivot, Cutoff, Low, High; if ( Cutoff <= Right-Left ) { /* 如果序列元素充分多,进入快排 */ Pivot = Median3( A, Left, Right ); /* 选基准 */ Low = Left; High = Right-1; while (1) { /*将序列中比基准小的移到基准左边,大的移到右边*/ while ( A[++Low] < Pivot ) ; while ( A[--High] > Pivot ) ; if ( Low < High ) Swap( &A[Low], &A[High] ); else break; } Swap( &A[Low], &A[Right-1] ); /* 将基准换到正确的位置 */ Qsort( A, Left, Low-1 ); /* 递归解决左边 */ Qsort( A, Low+1, Right ); /* 递归解决右边 */ } else InsertionSort( A+Left, Right-Left+1 ); /* 元素太少,用简单排序 */ }
(52, 49, 80, 36, 14, 75, 58, 97, 23, 61)
经第1趟快速排序之后为:(23, 49, 14, 36) 52 (75, 58, 97, 80, 61)
经第2趟快速排序之后为:(14) 23 (49, 36) 52 (61, 58) 75 (80, 97)
经第3趟快速排序之后为:(14, 23, 36, 49, 52, 58, 61, 75, 80, 97)
注:为避免出现枢轴记录关键字为”最大”或”最小”的情况,通常进行的快速排序采用”三者取中”的改进方案,即以 R[s]、R[t] 和 R[(s+t)/2] 三者中关键字介于中值者为枢轴。只要将它和 R[s] 互换,一次划分的算法仍不变。
3 选择排序
3.1 简单选择
算法思想:设待排序的文件为(r[1],r[2],…,r[n]),关键字为(r[1].key,r[2].key,…,r[n].key),
第1趟(遍):在(r[1],r[2],…,r[n])中,选出关键字最小的记录r[min].key,若min≠1,则交换r[1]和r[min];
需要进行n-1次比较。
第2趟(遍):在n-1个记录(r[2],…,r[n])中,选出关键字最小的记录r[min].key,若min≠2,则交换r[2]和r[min];
需要进行n-2次比较。
第n-1趟(遍):在最后的2个记录记录(r[n-1],r[n])中,选出关键字最小的记录r[min].key,若min≠n-1,则交换r[n-1]和r[min];需要进行1次比较。

3.2 树形选择排序
树形选择排序又称锦标赛排序(Tournament Sort),是一种按照锦标赛的思想进行选择排序的方法。可用一棵有n个叶子结点的完全二叉树表示。
基本思想为:
首先对n个记录的关键字进行两两比较,然后在其中n/2个较小者之间再进行两两比较,如此重复,直到选出最小关键字的记录为止(树根)。
将最小关键字输出,且将其原来位置改为极大数,与此位置相关部分重新(向树根方向)进行比较,选出次小关键字,保留结果。
如此下去,直至全部排序完成。

该方法比直接选择排序速度上有很大提高,其缺点有:
(1)需要另开储存空间保存排序结果;
(2)n个待排序关键字,需要额外的(n-1)个内部结点(包括根结点),增加了内存开销。
(3)将最小关键字改为极大数,再与兄弟结点比较属于多余。
故:树形选择排序一般不是用来排序而是用来证明某些问题。为了弥补以上缺点,威洛姆斯在1964年提出了另一种形式的选择排序—堆排序。
3.3 堆排序
堆的定义略
问题1:如何将序列{k1,k2,…,kn} 处理成(大顶)堆(初始化)?
问题2:如何在堆顶元素被替换后,调整剩余元素成为一个新的堆。

void Swap( ElementType *a, ElementType *b ) { ElementType t = *a; *a = *b; *b = t; } void PercDown( ElementType A[], int p, int N ) { /* 改编代码4.24的PercDown( MaxHeap H, int p ) */ /* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */ int Parent, Child; ElementType X; X = A[p]; /* 取出根结点存放的值 */ for( Parent=p; (Parent*2+1)<N; Parent=Child ) { Child = Parent * 2 + 1; if( (Child!=N-1) && (A[Child]<A[Child+1]) ) Child++; /* Child指向左右子结点的较大者 */ if( X >= A[Child] ) break; /* 找到了合适位置 */ else /* 下滤X */ A[Parent] = A[Child]; } A[Parent] = X; } void HeapSort( ElementType A[], int N ) { /* 堆排序 */ int i; for ( i=N/2-1; i>=0; i-- )/* 建立最大堆 */ PercDown( A, i, N ); for ( i=N-1; i>0; i-- ) { /* 删除最大堆顶 */ Swap( &A[0], &A[i] ); /* 见代码7.1 */ PercDown( A, 0, i ); } }
这个代码把问题1和问题2统一化了
时间复杂度:O(nlogn)
4 归并排序

归并的操作,就是两个指针,谁少就copy谁,最后就把剩下的元素copy过去
第一个想法:
每个子文件的长度从2,4,8一直递增
1.假如说:现在还剩下2s以上的空缺,就直接s和s互相互补即可
2.假如说:现在还剩下s-2s的空缺,就剩下的部分归并
3.假如说:现在还剩下0-s的空缺,就直接照抄


当然,还有一种写法就是找到最中间的一个元素,然后进行分化
/* 归并排序 - 递归实现 */ /* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/ void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd ) { /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */ int LeftEnd, NumElements, Tmp; int i; LeftEnd = R - 1; /* 左边终点位置 */ Tmp = L; /* 有序序列的起始位置 */ NumElements = RightEnd - L + 1; while( L <= LeftEnd && R <= RightEnd ) { if ( A[L] <= A[R] ) TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */ else TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */ } while( L <= LeftEnd ) TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */ while( R <= RightEnd ) TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */ for( i = 0; i < NumElements; i++, RightEnd -- ) A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */ } void Msort( ElementType A[], ElementType TmpA[], int L, int RightEnd ) { /* 核心递归排序函数 */ int Center; if ( L < RightEnd ) { Center = (L+RightEnd) / 2; Msort( A, TmpA, L, Center ); /* 递归解决左边 */ Msort( A, TmpA, Center+1, RightEnd ); /* 递归解决右边 */ Merge( A, TmpA, L, Center+1, RightEnd ); /* 合并两段有序序列 */ } } void MergeSort( ElementType A[], int N ) { /* 归并排序 */ ElementType *TmpA; TmpA = (ElementType *)malloc(N*sizeof(ElementType)); if ( TmpA != NULL ) { Msort( A, TmpA, 0, N-1 ); free( TmpA ); } else printf( "空间不足" ); }
/* 归并排序 - 循环实现 */ /* 这里Merge函数在递归版本中给出 */ /* length = 当前有序子列的长度*/ void Merge_pass( ElementType A[], ElementType TmpA[], int N, int length ) { /* 两两归并相邻有序子列 */ int i, j; for ( i=0; i <= N-2*length; i += 2*length ) Merge( A, TmpA, i, i+length, i+2*length-1 ); if ( i+length < N ) /* 归并最后2个子列*/ Merge( A, TmpA, i, i+length, N-1); else /* 最后只剩1个子列*/ for ( j = i; j < N; j++ ) TmpA[j] = A[j]; } void Merge_Sort( ElementType A[], int N ) { int length; ElementType *TmpA; length = 1; /* 初始化子序列长度*/ TmpA = malloc( N * sizeof( ElementType ) ); if ( TmpA != NULL ) { while( length < N ) { Merge_pass( A, TmpA, N, length ); length *= 2; Merge_pass( TmpA, A, N, length ); length *= 2; } free( TmpA ); } else printf( "空间不足" ); }
5 基数排序
就是构建十个桶,按照个位,先按照各元素放入桶里.
接着再取出,按照0-9的顺序,接着是十位,接着是百位
/* 基数排序 - 次位优先 */ /* 假设元素最多有MaxDigit个关键字,基数全是同样的Radix */ #define MaxDigit 4 #define Radix 10 /* 桶元素结点 */ typedef struct Node *PtrToNode; struct Node { int key; PtrToNode next; }; /* 桶头结点 */ struct HeadNode { PtrToNode head, tail; }; typedef struct HeadNode Bucket[Radix]; int GetDigit ( int X, int D ) { /* 默认次位D=1, 主位D<=MaxDigit */ int d, i; for (i=1; i<=D; i++) { d = X % Radix; X /= Radix; } return d; } void LSDRadixSort( ElementType A[], int N ) { /* 基数排序 - 次位优先 */ int D, Di, i; Bucket B; PtrToNode tmp, p, List = NULL; for (i=0; i<Radix; i++) /* 初始化每个桶为空链表 */ B[i].head = B[i].tail = NULL; for (i=0; i<N; i++) { /* 将原始序列逆序存入初始链表List */ tmp = (PtrToNode)malloc(sizeof(struct Node)); tmp->key = A[i]; tmp->next = List; List = tmp; } /* 下面开始排序 */ for (D=1; D<=MaxDigit; D++) { /* 对数据的每一位循环处理 */ /* 下面是分配的过程 */ p = List; while (p) { Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */ /* 从List中摘除 */ tmp = p; p = p->next; /* 插入B[Di]号桶尾 */ tmp->next = NULL; if (B[Di].head == NULL) B[Di].head = B[Di].tail = tmp; else { B[Di].tail->next = tmp; B[Di].tail = tmp; } } /* 下面是收集的过程 */ List = NULL; for (Di=Radix-1; Di>=0; Di--) { /* 将每个桶的元素顺序收集入List */ if (B[Di].head) { /* 如果桶不为空 */ /* 整桶插入List表头 */ B[Di].tail->next = List; List = B[Di].head; B[Di].head = B[Di].tail = NULL; /* 清空桶 */ } } } /* 将List倒入A[]并释放空间 */ for (i=0; i<N; i++) { tmp = List; List = List->next; A[i] = tmp->key; free(tmp); } }
6 计数排序
这个可以用于排序的数范围已知的情况,非常好写
7 排序算法的比较

线性结构
1 基础
1.数据,数据元素,数据对象,数据项,数据结构的概念
什么是基本单位,什么是最小单位,什么是所有能输入到计算机中并被计算机程序处理的符号总称?性质相同的元素的集合?
2.结构的分类?
逻辑结构:集合,线性表,树,图
物理结构:顺序存储结构,物理存储结构,索引存储结构,哈希存储结构
3.引用参数:&:可以扩展为指针
4.算法的五个特征
(1)有穷性
(2)可读性
(3)健壮性
(4)可行性
(5)高效性
5.时间复杂度的分析:
(1)大致的时间复杂度为多数
(2)递归或者循环调用时,调用的每个语句都要算进去
(3)计算语句频度的方法?
6.空间复杂度分析:
(1)递归:有栈存储,至少的空间
(2)有递归次数:
2 线性表
1.表长:表长与存储的长度区别,maxlength和size的区别
2.直接前驱后继:首元素没有前驱,尾元素没有后继
3.抽象数据类型:了解(跟class一样)
4.存储特征:
顺序存储结构:可以随机读取元素,插入删除复杂
链式存储结构:不可以随机读取元素,插入删除较为简单
5.自由区:空闲的空间
6.首地址+偏移量选址法
(见数组)
7.动态静态分配的顺序存储结构
静态存取
#define maxleng 100 typedef struct { ElemType elem[maxleng];//下标:0,1,...,maxleng-1 int length; //表长 } SqList; SqList La;
动态存取:
#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { ElemType *elem;//存储空间基地址 int length; //表长 int listsize; //当前分配的存储容量 //(以sizeof(ElemType)为单位 } SqList; SqList Lb;
有增量#define LISTINCREMENT 10
溢出时扩充的方法
if (L.length>=L.listsize) /*溢出时扩充*/ { ElemType *newbase; newbase=(ElemType *) realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType)); if (newbase==NULL) return OVERFLOW; //扩充失败 L.elem=newbase; L.listsize+=LISTINCREMENT; }
9.链表
1.带头结点和不带头结点
带头结点的作用:需要额外开辟一个空间,但是插入和删除首元素时不用进行特殊处理
10.静态链表:用数组模拟,数组里面有data域和下一个元素的编号,head->0,尾元素指向0
11.循环链表:
尾指针:有头:指向表头
无头:指向第一个元素
head:设置任意一个指
只需要设一个尾指针就可以满足,可以找到链表的任何一个值
12.双向链表
首结点前驱是空,尾结点后继是空
表头结点前驱是尾结点,后继指头结点
会考一些操作
13.双向循环链表:没有哪一个指针域是空

3 栈和队列
3.1 栈
1.先进后出
2.栈顶和栈底的定义
3.栈顶的几个定义法:和
的上一个单元:空栈时分别对应-1和0
4.进展顺序判断:第二斯特林数,溢出和下溢的判断
5.符号表达式和代替递归函数
6.存储形式
(1)数组,加个top
(2)链式存储,用表头插入:搞清楚插入删除的复杂度:
3.2 队列
1.先进先出
2.双向队列:中间值不能动
输入受限:只允许在表的一端插入、在两端删除元素的线性表
输出受限:只许在表的两端插入、在一端删除元素的线性表
3.循环队列:
溢出判断:(Q.rear+1)% MAXLENGQ.front
下溢判断:Q.front==Q.rear
算队列长的方法:(Q.rearQ.front+maxlength)%maxlength
改进:有6个空间,只存5个元素
还要记住几个插入删除的算法怎么写
4 串
1.’\0’C语言
a[0]存指定的串长 Pascal
2.字符堆:指针指向一个地址(第一个字母的地址),还有一个元素存长度
3.链式堆的存储密度
(1)多字符和单字符
(2)计算方式:,开辟的总空间=字符数+指针域
4.KMP算法,求那个next数组的值

5 数组
1.行存储和列存储:
首元素寻址法:有0行0列和无0行0列
从左到右&从右到左
例子:三维数组a[1..p,1..m,1..n],假定无0页0行0列
1)以行序为主序,的地址为
(2)以列序为主序,的地址为
如果有0行0列:所有-1去掉
2.矩阵压缩存储
(1)对称矩阵与三对角

3.稀疏矩阵
(1)三元组表:存行列值和元素值
(2)十字链表
4.广义表:加递归,元素可以是单独的值也可以是新的广义表

结构位置表示:a,b,c,d 都表明好
(1)广义表的图型表示—-树型结构
约定 □—-单元素/原子
○—-列表,若有表名,附表名:对应()
(2)存储结构

(3)表头:第一个元素:可元素,可表
(4)表尾:剩下的元素都是表尾,一定是广义表
0 条评论