精华内容
下载资源
问答
  • 带头结点的单链表L中,删除所有值为x的结点,并释放其空间,假设值为x的结点...若p所指结点的值为x,则删除,并让p移向它的下一结点,否则让pre和p指针同时后移一个结点。 相关代码: void del_x(Linklist *&...

    在带头结点的单链表L中,删除所有值为x的结点,并释放其空间,假设值为x的结点不唯一,试编写算法以实现上述操作。


     思路:两个指针一次遍历,用p从头到尾扫描单链表,pre指向*p结点的前驱(因为删除一个结点,首先得知道它的前驱结点的位置)。若p所指结点的值为x,则删除,并让p移向它的下一结点,否则让pre和p指针同时后移一个结点。

    相关代码:

    void del_x(Linklist *&L,ElemType x)
    {
        Linklist *p=L->next,*pre=L,*q;	
    	//分别定义了结构体指针变量p,以及指向它的前驱的指针变量pre,还有用来临时存放要删除的结点的指针变量q 
        while(p!=NULL){	
            //p不为NULL则为真,用于遍历整个链表,这里也可以直接写"p"表示非0则为真,达到同样的效果。注意这里不能填p->next!=NULL,这样的话最后一个结点会遍历不到
        	if(p->data==x)	
        	    {
        		q=p;	//q临时存放要删除的结点 
        		p=p->next;
        		pre->next=p;
        		free(q);	//这三行为标准的删除语句 
    	    }
    		else{
    			pre=p;
    			p=p->next;	//pre与p指针同时向后移一位 
    		    }
    	}
    }

     试编写在带头结点的单链表L中删除一个最小值结点的高效算法(假设最小值结点是唯一的)

     总的原理和上面删除与x值相同的结点差不多,定义一个指针p,和它的前驱指针pre,p还是遍历整个链表,另外还有用来存放它们最小值结点的两个指针,分别为minpre和minp。

    相关算法:

    Linklist del_Min(Linklist *&L,ElemType x)
    {
        Linklist *p=L->next,*pre=L,*q;	
    	//分别定义了结构体指针变量p,以及指向它的前驱的指针变量pre。这两个指针用于比较、遍历 
    	Linklist *minpre=pre,*minp=p; 
    	//分别用来存放pre的值,与最小值minp,这两个智者用于存放最小值的结点以及最小值结点的前驱结点 
        while(p!=NULL){	
            //p不为NULL则为真,用于遍历整个链表,这里也可以直接写"p"表示非0则为真,达到同样的效果。注意这里不能填p->next!=NULL,这样的话最后一个结点会遍历不到
        	if(p->data<minp->data)	
        	    {
        	    	minp=p;	//让minp指向最小值的结点 
    				minpre=pre;	//minpre始终指向最小值结点的前一个结点。  	
    	    }
    			pre=p;
    			p=p->next;	//pre与p指针同时向后移一位 
    	}
    	minpre->next=minp->next;
    	free(minp);
    	return L;
    }

    试编写算法将带头结点的单链表就地逆置 ,所谓就地逆置是指辅助空间复杂度为O(1)

    第一种方法为直接把链表的指针反过来指向,将第一个结点的next域置空,然后再将头指针指向原本链表的最后一个结点。

    相关代码: 

    #include <stdio.h>
    Linklist Reverse_1(Linklist *&L)
    {
    	Linklist *pre,*p=L->next,*r=p->next;
    	p->next=NULL;	//处理组开始的结点,将它的next域置空,变成逆置链表的尾结点。 
    	while(p!=NULL)	//p依旧为遍历单链表 
    	{
    		pre=p;	//依次遍历 
    		p=r;
    		r=r->next;
    		p->next=pre;	//指针反置,后一个指向前一个结点 
    	 } 
    	L->next=p;	//将头结点指向原本链表最后一个结点 
    	return L;
    	
     } 

    第二种方法则是使用头插法,首先将第一个结点的next域置为空,然后后面的结点依次连接到头结点后面(注意,后面的每个结点都是连接到头结点),并且后面连接好之前插好的结点。 

    #include <stdio.h>
    Linklist Reverse_2(Linklist *&L)
    {
    	Linklist *pre,*p=L->next;
    	L->next=NULL;	//第一次循环会将第一个结点变成尾结点,会将L->next赋值给尾结点的指针域,即赋值为空 
    	while(p!=NULL)	//p依旧为遍历单链表 
    	{
    		pre=p;	//将p所指向的结点让pre也指向 
    		p=p->next;	 
    		pre->next=L->next;	//下面这两步是常规的插入操作,先连后断,现将pre的next域指向L的next域所指向的结点 
    		L->next=pre;	//将L的next域指向pre,两者不可调换位置,否则会断链。 
    	 } 
    	return L;
    	
     } 

     

     

    展开全文
  • 若p所指结点的值为x,则删除,并让p指向下个结点,否则让pre和p指针同步后移一个结点。解法二: 采用尾插法建立单链表,用p指针扫描L的所有结点,当其值不为x时将其链接到L之后,否则将其释放。我个人的解法更偏向...

    标准答案有两种解法,解法一:

        用p从头到尾扫描单链表,pre指向*p结点的前驱。若p所指结点的值为x,则删除,并让p指向下个结点,否则让pre和p指针同步后移一个结点。

    解法二:

        采用尾插法建立单链表,用p指针扫描L的所有结点,当其值不为x时将其链接到L之后,否则将其释放。

    我个人的解法更偏向于使用p指针指向头指针,判断p-next是否为空或者值为x,如果为空则return,如果不为x则让p=p->next,如果为x则让q指向p-next,让p->next=q->next,注意此时不用让p=p->next,否则会漏过一个结点。

    代码如下:

    void Del_X(LinkList &L, int x) {
    	if (L->next == NULL ) {
    		return;
    	}
    	LNode *p, *q;
    	p = L;
    	while (p->next != NULL) {
    		if (p->next->data == x) {
    			q = p->next;
    			p->next = q->next;
    			delete q;
    		}
    		else {
    			p = p->next;
    		}
    	}
     }

    展开全文
  • 第一部分 数据结构与算法 1:链表不具备的特点是 A 可随机访问任何一个元素 B 插入...2:在一个单链表中,若删除P所指结点的后续结点,则执行 A p = p->next;p->next = p->next->next; B p->next = p->nex

    第一部分 数据结构与算法

    1:链表不具备的特点是

    A 可随机访问任何一个元素      B 插入,删除操作不需要移动元素

    C 无需事先估计存储空间大小    D 所欲存储空间与线性表长度成正比

    2:在一个单链表中,若删除P所指结点的后续结点,则执行

    A p = p->next;p->next = p->next->next;

    B p->next = p->next;

    C p->next = p->next->next;

    D p = p->next->next

    3:将一棵二叉树的根节点放入队列,然后递归的执行如下操作,将出对结点所有子节点加入队。以上操作可以实现哪种遍历

    A 前序遍历 B 中序遍历 C 后序遍历 D 层序遍历

    4:设一课完全二叉树共有999个结点,则在该二叉树中的叶节点个数是

    A 499 B 500 C 501 D 不唯一

    5:以下哪种排序算法对【1,3,2,4,5,6,7,8,9】进行的排序最快

    A 冒泡 B 快排 C 归并 D 堆排

    第二部分 软件工程与数据库

    1:一条sql语句中,group by应位于什么位置

    A 在where子句关键字之前    B 在where子句之后

    C 在from之前                    D 在order by 之后




    第三部分:逻辑

    1:选择合适字母 : CFI DHL EJ_

    A: E   B:  G   C:  H   D:  C

    2:选择合适的图形

    3:选择左侧的纸板折叠成的纸盒是:

    4:右侧第一行问号处应该填写的数字是:

    5:有两根粗细均匀的香,每根燃尽需要1个小时,用什么方法确定15分钟。

    第四部分:java基础

    1:一个以“.java”为后缀的源文件

    A 只能包含一个类,类名必须与文件名相同  

    B 只能包含与文件名相同的类以及其中的内部类

    C 只能有一个与文件名相同的类,可以包含其他类

    D 可以包含任意类

    2: 代码system.out.println(10%3*2);将打印

    A 1    B 2    C 4    D 6

    3:以下代码将打印出

    4:下面函数将返回

    5:以下代码将打印出

    第五部分:简答题

    1:谈谈你对多态的理解

    2:如果铁道部分邀请你来重新设计火车票订票网站的架构,解决高峰时期服务不可用的问题,你有什么好主意。


    展开全文
  • 数据结构习题集锦.ppt

    2020-09-17 07:59:28
    cm2练习 表长为n的顺序存储的线性表,当在任何位置上插入或删除一个元素的概 率相等时,插入一个元素...A0(n)0(m)B0(n)0(1)C0(1)0(n)D0(1)0(1) 在一个单链表中,若删除p所指结点的后继结点,则执行) A p->next=p->next-nex
  • JD(2014)

    2014-10-15 08:19:38
    第一部分 数据结构与算法 1:链表不具备的特点是 A 可随机访问任何一个元素 B 插入...2:在一个单链表中,若删除P所指结点的后续结点,则执行 A p = p->next;p->next = p->next->next; B p->next = p->nex

    第一部分 数据结构与算法

    1:链表不具备的特点是

    A 可随机访问任何一个元素      B 插入,删除操作不需要移动元素

    C 无需事先估计存储空间大小    D 所欲存储空间与线性表长度成正比

    2:在一个单链表中,若删除P所指结点的后续结点,则执行

    A p = p->next;p->next = p->next->next;

    B p->next = p->next;

    C p->next = p->next->next;

    D p = p->next->next

    3:将一棵二叉树的根节点放入队列,然后递归的执行如下操作,将出对结点所有子节点加入队。以上操作可以实现哪种遍历

    A 前序遍历 B 中序遍历 C 后序遍历 D 层序遍历

    4:设一课完全二叉树共有999个结点,则在该二叉树中的叶节点个数是

    A 499 B 500 C 501 D 不唯一

    5:以下哪种排序算法对【1,3,2,4,5,6,7,8,9】进行的排序最快

    A 冒泡 B 快排 C 归并 D 堆排

    第二部分 软件工程与数据库

    1:一条sql语句中,group by应位于什么位置

    A 在where子句关键字之前    B 在where子句之后

    C 在from之前                    D 在order by 之后




    第三部分:逻辑

    1:选择合适字母 : CFI DHL EJ_

    A: E   B:  G   C:  H   D:  C

    2:选择合适的图形

    3:选择左侧的纸板折叠成的纸盒是:

    4:右侧第一行问号处应该填写的数字是:

    5:有两根粗细均匀的香,每根燃尽需要1个小时,用什么方法确定15分钟。

    第四部分:java基础

    1:一个以“.java”为后缀的源文件

    A 只能包含一个类,类名必须与文件名相同  

    B 只能包含与文件名相同的类以及其中的内部类

    C 只能有一个与文件名相同的类,可以包含其他类

    D 可以包含任意类

    2: 代码system.out.println(10%3*2);将打印

    A 1    B 2    C 4    D 6

    3:以下代码将打印出

    4:下面函数将返回

    5:以下代码将打印出

    第五部分:简答题

    1:谈谈你对多态的理解

    2:如果铁道部分邀请你来重新设计火车票订票网站的架构,解决高峰时期服务不可用的问题,你有什么好主意。

    展开全文
  • 1.在一个单链表中,若删除P所指结点的后续结点,则执行? 正确答案: C p=p->next;p->next=p->next->next p->next=p->next p->next=p->next->next p=p->next->next 解析: 让p的下...
  • 数据结构反思1

    2020-09-13 23:17:00
    1.在单链表中,若p所指的结点不是最后结点,p之后插入s所指结点,则执行 s->next=p->next; p->next=s; 注意插入链表时的顺序,不要因为顺序颠倒而使p->next丢失 本题的第二函数脑子就傻了,不...
  • 文章标题

    2017-12-14 23:12:14
    带头结点的单链表L中,删除所有值为x的...若p所指结点的值为x,则删除,并让p移向下一结点,否则让pre,p指针同步后移一个结点。 void Del_X_1(Linklist &L,ElemType x){ //L为带头结点的单链表,本算法删除L中所有值
  • 求两递增单链表的差集

    千次阅读 2013-03-13 16:36:37
    /* 求两链表的差集只需A删除A、B共同的... 两者所指节点值相同则删除p所指节点。最后p与q任意指针指向NULL则结束 */ void Difference(LNode *&A,LNode* B) { LNode *p=A->next,q=b->next; LNode *pre=A; L
  • 数据结构刷夜

    2020-10-02 21:34:54
    在一个单链表中,若q所指结点是p所指结点的前驱节点,若在q与p之间插入一个s所指的结点,则执行( q->link = s;s->link = p; ) 先分析逻辑关系变化 再考虑物理关系变化 删除与插入类似 只需要改变指针 顺序...
  • 18、在一个单链表中,若删除p所指结点的后续结点,则执行【 】 (A)p->next=p->next->next; (B)p=p->next; p->next=p->next->next; (C)p->next=p->next; (D)p =p->next->next; 19、线性表是具有n个【 】的...
  • 多项式相加算法的思路是,不产生新的结点而利用原有结点空间,设两个指针变量p和q分别指向A和B两个多项式单链表的第一个结点,依次比较两指针所指结点的指数项。指数相等系数相加,和不为零修改*p的系数项并删除*q...
  • 一选择题每题2分共20分 1长度为n 的线性表(a, a , a )... n+i C.n-i+1 D.n-i-1 2 在一个单链表head 中若要在指针p 所指结点后插入一个q 指针所指结点则执行 A. p->next=q->next; q->next=p; B. q->next=p->next; p
  • 《数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    9.以下数据结构中,一个是线性结构(D)?【北方交通大学 2001 一、1(2分)】 A.广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10.以下那一个术语与数据的存储结构无关?(A )【北方交通大学 2001 一、2(2分)】 A...
  • PAGE 试卷A 第 PAGE 1页 共7页 模拟卷 选择题本大题共15小题每题2分共30分 1线性表最常用...A一定连续 B一定不连续 C不一定连续 D部分连续部分不连续 3双向循环链表存储结构中删除p所指结点时必须修改指针 Ap
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    D. *建立函数create:根据一维数组a[n]建立一个单链表,使单链表中各元素的次序与a[n]中各元素的次序相同,要求该程序的时间复杂度为O(n)。 E. *整理函数tideup:非递减有序的单链表中删除值相同的多余...
  • 在一个线性结构插入或删除任何一个结点后还应是线性结构。栈、队列、串等都为线性结构。 如果一个数据结构不是线性结构,则称之为非线性结构。数组、广义表、树和图等数据结构都是非线性结构。 (2)线性表的顺序...
  • 数据结构实验

    2012-04-13 09:55:47
    已知有—棵以二叉链表存储的二叉树,root指向根结点,p指向二叉树任一结点,如何求从根结点到p所指结点之间的路径? 实验6:二分查找、Hash查找算法的程序实现 (第十五三周星期三7、8节) 、 实验目的 1 ....
  • 二叉排序树与平衡二叉树的实现

    热门讨论 2010-12-26 15:25:31
     平衡二叉树是构造二叉排序树的过程中,每当插入一个结点时,首先检查是否因插入新结点而破坏了二叉排序树的平衡性,若是,则找出其中的最小不平衡子树,保持二叉排序树特性的前提下,调整最小不平衡子树中各...
  • 4. 在单链表中删除指针p所指结点的后继结点,则执行( )。 A. p->next= p->next->next B. p->next= p->next C. p= p->next->next D. p= p->next; p->next= p->next->next 5. 某链表最常用的操作是最后一个结点...
  • 数据结构题

    2012-12-27 16:58:40
    17.单链表中若在指针p所指的结点之后插入指针s所指结点,则可用下列两语句实现该操作,是_s->next=p->next和_______ _。 18.假设以S和X分别表示进栈和退栈操作,则对输入序列a,b,c,d,e进行系列栈操作SSXSXXSSXX...
  • (64) 在单链表中,增加头结点的目的是(A) A. 方便运算的实现 B. 使单链表至少有一个结点 C. 标识表结点中首结点的位置 D. 说明单链表是线性表的链式存储实现 (65) 软件设计包括软件的结构、数据接口和过程设计,其中...
  • 单链表的上一个结点指针指向下一个结点,最后一个结点的指针域为null。 结点删除: <img alt="" src="http://my.csdn.net/uploads/201204/26/1335453593_8925.png" /><br /> 删除一个结点࿰...

空空如也

空空如也

1 2
收藏数 26
精华内容 10
关键字:

在一个单链表中,若删除p所指结点