01.顺序结构
main.c
#include "seq.h"
int main(){
seq_p S=create_seqlist();
inputall(S);
insert_head(S);
delete_head(S);
insert_tail(S);
delete_tail(S);
insert_pos(S);
delete_pos(S);
update(S);
int ret=findpos(S);
printf("主函数输出查找后的列表%d\n",ret);
seq_free(&S);
output(S);
return 0;
}
seq.c
#include "seq.h"
seq_p create_seqlist()
{
seq_p S=(seq_p)malloc(sizeof(seq_list));
if(S==NULL){
return NULL;
}
bzero(S,sizeof(seq_list));
return S;
}
int empty_seq(seq_p S)
{
if(S==NULL){
printf("入参为空\n");
return -2;
}
return S->len==0?1:0;
}
int full_seq(seq_p S)
{
if(S==NULL){
printf("入参为空\n");
return -2;
}
return S->len==MAX?1:0;
}
//输出数据函数
void output(seq_p S)
{
if(S==NULL){return;}
int n=empty_seq(S);
if(n==1){
printf("02:顺序列表为空，没有数据可以删除\n");
return;
}
int i;
for(i=0;i<S->len;++i){
printf("%d ",S->arr[i]);
}
puts("");
}
//输入数据函数
seq_p input(seq_p S)
{
printf("请输入您需要插入的数据:");
scanf("%d",&S->number);
return S;
}
//先插入数据中的顺序列表
seq_p inputall(seq_p S)
{
printf("请输入您要放入空列表中的个数:");
scanf("%d",&S->num1);
printf("请输入数据:");
getchar();
for(int i=0;i<S->num1;++i){
scanf("%d",&S->arr[i]);
S->len++;
}
return S;
}
//头插
seq_p insert_head(seq_p S)
{
if(S==NULL){return NULL;}
int m=full_seq(S);
if(m==1){
printf("01:顺序列表已满,不能插入数据\n");
output(S);
return S;
}else if(m==0){
input(S);
int i;
for(i=S->len-1;i>=0;--i){
S->arr[i+1]=S->arr[i];
}
S->arr[0]=S->number;
S->len++;
printf("01:输出插入头部数据的顺序列表:\n");
output(S);
return S;
}
}
//头删
seq_p delete_head(seq_p S)
{
if(S==NULL){return NULL;}
int n=empty_seq(S);
if(n==1){
printf("02:顺序列表为空，没有数据可以删除\n");
return S;
}else if(n==0){
for(int i=1;i<S->len;++i){
S->arr[i-1]=S->arr[i];
}
S->len=S->len-1;
printf("02:输出删除头部数据的顺序列表\n");
output(S);
return S;
}
}
//尾插
seq_p insert_tail(seq_p S)
{
if(S==NULL){return NULL;}
int m=full_seq(S);
if(m==1){
printf("03:顺序列表已满,不能插入尾部数据\n");
output(S);
return S;
}else if(m==0){
input(S);
S->arr[S->len]=S->number;
S->len++;
printf("03:输出插入尾部数据的顺序列表\n");
output(S);
return S;
}
}
//尾删
seq_p delete_tail(seq_p S)
{
if(S==NULL){return NULL;}
int n=empty_seq(S);
if(n==1){
printf("04:顺序列表为空，尾部没有数据可以删除\n");
return S;
}else if(n==0){
S->arr[S->len]=0;
S->len=S->len-1;
printf("04:输出删除尾部数据的顺序列表:\n");
output(S);
return S;
}
}
seq_p insert_pos(seq_p S)
{
if(S==NULL){return NULL;}
int m=full_seq(S);
if(m==1){
printf("05:顺序列表已满,不能插入按位置插入数据\n");
output(S);
return S;
}else if(m==0){
int number,pos;
printf("05:请输入您需要插入的数据和位置:");
scanf("%d%d",&number,&pos);
if(pos<0||pos>S->len){
printf("位置不合理.\n");
return S;
}
int i;
for(i=S->len-1;i>=pos;--i){
S->arr[i+1]=S->arr[i];
}
S->arr[pos]=number;
S->len++;
printf("05:输出按位置插入数据的顺序列表:\n");
output(S);
return S;
}
}
seq_p delete_pos(seq_p S)
{
if(S==NULL){return NULL;}
int n=empty_seq(S);
if(n==1){
printf("06:顺序列表为空,不能删除按位置插入数据\n");
output(S);
return S;
}else if(n==0){
int number,pos;
printf("06:请输入您需要删除的数据和位置:");
scanf("%d%d",&number,&pos);
if(pos<0||pos>=S->len)
{
printf("位置不合理\n");
}
int i;
for(i=pos+1;i<=S->len;++i){
S->arr[i-1]=S->arr[i];
}
S->len--;
printf("06:输出按位置删除数据的顺序列表:\n");
output(S);
return S;
}
}
//12.按位置修改元素
seq_p update(seq_p S)
{
if(S==NULL){return NULL;}
int n=empty_seq(S);
if(n==1){
printf("12:顺序列表为空,不能按位置修改数据\n");
output(S);
return S;
}else if(n==0){
int number,pos;
printf("12:请输入您需要修改的位置和数据:");
scanf("%d%d",&number,&pos);
if(pos<0||pos>=S->len)
{
printf("位置不合理\n");
}
S->arr[pos-1]=number;
printf("12:输出按位置修改数据的顺序列表:\n");
output(S);
return S;
}
}
//13.按值查找返回下标
int findpos(seq_p S)
{
if(S==NULL){return -1;}
int n=empty_seq(S);
if(n==1){
printf("13:顺序列表为空,不能按数据查找下标\n");
output(S);
return -1;
}else if(n==0){
int number,pos;
printf("13:请输入您需要查找的数据");
scanf("%d",&number);
for(int i=0;i<S->len;++i){
if(S->arr[i]==number){
pos=i;
printf("13_01:查找数据%d存在顺序列表中下标%d\n",number,pos);
printf("13_02:输出查找后数据的顺序列表:\n");
output(S);
return pos;
}
}
printf("13_03:查找数据%d不存在顺序列表中\n",number);
return -2;
printf("13_04:输出查找后数据的顺序列表:\n");
output(S);
}
}
//释放顺序表
# if 0
void seq_free(seq_p S)
{
printf("释放顺序列表前数据:\n");
output(S);
if(S!=NULL){
free(S);
}
printf("%p\n",S);
return;
}
#endif
#if 1
void seq_free(seq_p *S)
{
printf("100:释放顺序列表前数据:\n");
output(*S);
//必须先判断S的值，再判断*S的值
if(S==NULL||*S==NULL)
{
printf("入参不合理\n");
return;
}
free(*S);
*S=NULL;
printf("100:释放顺序列表后数据\n");
printf("%p\n",S);
return;
}
#endif
seq.h
#ifndef __SEQ_H__
#define __SEQ_H__
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 6
typedef struct seq_list
{
int arr[MAX];
int len;
int num1;//开始输入数组中个数
int number;//输入数组中的数据
int pos;//插入数组的位置
}seq_list,*seq_p;
seq_p create_seqlist();
int empty_seq(seq_p S);
int full_seq(seq_p S);
void output(seq_p S);
seq_p input(seq_p S);
seq_p inputall(seq_p S);
seq_p insert_head(seq_p S);
seq_p delete_head(seq_p S);
seq_p insert_tail(seq_p S);
seq_p delete_tail(seq_p S);
void seq_free(seq_p *S);
seq_p insert_pos(seq_p S);
seq_p delete_pos(seq_p S);
seq_p update(seq_p S);
int findpos(seq_p S);
#endif
makefile
EXE=seq
Objs=$(patsubst %.c,%.o,$(wildcard *.c))
CC=gcc
CFlags=-c -o
all:$(EXE)
$(EXE):$(Objs)
$(CC) $^ -o $@
%.o:%c
$(CC) $^ $(CFlags) $@
.PHONY:clean
clean:
rm -f $(Objs) $(EXE)
02.单向链表
main.c
#include "link.h"
int main()
{
node_p H = create_link();
insert_head(H,12);
insert_head(H,34);
insert_head(H,70);
insert_head(H,6);
show_link(H);
printf("第2个位置的元素为%d\n",search_pos(H,2));
update_value(H,12,100);
show_link(H);
reverse_link(H);
printf("逆置后\n");
show_link(H);
return 0;
}
link.c
#include "link.h"
//1、申请单链表(头结点)
node_p create_link()
{
node_p H = (node_p)malloc(sizeof(node));
if(H==NULL)
{
return NULL;
}
H->next = NULL;
H->len = 0; //当只有头结点时，长度为0
return H;
}
//2、申请数据结点
node_p create_node(int value)
{
node_p new_node = (node_p)malloc(sizeof(node));
if(new_node==NULL)
{
printf("申请空间失败\n");
return NULL;
}
new_node->data = value; //给数据结点的数据域赋值
new_node->next = NULL; //数据节点的指针域赋值
return new_node;
}
//3、判空
int empty_link(node_p H)
{
if(H==NULL){return -1;}
return H->next==NULL?1:0;
}
//4、头插
void insert_head(node_p H,int value)
{
if(H==NULL)
{
printf("入参为空，请检查\n");
return;
}
//申请新结点
node_p new = create_node(value);
//让新结点指向原来头结点的后继结点
new->next = H->next;
//让头结点指向新结点
H->next = new;
//头结点保存的链表长度自增
H->len++;
}
//5、尾插
void insert_tail(node_p H,int value)
{
if(H==NULL)
{
printf("入参为空，请检查\n");
return;
}
//1、找到尾结点
node_p p = H;
//尾结点的条件p->next==NULL;
while(p->next!=NULL)
{
p = p->next; //找下一个结点
}
//2、申请新的数据结点
node_p new = create_node(value);
//3、让最后一个结点的指针域指向新结点
p->next = new;
//4、因为新结点的指针域在申请后已经置NULL了，无需再次重置
H->len++;
}
//6、输出单向链表
void show_link(node_p H)
{
if(H==NULL){return;}
if(empty_link(H))
{
printf("链表为空，无需数超出\n");
return;
}
//从第一个结点开始输出，
//到最后一个结点结束，最后一个结点需要进入循环
node_p p = H->next;
while(p!=NULL)
{
printf("%d->",p->data);
p = p->next;
}
//退出循环说明p走到了NULL，遍历结束整条链表
printf("NULL\n");
}
//7、头删
void delete_head(node_p H)
{
if(H==NULL){return;}
if(empty_link(H)){return;}
//1、保存要删除结点的首地址
node_p dele = H->next;
//2、让头结点指向原来的第二个结点
H->next = H->next->next; //H->next = dele->next;
free(dele);
H->len--;
}
//8、尾删
void delete_tail(node_p H)
{
if(H==NULL){return;}
if(empty_link(H)){return;}
//由于是单向链表只能向后查找
//所以需要找到倒数第二个结点
node_p p = H;
while(p->next->next!=NULL)
{
p = p->next;
}
//退出循环说明找到倒数第二个结点
node_p dele = p->next; //保存倒数第一个结点
p->next = NULL; //给倒数第二个结点的指针域置空
free(dele);
H->len--;
}
//9、按位置插入
void insert_pos(node_p H,int pos,int value)
{
if(H==NULL){return;}
//第一个循环变量i记录位置
if(pos<=0)
{
printf("位置不合理\n");
return;
}
int i = 0;
//定义指针循环结点
node_p p = H;
for(i=0,p=H;i<pos-1;i++,p=p->next)
{
//判断位置不合理的情况
if(p==NULL)
{
printf("插入位置不合理\n");
return;
}
}
node_p new = create_node(value);
//新结点指向pos位置结点
new->next = p->next;
//pos-1位置结点，指向新结点
p->next = new;
H->len++;
}
//10、按位置删除
void dele_pos(node_p H,int pos)
{
if(H==NULL){return;}
if(pos<1)
{
printf("位置不合理\n");
return;
}
int i;
node_p p;
//删除pos位置还是找到pos-1位置结点
for(i=0,p=H;i<pos-1;i++,p=p->next);
//找到pos-1位置结点后，判断是否有pos位置的结点
if(p->next==NULL)
{
printf("位置不合理\n");
return;
}
//保存要删除结点的首地址
node_p dele = p->next;
p->next = p->next->next; //p->next = dele->next;
free(dele);
H->len--;
}
//11、按位置查找返回元素的值
int search_pos(node_p H,int pos)
{
if(H==NULL){return -2;}
if(pos<1){return -1;}
if(empty_link(H)){return -3;}
int i;
node_p p;
for(i=1,p=H->next;i!=pos;i++,p=p->next)
{
if(p==NULL)
{
printf("位置不合理\n");
return -1;
}
}
return p->data;
}
//12、按值修改
void update_value(node_p H,int value,int new_value)
{
if(H==NULL){return;}
if(empty_link(H)){return;}
node_p p = H->next;
//循环整条链表
for(;p!=NULL;p=p->next)
{
if(p->data==value)
{
p->data = new_value;
return;
}
}
}
//13、逆置
void reverse_link(node_p H)
{
if(H==NULL){return;}
if(empty_link(H)){return;}
if(H->next->next==NULL){return;}
//提前将第二个结点开始链表保存下来
node_p p = H->next->next;
node_p q;
//让原来的第一个结点变成现在的最后一个结点
H->next->next = NULL;
//循环头插
//只要p的指向的结点不为空说明要头插
while(p!=NULL)
{
//先保留下一个要头插结点的首地址
q = p->next;
//头插
p->next = H->next;
H->next = p;
p = q; //让p指向下一个要头插的结点
}
}
link.h
#ifndef __LINK_H__
#define __LINK_H__
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
union
{
int data; //数据节点的数据域
int len; //头结点的长度
};
struct node *next;
}node,*node_p;
//1、申请单链表(头结点)
node_p create_link();
//2、申请数据结点
node_p create_node(int value);
//3、判空
int empty_link(node_p H);
//4、头插
void insert_head(node_p H,int value);
//5、尾插
void insert_tail(node_p H,int value);
//6、输出单向链表
void show_link(node_p H);
//7、头删
void delete_head(node_p H);
//8、尾删
void delete_tail(node_p H);
//9、按位置插入
void insert_pos(node_p H,int pos,int value);
//10、按位置删除
void dele_pos(node_p H,int pos);
//11、按位置查找返回元素的值
int search_pos(node_p H,int pos);
//12、按值修改
void update_value(node_p H,int value,int new_value);
//13、逆置
void reverse_link(node_p H);
#endif
03.单向循环链表
main.c
#include "loop.h"
int main()
{
node_p H = create_loop();
insert_head(H,67);
insert_head(H,90);
insert_head(H,34);
insert_head(H,8);
show_loop(H);
printf("H->next=%p\n",H->next);
H = delete(H); //删除头结点后链表已经没有头结点了
//H需要重新被赋值
show_no_head(H);
return 0;
}
circle.c
#include "loop.h"
//1、申请单向循环链表
node_p create_loop()
{
node_p H = (node_p)malloc(sizeof(node));
if(H==NULL)
{
printf("申请空间失败\n");
return NULL;
}
H->len=0;
H->next = H;
return H;
}
//2、申请结点
node_p create_node(int value)
{
node_p new = (node_p)malloc(sizeof(node));
new->next = NULL;
new->data = value;
return new;
}
//3、判空
int empty_loop(node_p H)
{
if(H==NULL){return -1;}
return H->next==H?1:0;
}
//4、头插
void insert_head(node_p H,int value)
{
if(H==NULL){return;}
node_p new = create_node(value);
//新结点的后继指向头结点的后继
new->next = H->next;
H->next = new;
H->len++;
}
//5、尾插
void insert_tail(node_p H,int value)
{
if(H==NULL){return;}
node_p p=H; //p用于遍历链表，找到最后一个结点
while(p->next!=H)
{
p=p->next;
}
node_p new = create_node(value);
//退出循环后p指向最后一个结点
p->next = new;
new->next=H;
//new->next = p->next;
//p->next = new;
H->len++;
}
//6、头删
void dele_head(node_p H)
{
if(H==NULL){return;}
if(empty_loop(H)){return;}
//保存要删除结点的首地址
node_p p=H->next;
//让头结点指向原来的第二个结点
H->next=p->next;
free(p);
H->len--;
return;
}
//7、尾删
void dele_tail(node_p H)
{
if(H==NULL){return;}
if(empty_loop(H)) {return;}
node_p p=H;
//尾删要找倒数第二个结点
while(p->next->next!=H)
{
p=p->next;
}
//循环退出时p指向倒数第二个节点
node_p q=p->next;
p->next=H;
free(q);
//free(p->next); //先释放最后一个结点
//p->next = H;
H->len--;
}
//8、输出
void show_loop(node_p H)
{
if(H==NULL){return;}
if(empty_loop(H)){return;}
node_p p = H->next;
while(p!=H)
{
printf("%d->",p->data);
p = p->next;
}
printf("H\n");
}
//9、删除单向循环链表的头结点
//删除头结点后需要返回给主调函数处新的链表的头
node_p delete(node_p H)
{
if(H==NULL){return NULL;}
if(empty_loop(H)){return NULL;}
//保存第一个结点的首地址
node_p p = H->next;
//找到最后一个结点
node_p tail = H->next;
while(tail->next!=H)
{
tail=tail->next;
}
//让最后一个结点的后继节点变成原来的第一个结点
tail->next = p;
//释放头结点
free(H);
return p;
}
//10、删除头结点后的单向循环链表的输出
void show_no_head(node_p H)
{
if(H==NULL){return;}
//不需要再判空
//因为没有头结点了传过来的结点只要不是空说明链表中就有元素
node_p p = H;
do
{
printf("%d->",p->data);
p = p->next;
}while(p!=H);
printf("H\n");
//需要第一次循环时不判断条件
//只能使用do··while
}
circle.h
#ifndef __LOOP_H__
#define __LOOP_H__
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
union
{
int len;
int data;
};
struct node *next;
}node,*node_p;
//1、申请单向循环链表
node_p create_loop();
//2、申请结点
node_p create_node(int value);
//3、判空
int empty_loop(node_p H);
//4、头插
void insert_head(node_p H,int value);
//5、尾插
void insert_tail(node_p H,int value);
//6、头删
void dele_head(node_p H);
//7、尾删
void dele_tail(node_p H);
//8、输出
void show_loop(node_p H);
node_p delete(node_p H);
//10、删除头结点后的单向循环链表的输出
void show_no_head(node_p H);
#endif
03.双向链表
main.c
#include "double.h"
int main()
{
node_p H = create_double();
insert_head(H,12);
insert_head(H,34);
insert_head(H,90);
show(H);
insert_pos(H,3,24);
show(H);
dele_pos(H,0);
show(H);
des_double(&H);
printf("释放后\n");
show(H);
printf("H=%p\n",H);
return 0;
}
double.c
#include "double.h"
//1、创建双向链表
node_p create_double()
{
node_p H=(node_p)malloc(sizeof(node));
if(H==NULL)
{
return NULL;
}
H->len=0;
H->next=NULL;
H->pri=NULL;
return H;
}
//2、创建结点
node_p create_node(int data)
{
node_p new = (node_p)malloc(sizeof(node));
if(new==NULL){return NULL;}
new->data = data;
new->pri = NULL;
new->next = NULL;
return new;
}
//3、判空
int empty_double(node_p H)
{
if(H==NULL){return -1;}
return H->next==NULL;
}
//4、头插
void insert_head(node_p H,int value)
{
if(H==NULL){return;}
node_p new = create_node(value);
//新结点的后继保存原来头结点的后继
new->next = H->next;
//新结点的前驱指向头结点
new->pri = H;
//头结点后继节点的前驱指向新结点
if(H->next!=NULL)
{
H->next->pri = new;
}
//头结点的后继指向新结点
H->next = new;
H->len++;
}
//5、尾插
void insert_tail(node_p H,int value)
{
if(H==NULL)
{return;}
node_p p = H;
while(p->next!=NULL)
{
p = p->next;
}
node_p new = create_node(value);
//新结点的前驱指向尾结点
new->pri = p;
//尾结点的后继指向新结点
p->next = new;
H->len++;
}
//6、输出
void show(node_p H)
{
if(H==NULL){return;}
if(empty_double(H)){return;}
node_p p = H->next;
while(p)
{
printf("%d->",p->data);
p = p->next;
}
printf("NULL\n");
}
//7、任意位置插入
void insert_pos(node_p H,int pos,int value)
{
if(H==NULL){return;}
if(pos<=0){return;}
//找到pos-1位置的结点
int i;node_p p;
for(i=0,p=H;i<pos-1;i++,p=p->next)
{
if(p==NULL)
{
printf("位置不合理\n");
return;
}
}
//退出循环时p指向pos-1位置的结点
if(p==NULL)
{
printf("位置不合理\n");
return;
}
node_p new = create_node(value);
new->next = p->next;
new->pri = p;
if(p->next!=NULL)
{
p->next->pri = new;
}
p->next = new;
H->len++;
}
//8、头删
void dele_head(node_p H)
{
if(H==NULL){return;}
if(empty_double(H)){return;}
//保存要删除结点的首地址
node_p del = H->next;
//如果链表中节点个数多于一
if(del->next!=NULL)
{
del->next->pri = H;
}
//让头结点的后继保存第一个结点的后继
H->next = del->next;
free(del);
H->len--;
}
//9、尾删
void dele_tail(node_p H)
{
if(H==NULL){return;}
if(empty_double(H)){return;}
//找到最后一个结点
node_p p = H;
while(p->next!=NULL)
{
p = p->next;
}
//退出循环时p是最后一个结点
//让倒数第二个结点的后继指向NULL
p->pri->next = NULL;
free(p);
H->len--;
}
//10、按位置删除
void dele_pos(node_p H,int pos)
{
if(H==NULL){return;}
if(empty_double(H)){return;}
if(pos<=0){return;}
//找到pos位置的结点
int i;node_p p;
for(i=0,p=H;i<pos;i++,p=p->next)
{
if(p==NULL)
{
printf("位置不合理\n");
return;
}
}
//循环结束p指向pos位置的结点
if(p==NULL)
{
printf("位置不合理\n");
return;
}
//pos+1结点的前驱指向pos-1结点
if(p->next!=NULL)
{
p->next->pri = p->pri;
}
//pos-1结点的后继指向pos+1结点
p->pri->next = p->next;
free(p);
H->len--;
}
//11、按值查找返回位置
int search_value(node_p H,int value)
{
if(H==NULL)
{return -1;}
if(empty_double(H)){return -2;}
}
//12、按位置修改元素
void update_pos(node_p H,int pos,int new_value)
{
if(H==NULL){return;}
if(empty_double(H)){return;}
if(pos<=0){return;}
}
//13、释放双向循环链表
void des_double(node_p *H)
{
if(H==NULL||*H==NULL)
{return;}
while((*H)->next)
{
dele_head(*H);
}
//退出循环说明链表中只有头结点了
free(*H);
*H=NULL;
}
double.h
#ifndef __DOUBLE_H__
#define __DOUBLE_H__
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
union
{
int len;
int data;
};
struct node *pri; //指向前驱结点的指针
struct node *next; //指向后继结点的指针
}node,*node_p;
//1、创建双向链表
node_p create_double();
//2、创建结点
node_p create_node(int data);
//3、判空
int empty_double(node_p H);
//4、头插
void insert_head(node_p H,int value);
//5、尾插
void insert_tail(node_p H,int value);
//6、输出
void show(node_p H);
//7、任意位置插入
void insert_pos(node_p H,int pos,int value);
//8、头删
void dele_head(node_p H);
//9、尾删
void dele_tail(node_p H);
//10、按位置删除
void dele_pos(node_p H,int pos);
//13、释放双向循环链表
void des_double(node_p *H);
#endif
04.双向循环链表
main.c
#include "dloop.h"
int main()
{
node_p H=(node_p)create_dloop();
//1.头插
printf("请输出头插的第一个数字双向链表:\n");
insert_head(H,4);
show(H);
printf("请输出头插的第二个数字双向链表:\n");
insert_head(H,3);
show(H);
printf("请输出头插的第三个数字双向链表:\n");
insert_head(H,2);
show(H);
printf("请输出头插的第四个数字双向链表:\n");
insert_head(H,1);
show(H);
//2.尾插
printf("请输出尾插的第一个数字双向链表:\n");
insert_tail(H,5);
show(H);
printf("请输出尾插的第二个数字双向链表:\n");
insert_tail(H,6);
show(H);
//3.按位置插入
printf("请输出按位置插入双向链表:\n");
insert_pos(H,3,77);
show(H);
//4.头删
printf("请输出头删双向链表:\n");
dele_head(H);
show(H);
//5.尾删
printf("请输出头删双向链表:\n");
dele_tail(H);
show(H);
//6.按位置删除
printf("请输出按位置删除双向链表:\n");
delete_pos(H,3);
show(H);
//7.按位置查找返回值
int ret=search_value(H,2);
printf("请输出按位查找的返回值%d:\n",ret);
show(H);
printf("销毁前:\n");
printf("%p\n",H);
free_loop(&H);
printf("销毁后:\n");
printf("%p\n",H);
}
dloop.c
#include "dloop.h"
//1.创建双链表的空结点
node_p create_dloop()
{
node_p H=(node_p)malloc(sizeof(node));
if(H==NULL)
{
printf("申请内存失败.\n");
return NULL;
}
H->pri=H;
H->next=H;
H->len=0;
return H;
}
//2.申请结点
node_p create_node(int value)
{
node_p new=(node_p)malloc(sizeof(node));
new->next=NULL;
new->data=value;
}
//3.判空
int empty_dloop(node_p H)
{
if(H==NULL){
printf("入参为空.\n");
return -1;
}
return H->next==H?1:0;
}
//4.头插
void insert_head(node_p H,int value)
{
if(H==NULL)
{
printf("入参为空.\n");
return;
}
node_p new=create_node(value);
new->next=H->next;
new->pri=H;
if(H->next!=NULL){
H->next->pri=new;
}
H->next=new;
H->len++;
}
//5.尾插
void insert_tail(node_p H,int value)
{
if(H==NULL)
{
printf("入参为空.\n");
return;
}
int i;
node_p new=create_node(value);
node_p p=H;
//1.找到了最后一个结点的位置
while(p->next!=H){
p=p->next;
}
new->pri=p;
new->next=H;
p->next=new;
H->pri=new;
H->len++;
}
//6.按位置插入
void insert_pos(node_p H,int pos,int value)
{
if(H==NULL){
printf("入参为空.\n");
return;
}
if(pos<0){
printf("插入位置的数据不合理.\n");
return;
}
int i;
node_p p;
for(i=1,p=H->next;i<pos-1;i++,p=p->next)
{
if(p==H){
printf("位置不合理.\n");
return;
}
}
if(p==H){
printf("位置不合理.\n");
return;
}
node_p new=(node_p)create_node(value);
new->next=p->next;
new->pri=p;
if(p->next!=H){
p->next->pri=new;
}
p->next=new;
H->len++;
}
//7.输出
void show(node_p H)
{
if(H==NULL){
printf("入参为空.\n");
return;
}
if(empty_dloop(H)){
printf("双向循环链表为空,无输出.\n");
return;
}
node_p p=H->next;
while(p!=H){
printf("%d->",p->data);
p=p->next;
}
printf("NULL\n");
}
//8.头删
void dele_head(node_p H)
{
if(H==NULL){
printf("入参为空.\n");
return;
}
if(empty_dloop(H)){
printf("循环双链表为空,无数据可删除.\n");
return;
}
node_p dele=H->next;
//判断是否就一个数据
if(dele->next!=H){
dele->next->pri=H;
}
H->next=dele->next;
free(dele);
H->len--;
}
//9.尾删
void dele_tail(node_p H)
{
if(H==NULL)
{
printf("入参为空.\n");
return;
}
node_p p=H;
while(p->next!=H){
p=p->next;
}
p->pri->next=H;
H->pri=p->pri;
free(p);
H->len--;
}
//10.按位置删除
void delete_pos(node_p H,int pos)
{
if(H==NULL){
printf("入参为空.\n");
return;
}
if(empty_dloop(H)){
printf("双向链表为空.\n");
return;
}
node_p p;
int i;
for(i=1,p=H->next;i<pos;i++,p=p->next){
if(p==H){
printf("位置不合理.\n");
return;
}
}
if(p==H){
printf("位置不合理.\n");
return;
}
//1.pos+1结点的前驱指向pos-1结点
if(p->next!=H){
p->next->pri=p->pri;
}
//2.pos-1结点的后继指向pos+1结点
p->pri->next=p->next;
free(p);
H->len--;
}
//11.按位置查找返回值
int search_value(node_p H,int pos)
{
if(H==NULL)
{
printf("入参为空.\n");
return -1;
}
if(empty_dloop(H)){
printf("双向循环链表为空.\n");
return -2;
}
int i;
node_p p;
for(i=1,p=H->next;i<pos;i++,p=p->next){
if(p==H){
printf("位置不合理.\n");
return -3;
}
}
if(p==H){
printf("位置不合理.\n");
return -3;
}
return p->data;
}
//12.释放链表
void free_loop(node_p *H)
{
if(H==NULL||*H==NULL)
{
printf("入参为空.\n");
return;
}
while((*H)->next!=(*H)){
dele_head(*H);
}
free(*H);
*H==NULL;
}
dloop.h
#ifndef __DLOOP_H__
#define __DLOOP_H__
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct node
{
union{
int len;
int data;
};
struct node *pri;
struct node *next;
}node,*node_p;
node_p create_dloop();
node_p create_node(int value);
int empty_dloop(node_p H);
void insert_head(node_p H,int value);
void insert_tail(node_p H,int value);
void insert_pos(node_p H,int pos,int value);
void show(node_p H);
void dele_head(node_p H);
void dele_tail(node_p H);
void delete_pos(node_p H,int pos);
int search_value(node_p H,int pos);
void free_loop(node_p *H);
#endif