874数据结构大题

链表

定义：

1
2
3
4
5
6
//链表的定义
typedef struct  Node
{
	int data;
	struct Node* next;
}Node, *LinkList;

2016年题1：查询链表倒数第K个数据

已知一个带有表头结点的单链表，结点结构为 data|link。假设该链表只给出了头指针 list（类型为 LinKlist）。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点（k 为正整数）。若查找成功，算法输出该结点的 data 值，并返回 1，否则，只返回 0

算法思想：由于单链表只能从头到尾依次访问链表的各个节点，所以如果要找链表的倒数第k个元素，也只能从头到尾进行遍历查找。在查找过程中，设置两个指针，让其中一个指针比另一个指针先前移k-1步，然后两个指针同时往前移动。循环直到先行的指针指为NULL时，另一个指针所指的位置就是所要找的位置，这样只需要一次遍历即可找到倒数第k个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int data;
    struct node *next;
} LinKlist;

// 找出单链表中的倒数第k个元素
int *search_last_k(LinKlist *head, int k)
{
    LinKlist *p1 = head;
    LinKlist *p2 = head;

    for (int i = 0; i < k; i++) {
        p2 = p2->next;
        if(p2==NULL)
        {
           return 0;    
        }
    }


    while (p2 != NULL) {
        p1 = p1->next;
        p2 = p2->next;
    }

    printf("%d",p1->data);
    return 1;

}

2017年题1：求两个链表的交集

有两个非空的整数集合 A.B，分别采用带头结点的单链表 ha 和 hb 存储，单链表中数据结点值的次序和对应集合的元素次序相同。单链表的结点类型如下

1
2
3
4
5
6
7
8
9
typedef struct node

{ 

int data;

Struct node *next;

}LinkNode;

现在求它们的交集，交集存放在带头结点的单链表 hc 中，完成以下算法设计，要求算法执行后不破坏原来的单链表，算法中给出适当的注释：

若两个集合的元素是递增有序的，设计对应的高效算法，给出算法的时间复杂度。

思路：釆用归并的思想，设置两个工作指针pa和pb，对两个链表进行归并扫描，只有同时出现在两集合中的元素才链接到结果表中且仅保留一个，其他的结点全部释放。当一个链表遍历完毕后，释放另一个表中剩下的全部结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
LinkList Union(LinkList &ha,LinkList &hb,LinkList hc) 
{
  LinkNode *pc=NULL;
  LinkNode *pa=ha->next;
  LinkNode *pb=hb->next;
  LinkNode *c_tail=(*hc);
  while(pa&&pb){
      if(pa->data>pb->data){
          pb=pb->next;
      }
      else if(pa->data<pb->data){
          pa=pa->next;
      }
      else
      {
        pc=(LinkNode*)malloc(sizeof(LinkNode*)); //开辟新链点pc
        pc->data=pa->data;           //处理pc数据域
        pc->next=NULL;             //处理pc指针域
        c_tail->next=pc;        //将pc挂到C的链尾
        c_tail=pc;
      }
     
  } 
  return hc;
}

时间复杂度：在ha，hb长度之间

2019年题2：链表相减

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相减，并以相同形式返回一个表示差的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

以下是两数相加的代码，关于两数相减的代码暂无

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //定义一个新联表伪指针，用来指向头指针，返回结果
        ListNode prev = new ListNode(0);
        
        int carry = 0;
        //定义一个可移动的指针，用来指向存储两个数之和的位置
        ListNode cur = prev;
        //当l1 不等于null或l2 不等于空时，就进入循环
        while(l1!=null || l2!=null){
            //如果l1 不等于null时，就取他的值，等于null时，就赋值0，保持两个链表具有相同的位数
            int x= l1 !=null ? l1.val : 0;
            //如果l1 不等于null时，就取他的值，等于null时，就赋值0，保持两个链表具有相同的位数
            int y = l2 !=null ? l2.val : 0;
            //将两个链表的值，进行相加，并加上进位数
            int sum = x + y + carry;
            //计算进位数
            carry = sum / 10;
            //计算两个数的和，此时排除超过10的请况（大于10，取余数）
            sum = sum % 10;
            //将求和数赋值给新链表的节点，
            //注意这个时候不能直接将sum赋值给cur.next = sum。这时候会报，类型不匹配。
            //所以这个时候要创一个新的节点，将值赋予节点
            cur.next = new ListNode(sum);
            //将新链表的节点后移
            cur = cur.next;
            //当链表l1不等于null的时候，将l1 的节点后移
            if(l1 !=null){
                l1 = l1.next;
            }
            //当链表l2 不等于null的时候，将l2的节点后移
            if(l2 !=null){
                l2 = l2.next;
            } 
        }
        //如果最后两个数，相加的时候有进位数的时候，就将进位数，赋予链表的新节点。
        //两数相加最多小于20，所以的的值最大只能时1
        if(carry == 1){
            cur.next = new ListNode(carry);
        }
        //返回链表的头节点
        return prev.next;
    }

