数据结构双向链表与双向循环链表 6.17-EW帮帮网

前言

坤坤

坤

不行了，抓紧搞完睡觉

概述

1.基础：双向链表

2.一些代码：双向链表与双向循环链表的相关功能的实现

1.基础：双向链表

基本格式：NULL → → → … NULL

定义：

typedef struct node {

    union {

        int len;

        int data;

    };

    struct node *pre;

    struct node *next;

} node, *node_p;

增：先尾后首

new->pre = p;
new->next = p->next;

p->next = new;
p->next->pre = new;

删：先存后删

p->next->pre = p;
node_p p = p->next;
node_p p_delete = p->next;

注：1.仅最后一个`→`表读取，其余表地址偏移

2.赋值等式右侧不需要区分new->pre, new->next（new被赋值时）。

查：

查: node_p p = H
for (int i=0; i<pos; ++i)
    p = p->next;
// 线性查找

创建：

//创建链表与V连接:
node_p H = (node_p) malloc (sizeof (cnode));
H->... = ...
return H;

手写笔记

2.一些代码：

双向链表与双向循环链表的相关功能的实现：

2.1 双向链表

1.makefile

EXE=02_double_list
Objs+=main_double.o
Objs+=fun_double.o
CC=gcc
CFlags=-c -o

all:$(EXE)
$(EXE):$(Objs)
	$(CC) $^ -o $@
%.o:%.c
	$(CC) $^ $(CFlags) $@

#伪目标
.PHONY:clean
clean:
	rm $(EXE) $(Objs)

2.double.h

#ifndef __DOUBLE_H__
#define __DOUBLE_H__

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    union
    {
        int len;
        int data;    
    };
    struct node *pre;     //指向前驱结点的指针
    struct node *next;    //指向后继结点的指针
}node,*node_p;

//fun
//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 delete_head(node_p H);
//9、尾删
void delete_end(node_p H);
//10、位删
void delete_pos(node_p H,int pos);
//11、按值查找返回位置
int serch_value(node_p H, int value);
//12、按位置修改元素
void update_pos(node_p H,int pos,int new_value);
//13、释放双向循环列表
void release_double(node_p* H);

#endif

3.fun.c

#include "double.h"
//1、创建双向链表
node_p create_double(){
    node_p H = (node_p)malloc(sizeof(node_p));

    if(H==NULL){printf("failed");return NULL;}
    
    H->len = 0;
    H->pre = NULL;
    H->next = NULL;
    return H;
}
//2、创建结点
node_p create_node(int data){
    node_p H = (node_p)malloc(sizeof(node));

    if(H==NULL){printf("failed");return NULL;}

    H->data = data;
    H->pre = NULL;
    H->next = NULL;
    return H;
}
//3、判空
int empty_double(node_p H){
    if(H->pre == NULL && H->next == NULL){
        return 1;
    }
    else{return 0;}
}
//4、头插
void insert_head(node_p H,int value){
    node_p new = create_node(value);
    node_p p = H;

    new->next = p->next;
    new->pre = p;

    if(H->next != NULL)
    {
        p->next->pre = new;
    }
    p->next = new;

    H->len++;
    return;
}
//5、尾插
void insert_tail(node_p H, int value){
    if(H == NULL)return;
    node_p new = create_node(value);
    node_p p = H;

    while(p->next != NULL)p = p->next;
    
    p->next = new;
    new->pre = p;
    H->len++;
}
//6、输出
void show(node_p H){
    if(H == NULL)return;
    if(empty_double(H)){printf("empty");return;}
    node_p p = H->next;

    while(p){
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}
//7、按位置插入
void insert_pos(node_p H, int pos,int value){
    if(H == NULL)return;
    if(pos<0||pos>H->len){printf("error");return;}

    node_p new = create_node(value);
    node_p p = H;
    
    for(int i = 0; i<pos; ++i)p = p->next;
    new->pre = p;
    new->next = p->next;
    if(p->next != NULL)p->next->pre = new;
    p->next = new;

    H->len++;
    return;
}
//8、头删
void delete_head(node_p H){
    if(H == NULL)return;
    if(empty_double(H)){printf("empty");return;}

    node_p p = H;
    p->next = p->next->next;

    H->len--;
    return;
}
//9、尾删
void delete_end(node_p H){
    if(H == NULL)return;
    if(empty_double(H)){printf("empty");return;}

    node_p p = H;
    while(p->next->next!=NULL){
        p = p->next;
    }

    p->next = NULL;
    H->len--;
    return;
}
//10、位删
void delete_pos(node_p H,int pos){
    if(H == NULL)return;
    if(empty_double(H)){printf("empty");return;}
    if(pos<0)return;

    node_p p = H;
    for(int i =0; i<pos; ++i)p = p->next;

    node_p p_delete = p->next;
    p->next = p->next->next;
    p->next->pre = p;

    if(p->next != NULL){
        p_delete->next->pre = p;
    }

    free(p_delete);
    H->len--;
    return;
}
//11、按值查找返回位置
int serch_value(node_p H, int value){
    if(H==NULL)return -1;
    if(empty_double(H))return -2;

    node_p p = H;
    for(int i = 0; i<H->len; ++i){
        p = p->next;
        if(p->data == value){
            return i;
        }
    }
}
//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;}

    node_p p = H;
    for(int i = 0; i<pos; ++i){
        p = p->next;
    }

    p->next->data = new_value;
}
//13、释放双向循环列表
void release_double(node_p* H){
    if(H==NULL || *H==NULL){return;}
    while((*H)->next)delete_head(*H);

    free(*H);
    *H=NULL;
    printf("released\n");
}

