数据对象、数据元素与数据项

数据对象是数据元素的集合；
数据元素也称为记录，每条记录包含若干个数据项

数据结构

数据元素之间若干种特定关系的集合

逻辑结构

• 集合结构：所有元素同属一个集合
• 线性结构：一对一
• 树形结构：一对多
• 图形结构：多对多

物理结构

在计算机中的存储形式

• 顺序存储
• 链式存储

ADT

数据类型：一组性质相同的值得集合，及定义在此集合上的一些操作
抽象数据类型：一个数学模型，及定义在该模型上得一组操作

1. 基本类型：整数、字符型、浮点型、bool、...
2. 结构类型：结构体、数组、...

线性表

两种存储方式下的增删改查——c语言实现

1. 顺序存储

/*创建*/
#define MAXSIZE 20     // 预处理，定义宏常量
typedef int ElemType;  // 起别名、定义数据类型
typedef struct
{
    ElemType data[MAXSIZE];
    int length;
}SqList;

/*获取元素*/
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
Status GetElem(SqList L,int i,ElemType *e)
{
    if (L.length==0 || i<1 || i>L.length)
        return ERROR;
    *e=L.data[i-1];
    return OK;
}

/*插入*/
Status ListInsert(SqList *L,int i,ElemType e)
{
    int k;
    if (L->length==MAXSIZE)
        return ERROR;
    if (i<1 || i>L->length+1)
        return ERROR;
    if (i<=L->length)
    {
        for (k=L->length-1;k>=i-1;k--)
            L->data[k+1]=L->data[k];
    }
    L->data[i-1]=e;
    L->length++;
    return OK;
}

/*删除*/
Status ListDelete(SqList *L,int i,ElemType *e)
{
    int k;
    if (L->length==0)
        return ERROR;
    if (i<1 || i>L->length)
        return ERROR;
    *e=L->data[i-1];
    if (i<L->length)
    {
        for (k=i;k<L->length;k++)
            L->data[k-1]=L->data[k];
    }
    L->length--;
    return OK;
}

2. 链式存储

单链表

/*创建*/
typedef struct Node
{
    ElemType data;
    struct Node *next;     // next是struct Node类型的指针
}Node, *LinkList;    // LinkList为Node*类型

/*获取元素*/
Status GetElem(LinkList L,int i,ElemType *e)
{
    int j;
    LinkList p;
    p = L->next;
    j = 1;
    while (p && j<i)
    {
        p = p->next;
        ++j;
    }
    if (!p || j>1)
        return ERROR;
    *e = p->data;
    return OK;
}

/*插入*/
Status ListInsert(LinkList *L,int i,ElemType e)
{
    int j;
    LinkList p,s;
    p = *L;
    j = 1;
    while (p && j<i)
    {
        p = p->next;
        ++j;
    }
    if (!p || j>i)
        return ERROR;
    s = (LinkList)malloc(sizeof(Node));    // 分配内存
    s->data =e;
    s->next = p->next;
    p->next = s;
    return OK;
}

/*删除*/
Status ListDelete(LinkList *L,int i,ElemType *e)
{
    int j;
    LinkList p,q;
    p = *L;
    j = 1;
    while (p->next && j<i)
    {
        p = p->next;
        ++j;
    }
    if (!(p->next) || j>i)
        return ERROR;
    if (!(p->next) || j>i)
        return ERROR;
    q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);    // 回收节点，释放内存
    return OK;
}

静态链表

/*创建*/
#define MAXSIZE 1000
typedef struct
{
    ElemType data;
    int cur;
}Component, StaticLinkList[MAXSIZE];

/*使用备用链表操作内存*/
int Malloc_SLL(StaticLinkList space)    // 分配内存
{
    int i = space[0].cur;
    if (space[0].cur)
        space[0].cur = space[i].cur;
    return i;
}
void Free_SSL(StaticLinkList space,int k)    // 释放内存
{
    space[k].cur = space[0].cur;
    sapce[0].cur = k;
}

/*插入*/
Status ListInsert(StaticLinkList L,int i,ElemType e)
{
    int j,k,l;
    k = MAX_SIZE-1;
    if (i<1 || i > ListLength(L)+1)
        return ERROR;
    j = Malloc_SSL(L);
    if (j)
    {
        L[j].data = e;
        for (l=1;l<=i-1;l++)
            k=L[k].cur;
        L[j].cur=L[k].cur;
        L[k].cur=j;
        return OK;
    }
    return OK;
}

/*删除*/
Status ListDelete(StaticLinkList L,int i)
{
    int j,k;
    if (i<1 || i>ListLength(L))
        return ERROR;
    k = MAX_SIZE-1;
    for (j=1;j<=i-1;j++)
        k=L[k].cur;
    j = L[k].cur;
    L[k].cur = L[j].cur;
    Free_SSL(L,j);
    return OK;
}

循环链表

双向链表

/*创建*/
typedef struct DulNode
{
    ElemType data;
    struct DulNode *prior;    // 前驱指针
    struct DulNode *next;     // 后继指针
}DulNode, *DuLinkList;

/*插入*/
s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;

/*删除*/
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);