数据结构与算法---链表（1)_链表.length

目录

从线性表开始

定义

顺序存储结构

三个属性

获得元素的操作

插入的操作

删除的操作

链式存储结构

单链表

单链表的读取

单链表的插入与删除

单链表的整表创建

单链表的整表删除

---

• 从线性表开始

        线性表是什么？

       零个或多个数据元素的有限序列，是有限的也是有序的。

       线性表的意义

       可以根据位序获得数据元素，查找某个元素是否存在，获得线性表的长度。

• 定义

InitList(*L)：       //初始化操作，建立一个空的线性表L
ListEmpty(L):        //若线性表为空，返回true，反之返回false
ClearList(*L):       //清空线性表
GetElem(L,i,*e):     //将线性表中第i个元素值返回给e
LocateElem(L,e):     //在线性表中查找与e相等的元素，如果查找成功，返回该元素在表中序号，失败返回0
ListInsert(*L,i,e):  //在表中第i个元素插入e
ListDelete(*L,i,*e)；//删除表中第i个元素，并用e返回其值
ListLength(L):       //返回值为表中的元素个数

关于线性表的更复杂操作，都可以由上述基本操作组合来实现。

---

• 顺序存储结构

将相同数据类型的数据元素依次存放在一个一维数组中，数组的长度为最大存储容量。

• 三个属性

• 存储空间的起始位置：数组data，它的位置即为存储空间的位置。
• 线性表最大存储容量：数组长度MaxSize。
• 线性表的当前长度：length

#define MaxSize 20      //宏定义，表示MaxSize为20，即最大空间为20
typedef int ElemType    //定义ElemType为int类型
typedef struct
{
  ElemType data[MaxSize];   //数组存储数据元素，最大为MaxSize
  int length;               //线性表当前长度
}SqList;                    //该结构体命名为SqList

• 获得元素的操作

可以使用基本操作中的GetElem(L,i,*e): 将线性表中第i个元素值返回给e。即把数组中第i-1下标的值返回即可。

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;    //将状态返回函数定义为int型
Status GetElem(SqList L,int i,ElemType *e)
{
    if(L.length==0 || i<1 || i>L.length)
        return ERROR;   //如果线性表长度为0或要求获得第0个元素或获得元素长度比线性表大，返回ERROR
    *e=L.data[i-1];     //将第i-1下标的数组值返回给指针e
    return OK;
}

• 插入的操作

如何实现ListInsert(*L,i,e):在线性表中第i个位置插入元素e。

思路：

1. 当插入位置不合理时，报出异常。
2. 如果线性表长度大于数组长度，报出异常。
3. 从最后一个元素开始向前遍历到第i个位置，再分别向后移动一个位置。
4. 将e插入位置i处。
5. 表长加1。

Status ListInsert(SqList *L, int i, ElemType e)
{
    int k;
    if (L->length==MaxSize)                 //当线性表长度已经满的时候
        return ERROR;
    if (i<1 || i>L->length+1)               //当i不在范围时，插入位置不合理
        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;                         //将e插入到第i-1下标的数组中
    L->length++;                            //表长加1
    return OK;
}

• 删除的操作

如何实现ListDelete(L,i,*e):删除第i个元素，并用e返回其值

思路：

1. 如果删除位置不合理，报出异常。
2. 从删除元素的位置开始遍历到最后一个元素的位置，分别向前移动一个位置。
3. 取出删除元素。
4. 表长减一

Status ListDelete(SqList *L,int i,ElemType *e)
{
    int k;
    if(L->length==0)                        //如果表长为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--;                            //表长减1
    return OK;
    
}

---

• 链式存储结构

顺序存储结构的缺点在删除和插入的时候需要移动大量元素，显然需要耗费很长时间。

how?

干脆所有元素不要考虑相邻的位置，只是让每个元素知道它下一个元素在哪里。

• 单链表

将每个元素的数据信息定义为数据域，把存储直接后继位置的域称为指针域。这两部分信息组成元素的存储映像，称为结点。n个结点链结成一个链表，因此链表的每个结点只包含一个指针域，所以称为单链表。

把链表第一个结点的存储位置叫做头指针，之后的每一个结点，其实就是上一个指针所指向的位置，最后一个结点指针为“空”，通常用NULL表示。头指针是链表的必要元素，不论该表是否为空。头指针有标识的作用，通常用链表的名字来命名。

typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList;        //定义一个LinkList

• 单链表的读取

思路：

• 声明一个指针p指向链表的第一个结点，初始化计数器j从1开始。
• 当j<i时，遍历链表，让p的指针向后移动，不断移向下一个结点，j累加1。
• 若到链表末尾p为空，则说明第i个结点不存在。
• 否则查找成功，返回结点p的数据。

