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

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

12


image.png


  • 有序表,直接循环扫描
  • 判断是否相等,相等直接删除,释放空间
  • 不等就下一个
  • 时间复杂度O(n),空间复杂度O(1)


void delSame(LinkList &L) {
  LNode *p = L->next, *del;
  while (p->next != NULL) {
    if (p->data == p->next->data) {
      del = p->next;
      p->next = del->next;
      free(del);
    } else {
      p = p->next;
    }
  }
}
复制代码


13

image.png


  • 经典合并链表!不过是两个递增合并为一个递减,头插即可
  • 因为哪哪都要用到头插,我们可以把它抽离成一个单独的函数使用
  • 遍历完后,肯定有一个链表有剩余元素,我们可以通过  if (pa == NULL) pa = pb; 节省步骤
  • 时间复杂度O(n),空间复杂度O(n)


// 头插
void headInsert(LinkList &L, int num) {
  LNode* node = (LNode *)malloc(sizeof(LNode));
  node->data = num;
  node->next = L->next;
  L->next = node;
}
LinkList mergeList(LinkList A, LinkList B) {
  // 1.创建一个新链表
  LNode* L = (LinkList)malloc(sizeof(LNode));
  L->next = NULL;
  // 2.遍历插入
  LNode *pa = A->next, *pb = B->next, *q;
  while (pa != NULL && pb != NULL) {
    if (pa->data < pb->data) {
      headInsert(L, pa->data);
      pa = pa->next;
    } else {
      headInsert(L, pb->data);
      pb = pb->next;
    }
  }
  // 3.处理剩余元素
  if (pa == NULL) pa = pb;
  while (pa != NULL) {
    headInsert(L, pa->data);
    pa = pa->next;
  }
  return L;
}
复制代码


14

image.png

  • 创建一个新链表C,找到公共元素尾插进去,每次只记录尾结点
  • 同时遍历A,B找出结点值相等的元素
  • 时间复杂度O(n),空间复杂度O(1)


LinkList getSame(LinkList A, LinkList B) {
  // 1.创建链表和指针
  LNode* C = (LinkList)malloc(sizeof(LNode));
  C->next = NULL;
  LNode *tail = C, *pa = A->next, *pb = B->next, *node;
  // 2.同步遍历
  while (pa != NULL && pb != NULL) {
    if (pa->data < pb->data) {
      pa = pa->next;
    } else if (pa->data > pb->data) {
      pb = pb->next;
    } else {
      // 3.相等就尾插进新链表
      node = (LNode*)malloc(sizeof(LNode));
      node->data = pa->data;
      tail->next = node;
      tail = node;
      // 4.继续向后扫描
      pa = pa->next;
      pb = pb->next;
    }
  }
  return C;
}


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

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