双向循环链表的建立，插入，删除（带头节点）

千次阅读

2018-01-03 00:28:33

#include<iostream>
#include<cstdio>
#include<malloc.h>

#define OVERFLOW -2
#define ERROR -1

typedef struct DuLNode{
    int data;
    struct DuLNode *prior,*next;
}DuLNode,*DuLinkList;

void CreateList_DuL(DuLinkList &L,int n){//头插入法建立双向循环链表
    int data;
    DuLNode *rear,*p;
    rear=L=(DuLinkList)malloc(sizeof(DuLNode));
    L->next=NULL;
    for(int i=0;i<n;i++){
        p=(DuLinkList)malloc(sizeof(DuLNode));
        scanf("%d",&data);
        p->data=data;
        p->next=rear->next;
        rear->next=p;
        p->prior=rear;
        rear=p;
    }
    rear->prior=L;
    L->prior=rear;
}

void ListInsert_Dul(DuLinkList &L,int i,int e){
    //在双向链表第i个位置插入元素e
    DuLNode *p,*q;

    p=L;
    int j=0,data;
    while(p&&j<i-1){
        p=p->next;j++;
    }
    if(!p||j>i-1)return;
    q=(DuLinkList)malloc(sizeof(DuLNode));
    q->data=e;
    q->next=p->next;
    p->next->prior=q;
    p->next=q;
    q->prior=p;
}

