• 实现双向链表的插入删除和查询，并写出测试用例。 #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;
//尾插法建立双向链表
{
DoubleListNode *pNew=new DoubleListNode;
pNew->data=value;
pNew->prior=pNew->next=NULL;
{
}
else
{
while(pNode->next!=NULL)//找到尾结点
{
pNode=pNode->next;
}
pNode->next=pNew;
pNew->prior=pNode;
}
}
//删除结点分为：  删除头结点和删除其他结点两种情况， 在删除头结点时需注意： 双向链表只含一个头结点的情况和含有多个结点删除头结点的情况
//删除其他结点时需注意 删除尾结点的是指针的特殊情况
{
{
return ;
}
DoubleListNode *pToBeDelete=NULL;
{
{
}
}
else//删除双向链表中的其它结点
{
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;
}
}
{
{
return;
}
while(pNode!=NULL)//对于单链表的判断此处while（pNode！=NULL）
{
cout<<pNode->data<<" -->";
pNode=pNode->next;
}
cout<<"NULL"<<endl;
}
int main()
{
for(int i=1;i<=10;i++)
{
}

for(int i=1;i<=10;i++)//一直删除头结点
{
}
for(int i=1;i<=10;i++)
{
}
for(int i=10;i>=0;i--)//一直删除尾结点
{
}

return 0;
}双向循环操作的考虑的东西要稍微多一点点：

基本也一样：

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
//以下为双向循环链表的操作
typedef struct DoubleListNode
{
int data;
DoubleListNode *prior,*next;
}DoubleListNode;
{
DoubleListNode *pNew=new DoubleListNode;
pNew->data=value;
pNew->prior=pNew->next=NULL;
{
pNew->next=pNew->prior=pNew;
}
else
{
pNew->prior=pNode;
pNode->next=pNew;

}
}
{
{
return ;
}
DoubleListNode *pToBeDelete=NULL;
{
}
{
}
else//删除双向链表中的其它结点
{
{
pNode=pNode->next;
}
{
pToBeDelete=pNode->next;
pNode->next=pToBeDelete->next;//这里绝对不能搞错。
pToBeDelete->next->prior=pNode;
}
}
if(pToBeDelete!=NULL)
{
delete pToBeDelete;
//pToBeDelete->prior=pToBeDelete->next=NULL;
}
}
{
{
return;
}
{
cout<<pNode->data<<" -->";
pNode=pNode->next;
}
cout<<"NULL"<<endl;
}
int main()
{
for(int i=1;i<=10;i++)
{
}

for(int i=1;i<=10;i++)//一直删除头结点
{
}
for(int i=1;i<=10;i++)
{
}
for(int i=10;i>=0;i--)//一直删除尾结点
{
}

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;

this.value = value;
}
System.out.print(" "+value);
}
}


链表对象，存放首结点 末节点
public class DoubleLinkList {

this.first = first;
this.last = last;
}

public void insertFirst(long dd){
//把first节点的后置节点置为当前节点，
if(isEmpty()){//如果是空链表 需要把last指向末尾
}else{
}

}
public void insertLast(long dd){
if(isEmpty()){
}else{
}
}

if(first.next==null){ //if only one item
last=null;       //null <-- last
}else{
first.next.pre=null;
}
first=first.next;
return  temp;
}

if(first.next==null){
first=null;
}else{
last.pre.next=null;
}
last=last.pre;
return temp;
}

public  boolean insertAfterKey(long key,long dd){
while (curr.value!=key){
curr=curr.next;
if(curr==null){
return false; //didn't find it
}
}
if(curr==last){
}else{
}
return true;
}

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):");
while (curr!=null){
curr=curr.next;
}
System.out.println("");
}

public  void displayBackWord(){
System.out.print("List (last-->first: ");
while (curr!=null){
curr=curr.pre;
}
}
public boolean  isEmpty(){
return first==null;
}
return first;
}

this.first = first;
}

return last;
}

this.last = last;
}
}




展开全文
#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(struct node)
typedef int datatype;
typedef struct node
{
datatype data;
struct node *next,*prior;
//双向链表的前插运算  在结点p之前
{
s=(struct node*)malloc(LEN);
s->data=x;
s->next=p;
s->prior=p->prior;
p->prior->next=s;
p->prior=s;

}
//双向链表的后插运算 假设双链表的结点p的后继结点为q，在结点p之后插入一个新结点s
{
s=(struct node*)malloc(LEN);
s->data=x;
s->next=p->next;
p->next->prior=s;
s->prior=p;
p->next=s;
}

//双向链表的自身删除运算
{
if(p!=0)
{
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
}
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-&...
• (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...

...