线性表

简介

线性表(List):零个或多个数据元素的有限序列

顺序存储结构

/*顺序存储*/
constexpr auto MAXSIZE = 20; 
constexpr auto OK = true;
constexpr auto ERROR = false;    

ElemType GetElem(SqList L, int i, ElemType* e);//读取元素
ElemType ListInsert(SqList* L, int i, ElemType e);//插入元素
ElemType ListDelete(SqList* L, int i, ElemType* e);//删除元素

//定义顺序存储结构
typedef int ElemType;
typedef struct {
    ElemType data[MAXSIZE];
    int length;
}SqList;

//读取元素
ElemType GetElem(SqList L,int i,ElemType *e) {
    if (L.length == 0 || i<1 || i>L.length)/*1.L的长度不能为0，2.i<1所读取元素不在线性表内，3.i>L.length 所读取元素不在线性表内*/
        return ERROR;
    *e = L.data[i - 1];
    return OK;
}

顺序结构的插入与删除

//插入元素
/*
* 初始条件：表已存在，1 <= i <= ListLength(L)
* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
*/
ElemType 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; k >= i - 1; k--)
            L->data[k + 1] = L->data[k]; 
    }
    L->data[i - 1] = e;
    L->length++;
    return OK;
}

//删除元素
/*
* 初始条件：表已存在，1 <= i <= ListLength(L)
* 操作结果：在L中第i个位置之前插入新的数据元素e， L的长度减1
*/
ElemType ListDelete(SqList* L, int i, ElemType *e) {
    int k;
    if (L->length == 0) //表空
        return ERROR;
    if (i<1 || i>L->length) //i不在范围内
        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;
}

/*
code需要注意的地方
* 删除元素判断元素不在范围
* if (i<1 || i>L->length) //i不在范围内
        return ERROR;
* 添加元素判断元素不在范围
* if (i<1 || i>L->length + 1) //i不在范围内
        return ERROR;
*/

优点

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间

• 快速地存取表中任一位置的元素

缺点

• 插入删除操作需要移动大量元素
• 当线性表长度变化较大时，难以确定存储空间容量
• 造成存储空间的“碎片”

线性表的链式存储结构

头指针

• 链表指向第一个结点的指针，若链表有头结点，则是指向头节点的指针
• 头指针具有标识作用，所以常用头指针冠以链表的名字
• 无论链表是否为空，头指针均不为空。头指针是链表的必需元素

头节点

• 为操作的统一和方便设立，放第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
• 有头结点时，在第一元素结点前插入结点和删除第一结点，其操作与其他操作一致
• 头结点不一定是必须要素

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

ElemType GetElem(LinkList L, int i, ElemType* e);//链表的读取
ElemType ListInset(LinkList* L, int i, ElemType e);//单链表的插入
ElemType ListInset(LinkList* L, int i, ElemType* e);//单链表的删除

单链表的读取

/*
* 初始条件：表已存在，1 <= i <= ListLength(L)
* 操作结果：用e返回L中第i个元素的值
*/
ElemType GetElem(LinkList L,int i,ElemType *e) {
    int j = 1;    //计时器
    LinkList p; 
    p = L->next;  //p指向L链表的第一个元素
    while (p && j<i)
    {
        p = p->next; 
        ++j;
    }
    if (!p || j > i)
        return  ERROR;
    *e = p->data;
    return OK;
}

单链表的插入与删除