Status GetElem(LinkList L,int i, ElemType *e)
{
    int j;
    LinkList p;                //声明一个指针p
    p=L->next;                 //p指向链表中第一个结点
    j=1;
    while(p && j<i)            //当p不为空且计数器还没有等于i的时候，循环继续
    {
        p = p->next;
        ++j;
    }
    if(!p || j>i)
        return ERROR;
    *e = p->data;             //将第i个结点赋值给e
    return OK;
}

• 单链表的插入与删除

插入节点就是用插入前节点的指针域链接上插入节点的数据域，再把插入节点的指针域链接上插入后节点的数据域。反之则为删除。

在单链表第i个数据中插入结点思路：

1. 声明一个指针p指向链表头结点，初始化计数器j从1开始计数。
2. 当j<i的时候，遍历链表，将p的指针不断向后移动，j累加1.
3. 若到链尾p为空，则说明第i个结点不存在。
4. 若找到，则在系统中生成一个空结点s。
5. 将数据元素e赋值给s->data。
6. s->next = p->next;p->next = s
7. 返回OK。

Status ListInsert(LinkList *L,int i,ElemType e)
{
    int j=1;
    LinkList p,s;
    p = *L;
    while(p && j<i)                        //寻找第i-1个结点
    {
        p = p->next;
        ++j;
    }
    if(!p || j>i)
        return ERROR;
    s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;                    //将s后继结点变成原来p的后继结点
    p->next = s;                          //将p的后继结点变成s
    return OK;
}

在单链表第i个数据删除结点的思路：

1. 声明一指针p指向链表头指针，初始化计数器j从1开始。
2. 当j<i时，就遍历链表，让p的指针向后移动，j累加。
3. 若到链尾，p为空，则说明第i个结点不存在。
4. 查找成功，将要删除的结点p->next赋值给q。
5. 运用删除标准语句p->next = q->next。
6. 将q中数据赋值给e。
7. 释放结点q。
8. 返回OK。

Status ListDelete(LinkList *L,int i,ElemType e)
{
    int j=1;
    LinkList p,s;
    p = *L;
    while(p && j<i)                        //寻找第i-1个结点
    {
        p = p->next;
        ++j;
    }
    if(!(p->next)|| j>i)
        return ERROR;
    q = p->next;
    p->next = q->next;                    //将p的后继的后继赋值给p的后继
    *e = q->data;                         //将q的数据赋值给e
    free(q);                              //将q结点释放
    return OK;
}

• 单链表的整表创建

单链表和顺序存储结构不一样，是一种动态的结构，对于每个链表的大小可以根据系统的情况和实际的需求即时生成。

思路：

1. 声明一指针p和计数器变量i。
2. 初始化一个空链表L。
3. 让L的头结点的指针指向NULL，即建立一个带头结点的单链表。
4. 循环：
   1. 生成一新结点赋值给p；
   2. 随机生成一数字赋值给p的数据域；
   3. 将p插入到头结点与前一新结点之间。

//尾插法
void CreateListTail(LinkList *L,int n)
{
    LinkList p,r;
    int i;
    srand(time(0));                            //初始化随机数种子
    *L = (LinkList)malloc(sizeof(Node));       //整个线性表
    r=*L;                                      //r指向尾部的结点
    for(i=0;i<n;i++){
        p=(Node *)malloc(sizeof(Node));        //生成新结点
        p->data = rand()%100+1;
        r->next = p;                           //将r的后继变为p
        r=p;                                   //将p变为r，即原先r的后继变为r
    }
r->next = NULL;                                //当前链表结束
}

• 单链表的整表删除

当我们不想使用这个单链表后，需要在内存中将它释放掉。

思路如下：

1. 声明结点p和q。
2. 将第一个结点赋值给p。
3. 循环：
   1. 将下一结点赋值给q。
   2. 释放p。
   3. 将q赋值给p。

//假设线性表L已存在
Status ClearList(LinkList *L)
{
    LinkList p,q;
    p = (*L)->next;                //p指向第一个结点
    while(p){                      //当p存在时，循环继续
        q=p->next;
        free(p);
        p=q;
    }
    (*L)->next=NULL;               //头结点指针域为空
    return OK;
}

从时间复杂度上看，顺序存储结构在查找元素的操作上为O(1)，单链表则需O(n)。在插入和删除操作时，顺序存储结构为O(n)，单链表需要O(1)。

从空间上看，顺序存储结构内存空间易溢出，而单链表可以动态变化。