0%

数据结构随笔2📝

内容来源凯哥的数据结构课以及ppt。

数据结构导论

数据结构的定义

  • 数据:数据就是数值,也就是我们通过观察、实验或计算得出的结果。数据有很多种,最简单的就是数字。数据也可以是文字、图像、声音等。数据可以用于科学研究、设计、查证等。
  • 数据结构:数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
  • 数据结构 = 数据 + 关系

线性结构与非线性结构

  • 线性结构:线性表、队列、栈、串、数组等。
  • 非线性结构:树、表、图,以及混合结构。
  • 线性结构对应:结构更简单,功能更基础,维护更简单。
  • 非线性结构对应:结构更复杂,功能更强到,维护更困难。

List 线性表

结构特点

  • 全序关系,每一个元素都具有唯一的前驱和后继

  • 严格同构,任何两个组成部分之间具有相同结构

映射

连续映射

  • 连续映射:所有元素依据此许映射为连续而完整的物s理空间,称为顺序表

  • 优势:借助物理空间的连续性确保全序关系,管理简单,访问速度快。

  • 劣势:连续空间难以预先准确规划,造成浪费或者无法扩展。

  • 一个好的习惯:初始化.

    动态创建字符数组:

    1
    char *myBuffer=(char*)malloc(0x1f)

离散映射

  • 离散映射:各个元素映射到离散的物理空间并通过结构信息维护全序关系,称为链表

  • 优势:不依赖物理空间的连续性,分散存储,充分利用存储空间,具有良好可扩展性。

  • 劣势:需要额外信息维护结构,逻辑较为复杂,动态分配内存造成额外时间消耗。

线性表:

实现在线性表中插入元素:

  • 通常的写法:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    Bool insert(struct Student value , int index) //index从1开始
    {
    int pos;
    if (index> g_studentListMgr->count+1 || g_studentListMgr->count == MAX_List_length) return FALSE;
    for(pos = g_studentListMgr->count-1;pos>=index-1;pos--)
    {
    g_studentListMgr.students[pos+1] = g_studentListMgr.students[pos];
    }
    g_studentListMgr.students[index-1] = value;
    g_studentListMgr->count+=1
    return TRUE;
    }
  • Insert的实现分析:

    • 最好情况:插入的位置在线性表尾部,时间复杂度为O(1)
    • 最差情况:插入的位置在线性表头部,时间复杂度为O(n)
    • 平均情况:各个位置都是等概率插入,时间复杂度为O(n/2)
  • 一种高效的在线性表中插入元素的方法:memmove函数

    1
    void *memmove( void* dest, const void* src, size_tcount );

    由src所指内存区域复制count个字节到dest所指内存区域。

    src和dest所指内存区域可以重叠,但复制后dest内容会被更改。函数返回指向dest的指针。

    1
    2
    memmove(g_studentListMgr.students+index , g_studentListMgr.students+index-1 , g_studentListMgr->count - index);
    g_studentListMgr.students[index-1] = value;

remove的实现方法同理:

  • 使用memmove函数

    1
    2
    memmove(g_studentListMgr.students+index-1 , g_studentListMgr.students+index , g_studentListMgr->count - index);
    g_studentListMgr.students[count] = 0;

线性表总结:

  • 存储空间静态分配,难以动态扩充
  • 数据插入需要进行数据移动,代价O(n)较高
  • 数据删除需要进行数据移动,代价O(n)较高
  • 数据查找需要进行全表遍历,代价O(n)较高
  • 按位置(下标)可直接获取,代价O(1)极低

链表:

  • 一个好的习惯:初始化,

    创建链表:

    1
    2
    3
    4
    5
    6
    7
    struct UniDirectStudentList g_studentListMgr;
    Boolean Initialize()
    {
    g_studentListMgr.head = NULL;
    g_studentListMgr.count = 0;
    return TRUE;
    }
  • 插入和删除部分比较简单,不再赘述。

  • get和locate也比较简单,同样不再赘述。

  • 链表的合并:

    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
    Void union(struct UniDirectStudentList* list1,struct UniDirectStudentList* list2) 
    {
    struct Student *tmpPtr , *tmpNode1, *tmpNode2 = list2->head;
    while(tmpNode2!=NULL)
    {
    tmpNode1 = list1->head;
    while(tmpNode1!=NULL)
    {
    if(!strcmp(tmpNode1->id , tmpNode2->id))
    {
    tmpPtr = tmpNode2;
    tmpNode2 = tmpNode2->nextAddr;
    free(tmpPtr);
    break;
    }
    else { tmpNode1 = tmpNode1->nextAddr; }
    }
    if(tmpNode1 == NULL) //若链表一中没有该元素,则将该元素添加到链表一头部。
    {
    tmpPtr = tmpNode2;
    tmpNode2 = tmpNode2->nextAddr;
    tmpPtr->nextAddr = list1->head;
    list1->head = tmpPtr;
    }
    }
    }
  • 循环链表的应用:CPU进程调度。

Stack栈

栈的定义

栈(stack)在计算机科学中是限定仅在表尾进行插入或删除操作的线性表。栈是一种数据结构,它按照后进先出(LIFO)的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据。栈就是一种类似桶堆积物品的数据结构,进行删除和插入的一端称栈顶,另一端称栈底。插入一般称为压栈(push),删除则称为弹栈(pop)。 栈也称为后进先出表。

特殊之处

栈的特殊之处体现在元素的添加(push)和删除(pop)

栈的层次化架构

通用线性结构:insert, get, remove

栈结构:push, pop

栈的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
extern struct SeqStudentListByArray* g_studentListMgr; //假设顺序表已经完成初始化
Boolean push(struct Student value)
{
return insert(value , g_studentListMgr->count+1);
}

Boolean pop(struct Student& value)
{
if(!get(g_studentListMgr->count , value)) {
return FALSE;
}else{
return remove(g_studentListMgr->count);
}
}

后记

由于期末考试的缘故,很多知识比如后面的树和图论在梳理的同时没办法认真的把笔记整理出来了,实在是有点遗憾。