数据结构代码题--排序算法（快排），二叉树的基本知识，链表的基本操作引申

发布于：2024-11-11 ⋅ 阅读:(79) ⋅ 点赞:(0)

排序算法：

完成比完美更重要！

题目中常考的是平均时间复杂度：但是具体计算时，能用最坏就用最坏

插入：直接插，希尔

交换：冒泡，快排

选择：简单选择，堆排

归并，二路归并，基数

为了高分，一般选择希尔，堆排，快排，但是堆排的代码不好写，希尔的复杂度不好分析，一般代码提只考虑快排

  • 什么时候用快排：
    • 顺序表，数组
    • 乱序数组，并且排序号有利于解决问题
//快速排序基本代码
int partition(int A[],int L,int R){
	int mid = A[L];
	while(L<R){
		while(A[R]>=mid) R--;//右指针从右往左移
		A[L] = A[R];//当<mid时，退出循环，和R交换位置
		while(A[L]<=mid) L++;
		A[R] = A[L];
	}
	A[L] = mid;
	return L;
}
void quick_sort(int A[],int L,int R)
{
	if(L >= R) return;
	int M = partition(A,L,R);
	quick_sort(A,L,M-1);
	quick_sort(A,M+1,R);
}


/*（1）折半查找（最优），顺序查找，归并排序，快速排序
本题采用快排：（1）两个数组合并成一个大数组
（2）对大数组进行排序（Qsort）
（3）找到中间元素
*/

int partition(int A[],int L,int R){
	int pivot = A[L];
	while(L<R){
		while(A[R]>=mid) R--;
		A[L] = A[R];
		while(A[L]<=mid) L--;
		A[R] = A[L];
	}
	mid = A[L];		
}

