美文网首页
线性表（二）链式结构表示与实现

线性表（二）链式结构表示与实现

作者: 张小罗 | 来源:发表于2018-05-10 07:24 被阅读6次
链式表示

线性表的链式存储结构的特点是用一组任意的得存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示ai和ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继存储位置的信息。这两部分信息组成ai的存储映像，称为结点（node）。
结点包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。n个结点链组成一个链表，即为线性表的链式存储结构。由于每个节点中只包含一个指针域，故又称线性链表或单链表。

元素定义
typedef int ElemType;
单链表定义
typedef struct LNode{
        ElemType data;
        struct LNode *next;
}LNode, *LinkList;            // 带头结点线性链表

我们在单链表的第一个结点之前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表长度等类的附加信息，头结点的指针指向第一个元素结点的存储位置。

链式存储

在单链表中，任何两个元素的存储位置之间没有固定的联系。然后，每个元素的存储位置都包含在其直接前驱结点的信息之中，由此在单链表中，去得第i个数据元素必须从头指针出发寻找。因此单链表是非随机存取的存储结构，这种存储结构相对于顺序存储结构，具有空间利用合理，插入和删除时不需要移动等优点，因此在很多场合下，链式存储是线性表的首选存储结构。

基本操作
#include <stdio.h>
#include <stdlib.h>

#define FAILURE -1
#define SUCCESS 1

typedef int ElemType;  // 元素定义

typedef struct LNode{
        ElemType data;
        struct LNode *next;
}LNode, *LinkList;      // 带头结点

int compare(ElemType e1, ElemType e2){
        // 比较e1和e2元素是否相同，具体实现和ElemType类型有关
        if(e1 == e2) 
                return SUCCESS;
        else
                return FAILURE;
}

int visit(ElemType e){ 
        // 访问e元素，具体实现和ElemType类型有关
        printf("%d ", e); 
        return SUCCESS;
} 

void InitList_L(LinkList *L){
        // 初始化线性链表，L指向data为空的头结点
        *L = (LinkList)malloc(sizeof(LNode));
        if (!*L) exit(-1);      //创建头结点失败
        (*L)->next = NULL;
}

void DestroyList_L(LinkList *L){
        // 销毁单链表, 不仅释放数据节点，也销毁头结点
        LinkList p = *L;        //头结点
        LinkList np; 
        while(p){
                np = p->next;
                free(p);
                p = np; 
        }   
        *L = NULL;
}

void ClearList_L(LinkList *L){
        // 带头结点的链表,仅清除数据节点
        LinkList p = (*L)->next;
        LinkList np; 
        while(p){
                np = p->next;
                free(p);
                p = np; 
        }   
        (*L)->next = NULL;
}

int ListEmpty_L(LinkList L){ 
        if(L->next == NULL)
                return SUCCESS;
        else
                return FAILURE;
}

int ListLength_L(LinkList L){
        // 返回单链表的长度
        int i = 0;
        while(L->next){
                i++;
                L = L->next;
        }
        return i;
}

int GetElem_L(LinkList L, int i, ElemType *e){
        // 用e返回线性表L中第i位置元素
        // 其中1<=i<=L.length
        int p = 1;
        L = L->next;
        while(L && p < i){
                p++;
                L = L->next;
        }
        if(!L || p > i) return FAILURE;
        *e = L->data;
        return SUCCESS;
}

int LocateElem_L(LinkList L, ElemType e, int (*compare)(ElemType, ElemType)){
        // 从L中查找第一个与e元素满足compare函数关系的元素
        // 如果不存在则返回0
        int p = 1;
        L = L->next;
        while(L){
                if(compare(L->data, e) > 0){    // 找到
                        return p;
                } else{
                        L = L->next;
                        p++;
                }
        }
        return FAILURE;
}

int PriorElem_L(LinkList L, ElemType cur_e, ElemType *pre_e){
        // 若cur_e是L中元素且不是第一个，则用pre_e返回它的前驱，否则失败
        LinkList pre, cur;
        pre = L;
        cur = L->next;
        if(cur->data == cur_e) return FAILURE;  //第一个位置
        while(cur && cur->data != cur_e){
                pre = cur;
                cur = cur->next;
        }
        if(!cur) return FAILURE;
        *pre_e = pre->data;
        return SUCCESS;
}

