数据结构与算法之线性表

本文内容：
线性表的顺序存储
 线性表的链式存储-单向链表
 线性表的连式存储-双向链表

线性表的定义

线性表是由n个结点组成的有序数列，序列中的所有节点具有相同的数据类型。线性表是线性结构。它存在唯一的一个首结点，和唯一的一个尾结点。除了首节点以外，所有的结点都有且仅有一个直接前驱。除了尾结点以外，所有的结点都有且仅有一个直接后继。
线性表的结点
线性表的结点可以是单值元素，每个元素仅有一个数据项。如：

26个字母组成的字母表：(A, B, C, D, E, F,..., X, Y, Z)

线性表的结点也可以是多值元素，每个元素含有多个数据项。如：

某个部门的成员表：
{
('张三', '男', '188****2121'),
('小明', '男', '133****1234'),
('李四', '女', '155****8385'),
('小刘', '男', '136****4467')
}

线性表的存储方式有：顺序存储和链式存储。

顺序存储：结点按照逻辑顺序依次存储在一段连续的存储单元中。顺序存储方式逻辑结构和物理结构是一致的。
链式存储：结点存储在一组任意的存储单元中，这个存储单元可以连续也可以不连续。链式存储方式逻辑结构和物理结构不一定相同。

一、线性表的顺序存储

1、线性表的结构体设计

#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0
#define MAXSIZE 10//线性表长度的最大值

typedef int Status;//状态值
typedef int ElemType;//结点的数据类型，视实际情况而定。在此以int为例。

typedef struct {
    ElemType *data;//指向存放线性表数据的数组第一个元素的指针
    int length;
}SqList;

2. 线性表的初始化

Status InitSqList (SqList *L){
    //线性表的数据数组开辟MAXSIZE的内存空间
    L->data = malloc(sizeof(ElemType)*MAXSIZE);
    
    if (!L->data) return ERROR;
    L->length = 0;
    
    return OK;
}

3. 线性表中插入数据

在第place个位置(下标：place-1)插入元素e：
①. 从最后一个元素开始到第place个元素依次向后移动一位
②. 在第place个位置插入数据
③. 线性表长度加1

Status InsterSqList(SqList *L, ElemType e, int place) {
    
    if (L->length == MAXSIZE) {
        printf("线性表中没有空间了，不能进行插入操作！\n");
        return ERROR;
    }
    if (place > L->length+1 || place < 1) {
        printf("插入的位置不合法！\n");
        return ERROR;
    }
    
    if (place <= L->length) {
        //满足条件则表示不是插在线性表的最后一位
        //向后移动元素，把第place个位置空出来
        for (int i = L->length-1; i >= place-1; i--) {
            L->data[i+1] = L->data[I];
        }
    }
    
    //插入数据
    L->data[place-1] = e;
    //线性表长度加1
    L->length += 1;
    
    return OK;
}

时间复杂度：O(n)，时间复杂度主要耗费在结点的移动，当n比较大时，算法的效率较低。

4. 线性表中删除数据

删除线性表中的第place个元素：
①. 第place个元素之后的元素依次向前移动一位
②. 线性表长度减1

Status DeletElem(SqList *L, int place) {
    
    //位置是否合法
    if (place < 1 || place > L->length) {
        printf("删除的位置不存在！");
        return ERROR;
    }
    
    //第place个元素之后的元素依次向前移动一位
    for (int i = place; i < L->length; i++) {
        L->data[place-1] = L->data[place];
    }
    //线性表长度减1
    L->length--;
    
    return OK;
}

时间复杂度：O(n)，时间复杂度主要耗费在结点的移动，当n比较大时，算法的效率较低。

5. 线性表中查询数据

在线性表中查询元素e，返回元素e的位置，0表示没找到：

int querySqList(SqList L, ElemType e) {
    
    int place = 0;
    
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            place = I+1;
            break;
        }
    }
    
    return place;
}

时间复杂度：O(n)，时间复杂度主要耗费在循环和比较，当n比较大时，算法的效率较低。

二、线性表的链式存储-单向链表

链表的结点在内存中可能是不连续的，为了表示结点间的逻辑关系，在存储结点的同时还必须存储其直接后继结点的指针，所以这两部分构成了单向链表的结点。分别为数据域和指针域。
为了方便操作，通常在首元结点之前设置一个数据域不存储信息的头结点，头结点的指针域指向首元结点。
链表的尾结点指针域指向NULL，表示链表的结束。

单链表的结点

单链表示意图

1. 单向链表的结点结构

#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0

typedef int Status;//状态值
typedef int ElemType;//结点的数据类型，视实际情况而定。在此以int为例。

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

typedef struct Node *LinkList;

2. 单向链表的创建

创建一个空的单链表：

Status InitLinkList(LinkList *L) {
    //头结点
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return ERROR;
    (*L)->next = NULL;
    return OK;
}

创建一个非空的单链表可以使用头插法和尾插法两种方式，头插法是将插入的每个结点都作为链表的首元结点；尾插法是将插入的每个结点都作为链表的尾结点：

头插法
① 新结点的指针域指向头结点指针域指向的结点；
② 头结点的指针域指向新结点。

头插法

Status InitLinkList(LinkList *L) {
    //头结点
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return ERROR;
    (*L)->next = NULL;
    
    ElemType elem;
    LinkList temp;
    printf("请输入结点的值，输入0结束：\n");
    //头插法：每次插入的结点都作为首元结点
    while (1) {
        scanf("%d",&elem);
        if (elem == 0) break;
        
        temp = (LinkList)malloc(sizeof(Node));
        temp->data = elem;
        temp->next = (*L)->next;
        (*L)->next = temp;
    }
    return OK;
}