void Qsort_Judge(int A[],int L,int R){
	int M = partition(A,L,R);
	if(M==
	Qsort_Judge
}


（1），先将数组排序好
（2），找中间的元素，遍历数组，count中间元素的值
（3），如果count>2/n

Qsort(A,0,n-1);
int x = A[n/2];
for((int i = n/2-1,i>=0;i--){
	if(A[i] == x){
		count++;
		}
	}
	
	比较好的方法：投票算法：
	定义一个候选值candidata,一个count
	如果count == 0
  把第一个元素设置为candidat,
	遍历，如果下一个元素==candidate count++
	如果下一个元素 ！=candidate count--
	 for (int num : nums) {
        if (count == 0) {
            candidate = num;
            count = 1;
        } else if (num == candidate) {
            count++;
        } else {
            count--;
        }
    }


往快排上面想一下：
	（1）乱序，所以先利用快排排序
	（2）遍历找到第一个大于0的数
	（3）如果那个数>=2,那么结果就是1
	（4）如果那个数=1.让它往后遍历，同时定义一个m++,直到两者不相等
	(4ii) 或者，遍历，比较差值插值>2,就返回
	k 为第一个大于0的数组位置
	for(int m = k+1;m<n;m++){
		if(A[m] - A[m-1] >1)
			return A[m
	}

划分函数的意义：

  • 划分函数返回pivot在数组中的位置

  • 利用划分函数可以找到数组中第k小或者第k大的元素（如果划分结果是k)

  • 找到数组中更小的或者更大的k个元素（如果划分结果是k)

  • 把数组用划分为左右两个部分

  • 先利用一次划分返回值m

  • 如果k<m,对(0,m-1)的元素再次划分

利用划分函数找到数组中第k小的元素
int func(int A[],int n,int k){
	while(1){
		int M = partition(A,L,R);
		if(M==k-1) break;
		else if(M>k-1) R = M-1;
		eles if(M<k-1) L = M+1;
	}
return A[k-1];
}


利用划分函数找到数组中第k小的元素
int func(int A[],int n,int k){
	while(1){
		int M = partition(A,L,R);
		if(M==k) break;
		else if(M>k) R = M-1;
		eles if(M<k) L = M+1;
	}
return A[k-1];
}


利用划分的思想，找到第n/2的位置

二路归并函数思想运用（空间复杂度（O(n))

  • 什么时候用归并
    • 合并数组(有序的）
    • 合并好之后是有序的
  • 归并函数基本功
int Merge(int A[],int N,int B[],int M,int C[]){
	while(i<M&&j<N){
		if(A[i]<B[j]{
		C[k++] = A[i++];
		}
		if(B[j]<A[i]{
		C[k++] = B[j++];
		}
	//复制操作
		while(i<M){
			C[k++] = A[i++];
		}
		while(j<N){
		C[k++] = B[j++];
		}
		return 1;
}
	


(1)归并排序(O(logn))
(2)找（N+M)/2

链表算法题:灵活度低，回归基础

//定义单链表结点
typedef struct LNode{
	int data;
	struct LNode *next;
} LNode,*LinkList;

//求单链表的长度
int get_length(Linklist L){
	int length = 0;
	LNode * p = L->next;
	while(p!=NULL){
		length++;
		p = p->next;
	}
	cout<<"链表长度为"<<length<<endl;
	return length;
}

//返回单链表的中间结点
LNode getMidNode(LinkList L){
	int length = 0;
	LNode * p = L->next;
	while(p!=NULL){
		length++;
		p = p->next;
	}
	int n = p/2;
	return getnNode(L,n);
}

// 返回单链表第n个结点
LNode getnNode(LinkList L,int n){
	LNode *p = L->next;
	int count = 0;
	while(p!=NULL){
		count++;
		if(count==n)
			break;
			p = p->next;
	}
	return p;
}
// 倒数第k个结点：快慢指针，快指针先走k步，之后快指针和慢指针
再一起走

// 



1，分别计算str1,str2的长度m,n,以及他们的差值k
2，p指针从str1,开始向后走k步
3，q指针从str2开始，与p指针现在的位置共同走，边走边判断两者是
否相等

LNode getLastSameLetter(LinkList L1,LinkList L2){
	int m = get_length(L1);
	int n = get_length(L2);
	int k = m-n;
	int count = 0;
	if(k>=0){
		LNode *p = getnNode(L1,k);
		q = L2;
	}
	else{
		LNode *q = getnNode(L2,k);
		q = L1->next;
	}
	while(p!=NULL&&q!=NULL){
		if(p = q)
			break;
		p = p->next;
		q = q->next;
	}
	return p;
}

按关键字条件查找删除（前后指针）

删除操作，用双指针，删除p

void deleteX(LinkList L,int x){
	LNode pre = L->next;
	LNode p = pre->next;
	while(p!=NULL){
		if(p->data == x){
			LNode *q = p;
			p = p->next;
			q ->next = p;
			free(q);
		}
		else{
			pre = p;
			p = p->next;
		}
	}
}

插入操作，用双指针，插入x

在关键字递增有序的单链表中插入新的关键字，确保插入后单链表
递增有序
void insert（LinkList L,int x){
	LNode pre = L->next;
	Lnode p = pre -> next;
	LNode temp = new LNode(x,NULL);
	temp ->data =  x;
	while(p!=NULL){
		if(p->data >x){
			pre->next = temp;
			temp ->next = p;
		}
		else{
			pre = pre->next;
			p = p ->next;
		}
		if(p == NULL){
			pre ->next = temp;
		}
	}
}


1,需要找到绝对值相等的结点
2，需要双指针进行删除
3，如果题目中说时间复杂度尽可能高的算法，那么可以考虑空间换时
间，也就是，用一个数组进行记录，出现了多少次

void removeDuplicateNode(LinkList L,int a){
	int count[n+1];
	for(int i = 0;i<=n;i++){
		count[i] = 0;
	}
	LNode pre = L;
	LNode p = pre->next;
	while(p!=NULL){
		if(count[abs(p->data)]==0)
			count[abs(p->data)] = 1;
		else if(count[abs(p->data)]==1){
			LNode temp = p;
			p = p->next;
			pre->next = p;
			free(p);
		}
		pre = pre->next;
		p = pre->next;
	}
}

头插法：实现链表的原地逆置

尾插法：保持原顺序

尾插法

设置两个链表，与一个计数器

计数器为奇数采用尾插法进A

计数器为偶数采用头插法进B

设置两个链表头，与一个计数器

计数器<n/2的，把数据拆下来，采用尾插法进A

计数器>n/2的，把数据拆下来，采用头插法进B

在原始L，依次拆下来A,B，进入L

二叉树的算法题：

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

int treeHeight = 0;
int max(int a,int b){
	return ( a > b) ? a:b;
}

//前序遍历
void PreOrder(BiTree root,int depth){//n是第几层
	if(root == NULL) return;
	visit(root);
	treeHeight = max(treeHeight,depth);
	PreOrder(root->lchild,depth+1);
	PrePrder(root->rchild,depth+1);
}

//中序遍历
void InOrder(BiTree root){
	if(root == NULL) return;
	InOrder(root->lchild);
	visit(root);
	Inorder(root->rchild);
}

//后序遍历
int  PostOrder(BiTree root){
	if(root == NULL) return;
	int l = PostOrder(root->lchild);
	int r = PostPrder(root->rchild);
	cout<<"该树的平衡因子为"<<l-r<<endl;
	visit(root);
}

//层序遍历，由于要实现Q,大题代码一般不考，如果考了，直接用队列
void InitQueue(Queue &Q);
void EnQueue(Queue &Q,BiTNode *x);
void DeQueue(Queue &Q,BitNode *x);
bool IsEmpty(Queue &Q);
void levelOrder(BiTree T){
	Queue Q:
	InitQueue(Q);
	Bitree p;
	Enqueue(Q.T);
	while(!IsEmpty(Q)){
		Dequeue(Q,p);//让队头元素出列
		visit(p);//出队访问
		if(p->left !=NULL)
			EnQueue(Q,p->lchild);//
		if(p->right !=NULL)
			EnQueue(Q,p->right);
		}
	}
}

//求树的高度1(通过参数传递向下传递）
int TreeHeight = 0;
PreOrder(BiTree root ,int height){
	if(root ==NULL) return;
	visit(root);
	if(height >TreeHeight)
		TreeHeight = height;
	PreOrder(root->left,height+1);
	PreOrder(root->right,height+1);
}
PreeOrder(root,1)
	//求树的高度2（通过返回值）
PostOrder(BiTree root){
	if(root ==NULL) return;
	int l = PostOrder(root->left,height+1);
	int r = PostOrder(root->right,height+1);
	TreeHeight = ( l > r ) ? l : r;
	visit(root);
}
	
//求树的宽度：结点最多的那一层有多少结点
//最初想到的是层序，但是尽量用先中后
//利用先中后的参数或者返回值
//利用先序遍历作为代码的框架
int width[MAX];
void PreOrder(BiTree root,int level){//n是第几层
	if(root == NULL) return;
	width[level]++;
	PreOrder(root->lchild,depth+1);
	PrePrder(root->rchild,depth+1);
}
void treeWidth(BiTree T){
	for(int i = 0;i<MAX;i++)
		width[i] = 0;
	  PreOrder(root,0);
	  int maxWidth = 0;
		for(int i = 0;i<MAX;i++){
			if(width[i]>maxWidth)
				maxWidth = width[i];
		}
		cout<<"树的宽度是:"<<maxWidth;g
}

//求WPL（带权路径长）
1，找到叶子结点，没有子节点
2，向下传参
int WPL;
void PreOrder（BiTree T,int n){
	if(T==NULL) return;
	if(T->left==NULL&&T->right==NULL){
		WPL+=T->weight*n
	}
	PreOrder(root->lchild,depth+1);
	PrePrder(root->rchild,depth+1);
}
PreOrder(root,0);