栈

基础知识

1
2
3
4
typedef struct {
	int data[MaxSize];  //栈的最大值
	int top;             //栈顶指针
}SqStack;

2021年题2：设计中缀表达式转后缀表达式的算法

机算：

从左到右开始扫描中缀表达式，遇到数字， 直接输出
遇到运算符

  1. 若为“(” 直接入栈
  2. 若为“)” 将符号栈中的元素依次出栈并输出, 直到 “(“, “(“只出栈, 不输出
  3. 若为其他符号, 将符号栈中的元素依次出栈并输出, 直到遇到比当前符号优先级更低的符号或者”(“
    • 如果”+“or “-” 是当前符号，那么会将栈清空，或者遇到“（”
    • 如果“×”or “/” 是当前符号，那么会在遇到下一个“×”or “/” 时停止，或者遇到“（”
  4. 将当前符号入栈。扫描完后, 将栈中剩余符号依次输出

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/*中缀转后缀函数*/
void Change(SqStack *S,Elemtype str[])
{
	int i=0;
	Elemtype e;
	InitStack(S);  //初始化运算符栈
	while(str[i]!='\0')  //字符串未到末尾
	{
		while(isdigit(str[i]))  
		{/*过滤数字字符，直接输出，直到下一位不是数字字符打印空格跳出循环 */
			printf("%c",str[i++]);
			if(!isdigit(str[i]))
			{
				printf(" ");
			}
		}
		/*加减运算符优先级最低，如果栈顶元素为空则直接入栈，否则将栈中存储的运算符
		全部弹栈，如果遇到左括号则停止，将弹出的左括号从新压栈，因为左括号要和右括号
		匹配时弹出，这个后面单独讨论。弹出后将优先级低的运算符压入栈中*/
		if(str[i]=='+'||str[i]=='-')
		{
			if(!StackLength(S))        //判断栈是否为空
			{
				PushStack(S,str[i]);  
			}
			else
			{
				while( StackLength(S) && e != '(' )
				{
					PopStack(S,&e);   //出栈，将栈顶元素赋予e
					if(e=='(')
					{
						PushStack(S,e);
					}
					else
					{
						printf("%c ",e);
					}
				}
				
				PushStack(S,str[i]);
			}
		}
		/*当遇到右括号是，把括号里剩余的运算符弹出，直到匹配到左括号为止
		左括号只弹出不打印（右括号也不压栈）*/
		else if(str[i]==')')
		{
			PopStack(S,&e);
			while(e!='(')
			{
				printf("%c ",e);
				PopStack(S,&e);
			}
		}
		/*乘、除、左括号都是优先级高的，直接压栈*/
		else if(str[i]=='*'||str[i]=='/'||str[i]=='(')
		{
			PushStack(S,str[i]);
		}
		
		else if(str[i]=='\0')
		{
			break;
		}
		
		else
		{
			printf("\n输入格式错误！\n");
			return ;
		}
		i++;
	}
	/*最后把栈中剩余的运算符依次弹栈打印*/
	while(StackLength(S))
	{
		PopStack(S,&e);
		printf("%c ",e);
	}
}

再来几道题加强一下树的递归吧

  • 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}
  • 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}
  • 二叉树的最小深度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return 1;
        }

        int min_depth = Integer.MAX_VALUE;
        if (root.left != null) {
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        if (root.right != null) {
            min_depth = Math.min(minDepth(root.right), min_depth);
        }

        return min_depth + 1;
    }
}

树

基础知识

定义：

