关于线性表那些事

概念

线性表是零个或多个具有相同特性的数据元素组成的有限序列，该序列中所含元素的个数叫做线性表的长度，线性表有以下几个特点：

  • 首先是一个序列

  • 其次是有限的

  • 可以是有序的也可以是无序的

  • 线性表的开始元素没有前驱元素只有后继元素，线性表的结束元素没有后继元素只有前驱元素，除了开头元素和结尾元素以外，每个元素都有且只有一个前驱元素和后继元素

线性表的结构分为顺序结构和链式结构

顺序结构

顺序表就是把线性表中的所有元素按照某种逻辑顺序，依次存储到从指定位置开始的一块连续的存储空间，重点是连续的存储空间。

数组长度和线性表的长度区别：数组长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的，线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。

关于顺序表的创建和初始化


#define SUCCESS 1

#define FAIL 0

typedef int elemType;

typedef int status;

typedef struct {

    elemType *data;

    int length;

}Sqlist;

status initList(Sqlist *list){

    list->data =  malloc(sizeof(elemType) * MAXSIZE);

    if(!list->data) exit(FAIL);

    list->length = 0;

    return SUCCESS;

}

插入算法步骤

  • 如果插入位置不合理，抛出异常；

  • 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；

  • 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；

  • 将要插入的元素填入位置i处；

  • 长度+1

代码如下：

status insertData(Sqlist *list,int index,elemType data){
    if((index<1) || (index>list->length+1)) return FAIL;

    //存储空间已满
    if(L->length == MAXSIZE) return FAIL;

    //插入数据不在表尾,则先移动出空余位置
    if(index <= list->length){
        for(int j = list->length-1; j>=index-1;j--){
            list->data[j+1] = L->data[j];
        }
    }

    list->data[index-1] = data;
    ++list->length;//长度+1
    return SUCCESS;
}

删除步骤

  • 如果删除位置不合理，抛出异常；

  • 取出删除元素；

  • 从删除位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；

  • 长度减1

代码如下：

status listDelete(Sqlist *list,int i){

    //线性表为空
    if(list->length == 0) return FAIL;

    //i值不合法判断
    if((i<1) || (i>list->length+1)) return FAIL;
    for(int j = i; j < list->length;j++){
        //被删除元素之后的元素向前移动
        list->data[j-1] = list->data[j];
    }

    //表长度-1;
    list->length --;
    return SUCCESS;
}

链式结构

链式结构如图所示

链式结构.png

链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。

在顺序存储结构中，每个数据元素只需要存储数据元素就可以了。现在链式结构中，处理要存储数据元素信息之外，还要存储它的后继元素的存储地址。

在链表中，为了方便定位链表，我们一般会在创建链表的时候，先给他一个头节点，头节点没有实际内容的作用，作为一个链表的哨兵，可以方便定位。

链表主要分成单向链表、单向循环链表、双向链表、双向循环链表，下面我们分别来讲讲。

单向链表

单向链表每一个节点，都包含一个data和一个指向下一个节点的指针


单向链表.png

在初始化单向链表的时候，需要注意头节点是没有内容的，->next下一个节点才是真正的首元节点，代码如下：

Status InitList(LinkList *L){
    *L = (LinkList)malloc(sizeof(Node));
    //存储空间分配失败
    if(*L == NULL) return ERROR;
    //将头结点的指针域置空
    (*L)->next = NULL;
    return OK;
}

单向链表插入和删除

先来看下示意图：

单向链表插入删除.png

插入的主要步骤：

  • 定义一个指针指向链表头节点，初始化j从1开始；

  • 当j < i 时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；

  • 若到链表末尾p为空，则说明第i个结点不存在；否则查找成功，在系统中生成一个空结点s

  • 将数据元素e赋值给 s->data；

  • 单链表的插入标准语句 s->next; p->next=s;

  • 返回成功