//判断二叉排序树
中序遍历，判断递增
int temp = MIN_INT;//已经访问过的最大值
bool isBST = True;
void InOrder(BiTree root){
	if(root == NULL) return;
	InOrder(root->lchild);
	if(T->data >=temp) temp = T=>data;
	else isBST = False;
	Inorder(root->rchild);
}

//二叉树是否平衡
后续遍历返回树高
bool isBalance = true;
int  PostOrder(BiTree root){
	if(root == NULL) return;
	int l = PostOrder(root->lchild);
	int r = PostPrder(root->rchild);
	if(left-right>1) isBalance = False;
	if(left->righ<-1) isBalance = False;
	if(left >right) return left+1;
	else return right+1;
	visit(root);
}
//完全二叉树  
第一个不满的孩子是否是：有右但没左孩子
使用层序遍历
void InitQueue(Queue &Q);
void EnQueue(Queue &Q,BiTNode *x);
void DeQueue(Queue &Q,BitNode *x);
bool IsEmpty(Queue &Q);
void levelOrder(BiTree T){
	Queue Q:
	InitQueue(Q);
	Bitree p;
	Enqueue(Q.T);
	while(!IsEmpty(Q)){
		Dequeue(Q,p);//让队头元素出列
		visit(p);//出队访问
		if(p->left !=NULL)
			EnQueue(Q,p->lchild);//
		if(p->right !=NULL)
			EnQueue(Q,p->right);
		}
	}
}
bool isComplete = true;//判断是否为完全二叉树
bool flag = false;//flag = true表示层序遍历时出现
//过叶子或者只有左孩子的分枝结点
void visit（BiTNode *p){
	if(p->lchild==NULL&&p->rchild==NULL) flag = true;
//第一次访问到孩子缺失的结点
//如果是无左有右，可以判断一定不完全，
//如果是有左无右，此时还没没有办法判断，因为后续可能出现有问题的
//如果是无左无右，此时也没有办法判断，因为后续可能出现有问题的
//因此做个标记，表明后面不可以出现这两种情况，如果出现，那就是错的
		if(p->lchild == NULL &&p->rchild!=NULL) isComplete = flase;
	if(p->lchild!=NULL &&p->right==NULL{
		if(flag) isComplete = false;
		flag = true;
	}
	//前一步是为了判断这个结点是不是第二次出现
	//flag = true是判断，这个结点，是不是第一次出现，如果是第一次出现，也即是flag是falsa，
	//那就应当当做第一次出现来判断
	
	if(p->lchild!=NULL &&p->right!=NULL{
		if(flag) isComplete = false;
}
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布