数据结构-线性表 linked list

线性表

概念：

线性表是n个数据特性相同元素组成的有限序列，是最基本的也是最常用的一种线性结构（线性表、栈、队列、数组都是线性结构），同时也是其他数据结构的基础。

对于非空的线性表或线性结构，都有：

存在唯一一个被称为‘第一个’的数据元素
存在唯一一个被称为‘最后一个’的数据元素
除第一个外，结构中的每个数据元素均只有一个前驱
除最后一个外，结构中的每个数据元素均只有一个后继

两种存储方式

顺序存储

概念：用一组地址连续的存储单元依次存储线性表的数据元素，像这种存储结构的线性表成为顺序表。

特点：逻辑上相邻的数据元素，存储结构上也相邻。

只要确定好了顺序表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储是一种随机存取的存储结构，因为高级语言中的数组类型也是随机存取的特性，所以通常我们都使用数组来描述数据结构中的顺序存储结构，用动态分配的一维数组来表示线性表。

顺序表的C语言代码实现

#define MAXSIZE 10
typedef int ElementType;

typedef struct {
    ElementType data[MAXSIZE];
    int length;
}SeqList;

//初始化
SeqList * initSeqList() {
    SeqList *list;
    list = (SeqList *)malloc(sizeof(SeqList));
    list->length = 0;
    return list;
}

//插入
void insertSeqList(SeqList list,ElementType data,int i) {
    if (i > list.length || i < 1) {
        return;
    }
    for (int j = list.length; j>=i; j--) {
        list.data[j] = list.data[j-1];
    }
    list.data[i-1] = data;
    list.length++;
}

//删除
void deleteSeqList(SeqList list,int i) {
    if (i > list.length || i < 1) {
        return;
    }
    for (int j = i; j<list.length; j++) {
        list.data[j] = list.data[j-1];
    }
    list.length--;
}

//定位 找出表中相等于参数的最小下标值
int locationSeqList(SeqList list,ElementType x) {
    int i = 0;
    while (i<list.length && list.data[i] != x) {
        i++;
    }
    if (i<list.length) {
        return i+1;
    }
    return 0;
}

线性表的链式存储

定义：线性表的链式存储是指存储结构是链式的。常见的链式存储有单链表、循环链表和双向链表。

单链表：单链表是由一个数据域和指针域组成的一个节点集合。data部分称为数据域，用于存放线性表元素；next部分称为指针域，存放一个指针，该指针指向本结点所含数据元素的直接后继结点，所有结点通过指针链接成链表。

大多数情况下链表会有一个头节点head，head的next指针指向链表的第一个结点，称为首节点，最后一个结点称为尾结点，首尾之间的结点称为表结点；

一些基本运算：

结构体定义

typedef struct {
    int age;
    int score;
}DataType;

typedef struct node {
    DataType data;//数据域
    struct node *next;//指针域
}Node,*linkList;

Node head;//头结点

初始化

linkList initLinkList() {
    linkList head;
    head = malloc(sizeof(Node));
    head->next = NULL;
    return head;
}

求表长

int lengthLinkList(linkList head) {
    int count = 0;
    linkList first = head->next;
    while (first->next != NULL) {
        count++;
        first = first->next;
    }
    return count;
}

读表元素给定序号i 求表head第i个元素

Node * getLinkList(linkList head,int i) {
    Node *p;
    p = head->next;//指向首节点
    int k = 1;
    while (k < i && p != NULL) {
        k++;
        p = p->next;
    }
    if (k == i) {
        return p;
    } else {
        return NULL;
    }
}

定位给定元素求index

int locationLinkList(linkList head,DataType x) {
    Node *p = head->next;
    int k = 0;
    while (p != NULL && p->data.num != x.num) {
        k++;
        p = p->next;
    }
    if (p!=NULL) {
        return k+1;
    }
    return 0;
}

插入单链表的插入是将给定值为x的元素插入到head链表 i 序号之前