删除的主要步骤

  • 定义两个指针指p、s指向链表头节点，初始化i从1开始

  • 判断当前链表是否只有头节点，如果不存在其他节点，return error，否则继续执行

  • 判断是否删除的首元节点，删除第一个节点的时候需要注意把头节点的指针移动到下一个节点

  • 释放，并返回成功

代码如下：
单向链表插入

Status ListInsert(LinkList *L,int i,ElemType e){
    int j;
    LinkList p,s;
    p = *L;
    j = 1;
    //寻找第i-1个结点
    while (p && j<i) {
        p = p->next;
        ++j;
    }
    //第i个元素不存在
    if(!p || j>i) return ERROR;
    //生成新结点s
    s = (LinkList)malloc(sizeof(Node));
    //将e赋值给s的数值域
    s->data = e;
    //将p的后继结点赋值给s的后继
    s->next = p->next;
    //将s赋值给p的后继
    p->next = s;
    return OK;
}

单向链表删除

Status ListDelete(LinkList *L,int i,ElemType *e){
    int j;
    LinkList p,q;
    p = (*L)->next;
    j = 1;
    //查找第i-1个结点,p指向该结点
    while (p->next && j<(i-1)) {
        p = p->next;
        ++j;
    }

    //当i>n 或者 i<1 时,删除位置不合理
    if (!(p->next) || (j>i-1)) return  ERROR;

    //q指向要删除的结点
    q = p->next;

    //将q的后继赋值给p的后继
    p->next = q->next;

    //将q结点中的数据给e
    *e = q->data;

    //让系统回收此结点,释放内存;
    free(q);
    return OK;
}

单向循环链表初始化

先来看一下单向循环链表和单向链表的区别，单向循环链表图如下

单向循环链表.png

单向循环链表就像一个首尾相接的蛇，他的最后一个节点的next不是指向NULL，而是指向了首元节点，以此达到循环。在初始化的时候，需要注意

初始化的时候，需要创建一个新的节点指向自身，往里面增加节点的时候需要注意最后一个节点需要指向首元节点。


#define ERROR 0
#define OK 1
#define MAXSIZE 20

typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

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

typedef struct Node * LinkList;

Status CreateList(LinkList *L){
    int item;
    LinkList temp = NULL;
    LinkList target = NULL;
    printf("输入节点的值，输入0结束\n");
    while(1) {
        scanf("%d",&item);
        if(item==0) break;
        //如果输入的链表是空。则创建一个新的节点，使其next指针指向自己 
        (*head)->next=*head;
        if(*L==NULL) {
            *L = (LinkList)malloc(sizeof(Node));
            if(!L) exit(0);
            (*L)->data=item;
            (*L)->next=*L;
        } else {
          //输入的链表不是空的，寻找链表的尾节点，使尾节点的next=新节点。新节点的next指向头节点
            for (target = *L; target->next != *L; target = target->next);
            temp=(LinkList)malloc(sizeof(Node));
            if(!temp) return ERROR;
            temp->data=item;
            temp->next=*L;  //新节点指向头节点
            target->next=temp;//尾节点指向新节点
        }
    }
    return OK;
}

单向循环链表插入和删除

插入的主要步骤：

  • 定义一个指针target指向链表头节点，初始化j从1开始；

  • 当j < i 时，就遍历链表，让target的指针向后移动，不断指向下一个结点，j累加1；

  • 若到链表末尾target为空，则说明第i个结点不存在；否则查找成功，在系统中生成一个空结点s

  • 将数据元素e赋值给 temp->data = data；

  • 单链表的插入标准语句 temp->next = target->next; target->next = temp;

  • 返回成功

需要注意的是，在插入节点的时候，我们需要判断插入位置是否是第一个节点。如果是第一个节点，需要让新的节点next指向原节点，并且头节点指向新增加节点，修改尾节点。

