数据结构-----双向链表

一、双向循环列表

head.h

#ifndef __head_h__ #define __head_h__ #include <stdio.h> #include <string.h> #include <stdlib.h> enum { SUCCESS, FALSE=-1 }; typedef char datatype; //双向列表结构体 typedef struct Node { //存数据域 datatype data; //存上一个地址 struct Node *back; //存下一个地址 struct Node *next; }*Doublelink; //头插 Doublelink insert_head(datatype element,Doublelink head); //输出 void output_head(Doublelink head); //头删 Doublelink delete_head_link(Doublelink head); //尾插 Doublelink insert_back_link(Doublelink head,datatype element); //尾删 Doublelink delete_back_link(Doublelink head); #endif

main.c

#include "head.h" int main(int argc, const char *argv[]) { Doublelink head=NULL;//定义双向列表头节点 int n; printf("请输入n的值："); scanf("%d",&n); datatype element; for(int i=0;i<n;i++) { printf("请输入%d个数的值：",i+1); getchar(); element=getchar(); head=insert_head(element,head); } //输出 output_head(head); //头删 printf("头删后的结果为：\n"); head=delete_head_link(head); output_head(head); //尾插 printf("请输入在末尾要插入的值："); getchar(); element=getchar(); printf("尾插后的结果为：\n"); head=insert_back_link(head,element); output_head(head); //尾删 printf("尾删后的结果为：\n"); head=delete_back_link(head); output_head(head); return 0; }

test.c

#include "head.h" //创建节点 Doublelink create_node() { Doublelink s=(Doublelink)malloc(sizeof(struct Node)); if(NULL==s) return NULL; //新节点的数据域初始化 s->data=0; //指针域初始化 s->next=s->back=s; return s; } //头插 Doublelink insert_head(datatype element,Doublelink head) { //创建新节点 Doublelink s=create_node(); s->data=element; //链表为空 if(head==NULL) head=s; //存在至少一个节点 else { Doublelink rear=head->back; s->next=head; head->back=s; head=s; rear->next=head; head->back=rear; } return head; } //遍历(正向) void output_head(Doublelink head) { //链表为空 if(head==NULL) { printf("输出失败\n"); return; } else { Doublelink p=head; do { printf("%c ",p->data); p=p->next; }while(p!=head); putchar(10); } } //头删 Doublelink delete_head_link(Doublelink head) { //链表为空 if(head==NULL) { printf("删除失败\n"); return head; } else { Doublelink p=head; head=head->next; head->back=p->back; p->back->next=head; free(p); p=NULL; return head; } } //尾插 Doublelink insert_back_link(Doublelink head,datatype element) { Doublelink s=create_node(); s->data=element; if(head==NULL) head=s; Doublelink p=head; while(p->next!=head) { p=p->next; } p->next=s; s->next=head; s->back=p; head->back=s; return head; } //尾删 Doublelink delete_back_link(Doublelink head) { //判断为空 if(head==NULL) { printf("尾删失败\n"); return head; } Doublelink p=head->back; Doublelink q=p->back; q->next=head; head->back=q; free(p); p=NULL; return head; }

二、双向链表的尾删 //尾删 void delete_back_link(Doublelink head) { //判断为空 if(head==NULL) { printf("尾删失败\n"); return ; } Doublelink p=head; if(p->next==NULL) { head=delete_head_link(head); return; } while(p->next!=NULL) { p=p->next; } p->back->next=NULL; free(p); p=NULL; return ; }