首页 > 编程语言 > 数据结构(借鉴408)-高阶算法的应用

数据结构(借鉴408)-高阶算法的应用

时间：2023-02-26 23:55:06浏览次数：39  
标签：结点 return int data head next 数据结构 高阶 408

数据结构 高阶算法的应用

算法分析和解题的一般套路

  1. 算法解法
  • 暴力解 ：枚举解法
  • 可行解 ：目标解法
  • 最优解 ：缘分解法
  1. 算法解题得分套路
  • 结构体定义
  • 算法思想和算法步骤
  • 算法实现 注释
  • 算法复杂度分析：时间复杂度和空间复杂度

线性表的高阶应用

1.双指针策略

  1. 一块，一慢 距离缩短
  2. 一早，一晚 距离固定
  3. 一左，一右

3.单链表或数组逆序

  1. 单链表： 头插法 [头逆尾顺]
    每次将原先链表的每个结点头插法插入到原来单链表的head后。
ListNode *reverseList(ListNode *head){

	ListNode *tmp = NULL;
	ListNode *cur = NULL;
	if(!head) return NULL;
	cur = head->next;
	while(cur){
		tmp = cur->next;
		cur->next = tmp->next;
		tmp->next = head->next;
		head->next = tmp;
	}
	return head;

}
  1. 数组： 数字逆置-对位交换
  • 全部数组
  • 数组中一部分 s+i -- e-i i=0,1,...,e-s/2
void revers(SqList &L){
	ElemType x；
	for(i=0; i<L.length/2; i++){
		x = L.data[i];
		L.data[i] = L.data[L.length -i-1];
		L.data[L.length -i-1] = x;
	}
}

4.单链表或数组旋转

  1. 借助分段逆置实现 ab-> b逆a逆 ->ba 线性代数矩阵逆置
  2. 搜索旋转排序数组 有序--->二分法 分界点
  3. 给定一个链表和一个特定值x，对链表进行分隔，使得所有小于x的结点都在大于或等于x的结点之前。应当暴力两个分区中 每个结点的初始相对位置。
    局部排序。首先找到第一个大于或等于给定值的结点，然后每找到一个小于特定值的点取出置于其之前。
ListNode *partition(ListNode *head, int x){
	ListNode *dummy = new ListNoe(-1);
	dummy->next = head;
	ListNode *pre = dummy, *cur = head;
	while(pre->next && pre->next->val < x)
		pre = pre->next;
	cur = pre;
	while(cur->next){
		if(cur->next->val < x){
			ListNode *tmp = cur->next;
			cur->next = tmp->next;
			tmp->next = pre->next;
			pre->next = tmp;
			pre = pre->next; 
		}
		else{
			cur = cur->next;
		}
	}
	return dummy->next;
}
  1. 链表旋转
    给定一个链表，进行旋转链表的操作，将链表中每个结点向右移动k个位置，其中k是非负数。

解析：

  • 用快慢指针。快指针先走k步，然后两个指针同时移动，当快指针到末尾时，慢指针的下一个位置时新的顺序的头结点。 当原链表为空时，直接返回NULL。当k大于链表长度和k远远大于链表长度时：首先需要遍历一遍原链表 得到链表长度n，然后k对n取余。
  • 一个指针。原理：先遍历真个链表获得链表长度n，然后把链表头和尾链接起来，再往后走 n-k%n 个结点就到达新链表的头结点前一个点，这时断开链表即可。
//单个指针
ListNode *rotateRight(ListNode *head, int k){
	if(!head) return NULL;
	int n = 1;
	ListNode *cur = head;
	while(cur->next){    //链表长度
		++n;
		cur = cur->next;
	}
	cur->next = head;   //构成环
	int m =  n-k%n;
	for(int i=0; i<m; ++i){
		cur = cur->next;
	}
	ListNode *newhead = cur->next;
	cur->next = NULL;
	return newhead;
}

二叉树

二叉链表结点。 有3个域：一个数据域，两个分别指向左右子结点的指针域

typedef struct BTNode{
	ElemType data;
	struct BTNode *Lchild,*Rchild;
}BTNode;

先序遍历

总分结构

//递归
void recursionPreorderTraversal(TreeNode root){
	if(root != null){
		printf(root.val + "");
		recursionPreorderTraversal(root->left);
		recursionPreorderTraversal(root->right);
	}
}

中序遍历

BST 表达式（中缀）

//递归
void recursionPreorderTraversal(TreeNode root){
	if(root != null){
		recursionPreorderTraversal(root->left);
		printf(root.val + "");
		recursionPreorderTraversal(root->right);
	}
}

