数据结构【线性表篇】(三）

文章目录

数据结构【线性表篇】(三）
前言
- 为什么突然想学算法了？
- 为什么选择码蹄集作为刷题软件？
目录
- 一、双链表
- 二、循环链表
- 三、静态链表
结语

前言

在这里插入图片描述

为什么突然想学算法了？

> 用较为“官方”的语言讲，是因为算法对计算机科学的所有分支都非常重要。在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。
> 但从实际而言，是因为当下竞争压力逐渐增大，无论走哪一条路，都不免需要一些相对丰富的算法知识，是故，便产生了一个寒假巩固速成算法的计划，可能对于像我这种算法竞赛小白而言，几乎很难，但我仍然还是想尝试一下，毕竟，梦想还是要有的，万一实现了呢？～(￣▽￣～)~

在这里插入图片描述

为什么选择码蹄集作为刷题软件？

码蹄集，是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的，其依托全国各大名校计算机系和清华大学出版社等单位的强大资源，旨在为计算机学习爱好者提供全面和权威的计算机习题。
.

typedef struct DNode{                       //定义双链表结点类型
    int data;                               //数据域
    struct DNode *prior,*next;              //前驱和后驱指针
}DNode,*DLinklist;

//初始化双链表
bool InitDLinkList(DLinklist &L){
    L = (DNode *)malloc(sizeof(DNode));     //分配一个头结点
    if(L==NULL)                             //内存不足，分配失败
        return false;
    L->prior = NULL;                        //头结点的prior永远指向NULL
    L->next = NULL;                         //头结点之后暂时还没有节点
    return true;
}

//判断双链表是否为空(带头结点)
bool Empty(DLinklist L){
    if(L->next == NULL)
        return true;
    else
        return false;
}

//双链表的插入
//在p结点后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
    if(p==NULL || s==NULL)                  //非法参数
        return false;
    s->next=p->next;
    if(p->next != NULL)
        p->next->prior=s;                   //如果p结点有后继结点
    s->prior=p;
    p->next=s;
    return true;
}

//删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
    if(p==NULL) return false;
    DNode *q = p->next;                     //找到p的后继结点q
    if(q==NULL) return false;               //p没有后继
    p->next=q->next;
    if(q->next!=NULL)                       //q结点不是最后一个结点
        q->next->prior=p;
    free(q);                                //释放结点空间
    return true;
}

//双链表的删除
void DestoryList(DLinklist &L){
    //循环释放各个数据结点
    while(L->next != NULL)
        DeleteNextDNode(L);
    free(L);
    L=NULL;
}

//双链表的遍历
//前向遍历
//while(p!=NULL){
//    //对结点p做出相应处理，如打印
//    p=p->next;
//}

//后向遍历
//while(p!=NULL){
//    //对结点p做出相应处理
//    p=p->prior;
//}

//前向遍历(不带头结点)
//while(p->prior!=NULL){
//    //对结点p做出相应处理
//    p=p->prior;
//}

void printDoubleList(DLinklist L){
    DNode *p = L;
    p = p->next;
    while(p!=NULL){
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

int main(){

    //初始化双链表
    DLinklist L;
    InitDLinkList(L);

    return 0;
}

二、循环链表

//循环单链表
typedef struct LNode{           //定义单链表结点类型
    int data;                   //每个节点存放一个数据元素
    struct LNode *next;         //指针指向下一个节点
}LNode, *LinkList;

//初始化一个循环单链表
bool InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode));     //分配一个头结点
    if(L==NULL)                             //内存不足，分配失败
        return false;
    L->next = L;                            //头结点next指向头结点
    return true;
}

//判断循环单链表是否为空
bool Empty(LinkList L){
    if(L->next == L)
        return true;
    else
        return false;
}

//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L,LNode *p){
    if(p->next == L)
        return true;
    else
        return false;
}

//循环双链表
typedef struct DNode{           //定义双链表结点类型
    int data;                   //每个节点存放一个数据元素
    struct DNode *prior,*next;
}DNode, *DLinkList;

//初始化一个循环双链表
bool InitDLinkList(DLinkList &L){
    L = (DNode *)malloc(sizeof(DNode));     //分配一个头结点
    if(L==NULL)                             //内存不足，分配失败
        return false;
    L->prior = L;                           //头结点的prior指向头结点
    L->next = L;                            //头结点的next指向头结点
    return true;
}

//判断循环双链表是否为空
bool Empty(DLinkList L){
    if(L->next == L)
        return true;
    else
        return false;
}

//判断结点p是否为循环双链表的表尾结点
bool isTail(DLinkList L,DNode *p){
    if(p->next == L)
        return true;
    else
        return false;
}

//双链表的插入
//在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
    s->next=p->next;                        //将结点*s插入到结点*p之后
    p->next->prior=s;
    s->prior=p;
    p->next=s;
}

//双链表的删除
//删除p的后继结点q
bool DeleteNextDNode(DNode *p,DNode *q){
    p->next=q->next;
    q->next->prior=p;
    free(q);
}

int main(){
    //初始化循环双链表
    DLinkList L;
    InitDLinkList(L);

    return 0;
}

三、静态链表

#define MaxSize 10      //静态链表的最大长度
typedef struct Node{            //静态链表结构类型的定义
    int data;           //存储数据元素
    int next;           //下一个元素的数组下标
}SLinkList[MaxSize];

int main(){
    SLinkList L;
    return 0;
}