408王道数据结构课后代码习题(一)

简介: 408王道数据结构课后代码习题(一)

顺序表结构体


考试直接使用,一般不会让你写出结构体


#define MaxSize 50
typedef struct {
  ElemType data[MaxSize];
  int length;
}SqList; 
复制代码


2.2.3, 1


image.png


  • 暴力解法一般就是循环,循环一次不行,就来两次,两次不行三次 ...
  • 时间复杂度 O(n),空间复杂度O(1)


int del_min(SqList &list) {
  if (list.length == 0) {
    cout << "Error!" << endl;
    return -1;
  }
  // 1.假设0号元素最小
  int min = list.data[0]; 
  int pos = 0;
  // 2.循环找出最小元素并记录位置, 从1开始
  for (int i = 1; i < list.length; i++) {
    if (list.data[i] < min) {
      min = list.data[i];
      pos = i;
    }
  }
  // 3.删除最小元素并用最后一个元素替换
  list.data[pos] = list.data[list.length - 1];
  list.length--; 
  return min;
}
复制代码


2.2.3, 2


image.png


  • 暴力就是再整一个数组,原数组从末尾循环遍历放到新数组里
  • 要求空间复杂度O(1)的话,从头循环到中间,交换头尾元素
  • 偶数或者奇数个元素,循环到中间,都是 < length/2,因为如果长度为4或者5,都是循环到下标为1即停,为5的时候最中间的元素(下标为2)不需要移动。
  • 时间复杂度O(n),空间复杂度O(1)


void reverse(SqList &list) {
  for (int i = 0; i < list.length / 2; i++) {
    // 不让用swap()的话,可以定义一个辅助变量来交换
    swap(list.data[i], list.data[list.length - 1 - i]);
  }
}
复制代码


2.2.3, 3


image.png


  • 暴力就是再整一个数组,循环遍历把不等于x的元素都放入新数组
  • 时间复杂度O(n),空间复杂度O(1)就要求一次循环内解决
  • 把所有等于x的元素都扔到最后,然后 length 减掉就可以了
  • 反向:也就是把所有不等于x的元素扔到前面,后面自然就是等于x的元素了


void del_x(SqList &list, int x) {
  int k = 0;
  for (int i = 0 ; i < list.length ; i++) {
    // 1.把所有要保存的值都放在前面
    if (list.data[i] != x) {
      list.data[k++] = list.data[i];
    }
  }
  // 2.直接扔掉后面的元素
  list.length = k;
}
复制代码


  • 一次循环 -> 双指针
  • 类似快排,从两端向中间移动,将左边的x与右边的非x交换


// 太麻烦了,不如上一个方法
void del_x_2(SqList &list, int x) {
  int i = -1, j = list.length, k = 0;
  while (i < j) {
    while (list.data[++i] != x); 
    while (list.data[--j] == x) k++;
    if (i < j) {
      swap(list.data[i], list.data[j]);
      k++;
    }
  }
  list.length -= k;
}


目录
打赏
0
0
0
0
7
分享
相关文章
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
144 77
|
1月前
|
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
61 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【C++数据结构——图】最短路径(头歌教学实验平台习题) 【合集】
任务描述 本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。 相关知识 为了完成本关任务,你需要掌握:Dijkst本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。为了完成本关任务,你需要掌握:Dijkstra算法。带权有向图:该图对应的二维数组如下所示:Dijkstra算法:Dijkstra算法是指给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径。Dijkstra算法的具体步骤如下:(1)初始时,S只包含源点,即S={v},v的距离为0。
63 15
|
1月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
49 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
47 10
|
1月前
|
【C++数据结构——图】最小生成树(头歌实践教学平台习题) 【合集】
【数据结构——图】最小生成树(头歌实践教学平台习题)目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:【合集】任务描述 本关任务:编写一个程序求图的最小生成树。相关知识 为了完成本关任务,你需要掌握:1.建立邻接矩阵,2.Prim算法。建立邻接矩阵 上述带权无向图对应的二维数组,根据它建立邻接矩阵,如图1建立下列邻接矩阵。注意:INF表示无穷大,表示整数:32767 intA[MAXV][MAXV];Prim算法 普里姆(Prim)算法是一种构造性算法,从候选边中挑
45 10
|
1月前
|
【C++数据结构——图】图的邻接矩阵和邻接表的存储(头歌实践教学平台习题)【合集】
本任务要求编写程序实现图的邻接矩阵和邻接表的存储。需掌握带权有向图、图的邻接矩阵及邻接表的概念。邻接矩阵用于表示顶点间的连接关系,邻接表则通过链表结构存储图信息。测试输入为图的顶点数、边数及邻接矩阵,预期输出为Prim算法求解结果。通关代码提供了完整的C++实现,包括输入、构建和打印邻接矩阵与邻接表的功能。
50 10
|
3月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
336 9
|
3月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
55 1
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等