数据结构重点代码
前言
本文是为了总结个人认为的数据结构重点代码(不包括图代码)
顺序表部分
//顺序表结构体定义 |
-
一个顺序表内包涵各类字符串，设计算法把顺序表内的字母元素放在左端，非字母元素放在右端，要求使用当前数据空间且移动次数尽可能少(2023真题)
//算法思路：定义3个函数,方便调用,is_alpha函数判断输入的data是否为字母元素,swap函数交换输入的两值,主函数move_letters_to_left中负责调整元素
//1. move_letters_to_left函数中定义left,right分别指向顺序表中第一个元素和最后一个元素
//2. 当data[left]是字母时,left后移,找到第一个非字母停止,
//3. right从最后一个元素从后往前扫描,对于data[right]是非字母时,right前移,找到第一个是字母时停止
//4. 交换 swap(l.data[left], l.data[right]),交换完left后移,right前移
//5. 重复2,3,4步骤,直到left和right相遇为止
int is_alpha(char data){
if ((ch>= 'a' && ch <= 'z' )|| (ch >= 'A' && ch <= 'Z')) {//判断输入字符是否为字母元素
return 1;
}
return 0;
}
void swap(datatype &a,datatype &b){//交换两值
char temp=a;
a=b;
b=temp;
}
void move_letters_to_left(seqlist &l, int len) {
int left = 0, right = len-1;
while (left < right) {//循环结束的时候，字母和非字母就已经完成调整
if (is_alpha(l.data[left])) {//left位是字母元素，left++
left++;
} else if (!isalpha(l.data[right])) {//right上是非字母元素，right--
right--;
} else {
swap(l.data[left], l.data[right]);//当上面if语句走完就已经找到需要交换的元素位置left和right，交换完成后left++，right--,移动指针，继续对比
left++;
right--;
}
}
} -
实现顺序表的逆置
//算法思路：定义两个函数swap与reverse,swap用于交换两值
//reverse函数中定义两值,i,j分别指向顺序表第一个元素与最后一个元素
//依次调用swap交换两端元素,交换完成i后移,j前移
//直到i,j相遇时,顺序表逆置完成.
void swap(datatype &a,datatype &b){//交换两值
char temp=a;
a=b;
b=temp;
}
void reverse(seqlist &l){//逆置
int i,j;
i=0,j=l.length-1;
while(i<j){
swap(l.data[i],l.data[j]);
i++;
j--;
}
} -
在一个有序表内插入值为x节点后,表依旧有序(2016年真题)
//算法思路：先判断当前表的情况 是否为空表或者表满,表满时无法插入,空表时直接插入到第一个后length+1
//当表内已存在元素时,定义i 依次循环比较data[i]是否大于x,当小于时 i后移,
//当while循环结束时,此刻找到插入位置i,同时考虑当前i的位置有两种情况1为表内2为表尾,当为表尾时,直接插入表尾后length+1即可,当i位置处于表内时,需将i后元素依次后移一位后插入x,后length+1即可.
void insertx(seqlist *l,datatype x){
if (l->length==MaxSize){//表满
printf("FULL");
return;
}
if (l->size==0){//空表时,直接放入
l->data[0]=x;
l.length+=1;
}
int i;
while (i<l->length&&l->data[i]<x){//找到插入位置
i++;
}
if(i<=l->length-1){//当插入位置在表内(0-lenght-1)
for(int j=l->length-1,j>=i,j--){ //或者j = l->length; j >i ; j-- 则 l->data[j]=l->data[j-1];
l->data[j+1]=l->data[j];
}
l->data[i]=x;
l->length+=1;
}else{//插入位置不在当前表中,放入表尾(此刻x大于全表任何元素)
l->data[l->length]=x;
l->length+=1;
}
}
链表部分
//链表结构体定义 |
-
带头节点的单链表,设计函数,求两个单链表的合集,结果用新的链表返回(2013年真题）
//算法思路：定义p ，q指针,分别指向A B 的第一个数据节点.同时创建合集链表的头节点C,C的尾结点r,定义s指针为元素插入C表准备,
//当p,q都存在时,先固定p指针不动,将q指针依次后移,当找到与p指针指向元素一致元素时,插入C表,插入后p指针后移,循环往复,
//直到while循环结束时,合集链表都已经插入完成,此时处理尾结点使其置空 return C函数结束
linklist merge(Linklist A,Linklist B){
linklist C=(Lnode*)malloc(sizeof(Lnode));//头节点
Lnode* r, *s;
r=C;
Lnode* p=A->next;
Lnode* q=B->next;
while(p){//p存在
while(q&&q->data!=p->data){//非合集 后移动q
q=q->next;
}
if(q){//是合集元素，插入C表
s=(Lnode*)malloc(sizeof(Lnode));//创建插入节点
s->data=q->data;
r->next=s;//尾插法
r=s;
}
p=p->next;.//往后遍历
}
r->next=Null;//处理尾节点
return C;
} -
两个带头结点的升序链表合并成一个新的带头节点的升序链表（2022年真题）
linklist merge(linklist A,linklist B){
linklist c=(Lnode*)malloc(sizeof(Lnode));
Lnode*r=c;
Lnode*p=A->next;
Lnode*q=B->next;
while(q&&p){
if(p->data>q->data){//q<p时
B->next=q->next;//q节点断链
r->next=q;//r链接至q
r=q;//表尾指针后移
q=B->next;//更新q指针
}else{//q>p时
A->next=p->next;//p节点断链
r->next=p;//r链接至p
r=p;//表尾指针后移
p=B->next;//更新p指针
}
}
if(q){//当q不为空时,链接到r
r->next=q;
}
if(p){//当p不为空时,链接到r
r->next=p;
}
free(A);
free(B);
return C;
} -
删除带头节点中的奇数值的节点（2018/2014年真题)
linklist delodd(linklist &l){
if(l==null){
return NULL;
}
Lnode*pre=l,p=l->next;
while(p){
if(p->data%2==0){//偶数后移动
pre=p;
p=p->next;
}else{//奇数删除
pre->next=p->next;
free(p);
p=pre->next;
}
}
} -
删除不带头节点中的第一个值为x的节点（2015年真题)
linklist del_x(linklist &l){
if(l==NULL){
printf("空表");
return NULL;
}
Lnode*pre=(Lnode*)malloc(sizeof(Lnode));//虚拟头节点
pre->next=l;//虚拟头结点链接到l
Lnode*p=pre->next,*s=pre;//p为数据节点,s标识pre是否移动
while(p&&p->data!=x){
pre=p;
p=p->next;
}
if(p){//找到值为x的节点
if(s==pre){//pre未移动表示值为x的节点是第一个数据节点
l=l->next;//l直接后移一个即可
}else{//删除值为x的节点
pre->next=p->next;
free(p);
}
}
return l;
} -
求单链表中的节点个数（2016年真题)
int count(linklist l){//节点是指数据节点
if(l==head){
return 0;
}
int n=0;
Lnode*p=l->next;
while(p){
n++;
p=p->next;
}
return n;
} -
不带头节点的单链表是否为升序链表，是返回1，不是返回2（2021年真题）
int isuporder(linklist l){
if(l==Null){
return 0;
}
Lnode*pre=l,*p=l->next;
while(p){
if(pre->data>p->data){//非升序返回0
return 0;
}else{//当前是升序 ，后移
pre=p;
p=p->next;
}
}//while循环结束时，单链表为升序 返回1
return 1;
} -
删除不带头节点head的倒数第m个元素（2023年真题）
//写法一:虚拟头结点
linklist del_m(linklist &l){
if(l==NULL){
return NULL;
}
Lnode*pre=(Lnode*)malloc(sizeof(Lnode));//虚拟头结点
pre->next=l;
Lnode*p=pre->next;
int len=1;
while(p&&len<=m){//len取0时 len<m ,len取1时 len<=m 否则后移次数对不上
len++;
p=p->next;
}
if(len<m){
printf("表长不够");
return l;
}
while(p){
pre=pre->next;
p=p->next;
}
Lnode*s=pre->next;//pre后一个节点就是倒数第m个元素
pre->next=s->next;
free(s);
return l;
}
//写法二
linklist del_m(linklist &l){
if(l==NULL){
return NULL;
}
Lnode* pre,*s;
Lnode*p=l;
int len=0;
while(p&&count<m){
p=p->next;
len++;
}
if(len<m){
printf("表长不够");
return l;
}
if(p==NULL){//当p在表尾,此刻倒数第m个元素就是表中第一个元素,删除即可
pre=l;;
l=l->next;
free(pre);
retrun l;
}
s=l;
while(p){//p处于表中
pre=s;
s=s->next;
p=p->next;
}//删除第m个节点就是当前的s元素
pre->next=s->next;
free(s);
return l;
} -
一个带头结点的单链表,将奇数移到链表前面,偶数放到后面
void pation(linklist &l){
if(l==NULL){
return;
}
Lnode *pre=l,p=pre->next;
while(p&&p->data%2==1){//奇数后移
pre=p;
p=p->next;
}
while(p){
while(p&&p->data%2==0){
pre=p;
p=p->next;
}
if(p){//偶数后存在奇数时,将其头插到前方
pre->next=p->next;
p->next=l->next;//头插法
head->next=p;
p=pre->next;//更新p指针
}
}
}
树部分
结构体
//二叉树结构体定义 |
-
3种遍历（递归）
//前序遍历
void preOrder(binTree T) {
if (T != NULL) {
printf("%d",T->data);
preOrder(T->lchild);
preOrder(T->rchild);
}
}
//中序遍历
void InOrder(binTree T) {
if (T != NULL) {
InOrder(T->lchild);
printf("%d",T->data);
InOrder(T->rchild);
}
}
//后序遍历
void PostOrder(binTree T) {
if (T != NULL) {
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%d",T->data);
}
} -
层次遍历
//层次遍历借助队列完成 此处提供两种写法 一种为伪代码 另一种为数组队列
void LevelOrder1(binTree T){//伪代码写法
if(T==NULL){
return;
}
Queue Q;
InitQueue(Q);
binode*p=T;
Enqueuq(Q,p);
while(!isempty(Q)){
Dequeue(Q,p);
print("%d",p->data);
if(p->lchild){
Enqueuq(Q,p->lchild);
}
if(p->rchild){
Enqueuq(Q,p->lchild);
}
}
}
void levelorder2(binTree T){//数组队列方式
if(T==NULL){
return;
}
binode* queue[MaxSize];
int front=-1,rear=-1;
binode*p=T;
queue[++rear]=p;
while(front<rear){
p=queue[++front];
print("%d",p->data);
if(p->lchild){
queue[++rear]=p->lchild;
}
if(p->rchild){
queue[++rear]=p->rchild;
}
}
} -
反转层次遍历
//算法思路:与层次遍历一致,但是在出队时,不打印元素,而是使其进栈,在完成层次遍历后,依次出栈打印这样打印出来的就是反转的层次遍历
void ReLevelOrder1(binTree T){//伪代码写法
if(T==NULL){
return;
}
Queue Q;
Stack S;
InitStack(S);
InitQueue(Q);
binode*p=T;
Enqueuq(Q,p);
while(!isempty(Q)){
Dequeue(Q,p);
Push(S,p);
if(p->lchild){
Enqueuq(Q,p->lchild);
}
if(p->rchild){
Enqueuq(Q,p->lchild);
}
}
while(!isempty_stack(s)){//栈非空
Pop(S,p);//出栈打印即是反转层次遍历
printf("%d",p->data);
}
} -
先序非递归/前序非递归
//非递归遍历借助于栈实现
void PreOrder(binTree T){//打印顺序为根左右
Stack S;
InitStack(S);
binode*p=T;
while(p||!isempty(s)){
if(p!=null){
print("%d",p->data);//打印节点数据
Push(S,p);//节点进栈
p=p->lchild;//遍历左子树
}else{//左子树进栈完成,转到右子树
Pop(S,p);
p=p->rchild;
}
}
} -
中序非递归(2019年真题)
void InOrder(binTree T){//打印顺序为左根右
Stack S;
InitStack(S);
binode*p=T;
while(p||!isempty(s)){
if(p!=null){
Push(S,p);//节点进栈
p=p->lchild;//遍历左子树
}else{
Pop(S,p);//节点出栈
print("%d",p->data);//打印节点数据
p=p->rchild;//遍历右子树
}
}
} -
后序非递归
void PostOrder(binTree T){//打印顺序为左右根 特殊一些,需要考虑在子树时如何返回到根节点
Stack S;
InitStack(S);
binode*p=T;
binode*r=NULL;//r负责记录上一个打印的节点位置
while(p||!isempty(S)){
if(p!=null){
Push(S,p);//节点进栈
p=p->lchild;//遍历左子树
}else{
GetTop(S,p);//p为空时,则获取栈顶元素
if(p->rchlid&&p->rchild!=r){//p有右孩子且未遍历
p=p->rchild;//p遍历右子树
}else{//没有右子树或者右子树遍历过
Pop(S,p);
print("%d",p->data);//打印节点数据
r=p;//更新记录节点
p=NULL;//遍历指针置空
}
}
}
} -
打印二叉树中x节点的所有祖先,设x的值不超过1个
//后序遍历中,栈中存放节点的祖先
void find_x_ancestor(binTree T,int x){
Stack S;
InitStack(S);
binode*p=T;
binode*r=NULL;//r负责记录上一个打印的节点位置
while(p||!isempty(S)){
if(p!=null){
Push(S,p);//节点进栈
p=p->lchild;//遍历左子树
}else{
GetTop(S,p);//p为空时,则获取栈顶元素
if(p->rchlid&&p->rchild!=r){//p有右孩子且未遍历
p=p->rchild;//p遍历右子树
}else{//没有右子树或者右子树遍历过
Pop(S,p);
if(p->data==x){//改写部分-在出栈后判断是否为x,当为x值,当前栈内就是x的祖先元素
while(!empty(S)){
Pop(S,p);
printf("%d",p->data);
}
}
r=p;//更新记录节点
p=NULL;//遍历指针置空
}
}
}
} -
求二叉树的高度/深度(递归)
int depth(binTree T){
if(T==NULL){
return 0;
}
int ldep,rdep;
ldep=depth(T->lchild);//ldep统计左子树高度
rdep=depth(T->rchild);//rdep统计右子树高度
if(ldep>rdep){//比较左右子树高度,取最大值+1 ,+1为根的高度
return ldep+1;
}else{
return rdep+1;
}
} -
非递归求二叉树的高度/深度(2021真题)
//类层次遍历的思路,当一层最右节点出队时,这层就已经遍历完成,h加一
int high(binTree T){
if(T==NULL){
return 0;
}
int h=0,last=0;//last指向每层最后一个节点
binode*Q[MaxSize];//数组队列
int front=-1,rear=-1;//从-1开始方便对应关系
binode*p=T;
Q[++rear]=p;//根进队
while(front<rear){//队列非空
p=Q[++front];//出队
if(p->lchild){
Q[++rear]=p->lchild;
}
if(p->rchild){
Q[++rear]=p->rchild;
}
if(front==last){//当二叉树一层的最右节点出队时
h++;
last=rear;//last移动到下一层
}
}
return h;
} -
求二叉树的单分支节点个数
int count(binTree T){
if(T==NULL){
return 0;
}
int n1,n2;
if((T->lchild==null&&T->rchild)||(T->rchild==null&&T->lchild)){//根为单分支
n1=count(T->lchild);
n2=count(T->rchild);
return n1+n2+1;//额外+1
}else{
n1=count(T->lchild);
n2=count(T->rchild);
return n1+n2;
}
} -
求二叉树双分支节点个数
int count(binTree T){
if(T==NULL){
return 0;
}
int n1,n2;
if(T->lchild&&T->rchild){//根为双分支
n1=count(T->lchild);
n2=count(T->rchild);
return n1+n2+1;//额外+1
}else{
n1=count(T->lchild);
n2=count(T->rchild);
return n1+n2;
}
} -
求二叉树叶子节点个数
//此处提供两种写法,一种利用全局变量,一种通过返回int
int n=0;
void count1(binTree T){
if(T!=NULL){
if(T->lchild==null&&T->rchild==null){
n++;
}
count1(T->lchild);
count1(T->rchild);
}
}
int count2(binTree T){
if(T==NULL){
return 0;
}
int n1,n2;
if(T->lchild==null&&T->rchild==null){
return 1;
}else{
n1=count2(T->lchild);
n2=count2(T->rchild);
return n1+n2;
}
} -
求二叉树是否等价
int equal(binTree T1,binTree T2){
int left,right;
if(T1==NULL&&T2==NULL){//都为空时,等价
return 1;
}else if(T1==NULL||T2==NULL){//有一个不为空时,不等价
return 0;
}else{//递归比较
left=equal(T1->lchild,T2->lchild);
right=equal(T1->rchild,T2->rchild);
return left&&right;
}
} -
交换二叉树左右子树
void swap(binTree &T){
if(T!=NULL){
binode*temp=T->lchild;
T->lchild=T->rchild;
T->rchild=temp;
swap(T->lchild);
swap(T->rchild);
}
} -
查找x节点所在层数
void search_x_level(bintree T,int x,int level){//level初值为1
if(T!=NULL){
if(T->data==x){
print("x在第%d层",level);
}
search_x_level(T->lchild,x,level+1);
search_x_level(T->rchild,x,level+1);
}
} -
求二叉树的宽度(一个树中节点数最多的一层的节点个数)
//层次遍历改写+level数组统计
void width(bintree T){
if(T==NULL){
return 0;
}
binode*Q[MaxSize];
int front=0,rear=0;//队头,队尾
int level[MaxSize];
binode*p=T;
int k=1;//记录层数
level[rear]=k;//更新level数组
level[rear]=p;//根进队
rear++;//更新rear
while(front<rear){//队列非空
p=Q[front];
k=level[front];
front++;//出队
if(p->lchild){
Q[rear]=p->lchild;
level[rear]=k+1;//新一层
rear++;//进队
}
if(p->rchild){
Q[rear]=p->rchild;
level[rear]=k+1;//新一层
rear++;//进队
}
}//level数组已经更新完成
//eg:123 三个元素构成的二叉树 level应为1 2 2
//统计宽度
int max=0,n,i=0;
k=1;
while(i<rear){
n=0;//层数初始化
while(i<rear&&level[i]==k){//统计每层个数
n++;
i++;
}
k++;
if(n>max){
max=n;//更新节点数
}
}
return max;//返回宽度
} -
判断二叉树是否为完全二叉树
//层次遍历全进栈,后判断null后是否全为null
int iscompete(bintree T){
if(T==NULL){//空树是完全二叉树
return 1;
}
Queue Q;
InitQueue(Q);
binode*p=T;
Enqueuq(Q,p);
while(!isempty(Q)){
Dequeu(Q,p);
if(p!=NULL){//全进队
Enqueuq(Q,p->lchild);
Enqueuq(Q,p->rchild);
}else{//当出现p==null时,判断后续是否存在null
while(!empty(Q)){
Pop(Q,p);
if(p==null){
return 0;
}
}
}
}
return 1;
} -
查找前序最后一个节点(样卷考过)
//递归
binode* lastnode(binTree T){//前序为根左右顺序,最后一个节点可能出现在根节点,右子树最优,或者左子树最右
if(T==NULL){
return NULL;
}
if(T->rchild==NULL&&T->lchild==NULL){
return T;
}else{
if(T->rchild){
return lastnode(T->rchild);
}else{
return lastnode(T->lchild);
}
}
}
//非递归
binode* lastnode(binTree T){
binode*p=T;
if(p){
while(p->rchild||p->lchild){
if(p->rchild){
p=p->rchild;
}else{
p=p->rchild;
}
}
}
return p;
} -
返回二叉树中序遍历中第一个/最后一个节点
//中序遍历第一个
bintree inorder_first(bintree T){//第一个出现在左子树最左,或者根
if(T&&T->lchild){
inorder_first(T->lchild);
}else{
return T;
}
}
//中序遍历最后一个
bintree inorder_first(bintree T){//最后一个出现在右子树最右或者根
if(T&&T->rchild){
inorder_first(T->rchild);
}else{
return T;
}
}
线索二叉树
//线索二叉树结构体定义 |
-
中序线索二叉树的创建与遍历(中序线索二叉树遍历为2017真题)
void Inthread(binTree &p,binTree &pre){//创建考的概率不大
if(p!==NULL){//改写中序遍历
Inthread(p->lchild);//递归遍历左子树
if(p->lchild==NULL){//左孩子为空需线索化
p->lchild=pre;//左孩子指向前驱
p->ltag=1;//改变标志位
}
if(pre&&pre->rchild==NULL){//pre不为空,且右孩子为空需要线索化
pre->rchild=p;
pre->rtag=1;
}
pre=p;//更新pre位置
Inthread(p->rchild);//递归遍历右子树
}
}
//中序线索二叉树遍历
binTree FirstNode(binTree T){//以T为中序遍历的第一个遍历节点
while(T->ltag==0){//有左孩子指向左孩子
T=T->lchild;
}
return T;//无左孩子则返回其位置
}
binTree NextNode(binTree T){//以T为中序遍历的后继
if(T->rtag==0){//有右孩子,返回右子树的第一个遍历节点
return FirstNode(T->rchild);
}else{//无右孩子则其就是后续
return T->rchild;
}
}
void inorder(binTree T){
for(binode*p=FirstNode(p);p!=NULL;p=NextNode(p)){
print("%c",p->data);//打印数据
}
} -
先序线索二叉树的创建与遍历
void prethread(binTree &p,binTree &pre){
if(p!==NULL){//改写先序遍历
if(p->lchild==NULL){//左孩子为空需线索化
p->lchild=pre;//左孩子指向前驱
p->ltag=1;//改变标志位
}
if(pre&&pre->rchild==NULL){//pre不为空,且右孩子为空需要线索化
pre->rchild=p;//pre节点的右指针指向p
pre->rtag=1;//改变标志位
}
pre=p;//更新pre位置
if(p->ltag==0){//根已线索化,递归遍历前需判断
prethread(p->lchild,pre);//左子树未线索化,递归遍历左子树
}
if(p->rtag==0){//右子树未线索化
prethread(p->rchild,pre);//递归遍历左子树
}
}
}
//先序线索二叉树遍历
binTree FirstNode(binTree T){//以T为中序遍历的第一个遍历节点
if(T->ltag==0){//有左孩子指向左孩子
return T->lchild;
}else{
return T->rchild;//无左孩子则指向右孩子或后续
}
}
void preorder(binTree T){
for(binode*p=T;p!=NULL;p=NextNode(p)){
print("%c",p->data);//打印数据
}
} -
后序线索二叉树的创建
void PostThread(binTree &p,binTree &pre){
if(p!==NULL){//改写后序遍历
PostThread(p->lchild,pre);//递归遍历左子树
PostThread(p->rchild,pre);//递归遍历右子树
if(p->lchild==NULL){//左孩子为空需线索化
p->lchild=pre;//左孩子指向前驱
p->ltag=1;//改变标志位
}
if(pre&&pre->rchild==NULL){//pre不为空,且右孩子为空需要线索化
pre->rchild=p;//pre节点的右指针指向p
pre->rtag=1;//改变标志位
}
pre=p;//更新pre位置
}
}
查找部分
-
顺序查找
int find(int a[],int len,int x){
for(int i=0,i<len;i++){
if(a[i]==x){
return i;
}
}
return 0;
} -
折半查找
void mid_search(int a[],int x,int len){
int low=0,high=len-1;
while(low<=high){
int mid=(low+high)/2;
if(a[mid]==x){
return mid;//查找成功
}else if(a[mid]>x){//查找数据在左半表
high=mid-1;
}else{//查找数据在右半表
low=mid+1;
}
}
return 0;//查找失败
}
//递归写法
void mid_search(int a[],int x,int low,int high){
if(low>high){
return 0;
}
int mid=(low+high)/2;
if(a[mid]>x){
return mid_search(a,x,low,mid-1);
}else if(a[mid]<x){
return mid_search(a,x,mid+1,high);
}else{
return mid;
}
}
二叉排序树
//二叉树排序树结构体定义 |
-
二叉排序表的创建
int BST_Insert(bstree &T,int x){
if(T==NULL){
T=(bsnode*)malloc(sizeof(bsnode));
T->data=x;
T->lchild=NULL;
T->rchild=NULL;
return 1;//插入成功
}else if(T->data==x){//重复不插入
return 0;
}else if(T->data>k){//大于k插入右子树
BST_Insert(T->rchild,int x)
}else{
BST_Insert(T->lchild,int x)//小于则插入左子树
}
}
void Creat_BST(bstree &T,int A[],int len){
T=NULL;
int i=0;
while(i<len){
BST_Insert(T,A[i]);//遍历数组的每一个元素
i++;
}
} -
在二叉排序树中查找值为x的节点
//非递归
bsnode* search_x(bstree T,int x){
while(T!=NULL){
if(T->data>x){//大于往左找
T=T->lchild;
}else if(T->data<x){//小于往右找
T=T->rchild;
}else{
return T;//找到
}
}
return NULL;//没找到
}
//递归
bsnode* search_x(bstree T,int x){
if(T==NULL){
return NULL;
}else{
if(T->data==x){
return T;
}else if(T->data<x){
return search_x(T->rchild,x);
}else{
return search_x(T->lchild,x);
}
}
} -
判断二叉树是否是二叉排序树
int pre=INI_MIN;//初始定义成一个很小的值,记录上一节点的值
int JudegBST(bstree T,int &pre){
int b1,b2;//接收左右子树是否为二叉排序树,是1 否0
if(T==NULL){//空树是二叉排序树
return 1;
}else{
b1=JudegBST(T->lchild,pre);
if(b1==0||T->data<=pre){//左子树返回0或者根小于左节点的最大值
return 0;
}
pre=T->data;//更新pre,记录节点数据值
b2=JudegBST(T->rchild,pre);//判断右子树
return b2;
}
} -
查找给定节点在二叉排序中的层次
int level(bstree T,binode*p){
int n=1;
while(T!=p){
if(T->data<p->data){//小于去右子树找
T=T->rchild;
}else{//大于去右子树找
T=T->lchild;
}
n++;//往下找层数+1
}
return n;//返回所在层数
} -
查找二叉排序树中的最大和最小元素
int Minkey(bstree T){//最小只可能在左边最左或者根
while(T->lchild!=NULL){
T=T->lchild;
}
return T->data
}
int Maxkey(bstree T){//最小只可能在右边最右或者根
while(T->rchild!=NULL){
T=T->rchild;
}
return T->data
}
排序部分
-
直接插入排序(重点,两种都考过)
//顺序存储
void Insert_Sort(ElemType A[], int len) {
int i, j;
for (i = 2; i <= len; ++i) {//遍历数组
if (A[i - 1] > A[i]) {//遍历元素小于前一个需要寻找插入位置
A[0] = A[i];//将遍历元素放到A[0]
for (j = i - 1; A[j] > A[0]; --j) {//寻找待排序元素插入位置
A[j + 1] = A[j];//将元素后移
}
A[j + 1] = A[0];//把待插入元素插入对应位置
}
}
}
//链式存储
typedef struct Lnode {
int data;
struct Lnode *next;
} Lnode, *LinkList;
void linklistsort(LinkList &l){
if (l->next== NULL){//空表
return;
}
Lnode *pre,*q,*p,*r;//pre和q遍历已排序节点,p和r遍历待排序节点
p=l->next->next;//后移到第二个数据节点
l->next->next= NULL;//断链
while (p){//p不为空时
pre=l;//初始化pre和q
q=pre->next;
while (q!= NULL&&p->data>q->data){//当q<p时,不后移
pre=q;
q=q->next;
}
r=p->next;//防断链指针
p->next=q;//插入有序链表中 q刚开始有可能为null,此刻p断链链接到有序序列
pre->next=p;
p=r;//更新p指针位置,指向下一个待排序节点
}
} -
折半插入排序(代码填空题考过)
void MidInsertSort(int A[], int n) {
int i, j, low, high, mid;
for (i = 2; i <= n; i++) {
A[0] = A[i];
low = 1, high = i - 1;//折半查找 找到插入位置 while循环结束时low为插入元素的位置
while (low <= high) {
mid = (low + high) / 2;
if (A[mid] > A[0]) {//左半表
high = mid - 1;
} else {//右半表
low = mid + 1;
}
}
for (j = i - 1; j >=low; --j) {//将插入位置后的元素后移一位
A[j + 1] = A[j];
}
}
A[low] = A[0];// 插入待排序元素
} -
希尔排序(要会模拟数组变化状态)
void ShellSort(ElemType A[], int n) {
int d, i, j;//d为增量
for (d= n / 2; d >= 1; d = d / 2) {//步长变化 初试d=n/2,后续减半
for (i = d + 1; i <= n; i++) {//以d为步长插入排序,核心还是插入排序
if (A[i] < A[i - d]) {//带排序元素小于上一个元素时需要插入排序
A[0] = A[i];//待排序元素复制到A[0]
for (j = i - d; j > 0 && A[0] < A[j]; j = j - d) {//寻找带排序元素插入位置
A[j + d] = A[j];//比待排序元素大的后移
}
A[j + d] = A[0];//插入待排序元素
}
}
}
} -
快速排序(重点)
int Partition(int arr[], int low, int high) {
int pivot = arr[low];//以第一个为基准
while (low < high) {//low<high时才有比较意义
while (low < high && arr[high] > pivot) {//从右往左找小于基准的元素
high--;
}//while循环结束表示找到arr[high]<pivot的值
arr[low] = arr[high];//把小于pivot的值移到右边
while (low < high && arr[low] <= pivot) {//从左往右找大于基准的元素
low++;
}//while循环结束表示找到arr[low]>pivot的值
arr[high] = arr[low];//把大于pivot的值移到左边
}
arr[high] = pivot;
return high;
}
void Quicksort(int A[], int low, int high) {
if (low < high) {
//分割左侧数组比分割点小,右侧都比分割点大
int pivot_pos = Partition(A, low, high);
//分割点前一半,继续分割排序
Quicksort(A, low, pivot_pos - 1);
//分割点后一半,继续分割排序
Quicksort(A, pivot_pos + 1, high);
}
} -
简单选择排序
void swap(int &a, int &b) {//交换两值
int temp=a;
a = b;
b = temp;
}
void Select_Sort(ElemType A[], int n) {
int i, j, min;
for (i = 0; i < n - 1; i++) {//最多n-1趟
min = i;//记录遍历过的最小值位置
for (j = i + 1; j < n; ++j) {//遍历剩余待排序元素
if (A[j] < A[min]) {
min = j;//找到最小值下标
}
swap(A[i], A[min]);//交换i的位置,即将小值放到前面了
}
}
} -
二路归并排序(不是很重要,要会模拟)
void Merge(int A[], int low, int mid, int high) {
int B[N];//辅助数组 降低操作次数
int i, j, k;
for (k = low; k <= high; k++) {//A中元素复制到B
B[k] = A[k];
}
for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
if (B[i] <= B[j]) {
//较小值复制到A中
A[k] = B[i++];//如果相等时,优先放置i指向的元素(保证稳定性)
} else {
A[k] = B[j++];
}
}
while (i <= mid) {//存在剩余元素,继续放入
A[k++] = B[i++];
}
while (j <= high) {
A[k++] = B[j++];
}
}
void MergeSort(int A[], int low, int high) {
if (low < high) {
int mid = (low + high) / 2;//分成左右两表
MergeSort(A, low, mid);//递归排序左表
MergeSort(A, mid + 1, high);//递归排序右表
Merge(A, low, mid, high);//全表归并
}
} -
冒泡排序
void swap(int &a, int &b) {//交换两值
int temp=a;
a = b;
b = temp;
}
void bubble_swap(int A[], int len) {
int flag;//记录是否存在交换
for (int i = 0; i < len - 1; ++i) {//最多进行n-1趟冒泡
flag = 0;//初始化flag
for (int j = len - 1; j > i; --j) {//遍历待排序元素进行冒泡
if (A[j - 1] > A[j]) {
swap(A[j - 1], A[j]);
flag = 1;
}
}
if (flag == 0) {//内层循环未发生交换,表示排序已经完成,直接退出排序
break;
}
}
}
//双向冒泡
void double_bubble_swap(int A[], int len) {
int flag=1;//记录是否存在交换
int low=0,high=len-1;
while(low<high&&flag==1){
flag=0;
for(int i=low,i<high;i++){
if(A[i]>A[i+1]){//大的后放
swap(A[i],A[i+1]);
flag=1;
}
}
high--;//for循环结束时,定好一个最大值
for(int j=high,i>low;j--){
if(A[j]<A[j-1]){//小的前放
swap(A[j],A[j-1]);
flag=1;
}
}
low--;//for循环结束时,定好一个最小值
}
} -
堆排序(代码填空题考过)
void swap(int &A, int &B) {//交换两值
int temp = A;
A = B;
B = temp;
}
void HeadJust(int A[], int k, int len) {
A[0] = A[k];//A[0]暂存调整元素
int i=2*k;//定义i初始化为左孩子位置
while(i<=n){
if(i<n&&A[i+1]>A[i]){//右大于左
i++;//索引到右孩子
}
if(A[i]>A[0]){//对比调整元素和较大的孩子的大小
A[k]=A[i];//孩子值大于调整元素,让孩子来到调整位置
k=i;//将较大孩子的位置做完下一次循环的调整位置
i=2*i;//更新索引i为下一次循环调整的左孩子索引
}else{//当i超过索引值,直接跳出循环,或者无需调整
break
}
}
A[k] = A[0];//调整元素放入最终位置
}
void BuildMaxHeap(ElemType A[], int len) {
for (int i = len / 2; i > 0; i--) {//从最后一个分支往上调整
HeadJust(A, i, len);
}
}
void HeapSort(ElemType A[], int len) {
BuildMaxHeap(A, len);//建大根堆
for (int i = len; i > 1; i--) {//n-1趟交换
swap(A[i], A[1]);//交换堆顶和堆底元素,输出堆顶
HeadJust(A, 1, i - 1);//重新调整
}
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 逆光海！