1
2
3
4
5
typedef struct BiTNode
{
    char data;
    struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;

递归遍历操作：

1
2
3
4
5
6
7
8
9
10
11
//二叉树的先序，中序，后序遍历(递归)
void PreOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
  //  printf("%c ", T->data);  先序
    PreOrderTraverse(T->lchild);
  //  printf("%c ", T->data);  中序
    PreOrderTraverse(T->rchild);
  //  printf("%c ", T->data);  后序
}

层序遍历&队列相关操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// 定义层次遍历中辅助队列的结构
typedef struct queue {
    BiTree data;
    struct queue* next;
}LinkNode,*PNODE;

// 定义辅助队列的队头队尾指针
typedef struct {
    LinkNode* front, * rear;
}LinkQueue,*PQUEUE;

// 初始化队列
void InitQueue(PQUEUE Q) {
    Q->front = Q->rear = (PNODE)malloc(sizeof(LinkNode)); 
    Q->front->next = NULL;
}

// 进队操作
void EnQueue(PQUEUE Q, BiTree x) {
    PNODE s = (PNODE)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q->rear->next = s;
    Q->rear = s;
}

// 出队操作
BiTree DeQueue(PQUEUE Q) {
    PNODE p = Q->front->next;
    if (Q->front == Q->rear)
        return NULL;
 
    Q->front->next = p->next;
    if (Q->rear == p)
        Q->rear = Q->front;

    return p->data;
}
// 层次遍历
void LevelOrder(BiTree T) {
    LinkQueue Q;
    InitQueue(&Q);
    BiTree p=NULL;
    EnQueue(&Q, T);
    while (Q.front!=Q.rear) {  //判断是否队空
        p=DeQueue(&Q);
        printf("%c ", p->data);
        if (p->lchild != NULL)
            EnQueue(&Q, p->lchild);
        if (p->rchild != NULL)
            EnQueue(&Q, p->rchild);
    }
}

2015年题2：输出根节点到指定结点的路径

思路：借助栈结构来保存路径上的结点，首先从根结点开始，一直往左找，如果左边找到就返回true；否则，如果左边找不到并且右子树不为空的情况下再继续往右子树找。如果左右子树都找不到，就弹出栈顶结点并返回false。方法运行完毕后，栈中保存的元素就是一条从根到给定结点的路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static boolean searchNode(TreeNode root,Stack<TreeNode> s,TreeNode node) {
        if(root == null) return false;
        s.push(root);
        if(root.val == node.val) return true;
        boolean b = false;
        //先去左子树找
        if(root.left != null) b = searchNode(root.left,s,node);
        //左子树找不到并且右子树不为空的情况下才去找
        if(!b && root.right != null) b = searchNode(root.right,s,node);
        //左右都找不到，弹出栈顶元素
        if(!b) s.pop();
        return b;
    }

2018年题2：求树的平衡因子

二叉树结点的平衡因子（bf）定义为该结点的左子树高度与右子树高度之差。

设二叉树结点结构为：(lchild,data,bf,rchild)，child，rchild 左右儿子指针；data 是数据元素；

bf 是平衡因子，编写递归算法计算二叉树中各个结点的平衡因子。

递归的计算每个节点的左子树与右子树的深度，然后左子树深度-右子树深度即为平衡因子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int Depth(BiTree T)
{
int l=0,r=0;
int *p;
p=T;          //p指向当前树T
if(p==NULL)
  return 0;
else
{
l=Depth(p->lchild);      //遍历左子树
r=Depth(p->rchild);        //遍历右子树
return (l>r?l:r)+1;       //左子树与右子树个数多的为当前树的深度
}
}
int bf(BiTree &T)
{
int LNum,RNum;     //记录左右子树的度
if(T)
{
 bf(T->lchild);       //从树的底部开始计算
 bf(T->rchild):
 LNum=Depth(T->lchild);      //当前节点左子树的度
 RNum=Depth(T->rchild);  //当前节点右子树的度
 T->bf=LNum-RNum;     //当前节点的平衡因子
}
}

2020年题1：打印二叉树的某一层