删除的主要步骤

  • 定义两个指针指temp、taeget向链表头节点，初始化i从1开始

  • 判断当前链表收否只有头节点，如果不存在其他节点，return error，否则继续执行

  • 删除找到的节点，修改前一个节点的next指向，释放被删除的节点

  • 返回成功

删除需要注意头节点

代码定义如下


Status ListInsert(LinkList *L, int place, int num) {
    LinkList temp, target;
    int i;
    if (place == 1) {
        //如果插入的位置为1,则属于插入首元结点,所以需要特殊处理
        //1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
        //2. 找到链表最后的结点_尾结点,
        //3. 让新结点的next 执行头结点.
        //4. 尾结点的next 指向新的头结点;
        //5. 让头指针指向temp(临时的新结点)
        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) {
            return ERROR;
        }
        temp->data = num;
        for (target = *L; target->next != *L; target = target->next);
        temp->next = *L;
        target->next = temp;
        *L = temp;
    } else {
        //如果插入的位置在其他位置;
        //1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
        //2. 先找到插入的位置,如果超过链表长度,则自动插入队尾;
        //3. 通过target找到要插入位置的前一个结点, 让target->next = temp;
        //4. 插入结点的前驱指向新结点,新结点的next 指向target原来的next位置 ;
        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) {
            return ERROR;
        }
        temp->data = num;
        for (i = 1, target = *L; target->next != *L && i != place - 1; target = target->next, i++) ;
        temp->next = target->next;
        target->next = temp;
    }
    return OK;
}

Status  LinkListDelete(LinkList *L, int place) {
    LinkList temp, target;
    int i;

    //temp 指向链表首元结点
    temp = *L;
    if (temp == NULL) return ERROR;
    if (place == 1) {
        if ((*L)->next == (*L)) {
            (*L) = NULL;
            return OK;
        }
        target->next = (*L)->next;
        for (target = *L; target->next != *L; target = target->next) ;

        temp = *L;
        *L = (*L)->next;
        target->next = *L;
        free(temp);
    } else {
        for (i = 1, target = *L; target->next != *L && i != place - 1; target = target->next, i++) ;
        temp = target->next;
        target->next = temp->next;
        free(temp);
    }
    return OK;
}

双向链表和双向循环链表

双向链表相比较单向链表，多了一个前驱，而双向循环链表的则在双向链表的情况下，多了首尾的指向

双向链表.png
双向循环链表.png

初始化

双向和双向循环链表创建.png

对比的代码如下

// 双向链表
Status CreateList(LinkList *L) {
    *L = (LinkList)malloc(sizeof(Node));
    if ((*L) == NULL) return ERROR;
    (*L)->prior = NULL;
    (*L)->next = NULL;
    return OK;
}

// 双向循环链表
Status CreateList(LinkList *L) {
    *L = (LinkList)malloc(sizeof(Node));
    if ((*L) == NULL) return ERROR;
    (*L)->prior = *L;  // 这里和上面不一样，指向自己，
    (*L)->next = *L; 
    return OK;
}

插入

双向链表的插入和单向列表的插入对比，其实是相似的，不同之处在于，双向链表在找到需要插入的节点后，需要先指定插入节点的prior和next，然后再确定proir->next 和 next->prior，大致步骤如下

  • 判断插入的位置是否合法，不合法return error，创建节点temp和指向头节点的链表p，i从1开始

  • 遍历链表，让p的指针向后移动，不断指向下一个结点，i累加1；

  • 若到链表末尾p为空，则说明第i个结点不存在；否则查找成功，在系统中生成一个空结点temp

  • 将数据元素e赋值给 temp->data = e；

  • 指定temp的前驱和后驱

  • 替换temp的前驱的后驱，temp后驱的前驱

  • 返回成功

需要注意的是，在插入节点的时候，我们需要判断插入位置是否是第一个节点。如果是第一个节点，需要让新的节点next指向原节点，并且头节点指向新增加节点，修改尾节点。