后序遍历

分总结构

//递归
void recursionPreorderTraversal(TreeNode root){
	if(root != null){
		recursionPreorderTraversal(root->left);
		recursionPreorderTraversal(root->right);
		printf(root.val + "");
	}
}

层次遍历

层次遍历，需要设置一个队列，初始化时为空
设T是指向根结点的指针变量，若二叉树为空，则返回；否则，令p=T，p入队。
1.队首元素出队到p。
2.访问p所指向的结点。
3.将p所指向的结点的左、右子结点依次入队，直到队空为止。

void LevelOrder(queue<Node *> & nodeQueue){
	if(nodeQueue.empty()) return;
	
	Node *frontNode = nodeQueue.front(); 
	cout<<frontNode->element<<"";
	nodeQueue.pop();
	if(frontNode->lChild != NULL)
		nodeQueue.push(frontNode->lChild);
	if(frontNode->rChild != NULL)
		nodeQueue.push(frontNode->rChild);
	LevelOrder(nodeQueue);
}

二叉树的应用

  1. 求二叉树中叶子的个数：先序遍历
  2. 求二叉树的高度： 后序遍历
  3. 求二叉树的宽度：(各层结点个数的最大值) 层次遍历
  4. 交换二叉树的左、右子树 先序遍历、后序遍历
  5. 二叉树的最小深度 后序遍历
  6. 对称树 先序遍历、后序遍历

图

深度优先

广度优先

图的应用

  1. 假设图采用邻接表表示，采用深度优先遍历和广度优先遍历，判断结点i和结点j之间是否存在路径。

深度优先方法：设置一个全局的数组visitd[]用于存储定点的访问情况，初始化全是0，并且用0表示没有访问过，用1表示访问过。当采用深度优先遍历方式时，若从i出发，遍历结束时，如果visited[j]=1,表示结点i和结点j之间有路径；否则没有路径。

Int visited[MaxVetex];
bool DFSMethod(Graph G, int i, int j){
	memset(visited, 0, sizeof(visited));
	DFS(G, i);
	if(visited[j] == 0) return false;
	else return true;
}

广度优先方法同深度优先方法

  1. 假设图用邻接表表示，设计一个算法，判断无向图是否是连通图。

深度优先方法：设置一个全局的数组visitd[]用于存储定点的访问情况，初始化全是0，并且用0表示没有访问过，用1表示访问过。当采用深度优先遍历方式时，若从i出发，遍历结束时，只存在结点j，如果visited[j]=0，表示不是连通图。

Int visited[MaxVetex];
bool DFSMethod(Graph G, int i, int j){
	memset(visited, 0, sizeof(visited));
	bool flag = true;
	DFS(G, i);
	for(int i=0; i<G->num ; i++){
		if(visited[j] == 0){
			flag = false;
			break;		
		}
	}
	return flag;
}

广度优先方法同深度优先方法

3.假设图采用邻接表表示，设计一个算法，求解距离结点U最远的结点V。
图采用邻接表表示，采用广度优先搜索，从结点U出发，最后一层的顶点距离U比较远，特别地，最后一层的最后一个结点一定是最远的。

int visited[MaxVertex];
int maxDist(Graph G, int U){
	ArcNode *p;
	int queue[MaxVertex], front = rear=0, j, k;
	rear++;
	queue[rear]=U;
	visited[U] =1；
	while(rear != front){
		front = (front+1) % MaxVertex;
		V = queue[front];
		p = V->adjList[V].firstArc;
		while(p!= NULL){      //BFS
			j = p->adjvex;
			if(visited[j] == 0){
				visited[j] = 1;
				rear = (rear +1 ) % MaxVertex;
				queue[rear] = j;
			}
			p = p->nextArc;
		}
	}
	return V;
}

  1. 拓扑排序

  2. 已知某图的邻接矩阵为A，若从顶点i到顶点j有边，则A[i,j]=1;否则A[i,j]=0。试编写一算法求矩阵A的传递包C，使得若从顶点i到顶点j有一条或多条路径，则C[i,j]=1;否则C[i,j]=0。
    typedef int adjmatrix[maxvtxnum][maxvtxnum];
    void Change(adjmatrix A, adjmatrix C, int n);

分析：
首先，若从顶点i与顶点j存在直接路径，则顶点i，j联通；若顶点i存在到顶点k的路径，而顶点k存在到顶点j的路径，则顶点i，j同样联通，表达式为 C[i][j] = C[i][j] or (C[i][k] and C[k][j]) //C为传递包
用3层循环遍历即可求出传递包C，描述如下：
for 间接通过每个结点k
for 每个结点i
for 每个结点j
C[i][j] = C[i][j] or (C[i][k] and C[k][j])

