数据结构与算法-线性数据结构

字数统计: 1.9k字   |   阅读时长≈ 7分

线性的数据结构

线性结构是指元素只有一个前趋和后继

线性的数据结构分为物理线性结构和逻辑线性结构

物理线性是元素在内存中的地址是连续的；逻辑线性在内存中的地址不一定是连续的，在逻辑上存在前趋和后继

常用的线性数据结构包括数组、链表、栈、队列

数组

数组是最常用的线性数据结构，一般使用时可以在内存中申请一块固定大小的空间用于存储各类型元素

优点：
支持随机存取，读写都是O(1)复杂度，只需要知道下标即可

缺点：
1.大小一般都是固定的，如果扩容则需要申请一块新的内存将原有数据迁移过去
2.插入和删除操作困难，

链表

前面说到数组的插入和删除效率不高，可以通过链表来解决这一问题

链表的基本结构

最简单的链表包括一个数据域和一个指针域，其中数据域用于存放数据，指针域用于存放下个节点的地址

代码表示如下：

1
2
3
4
5
struct Node
{
    int Data;
    struct Node* Next;
};

这种结构可以实现更高效的插入和删除操作，但作为代价，它不支持随机存取，变成一种顺序存取的结构

链表不止这一种形式，还有双向链表和循环链表

双向链表：

1
2
3
4
5
6
struct Node
{
    int Data;
    struct Node* Pre;
    struct Node* Last;
};

循环链表：只需将最后一个元素的后继指向第一个元素即可，如果时双向链表则还需将头节点的前趋指向最后一个元素

插入和删除操作

以简单链表为例

1
2
3
4
5
6
7
8
9
10
11
12
13
//删除操作

Node* Temp=DeleteNode;
Node* Pre=PreNode;
Pre->Next=Temp->Next;
delete Temp;


//插入操作

InsertNode->Next=ThisNode->Next;
ThisNode->Next=InsertNode;

栈

什么是栈

栈(stack),是一种先进后出(或后进先出)的结构，后进的元素为栈顶(top),最先进的为栈底

一个常用的例子是浏览器的网页：当我们浏览网页时我们可以通过一些操作进行回退到上一次浏览的内容

或者玩的玩具枪的弹夹也是一个栈，我们把子弹装入弹夹看作压栈，每次扣动扳机可以看作一次出栈

栈的主要功能包括进栈、出栈、获取栈顶元素

栈的实现方式有两种，分别是顺序栈和链栈

顺序栈的实现

1
2
3
4
5
struct stack
{
    int *Data;
    int top;
};

栈的进栈、出栈、获取栈顶元素实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//进栈  
void Push(stack* S,int Value)
{
    S->top++;
    Data[top]=Value;
}


//出栈
void Pop(stack *S)
{
    S->top--;
}


//获取栈顶元素  
int Top(stack* S)
{
    return S->Data[top]; 
}

链栈的实现

链栈的实现基础是链表，使用头插法，把访问限制在链表的第一个元素，就可以实现对栈的访问

1
2
3
4
5
6
7
struct ListStack
{
    int Data;
    struct ListStack* Next;
};

ListStack* S;

栈的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//入栈  
void Push(ListStack* S,int Value)
{
    ListStack* Temp=new ListStack;
    Temp->Data=Value;
    Temp->Next=S->Next;
    S->Next=Temp;
}


//出栈
void Pop(ListStack* S)
{
    ListStack* Temp=S;
    S=S->Next;
    delete Temp;
}

//获取栈顶元素  
int Top(ListStack* S)
{
    return S->Data;
}

注意：以上操作是假设均不为空的情况，实际实现时要进行判空操作

队列

什么是队列

队列是一种先进先出(后进后出)的数据结构，它只能在队尾添加元素，在队头弹出元素

一个常见的例子是排队(无论是去银行取钱或者在超市买东西都会排队)，当我们排队时总是会自觉地站到队尾

而非插队，当位于队首的人离开时我们会向前走一步直到我们走到队首接受相应的服务(弹出队列)

上面的对垒是一种单端队列，当然还有一种队列是双端队列，双端队列与单端队列的区别是双端队列的

队尾和队首都可以进行插入和弹出操作

队列的实现

队列有多种实现方式，我们可以使用循环数组来实现，通过声明front、rear指针来实现对队首和队尾的操作

