精华内容
下载资源
问答
  • 还有几天就要考数据结构了,复习的时候,不,是预习的时候深刻体会到了sqx老师的一句话:出来混,迟早要还的。...这里我解释一下输入时多个0是因为创建A B 链表的时候需要一个flag标识符来中止插入链表。 ...

    还有几天就要考数据结构了,复习的时候,不,是预习的时候深刻体会到了sqx老师的一句话:出来混,迟早要还的。 所以我开始还了 (55555)
    先还一个链表这里的简单操作叭。。。。

    源代码如下:

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    运行结果如下:
    在这里插入图片描述
    在这里我解释一下输入时多个0是因为在创建A B 链表的时候需要一个flag标识符来中止插入链表。

    展开全文
  • 合并有序链表

    2020-09-04 10:41:56
    合并有序链表 1、参考资料 https://www.nowcoder.com/practice/a479a3f0c4554867b35356e0d57cf03d ...遍历的过程中,我们将元素值小的节点依次链 mergerList 的后边,最后,我们看看哪个链表还有剩余的节

    合并有序链表

    1、参考资料

    https://www.nowcoder.com/practice/a479a3f0c4554867b35356e0d57cf03d

    2、题目要求

    将两个有序的链表合并为一个新链表,要求新的链表是通过拼接两个链表的节点来生成的,即不开辟新的内存空间

    3、代码思路

    首先,为了方便操作链表,我们定义一个 dummyHead,我们遍历两个链表,直到其中有一个到达尾部,则停下来

    在遍历的过程中,我们将元素值小的节点依次链在 mergerList 的后边,最后,我们看看哪个链表还有剩余的节点,将其链在 mergeList 的后边,最后返回合并链表的首节点

    4、代码实现

    代码

    static class Solution {
        /**
         * 合并两个有序链表
         *
         * @param list1 ListNode类
         * @param list2 ListNode类
         * @return ListNode类
         */
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode dummyHead = new ListNode(0); // 合并后链表的头结点
            ListNode mergeListPointer = dummyHead; // 合并链表的指针
            ListNode list1Poniter = list1; // list1 的指针
            ListNode list2Poniter = list2; // list2 的指针
    
            // 任意一个链表到尾部,则停止循环
            while (list1Poniter != null && list2Poniter != null) {
                // 将小的元素接到 mergeList 的后面
                if (list1Poniter.val < list2Poniter.val) {
                    mergeListPointer.next = list1Poniter;
                    list1Poniter = list1Poniter.next; // 指针后移
                } else {
                    mergeListPointer.next = list2Poniter;
                    list2Poniter = list2Poniter.next; // 指针后移
                }
                mergeListPointer = mergeListPointer.next; // 指针后移
            }
            // 看看哪个链表还有剩余的部分,将它接在 mergeList 的后面
            if (list1Poniter != null) {
                mergeListPointer.next = list1Poniter;
            } else {
                mergeListPointer.next = list2Poniter;
            }
            // 返回合并后链表的首结点
            return dummyHead.next;
        }
    }
    
    
    static class ListNode {
        int val;
        ListNode next = null;
    
        public ListNode(int val) {
            this.val = val;
        }
    }
    
    展开全文
  • 有序表查找

    2020-03-13 23:43:51
    有序表查找 一、二分查找(折半查找) 线性表中的数据必须是关键码有序(一般从小到大排列),且线性表必须采用顺序存储。 基本思想:将给定值与中间值进行比较,若小于中间值则左半区继续比较,若大于中间值,则...

    有序表查找

    一、二分查找(折半查找)
    线性表中的数据必须是关键码有序(一般从小到大排列),且线性表必须采用顺序存储。
    基本思想:将给定值与中间值进行比较,若小于中间值则在左半区继续比较,若大于中间值,则在右半区进行比较,一直重复,直到中间值等于给定值。或者所有查找区域无记录,查找失败为止。

    int Binary_Search(int * a, int n, int key)
    {
    	int low = 1, high = n, mid;
    	while(low <= high)
    	{
    		mid = (low + high)/2;
    		if (key < a[mid])
    		{
    			high = mid - 1;
    		}
    		else if (key > a[mid])
    		{
    			low = mid + 1;
    		}
    		else
    		{
    			return mid;
    		}
    	} 
    	return 0;
    }
    

    二、插值查找
    思想与二分查找相同,只是折的位置不同,更适用于大规模均匀的数据

    int Binary_Search(int * a, int n, int key)
    {
    	int low = 1, high = n, mid;
    	while(low <= high)
    	{
    		mid = (high - low)*(key - a[low])/(a[high] - a[low]); //插值
    		if (key < a[mid])
    		{
    			high = mid - 1;
    		}
    		else if (key > a[mid])
    		{
    			low = mid + 1;
    		}
    		else
    		{
    			return mid;
    		}
    	} 
    	return 0;
    }
    

    三、斐波那契查找
    思想:还是二分查找的思想,区别还是在于折的位置的不同
    它利用了黄金分割的原理,如下图是斐波那契数列。
    在这里插入图片描述

    int Fibonacci_Search(int * a , int n, int key)
    {
    	int low, high, mid, i, k;
    	low = 1;
    	high = n;
    	k = 0;
    	while(n > F[k] - 1)
    	{
    		k++;              //计算n在数列中的位置
    	}
    	for (i = n; n <  F[k] -1; i++)
    	{	
    		a[i] = a[n];       //将要查找的数列补齐,这一步很重要,不然有可能会在查找的过程中溢出。
    	}
    	while(low <= high)
    	{
    			mid = low + F[k-1] - 1;
    			if (key < a[mid])
    			{
    				high  = mid - 1;  //
    				k = k - 1;   //数列下标减一位
    			}
    			else if (key > a[mid])
    			{
    				low = mid + 1;
    				k = k - 2;
    			}
    			else
    			{
    				if(mid <= n)
    				{
    					return mid;  //相等则返回mid
    				}
    				else 
    				{
    					return n;   //此时越界,应返回n
    				}
    			}
    	}
    	return 0;
    }
    

    在这里插入图片描述

    展开全文
  • 小白今天刚入门数据结构,正在学习《数据结构高分笔记》,...题目要求:已知递增有序的单链表A,B,元素个数分别m,n,分别存储一个集合,请设计算法,求出A与B的差集,将结果保存在A表中,保持元素递增有序。 #in


    小白今天刚入门数据结构,正在学习《数据结构高分笔记》,其中第35页仿真题目(2)完成情况如下,如有错误,不吝赐教。


    题目要求:已知递增有序的单链表A,B,元素个数分别m,n,分别存储一个集合,请设计算法,求出A与B的差集(我这里定义的差集是指除共同元素以外的元素),将结果保存在A表中,保持元素递增有序。

    测试结果如下:





    由于程序比较基础,不处理内存分配失败情况,没有对错误输入情况进行筛查,默认输入数据均递增有序且合规。


    #include <stdio.h>
    #include <stdlib.h>
    #define m 3
    #define n 4
    
    typedef struct Lnode
    {
    	int data;
    	struct Lnode *next;
    }Lnode,*Linklist;//节点类型和指向结构的指针类型
    
    Linklist Creatnode(int temp);
    void Creatlist(Linklist L,int x);//x为数据长度
    void initlist(Linklist *L);
    void printlist(Linklist L,int x);//x为数据长度
    void printlist2(Linklist L);
    void AchaB(Linklist L1,Linklist L2);
    void jointprint(Linklist L1,Linklist L2,int x,int y);//x,y为数据长度
    
    void main ()
    {
    	/*初始化*/
    	Linklist L1;
    	Linklist L2;
        initlist(&L1);
    	L1->next=NULL;//初始状态头结点指针指向NULL
    	initlist(&L2);
    	L2->next=NULL;//初始状态头结点指针指向NULL
    	Creatlist(L1,n);
    	Creatlist(L2,m);
    	jointprint(L1,L2,n,m);
    	AchaB(L1,L2);
    	printf("\n");
    }
    Linklist Creatnode(int temp)//单节点创建
    {
    	
    	Linklist p;
    	p=(Linklist)malloc(sizeof(Lnode));
    	p->data=temp;
    	p->next=NULL;//新创建的节点指向空
    	return p;
    }
    
    void jointprint(Linklist L1,Linklist L2,int x,int y)//数据输入结果打印
    {
    	printf("构造链表如下:\n");
    	printlist(L1,x);
    	printlist(L2,y);
    	printf("\n");
    }
    
    void initlist(Linklist *L)//内存分配
    {
    	*L=(Linklist)malloc(sizeof(Lnode));//等同于**L=返回的指针*p
    	
    }
    
    void Creatlist(Linklist L,int x)//链表创建
    {
    	/*创建表*/
    	Linklist f;
    	f=L;
    	printf("现在构造第链表\n");
        int temp;
    	for (int i=0;i<x;i++)
    	{
    		printf("请输入第%d个节点值(整数)\n",i+1);
    		scanf("%d",&temp);
    		f->next=Creatnode(temp);//这一步完成了节点的内存分配和值的写入	
    		f=f->next;
    	}
    	/*创建表*/
    	//	printlist(L);
    }
    
    void printlist(Linklist L,int x)//打印单表
    {
    	Linklist print;
    	print=L->next;
    	for(int i=0;i<x;i++)
    	{
    		printf(" %d ",print->data);
    		print=print->next;
    	}
    }
    
    void printlist2(Linklist L)//操作结果打印
    {
    	Linklist print;
    	print=L->next;
    	for(int i=0;i<(2*n);i++)
    	{
    		printf(" %d ",print->data);
    		print=print->next;
    		if (print==NULL)break;
    	}
    	printf("\n");
    }
    
    
    void AchaB(Linklist L1,Linklist L2)//求差集
    
    {
    	Linklist p1;
    	Linklist p2;
    	Linklist r2;
    	Linklist r1;
    	Linklist del;
    	p1=L1->next;
    	p2=L2->next;
    	r2=L2;
    	r1=L1;
    	while(p1!=NULL&&p2!=NULL)
    	{
    		if(p1->data>p2->data)
    		{
    			r2=r2->next;
    			p2=p2->next;
    			
    		}
    		else if (p1->data<p2->data)
    		{
    			p1=p1->next;
    			r1=r1->next;
    		}
    		else 
    		{
    			del=p2;
    			p2=p2->next;
    			r2->next=p2;
    			free (del);
    			del=p1;
    			p1=p1->next;
    			r1->next=p1;
    			free(del);
    		if (p1==NULL||p2==NULL)break;
    		}
    	}
    	//至此,差集求完
    
    	//下面两个有序链表头插
    	p1=L1->next;
    	p2=L2->next;
    	r2=L2;
    	r1=L1;
    	Linklist temp;
    
    	while (p1!=NULL&&p2!=NULL)
    	{
    		if (p1->data>p2->data)
    		{
    			temp=p2;
    			p2=p2->next;
    			r2->next=p2;
    			temp->next=p1;
    			r1->next=temp;
    			r1=r1->next;
    		}
    		else if (p1->data<p2->data)
    		{
    			p1=p1->next;
    			r1=r1->next;
    		}
    	}
    	if (p1==NULL)
    	r1->next=L2->next;
    		printf("两个链表的差集链表构造完毕,结果如下:\n");
    		printlist2(L1);
    }
    
    



    展开全文
  • 合并有序链表(Java)

    2021-02-03 09:16:00
    如果B从某个元素开始比A的全部元素都大,又因为B是有序链表,这个就简单了,直接把B拼接到A的尾巴即可,无需再一个个比较。 PS: 由于链表有头尾两节点,内存中属于分散存储,所以设置好头尾下一.
  • #include<stdio.h> #include<stdlib.h> struct list{ int data; list *next; }; int main4(){ list *headA,*headB,*headC,*temp,*p; temp=(list*)malloc(sizeof(list)); temp->... p=
  • 合并两个有序链表

    2017-07-13 21:12:38
    合并两个有序链表,可以分为以下几种情况:a)当要合并的两条链表都为空,返回空;b)当一个链表为空;此时我们直接返回好另一条链表即可;c)都不为空,两个链表进行合并;此中由于我们不知道链表1和链表2应该以谁为...
  • 给出两个长度为 n 的有序表 A 和 B, A 和 B 中各任取一个元素,可以得到 n^2 个和,求这些和中最小的 n 个。 输入 第 1 行包含 1 个整数正 n(n≤400000)。第 2 行与第 3 行分别有 n 个整数,各代表有序表 A ...
  • A和B是两个单链表(带有表头节点),其中元素是递增有序的,设计一个算法,将A和B归并成一个按元素值非增减有序的链表C,C由链表A和B的节点组成 2. 思路分析: ① 我们知道头插法最终创建的链表的顺序与插入的顺序...
  • 两个有序链表的合并

    2020-05-06 14:36:27
    两个简单有序链表如链表A:1->2->3,链表B:1->2->4,如何快速有效的合并一起: 算法 暴力破解法 ,最简单的方法。即依次分别取出两个链表的一个元素进行比较,并用一个新的链表C来保存比较结果即可...
  • 有序表的最小和

    2016-04-07 23:29:58
    给出长度为n得有序表A和B,A和B中各取一个元素,可以得到n^2个和,求这些和中最小的n个 【输入格式】 第一行包含一个整数n(n 第二行与第三行分别n个整数,从小到大排列 【输入样例】 3 1 2 5 2 4 7 【输出...
  • 154个元素组成有序表进行二分法查找,可能的比较次数为() A:10 B:8 C:4 D:2答案:BCD别出新意的解题思路: 折半查找过程可用二叉树来描述,把有序表中间位置上的结点作为树的根结点,左子表和右子表...
  • 循环有序链表中插入一个新值。例如:插入7之后算法: 为新插入的节点分配内存,并将数据放在新分配的节点中。让指向新节点的指针是new_node。内存分配之后,以下是需要处理的三种情况。1)链接为空: a)因为...
  • // ConsoleApplication3.cpp : 定义控制台应用...#include "stdafx.h" //A,B分别有序,打印出属于A,不属于的B的元素保存在A中。 #include  typedef struct LNode { int data; struct LNode* next; }LNode
  • Given a node from a cyclic linked list which is sorted in ascending order, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be a refere...
  • 设顺序表A的数据元素递增有序,试写一程序,将x插入到顺序表的适当位置上,使该表仍然有序
  • 给出两个长度为n的有序表AA和B中各任取一个元素,可以得到n^2个和,求 这些和中最小的n个. [输入格式] 第一行包含一个整数n(n&amp;lt;400000); 第二行与第三行分别有n个整数,分别代表有序表A和...
  • 给出一个递增有序表A中采用二分查找算法查找值为k的关键字的递归算法。 分析 即二分查找的算法。 代码 核心代码: /* 二分查找的核心算法 */ /* A[]指的是要查找的数组;low指的是开始下标;high指的是结束...
  • 目的:a,b两无序链表合并后有序输出 功能:使用链表解决一些实际问题,巩固对链表理解和应用 */ #include<stdio.h> #include<math.h> #include<malloc.h> #include<stdlib.h> typedef ...
  • 归并排序的递归过程中,我们的算法是将原始数组a切割成两段:a1和a2,对a1和a2分别排序后,再将二者归并成一个有序的数组。这里的思路是一样的,只不过将数组变成了链表。 大体的思路是: 确定合并后的新链表的头...
  • 有序表的索引顺序结构查找次数分析@(算法学习) 为了提高查找效率,对65025个元素的有序顺序表建立索引顺序结构,最好情况下查找到表中已有元素,平均需要执行(B)次关键字比较。 A. 10 B. 14 C. 20 D. ...
  • 顺序的最大容量创建顺序对象时指定; 实现从尾部追加(输入一组数,以-1结束)、打印顺序的所有元素、插入元素至指定位置等基本操作。 实现向升序中插入元素x,插入后依旧是升序 import java.util....
  • 这个是单链表的,顺序我也有写,我的另一个文章中 我不太善于解释,注释都写代码旁边了,function里面的算法就是作业要求的,直接看就可以了,不过整体看过来可能更好,希望能帮到你吧#include #include #...
  • a)求前驱是指,输入一个元素值(而不是位置),求该元素顺序中的直接前驱元素值。求后继是指:输入一个元素值(而不是位置),求该元素顺序中的直接后继元素值;(b)为了方便修改数据元素的类型,请使用...
  • 已知单链表 A, B 和 C 均为递增有序排列,现要求对 A 作如下操作:删去那些既 B 中出现又 C 中出现的元素。试对单链表编写实现上述操作的算法。 分析 题目的要求我们可以理解成将三个单链表的交集从...
  • Leetcode刷题的时候,碰到有序链表的合并问题,第21题是两个链表的合并,第23提是k个链表的合并,第23题利用第21题的解法,将两个链表合成一个,再把合成的链表作为新链表和下一个链表合并即可。合并链表有很多...
  • 两个非递减有序表合并

    千次阅读 2016-11-20 12:15:42
    设计实现一个算法,用以对两个非递减有序表A、B进行合并,其中A=(2,5,8,9) ,B=(3,4,8,10,12,20)。 对两个表依次查找,例如以A表为主要目标,从B表中依次查找,因为两个表都是有序的,所以从B中的第一个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,364
精华内容 545
关键字:

在有序表a