精华内容
下载资源
问答
  • 双向链表的插入删除和查询

    千次阅读 2013-03-17 23:57:30
    实现双向链表的插入删除和查询,并写出测试用例。 #include #include using namespace std; /*** *实现双向链表的插入、查找、删除 *xx笔试算法题 ***/ typedef struct Node { int data; struct ...

    实现双向链表的插入删除和查询,并写出测试用例。


    #include <iostream>
    #include <cstdlib>
    
    using namespace std;
    
    
    
    /***
    *实现双向链表的插入、查找、删除
    *xx笔试算法题
    ***/
    
    typedef struct Node
    {
        int data;
        struct Node * next;
        struct Node * prev;
    }Node;
    
    /**在链表h第pos个节点前插入值为v的节点,如果不存在
    第pos个节点,则插入在尾部*/
    Node * dlinsert(Node *h, int pos, int v)
    {
        int i=0;
        Node * t=h;
        Node * pre = h;
        while(i<pos && t )
        {
            i++;
            pre = t;
            t = t->next;
        }
        Node * n = (Node*)malloc(sizeof(Node));
        n->data = v;
        if(h==0)///空表
        {
            n->prev = 0;
            n->next = 0;
            return n;
        }
        if(t!=0)///不在尾部
        {
            n->next = t;
            n->prev = pre;
            t->prev = n;
            pre->next=n;
        }
        else///insert at tail
        {
            pre->next = n;
            n->prev = pre;
            n->next = 0;
        }
        return h;
    }
    
    void print(Node *h)
    {
        cout<<"order:"<<endl;
        while(h)
        {
            cout<<h->data<<" ";
            h = h->next;
        }
        cout<<endl;
    }
    
    void printReverse(Node *h)
    {
        cout<<"reverse order:"<<endl;
        while(h&&h->next)
        {
            h = h->next;
        }
        while(h)
        {
            cout<<h->data<<" ";
            h = h->prev;
        }
        cout<<endl;
    }
    
    /*** 查找第一个值为v的节点,并返回该节点的指针*/
    Node * query(Node *h, int v)
    {
        while(h&&h->data!=v)
            h = h->next;
        return h;
    }
    
    /**删除值为v的第一个节点,并置位flag*/
    Node * dldelete(Node *h, int v, int *flag)
    {
        Node * d = query(h,v);
        if(d)///delete node d
        {
            cout<<"find "<<endl;
            if(d->next==0)///last node
            {
                d->prev->next = 0;
            }
            else if(d->prev==0)///first node
            {
                d->next->prev=0;
                h = d->next;///for return
            }
            else
            {
                d->next->prev = d->prev ;
                d->prev->next = d->next;
            }
            free(d);
            *flag = 1;
            return h;
        }
        else
        {///failed delete
            cout<<"not find "<<endl;
            *flag = 0;
            return h;
        }
    }
    
    
    int main()
    {
        Node *h=0;
        h=dlinsert(h,1,9);
        print(h);
        printReverse(h);
    
        h=dlinsert(h,2,8);
        print(h);
        printReverse(h);
    
        h=dlinsert(h,1,3);
        print(h);
        printReverse(h);
    
        h=dlinsert(h,1,5);
        print(h);
        printReverse(h);
    
        ///test query
        int v = 1;
        Node * s=query(h,v);
        if(s)
            cout<<s<<"->"<<s->data<<endl;
        else
            cout<<"cannot find "<<v<<" in the list."<<endl;
    
        ///test delete
        int st=0;
        int * flag =&st ;
        v = 8;
        h = dldelete(h,v,flag);
        cout<<"delete state:"<<*flag<<endl;
        print(h);
        printReverse(h);
    
        return 0;
    }
    


    当时不知道怎么2了,一直在考虑循环链表的头和尾指针为题。。。。。


    展开全文
  • 插入结点分为: 双向链表为空, 和双向链表表非空两种情况 删除结点分为: 删除头结点和删除其他结点两种情况, 在删除头结点时需注意: 双向链表只含一个头结点情况和含有多个结点删除头结点情况 删除其他结点时...

    对于不是循环的双向链表:

    写成程序时画图示意一下:几个特殊点注意一下尤其注意空指针

    插入结点分为: 双向链表为空, 和双向链表表非空两种情况

    删除结点分为 删除头结点和删除其他结点两种情况 在删除头结点时需注意: 双向链表只含一个头结点的情况和含有多个结点删除头结点的情况

    删除其他结点时需注意 删除尾结点时,指针的特殊情况

    双向非循环链表的操作和单链的操作基本一致:


    双向非循环链表的插入和删除操作参考代码:

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    using namespace std;
    //以下为双向链表的操作
    typedef struct DoubleListNode
    {
         int data;
    	 DoubleListNode *prior,*next;
    }DoubleListNode;
    //尾插法建立双向链表 
    void AddNodeToTail(DoubleListNode**pHead,int value)//插入结点分为: 双向链表为空, 和双向链表表非空两种情况
    {
        DoubleListNode *pNew=new DoubleListNode;
    	pNew->data=value;
    	pNew->prior=pNew->next=NULL;
    	if(*pHead==NULL)
    	{
    	     *pHead=pNew;
    	}
    	else
    	{
    	     DoubleListNode* pNode=*pHead;
    		 while(pNode->next!=NULL)//找到尾结点
    		 {
    			 pNode=pNode->next;
    		 }
    		 pNode->next=pNew;
    		 pNew->prior=pNode;
    	}
    }
    //删除结点分为:  删除头结点和删除其他结点两种情况, 在删除头结点时需注意: 双向链表只含一个头结点的情况和含有多个结点删除头结点的情况
    //删除其他结点时需注意 删除尾结点的是指针的特殊情况
    void RemoveNode(DoubleListNode**pHead,int value)
    {
         if(pHead==NULL||*pHead==NULL)
    	 {
    	    return ;
    	 }
    	 DoubleListNode *pToBeDelete=NULL;
    	 if((*pHead)->data==value)//删除双向链表的头结点
    	 {
    	      pToBeDelete=*pHead;
    		  *pHead=(*pHead)->next;
    		  if(*pHead!=NULL)//此种情况为删除只有一个头结点的情况
    		  {
    			(*pHead)->prior=NULL;
    		  }
    	 }
    	 else//删除双向链表中的其它结点
    	 {
    	     DoubleListNode *pNode=*pHead;
    		 while(pNode->next!=NULL&&pNode->next->data!=value)//找到删除结点的前驱结点
    		 {
    		     pNode=pNode->next;
    		 }
    		 if(pNode->next!=NULL&&pNode->next->data==value)
    		 {
    		      pToBeDelete=pNode->next;
    			  pNode->next=pToBeDelete->next;
    			  if(pToBeDelete->next!=NULL)//考虑删除尾结点的情况
    			  {
    			  pToBeDelete->next->prior=pNode;
    			  }
    		 }
    	 }
    	 if(pToBeDelete!=NULL)
    	 {
    	     delete pToBeDelete;
    		 pToBeDelete->prior=pToBeDelete->next=NULL;
    	 }
    }
    void PrintList(DoubleListNode*pHead)
    {
         if(pHead==NULL)
    	 {
    	     return;
    	 }
    	 DoubleListNode *pNode=pHead;
    	 while(pNode!=NULL)//对于单链表的判断此处while(pNode!=NULL)
    	 {
    	      cout<<pNode->data<<" -->";
    		  pNode=pNode->next;
    	 }
    	 cout<<"NULL"<<endl;
    }
    int main()
    {
       DoubleListNode *pHead=NULL;
       for(int i=1;i<=10;i++)
       {
            AddNodeToTail(&pHead,i);
       }
       PrintList(pHead);
        RemoveNode(&pHead,7);//删除中间结点
    	 PrintList(pHead);
    
        for(int i=1;i<=10;i++)//一直删除头结点
       {
           RemoveNode(&pHead,i);
    	  PrintList(pHead);
       }
        for(int i=1;i<=10;i++)
       {
            AddNodeToTail(&pHead,i);
       }
       PrintList(pHead);
       for(int i=10;i>=0;i--)//一直删除尾结点
       {
          RemoveNode(&pHead,i);
    	  PrintList(pHead);
       }
       
       return 0;
    }

    双向循环操作的考虑的东西要稍微多一点点:


    基本也一样:


    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    using namespace std;
    //以下为双向循环链表的操作
    typedef struct DoubleListNode
    {
         int data;
    	 DoubleListNode *prior,*next;
    }DoubleListNode;
    //尾插法建立循环双向链表   对于非空双向循环链表先找到尾结点pNode=(*Phead)->prior;
    void AddNodeToTail(DoubleListNode**pHead,int value)
    {
        DoubleListNode *pNew=new DoubleListNode;
    	pNew->data=value;
    	pNew->prior=pNew->next=NULL;
    	if(*pHead==NULL)//注意对于尾插法的循环双向链表来说,(*pHead)->prior 即为尾节点 插入很容易
    	{
    	     *pHead=pNew;
    		 pNew->next=pNew->prior=pNew;
    	}
    	else
    	{
    	     DoubleListNode *pNode= (*pHead)->prior;//pNode 指向了原来的尾结点
    		 pNew->next=*pHead;//尾插法新节点的后继为头结点
    		 pNew->prior=pNode;
    		 pNode->next=pNew;
    		 (*pHead)->prior=pNew;
    		 
    	}
    }
    void RemoveNode(DoubleListNode**pHead,int value)
    {
         if(pHead==NULL||*pHead==NULL)
    	 {
    	    return ;
    	 }
    	 DoubleListNode *pToBeDelete=NULL;
    	 if((*pHead)->data==value&&(*pHead)->next==(*pHead))//删除只含一个结点循环双向链表 此处的条件一定不能错
    	 {
    	      pToBeDelete=*pHead;
    		  *pHead=NULL;
    	 }
    	 else if((*pHead)->data==value)//删除含多个元素的头结点
    	 {
    	      pToBeDelete=*pHead;
    		  *pHead=(*pHead)->next;//原先头结点的的下个结点更新为新的头指针
    		  (*pHead)->prior=pToBeDelete->prior;//头结点的前驱指向尾结点
    		  pToBeDelete->prior->next=*pHead;//尾结点的后继指向头结点
    	 }
    	 else//删除双向链表中的其它结点
    	 {
    	     DoubleListNode *pNode=*pHead;
    		 while(pNode->next!=(*pHead)&&(pNode->next->data!=value))//找到删除结点的前驱结点
    		 {
    		     pNode=pNode->next;
    		 }
    		 if(pNode->next!=(*pHead)&&(pNode->next->data==value))
    		 {
    		      pToBeDelete=pNode->next;
    			  pNode->next=pToBeDelete->next;//这里绝对不能搞错。
    			  pToBeDelete->next->prior=pNode;
    		 }
    	 }
    	 if(pToBeDelete!=NULL)
    	 {
    	     delete pToBeDelete;
    		 //pToBeDelete->prior=pToBeDelete->next=NULL;
    	 }
    }
    void PrintList(DoubleListNode*pHead)
    {
         if(pHead==NULL)
    	 {
    	     return;
    	 }
    	 DoubleListNode *pNode=pHead;
    	 while(pNode->next!=pHead)//对于单链表的判断此处while(pNode!=NULL)
    	 {
    	      cout<<pNode->data<<" -->";
    		  pNode=pNode->next;
    	 }
    	 cout<<pHead->prior->data<<" -->";//打印最后一个结点
    	 cout<<"NULL"<<endl;
    }
    int main()
    {
       DoubleListNode *pHead=NULL;
       for(int i=1;i<=10;i++)
       {
            AddNodeToTail(&pHead,i);
       }
       PrintList(pHead);
        RemoveNode(&pHead,7);//删除中间结点
    	 PrintList(pHead);
    
        for(int i=1;i<=10;i++)//一直删除头结点
       {
           RemoveNode(&pHead,i);
    	  PrintList(pHead);
       }
        for(int i=1;i<=10;i++)
       {
            AddNodeToTail(&pHead,i);
       }
       PrintList(pHead);
       for(int i=10;i>=0;i--)//一直删除尾结点
       {
          RemoveNode(&pHead,i);
    	  PrintList(pHead);
       }
       
       
       return 0;
    }




    展开全文
  • 链表节点 存放 结点值,前继结点,后续结点 public class DoubleLink { public Long value; public DoubleLink pre; public DoubleLink next; public DoubleLink(Long value) { this.value = value; } ...

    链表节点 存放 结点值,前继结点,后续结点

    public class DoubleLink {
        public Long value;
        public DoubleLink pre;
        public DoubleLink next;
    
        public DoubleLink(Long value) {
            this.value = value;
        }
        public void displayDoubleLink(){
            System.out.print(" "+value);
        }
    }
    
    

    链表对象,存放首结点 末节点

    public class DoubleLinkList {
        private DoubleLink first;
        private DoubleLink last;
    
        public DoubleLinkList() {
            this.first = first;
            this.last = last;
        }
    
        public void insertFirst(long dd){
            DoubleLink newLink = new DoubleLink(dd);
            //把first节点的后置节点置为当前节点,
            if(isEmpty()){//如果是空链表 需要把last指向末尾
                last=newLink;
            }else{
                first.pre=newLink;  //newLink <-- old first
            }
            newLink.next=first;
            first=newLink;
    
        }
        public void insertLast(long dd){
            DoubleLink newLink = new DoubleLink(dd);
            if(isEmpty()){
                first=newLink;
            }else{
                last.next=newLink;
                newLink.pre=last;
            }
            last=newLink;
        }
    
        public DoubleLink deleteFirst(){
            DoubleLink temp=first;
            if(first.next==null){ //if only one item
                last=null;       //null <-- last
            }else{
                first.next.pre=null;
            }
            first=first.next;
            return  temp;
        }
    
        public DoubleLink deleteLast(){
            DoubleLink temp=last;
            if(first.next==null){
                first=null;
            }else{
                last.pre.next=null;
            }
            last=last.pre;
            return temp;
        }
    
    
        public  boolean insertAfterKey(long key,long dd){
            DoubleLink curr=first;
            while (curr.value!=key){
                curr=curr.next;
                if(curr==null){
                    return false; //didn't find it
                }
            }
            DoubleLink newLink=new DoubleLink(dd);
            if(curr==last){
                newLink.next=null;
                last=newLink;
            }else{
                 newLink.next=curr.next;
                 curr.next.pre=newLink;
            }
            newLink.pre=curr;
            curr.next=newLink;
            return true;
        }
    
        public DoubleLink deleteKey(long key){
            DoubleLink curr=first;
            while (curr.value!=key){
                curr=curr.next;
                if(curr.next==null){
                    return null;
                }
            }
            if(curr==first){
                first=curr.next;
            }else{
                curr.pre.next=curr.next;
            }
            if(curr==last){
                last=curr.pre;
            }else{
                curr.next.pre=curr.pre;
            }
            return curr;
        }
    
    
        public void dispalyForward(){
            System.out.print("List(first--last):");
            DoubleLink curr=first;
            while (curr!=null){
                curr.displayDoubleLink();
                curr=curr.next;
            }
            System.out.println("");
        }
    
        public  void displayBackWord(){
            System.out.print("List (last-->first: ");
            DoubleLink curr=last;
            while (curr!=null){
                curr.displayDoubleLink();
                curr=curr.pre;
            }
        }
         public boolean  isEmpty(){
            return first==null;
         }
        public DoubleLink getFirst() {
            return first;
        }
    
        public void setFirst(DoubleLink first) {
            this.first = first;
        }
    
        public DoubleLink getLast() {
            return last;
        }
    
        public void setLast(DoubleLink last) {
            this.last = last;
        }
    }
    
    
    展开全文
  •  //双向链表的后插运算 假设双链表的结点p的后继结点为q,在结点p之后插入一个新结点s  dlinklist *dinsert_after(dlinklist *head,dlinklist *p,int x)  {  dlinklist *s;  s=(struct node*)malloc(LEN);...

    #include<stdio.h>
    #include<stdlib.h>
    #define LEN sizeof(struct node)
    typedef int datatype;
    typedef struct node
    {
        datatype data;
        struct node *next,*prior;
    }dlinklist;
    dlinklist *head;
    //双向链表的前插运算  在结点p之前 
    dlinklist *dinsert_before(dlinklist *head,dlinklist *p,int x)
    {
        dlinklist *s;
        s=(struct node*)malloc(LEN);
        s->data=x;
        s->next=p;
        s->prior=p->prior;
        p->prior->next=s;
        p->prior=s;
        return(head);
        
     } 
     //双向链表的后插运算 假设双链表的结点p的后继结点为q,在结点p之后插入一个新结点s  
     dlinklist *dinsert_after(dlinklist *head,dlinklist *p,int x)
     {
         dlinklist *s;
         s=(struct node*)malloc(LEN);
         s->data=x;
        s->next=p->next;
        p->next->prior=s;
        s->prior=p;
         p->next=s; 
     }
     
     //双向链表的自身删除运算
     dlinklist *delete_nodep(dlinklist *head,dlinklist *p)//删除p结点 
     {
         if(p!=0)
         {
             p->prior->next=p->next;
             p->next->prior=p->prior;
             free(p);
             return (head);
         }
         else return 0;
      } 
     

    展开全文
  • #include<stdio.h> #include<stdlib.h> #include<string.h> #define OVERFLOW -2 #define FALSE 0 #define TRUE 1 #define OK 1 #define ERROR 0 ...//链表元素数据类型 typedef stru...
  • 如何使用c语言实现双向链表的插入删除操作如何使用c语言实现双向链表的插入删除操作? 我自己编的,数据定义 typedef struct duLNode {int data; struct duLNode *prior; struct duLNode *next; }duLNode,*dulinklist...
  • 双向链表,创建,插入删除,销毁等,写一个代码(包括详细注释,初学者都看得懂),已经成功测试。及拿即用。
  • 双向链表的插入删除

    万次阅读 多人点赞 2018-09-21 17:23:50
    双向链表的插入 第一步:首先找到插入位置,节点 s 将插入到节点 p 之前 第二步:将节点 s 的前驱指向节点 p 的前驱,即 s-&gt;prior = p-&gt;prior; 第三步:将节点 p 的前驱的后继指向节点 s 即 p-&...
  • 双向链表的插入删除(c++实现)

    千次阅读 2020-04-30 16:28:13
    (https://blog.csdn.net/qq_36472818/article/details/96306824)进一步实现单向链表的插入删除双向链表插入节点 在双向链表中插入新节点与单向链表相似,而根据新节点插入位置的不同,分为三种不...
  • 双向链表的插入 第一步:首先找到插入位置,节点 s 将插入到节点 p 之前 (//箭头指向谁,是谁被存) 第二步:将节点 s 的前驱指向节点 p 的前驱,即 s->prior = p->prior; //p的前驱里面存放的是第...
  • 双向链表的插入 第一步:首先找到插入位置,节点 s 将插入到节点 p 之前 第二步:将节点 s 的前驱指向节点 p 的前驱,即 s->prior = p->prior; 第三步:将节点 p 的前驱的后继指向节点 s 即 p->prior->next =...
  • 双向链表的插入删除图解

    千次阅读 多人点赞 2018-01-31 14:20:43
    双向链表的插入 第一步:首先找到插入位置,节点 s 将插入到节点 p 之前  第二步:将节点 s 的前驱指向节点 p 的前驱,即 s->prior = p->prior;  第三步:将节点 p 的前驱的后继指向节点 s 即 p->prior->...
  • 一 单链表 ...注意:此时理解双向链表的两个箭头: pre和next都是从本节点指向别的节点的!!! pre: 从该节点指向它的前一个节点; next: 从该节点指向它的后一个节点 举例:a2.pre = a1; a2.next =
  • 双向链表的插入删除,mergesort等。#include&lt;iostream&gt; using namespace std; struct BiListNode { int val; BiListNode *pre; BiListNode *next; BiListNode(int x) :val(x), pre(NULL), next...
  • 本文将详细介绍建立双向链表,实现对双向链表的插入,删除操作,需要了解的朋友可以参考下
  • /*双向链表的插入删除,与两表的合并*/ #include<stdio.h> #include<stdlib.h> #include<malloc.h> #define ERROR 0; #define OK 1; typedef struct Node{ char data; struct Node*prior,*next;...
  • 如何实现双向链表的插入删除操作  循环单链表的出现,虽然能够实现从任一结点出发沿着链能找到其前驱结点,但是时间复杂度为O(N)。如果希望能从链表中快速确定某一个结点的前驱,另一个解决方法就是在单链表的每...
  • 这是一个关于双向链表的建立、头部插入、尾部插入、查找元素、删除元素的完整程序。
  • 双向链表不一定是双端,不用必须有last节点 //链结点 public class Link { public long dData; public Link next; public Link previous; public Link(long d) { dData=d; } public void...

空空如也

空空如也

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

双向链表的插入删除