[数据结构与算法] 线性表详解（代码演示）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 线性表详解（代码演示） -> 正文阅读

[数据结构与算法]线性表详解（代码演示）

1.顺序表

顺序表是指用一段连续的地址，依次存放数据元素的线性数据结构，这种存储方式使得顺序表的物理结构与逻辑结构都是连续的。

q1：这和平时再函数中定义的数组有什么区别？

ans1：函数中的数组被存放在栈段中，而栈段有系统限制的大小【ulimit -s】。因此顺序表往往使用再堆段中操作管理动态数组的方式实现。

（1）管理结点

如果把数据结构比作仓库，数据元素比作货物，除了货物之外，还应该有货物的数量，货架的数量等信息。要体现这些信息，就需要“管理结点”。

eg：

? 顺序表中，管理结点内部一般存放：数据域地址(*data)、总容量(size)、当前数据量(len)

顺序表的基本实现代码：

#include<stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Vector{
    int *data; //数据域指针
    int total; //总容量
    int len; //当前容量
} Vector;

Vector *initVector(int total){
    //初始化管理结点
    Vector *v = (Vector *)malloc(sizeof(Vector));
    //初始化数据域
    v->data = (int *)malloc(sizeof(int) * total);
    v->len = 0; //当前容量为0
    v->total = total; //设置总容量
    return v;
}

//在data[idx] 处插入x
void insert(Vector *v, int idx, int val){
    if(!v) return ;
    if(idx > v->len || idx < 0) return ;
    if(v->len == v->total) return ; //满了
    //元素移动
    for(int i = v->len; i > idx; i--){
        v->data[i] = v->data[i - 1];
    }
    v->data[idx] = val; //真正的插入
    ++ v->len; //更新管理结点
}

void delete(Vector *v, int idx){
    if(!v) return ;
    if(idx >= v->len || idx < 0) return ;
    for(int i = idx; i < v->len; i++){
        v->data[i] = v->data[i + 1];
    }
    -- v->len;
}

int isEmpty(Vector *v){
    return !v || (v->len == 0);
}

void printVector(Vector *v){
    for(int i = 0; i < v->len; i++){
        printf("%d ", v->data[i]);
    }
    printf("\n----------------------\n");
}

int main(){
    Vector *v = initVector(100);

    for(int i = 0; i < 10; i++){
        insert(v, i, i);
    }
    printVector(v);
    insert(v, 3, 100);
    printVector(v);
    insert(v, 5, 200);
    printVector(v);
    delete(v, 10);
    printVector(v);


    return 0;
}

（2）顺序表的扩容

当进行插入时，顺序表满，就进行扩容。一般扩容规则：倍增（2*size）

int expend(Vector *v){
    int exTotal = v->total;
    int *temp;
    while(exTotal){
        //尝试重新申请空间
        temp = (int *) realloc (v->data, sizeof(int*) * (v->total + exTotal));
        if(temp) break; //申请成功
        exTotal >> 1; //不行就减半
    }
    if(!temp) return 0; //申请失败
    //维护管理结点
    v->data = temp;
    v->total += exTotal;
    return 1;
}

void insertWithExtend(Vector *v, int idx, int val){
    if(!v) return ;
    if(idx > v->len || idx < 0) return ;
    if(v->len == v->total) {
        if(!expend(v)) return ;//尝试扩容

    }
    //元素移动
    for(int i = v->len; i > idx; i--){
        v->data[i] = v->data[i - 1];
    }
    v->data[idx] = val; //真正的插入
    ++ v->len; //更新管理结点
}

2.链表

链表是一种物理结构不连续，但是可以依靠结点中的指针实现逻辑结构连续的先行数据结构。

构成链表的数据元素被称为“结点”，结点内部存放数据和指向下一个结点的指针，只有单一结点的指针的链表是单链表。

链表的管理结点一般仅需要存放头结点指针(*head)

如果需要频繁获取链表长度，管理节点中可以额外存放链表长度(len)

（1）头插法和尾插法：

#include<stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node{
    int val;
    struct Node *next;
} Node;

Node *initNode(int val){
    Node *node = (Node *) malloc (sizeof(Node));
    node->val = val;
    node->next = NULL;
    return node;
}

typedef struct List{
    Node *head;
    int len;
} List;

List *initList(){
    List *l = (List *) malloc (sizeof(List));
    l->head = NULL;
    l->len = 0;
    return l;
}

void insertToHead(List *list, int val){
    if(!list) return ;
    Node *node = initNode(val);
    node->next = list->head;
    list->head = node;
    ++ list->len;
}

void insertToTail(List *list, int val){
    if(!list) return ;
    Node *node = initNode(val);
    if(!list->head){ //如果链表为空
        list->head = node;
        ++list->len;
        return ;
    }
    Node *p = list->head;
    while(p->next){
        p = p->next;
    }
    p->next = node;
    ++ list->len;
}

void printList(List *list){
    Node *p = list->head;
    while(p){
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n----------------------\n");
}

int main(){
    List *l = initList();
    for(int i = 0; i < 3; i++){
        insertToHead(l, i);
    }
    for(int i = 3; i < 8; i++){
        insertToTail(l, i);
    }
    printList(l);
    for(int i = 8; i < 10; i++){
        insertToHead(l, i);
    }
    printList(l);
    
    return 0;
}

（2）在任意位置插入和删除：

#include<stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node{
    int val;
    struct Node *next;
} Node;