4.main.c

#include "double.h"
int main(int argc, const char *argv[])
{
    node_p H = create_double();
    insert_head(H,4);
    insert_head(H,3);
    insert_head(H,2);
    insert_head(H,1);
    show(H);

    insert_tail(H,6);
    printf("尾插6：");
    show(H);

    insert_pos(H,2,5);
    printf("位插5：");
    show(H);

    delete_head(H);
    printf("头删 ：");
    show(H);

    delete_end(H);
    printf("尾删 ：");
    show(H);

    delete_pos(H,1);
    printf("位删 ：");
    show(H);

    int num = serch_value(H,3);
    printf("查找 :a[%d]=3\n",num);

    update_pos(H,1,9);
    printf("修改 ：");
    show(H);

    release_double(&H);
    return 0;
}

5.运行结果

ubuntu@ubuntu:~/data_structre/class3$ ./02_double_list 
1 2 3 4 
尾插6：1 2 3 4 6 
位插5：1 2 5 3 4 6 
头删 ：2 5 3 4 6 
尾删 ：2 5 3 4 
位删 ：2 3 4 
查找 :a[1]=3
修改 ：2 9 4 
released
ubuntu@ubuntu:~/data_structre/class3$

2.2 双向循环链表

1.makefile

EXE=01_double_loop
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 $(EXE) $(Objs)

2.double_loop.h

#ifndef _HEAD_H_
#define _HEAD_H_

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct node
{
    union
    {
        int len;
        int data;    
    };
    struct node *pre;     //指向前驱结点的指针
    struct node *next;    //指向后继结点的指针
}node,*node_p;

//fun
void output(node_p H);
node_p create_dloop();
node_p create_node(int data);
void insert_head(node_p H, int data);
void insert_end(node_p H, int data);
void insert_pos(node_p H, int pos, int data);
void delete_head(node_p H);
void delete_tail(node_p H);
void delete_pos(node_p H, int pos);
int check(node_p H, int pos);

#endif

3.fun.c