int NextElem_L(LinkList L, ElemType cur_e, ElemType *next_e){
        // cur_e是L中元素且不是最后一个，则用next_e返回它的后继元素
        LinkList cur, next;
        cur = L;
        next = cur->next;
        while(next && cur->data != cur_e){
                cur = next;
                next = next->next;
        }
        if(!next) return FAILURE;
        *next_e = next->data;
        return SUCCESS;
}

int InsertList_L(LinkList L, int i, ElemType e){
        // 在带头结点的L中第i位置之前插入e
        LNode *p = L;   // p指向L头结点
        int j=0;
        while(p && j<i-1){
                p = p->next;
                j++;
        }
        if(!p || j > i-1) return FAILURE;       // i值不合理
        LNode *s = (LNode*)malloc(sizeof(LNode));
        s->data = e;
        s->next = p->next;
        p->next = s;
        return SUCCESS;
}

int DeleteList_L(LinkList L, int i,  ElemType *e){
        // 删除线性链表L中第i位置节点，并由e返回
        LNode *p = L;
        int j = 0;
        while(p && j<i-1){
                p = p->next;
                j++;
        }
        if(!p || j>i-1) return FAILURE;
        // 此时p指向第i-1位置节点
        // q指向待删除节点
        LNode *q = p->next;
        // 移除节点
        p->next = p->next->next;
        // 将值返回
        *e = q->data;
        free(q);
        return SUCCESS;
}

int ListTraverse_L(LinkList L, int (*visit)(ElemType)){
        // 对L中每一个元素调用visit函数，一旦visit失败，则操作失败
        L = L->next;
        while(L){
                if(visit(L->data) < 0) return FAILURE;
                L = L->next;
        }
        return SUCCESS;
}

void MergeList_L(LinkList La, LinkList Lb, LinkList *Lc){
        // 归并两个有序线性链表，要求结果也有序排列
        LNode *pa = La->next, *pb = Lb->next;
        LNode *pc;
        *Lc = pc = La;  // Lc以La头结点为头结点
        while(pa && pb){
                if(pa->data <= pb->data){
                        pc->next = pa;
                        pa = pa->next;
                } else{
                        pc->next = pb;
                        pb = pb->next;
                }

                pc = pc->next;
        }
        // 归并剩余结点
        pc->next = pa ? pa:pb;
        free(Lb);       // 释放Lb头结点
}

void difference(LinkList La, LinkList Lb){
        // 计算带头结点的线性链表La和Lb的差集，并将结果保存在La链表中
        LinkList pa = La;
        while(pa->next){
                LinkList pb = Lb->next;
                while(pb && pb->data != pa->next->data) pb = pb->next;
                if(!pb) pa = pa->next;  // 没有在pb中找到
                else {                  // 在pb中找到
                        LinkList tem = pa->next;
                        pa->next = pa->next->next;
                        free(tem);
                }
        }
}