Node *initNode(int val){
    Node *node = (Node *) malloc (sizeof(Node));
    node->val = val;
    node->next = NULL;
    return node;
}

typedef struct List{
    Node *head;
    int len;
} List;

List *initList(){
    List *l = (List *) malloc (sizeof(List));
    l->head = NULL;
    l->len = 0;
    return l;
}

void insertToHead(List *list, int val){
    if(!list) return ;
    Node *node = initNode(val);
    node->next = list->head;
    list->head = node;
    ++ list->len;
}

void insertToTail(List *list, int val){
    if(!list) return ;
    Node *node = initNode(val);
    if(!list->head){ //如果链表为空
        list->head = node;
        ++list->len;
        return ;
    }
    Node *p = list->head;
    while(p->next){
        p = p->next;
    }
    p->next = node;
    ++ list->len;
}

void printList(List *list){
    Node *p = list->head;
    while(p){
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n----------------------\n");
}

//在编号为idx的位置插入值为val的点
void insert(List *list, int idx, int val){
    if(!list) return ;
    if(idx > list->len || idx < 0) return ;
    if(idx == 0) {
        insertToHead(list, val);
        return ;
    }
    Node *node = initNode(val);
    Node *p = list->head;
    for(int i = 0; i < idx - 1; i++){
        p = p->next;
    }
    node->next = p->next;
    p->next = node;
    ++ list->len;
}

void freeNode(Node *node){
    if(!node) return ;
    free(node);
    return ;
}

//删除编号为idx的结点
void delete(List *list, int idx){
    if(!list) return ;
    if(idx >= list->len || idx < 0) return ;
    if(idx == 0){
        list->head = list->head->next;
        -- list->len;
        return ;
    }
    Node *p = list->head;
    for(int i = 0; i < idx - 1; i++){
        p = p->next;
    }
    Node *node = p->next;
    p->next = p->next->next;
    freeNode(node);
    -- list->len;
    return ;
}

int main(){
    List *l = initList();
    for(int i = 0; i < 5; i++){
        insertToTail(l, i);
    }
    printList(l); //0 1 2 3 4

    insert(l, 3, 100);
    printList(l); // 0 1 2 100 3 4
    insert(l, 0, 200);
    printList(l); // 200 0 1 2 100 3 4

    delete(l, 0);
    printList(l); //0 1 2 100 3 4
    delete(l, 5);
    printList(l); //0 1 2 100 3
    
    return 0;
}

（3）虚头结点

在需要特殊处理头结点的时候，可以实现一个带有虚头结点的链表，在链表初始化或在某些操作执行时，将一个额外的结点放在头指针执行的地方。

虚头结点可以使得整个链表永远不空，永远有头，所以拥有虚头结点的链表在处理各类头结点操作时会更加便捷。

#include<stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node{
    int val;
    struct Node *next;
} Node;

Node *initNode(int val){
    Node *node = (Node *) malloc (sizeof(Node));
    node->val = val;
    node->next = NULL;
    return node;
}

typedef struct List{
    Node *head;
    int len;
} List;

List *initList(){
    List *l = (List *) malloc (sizeof(List));
    l->head = initNode(0);
    l->len = 0;
    return l;
}

void insertToHead(List *list, int val){
    if(!list) return ;
    Node *node = initNode(val);
    node->next = list->head->next;
    list->head->next = node;
    ++ list->len;
}

void insertToTail(List *list, int val){
    if(!list) return ;
    Node *node = initNode(val);
    Node *p = list->head;
    while(p->next){
        p = p->next;
    }
    p->next = node;
    ++ list->len;
}

void printList(List *list){
    Node *p = list->head->next;
    while(p){
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n----------------------\n");
}

//在编号为idx的位置插入值为val的点
void insert(List *list, int idx, int val){
    if(!list) return ;
    if(idx > list->len || idx < 0) return ;
    Node *node = initNode(val);
    Node *p = list->head->next;
    for(int i = 0; i < idx - 1; i++){
        p = p->next;
    }
    node->next = p->next;
    p->next = node;
    ++ list->len;
}

void freeNode(Node *node){
    if(!node) return ;
    free(node);
    return ;
}

//删除编号为idx的结点
void delete(List *list, int idx){
    if(!list) return ;
    if(idx >= list->len || idx < 0) return ;
    Node *p = list->head; //加上next循环就idx-1
    for(int i = 0; i < idx; i++){
        p = p->next;
    }
    Node *node = p->next;
    p->next = p->next->next;
    freeNode(node);
    -- list->len;
    return ;
}

int main(){
    List *l = initList();
    for(int i = 0; i < 5; i++){
        insertToTail(l, i);
    }
    printList(l); //0 1 2 3 4

    insert(l, 3, 100);
    printList(l); // 0 1 2 100 3 4
    insert(l, 0, 200);
    printList(l); // 200 0 1 2 100 3 4

    delete(l, 0);
    printList(l); //0 1 2 100 3 4
    delete(l, 5);
    printList(l); //0 1 2 100 3
    
    return 0;
}