线性表 - Yuan's Blog

线性表是n个数据元素的有限序列，序列中的每个元素，可以是一个数字，可以是一个字符，也可以是复杂的结构体或对象。
线性表的存储结构有两种，一种是顺序存储结构，另一种是链式存储结构。

顺序表

1.定义顺序表

#define MAXSIZE 20
typef int ElemType;
typedef struct  
{
    ElemType data[Maxsize];
    int length;
}Sqlist;

顺序存储格式有三个属性：

存储空间的起始位置：数据data，它的位置就是存储空间的起始位置。
线性表的最大存储容量：MAXSIZE
线性表的当前长度：length

2.获得新元素

Status GetElem(Sqlist L,int i,ElemType *e)  //Status是函数的类型，当函数返回值为函数结果状态代码时，函数定义为Status类型
{
    if (L.length==0 || i<1 || i>L.length)   //这一段分别验证线性表、输入获取链表的位置是否错误
        return ERROR;
    *e=L.data[i-1];
    return OK;
}

3.插入操作

Status ListInsert(Sqlist *L,int i,ElemType e)
{
    int k;
    if(L->length==MAXSIZE)  //线性表满了，->表示L结构体中length的值
        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++;    //长度增加
}

线性表的存储结构，读取、插入、删除的时间复杂度都是O(n)。

链表

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。

头指针：链表中第一个节点的存储位置叫做头指针
头节点：第一个节点也叫做头节点，该节点数据域可以不存储任何信息，也可以存储如线性表长度等附加信息。
节点：由存放数据元素的数据域与存放后继节点地址的指针域组成
- 假设p是一个指向线性表第i个元素的指针，则节点a_i的数据域就可以用p->data来表示
- 节点a_i可以用p->data表示
- p->next->data == a_i+1

1.定义链表

typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList;

突然对typedef有点感兴趣，研究了一下：
* typedef就是C库里边的一个取名函数
* 经常与结构体、联合体、枚举、函数指针声明结合使用
* 函数指针变量 int (*func_t)(int a, int b)

2.读取链表

Status GetElem(Linklist L,int i,ElemType *e)    //输入
{
    int j;
    Linklist p;
    p=L->next;
    j=1;    //计数器
    while(p&&j<i)   //如果链表p不为空、计数器没有等于i
    {
        p=p->next;
        j++;
    }
    if(!p||j>i) //链表p为空、j超出链表的总数
        return ERROR;
    *e=p->data;
    return OK
}

单链表的结构中没有定义表长，不知道要循环多少次，用For循环来控制，核心思想就是“工作指针后移”，最坏情况的时间复杂度是O(n).

3.单链表插入

Status ListInsert(LinkList *L,int i,ElemType e)
{
    int j;  //计数器
    LinkList p,s;
    p=*L;   //将p指向链表
    j=1;
    while(p&&j<i)   //当链表p不为空、取值i在链表j内
    {
        p=p->next;
        ++j;
    }
    if(!p||j>i)
        return ERROR;
    s=(LinkList)malloc(sizeof(Node));   //malloc用于生成一个节点
    s->data=e;
    s->next=p->next;
    p->next=s;
    return OK;
}

4.单链表的删除

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;
    q=p->next;
    p->next=q->next;
    *e=q->data;
    free(q);    //用于释放内存
    return OK;
}

对于单链表的插入与删除，时间复杂度为O(1),因此效率相较于列表更为明显

5.单链表的整体创建(头插)

void CreatListHead(Listlink *L,int n)
{
    Linklist *p;
    int i;
    strand(time(0));
    *L=(Linklist)malloc(sizeof(Node));
    p->data=NULL;
    for(i=0;i<n;i++)
    {
        p=(Linklist)malloc(sizeof(Node));
        p->data=rand()%100+1;
        p->next=(*L)->next; //将新建的节点指向头节点的后一位
        (*L)->next=p;   //更新头节点的后一位
    }
}

感觉头插法不是真正意义上的插在头节点的后边，觉得每个节点都是指向下一个节点的指针，头插法只是利用了节点头的性质进行的插入
但是非要说好像又有点关系，毕竟节点头就是这个链表的头部嘛每次都是插在这个头部的后边自然就叫头插法了。
新来的指向上一个结点
头节点总数指向最新的节点

5.1单链表的整体创建（尾插）

void CreatLinklistTail(Linklist *L,int n)
{
    Linklist p,r;
    int i;
    srand(time());
    *L=(Linklist)malloc(sizeof(Node));
    r=*L;   //先把这个r存一个头节点的指针 然后之后的r就是上一个节点的地址啦
    for(i=0,i<n,i++)
    {
        p=(Node*)malloc(sizeof(Node));
        p->data=rand()%100+1;
        r->next=p;
        r=p;
    }
    r->next=NULL;
} 

