线性表

抽象数据类型的标准格式:ADT(Abstract Date Type)

ADT 抽象数据类型名
Data    
    数据元素之间逻辑关系的定义
Operation 
    操作
endADT

线性表抽象数据类型格式

ADT 线性表(List) 
Data 
    线性表的数据对象集合为{a1,a2,...,an},每个元素的类型均为DataType。
    其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素；
    除最后一个元素an外，每一个元素有且只有一个直接后驱元素。
    数据元素之间的关系是一对一的关系。
Operation
    InitList(*L):           初始化操作，建立一个空的线性表L。 
    ListEmpty(L):           若线性表为空，返回true，否则返回false。 
    ClearList(*L):          将线性表清空。
    GetElem(L,i,*e):        将线性表L中的第i个位置元素值返回给e。
    LocateElem(L,e):        在线性表L中查找与定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败。
    ListInsert(*L,i,e):     在线性表L中的第i个位置插入新元素e。
    ListDelete(*L,i,*e):    删除线性表L中的第i个位置元素，并用e返回其值。
    ListLength(L):          返回线性表L的元素个数
endADT

上面说到的Operation是最基本的操作（基操基操），对于实际问题中涉及到的关于线性表的复杂操作，完全可以用这些基本操作组合实现。
例如：求A=A∪B(将B中A不存在的元素找出，插入到A中)

/*
    Name: A=A∪B
    Author:Liweidong
    Date: 16/07/18 15:00
    Description:  求集合A与B的并集。
*/ 
void unionL(List *La,List *Lb){
    int La_len,Lb_len,i;
    ElemType e;
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    
    for(i=1;i<Lb_len;i++){
        GetElem(Lb,i,&e);
        if(!LocateElem(*La,e))
            ListInsert(La,++La_len,e);
    }
}

线性表的顺序存储结构(sequence list ->SqList)

线性表的顺序存储的结构代码

#define MAXSIZE 20
typedef int ElemType;   //ElemType类型根据实际情况确定，此处假设为int。
typedef struct
{
    ElemType data[MAXSIZE];
    int length;
}SqList;

GetElem(L,i,*e)：

将线性表L中的第i个位置元素值返回给e。

算法思路：

  • 只要 i 的数值在数组下标范围内，就返回数组第 i - 1 的值即可
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
/*  
    Status是函数的类型，其值是函数结果状态代码，如OK等。
    初始条件：顺序线性表L已存在，1 ≤ i ≤ ListLength(L)。
    操作结果：用e返回L中第i个数据元素的值
*/

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;
}

ListInsert(*L,i,e):

在线性表L中的第i个位置插入新元素e。

算法思路：

  1. 如果插入位置不合理，抛出异常；
  2. 如果线性表长度大于数组长度，则抛出异常或动态增加容量；
  3. 从最后一个元素开始向前遍历到第i个元素，分别将它们都向后移动一个位置；
  4. 将要插入元素填入位置i处；
  5. 表长加1.
/*  
    初始条件：顺序线性表L已存在，1 ≤ i ≤ ListLength(L)。
    操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
*/

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;
}

ListDelete(L,i,e):

删除线性表L中的第i个位置元素，并用e返回其值。

算法思路：

  1. 如果删除位置不合理，抛出异常；
  2. 取出删除元素；
  3. 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
  4. 表长减1。
/*  
    初始条件：顺序线性表L已存在，1 ≤ i ≤ ListLength(L)。
    操作结果：删除线性表L中的第i个位置元素，并用e返回其值,L的长度减1.
*/

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;
}

线性表顺序存储结构的优缺点

优点：

  • 无须为表示表中元素之间的逻辑关系而增加额外的存储空间；
  • 可以快速的存取表中任一位置的元素。

缺点：

  • 插入和删除操作需要移动大量的数据(参考代码，时间复杂度为n)；
  • 当线性表长度变化较大时，难以确定存储空间的容量；
  • 造成存储空间的"碎片"。

顺序表的链式存储结构

一些名词定义：

  • 为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，
  • 对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即地址)。
  • 把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。
  • 指针域中存储的信息称作指针或链。
  • 这两部分信息组成数据元素ai的存储映像，称为结点(Node)。
  • n个结点(ai的存储映像)链结成一个链表，即为线性表的链式存储结构。
  • 因为此链表的每个结点只包含一个指针域，所以叫做单链表。

头指针和头结点

头指针：链表中第一个结点的存储位置叫做头指针；
头结点：在单链表的第一个结点前附设一个结点，称为头结点。