void Change(adjmatrix A, adjmatrix C, int n){
	for(int i=0; i!=n; ++i){
		for(int j=0; j!=n; ++j){
			C[i][j] = A[i][j]; // 将C初始化为邻接矩阵
		}
	}
	for(int k=0; k!=n; ++k){
		for(int i=0; i!=n; ++i){
			for(int j=0; j!=n; ++j){
			//结点i间接通过结点k是否和结点j联通
				return C[i][j] = C[i][j] or (C[i][k] and C[k][j]);
			}
		}
	}
}
//时间复杂度O(n^3)

其他高阶应用

哈希查找

除留余数法和链地址解决冲突

typedef struct{  //元素类型
	keytype key;
	char info[20];
}elemtype
typedef struct hnode{  //哈希表链结点类型
	elemtype data;
	hnode *next;
}hnode, *head

初始化、插入、删除

typedef head HT[100]; //HT为哈希表类型

void InitHT(HT ht, int n);
void InsertHT(HT ht, int n, elemtype x);
bool SearchHT{Ht ht, int n, elemtype x)；
int DeleteHT(HT ht, int n, keytype K);//成功1，失败0

//初始化
void Init(HT ht, int n){
	for(int i=0; i<n; i++){
		ht[i]->next = NULL;
	}
}


//插入
void InsertHT(HT ht, int n, elemtype x){
	head newnode = (List)malloc(sizeof(struct ListNode));
	head p,pre;
	if(!newnode){
		printf("Insufficient memory\n");
		return;
	}

	newnode->data = x;
	if(ht[x.key % n]){  //该链条不为空
		for(p=ht[x.key%n]; p!=NULL; pre=p, p=p->next){
			if(p->data.key == x.key) break;
		}

		newnode->next = pre->next;
		pre->next = newnode;
	}
	else{
		ht[x.key%n] = newnode;
		newnode->next = NULL;
	}
}