L是指整个单链表,r是指向尾节点的变量,r会随着循环不断地变化结点,而L则是随着循环增长为一个多节点链表.

尾插法就没有用到头节点，是利用了一个变量r存储上一个节点的地址下一个节点生成后把上一个节点指向这个新节点
上一个节点指向新来的

6.单链表地整表删除

Status ClearList(Linklist *L)
{
    Linklist p,q;
    p=(*L)->next;
    while(p)
    {
        q=p->next;
        free(p);
        p=q;
    }
    (*L)->next=NULL;
}

通过上诉对比，可以得出：

若线性表需要频繁查找，少量插入和删除，宜采用顺序存储结构。
当线性表中的元素个数变化较大或根本不知道由多大时，最好用单链表结构。

静态链表

数组的元素都是由两个数据域组成，data和cur，一个存储数据一个存储后继在数组中的下标。这种数组描述的链表就叫做静态链表

#define MAXSIZE 1000
Typedef struct
{
    ElemType data;
    int cur;
}Component,StaticLinklist[MAXSIZE];

通常把未被使用的数组元素称为备用链表
数组的第一个元素，即下标为0的元素的cur就存放备用链表的第一个节点的下标；
最后一个元素的cur则存放第一个有数值的元素的下标。

1.初始化静态链表

Status InitList(StaticLinkList space)
{
    int i;
    for (i=0;i<MAXSIZE-1;i++)
        space[i].cur=i+1;
    space[MAXSIZE-1].cur=0;
    return OK;
}

2.静态链表的插入

int Malloc_SSL(StaticLinkList space)
{
    int i=space[0].cur;
    if(space[0].cur)
    space[0].cur=space[i].cur;
    return i;
}

在插入之前，还要写一段用于动态分配内存的函数，这段函数的作用是返回第一个cur指向的空闲下标。

Status LiskInsert(StaticLinkList L,int i,ElenType e)
{
    int j,k,l;
    k=MAXSIZE-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 ERROR;
}

将所有未被使用过的已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新节点。

3.静态链表的删除

Status LinkList(StaticLinkLint L,int i)
{
    int i,j;
    if(i<1||i>LinkLength(L))
        return ERROR;
    k=MAXSIZE-1;
    for (j=1;j<=i-1;j++)
        k=L[k].cur; //k就是i-1的下标
    j=L[k].cur; //j就是i的下标
    L[k].cur=L[j].cur;  //将i的游标赋给i-1
    Free_SSL(L,j);
    return OK;
}

看到这里，突然激起了对For循环的研究：

For的本质就是对表达式进行循环操作
- 循环操作的表达很酷，关键点就是中间那个判断表达式
- 按照习惯i都取1，中间的判断表达式可以<或者<=某个值
  - 当取<时，循环的次数就是小于那个值-1
  - 当取<=时，循环的次数就是小于的那个值
    有点感受：
静态链表的一个变量可以表示两种状态：一种是当前的状态一种是之后的状态
因此要进行删除操作就只需要两个变量。
1
2
3
4
5
Void Free_SSL(StaticLinkList space,int k)
{
space[k].cur=space[0].cur;
space[0].cur=k;
}
这个函数没什么好说的，你删了个东西下次插肯定就是先用这个位置了嘛

循环链表

由于单链表不能从任意一个节点开始访问链表的所有节点，这样，我们把终端节点的指针指向头结点，这种头尾相接的单链表称为单循环链表，简称循环链表。

对于链表的插入，循环链表与单链表的差异主要就在循环的判断上，原来是判断 p->next 是否为空，现在则是判断 p->next 是否是头指针地址。
设定的尾指针 rear 指向节点的尾部，可以让查找尾部节点的时间复杂度为 O(1)。

如果要找B的第一个节点，则可以用 rearB->next->next。

p=rearA->next;  //先把A的头结点地址取出来
rearA->next=rearB->next->next;  //把A的尾指针指向B的头节点

q=rearB->next;  //把B的头节点地址取出来
rearB->next=p;  //将B的尾指针指向A的头结点
free(q);

双向链表

双向链表是在单链表的每个节点中，再设置一个指向其前驱结点的指针域。

双向链表的存储结构

typedef struct DulNode
{
    ElemType data;
    struct DuLNode *prior;
    struct DuLNode *next;
} DulNode,*DuLinkList;

双链表的其他操作

双链表是单链表扩展出来的，所以很多操作都是跟单链表相同的，比如求长度的 ListLength,查找元素的 GetElem,获取元素位置的 LocateElem。
但在结点的插入上有点不同：

s->prior=p; //插入的前驱
s->next=p->next;    //插入的后继
p->next->prior=s;   //q的前驱
p->nexy=s;  //p的后继

关键点就是：要在改变p之前改变q。
删除：

p->prior->next=p->next; //p的前驱指向后继
p->next->prior=p->prior;    //p的后继指向前驱
free(p);