/*
* s->next = p->next;
* p->next = s;
* 上面这两句话的代码顺序一定不能乱，如果先p->next=s再是s->next=p->next这时会出现一个问题，s->next=s那么第a(i+1)个元素就没有了上级
* 初始条件：表已存在，1 <= i <= ListLength(L)
* 操作结果：在L中第i个结点位置之前插入新的数据元素e,L的长度加1
*/
ElemType ListInset(LinkList *L,int i,ElemType e) {//注意这里LinkList类型本身就是指针，在这里L是二重指针
    int j = 1;//计时器
    LinkList p, s; 
    p = *L;
    while (p&&j<i)
    {
        p = p->next;
        ++j;
    }
    if (!p || j > i)
        return ERROR;
    s = (LinkList)malloc(sizeof(Node)); //申请node变量对应大小的内存，返回的是无类型地址， (LinkList)是要将其强制转换成LinkList类型 
    s->data = e;
    s->next = p->next;                  //将s接到p后面，将p的后继赋值给s的后继
    p->next = s->next;                  //将s接到p后面，将s赋值给p的后继
    return OK;
}

/*
* q = p->next;
* p->next = q->next;
* 这里存在和上面一样的问题使用时不能将顺序弄反
* 初始条件：表已存在，1 <= i <= ListLength(L)
* 操作结果：删除L中的第i个元素，并用e返回其值，L的长度减1
*/
ElemType ListInset(LinkList* L, int i, ElemType *e) {//注意这里LinkList类型本身就是指针，在这里L是二重指针
    int j = 1;//计时器
    LinkList p, q;
    p = *L;
    while (p->next && j < i)  //在这里是p->next而不是p，而在循环内部用的是p，注意这一步q = p->next;
    {
        p = p->next;
        ++j;
    }
    if (!p->next || j > i)
        return ERROR;
    q = p->next;
    p->next = q->next;
    *e = q->data;    //将q结点中的数据赋值给e
    free(q);         //让系统回收此结点，释放内存
  /*  
  * 这里的释放内存是这样的：
  * free释放的是q指针所指向的由malloc所分配的内存单元，q指针本身是不会释放的，
  * 所以之后可以将q指针重新指向新的内存地址，
  * free只是告诉系统，这块我不要了，但在内存分配给其它之前它都是存在的
  */
    return OK;
}

这里的释放内存是这样的：

• free释放的是q指针所指向的由malloc所分配的内存单元，q指针本身是不会释放的，
• 所以之后可以将q指针重新指向新的内存地址，
• free只是告诉系统，这块我不要了，但在内存分配给其它之前它都是存在的

关于p和p->next

• while (p&&j<i) 增加
• while (p->next && j < i) 删减
• 增加是p不能为空，删减是p->next不能为空，
• 因为 p = p->next当增加时下一个值可以是空尾部，
• 但减少是却不可以 p = p->next，即此时p为空那么就没有删减的意义了

单链表的整表创建

算法思路

• 声明指针p和计数器i
• 初始化一个空链表L
• 让L的头头结点的指针指向null，即所建立的为带头结点的单链表
• 循环：

  • 生成新结点赋值给p

  • 随机生成数字赋值给p的数据与p->data

  • 将p插入头结点与前一新结点之间

头插法

//随机产生n个元素的值，建立带头结点的单链线性表
//头插法
void CreateListHead(LinkList *L,int n) {
    LinkList p;
    int i;   
    srand(time(0));                                          //初始化随机数种子
    *L = (LinkList)malloc(sizeof(Node)); 
    (*L)->next = NULL;                                       //建立一个带头结点的单链表
    for ( i = 0; i < n; i++)
    {
        p = (LinkList)malloc(sizeof(Node));                  //生成新结点
        p->data = rand() % 100+1;                            //0~100的随机数
        p->next = (*L)->next;
        (*L)->next = 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;                          //0~100的随机数
        r->next = p;                                         //将表尾终端结点的指针指向新结点
        r = p;                                               //将当前的新结点定义为表尾终端结点
    }
    r->next = NULL;
}

单链表的整表删除