当然也可以使用链表来实现单端队列和双端队列

单端队列

使用循环数组实现

1
2
3
4
5
6
7
#define MaxSize 20
struct queue
{
    int Data[MaxSize];
    int front=0;
    int rear=0;
};

队列功能的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//入队操作  
void Push(queue* Q,int Value)
{
    if(Q->rear+1%MaxSize == Q->front){
        return;
        进行判满操作
    }

    Q->Data[Q->rear]=Value;
    Q->rear=(Q->rear+1)%MaxSize;   完成循环操作

}


//出队操作
void Pop(queue* Q)
{
    if(Q->front==Q->rear){
        return;
        进行判满操作
    }
    
    Q->front=(Q->front+1)%MaxSize;  完成循环操作
}

因为可以对队首和队尾访问，可以进行一层封装以获取队首和队尾的元素

使用链表的实现

1
2
3
4
5
6
7
8
9
10
11
struct queue
{
    int Data;
    struct queue* Next;
};

struct ListQueue
{
    queue* front;
    queue* rear;
};

队列功能的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//入队
void Push(ListQueue* LQ,int Value)
{
    queue* Temp=new queue;
    Temp->Data=Value;
    LQ->rear->Next=Temp;
}


//出队
void Pop(ListQueue* LQ)
{
    queue* Temp=LQ->front;
    LQ->fornt=LQ->front->Next;
    delete Temp;
}


// 同样要进行判空操作

双端队列

使用循环数组方式实现

1
2
3
4
5
6
7
8
#define MaxSize 10
struct deque
{
    int Data[Maxsize];
    int front=0;
    int rear=0;
    int size=0;
};

双端队列功能实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//头插
void PushFront(deque* D,int Value)
{
    if(D->size==MaxSize){
        return;
        满了，无法插入
    }

    front--;
    front=(front+MaxSize)%MaxSize;
    D->Data[front]=Value;
    D->size++;
}

//头删
void PopFront(deque* D)
{
    if(D->size==0){
        return;
    }

    D->front++;
    D->front=(D->front+MaxSize)%MaxSize;
    D->size--;
}

//尾插
void PushBack(deque* D,int Value)
{
    if(D->size==MaxSize){
        return;
    }

    D->rear++;
    D->rear=(D->rear+MaxSize)%MaxSize;
    D->Data[D->rear]=Value;
    D->size++;
}

//尾删
void PopBack(deque* D)
{
    if(D->size==0){
        return;
    }

    D->rear--;
    D->rear=(D->rear+MaxSize)%MaxSize;
    D->size--;
}

使用链表来实现

1
2
3
4
5
6
7
8
9
10
11
12
struct ListDequeNode
{
    int Data;
    ListDequeNode* Pre;
    ListDequeNode* Next;
};

struct ListDeque
{
    ListDequeNode* front;
    ListDequeNode* rear;
};

实现链表队列的功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//头插
void PushFront(ListDeque* LD,int Value)
{
    ListDequeNode* Temp=new ListDequeNode;
    Temp->Data=Value;

    ListDequeNode* TempFront=LD->front;

    Temp->Next=LD->front;
    LD->front=TempFront;
}

//头删
void PopFront(ListDeque* LD)
{
    ListDequeNode* Temp=LD->front;
    LD->front=LD->front->Next;
    delete Temp;
}

//尾插
void PushBack(ListDeque* LD,int Value)
{
    ListDequeNode* Temp=new ListDequeNode;
    Temp->Data=Value;

    ListDequeNode* TempRear=LD->rear;
    LD->rear->Next=Temp;

    LD->rear=LD->rear->Next;
}

//尾删
void PopBack(ListDeque* LD)
{
    ListDequeNode* Temp=LD->rear;
    LD->rear=LD->rear->Pre;
    delete Temp;
}

这里双端队列在插入删除时需要同时设置Pre和Next和判空操作

总结

介绍了4种常见的线性表并简单实现了一些主要功能，在实际开发中需要对线性表的结构进行完善，

可以使用面向对象来设计数据结构以满足需求

在实际操作中还要注意数据的边界条件和对元素是否合法进行判断(例如判断是否为空指针，是否为脏数据等)

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true


个人简介:
大学生一枚，想要从事游戏开发,
希望能做出自己的游戏

主要涉及技术：
UE4、Unity2D、C++