void main(){
        // 声明线性列表L
        LinkList L;
        // 初始化线性列表，令L指向头结点
        printf("****************** init list *************\n");
        InitList_L(&L);
        // 头结点位置
        printf("L position is: %p\n", L);
        // 头结点中data值
        printf("L data is: %d\n", L->data);
        // 插入值
        printf("*********** insert value ************\n");
        int a[] = {1, 3, 4, 5, 10, 5, 7};
        int i;
        for(i=0;i<7;i++){
                InsertList_L(L, i+1, a[i]);
        }
        printf("插入值后：\n");
        ListTraverse_L(L, visit);
        // get elem
        printf("\n****************** get elem from L*************\n");
        ElemType e1, e2;
        if(GetElem_L(L, 0, &e1) > 0){
                printf("get elem at index 0 success, reutrn value: %d\n", e1);
        } else {
                printf("get elem at index 0 failure\n");
        }
        if(GetElem_L(L, 4, &e2) > 0){
                printf("get elem at index 4 success, return value: %d\n", e2);
        } else {
                printf("get elem at index 4 failure\n");
        }
        if(GetElem_L(L, 20, &e2) >0){
                printf("get elem at index 20 success, return value: %d\n", e2);
        } else {
                printf("get elem at index 20 failure.\n");
        }
        // locate elem
        printf("\n***************** locate elem *************** \n");
        int index1, index2;
        index1 = LocateElem_L(L, -10, compare);
        index2 = LocateElem_L(L, 7, compare);
        if(index1 > 0){
                printf("locate -10 in L success, index at: %d\n", index1);
        } else {
                printf("locate -10 in L failure!\n");
        }
        if(index2 > 0){
                printf("locate 7 in L success, index at: %d\n", index2);
        } else {
                printf("locate 7 in L failure!\n");
        }
        // prior elem
        printf("\n*********** prior elem *************\n");
        ElemType pre_e1, pre_e2;
        if(PriorElem_L(L, 1, &pre_e1) > 0){
                printf("find prior elem of 1 in L success, value is: %d\n",
                                pre_e1);
        } else {
                printf("find prior elem of 1 in L failure!\n");
        }
        if(PriorElem_L(L, 7, &pre_e2) > 0){
                printf("find prior elem of 7 in L success, value is: %d\n",
                                pre_e2);
        } else {
                printf("find prior elem of 7 in L failure!\n");
        }
        // next elem
        printf("\n************ next elem ************\n");
        ElemType next_e1, next_e2;
        if(NextElem_L(L, 1, &next_e1) > 0){
                printf("find next elem of 1 in L success, valueu is: %d\n",
                                next_e1);
        } else {
                printf("find next elem of 1 in L failure!\n");
        }
        if(NextElem_L(L, 7, &next_e2) > 0){
                printf("find next elem of 7 in L success, value is: %d\n",
                                next_e2);
        } else {
                printf("find next elem of 7 failure!\n");
        }
        // traverse
        printf("\n***********traverse************\n");
        if(ListTraverse_L(L, visit) > 0){
                printf("traverse L success!\n");
        } else {
                printf("traverse L failure!\n");
        }
        // 删除一个元素
        ElemType e;
        printf("\n**************delete elem******************\n");
        if(DeleteList_L(L, 1, &e)>0){
                printf("delete success at index 1, deleted value is: %d\n", e);
        } else {
                printf("delete failure at index 1\n");
        }
        printf("now elem: ");
        ListTraverse_L(L, visit);
        printf("\n");

        if(DeleteList_L(L, 0, &e)>0){
                printf("delete success at index 0, deleted value is: %d\n", e);
        } else {
                printf("delete failure at index 0\n");
        }

        if(DeleteList_L(L, 6, &e)>0){
                printf("delete success at index 6, deleted value is: %d\n", e);
        } else {
                printf("delete failure at index 6\n");
        }
        // 销毁
        printf("********** destroy **************\n");
        DestroyList_L(&L);
        printf("L position is: %p\n", L);

        // 归并两个顺序表
        printf("\n********* start Merge ****************\n");
        LinkList La, Lb, Lc;
        InitList_L(&La);
        InitList_L(&Lb);
        InitList_L(&Lc);

        int la[] = {2, 4, 5, 10, 22};
        int lb[] = {1, 3, 8, 10, 12, 22, 34};

        for(i=0;i<5;i++){
                InsertList_L(La, i+1, la[i]);
        }
        for(i=0;i<7;i++){
                InsertList_L(Lb, i+1, lb[i]);
        }

        printf("La is: ");
        ListTraverse_L(La, visit);
        printf("\nLb is: ");
        ListTraverse_L(Lb, visit);
        MergeList_L(La, Lb, &Lc);
        printf("\nthe merge result Lc is: ");
        ListTraverse_L(Lc, visit);
        printf("\n");

        // 求差集
        LinkList Ld, Le;
        InitList_L(&Ld);
        InitList_L(&Le);

        int ld[] = {5, 10, 20, 15, 25, 30};
        int le[] = {5, 15, 35, 25, 30};

        for(i=0;i<6;i++){
                InsertList_L(Ld, i+1, ld[i]);
        }
        for(i=0;i<5;i++){
                InsertList_L(Le, i+1, le[i]);
        }

        printf("\n************** compute difference*****\n");
        printf("Ld is: ");
        ListTraverse_L(Ld, visit);
        printf("\n");
        printf("Le is: ");
        ListTraverse_L(Le, visit);

        printf("\nthe result that value in Ld and not in Le is: ");
        difference(Ld, Le);
        ListTraverse_L(Ld, visit);

        printf("\n");
}
运行结果
****************** init list *************
L position is: 0x24e6010
L data is: 0
*********** insert value ************
插入值后：
1 3 4 5 10 5 7 
****************** get elem from L*************
get elem at index 0 failure
get elem at index 4 success, return value: 5
get elem at index 20 failure.

