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

链式表示

线性表的链式存储结构的特点是用一组任意的得存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示a_i和a_i+1之间的逻辑关系，对数据元素a_i来说，除了存储其本身的信息之外，还需存储一个指示其直接后继存储位置的信息。这两部分信息组成a_i的存储映像，称为结点（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

最后编辑于：2018.05.10 07:25:32

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