单循环，双向，双循环链表
单向循环链表
相比于单向链表，单向循环链表仅仅是将单向链表的尾节点指向了头节点
#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;
else return 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->next
if(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的下一个，即NULL
p->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->prev
p->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("%dn",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;
}
}