层数即level值，每递归一次将level值-1，减到1的时候就是该层

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void TransLevel(Node* root,int level)
{
    if(root == NULL)
        return ;
    else
    {
        if(level == 1)
           printf("%d ",root->data);
        else
        {
            TransLevel(root->left,level-1);
            TransLevel(root->right,level-1);
        }
    }
}

图

基础知识

邻接矩阵法

1
2
3
4
5
6
7
8
9
10
11
12
13
#define VertexMax 100 //最大顶点数为100
#define MaxInt 32767 //表示最大整数，表示 ∞
#define Maxsize 100 //队列最大元素个数100 

typedef char VertexType; //每个顶点数据类型为字符型
typedef  int dataType;

typedef struct
{
	char Vertex[100];//存放顶点元素的一维数组,VertexType表示元素的数据类型
	int AdjMatrix[100][100];//邻接矩阵二维数组 
	int vexnum, arcnum;//图的顶点数和边数
}MGraph;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//查找元素v在一维数组 Vertex[] 中的下标，并返回下标 
int LocateVex(MGraph* G, char v)
{
	int i;

	for (i = 0; i < G->vexnum; i++)
	{
		if (v == G->Vertex[i])
		{
			return i;
		}
	}

	printf("No Such Vertex!\n");
	return -1;
}
1
2
3
4
5
6
7
8
void FindInDegree(MGraph G){//计算图中各节点的入度
	int i,j;
	for(i = 0; i < G.vexnum; i ++){
		for(j = 0; j < G.vexnum; j ++)
			if(G.AdjMatrix[i][j])//当两顶点之间存在边时，入度自加
				indegree[j] ++;  //列表示入度
	}
}

邻接表法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef struct ArcNode//边表 
{
	int adjvex;//存储的是该边指向的边在顶点数组即AdjList[]中的位置  下标域
	struct ArcNode *next;  //指针域，用于连接后续结点
}ArcNode;

typedef struct VNode //单个顶点 
{
	 int vertex;  //数据域   
	//int weight；//存储网的时候需要添加此项
	struct ArcNode *firstarc;   //第一个孩子节点  指针域，用于连接边表
}VNode;

typedef struct //顶点表 
{
	VNode AdjList[VertexMax];//由顶点构成的结构体数组 
	int vexnum,arcnum; //顶点数n和边数e 
}ALGraph;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int indegree[MAX];//用来存储所有节点的入度之和

void FindInputDgeree(ALGraph G){//计算所有节点的入度
	ArcNode *p;   //临时边表变量
	int i;
 
	for(i = 0; i < G.vexnum; i ++)
		indegree[i] = 0;         //初始化入度数组
 
	for(i = 0; i < G.vexnum; i ++){
		p = G.AdjList[i].firstarc;    //p设置为顶点的第一条边
 
		while(p){            //如果边不为空
			indegree[p->adjvex] ++;  //顶点的对应位置的度+1
			p = p->next;
		}
	}
}

2016年题2：时间复杂度为O((V+E)logK)的最短路径算法

首先，朴素的迪杰斯特拉算法的时间复杂度为:$O(n^2)$，达不到题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
void ShortestPath_Dijkstra(MGraph *G,VertexType start)
{
	int i,j,num;
	int loc;
	int min;
	int dist[VertexMax];//最短路径长度数组 
	int path[VertexMax];//最短路径数组 
	int s[VertexMax];
    //代表集合S（1代表该顶点已处理，属于集合S；0代表该顶点未处理，不属于集合S，属于集合V-S） 
	
	//1.初始化dist和path数组 
	loc=LocateVex(G,start);//获取源点的下标位置 
	for(i=0;i<G->vexnum;i++)
	{
		dist[i]=G->AdjMatrix[loc][i];//初始化dist数组
		
		if(dist[i]!=MaxInt)//初始化path数组
		{
			path[i]=loc;
		}
		else
		{
			path[i]=-1;
		}	  
	} 
    
//2.初始化S数组(s数组：代表集合S，1代表该元素属于集合S(已处理的顶点),0该元素不属于集合S(未处理的顶点)) 
    for(i=0;i<G->vexnum;i++)
	{
		s[i]=0;
	} 
	s[loc]=1;//代表起始点(源点)以处理完毕 
	num=1;
	
	//3.
	while(num<G->vexnum)
	{
		min=FindMinDist(dist,s,G->vexnum);
        //在dist数组中查找其对应s[i]=0，即未处理的最小值元素 
		s[min]=1;//将找到的最短边所对应的的顶点加入集合S
		
		for(i=0;i<G->vexnum;i++)//加入新的顶点后，更新dist和path数组 
		{
			if((s[i]==0)&&(dist[i]>dist[min]+G->AdjMatrix[min][i]))//路径累加
			{
				dist[i]=dist[min]+G->AdjMatrix[min][i];
				path[i]=min;
			}
		}
	    num++;	
	}    
}