异同点：

  1. 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针；
  2. 头指针具有标志作用，所以常用头指针冠以链表的名字；(标志冠名)
    无论链表是否为空，头指针均不为空。头指针是链表的必要元素。(必须存在)
  3. 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义;(也可存放链表的长度)
  4. 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了；(方便插入、删除操作)
  5. 头结点不一定是链表的必须要素。(可有可无)

线性表的链式存储的结构代码(链表：linked list -> LinkList)

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

GetElem(L,i,*e)：

将线性表L中的第i个位置元素值返回给e。

算法思路：

  1. 声明一个指针p指向链表第一个结点，初始化j从1开始；
  2. 当 j < i 时，就遍历链表，让p的指针向后移动，不断的指向下一结点，j累加1；
  3. 若到链表末尾p为空，则说明第i个结点不存在；
  4. 否则查找成功，返回结点p的数据。
/*  
    初始条件：顺序线性表L已存在，1 ≤ i ≤ ListLength(L)。
    操作结果：用e返回L中第i个数据元素的值。
    核心思想：工作指针后移。
*/
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>i)
        return ERROR;
    
    *e = p->data;
    
    return OK;
}

ListInsert(*L,i,e):

在线性表L中的第i个位置插入新元素e。

算法思路：

  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. 返回成功。
/*  
    初始条件：顺序线性表L已存在，1 ≤ i ≤ ListLength(L)。
    操作结果：在L中第i个结点位置之前插入新的数据元素e，L的长度加1。
    核心思想：工作指针后移。
*/

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

ListDelete(L,i,e):

删除线性表L中的第i个位置元素，并用e返回其值。

算法思路：

  1. 声明一个指针p指向链表第一个结点，初始化j从1开始；
  2. 当 j < i 时，就遍历链表，让p的指针向后移动，不断的指向下一结点，j累加1；
  3. 若到链表末尾p为空，则说明第i个结点不存在；
  4. 否则查找成功，将欲删除的结点p->next赋值给q；
  5. 单链表的删除标准语句 p->next = q->next;
  6. 将q结点中的值重新赋值给e，作为返回；
  7. 释放q结点；
  8. 返回成功。
/*  
    初始条件：顺序线性表L已存在，1 ≤ i ≤ ListLength(L)。
    操作结果：删除线性表L中的第i个位置元素，并用e返回其值,L的长度减1。
    核心思想：工作指针后移。
*/

Status ListDelete(LinkList *L,int i,ElemType e)
{
    int k;
    LinkList p,q;
    p = *L;
    k = 1;
    
    while (p->next && k<i)
    {
        p = p->next;
        ++k;
    }
    
    if(!(p->next) || k>i)
        return ERROR;
    
    q = p->next;
    p->next = q->next;
    *e = q->date;
    free(q);
        
    return OK;
}

单链表的整表创建

算法思路：

  1. 声明一指针P和计数器变量i;
  2. 初始化一空链表L;
  3. 让L的头结点的指针指向NULL，即建立一个带头结点的单链表;
  4. 循环：
    • 生成一新结点赋值给p;
    • 随机生成一数字赋值给p的数据域p->data;
    • 将p插入到头结点与前一新结点之间。
//  头插法创建单链表
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;
        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;
    
    for(i=0; i<n; i++){
        p = (Node *)malloc(sizeof(Node));
        p->data = rand()%100+1;
        r->next = p;
        r = p;
    }
    r->next = NULL;
}

单链表的整表删除

算法思路：

  1. 声明一结点p和结点q;
  2. 将第一个结点赋值给p;
  3. 循环
    • 将下一节点赋值给q;
    • 释放p;
    • 将q赋值给p;
//  删除单链表(将L置为空表) 
Status ClearList(LinkList *L){
    LinkList p,q;
    p = (*L)->next;
    while(p){
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;
    return OK;
}

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

存储分配方式：

顺序表用一段连续的存储单元依次存储线性表的数据元素
单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

时间性能：

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

空间性能：

顺序表需预分配存储空间，分大了，浪费；分小了，易发生溢出
单链表不需要分配空间，只要有就可以分配，元素个数也不受限制

TO BE CONTINUE

静态链表

循环链表

双向链表

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 214,875评论 6赞 496
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,569评论 3赞 389
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 160,475评论 0赞 350
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,459评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,537评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,563评论 1赞 293
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,580评论 3赞 414
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,326评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,773评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,086评论 2赞 330
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,252评论 1赞 343
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,921评论 5赞 338
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,566评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,190评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,435评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,129评论 2赞 366
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,125评论 2赞 352