单循环 双向 双循环链表

单向循环链表

相比于单向链表，单向循环链表仅仅是将单向链表的尾节点指向了头节点

#include <stdio.h>#include <stdlib.h>typedef struct node{int data; //数据域 struct node *next; //指针域 }Node;//初始化Node* InitList(){Node* head = (Node*)malloc(sizeof(Node));head->next = head;return head;}//判空int IsEmpty(Node *head) {return head->next == head;}//在尾部插入int InsertToListTail(Node *head, int data) {//新申请一个节点用于插入 Node *InsertNode = (Node*)malloc(sizeof(Node));InsertNode->data = data;//如果申请失败则返回0 if(!InsertNode) return 0;//找到尾节点 Node *p = head;while(p->next != head) p = p->next;//插入节点 InsertNode->next = p->next;p->next = InsertNode;return 1;}//删除指定节点int DelFromList(Node *head, int data) {//如果链表为空返回0 if(IsEmpty(head))return 0;//分别找到要删除节点和它的前趋节点 Node *pre = head;Node *p = head->next;while(p->data != data && p != head) {pre = pre->next;p = p->next;}//如果找不到返回0 if(p == head) return 0;//删除节点 pre->next = p->next;free(p);return 1;}//修改指定节点int UpdateList(Node *head, int index, int data) {//找到index所指的节点 Node *p = head->next;for(int i = 0; i < index && p!= head; i++ ) {p = p->next;}//如果index大于链表长度，则会在p==head是跳出循环 if(p == head) return 0;//修改数据 p->data = data;return 1;} //找到指定节点Node* FindNode(Node *head, int data) {//遍历链表找到对应节点 Node *p = head;while(p->data != data && p != head) {p = p->next;} //如果没找到返回NULL,找到了则返回对应节点 if(p == head) return NULL;elsereturn p;} //打印链表void PrintList(Node *head) {if(head->next == head) printf("空链表");Node *p = head->next;while(p != head) {printf("%d ",p->data);p = p->next;}printf("\n");}

双向链表

//定义结构体变量typedef struct node{int data;//data域存放数据struct node *prev;//prev指针域存放上一个结点的地址struct node *next;//next指针域存放下一个结点的地址}Node;

链表创建头结点[初始化]