***************** locate elem *************** 
locate -10 in L failure!
locate 7 in L success, index at: 7

*********** prior elem *************
find prior elem of 1 in L failure!
find prior elem of 7 in L success, value is: 5

************ next elem ************
find next elem of 1 in L success, valueu is: 3
find next elem of 7 failure!

***********traverse************
1 3 4 5 10 5 7 traverse L success!

**************delete elem******************
delete success at index 1, deleted value is: 1
now elem: 3 4 5 10 5 7 
delete failure at index 0
delete success at index 6, deleted value is: 7
********** destroy **************
L position is: 0x7ffe356bc5f8

********* start Merge ****************
La is: 2 4 5 10 22 
Lb is: 1 3 8 10 12 22 34 
the merge result Lc is: 1 2 3 4 5 8 10 10 12 22 22 34 

************** compute difference*****
Ld is: 5 10 20 15 25 30 
Le is: 5 15 35 25 30 
the result that value in Ld and not in Le is: 10 20

相关文章

  • 线性表（二）链式结构表示与实现

    链式表示 线性表的链式存储结构的特点是用一组任意的得存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以...

  • 数据结构与算法-C语言6-线性表之链式存储结构

    数据结构与算法-目录 1、线性表的链式存储结构 1.1、线性表链式存储结构定义 线性表的链式存储结构的特点是用一组...

  • C++线性表的链式存储结构

    C++实现线性表的链式存储结构： 为了解决顺序存储不足：用线性表另外一种结构-链式存储。在顺序存储结构(数组描述)...

  • 线性表(三)——双向链表的表示和实现

    在上篇文章中我们分析讨论了线性表的链式存储结构。链式存储结构表示的线性表主要分为单链表、单循环链表和双向循环链表三...

  • 数据结构-线性表（顺序表和链表）

    大纲：理解线性表的逻辑结构掌握线性表的顺序存贮结构和链式存贮结构；掌握线性表基本操作的实现。了解线性表的应用。 线...

  • 线性表---GoLang实现

    线性表 线性表分为顺序存储结构和链式存储结构 线性表的顺序存储结构 优点：无需为表示表中元素之间的逻辑关系而增加额...

  • 第二讲-线性表

    第二讲 什么是线性表 由同类型数据元素构成的有序序列结构。线性表可以用顺序存储结构，也可以使用链式存储结构。链式结...

  • 线性表的链式存储结构Java实现

    有了前面文章的铺垫：数据结构的基本理解线性表及其顺序存储结构的理解线性表的顺序存储结构java实现线性表链式存储就...

  • 数据结构之有序线性表的链式存储结构

    之前写了线性表的顺序存储结构和有序线性表的顺序存储结构以及线性表的链式存储结构,今天接着写有序线性表的链式存储结 ...

  • 线性表的链式存储--单链表

    Java之线性表的链式存储——单链表 我们都知道，线性表的存储结构分为两种，顺序存储结构和链式存储结构，线性表的分...

网友评论

      本文标题：线性表（二）链式结构表示与实现

      本文链接：https://www.haomeiwen.com/subject/obiprftx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|线性表（二）链式结构表示与实现|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！