/*
* 逐个释放内存
*/
ElemType ClearList(LinkList *L) {
    LinkList p,q;
    p = (*L)->next;              //p指向第一个结点
    while (p)                    //没到表尾
    {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;            //头结点指针域为空
    return OK;
}

单链表结构与顺序存储结构优缺点

存储分配方式

• 顺序存储 —— 连续的存储单元依次存储线性表的数据元素
• 链表存储 —— 一组任意的存储单元存放线性表的数据元素

时间性能

• 查找
  • 顺序O(1)
  • 单链表O(n)
• 插入删除
  • 顺序 —— 平均移动表长一半的元素，O(n)
  • 链表 —— 找出插入删除位置的指针后时间仅为O(1)

空间性能

• 顺序 —— 预分配存储空间不稳定
• 链表 —— 不需分配，元素个数不受限

静态链表

线性表的静态链表存储结构

typedef struct {
    ElemType data;
    int cur;                        /*游标（Cursor）,为0时表示无指向*/
}Component,StaticLinkList[MAXSIZE];

将一维数组space中各分量链成一备用链表，space[0].cur为头指针，“0”表示空指针

ElemType InitList(StaticLinkList space) {
    int i;
    for (i = 0;i < MAXSIZE;i++) 
        space[i].cur = i + 1;
    space[MAXSIZE - 1].cur = 0;     /*目前静态链表为空，最后一个元素的cur为0*/
    return OK;
}

插入操作

/*若备用空间链表非空，则返回分配的结点下标，否则返回0*/
int Malloc_SLL(StaticLinkList space) {
    int i = space[0].cur;           /*当前数组第一个元素的cur存的值，就是要返回的第一个备用空闲的下标*/
    if (space[0].cur)
        space[0].cur = space[i].cur;/*由于要拿出一个分量来使用，所以下一个分量用来做备用*/
    return i;
}

在L中第i个元素之前插入新的数据元素e

ElemType ListInsert(StaticLinkList L,int i,ElemType e) {
    int j, k, l;
    k = MAXSIZE - 1;
    if (i<1 || i>ListLength(L) + 1)
        return ERROR;
    j = Malloc_SLL(L);
    if (j)
    {
        L[j].data = e;
        for (l = 0; l <= i - 1; l++)
            k = L[k].cur;
        L[j].cur = L[k].cur;
        L[k].cur = j;
        return OK;
    }
    return ERROR;
}

删除在L中第i个数据元素e

ElemType ListDelete(StaticLinkList L,int i) {
    int j, k;
    if (i<1||i>ListLength(L))
        return ERROR;
    k = MAXSIZE-1;
    for (j = 0; j <= i - 1; j++)
        k = L[k].cur;
    j = L[k].cur;
    L[k].cur = L[i].cur;
    Free_SSL(L,j);
    return OK;
}

将下标为k的空闲结点回收到备用链表

void  Free_SSL(StaticLinkList space,int k) {
    space[k].cur = space[0].cur;
    space[0].cur = k;
}

初始条件：静态链表L已存在。操作结果：返回L中数据元素个数

int ListLength(StaticLinkList L) {
    int j = 0;
    int i = L[MAXSIZE-1].cur;
    while (i) {
        i = L[i].cur;
        j++;
    }
    return j;
}

静态链表不做赘述

循环链表

p = rearA->next;                   /*保存A表的头结点，*/
rearA->next = rearB->next->next;   /*将本是指向B表的第一个结点赋值给rearA->next*/
q =  rearB->next;				   /**/
rearB->next = p;				   /*将原A表的头结点赋值给rearB->next*/
free(q);                           /*释放q*/

双向链表

线性表的双向链表存储结构

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

原理依据

p->next->prior = p = p->prior->next

插入操作

//插入操作
s->prior = p;                 //把p赋值給s的前驱
s->next = p->next;            //把p->next赋值给s的后继
p->next->prior = s;           //把s赋值给p->next的前驱
p->next = s;                  //把s赋值给p的后继

删除操作

删除操作
p->prior->next = p->next;     //把p->next赋值给p->prior的后继
p->next->prior = p->prior;    //把p->prior赋值给p->的前驱
free(p);                      //释放结点