#include "double_loop.h"
//0.输出
void output(node_p H){
    node_p p = H->next;
    while(p!=H){
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}
//a.创建
node_p create_dloop(){
    node_p H = (node_p)malloc(sizeof(node));
    
    H->len = 0;
    H->pre = H;
    H->next = H;
    return H;
}
//b.创建结点
node_p create_node(int data){
    node_p H = (node_p)malloc(sizeof(node));
    
    H->data = data;
    H->pre = NULL;
    H->next = NULL;
    return H;
}
//c.头插
void insert_head(node_p H, int data){
    node_p new = create_node(data);

    new->pre = H;
    new->next = H->next;

    if(H->next != H){
        H->next->pre = new;}//先尾
    else{H->pre = new;}
    H->next = new;//后首

    H->len++;
    return;
}
//d.尾插
void insert_end(node_p H, int data){
    node_p new = create_node(data);

    node_p p = H;
    for(int i=0; i<H->len; ++i){
        p = p->next;
    }
    
    new->pre = p;
    new->next = H;

    H->pre = new;
    p->next = new;
    return;
}
//e.按位置插入
void insert_pos(node_p H, int pos, int data){
    node_p new = create_node(data);

    node_p p = H;
    for(int i=0; i<pos; ++i){
        p = p->next;
    }
    
    new->pre = p;
    new->next = p->next;

    p->next->pre = new;
    p->next = new;
    return;
}
//f.头删、
void delete_head(node_p H){
    node_p p = H;
    node_p p_delete = p->next;
    
    H->next = H->next->next;
    p_delete->next->pre = H;

    free(p_delete);
    return;
}
//尾删、
void delete_tail(node_p H){
    node_p p = H;
    while(p->next->next != H){
        p = p->next;
    }
    
    node_p p_delete = p->next;
    p->next = H;
    H->pre = p;

    free(p_delete);
    return;
}
//按位置删除
void delete_pos(node_p H, int pos){
    node_p p = H;
    for(int i=0; i<pos; ++i){
        p = p->next;
    }
    
    node_p p_delete = p->next;
    p->next = p->next->next;
    p_delete->next->pre = p;

    free(p_delete);
    return;
}

//g.按位置查找返回值
int check(node_p H, int pos){
    node_p p = H;
    for(int i=0; i<pos; ++i){
        p = p->next;
    }
    return p->next->data;
}

4.main.c

#include "double_loop.h"
int main(int argc, const char *argv[])
{
    node_p H = create_dloop();
    insert_head(H,5);
    insert_head(H,4);
    insert_head(H,3);
    insert_head(H,2);
    insert_head(H,1);
    output(H);

    insert_end(H,7);
    printf("尾插7：");
    output(H);

    insert_pos(H,2,9);
    printf("位插9：");
    output(H);

    delete_head(H);
    printf("头删 ：");
    output(H);

    delete_tail(H);
    printf("尾删 ：");
    output(H);

    delete_pos(H,1);
    printf("位删 ：");
    output(H);

    printf("位查 ：a[2]=%d\n",check(H,2));

    return 0;
}

5.运行结果

ubuntu@ubuntu:~/data_structre/class3_big_homework$ ./01_double_loop 
1 2 3 4 5 
尾插7：1 2 3 4 5 7 
位插9：1 2 9 3 4 5 7 
头删 ：2 9 3 4 5 7 
尾删 ：2 9 3 4 5 
位删 ：2 3 4 5 
位查 ：a[2]=4
ubuntu@ubuntu:~/data_structre/class3_big_homework$

结语

数据结构的学习代码量大，保护好自己的头发......

数据结构双向链表与双向循环链表 6.17

前言

概述

1.基础：双向链表

定义：

增：先尾后首

删：先存后删

查：

创建：

手写笔记

2.一些代码：

2.1 双向链表

1.makefile

2.double.h

3.fun.c

4.main.c

5.运行结果

2.2 双向循环链表

1.makefile

2.double_loop.h

3.fun.c

4.main.c

5.运行结果

结语

网站公告

今日签到

热门文章

最新发布

数据结构 双向链表与双向循环链表 6.17

前言

概述

1.基础：双向链表

定义：

增：先尾后首

删：先存后删

查：

创建：

手写笔记

2.一些代码：

2.1 双向链表

1.makefile

2.double.h

3.fun.c

4.main.c

5.运行结果

2.2 双向循环链表

1.makefile

2.double_loop.h

3.fun.c

4.main.c

5.运行结果

结语

网站公告

今日签到

热门文章

最新发布

数据结构双向链表与双向循环链表 6.17