头疼的算法与数据结构——双向循环链表

    xiaoxiao2021-03-25  49

    一:双向循环链表的简介

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表

    双链表的结构定义如下:

    struct node{ int data;//数据域 struct node* next;//后继 struct node* pre;//前驱 };

    整体结构:

    二:双向循环链的初始化

    //创建链表 void creatList(Node** h) { Node* pn=NULL;//存储新的节点 Node* p=NULL;//头节点的替身 int d; printf("请输入数据\n"); scanf("%d",&d); pn=creteNode(d); pn->next=NULL;//next指向空 pn->pre=NULL;//pre指向空 sum=1; *h=pn; p=*h; while(1) { printf("请输入数据\n"); scanf("%d",&d); if(d==0) { //创建到最后一个节点时,最后一个节点next为头节点 p->next=*h; (*h)->pre=p;//头节点的pre为最后一个节点 break; } pn=creteNode(d); p->next=pn; pn->pre=p; p=p->next; sum++;//元素个数++ } } 创建了一个链表。

    三:插入操作

    原理如图: 代码: //头插法 int addFont(int d,Node** h)//修改头节点 传入二级指针 { int i,n=sum; Node* pn=NULL; pn=creteNode(d); Node* p=*h; for(i=0;i<n-1;i++) { p=p->next; } //p为最后一个节点 pn->next=*h;//新节点成为头节点 p->next=pn;//最后一个节点p的下一个节点为新节点pn pn->pre=p;//新的头节点的pre为p (*h)->pre=pn;//原头节点的前一个节点为新节点 *h=pn;//新节点为头节点 sum++; } //插入 int insertNode(int n,int d,Node** h)//在n位置插入d { if((n<1)||(*h==NULL)||(n>sum)) { printf("插入位置不合法||链表为空!\n"); return 0; } Node* pn=creteNode(d);//创建新的节点 //插入位置为1,即插入头节点的位置 if(n==1) { addFont(d,h);//调用头插法 return 0; } else if(n==sum) { addBack(d,*h); return 0; } else { Node* pf=findNode(*h,n-1); //找到要删除的节点的前一个节点 pn->next=pf->next;//前一个节点的next等于新的节点的next pf->next->pre=pn;//pf的next节点的pre应该为pn pf->next=pn;//前一个节点的next等于新的节点 pn->pre=pf;//新节点的前一个节点为找到的前一个节点pf sum++; return 1; } }

    四:删除操作

    原理图: 代码: //删除头节点 int DelectFont(Node** h) { //DelectFont(h); int i, n1=sum; Node* p=*h; Node* pd=NULL;; for(i=0;i<n1-1;i++) { p=p->next; } //p为最后一个节点 pd=*h; *h=pd->next;//头节点的下一个节点成头节点 p->next=*h;//最后一个节点的next为头节点 (*h)->pre=p;//pd节点成为了头节点,它的前驱为p sum--;//元素个数-1 return 0; } //删除第n个位置的元素 int deleteNode(int n,Node** h) { //int i;//循环变量 //判断头节点是否为空,位置是不是合法 if((*h==NULL)||(n<1)||(n>sum)) { printf("删除的链表为空||删除的位置不合法!so 插入失败\n"); return 0; } Node* pd=NULL; //删除头节点 if(n==1) { DelectFont(h); return 0; } //删除 //找到要删除的节点的前一个节点 Node* pf=findNode(*h,n-1); pd=pf->next;//将要删除的节点的给pd pf->next=pd->next;//将删除元素的前一个的next指向删除元素的后一个元素 pd->pre=NULL;//pd的pre指向空 pd->next->pre=pf;//将删除元素的后一个元素的前驱给pf pd->next=NULL;//pdnext指向空 sum--; return 1; }

    五:整体代码

    #include <stdio.h> #include <stdlib.h> struct node{ int data; struct node* next; struct node* pre; }; typedef struct node Node; #define SIZE sizeof(Node) int sum;//节点个数 Node* creteNode(int d);//创建节点 void creatList(Node** h);//创建链表 Node* findNode(Node* h,int n);//查找某个节点的位置 int addBack(int d,Node* h);//末尾增加一个新的节点 int addFont(int d,Node** h);//修改头节点 传入二级指针 int insertNode(int n,int d,Node** h);//在n位置插入d int DelectFont(Node** h);//删除头节点 int deleteNode(int n,Node** h);//删除第n个位置的元素 void print(Node* h);//打印链表 //创建节点 Node* creteNode(int d) { Node* pn=(Node*)malloc(SIZE); pn->data=d; pn->next=NULL; pn->pre=NULL; return pn; } //创建链表 void creatList(Node** h) { Node* pn=NULL;//存储新的节点 Node* p=NULL;//头节点的替身 int d; printf("请输入数据\n"); scanf("%d",&d); pn=creteNode(d); pn->next=NULL;//next指向空 pn->pre=NULL;//pre指向空 sum=1; *h=pn; p=*h; while(1) { printf("请输入数据\n"); scanf("%d",&d); if(d==0) { //创建到最后一个节点时,最后一个节点next为头节点 p->next=*h; (*h)->pre=p;//头节点的pre为最后一个节点 break; } pn=creteNode(d); p->next=pn; pn->pre=p; p=p->next; sum++;//元素个数++ } } //查找某个节点的位置 Node* findNode(Node* h,int n) { int i; if((h==NULL)||(n<0)||(n>sum)) { printf("查找位置不合法||链表为空!\n"); return NULL; } if(n==1) { return h; } for(i=1;i<n;i++) { h=h->next; } return h; } //末尾增加一个新的节点 int addBack(int d,Node* h) { int i,n=sum; Node *pn=NULL; pn=creteNode(d); Node* p=h; for(i=0;i<n-1;i++) { p=p->next; } //此时的p指向了最后一个元素 p->next=pn;//最后一个节点p的next为新节点 pn->pre=p;//新节点的前一个节点为p pn->next=h;//pn的最后一个节点为头节点 h->pre=pn;//头节点的pre为新节点 sum++; } //头插法 int addFont(int d,Node** h)//修改头节点 传入二级指针 { int i,n=sum; Node* pn=NULL; pn=creteNode(d); Node* p=*h; for(i=0;i<n-1;i++) { p=p->next; } //p为最后一个节点 pn->next=*h;//新节点成为头节点 p->next=pn;//最后一个节点p的下一个节点为新节点pn pn->pre=p;//新的头节点的pre为p (*h)->pre=pn;//原头节点的前一个节点为新节点 *h=pn;//新节点为头节点 sum++; } //插入 int insertNode(int n,int d,Node** h)//在n位置插入d { if((n<1)||(*h==NULL)||(n>sum)) { printf("插入位置不合法||链表为空!\n"); return 0; } Node* pn=creteNode(d);//创建新的节点 //插入位置为1,即插入头节点的位置 if(n==1) { addFont(d,h);//调用头插法 return 0; } else if(n==sum) { addBack(d,*h); return 0; } else { Node* pf=findNode(*h,n-1); //找到要删除的节点的前一个节点 pn->next=pf->next;//前一个节点的next等于新的节点的next pf->next->pre=pn;//pf的next节点的pre应该为pn pf->next=pn;//前一个节点的next等于新的节点 pn->pre=pf;//新节点的前一个节点为找到的前一个节点pf sum++; return 1; } } //删除头节点 int DelectFont(Node** h) { //DelectFont(h); int i, n1=sum; Node* p=*h; Node* pd=NULL;; for(i=0;i<n1-1;i++) { p=p->next; } //p为最后一个节点 pd=*h; *h=pd->next;//头节点的下一个节点成头节点 p->next=*h;//最后一个节点的next为头节点 (*h)->pre=p;//pd节点成为了头节点,它的前驱为p sum--;//元素个数-1 return 0; } //删除第n个位置的元素 int deleteNode(int n,Node** h) { //int i;//循环变量 //判断头节点是否为空,位置是不是合法 if((*h==NULL)||(n<1)||(n>sum)) { printf("删除的链表为空||删除的位置不合法!so 插入失败\n"); return 0; } Node* pd=NULL; //删除头节点 if(n==1) { DelectFont(h); return 0; } //删除 //找到要删除的节点的前一个节点 Node* pf=findNode(*h,n-1); pd=pf->next;//将要删除的节点的给pd pf->next=pd->next;//将删除元素的前一个的next指向删除元素的后一个元素 pd->pre=NULL;//pd的pre指向空 pd->next->pre=pf;//将删除元素的后一个元素的前驱给pf pd->next=NULL;//pdnext指向空 sum--; return 1; } //打印链表 void print(Node* h) { int i,n=sum; printf("list:\n"); Node* p=h; printf("正序遍历:\n"); for(i=1;i<=n;i++) { printf("%d ",p->data); p=p->next; } //上面遍历到第一个节点 printf("\n"); printf("反序遍历:\n"); for(i=1;i<=n;i++) { printf("%d ",p->pre->data); p=p->pre; } printf("\n"); } int main() { Node* head=NULL; creatList(&head); deleteNode(2,&head); print(head); return 0; }
    转载请注明原文地址: https://ju.6miu.com/read-35758.html

    最新回复(0)