观察代码

在上述流程中，我们发现要想找到数组dist最小的节点，是需要O(n)的时间复杂度去遍历所有的点，而这一个操作也是朴素版dijkstra时间复杂度为$O(n^2)$的主要原因。

那么我们该如何优化它呢？很简单，我们可以维护一个堆，用堆来储存我们下一个需要用来更新的节点，取出堆顶元素的时间复杂度为$O(log_2n)$，是远快于遍历所有节点的，再用$O(log_2n)$遍历每一条边，时间复杂度为$O((n+m)log_2n)$

由于堆优化与边的数量有关，所以一般运用于稀疏图。

由于堆很难写，我们可以直接使用JAVA中的TreeMap数据结构，TreeMap会自动对Key值进行排序，所以每次更新dist的时候，用TreeMap可以提高效率，将原版那个耗时的for循环换成从优先队列中pop出dist值最小的顶点，其他一切照常

2017年题2：判断无向图是否有环

解法：有向图和无向图都可以用拓扑排序来判断是否有环,区别在于，无向图将度为0和1的结点压入栈，有向图将度为1的结点压入栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void TopologicalSort(MGraph G){
	FindInDegree(G);
	SqStack S;                //使用栈存储
	int i,j,count = 0;
	InitStack(S);           //初始化栈
 
	for(i = 0; i < G.vexnum; i ++)
		if(indegree[i]==0)
			Push(S,i);//把入度为零的节点压栈
     
	printf("拓扑序列如下:\n");
	while(!StackEmpty(S)){
		Pop(S,i);
		printf("%c\n",G.Vertex[i]);		
         count ++;
 
		for(j = 0; j < G.vexnum; j ++){
			if(G.AdjMatrix[i][j]！=0){
                indegree[j]--;       //删除出栈结点向对应的边，让其相邻结点的入度-1
				if(indegree[j]==0)   //如果入度为0，进栈
					Push(S,j);
			}
		}
	}
 
	if(count < G.vexnum)
		printf("此图有环存在!\n");
}

时间复杂度：邻接表：O(V+E) 邻接矩阵：O(V²)

2018年题1：求邻接表的入度

设有向图用邻接表表示，图有 n 个顶点，表示为 0 至 n-1，试写一个算法求顶点 k 的入度（0＜＝k＜n）

在拓扑排序中已经使用过了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int indegree[MAX];//用来存储所有节点的入度之和

void FindInputDgeree(ALGraph G){//计算所有节点的入度
	ArcNode *p;   //临时边表变量
	int i;
 
	for(i = 0; i < G.vexnum; i ++)
		indegree[i] = 0;         //初始化入度数组
 
	for(i = 0; i < G.vexnum; i ++){
		p = G.AdjList[i].firstarc;    //p设置为顶点的第一条边
 
		while(p){            //如果边不为空
			indegree[p->adjvex] ++;  //顶点的对应位置的度+1
			p = p->next;
		}
	}
}

2019年题1：深度遍历实现拓扑排序

按DFS的顺序，在出栈时输出，自然是逆拓扑排序，要实现拓扑排序，只需要再添加一个栈的结构，即可实现拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void DFS(MGraph* G, int i)
{
	int j;

	//1.处理起始点 

	visitedDFS[i] = 1;//2.将已访问的结点标志成1

	 //2.由起始点开始，对后续结点进行操作
	for (j = 0; j < G->vexnum; j++)//依次搜索vi的邻接点 
	{
		if (G->AdjMatrix[i][j] == 1 && visitedDFS[j] == 0)
            //当满足有边且未被访问过时，递归调用去查找该邻接点 
		{
			DFS(G, j);//注意此处的G已经是指针类型，不需要再&G 
		}
	}
    printf("%c", G->Vertex[i]);//逆拓扑排序，在出栈时输出 
}