双向循环链表步骤比双向链表，少了一步判断首元节点，因为循环链表的尾节点就是指向首元节点。但是需要判断尾节点的指向

代码如下：

// 插入
Status ListInsert(LinkList *L, int place , ElemType v) {
    if (place < 1) return ERROR;
    LinkList temp = (LinkList)malloc(sizeof(Node));

    if (temp == NULL) return ERROR;
    temp->data = v;
    temp->prior = NULL;
    temp->next = NULL;
    // 找到插入前的节点
    LinkList p = *L;
    // 找到插入位置 (place 位置的前一个结点)
    for (int i = 1; i < place; i++) {
        if (p->next == NULL) break;
        p = p->next;
    }

    if (p->next == NULL) {
        p->next = temp;
        temp->prior = p;
    } else {
        p->next->prior = temp;
        temp->next = p->next;
        temp->prior = p;
        p->next = temp;
    }
    return OK;
}

Status ListInsert(LinkList *L, int place , ElemType v) {
    // 有头节点 所以插入位置不能是<1
    if (place < 1) return ERROR;
    // 新节点
    LinkList temp = (LinkList)malloc(sizeof(Node));
    if (temp == NULL) return ERROR;
    temp->data = v;
    temp->prior = NULL;
    temp->next = NULL;

    // 找到插入前的节点
    LinkList p = *L;

    // 找到插入位置 (place 位置的前一个结点)
    for (int i = 1; i < place; i++) {
        if (p->next == NULL) break;
        p = p->next;
    }

    // 注意：因为有头节点，所有新节点一定是在头节点之后，所以头指针L，一定指向头节点
    if (p->next == NULL) {
        p->next = temp;
        temp->prior = p;
    } else {
        p->next->prior = temp;
        temp->next = p->next;
        temp->prior = p;
        p->next = temp;
    }
    return OK;
}

删除

双向链表对比与单向链表的删除，需要注意是不是删除尾节点，因为尾节点的next需要为NULL；双向循环链表的删除对比单向循环链表，仍然需要考虑是不是尾节点，因为他有下一个节点，把下一个节点和他前一个节点建立互相指向，释放自己。因为有头节点的引入，所以我们不需要额外关注头指针的指向了。

代码示例如下：

// 双向链表删除
Status ListDelete(LinkList *L, int place, ElemType *v) {
    // 有头节点 所以插入位置不能是<1
    if (place < 1) return ERROR;
    // 找到place位置的节点
    LinkList p = (*L)->next; // 从首元节点开始
    int i = 1
    for (; i < place; i++) {
        if (p->next == NULL) break;
        p = p->next;
    }
    if (i < place) return ERROR;
    *v = p->data;
    if (p->next == NULL) {
        p->prior->next = NULL;
        free(p);
    } else {
        // p是任意位置的节点
        // 1、将p的后一个节点指向p的前一个节点
        // 2、将p的前一个节点指向p的后一个节点
        // 3、释放
        p->next->prior = p->prior;
        p->prior->next = p->next;
        free(p);
    }
    return 1;
}

// 双向循环链表删除
Status ListDelete(LinkList *L, int place, ElemType *v) {
    if (place < 1) return ERROR;
    LinkList p = (*L)->next; // 从首元节点开始
    int i = 1;
    for (; i < place; i++) {
        if (p->next == NULL) break;
        p = p->next;
    }
    if (i < place) return ERROR;
    *v = p->data;
    // p是任意位置的节点
    // 1、将p的后一个节点指向p的前一个节点
    // 2、将p的前一个节点指向p的后一个节点
    // 3、释放

    p->next->prior = p->prior;
    p->prior->next = p->next;
    free(p);
    return 1;
}

结尾

总算把单向链表、单向循环链表、双向链表、双向循环链表理了一遍，但是结尾处有点匆忙，下次有时间再补一下图片和详细优化吧。写博客真的好累啊(´▽｀)

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