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

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

2.2.3, 6


image.png

  • 有序列表 ➡️ 相同元素排列在一起
  • 暴力,新开一个数组,将不同元素存入
  • 需要两个指针分别操作两个数组
  • 时间复杂度O(n),空间复杂度O(n)


void del_same(SqList &list) {
  if (list.length == 0) return;
  // 1.新开一个数组
  SqList copied = list;
  copied.data[0] = list.data[0];
  // 2.把不同元素存入
  int k = 0;
  for (int i = 1; i < list.length; i++) {
    if (list.data[k] != copied.data[i]) {
      copied.data[++k] = list.data[i];
    }
  }
  // 3.新换旧
  copied.length = k + 1;
  list = copied;
}
复制代码


  • 仔细想想,其实并不需要两个数组,双指针就可以
  • 前一个存储,后一个判断
  • 时间复杂度O(n),空间复杂度O(1)


void del_same2(SqList &list) {
  if (list.length == 0) return;
  int k = 0;
  for (int i = 1; i < list.length; i++) {
    if (list.data[k] != list.data[i]) {
      list.data[++k] = list.data[i];
    }
  }
  list.length = k + 1;
}
复制代码


2.2.4, 7


image.png

  • 这种题太典型了,合并有序顺序表以及合并有序链表,建议全文背诵hh
  • 循环,取下两个之中的较小的放入结果表中
  • 最后那个表还有剩余就把剩下的部分全部加入结果表
  • 时间复杂度O(n),空间复杂度O(n)


SqList merge(SqList A, SqList B) {
  SqList C;
  if (A.length + B.length > MaxSize) {
    cout << "ERROR!" << endl;
    return C;
  }
  int i = 0, j = 0, k = 0;
  // 1.两两比较,小的存入结果表
  while (i < A.length && j < B.length) {
    if (A.data[i] <= B.data[j])
      C.data[k++] = A.data[i++];
    else
      C.data[k++] = B.data[j++];
  }
  // 2.剩下的全部加入结果表,两个循环只会有一个运行
  while (i < A.length) 
    C.data[k++] = A.data[i++];
  while (i < B.length) 
    C.data[k++] = B.data[j++];
  // 3.返回结果表
  C.length = k;
  return C;
}
复制代码
  • 补充一下归并排序


void merge_sort(int l, int r) {
  if (l >= r) return;
  int mid = (l+r) >> 1;
  merge_sort(l, mid);
  merge_sort(mid+1, r);   
  int k = 0, i = l, j = mid+1;
  while (i <= mid && j <= r) {
    if (q[i] <= q[j]) 
      tmp[k++] = q[i++];
    else 
      tmp[k++] = q[j++];
  }
  while (i <= mid) 
    tmp[k++] = q[i++];
  while (j <= r) 
    tmp[k++] = q[j++];
  for (i = l, j = 0; i <= r; i++, j++) 
    q[i++] = tmp[j++];
}


目录
打赏
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助理

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