线性表的链式表示和实现

2017-04-04 本文已影响68人小黑_Coder

继上一篇博客讨论了线性表的顺序表示和实现今天我们就来讨论和实现一下线性表的链式存储。从上一片博客分析，我们知道线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也是相邻，因此可以随机存取表中任一元素。但是这个特点也带了此存储结构的弱点，就是在插入和删除操作时需要移动大量的元素。而我们今天要讨论的线性表的链式存储结构，由于它不要求逻辑上相邻的元素位置也要相邻，因此就能很好的避免移动元素，但是会失去随机存取的优点

名词解释

线性链表

用一组任意的储存单元存储线性表的数据元素，这组存储单元可以是连续也可以是不连续。

结点

为了表示表示每个元素a与其直接后继元素b之间的逻辑关系，对于数据元素a来说除了存储其本身的信息之外，还需要存储一个指示其直接后继b的位置信息，这两部分信息组成数据元素a的储存映像，称为结点。

数据域

结点中存储数据元素信息的域

指针域

结点中存储直接后继位置信息的域

单链表

每个结点中只包含一个指向直接后继地址的指针域的链表

线性表的单链表存储结构

typedef struct LNode {
    
    ElemType data;          //存储数据元素
    struct LNode *next;     //结点，指向直接后继元素地址
    
}SinglyLinkList;

基本操作

SinglyLinkList * InitSinglyLinkList();
Status InsertElemIntoSinglyLinkList(SinglyLinkList *linkList, int index, ElemType elem);
Status GetElemFromSinglyLinkList(SinglyLinkList linkList, int index, ElemType *elem);
Status GetIndexFromSinglyLinkList(SinglyLinkList linkList, int *index, ElemType elem);
Status DeleteElemFromSinglyLinkList(SinglyLinkList *linkList, int index);
Status IsElemFromSinglyLinkList(SinglyLinkList linkList, ElemType elem);
Status AppendElemForSinglyLinkList(SinglyLinkList *linkList, ElemType elem);
Status LengthSinglyLinkList(SinglyLinkList linkList, int *length);
Status ClearSinglyLinkList(SinglyLinkList *linkList);
Status DestroySinglyLinkList(SinglyLinkList *linkList);
Status PrintSinglyLinkList(SinglyLinkList linkList);

基本操作实现

初始化

SinglyLinkList * InitSinglyLinkList() {
    
    SinglyLinkList *linkList = (SinglyLinkList *)malloc(sizeof(SinglyLinkList));
    if (!linkList) {
        
        printf("OVERFLOW %s", __func__);
        return NULL;
    }
    linkList->data = 0;
    linkList->next = NULL;
    return linkList;
}

初始化即在堆上开辟sizeof(SinglyLinkList)大小的空间作为链表的头结点，然后将头结点的地址返回

插入元素

Status InsertElemIntoSinglyLinkList(SinglyLinkList *linkList, int index, ElemType elem) {
    
    if (index < 1 || !linkList) {
        
        return ERROR;
    }
    SinglyLinkList *listPointer = linkList;
    int counter = 1;
    while (listPointer && counter < index) {
        
        listPointer = listPointer->next;
        counter++;
    }
    if (!listPointer || counter > index) {
        
        return ERROR;
    } else {
    
        SinglyLinkList *insert = (SinglyLinkList *)malloc(sizeof(SinglyLinkList));
        if (!insert) {
            
            return OVERFLOW;
        } else {
            
            SinglyLinkList *temp = listPointer->next;
            listPointer->next = insert;
            insert->data = elem;
            insert->next = temp;
            return OK;
        }
    }
}

操作流程

首先寻找要插入元素的位置，如果链表活着插入位置不合法直接返回ERROR。在链表中插入一个元素，即为插入一个结点，因此先在堆上开辟一个InsertLNode结点，然后将InsertLNode结点插入到原链表中。
操作演示
- 说明：A->B：A的后继结点是B A=>B：A指针指向B A.next：A结点中的指针域
- 操作前:HEAD->A->B->C->D insertIndex = 3 listPointer => HEAD
- 寻找插入位置:HEAD->A->B->C->D listPointer => B
- 开辟插入空间:HEAD->A->B->C->D listPointer => B insertLNode
- 初始化临时指针:temp=>listPointer.next即为temp=>C
- 插入:listPointer.next = insertLNode insertLNode.next = temp即为HEAD->A->B(listPointer)->insertLNode->C(temp)->D
- 复制:insertLNode.data = elem

根据下标获取元素