void ListDelete_Dul(DuLinkList &L,int i){
    DuLNode *q,*p;
    p=L;
    int j=0;
    while(p&&j<i){
        p=p->next;j++;
    }
    if(!p||j>i)return;
    p->prior->next=p->next;
    p->next->prior=p->prior;
    free(p);
}
int main(){
    DuLinkList T;
    int n;
    printf("输入个数：\n");
    scanf("%d",&n);
    printf("输入个元素：\n");
    CreateList_DuL(T,n);
    printf("插入位置与值\n");
    int pos,val;
    scanf("%d%d",&pos,&val);
    ListInsert_Dul(T,pos,val);//随便想第三个位置插入4
    printf("打印：\n");
    DuLNode *p;
    p=T->next;
    while(p){
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n删除位置\n");
    scanf("%d",&pos);
    ListDelete_Dul(T,pos);
    printf("打印：\n");
    p=T->next;
    while(p){
        printf("%d ",p->data);
        p=p->next;
    }
}

c语言数据结构

更多相关内容

数据结构--单链表-循环链表-双向循环链表--单链表中删除节点--插入节点到单向链表的理解和以及代码实现

千次阅读 2019-05-27 17:06:45

4.双向循环链表 1.单链表：何为链表？通过地址的方式，找到数据。比如到银行办理业务，业务员根据票号，来找到下一个人进行办理业务。同样地，链表的意思是，通过一个地址，找到数据。 1.1数据内容...

文章目录

1.单链表：

何为链表？

通过地址的方式，找到数据。

比如到银行办理业务，业务员根据票号，来找到下一个人进行办理业务。

同样地，链表的意思是，通过一个地址，找到数据。

1.1数据内容为int型的链表

public class LinkList{
    public static void main(String[] args){
 
        Node n1=new Node(9);
        Node n2=new Node(8);
        Node n3=new Node(7);
        //追加节点
        n1.append(n2);
        n2.append(n3);
        System.out.println(n1.next().next().getData());//7

    }

}
//构建一个节点类
class Node{
    //节点内容
    int data;
    //下一个节点
    Node next;
    public Node(int value){
        this.data=value;
    }

    //为当前节点追加下一个节点
    public void append(Node node){
        //将当前节点赋值给currentNode
        Node currentNode=this;
        //循环向后找
        while(true){
            
            Node nextNode=currentNode.next;
            //如果下一个节点为空，则退出循环
            if(nextNode==null){
                break;
            }
            //将下一个节点赋给当前节点
            currentNode=nextNode;
        }
        //因为退出循环的时候，是当下一节点为空的时候，所以把需要返回的节点追加为当前节点的下一节点
        currentNode.next=node;
    }
    //返回下一个节点
    public Node next(){
        return this.next;
    }
    //获得节点内容
    public int getData(){
        return this.data;
    }

}

1.2数据内容为数组的链表

import java.util.Arrays;
import java.util.Set;

//import com.sun.corba.se.impl.orbutil.graph.Node;
public class LinkList{
    public static void main(String[] args){
        Node n1=new Node(new int[]{1,2,4,5,6});        
        Node n2=new Node(new int[]{7,8,9,10}); 
        Node n3=new Node(new int[]{11,12,13,14});
        n1.append(n2);
        n2.append(n3);
        //System.out.println(n1.next().getdata());
        n1.next().getdata();//7,8,9,10  
        }   
        
    }

 class Node{
    //节点内容
    int[] data;
    //下一个节点
    Node next;
    public Node(int[] value){
        this.data=value;
    }
    //追加节点
    public void append(Node node){
        Node currentNode=this;
        //往后寻找
        while(true){
            Node nextNode=currentNode.next;
            if(nextNode==null){
                break;
            }
            // 追加下一节点为当前节点;
            currentNode=nextNode;
        }
            //由于当前节点的后一节点为空，因此将node放到当前节点的下一节点       
            currentNode.next=node;
    }
    //返回下一个节点
    public Node next(){
        return this.next;
    }
    public void getdata(){
        for(int i=0;i<data.length;i++){
            System.out.print(data[i]+"\t");
        }
    }
    

}

2.删除插入单链表中的节点

删除节点：

public void remove(){
        //取出下下节点
        Node newNext=next.next;
        //将下下节点  赋值给当前节点的下一节点
        this.next=newNext;

思路：

取出当前节点的下下节点，将下下节点赋值给当前节点的下一节点。那么原来当前节点的下一节点就被删除了。

插入节点：

我们插入节点只能插入当前节点的下一节点，而不能直接插入给当前节点。

思路：1.先将当前节点下一节点取出 2.再将需要插入的节点赋值给当前节点的下一节点3.把之前取出的节点作为新节点的下一节点

 //插入节点
    public void add(node){
        //取出下一节点，作为下下节点
        Node nextNode=this.next;
        //将需要插入的节点，作为当前节点的下一节点
        this.next=node;
        //将之前的下下节点作为新节点的下一节点
        node.next=newNode;
    }

3.循环链表

之前的单向链表是通过一个节点，找下一个节点，但是我们却不能通过其他节点来找第一个节点，那么循环链表的意思就是通过最后一个节点，来寻找到第一个节点。整个节点就串联起来了。

在这里插入图片描述

整个循环链表和单链很相似。只需要将下一节点变为当前节点。

import java.util.Arrays;
import java.util.Set;
/**循环链表 */

public class LinkList2{
    public static void main(String[] args){
        LoopNode n1=new LoopNode(1);        
        LoopNode n2=new LoopNode(2); 
        LoopNode n3=new LoopNode(3);
        //追加节点
        n1.add(n2);
        n2.add(n3);
        System.out.println(n3.next().getdata());
        
        
       
        
        
        }   
        
    }

 class LoopNode{
    //节点内容
    int data;
    //这里就是与单链表的区别，将下一节点初始化为当前节点
    LoopNode next=this;
    public LoopNode(int value){
        this.data=value;
    }
   
    //插入节点
    public void add(LoopNode node){
        //取出下一节点，作为下下节点
        LoopNode nextNode=this.next;
        //将需要插入的节点，作为当前节点的下一节点
        this.next=node;
        //将之前的下下节点作为新节点的下一节点
        node.next=nextNode;
    }
    
   
    //返回下一个节点
    public LoopNode next(){
        return this.next;
    }
    public int getdata(){
        return this.data;
    }
    

}

4.双向循环链表

通过每个节点可以寻找到他的上一个和下一个节点。因此叫双向。这个相较于单向循环链表，就是多了一个向前的节点。

核心代码处理解：

在这里插入图片描述

  public class DoubleLoopLinkList{
    public static void main(String[] args){
       DoubleNode n1=new DoubleNode(2);
       DoubleNode n2=new DoubleNode(3);
       DoubleNode n3=new DoubleNode(4);
       n1.after(n2);
       n2.after(n3);
       System.out.println(n1.next().getdata());//3
       System.out.println(n2.pre().getdata());//2

    }
}
class DoubleNode{
    //节点数据
    int data;
    //上一个节点
    DoubleNode pre=this;
    DoubleNode next=this;
    
    public DoubleNode(int value){
        this.data=value;
    }
    /*增加节点   双向链表核心代码*/
    public void after(DoubleNode node){
        //原来节点的下一节点，
        DoubleNode nextNext=next;
        //将新节点作为当前节点的下一节点
        this.next=node;
        //把新节点作为当前节点的前一节点；
        node.pre=this;
        //让原来的节点的下一节点作为当前节点的下一节点
        node.next=nextNext;
       //将原来节点的上一节点作为新节点
        nextNext.pre=node;
    } 
    //下一个节点
    public DoubleNode next(){
         return this.next;
    }
    //上一个节点
    public DoubleNode pre(){
        return this.pre;
    }
    public int getdata(){
        return this.data;
    }
    
}

收起

展开全文

在双向链表指定节点后插入节点
千次阅读 2021-05-25 02:52:35

要在列表中的指定节点之后插入节点，需要跳过所需数量的节点以便到达目标节点，然后根据需要调整指针。为此，请参考使用以下步骤。为新节点分配内存。请使用以下语句。ptr = (struct node *)malloc(sizeof(struct ...

要在列表中的指定节点之后插入节点，需要跳过所需数量的节点以便到达目标节点，然后根据需要调整指针。

为此，请参考使用以下步骤。

为新节点分配内存。请使用以下语句。ptr = (struct node *)malloc(sizeof(struct node));

使用指针temp遍历列表以跳过所需数量的节点以到达指定节点。temp=head;

for(i=0;i

{

temp = temp->next;

// the temp will be null if the list doesn't last long up to mentioned location

if(temp == NULL)

{

return;

}

}

temp将指向for循环结束时的指定节点。要在此节点之后插入新节点，因此需要在此处调整ptr指针。使ptr的下一个指针指向temp的下一个节点。ptr -> next = temp -> next;

使新节点ptr的prev指针指向temp。ptr -> prev = temp;

使temp指针指向新节点ptr。temp -> next = ptr;

使temp节点的pre指针指向新节点。temp -> next -> prev = ptr;

算法

第1步：IF PTR = NULL

提示：OVERFLOW

转到第15步

[IF结束]

第2步：设置NEW_NODE = PTR

第3步：SET PTR = PTR - > NEXT

第4步：设置NEW_NODE - > DATA = VAL

第5步：SET TEMP = START

第6步：SET I = 0

第7步：重复第8步到第10步直到 I

第8步：SET TEMP = TEMP - > NEXT

第9步：如果TEMP = NULL

第10步：提示 “比所需的元素少”

转到第15步

[结束]

[循环结束]

第11步：设置NEW_NODE - > NEXT = TEMP - > NEXT

第12步：设置NEW_NODE - > PREV = TEMP

第13步：设置TEMP - > NEXT = NEW_NODE

第14步：设置TEMP - > NEXT - > PREV = NEW_NODE

第15步：退出

示意图如下 -

使用C语言实现的示意代码 -

#include

#include

void insert_specified(int);

void create(int);

struct node

{

int data;

struct node *next;

struct node *prev;

};

struct node *head;

void main()

{

int choice, item, loc;

do

{

printf("Enter the item which you want to insert?\n");

scanf("%d", &item);

if (head == NULL)

{

create(item);

}

else

{

insert_specified(item);

}

printf("Press 0 to insert more ?\n");

scanf("%d", &choice);

} while (choice == 0);

}

void create(int item)

{

struct node *ptr = (struct node *)malloc(sizeof(struct node));

if (ptr == NULL)

{

printf("OVERFLOW");

}

else

{

if (head == NULL)

{

ptr->next = NULL;

ptr->prev = NULL;

ptr->data = item;

head = ptr;

}

else

{

ptr->data = item;printf("Press 0 to insert more ?\n");

ptr->prev = NULL;

ptr->next = head;

head->prev = ptr;

head = ptr;

}

printf("Node Inserted\n");

}

}

void insert_specified(int item)

{

struct node *ptr = (struct node *)malloc(sizeof(struct node));

struct node *temp;

int i, loc;

if (ptr == NULL)

{

printf("OVERFLOW\n");

}

else

{

printf("Enter the location\n");

scanf("%d", &loc);

temp = head;

for (i = 0;i < loc;i++)

{

temp = temp->next;

if (temp == NULL)

{

printf("can't insert\n");

return;

}

}

ptr->data = item;

ptr->next = temp->next;

ptr->prev = temp;

temp->next = ptr;

temp->next->prev = ptr;

printf("Node Inserted\n");

}

}

执行上面示例代码，得到以下结果 -

Enter the item which you want to insert?

12

Node Inserted

Press 0 to insert more ?

0

Enter the item which you want to insert?

90

Node Inserted

Press 0 to insert more ?

2

¥ 我要打赏

纠错/补充

收藏

加QQ群啦，易百教程官方技术学习群

注意：建议每个人选自己的技术方向加群，同一个QQ最多限加 3 个群。

收起

展开全文