//查找
bool SearchHT{Ht ht, int n, elemtype x){
	head p,pre;
	if(ht[x.key % n]){  //该条链表不为空
		for(p=ht[x.key%n]; p!=NULL; pre=p, p=p->next){
			if(p->data.key == x.key) 
				return true;
			return false;
	}
	else{			//该条链表为空
		return false;
	}
}


//删除
int DeleteHT(HT ht, int n, keytype K){
	head p,pre，tmp;
	if(ht[x.key % n]){  //该条链表不为空
		for(p=ht[x.key%n]; p!=NULL; pre=p, p=p->next){
			if(p->data.key == x.key){
				tmp = p;
				pre->next = p->next;
				free(tmp);
				return 1;
			}
	}
	return 0;
}

排序算法

  1. 单链表实现快排
    将第一个链表的第一个结点的值作为左轴，然后向右进行遍历，设置一个small指针指向左轴的下一个元素，最后比较。如果比左轴小，那么使small指针指向的数据与遍历到的数据进行交换，最后将左轴元素与small指针指向的元素交换即可。之后就是递归。
void quicksort(Linklist head, LinkList end){
	//如果头指针为空或链表为空，直接返回
	if(head == NULL || head == end) 
		return ;
	int t;
	Linklist p = head->next;  //用来遍历的指针
	Linklist small = head；
	while(p != end){
		if(p->data < head->data){  //将小于轴的元素放在左边
			small = small->next;
			t = small->data;
			small->data = p->data;
			p->data = t;
		}
		p = p->next;
	}
	t = head->data;				//遍历完后，对左轴元素与small指向的元素交换
	head->data = small->data;
	small->data = t;
	quicksort(head, small);      //对左、右进行递归
	quicksort(small->next, end);

}
  1. 基数排序

二叉排序树

  1. 设计算法SearchInsert。 在一棵非空二叉排序树上查找元素值为e的结点，若该结点存在，则返回其指针；若该结点不存在，则插入元素为e的新结点，并返回新结点的指针。
typedef struct{
	int key;
	char info[10];
}elemtype;
typedef struct node{
	elemtype data;
	node *lchild, *rchild;
}node, *bitptr;

//bitptr Search_Insert(bitptr T, elemtype e)
node *Search_Insert(bitptr root, int e){
	node *p, *f, *new;
	p=root, f=root;
	while(p!=NULL){
		f=p;
		if(p->data.key == e) break;
		else if((p->data).key > e) p = p->lchild;
		else p = p->rchild;
	}

	if(p == NULL){
		new = (node*)malloc(sizeof(node));
		new->lchild = NULL;
		new->rchild = NULL;
		(new->data).key = e;

		if((f->data).key > e) f->lchild = new;
		else f->rchild = new;
		
		p = new;
	}
	return p;
}
  1. 给定一个二叉树，判断其是否是一个有效的二叉排序树

假设一个二叉搜索树具有如下特征：

  • 结点的左子树只包含小于当前结点的数
  • 结点的右子树只包含大于当前结点的数
  • 所有左子树和右子树自身必须也是二叉排序树
//链表
int IsSearchTree(const Bitree *t){  //递归遍历二叉树是否为二叉排序树
	if(!t) 			//空二叉树情况
		return 1;  
	else if(!(t->lchild) && !(t->rchild)) //左、右子树都没有情况
		return 1；
	else if((t->lchild) && !(t->rchild))  //只有左子树情况
	{
		if(t->lchild->data > t->data)
			return 0;
		else
			return IsSearchTree(t->lchild);
	}
	else if(!(t->lchild) && (t->rchild))  //只有右子树情况
	{
		if(t->rchild->data < t->data)
			return 0;
		else
			return IsSearchTree(t->rchild);
	}
	else  //左、右子树全有情况
	{
		if(t->lchild->data > t->data  || t->rchild->data < t->data)
			return 0;
		else
			return(IsSearchTree(t->lchild) && IsSearchTree(t->rchild));
	}

}

//数组
(a[i] < a[i/2])&&(a[i] > a[2i])&&(a[i] < a[2i+1])

标签：结点,return,int,data,head,next,数据结构,高阶,408
From： https://www.cnblogs.com/yongchao/p/17158271.html

相关文章

  • [数据结构] 单链表
    一、C语言实现1.1结构体定义typedefintElementType;//定义一个链表结构体structListNode{ElementTypeval;structListNode*next;};1.2相关方法......
  • 数据结构与算法概述
     一、数据结构与算法简介从广义上讲，数据结构是指一组数据的存储结构。算法是操作数据的一组方法。从狭义上讲，数据结构与算法是指某些著名的数据结构和算法，比如数组、列......
  • 02_03_Java语音进阶||day03_数据结构（集合相关）、List、Set、可变参数、Collections工具
    第一章数据结构1.1数据结构的作用Java是面向对象的语音，好似自动挡汽车，c语音手动挡，数据结构？数据结构：是变速箱的工作原理。你完全可以不懂变速箱怎样工作，就可以把自动挡车从......
  • 数据结构(借鉴408)-数组
    数据结构数组1.多维数组的存储2.特殊矩阵(数组)的压缩存储3.数组的应用定义与地址计算数组是由n(n>1)个具有相同数据类型的数据元素a1,a2,...,an组成的有序序列，且该......
  • 数据结构（严蔚敏版）——第一章《绪论》
    第一章绪论1.1、基本概念1.1.1、数据、数据元素、数据项、数据对象数据（Data）：是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。数值型数据......
  • Java刷题常用的数据结构总结
    (Java刷题常用的数据结构总结)1.基础运算//int型相关操作Integer.INT_MAX;//int型最大值Integer.INT_MIN;//int型最小值longname;//注意：没有c语言里面的longlong(i......
  • 数据结构(借鉴408)-排序
    数据结构排序分冶稳定性时间复杂度空间复杂度1.插入类排序直接插入排序折半插入排序希尔排序分组(间距d--)，直接插入排序2.交换类排序起泡排序快速排序......
  • Java刷题常用的数据结构总结
    目录1.基础运算2.字符串类3.数组类与链表4.栈和队列5.字典类6.树1.基础运算//int型相关操作Integer.INT_MAX;//int型最大值Integer.INT_MIN;//int型最小值long......
  • 数据结构与算法【基础版】：4.10 线索二叉树的概述
    线索二叉树有：前序线索化二叉树，中序线索化二叉树，后序线索化二叉树概述起因：无法知道二叉树中某一个叶子节点的前一个值是什么，也不能知道后一个是什么值最后一行的叶子节点存......
  • 数据结构与算法【基础版】：4.9 常用排序算法之堆排序（属于选择排序）【简单选择排序在3.6
    堆排序大顶堆：父节点始终大于任意子节点小顶堆：任意一个子节点都比父节点大思路：先找到最后一个非叶子节点，即最后一个节点的父节点和他的左右节点比较，左右节点大的情况和父节点......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99