一个有序单链表(从小到大),表头指针为head,编写个算法插入个元素为x的结点,使其仍有序
额,这个书上没有么?
void insert(node*head,int x)
{
node*p,*q;
p=head;
node*t;
t=(node*)malloc(sizeof(node)); 新节点幅值
t->val=x;
while((p!=NULL)&&(p->val<x))
{ q=p; p指针移动,q为其前驱指针
p=p->next;
}
if(p==NULL)
p->next=t;
else
{
t->next =p;
q->next =t;
}
}
第一,你单链表的头结点head里是否有存数据。
从你的 if (head == null) head = newnode;来看head是存了数据,而 if (head.next==null) head.next=newnode;来看head是没存数据的。两个在一起有点矛盾,要是head只做标志的作用不存数据则有第二个if就可以了;要是head存数据的话,有第一个if就可以了。
从后面的 while(head.next!=null)来看,你的head中应该是没有存数据的,而是从head.next开始存数据的。
第二, while(head.next!=null)循环中head指针的后移。最好不要亲自操作改变head指针的指向位置,因为它是来标记其实位置的。你这里等于是每次都有移动head指针,所以下次插入的时候,没丢掉head之前的数据。先定义一个指针结点指向head即可:Node p= head;然后比较的时候移动p即可。
第三,while中的内容中的 Node temp 时多余的。
第四, if (flag = false)中的等号。不知道Java里面的赋值赋好与逻辑等是不是一样的,但是我知道C/C++中德赋值是“=”,逻辑等是“==”,而VB中的两个等是一样的,都是“=”。我想Java中德应该两个等的表示是不一样的吧。
你试一试这个:
public void insert(Node head, Node newnode)
{
boolean inserted = false;
Node p= head;
if (head.next==null)
head.next=newnode;
while(p.next!=null)
{
if (p.next.value>newnode.value)
{
newnode.next = p.next;
p.next=newnode;
inserted = true;
break;
}
else
p= p.next;
}
if (flag == false)
p.next = newnode;
}
下面介绍如何在指针q指向的结点后面插入结点。该过程的步骤如下:
(1)先创建一个新结点,并用指针p指向该结点。
(2)将q指向的结点的next域的值(即q的后继结点的指针)赋值给p指向结点的next域。
(3)将p的值赋值给q的next域。
通过以上3步就可以实现在链表中由指针q指向的结点后面插入p所指向的结点。可以通过图1-5形象地展示出这一过程。
图1-5 向链表插入结点过程
下面给出代码描述:
1.void insertList(LinkList *list,LinkList q,ElemType e){ 2. /*向链表中由指针q指出的结点后面插入结点,结点数据为e*/ 3. LinkList p; 4. p=( LinkList)malloc(sizeof(LNode)); /*生成一个新结点,由p指向它*/ 5. p->data=e; /*向该结点的数据域赋值e*/ 6. if(!*list){ 7. *list=p; 8. p->next=NULL; 9. } /*当链表为空时*/ 10. else{ 11. p->next=q->next; 12. /*将q指向的结点的next域的值赋值给p指向结点的next域*/ 13. q->next=p; 14. /*将p的值赋值给q的next域*/ 15. } 16.} 上面的这段代码描述了如何在指针q指向的结点后面插入结点的过程。其过程包括以下几步。
(1)首先生成一个新的结点,大小为sizeof(LNode),用LinkList类型的变量p指向该结点。将该结点的数据域赋值为e。
(2)接下来判断链表是否为空。如果链表为空,则将p赋值给list,p的next域的值置为空。否则,将q指向的结点的next域的值赋值给p指向结点的next域,这样p指向的结点就与q指向结点的下一个结点连接到了一起。
(3)然后再将p的值赋值给q所指结点的next域,这样就将p指向的结点插入到了指针q指向结点的后面。
其实通过上面这段算法描述可以看出,应用这个算法同样可以创建一个链表。这是因为当最开始时链表为空,即list==NULL,该算法可自动为链表创建一个结点。在下面的创建其他结点的过程中,只要始终将指针q指向链表的最后一个结点,就可以创建出一个 链表。
注意:函数insertList()的参数中有一个LinkList *list,它是指向LinkList类型的指针变量,相当于指向LNode类型的指针的指针。这是因为在函数中要对list,也就是表头指针进行修改,而调用该函数时,实参是&list,而不是list。因此必须采取指针参数传递的办法,否则无法在被调函数中修改主函数中定义的变量的内容。以下的代码也有类似的情况。
一个有序单链表(从小到大),表头指针为head,编写个算法插入个元素为x...
1.void insertList(LinkList *list,LinkList q,ElemType e){ 2. \/*向链表中由指针q指出的结点后面插入结点,结点数据为e*\/ 3. LinkList p; 4. p=( LinkList)malloc(sizeof(LNode)); \/*生成一个新结点,由p指向它*\/ 5. p->data=e; \/*向该结点的数据域赋值...
有一个有序单链表(从小到大排序),表头指针为head,编写一个函数向该...
\/\/create an orderedly single-liked list template<class T> void slist<T>::insert_order(T item){ Node<T>*currptr,*preptr,*newnode;newnode=new Node<T>(item, NULL); \/\/prepare the inserted node \/\/find inserting positon preptr=NULL;currptr=head;while(currptr!=NULL){ if ...
有序单链表(从小到大排序),表头指针为head,编写一个函数向该单链表中...
第一,你单链表的头结点head里是否有存数据。从你的 if (head == null) head = newnode;来看head是存了数据,而 if (head.next==null) head.next=newnode;来看head是没存数据的。两个在一起有点矛盾,要是head只做标志的作用不存数据则有第二个if就可以了;要是head存数据的话,有第...
2、 有一个有序单链表(从小到大排列),表头指针为head,编写一个算法向该...
额,这个书上没有么?void insert(node*head,int x){ node*p,*q;p=head;node*t;t=(node*)malloc(sizeof(node)); 新节点幅值 t->val=x;while((p!=NULL)&&(p->val<x)){ q=p; p指针移动,q为其前驱指针 p=p->next;} if(p==NULL)p->next=t;else { t->next =p...
有序单链表和单链表的区别
有序单链表和单链表是两种不同的数据结构,它们的区别如下:1. 定义和特点:- 单链表(Singly Linked List):单链表是一种由节点组成的数据结构,每个节点包含数据和指向下一个节点的指针。它的特点是每个节点只有一个指针,指向下一个节点,最后一个节点的指针为空。- 有序单链表(Ordered Singly ...
什么是单链表?有序链表有什么特征?
有序链表就是,从头结点开始到链表结尾,节点中数据有序排列,比如说递增,递减或者其他满足一定条件的规则。单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;...
如何快速的创建有序单链表?
创建一个包括n个结点的有序单链表的时间复杂度是O(n2)。资料拓展:单链表简介:1、概念介绍 链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性...
建立一个有n个元素的有序单链表的时间复杂度度为什么是O(n^2) 求详 ...
因为o(n^2),对单链表而言,一些快速的排序算法,不能用,只能用直接插入等o(n^2)级的排序算法来实现排序。因为是有序单链表那么每次插入到链表尾结点,那么每次插入都要从头扫到尾,然后1+2+3+... m = O(m^2)这样。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的...
根据两个有序单链表生成一个新的有序单链表,原有单链表保持不变._百 ...
\/\/根据两个有序单链表L1和L2, 生成一个新的有序单链表 ListNode *p1 = L1->link, *p2 = L2->link;ListNode *first=new ListNode;ListNode *p=first;while ( p1 != NULL && p2 != NULL ) { \/\/当两个链表都未检测完时 if(p1->data < p2->data){ p=p->link = new ListNode;p-...
什么是单链表?
在一个具有n个结点的有序单链表中插入一个新结点,并使其仍然有序的时间复杂性为O(n);因为单链表保存的信息只有表头如果要在特定位置插入一个节点,需要先从表头一路找到那个节点。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) +指针(指示后继元素存储位置),元素就是存储...
浑军盐酸: 我也有.
于田县17180732179: 2、 有一个有序单链表(从小到大排列),表头指针为head,编写一个算法向该单链表中插入一个元素为x的结点 - ?
浑军盐酸: 额,这个书上没有么? void insert(node*head,int x) { node*p,*q; p=head; node*t; t=(node*)malloc(sizeof(node)); 新节点幅值 t->val=x; while((p!=NULL)&&(p->valnext; } if(p==NULL) p->next=t; else { t->next =p; q->next =t; } }
于田县17180732179: 有序单链表(从小到大排序),表头指针为head,编写一个函数向该单链表中插入一个元素为x的结点, - ?
浑军盐酸: 第一,你单链表的头结点head里是否有存数据. 从你的 if (head == null) head = newnode;来看head是存了数据,而 if (head.next==null) head.next=newnode;来看head是没存数据的.两个在一起有点矛盾,要是head只做标志的作用不存数据则...
于田县17180732179: 用C语言编写程序 数据结构?
浑军盐酸: 编写一个加密程序: 假设原文为字符序列C0C1C2.Cn-1,加密后所产生的密文已经编译运行通过,不过你的例子有问题: key=3 原文为abcd 密文应该为dbac
于田县17180732179: 非递减有序单链表 什么意思啊 - ?
浑军盐酸: 非递减有序单链表;是指从小到大有序啊,即递增;但又没说是单调递增,说明允许有重复的数据.
于田县17180732179: c语言中,头指针,表头指针,头结点,第一结点分别是什么???举个例子,谢谢. - ?
浑军盐酸: 头指针是以确定线性表中第一个元素对应的存储位置,一般用于处理数组,链表,队列等数据结构.单链表可以用头指针的名字来命名.单链表中头指针指向头节点.头指针指向上述数据结构的起始数据的指针,如指向数组首地址的指针,指向...
于田县17180732179: 已知单链表的结点顺序是由小到大排列的,设计一个算法,在此有序的单链表中插入 - ?
浑军盐酸: s表示要插入的节点,假设s已被赋值. L表示目的链表,且L.head仅为头指针,不存储信息 Node* q = L.head Node* p = L.head->next while( p != NULL ) { if( s->value <= p->value ) // 找到了s该插入的位置,并且此时p,q已记录下要插入的位置 break else q = p p = p->next } // 将s节点插入到q,p节点之间 s->next = p; q->next = s; 画画图就出来了,不过不要漏考虑插入位置在表头或表尾的情况
于田县17180732179: 写一个c语言算法?
浑军盐酸: 在VC6.0运行通过,如果需要在TC下运行,请自行修改. #include<stdio.h> #include<stdlib.h> typedef struct LNode {//定义链表结点结构 int data; struct LNode *next; }LNode,*LinkList; void displayList(LinkList L) {//显示链表数据 LNode *p = L->next; ...
于田县17180732179: 怎么看一个单链表是有序还是无序的呀 - ?
浑军盐酸: 单链表的数据值从小到大(或从大到小)就是有序的,否则就是无序的.