Status GetElemFromSinglyLinkList(SinglyLinkList linkList, int index, ElemType *elem) {
    
    if (index < 1) {
        
        return ERROR;
    }
    SinglyLinkList *listPointer = linkList.next;
    int counter = 1;
    while (listPointer && counter < index) {
        
        listPointer = listPointer->next;
        counter++;
    }
    if (!listPointer || counter > index) {
        
        return ERROR;
    } else {
        
        *elem = listPointer->data;
        return OK;
    }
}

根据元素获取下标

Status GetIndexFromSinglyLinkList(SinglyLinkList linkList, int *index, ElemType elem) {
    
    SinglyLinkList *listPointer = linkList.next;
    int counter = 1;
    while (listPointer) {
        
        if (listPointer->data == elem) {
            
            *index = counter;
            return OK;
        }
        listPointer = listPointer->next;
        counter++;
    }
    return ERROR;
}

删除元素

Status DeleteElemFromSinglyLinkList(SinglyLinkList *linkList, int index) {
    
    if (index < 1 || !linkList) {
        
        return ERROR;
    }
    SinglyLinkList *listPointer = linkList;
    int counter = 1;
    while (listPointer && counter < index) {
        
        listPointer = listPointer->next;
        counter++;
    }
    if (!listPointer || counter > index || !listPointer->next) {
        
        return ERROR;
    } else {
        
        SinglyLinkList *temp = listPointer->next;
        listPointer->next = temp->next;
        free(temp);
        return OK;
    }
}

在删除元素之后一定要记得free(deleteLNode)

判断是否是链表中的元素

Status IsElemFromSinglyLinkList(SinglyLinkList linkList, ElemType elem) {
    
    SinglyLinkList *listPointer = linkList.next;
    while (listPointer) {
        
        if (listPointer->data == elem) {
            
            return OK;
        }
        listPointer = listPointer->next;
    }
    return ERROR;
}

在链表后面拼接元素

Status AppendElemForSinglyLinkList(SinglyLinkList *linkList, ElemType elem) {
    
    if (!linkList) {
        
        return ERROR;
    }
    SinglyLinkList *listPointer = linkList;
    while (listPointer->next) {
        
        listPointer = listPointer->next;
    }
    SinglyLinkList *append = (SinglyLinkList *)malloc(sizeof(SinglyLinkList));
    if (!append) {
        
        return OVERFLOW;
    }
    listPointer->next = append;
    append->next = NULL;
    append->data = elem;
    return OK;
}

拼接元素需要注意的时候append->next = NULL

获取链表的长度

Status LengthSinglyLinkList(SinglyLinkList linkList, int *length) {
    
    int counter = 0;
    SinglyLinkList *listPointer = linkList.next;
    while (listPointer) {
        
        counter++;
        listPointer = listPointer->next;
    }
    *length = counter;
    return OK;
}

清空链表

Status ClearSinglyLinkList(SinglyLinkList *linkList) {
    
    if (!linkList) {
        
        return ERROR;
    }
    SinglyLinkList *listPointer = linkList->next;
    while (listPointer) {
        
        SinglyLinkList *temp = listPointer;
        listPointer = listPointer->next;
        free(temp);
    }
    linkList->next = NULL;
    return OK;
}

保留头结点，此链表还可以使用

销毁链表

Status DestroySinglyLinkList(SinglyLinkList *linkList) {
    
    if (linkList) {
        
        ClearSinglyLinkList(linkList);
    }
    free(linkList);
    linkList = NULL;
    return OK;
}

会要头结点也要free，并且要将linkList = NULL不然会出现野指针，此后链表不可在使用

输出链表

Status PrintSinglyLinkList(SinglyLinkList linkList) {
    
    SinglyLinkList *listPointer = linkList.next;
    int counter = 1;
    while (listPointer) {
        
        printf("the %dth elem is %d \n", counter, listPointer->data);
        counter++;
        listPointer = listPointer->next;
    }
    return OK;
}

线性链表特点

根据对线性链表基本操作的实现我们知道，我们在插入和删除元素的时候不需要移动其他元素，每一种基本操作的时间复杂度也相对比较清晰，这里就不在过多的赘述了。下面对比线性表的顺序表说一说链表和顺序表的区别。

顺序表在内存中是逐个存放的，也就是说第一个元素在地址A，则第二个元素就在地址A+1。
而链表每个节点没有相对固定的位置关系，某个节点在地址A其后的节点不一定是A+1，而在内存的其他空闲区域，呈现一种随机的状态。
链表的特性是在中间任意位置添加删除元素的都非常的快，不需要移动其它的元素。
但是链表在获取一个元素的时候需要从头结点开始遍历链表，没有顺序变那么快。

欢迎讨论

GitHub:https://github.com/LHCoder2016/DataStructure.git
Email:huliuworld@yahoo.com