尾插法
① 新结点的指针域的值尾结点指针域的值；
② 原来的尾结点的指针域指向新结点。
③ 记录新的尾结点

尾插法

Status InitLinkList(LinkList *L) {
    //头结点
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return ERROR;
    (*L)->next = NULL;
    
    ElemType elem;
    LinkList temp,p = (*L);
    printf("请输入结点的值，输入0结束：\n");
    //尾插法：每次插入的结点都作为尾结点
    while (1) {
        scanf("%d",&elem);
        if (elem == 0) break;
        
        temp = (LinkList)malloc(sizeof(Node));
        temp->data = elem;
        temp->next = p->next;
        p->next = temp;
        p = temp;
    }
    return OK;
}

头插法创建的链表是倒序的，尾插法创建的链表是顺序的，实际操作中尾插法更加符合逻辑，所以使用的更多。

3. 单向链表的插入

在单链表的第place个位置插入新的数据元素e:

① 找到第place的位置的前一个元素temp；
② 创建新结点，并将新结点的指针域指向temp的下一个结点
③ temp的指针域指向新结点

Status InsertNode(LinkList *L, int place, ElemType e) {
    
    int I=1;
    LinkList p;
    LinkList temp = *L;
    
    //temp:第place个元素的前一个
    while (i<place && temp) {
        temp = temp->next;
        I++;
    }
    
    if (!temp || i > place) {
        return ERROR;
    }
    
    //创建要插入的新节点
    p = (LinkList)malloc(sizeof(Node));
    p->data = e;
    p->next = temp->next;
    
    temp->next = p;
    
    return OK;
}

4. 单向链表的删除

删除单链表第place位置的元素：

① 找到第place的位置的前一个元素temp；
② temp的指针域指向temp的下一个结点的指针域指向的结点；
③ 释放temp的内存空间

LinkList p;
    LinkList temp = (*L)->next;//第一个是头结点
    int i = 1;
    
    //temp:第place个元素的前一个
    while (i<place-1 && temp->next) {
        temp = temp->next;
        I++;
    }
    
    if (!(temp->next) || i>place-1) return ERROR;
    
    p = temp->next;
    
    temp->next = p->next;
    
    free(p);
    
    return OK;

二、线性表的链式存储-双向链表

双向链表是为了解决单向链表的单向性的缺陷而引入的，双向链表的结点在单向链表结点的基础上多了一个指向结点直接前驱的指针。同样的，为了方便操作，可以在链表的开头添加一个头结点。双向链表的结点如图：

双向链表的结点

带有头结点的双向链表

1. 双向链表的结点定义

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

2. 双向链表的创建

使用尾插法创建非空的双链表：

Status InitList(LinkList *L) {
    
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return ERROR;

    (*L)->next = NULL;
    (*L)->prior = NULL;
    (*L)->data = 0;
    
    //使用尾插法插入数据
    LinkList p = *L;
    ElemType num = 0;
    
    printf("请输入插入的数据，输入0结束:\n");
    
    while (1) {
        scanf("%d",&num);
        if (num == 0) break;
        
        LinkList temp = (LinkList)malloc(sizeof(Node));
        temp->data = num;
        temp->prior = NULL;
        temp->next = NULL;
        
        p->next = temp;
        temp->prior = p;
        
        p = p->next;
    }
    return OK;
}

3. 双向链表的插入

在place位置插入元素e：

① 创建新结点temp，并使它的前驱和后继都为NULL
② 找到place位置的前一个结点p，判断p是否为尾结点，是则将temp的前驱指向p，p的后继指向temp；不是则将temp的后继指向p的下一个结点，p的下一个结点的前驱指向temp，然后将temp的前驱指向p，p的后继指向temp。

Status InsertNode(LinkList *L, int place, ElemType e) {
    
    int i = 1;
    LinkList p = *L;
    LinkList temp ;
    
    temp = (LinkList)malloc(sizeof(Node));
    temp->data = e;
    temp->next = NULL;
    temp->prior = NULL;
    
    while (i < place && p) {
        p = p->next;
        I++;
    }
    
    if (!p || i > place) return ERROR;
    
    if (p->next == NULL) {//插入到最后位置
        p->next = temp;
        temp->prior = p;
    }else {
        temp->next = p->next;
        p->next->prior = temp;
        
        p->next = temp;
        temp->prior = p;
    }
    
    return OK;
}

4. 双向链表的删除

删除place位置的结点:

① 找到place位置的前一个结点temp，要删除的结点p是temp的后继，temp的后继置为p的后继；
指向p，p的后继指向temp；不是则将temp的后继指向p的下一个结点，p的下一个结点的前驱指向temp，然后将temp的前驱指向p，p的后继指向temp。
② p不是尾结点时，p的后继的前驱指向temp；
③ 回收p的内存。

Status DeletNode(LinkList *L, int place) {
    int i = 1;

    LinkList temp = (*L)->next;
    LinkList p;// 要删除的结点
    
    while (i < place-1 && temp->next) {
        temp = temp->next;
        I++;
    }
    
    if (!temp || i > place) return ERROR;
    
    p = temp->next;
    
    temp->next = p->next;
    
    if (p->next) {
        p->next->prior = temp;
    }
    
    free(p);
    
    return OK;
}

还有一种首尾相接的链表：循环链表

数据结构与算法之线性表