-
顺序表之有序顺序表重复元素删除
2020-06-16 21:12:37思路:例SqList L = { 1, 2, 2, 3, 4, 4 },将每一个元素与之后面的元素进行比较,1与2比较不相等不做任何处理,1再次与2比较不做任何处理,1与3比较不做任何处理…1与之后面的所有元素比较不做任何处理;2与2比较,...(2.2.4-6)从有序顺序表中删除所有其值重复的元素,使表中所有元素的值均不同。
思路:例SqList L = { 1, 2, 2, 3, 4, 4 },将每一个元素与之后面的元素进行比较,1与2比较不相等不做任何处理,1再次与2比较不做任何处理,1与3比较不做任何处理…1与之后面的所有元素比较不做任何处理;2与2比较,相同第2个2删除即需要将之后的元素向前移动,3需要向前移动1步(即此轮(即内层循环的重复数)遍历的重复次数),后面的两个4需要向前移动1步;后面同理。内层每次比较完应该更新length为length-此轮重复次数。
代码如下:void Delete_Same(SqList &L){ //删除有序表重复值 for(int i=0;i<L.length;i++) { int same=0; for(int j=i+1;j<L.length;j++){ if (L.data[i] == L.data[j]) { same++; } else{ L.data[j-same]=L.data[j]; } } L.length=L.length-same; } }
思路(转自https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/solution/shan-chu-pai-xu-shu-zu-zhong-de-zhong-fu-yuan-su-y/):
使用快慢双指针法 分别定义指针i与指针j,开始两指针都指向num[0],
快指针i向前移动 指向的数组与 慢指针j所知数组比较 num【j】!=num【i】
若相同则快指针向前移动一格,慢指针向前移动一格;若不同,将快指针i指向数组赋值给慢指针j,快慢指针分别向前移动一格;重复操作直到i指针指到末尾。
若数组长度为0则直接return 0;
最后 返回慢指针所指数组长度加一 return j+1。class Solution { public: int removeDuplicates(vector<int>& nums) { int i,j; int length=nums.size(); if(length==0)//判断数组长度 若为0直接返回 return 0; for (i=0;i<nums.size();i++)//采用for循环使指针i不停向前移动 { if(nums[i]!=nums[j]) { if(i-j>1) //判断快慢指针 若相邻数组且元素值不同时,虽然也可进行赋值操作, //但可以省略该赋值操作,避免无意义操作提高运行效率 {nums[j+1]=nums[i];} j++; } } return j+1; } };
-
自学笔记之C++(5) --数据的插入与删除
2020-05-25 16:14:36如在一个递增和排列数组a中插入一个数x,使其仍然有序 思路: 查找应该放置的位置k 从最后一个数开始直到第k个元素为止,每一个元素下标向后移动一个位置 将x插入k位置 步骤2要从最后一个元素开始移动 for(i = n -...插入元素
如在一个递增和排列数组a中插入一个数x,使其仍然有序
思路:- 查找应该放置的位置k
- 从最后一个数开始直到第k个元素为止,每一个元素下标向后移动一个位置
- 将x插入k位置
步骤2要从最后一个元素开始移动
for(i = n - 1 ; i > = k ; i - - )
a[ i + 1] = a [ i ]代码实现
#define N 10 #include <iostream> using namespace std; int main() { int a[N], i, k, n, x; cout << "递增输入现有的元素个数:"; cin >> n; for (i = 0; i < n; i++) cin >> a[i]; cout << "要插入的元素:"; cin >> x; for (i = 0; i < n; i++) if (x < a[i]) break; k = i; for (i = n - 1; i >= k; i--) a[i + 1] = a[i]; a[k] = x; for (i = 0; i < n + 1; i++) cout << a[i] << " "; return 0; }
删除元素
思路:
- 找到该元素的位置k
- 找到后删除,然后从第k+1位依次向前移
- 若没找到提示“未找到”
代码实现
#define N 10 #include <iostream> using namespace std; int main() { int a[N], i, k, x, n; cout << "输入现有数组中元素的个数为:"; cin >> n; for (i = 0; i < n; i++) cin >> a[i]; cout << "输入要删除的数为:"; cin >> x; for (i = 0; i < n; i++) if (x == a[i]) break; k = i; for (i = k; i < n; i++) a[i] = a[i + 1]; for (i = 0; i < n - 1; i++) cout << a[i] << " "; }
-
数据结构之顺序表(数组)
2015-03-12 17:38:512. 设计一个算法从顺序表中删除重复的元素,并使剩余元素间的相对次序保持不变 3. 设计一高效算法删除顺序表中值为x的所有元素 代码如下: 写惯了JAVA,Python,要注意C语言没法动态构建数组,必须先申请数组空间,...本学期带数据结构,那就索性复习下C语言,把所写的代码记录下来
题目如下:
1. 两个有序的顺序表A和B,包含的元素个数分别为m与n,设计一算法实现B=AUB 2. 设计一个算法从顺序表中删除重复的元素,并使剩余元素间的相对次序保持不变 3. 设计一高效算法删除顺序表中值为x的所有元素
代码如下:
</pre><pre class="cpp" name="code">写惯了JAVA,Python,要注意C语言没法动态构建数组,必须先申请数组空间,其次声明要写在最前面。
#include <stdio.h> #include <stdlib.h> #define len 100 //数组长度 #define endflag -99 //结束标记 //获得数组,返回长度 int getArray(int *p){ int length =0; int i = 0; for(scanf("%d",&i);i!=endflag;scanf("%d",&i)) { *p++ = i; length++; } return length; } //输出数组 void printArray(int *p, int length){ int i; printf("数组:"); for(i=0;i<length;i++) printf("%d ",*(p+i)); printf("\n"); } //有序数组的并集 int ArrayUnion(int *a,int A_len,int *b,int B_len,int *out){ int *p,pLen,aLen,bLen; p = out; pLen = aLen = bLen = 0; while(aLen != A_len && bLen != B_len){ if(aLen < A_len && bLen < B_len){ if(*a > *b){ *p = *b; b++;bLen++; }else if(*a == *b){ *p = *b; a++;b++; aLen++;bLen++; }else{ *p = *a; a++;aLen++; } p++;pLen++; } if(aLen<A_len && bLen == B_len){ *p = *a; a++;aLen++; p++;pLen++; } if(aLen==A_len && bLen < B_len){ *p = *b; b++;bLen++; p++;pLen++; } } return pLen; } // 删除数组的第k个元素 int ArrayDelElem(int *arr,int length,int k){ int i; if(k>length) return 0; for(i=k;i<length;i++){ arr[i] = arr[i+1]; } return length - 1 ; } //删除数组中的j-k个元素 int ArrayDelRange(int *arr,int length,int j,int k){ int i,range; range = k-j; if(k>length) return 0; for(i=j;i<length - range;i++){ arr[i] = arr[i+range+1]; } return length - range - 1 ; } //顺序表去重复,返回数组长度 int distinct(int *arr,int length){ int i,k,reLen; k = 1; //去除元素的个数 reLen = length; for(i=0;i<length - k ;i++){ if(arr[i] == arr[i+1]){ reLen = ArrayDelElem(arr,reLen,i+1); k++; i--; //抵消++的作用,从这个数继续往下比 } } return reLen; } //删除顺序表中所有值为X的元素 int ArrayDelX(int *arr,int length,int x){ int i,PreIndex,AfterIndex; for(i=1;i<length;i++){ if(arr[i-1] < x){ if(arr[i] == x) PreIndex = i; }else if(arr[i-1] == x){ if(arr[i] > x){ AfterIndex = i-1; break; } } } return ArrayDelRange(arr,length,PreIndex,AfterIndex); } int main() { int A[len],A_len; printf("请输入数组A,输入%d结束:\n",endflag); A_len = getArray(A); //A_len = distinct(A,A_len); //第二题 A_len = ArrayDelX(A,A_len,2); //第三题 printArray(A,A_len); /*//第一题 int *out,k[2*len],A_len,B_len,outlen; int A[len],B[len]; out = k; printf("请输入数组A,输入%d结束:\n",endflag); A_len = getArray(A); printf("请输入数组B,输入%d结束:\n",endflag); B_len = getArray(B); outlen = ArrayUnion(A,A_len,B,B_len,out); printArray(out,outlen); */ return 0; }
-
归并排序的理解
2018-03-23 20:29:24归并排序是一个对递归和分治很好诠释的一个排序算法它是将一个无序的数组依次分开使之变为有序的数组,如果我们一直将其分解到一个数组中只有一个数,那么我们就可以理解为他是有序的,然后再将这些有序的数组依次...归并排序是一个对递归和分治很好诠释的一个排序算法
它是将一个无序的数组依次分开使之变为有序的数组,如果我们一直将其分解到一个数组中只有一个数,那么我们就可以理解为他是有序的,然后再将这些有序的数组依次合并成一个数组,至于如何合并就很简单了,我们只需要比较第一个数字,哪个数组的数字大就选取哪个数组的,然后把第一个数字拿到新的数组中,然后删除原数组中的值,依次比较,如果其中一个数组空了,那么我们就将另一个数组全部拿到新数组中,这样我们就可以得到一个有序的新数组,依次合并最终完成排序,举一个例子就很好理解。
(23,12,5,76,32,87,34,11)这里他是一个无序的数组,我们先把他进行分解
(23,12,5,76)(32,87,34,11)--->(23,12) (5,76)(32,87) (34,11)
(23)(12)(5)(76)(32)(87)(34)(11)此时出现的8个数组都可以视为有序的
然后依次进行合并
(12,23)(5,76)(32,87)(11,34)-->(5,12,23,76)(11,32,34,87)
最终变为(5,11,12,23,32,34,76,87)完成排序
代码如下
public class MergeSort { public static void merge(int[] a, int low, int mid, int high) { int i = low;// 定义左指针 int j = mid + 1;// 定义右指针 int k = 0; int[] temp = new int[high - low + 1]; while (i <= mid && j <= high) { if (a[i] < a[j]) { temp[k++] = a[i++]; } else { temp[k++] = a[j++]; } } // 把左边剩余的数移入数组 while (i <= mid) { temp[k++] = a[i++]; } // 把右边边剩余的数移入数组 while (j <= high) { temp[k++] = a[j++]; } // 把新数组中的数覆盖nums数组 for (int k2 = 0; k2 < temp.length; k2++) { a[k2 + low] = temp[k2]; } } public static void mergeSort(int[] a, int low, int high) { int mid = (low + high) / 2; if (low < high) { // 对左边进行分解 mergeSort(a, low, mid); // 对右边进行分解 mergeSort(a, mid + 1, high); // 左右进行归并 merge(a, low, mid, high); System.out.println(Arrays.toString(a)); } } public static void main(String[] args) { int a[] = { 23,12,5,76,32,87,34,11}; mergeSort(a, 0, a.length - 1); System.out.println("排序结果:" + Arrays.toString(a)); } }
-
数据结构与算法·实验二
2017-10-03 16:27:292、从键盘输入一个数,查找在以上创建的单链表中是否存在该数;如果存在,显示它的位置;如果不存在,给出相应提示。 3、删除上述单链表中指定的元素。 *4、把单链表进行排序,使之成为一个有序的单链表。 #... -
数据结构报告c++代码+截图
2018-08-05 13:44:13实验一 线性表的有关操作………………………………………………………………………4 ...左右两边全是1,从第二行起,中间的每一个数是上一行里相邻两个数之和。输入要打印的层数n,打印出相应的杨辉三角形。 -
面试题13:在O(1)时间删除链表结点:当要删除的结点不是尾结点而且不是仅有一个结点的头结点,可以把该结点i的下一个结点j的内容复制到结点i,同时把i结点的next指向j结点的next,然后再删除结点j。如果要删除的链表...
-
3.4.8 找出数组中出现次数超过一半的数,现在有一个数组,已知一个数出现的次数超过了一半,请用O(n)的复杂度的算法找出这个数。 3.4.9 找出被修改过的数字 3.5.0 设计DNS服务器中cache的数据结构。要求设计一个...
-
算法分析与设计习题集答案
2014-07-13 15:40:0212、 已知一个顺序表中的元素按元素值非递减有序排列,编写一个函数删除表中多余的值相同的元素。 13、 分别写出求二叉树结点总数及叶子总数的算法。 分治术 14、 有金币15枚,已知其中有一枚是假的,而且它的重量... -
判断一个栈是否是另一个栈的弹出序列 测试22 第二十三题 层序遍历二叉树 测试23 第二十四题 后序遍历二叉搜索树 测试24 第二十五题 二叉树中和为某值的路径 测试25 第二十六题 复杂链表的复制 测试26 第二...
-
版本控制的系统中都少不了diff的功能,即展示一个文件内容的增加与删除。 GFM中可以显示的展示diff效果。使用绿色表示新增,红色表示删除。 语法 其语法与代码高亮类似,只是在三个反引号后面写diff, 并且其内容中...
-
版本控制的系统中都少不了diff的功能,即展示一个文件内容的增加与删除。 GFM中可以显示的展示diff效果。使用绿色表示新增,红色表示删除。 语法 其语法与代码高亮类似,只是在三个反引号后面写diff, 并且其内容中...
-
上海电机学院C语言实训答案
2012-01-22 15:28:32输入一个正整数n (1),再输入n 个整数,将最小值与第一个数交换,最大值与最后一个数交换,然后输出交换后的n 个数。 (25)抓住肇事者 一辆卡车违反交通规则,撞人后逃跑。现场共有三个目击者,但都没有记住车号,... -
《数据结构 1800题》
2012-12-27 16:52:03①以下是该函数的程序段,请将未完成的部分填入,使之完整 int f(m,n) int m,n; { if(m==1) return (1) ; if(n==1){ return (2) ;} if(m) {return f(m,m);} if (m==n) {return 1+ (3) ;} return f(m.n-1)... -
1186. 删除一次得到子数组最大和 1218. 最长定差子序列 1227. 飞机座位分配概率 1261. 在受污染的二叉树中查找元素 1262. 可被三整除的最大和 1297. 子串的最大出现次数 1310. 子数组异或查询 1334. ...
-
数据结构实验
2012-04-13 09:55:47如何计算一个三元组表表示的稀疏矩阵对角线元素之和以及两个三元组表表示的稀疏矩阵的乘积? 实验5:二叉树的建立及遍历 (第十三周星期三7、8节) 一 、实验目的 1.学会实现二叉树结点结构和对二叉树的基本操作。... -
数据结构(C++)有关练习题
2008-01-02 11:27:18D. *建立函数create:根据一维数组a[n]建立一个单链表,使单链表中各元素的次序与a[n]中各元素的次序相同,要求该程序的时间复杂度为O(n)。 E. *整理函数tideup:在非递减有序的单链表中删除值相同的多余... -
数据结构演示软件
2013-06-02 21:32:36(2)删除顺序表中一个数据元素(del_sqlist) (3)合并两个有序顺序表(merge_sqlist) 2. 链表 (1)创建一个单链表(Crt_LinkList) (2)在单链表中插入一个结点(Ins_LinkList) (3)删除单链表中的一个结点... -
用C编写班级成绩管理系统
2009-06-18 19:32:07然后用链表把它们组成一个有序的整体。用对链表的操作来实现对所有学生信息的统一管理(成绩显示、成绩排序、成绩修改等)。最后为了以后按照处理后的顺序保存到文件中。 . 各函数的功能: 概要设计: 程序的模块... -
计算机二级公共基础知识
2011-04-30 14:00:09退队运算是从队列的队头删除一个数据元素。 队列的顺序存储结构一般采用队列循环的形式。循环队列s=0表示队列空;s=1且front=rear表示队列满。计算循环队列的元素个数:“尾指针减头指针”,若为负数,再加其容量... -
用c描述的数据结构演示软件
2012-07-24 13:31:25(2)删除顺序表中一个数据元素(del_sqlist) (3)合并两个有序顺序表(merge_sqlist) 2. 链表 (1)创建一个单链表(Crt_LinkList) (2)在单链表中插入一个结点(Ins_LinkList) (3)删除单链表中的一个结点... -
软件测试规范
2018-04-23 09:16:12一.概述 ............................................................................................................................................................ 1 二 软件测试理论 .................... -
二叉排序树与平衡二叉树的实现
2010-12-26 15:25:31每当插入一个新结点时,首先检查是否因插入新结点而破坏了二叉排序树的平衡性,若是,则找出其中的最小不平衡子树,在保持二叉排序树特性的前提下,调整最小不平衡子树中各结点之间的链接关系,进行相应的旋转,使之... -
数据结构题
2012-12-27 16:58:403.对关键字序列(72,87,61,23,94,16,05,58)进行堆排序,使之按关键字递减次序排列。请写出排序过程中得到的初始堆和前三趟的序列状态。 初始堆:_94,87,。。。_______ 第1趟:{94},87,72,61,58,23,16... -
upload ols
2020-12-26 12:57:18社区通过制定奖励机制、任务机制、信用评级机制等在线网红服务需求方与网红服务供给方之间建立的一个有序、公平、共享生态环境,共同营造网红生态链的健康发展。 美推网创始团队均来自于国际知名网红经纪公司... -
世界500强面试题.pdf
2019-11-01 14:33:261.3.9. 左移递减数列查找某一个数................................................................ 60 1.3.10. 对于一个整数矩阵,存在一种运算,对矩阵中任意元素加一时,需要其相 邻(上下左右)某一个元素也... -
oracle学习文档 笔记 全面 深刻 详细 通俗易懂 doc word格式 清晰 连接字符串
2017-05-06 20:26:52说明:Oracle中要删除一个用户,必须要具有dba的权限。而且不能删除当前用户,如果删除的用户有数据对象,那么必须加上关键字cascade。 用法:drop user 用户名 [cascade] 四、 用户权限与角色 1. 权限 Oracle中权限... -
收获不知Oracle
2018-08-07 14:23:175.2.1.7 活用三特征之索引有序248 5.2.1.8 不可不说的主外键设计265 5.2.1.9 组合索引高效设计要领272 5.2.1.10变换角度看索引的危害289 5.2.1.11如何合理控制索引数量295 5.2.2 位图索引的玫瑰花之刺 297 5.2.2.1 ... -
导师计划--数据结构和算法系列(上)
2020-12-09 04:46:22线性结构是一个有序数据元素的集合。它应该满足下面的特征: <ul><li>集合中必存在唯一的一个“第一个元素”</li><li>集合中必存在唯一的一个“最后的元素”</li><li>除最后一元素之外,其它数据元素均... -
Visual C++开发实战1200例(第1卷).(清华出版.刘锐宁.梁水.李伟明).part1
2016-06-16 01:35:39实例058 求一个正整数的所有因子 实例059 一元钱兑换方案 2.6 趣味计算 实例060 加油站加油 实例061 买苹果问题 实例062 猴子吃桃 实例063 老师分糖果 实例064 新同学的年龄 实例065 百钱买百鸡问题 实例...