2023-03-28 数据结构【 一】 基本数据结构存储表示

1.1 存储表示

1.1.1 线性表

声明类型；定义长度

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;     //Status 是函数返回值类型，其值是函数结果状态代码。
typedef int ElemType;    //ElemType 为可定义的数据类型，此设为int类型

#define MAXSIZE 100         //顺序表可能达到的最大长度
typedef struct{
    ElemType *elem;         //存储空间的基地址
    int length;             //当前长度
}SqList;

1.1.2 单链表

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;     //Status 是函数返回值类型，其值是函数结果状态代码。
typedef int ElemType;    //ElemType 为可定义的数据类型，此设为int类型

typedef struct LNode
{
    ElemType data;                          //结点的数据域
    struct LNode *next;                     //结点的指针域
}LNode,*LinkList;                           //LinkList为指向结构体LNode的指针类型

声明LNode结构类型；
并设置*next指针；

1.1.3 双链表

typedef struct DuLNode
{
    ElemType data;                          //结点的数据域
    struct DuLNode *prior;
    struct DuLNode *next;                   //结点的指针域
}DuLNode,*DuLinkList;                       //DuLinkList为指向结构体DuLNode的指针类型

双向链表，比单向链表多了个prior 指针；

1.1.4 顺序栈

typedef int Status;
typedef int SElemType;
typedef struct{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;

SElemType base ,top 栈指针；
并指定栈长度stacksize；

1.1.5 链栈

typedef int Status;
typedef int SElemType;
typedef struct SNode{
    SElemType data;
    struct SNode *next;
}SNode,*LinkStack;

SElemType data 数据域
struct SNode *next;指定向下指针；

1.1.6 循环队列

typedef struct{
    QElemType *base;//初始化时动态分配存储空间
    int front;//头指针
    int rear;//尾指针
}SqQueue;

初始化动态分布存储空间
指定头尾指针；

1.1.7 链队

typedef struct QNode{
    QElemType data;
    QNode *next;
}QNode,*QueuePtr;
typedef struct{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

QNode 含有指针的节点 链中必有指针；
队列 的实现通过front,rear 指定首尾