/***创建链表，返回头指针。**/Node* initList(){Linklist head = (Linklist)malloc(sizeof(LNode));//创建头结点head->next=NULL;//将next指针域置空head->prev=NULL;//将prev指针域置空return head;//返回头结点}

/***双向链表判空操作**/int isEmpty(Linklist head){if(head->next==NULL && head->prev==NULL){//为空 return 1;}//不为空 return 0; }

链表头插法创建

断开两个连接

特殊情况：

当只存在head结点时，head的next指针域为空。

已知Head结点和p结点，上面共四步：

Head->next=p;(1)p->prev=Head;(2)Head->next->prev=p;(3)p->next=Head->next;(4)

3 4 1

/***头插法创建链表**/void ListByInsertHead(Node* head ){Node *p;//指针p用来接受数据，进行插入int x;while(scanf("%d",&x)&&x!=-1){p=(Linklist)malloc(sizeof(LNode)) ;p->data=x;//头插法//只有头结点时，头结点的next域为NULL，不存在prev指针域，第一步要放在第三步之 //前，此时未更新head->nextif(head->next!=NULL){head->next->prev=p;}p->next=head->next;//单链表头插操作head->next=p;//单链表头插操作p->prev=head;//将p的prev指针域指向head（这一步放哪都行）}return ;}

链表尾插法创建

此时有四步改动

p->next=s;(1)p=s;(2)s->prev=p;(3)s->next=p->next;(4)//还有一种写法是s->next=NULL;

3 2

/***尾插法创建链表**/void ListByInsertTail(Node* head ){Node *p,*s;//指针p用来保存尾指针位置，指针s用来存数据进行插入p=head;//只有头结点时，头结点即为最后一个结点int x;while(scanf("%d",&x)&&x!=-1){s=(Node*)malloc(sizeof(Node)) ;s->data=x;//尾插法s->next=p->next;//s的结点指向尾结点p的下一个，即NULLp->next=s;//将尾结点的next指针指向要插入的结点//第三步和第四步不能交换s->prev=p;//要插入的结点的前一个结点更新为尾结点p=s;//将尾结点更新为新插入的结点}return ;}

/***尾插法创建链表第二种写法**/void ListByInsertTail(Node* head ){Node *p,*s;//指针p用来保存尾指针位置，指针s用来存数据进行插入p=head;//只有头结点时，头结点即为最后一个结点int x;while(scanf("%d",&x)&&x!=-1){s=(Node*)malloc(sizeof(Node)) ;s->data=x;//尾插法p->next=s;//将尾结点的next指针指向要插入的结点//第二步和第三步不能交换s->prev=p;//要插入的结点的前一个结点更新为尾结点p=s;//将尾结点更新为新插入的结点}s->next=NULL;//尾结点指向为空return ;}

指定结点前插入

在q结点前插入p结点

此处共有四处改动

p->prev=q->prev;(1)q->prev->next=p;(2)p->next=q;(3)q->prev=p;(4)/***指定结点前插入（在q结点前插入p结点）**/void Insert(Node *p, Node *q){//只有等q指针前面那个结点的相关操作处理完之后才能修改q->prevp->prev=q->prev;q->prev->next=p;p->next=q;q->prev=p;}

链表删除

特殊：p为尾指针

上述有三处改动

p->prev->next=p->next;(1)p->next=p->prev(2)free(p)(3)/***删除指定结点**/void delete_Node(Node *p){p->prev->next=p->next;if(p->next!=NULL){p->next->prev=p->prev;} free(p);}

循环双向链表的实现

小思考：自己实现循环双向链表

循环双向链表和双向链表的操作基本一致，注意由于head指针的prev域和尾指针的next域不为空，因此部分操作需要增加对这两个指针的连接

双向循环链表完整代码：

#include<stdio.h>#include<stdlib.h>#include<windows.h>typedef struct node{int data;struct node *prev;struct node *next;}LNode,*Linklist;//创建链表Linklist CreatList(); //双向循环链表判空操作int isEmpty(Linklist head); //链表的创建 [头插法]void ListByInsertHead(Linklist head );//链表的创建[尾插法]void ListByInsertTail(Linklist head );//将p结点插入q结点之前 void Insert(LNode *p, LNode *q);//删除p结点void delete_Node(LNode *p); //删除链表void delete_List(LNode *p); //打印链表void print_List(Linklist head);int main(){Linklist head = CreatList();printf("%d\n",isEmpty(head));ListByInsertTail(head);print_List(head);printf("\n");//Linklist head1 = CreatList();//ListByInsertHead(head1);//print_List(head1);LNode *t = (Linklist)malloc(sizeof(LNode));t->data=10;Insert(t,head->next);print_List(head);printf("\n");delete_Node(t);print_List(head);delete_List(head);return 0;} Linklist CreatList(){Linklist head = (Linklist)malloc(sizeof(LNode));head->next=head;head->prev=head;return head;}int isEmpty(Linklist head){if(head->next==head && head->prev==head){//为空 return 1;}//不为空 return 0; }void ListByInsertHead(Linklist head ){LNode *p;int x;while(scanf("%d",&x)&&x!=-1){p=(Linklist)malloc(sizeof(LNode)) ;p->data=x;head->next->prev=p;p->next=head->next;head->next=p;p->prev=head;}return ;}void ListByInsertTail(Linklist head ){LNode *p,*s;p=head;int x;while(scanf("%d",&x)&&x!=-1){s=(Linklist)malloc(sizeof(LNode)) ;s->data=x;s->next=p->next;//增加代码：尾指针所指的下一个结点即头指针的prev修改为要插入的结点，即将头指针与新要插入的结点连接起来p->next->prev=s; p->next=s;s->prev=p;p=s;}return ;}void Insert(LNode *p, LNode *q){p->prev=q->prev;q->prev->next=p;p->next=q;q->prev=p;}void delete_Node(LNode *p){p->prev->next=p->next;//if(p->next!=NULL){ //p->next不会为空，可删去 p->next->prev=p->prev;//} free(p);}void delete_List(LNode *p){LNode *t,*temp;t=p->next;while(t!=p&&t!=p){//判断条件改为当t又绕回一圈时即链表只剩一个结点 temp=t->next;delete_Node(t);t=temp;print_List(p);printf("\n");}free(p);}void print_List(Linklist head){Linklist p;p=head->next;while(1){printf("%d ",p->data);if(p->next==head){break;}p=p->next;} system("pause"); printf("\n");while(1){printf("%d ",p->data);if(p->prev==head){break;}p=p->prev;}}

如果觉得《单循环 双向 双循环链表》对你有帮助，请点赞、收藏，并留下你的观点哦！