数据结构 高阶算法的应用
算法分析和解题的一般套路
- 算法解法
- 暴力解 :枚举解法
- 可行解 :目标解法
- 最优解 :缘分解法
- 算法解题得分套路
- 结构体定义
- 算法思想和算法步骤
- 算法实现 注释
- 算法复杂度分析:时间复杂度和空间复杂度
线性表的高阶应用
1.双指针策略
- 一块,一慢 距离缩短
- 一早,一晚 距离固定
- 一左,一右
3.单链表或数组逆序
- 单链表: 头插法 [头逆尾顺]
每次将原先链表的每个结点头插法插入到原来单链表的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;
}
- 数组: 数字逆置-对位交换
- 全部数组
- 数组中一部分 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.单链表或数组旋转
- 借助分段逆置实现 ab-> b逆a逆 ->ba 线性代数矩阵逆置
- 搜索旋转排序数组 有序--->二分法 分界点
- 给定一个链表和一个特定值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;
}
- 链表旋转
给定一个链表,进行旋转链表的操作,将链表中每个结点向右移动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);
}
二叉树的应用
- 求二叉树中叶子的个数:先序遍历
- 求二叉树的高度: 后序遍历
- 求二叉树的宽度:(各层结点个数的最大值) 层次遍历
- 交换二叉树的左、右子树 先序遍历、后序遍历
- 二叉树的最小深度 后序遍历
- 对称树 先序遍历、后序遍历
图
深度优先
广度优先
图的应用
- 假设图采用邻接表表示,采用深度优先遍历和广度优先遍历,判断结点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;
}
广度优先方法同深度优先方法
- 假设图用邻接表表示,设计一个算法,判断无向图是否是连通图。
深度优先方法:设置一个全局的数组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;
}
-
拓扑排序
-
已知某图的邻接矩阵为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;
}
排序算法
- 单链表实现快排
将第一个链表的第一个结点的值作为左轴,然后向右进行遍历,设置一个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);
}
- 基数排序
二叉排序树
- 设计算法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;
}
- 给定一个二叉树,判断其是否是一个有效的二叉排序树
假设一个二叉搜索树具有如下特征:
- 结点的左子树只包含小于当前结点的数
- 结点的右子树只包含大于当前结点的数
- 所有左子树和右子树自身必须也是二叉排序树
//链表
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