数据结构-双向链表

头文件 #ifndef __HEAD_H__ #define __HEAD_H__ #include <stdio.h> #include<string.h> #include<stdlib.h> enum passble{SUCCESS,FALSE=-1}; typedef char datatype; //双向链表节点结构体 typedef struct Node {//数据域: 数据元素 datatype data; //指针域: 上一个节点的地址 struct Node *prev; //指针域:下一个节点的地址 struct Node *next; }*Doublelink; Doublelink create_node(); Doublelink insert_head(datatype element,Doublelink head); void output(Doublelink head,int n); Doublelink head_delete(Doublelink head); Doublelink insert_rear(Doublelink head,datatype element); doublelink rear_delete(doublelink head,datatype element); #endif ~ 1双向链表 #include "head.h" //创建新节点 Doublelink create_node() { Doublelink s=(Doublelink)malloc(sizeof(struct Node)); if(NULL==s) { return NULL; } //新节点的数据与初始化 s->data=0; //新节点的两个指针域 s->next=s->prev=NULL; return s; } //头插 Doublelink insert_head(datatype element,Doublelink head) { //创建一个新节点 Doublelink s=create_node(); s->data=element; //1.链表为空 if(NULL==head) head=s; else {//2.链表存在多个节点>=1 s->next=head; head->prev=s; head=s; return head; } } //打印 void output(Doublelink head,int n) { //1.判断链表是否为空 if(NULL==head) return; //2.正向遍历 Doublelink p=head; if(n==1) { while(p->next!=NULL)//最后一个节点的数据域不打印 { printf("%c",p->data); p=p->next; } printf("%c\n",p->data); } else { //逆向遍历 while(p!=NULL) { printf("%c",p->data); p=p->prev; putchar(10); } } } //头删 Doublelink head_delete(Doublelink head) { if(NULL==head) { return head; } Doublelink del=head; head=head->next; free(del); del=NULL; return head; }//尾删 doublelink rear_delete(doublelink head) { if(NULL == head) { return head; } if (head->next=head->prev) { // 只有一个节点的情况 free(head); return NULL; } Doublelink p = head; while (p->next->next != head) { // 找到尾节点的前一个节点 p = p->next; } doublelink s=p->next; p->next=NULL; s=s->next; // 将倒数第二个节点的 next 置为 NULL free(s); // 释放尾节点 return head; }

2双向循环链表

#include "head.h" //创建新节点 Doublelink create_node() { Doublelink s=(Doublelink)malloc(sizeof(struct Node)); if(NULL==s) { return NULL; } //新节点的数据与初始化 s->data=0; //新节点的两个指针域 s->next=s->prev=s; return s; } Doublelink insert_head(datatype element,Doublelink head) { //创建一个新节点 Doublelink s=create_node(); s->data=element; //1.链表为空 if(NULL==head) head=s; else {//2.链表存在多个节点>=1 Doublelink rear=head->prev; s->next=head; head->prev=s; rear->next=s; s->prev=rear; head=s; return head; } } void output(Doublelink head,int n) { //1.判断链表是否为空 if(NULL==head) return; //2.正向遍历 Doublelink p=head; if(n==1) { do//最后一个节点的数据域不打印 { printf("%c\n",p->data); p=p->next; } }while(p->next!=p);//最后一个节点的数据域不打印 else { //逆向遍历 do { printf("%c",p->data); p=p->prev; putchar(10); }while(p!=p); } } Doublelink head_delete(Doublelink head) { if(NULL==head) { return head; } Doublelink del=head; Doublelink s=head->prev; head=head->next; head->prev=s; s->next=head; free(del); del=NULL; return head; } Doublelink insert_rear(Doublelink head,datatype element) { Doublelink s=create_node(); if(head==NULL) { head=s; } else { Doublelink p=head->prev; p->next=s; s->prev=p; s->next=head; head->prev=s; } return head; } //尾删 doublelink rear_delete(doublelink head) { if(NULL == head) { return head; } if (head->next=head->prev) { // 只有一个节点的情况 free(head); return NULL; } Doublelink p= head->prev->prev; Doublelink s=p->next; p->next=head; head->prev=p; // 将倒数第二个节点的 next 置为 NULL free(s); // 释放尾节点 s=NULL; return head; }