数据结构双向循环链表Linux Ubuntu 下的C语言实现_ikunc语言代码

       大家好，我是练习编程时长两年半的昆工第一ikun，昨天咋们聊了单向循环链表，今天咋们来实现双向奔赴，也就是双向循环链表，话不多说，直接上代码；

一、数据结构中的结构

1.逻辑结构

① 集合结构：一个范围内，每一个个体之间没有任何关联

② 线性结构：一对一的关系，有唯一前驱和后继

第一个元素没有前驱，最后一个元素没有后继，中间元素既有唯一前驱，也有唯一后继

③ 树形结构：一对多的关系

第一个元素没有前驱，最后一个元素没有后继，中间元素有唯一前驱，但是可以有多个后继

④ 图形结构：多对多的关系，各个元素之间可能都有关联

2.存储结构

①顺序存储

特点：元素和元素之间依次存放

实现方法：数组、malloc

优点：数据查找和修改比较方便

缺点：浪费资源空间

插入数据、删除数据效率低

②链式存储

特点:在内存中的每一个元素之间用地址进行关联

优点：节省资源空间，插入数据、删除数据效率高

缺点：数据查找和修改效率低，需要遍历全部数据

③ 索引存储

特点：每一个元素都会创建一张索引表，资源开销比较大，

优点：数据查找效率高

④Hash存储（散列存储）

3.算法

（1）算法概念

有穷命令（指令、语句）的有序集合

（2）算法的特性

有穷性：算法执行步骤必须是有限的

可行性：在有效时间得到确定结果

确定性：算法中不能出现歧义

输入：算法有零个或多个外部输入

输出：算法有一个或多个输出

（3）语句频度：

一个语句在算法中循环执行的次数

（4）时间复杂度

算法的时间复杂度定义为算法中可执行语句的频度之和

事后统计法

事前预估法---大O计数法

大O计数法的表示方法：

T（n） = O（f（n））

f（n）是将时间复杂度的表达式中，将规模趋近于无穷或者一个新的表达式

T（n） = 3n^3+2n^2+4n+4

T(n) = O(n^3)

二、dlinklist.h头文件代码

#ifndef _DLINKLIST_
#define _DLINKLIST_
 
typedef int data_t;
typedef struct dlinklist
{
    data_t data;
    struct dlinklist *next;
    struct dlinklist *prior;
 
}DLinkList;
 
DLinkList *Create_DLinklist(); //创建头节点
 
int DLinklist_Size(DLinkList *head); //链表长度
 
void DLinklist_Insert(DLinkList *head, data_t data); //头插法插入数据
 
void DLinklist_Delete_Pos(DLinkList *head, int pos); //按位置删除数据
 
void DLinklist_Insert_Pos(DLinkList *head, int pos, data_t data); //任意位置插入数据
 
void DLinkList_Show(DLinkList *head); //打印表
#endif

三、dlinklist.c函数功能实现代码

#include <stdio.h>
#include <stdlib.h>
#include "dlinklist.h"
 
DLinkList *Create_DLinklist()
{
    DLinkList *head = (DLinkList *)malloc(sizeof(DLinkList));
    if(head == NULL){
        printf("创建失败！\n");
        return NULL;
    }
    head->data = -1;
    head->next = head;
    head->prior = head;
    return head;
}
//****************判断链表长度*****************
int DLinklist_Size(DLinkList *head)
{
    DLinkList *p = head;
    int len = 0;
    while(p->next != head){
        p = p->next;
        len++;
    }
return len;
}
//**************头插法插入数据*****************
void DLinklist_Insert(DLinkList *head, data_t data)
{
    DLinkList *new = (DLinkList *)malloc(sizeof(DLinkList));
    if(head == NULL){
        printf("创建失败！\n");
        return;
    }
    new->data = data;
    new->next = NULL;
    new->prior = NULL;
 
    head->next->prior =new;
    new->next = head->next;
    head->next = new;
    new->prior = head;
    return;
}
 
//******************任意位置插入数据******************
void DLinklist_Insert_Pos(DLinkList *head, int pos, data_t data)
{
    if(pos < 0 || pos > DLinklist_Size(head)-1){       //判断输入的位置是否合法
        printf("该位置不存在！！\n");
        return;
    }
 
     DLinkList *new = (DLinkList *)malloc(sizeof(DLinkList));
    if(head == NULL){
        printf("创建失败！\n");
        return;
    }
    new->data = data;
    new->next = NULL;
    new->prior = NULL;
 
    DLinkList *p = head;
    while(pos--){
        p = p->next;
    }
    p->next->prior = new;
    new->next = p->next;
    p->next = new;
    new->prior = p;
    return;
}
 
//*******************按位置删除数据*******************
void DLinklist_Delete_Pos(DLinkList *head, int pos)
{
    if(pos < 0 || pos > DLinklist_Size(head)-1){       //判断输入的位置是否合法
        printf("该位置不存在！！\n");
        return;
    }
    DLinkList *p = head->next;
    while(pos--){
        p = p->next;
    }
 
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    p = NULL;
    return;
}
 
//******************打印表*******************
void DLinkList_Show(DLinkList *head)
{
    DLinkList *p = head->next;
    while(p != head){
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
 
 
}

四、main.c主函数代码

#include <stdio.h>
#include "dlinklist.h"
 
int main(int argc, char *argv[])
{
    DLinkList * head = Create_DLinklist(); //创建头节点
    int n = 10;
    while(n--){
 
        DLinklist_Insert(head, n); //头插法插入数据
    }
DLinkList_Show(head);
 
DLinklist_Delete_Pos(head, 3);
DLinkList_Show(head);
 
DLinklist_Insert_Pos(head, 5, 999);
DLinkList_Show(head); 
 
int len = DLinklist_Size(head);
printf("%d\n", len);
 
    return 0;
} 

        好了，今天的分享就到这啦，坤坤今晚出去耍了，所以大家凑活看，明天再更新，我是练习编程时长两年半的昆工第一ikun，咋们明天见。