void insertLinkList(linkList head,DataType x,int i) {
    Node *insert,*q;
    if (i == 1) {
        q = head;
    } else {
        q = getLinkList(head, i-1);//找到直接前驱
    }
    if (q == NULL) {
        printf("位置不对");
    } else {
        insert = (Node *)malloc(sizeof(Node));
        insert->data = x;
        insert->next = q->next;
        q->next = insert;
    }
}

删除给定一个值，从链表中删除i序号的元素

void deleteLinklist(linkList head,int i) {
    //先获取被删除元素的直接前驱
    Node *p,*q;
    if (i == 1) {
        q = head;
    } else {
        q = getLinkList(head, i-1);//找到直接前驱
    }
    if (q != NULL && q->next != NULL) {
        p = q->next;
        q->next = p->next;
        free(p);//释放空间
    } else {
        printf("找不到要删除的节点");
    }
}

单链表的三种创建方式

方法一

通过插入算法来实现，依次增大插入位置i 使新的结点链入链表中时间复杂度为O(n^2)

linkList createLinkList(void) {
    linkList head;
    int i,x;
    head = initLinkList();
    i = 1;
    scanf("%d",&x);
    while (x != 0) {
        insertLinkList(head, x, i);
        i++;
        scanf("%d",&x);
    }
    return head;
}

方法二尾插法

方法一每次插入元素都要从首结点遍历到尾结点，然后插入元素，所以时间复杂度为O(n^2),可以使用一个指针标明尾结点的位置，这样每次插入元素就不用遍历整个表顾时间复杂度为O(n)

linkList createLinkList2() {
    linkList head;
    head = (Node *)malloc(sizeof(Node));
    Node *tail,*q;
    q = head;//头结点
    int x;
    scanf("%d",&x);
    while (x != 0) {
        tail = (Node *)malloc(sizeof(Node));
        tail->data = x;
        q->next = tail;
        q = tail;//指向尾结点
        scanf("%d",&x);
    }
    q->next = NULL;
    return head;
}

方法三头插法时间复杂度也为O(n)

linkList createLinkList3() {
    linkList head;
    head = (Node *)malloc(sizeof(Node));
    head->next = NULL;
    Node *p;
    int x;
    scanf("%d",&x);
    while (x != 0) {
        p = malloc(sizeof(Node));
        p->data = x;
        p->next = head->next;//新元素放到第一个，充当首结点
        head->next = p;
        scanf("%d",&x);
    }
    return head;
}

删除重复数据项

在线性表中，有可能有多个元素值相同；它们是重复结点，可以删除重复结点只保留index最小的结点

void deleteRepeatLinkList(linkList head) {
    Node *p,*d,*q;
    q = head->next;
    while (q != NULL) {
        p = q;
        while (p->next != NULL) {
            if (p->next->data == q->data) {
                d = p->next;//被删除结点
                p->next = d->next;
                free(d);
            } else {
                p = p->next;//指针后移
            }
        }
        q = q->next;//指针后移
    }
}

线性表的顺序实现、链接实现比较

顺序实现和链接实现都有各自的优缺点，下面就时间复杂度和空间复杂度展开讨论。

对于按位置查找，顺序表示随机访问，所以平均时间复杂度为O(1)，单链表需要对元素进行扫描，它的平均时间复杂度为O(n);
对于定位运算，基本操作是比较，需要扫描元素，顺序表和单链表的平均时间复杂度相同O(n);
对于插入和删除操作，在顺序表和单链表中都需要定位，在顺序表中，其基本操作是元素比较和结点的移动，平均时间复杂度为O(n)，在单链表中，由于需要定位，尽管不需要移动结点，平均时间复杂度同样是O(n);
单链表的每个结点包含数据域和指针域，指针域需要占用额外空间但不需要预分配空间；
顺序表需要预分配空间，如果预分配过大，造成空间浪费；若分配的小，将发生空间溢出；