2021题1：图中两点的途径

设计一个算法，找出带权图中是否存在点 i 到点 j 的途径，有的话是多长，该图由邻接矩阵表示，说明邻接矩阵的数据结构

迪杰斯特拉算法即可

排序

2020年题2：编写算法删除堆中一个元素

按照堆排序的思想，只需要将被删除元素与堆末尾元素换位，其他的按堆的调整即可

堆的调整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
void heapify(int* r, int dad, int end) //k~end为调整的范围 
{
	
	int ch = 2 * dad; //ch为dad的左孩子 

	while (ch <= end)
	{
		//让指针j选出左、右孩子中较大者 
		if (ch < end && r[ch] < r[ch + 1]) 
          //"lch<end"表示i还有右孩子 ,若右孩子大，则让指针j指向右孩子// 
		{
			ch++;
		}

//根节点与左、右孩子中的较大者 进行比较，进一步筛选出较大者，并将其换到根节点的位置上去 
		if (r[dad] < r[ch])
		{
			swap(&r[dad], &r[ch]);
		}
		//若发生了，则可能需要对其孩子进行二次调整 
		dad = ch;
		ch = 2 * dad;
	}
}

void heapSort(int r[], int n)
{
	int k;
	//构建堆：由下至上 （由第一个非叶子结点开始） 
	for (k = n / 2; k >= 1; k--)        // n/2即是由下到上的第一个非叶子结点
	{
		heapify(r, k, n);
	}

	//调整堆：由上至下 
	for (k = 1; k < n; k++)
	{
		//移走堆顶元素 
		swap(&r[1], &r[n - k +1]);  
        //r[1]是堆顶元素，即最大的元素，与堆最小的元素进行交换
		//调整堆 
		heapify(r, 1, n - k);        //每次都让堆顶元素出局，再重新构建堆
	}
}

假设删除元素为T，找到T的位置i，与堆底元素交换，有两种情况：

  1. 表尾元素>T，那么可能与T的父节点冲突，需要进行上浮操作
  2. 表尾元素<T，那么可能与T的子节点冲突，需要进行下沉操作

上浮：

1
2
3
4
5
6
7
8
9
10
11
12

void heap_increase_key(int a[],int i,int key)
{
 
	a[i] = key;
	while(i>1&& i/2 <a[i])
	{
		h_swap(a[i],a[i/2]);
		i=i/2;
	}
}

下沉：即常规的调整操作，dad即是t，end即是Length-1 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void heapify(int* r, int dad, int end) //k~end为调整的范围 
{
	int ch = 2 * dad; //ch为dad的左孩子 

	while (ch <= end)
	{
		//让指针j选出左、右孩子中较大者 
		if (ch < end && r[ch] < r[ch + 1]) 
          //"lch<end"表示i还有右孩子 ,若右孩子大，则让指针j指向右孩子// 
		{
			ch++;
		}

//根节点与左、右孩子中的较大者 进行比较，进一步筛选出较大者，并将其换到根节点的位置上去 
		if (r[dad] < r[ch])
		{
			swap(&r[dad], &r[ch]);
		}
		//若发生了，则可能需要对其孩子进行二次调整 
		dad = ch;
		ch = 2 * dad;
	}
}

2022：快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int Paritition1(int A[], int low, int high) {
   int pivot = A[low];    //选定low位置上的数作为枢轴，low空缺
   while (low < high) {
     while (low < high && A[high] >= pivot) { 
       --high;                 // 直到找到小于枢轴的数
     }  
     A[low] = A[high];         //把小于枢轴的数换到low的位置去，此时high空缺
     while (low < high && A[low] <= pivot) {
       ++low;                   // 直到找到大于枢轴的数
     }
     A[high] = A[low];        //把大于枢轴的数换到high的位置去，此时low空缺
   }
   A[low] = pivot;            //high=low时结束，此时将枢轴的值放到该中间位置
   return low;
 }

 void QuickSort(int A[], int low, int high) //快排母函数
 {
   if (low < high) {
     int pivot = Paritition1(A, low, high);
     QuickSort(A, low, pivot - 1);   //递归
     QuickSort(A, pivot + 1, high);
   }
 }