美文网首页数据结构与算法
记录数据结构与算法的学习之路 -----001.数据结构与算法初

记录数据结构与算法的学习之路 -----001.数据结构与算法初

作者: Jeffery_zc | 来源:发表于2020-04-01 16:26 被阅读0次

1.数据结构

1. 数据结构的基本术语

数据结构：指的数据对象中的数据元素之间的关系；
数据项: 一个数据元素由若干数据项组成；
数据元素: 组成数据的对象的基本单位;
数据对象: 性质相同的数据元素的集合(类似于数组);
数据: 程序的操作对象,用于描述客观事物，例如：二进制数据，整形，字符串。。都属于数据

数据，数据对象，数据元素以及数据项构之间存在的关系如下图

图1.png

比如说：公路上有公车，出租车，私家车。。。这些车辆的职能各不相同，我们可以把这些不同种类的车辆看成上不同的数据元素，它们之间的关系是并列关系，它们所组成的集合叫做数据对象。

2. 逻辑结构与物理结构

数据结构从视角上可以分为逻辑结构和物理结构

2.1逻辑结构

从逻辑关系上分析，数据结构可以分为集合结构、线性结构、树形结构以及图形结构。
1：集合结构：所有是数据元素都是平等的关系，没有先后顺序，如同一个动物园里各个动物之间的关系；
2：线性结构：数据与数据之间的关系是一对一的关系，比如数组、链表、字符串、栈、队列，其中队列和栈是特殊的线性结构，因为他们拥有特殊的读取方式，栈是现进后出，队列是先进先出；
3：树形结构：树形结构的关系是一对多，比如：红黑树，二叉树。。。
4：图形结构：图形结构的特点是多对多。

2.2物理结构

上述所说的数据结构只是说明了数据元素之间的逻辑关系，便于我们理解，但是这些数据不论在逻辑中再复杂，最终是会成为二进制数据被计算机保存在内存当中，于是就有了我们所说的物理结构。物理结构通常会分为顺序存储结构和链式存储结构。
1.顺序存储结构
所谓顺序存储结构，就是计算机在内存中开辟一段连续的内存，依次的存储进去。
2.链式存储结构
不需要提前开辟一条连续的存储空间，需要多大的内存空间，直接进行开辟就行了。
劣势：查询非常麻烦；
优势：插入内存非常简单。

2.算法初探

2.1 算法的定义

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每个指令表示一个或多个操作。
特点：
1. 有输入输出
2. 有穷性
3. 确定性
4. 可行性
设计要求：
1.正确性
2.可读性
3.健壮性
4.时间效率高和储存量低

2.2时间复杂度

2.2.1大O表示法

时间复杂度，又称"渐进式时间复杂度"，表示代码执行时间与数据规模之间的增长关系。大O表示法就是将代码的所有步骤转换为关于数据规模n的公式项，然后排除不会对问题的整体复杂度产生较大影响的低阶系数项和常数项。
规则：
1.用常数1取代运行事件中所有的常数；
2.在修改运行次数函数中，只保留最高阶项，例如：n^3+2n+2 ->n^3；
3.如果在最高阶存在且不等于1，则去掉这个项目相乘的常数，例如：7n^3+2n+2 ->n^3。
时间复杂度术语：
1：常数阶：

void testSum1(int n){
    int sum = 0;                //执行1次
    sum = (1+n)*n/2;            //执行1次
    printf("testSum1:%d\n",sum);//执行1次
}

1+1+1 =3,根据大O表示法的规则，所有常数都用1表示，所以时间复杂度是O(1)

2：线性阶：

void testSum3(int n){
    int i,sum = 0;               //执行1次
    for (i = 1; i <= n; i++) {   //执行n+1次
        sum += i;                //执行n次
    }
    printf("testSum3:%d\n",sum);  //执行1次
}

一共执行了1+(n+1)+n+1 = 3+2n次，跟据大O表示法，去掉相乘的常数，只保留最高阶，所以时间复杂度是 O(n)

3：平方阶：

void testSum4(int n){
    int sum = 0;
    for(int i = 0; i < n;i++)
        for (int j = i; j < n; j++) {
            sum += j;
        }
    printf("textSum4:%d",sum);
    
}
时间复杂度是O(n^2)

4：立方阶：

void testB(int n){
   int sum = 1;                         //执行1次
   for (int i = 0; i < n; i++) {        //执行n次
       for (int j = 0 ; j < n; j++) {   //执行n*n次
           for (int k = 0; k < n; k++) {//执行n*n*n次
               sum = sum * 2;          //执行n*n*n次
           }
       }
   }
}
时间复杂度是O(n^3)

5：nlog阶：

void testA(int n){
    int count = 1;         //执行1次
    //n = 10
    while (count < n) {
        count = count * 2;
    }
    
}

2的x次方等于n x = log2n  ->O(logn)

6：指数阶：O(2^n)或者O(n!) 除非是非常小的n,否则会造成噩梦般的时间消耗. 这是一种不切实际的算法时间复杂度. 一般不考虑!

大O表示法效率排序：
O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

2.3空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式 记做: S(n) = n(f(n)),其中,n为问题的规模,f(n)为语句句关于n所占存储空间的函数。 在考量算法的空间复杂度,主要考虑算法执行时所需要的辅助空间。

程序空间计算因素:

  1. 寄存本身的指令
  2. 常数
  3. 变量
  4. 输入
  5. 对数据进行操作的辅助空间

2.4 线性表

线性表是1对1对线性逻辑结构，对于⾮非空的线性表和线性结构,其特点如下：

  1. 存在唯⼀一的⼀一个被称作”第⼀一个”的数据元素;
  2. 存在唯⼀一的⼀一个被称作”最后⼀一个"的数据元素；
  3. 除了了第⼀一个之外,结构中的每个数据元素均有⼀一个前驱；
  4. 除了了最后⼀一个之外,结构中的每个数据元素都有⼀一个后继。

2.4.1线性顺序表

线性表的顺序存储不仅逻辑相邻，物理存储地址也相邻。下面我们通过代码来看看线性表的创建，删除，插入等操作。

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

/* ElemType类型根据实际情况而定，这里假设为int */
typedef int ElemType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;

/*线性结构使用顺序表的方式存储*/

//顺序表结构设计
typedef struct {
    ElemType *data;
    int length;
}Sqlist;

typedef struct Node * LinkList;


//2.1 初始化单链表线性表
Status InitList(LinkList *L){
    
    //产生头结点,并使用L指向此头结点
    *L = (LinkList)malloc(sizeof(Node));
    //存储空间分配失败
    if(*L == NULL) return ERROR;
    //将头结点的指针域置空
    (*L)->next = NULL;
    
    return OK;
}


//2.2 单链表插入
/*
 初始条件:顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果：在L中第i个位置之后插入新的数据元素e，L的长度加1;
 */
Status ListInsert(LinkList *L,int i,ElemType e){
 
    int j;
    LinkList p,s;
    p = *L;
    j = 1;
    
    //寻找第i-1个结点
    while (p && j<i) {
        p = p->next;
        ++j;
    }
    
    //第i个元素不存在
    if(!p || j>i) return ERROR;
    
    //生成新结点s
    s = (LinkList)malloc(sizeof(Node));
    //将e赋值给s的数值域
    s->data = e;
    //将p的后继结点赋值给s的后继
    s->next = p->next;
    //将s赋值给p的后继
    p->next = s;
    
    return OK;
}


//2.3 单链表取值
/*
 初始条件: 顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果：用e返回L中第i个数据元素的值
 */
Status GetElem(LinkList L,int i,ElemType *e){
    
    //j: 计数.
    int j;
    //声明结点p;
    LinkList p;
    
    //将结点p 指向链表L的第一个结点;
    p = L->next;
    //j计算=1;
    j = 1;
    
    
    //p不为空,且计算j不等于i,则循环继续
    while (p && j<i) {
        
        //p指向下一个结点
        p = p->next;
        ++j;
    }
    
    //如果p为空或者j>i,则返回error
    if(!p || j > i) return ERROR;
    
    //e = p所指的结点的data
    *e = p->data;
    return OK;
    
    
}

//2.4 单链表删除元素
/*
 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
 */

Status ListDelete(LinkList *L,int i,ElemType *e){
    
    int j;
    LinkList p,q;
    p = (*L)->next;
    j = 1;
    
    //查找第i-1个结点,p指向该结点
    while (p->next && j<(i-1)) {
        p = p->next;
        ++j;
    }
    
    //当i>n 或者 i<1 时,删除位置不合理
    if (!(p->next) || (j>i-1)) return  ERROR;
    
    //q指向要删除的结点
    q = p->next;
    //将q的后继赋值给p的后继
    p->next = q->next;
    //将q结点中的数据给e
    *e = q->data;
    //让系统回收此结点,释放内存;
    free(q);
    
    return OK;
}

/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(LinkList L)
{
    LinkList p=L->next;
    while(p)
    {
        printf("%d\n",p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList *L)
{
    LinkList p,q;
    p=(*L)->next;           /*  p指向第一个结点 */
    while(p)                /*  没到表尾 */
    {
        q=p->next;
        free(p);
        p=q;
    }
    (*L)->next=NULL;        /* 头结点指针域为空 */
    return OK;
}

//3.1 单链表前插入法
/* 随机产生n个元素值,建立带表头结点的单链线性表L(前插法)*/
void CreateListHead(LinkList *L, int n){
    
    LinkList p;
    
    //建立1个带头结点的单链表
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    //循环前插入随机数据
    for(int i = 0; i < n;i++)
    {
        //生成新结点
        p = (LinkList)malloc(sizeof(Node));
       
        //i赋值给新结点的data
        p->data = i;
        //p->next = 头结点的L->next
        p->next = (*L)->next;
        
        //将结点P插入到头结点之后;
        (*L)->next = p;
        
    }
}

//3.2 单链表后插入法
/* 随机产生n个元素值,建立带表头结点的单链线性表L(后插法)*/
void CreateListTail(LinkList *L, int n){
    
    LinkList p,r;
 
    //建立1个带头结点的单链表
    *L = (LinkList)malloc(sizeof(Node));
    //r指向尾部的结点
    r = *L;
    
    for (int i=0; i<n; i++) {
        
        //生成新结点
        p = (Node *)malloc(sizeof(Node));
        p->data = i;
        
        //将表尾终端结点的指针指向新结点
        r->next = p;
        //将当前的新结点定义为表尾终端结点
        r = p;
    }
    
    //将尾指针的next = null
    r->next = NULL;
    
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    Status iStatus;
    LinkList L1,L;
    struct Node *L2;
    ElemType e;
    
//    L1 =(LinkList) malloc(sizeof(Node));
//    L2 =(LinkList) malloc(sizeof(Node));
//
//    L1->data = 1;
//    L2->data = 2;
//    printf("L1.data=%d,L2.data=%d\n",L1->data,L2->data);
    
    //2.1 单链表初始化
    iStatus = InitList(&L);
    printf("L 是否初始化成功?(0:失败,1:成功) %d\n",iStatus);
    
    //2.2 单链表插入数据
    for(int j = 1;j<=10;j++)
    {
        iStatus = ListInsert(&L, 1, j);
    }
    printf("L 插入后\n");
    ListTraverse(L);
    
    //2.3 单链表获取元素
    GetElem(L,5,&e);
    printf("第5个元素的值为：%d\n",e);
    
    //2.4 删除第5个元素
    iStatus = ListDelete(&L, 5, &e);
    printf("删除第5个元素值为:%d\n",e);
    ListTraverse(L);
    
    //3.1 前插法整理创建链表L
    iStatus = ClearList(&L);
    CreateListHead(&L, 20);
    printf("整理创建L的元素(前插法):\n");
    ListTraverse(L);
    
    //3.2 后插法整理创建链表L
    iStatus = ClearList(&L);
    CreateListTail(&L, 20);
    printf("整理创建L的元素(后插法):\n");
    ListTraverse(L);
    
}

2.4.2线性单链表

2.4.2.1结点
对于链表来说，是由一个个结点组成的，每个结点分为数据域和指针域，线性表的链式存储最大的特点是不连续的，所以他们是通过指针域来链接的。 图2.png
2.4.2.2 单链表的逻辑状态
图3.png

通过上图可以看出，开始处有一个指针叫首指针，指向首元结点，且最后一个结点指向空(null)，这就是链表的特点。
当我们创建单链表的时候，我们会在首元结点前增加一个头结点，这个头结点是我们初始化链表对时候创建的，这样做的好处有一下2点：
1.便于首元结点处理，不需要对首元结点进行特殊处理；

2.便于空表和非空表的统一处理。 图4.png
2.4.2.2 单链表的插入与删除
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

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

typedef struct Node * LinkList;


//2.1 初始化单链表线性表
Status InitList(LinkList *L){
    
    //产生头结点,并使用L指向此头结点
    *L = (LinkList)malloc(sizeof(Node));
    //存储空间分配失败
    if(*L == NULL) return ERROR;
    //将头结点的指针域置空
    (*L)->next = NULL;
    
    return OK;
}
a. 插入

假设要在单链表的两个数据元素CC和Hank之间插⼊一个数据元素Cooci,已知p为其单链表存储结构中指向结点CC指针，如下图所示：

图5.png
首先我们要先找到插入之前的结点p，然后创建一个新的结点Cooci，然后对这个结点进行赋值，之后将cooci这个结点的指针指向hank结点，然后再断开cc结点指向hank结点的指针，最后将cc结点的指针指向cooci，这样，一个结点的插入就完成了。ps：不能先断开cc结点指向hank结点的指针，如果先断开了，hank结点将会丢失在链表中。 
//2.2 单链表插入
/*
 初始条件:顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果：在L中第i个位置之后插入新的数据元素e，L的长度加1;
 */
Status ListInsert(LinkList *L,int i,ElemType e){
 
    int j;
    LinkList p,s;
    p = *L;
    j = 1;
    
    //寻找第i-1个结点
    while (p && j<i) {
        p = p->next;
        ++j;
    }
    
    //第i个元素不存在
    if(!p || j>i) return ERROR;
    
    //生成新结点s
    s = (LinkList)malloc(sizeof(Node));
    //将e赋值给s的数值域
    s->data = e;
    //将p的后继结点赋值给s的后继
    s->next = p->next;
    //将s赋值给p的后继
    p->next = s;
    
    return OK;
}


//2.3 单链表取值
/*
 初始条件: 顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果：用e返回L中第i个数据元素的值
 */
Status GetElem(LinkList L,int i,ElemType *e){
    
    //j: 计数.
    int j;
    //声明结点p;
    LinkList p;
    
    //将结点p 指向链表L的第一个结点;
    p = L->next;
    //j计算=1;
    j = 1;
    
    
    //p不为空,且计算j不等于i,则循环继续
    while (p && j<i) {
        
        //p指向下一个结点
        p = p->next;
        ++j;
    }
    
    //如果p为空或者j>i,则返回error
    if(!p || j > i) return ERROR;
    
    //e = p所指的结点的data
    *e = p->data;
    return OK;
    
    
}
b. 删除
//2.4 单链表删除元素
要删除单链表中指定位置的元素,同插⼊入元素⼀一样; ⾸首先应该找到该位置的前驱结点; 如下图所示 在单链表中删除元素Hank时,应该⾸首先找到其前驱结点CC. 为了了在单链表中实现元素CC,Hank, Cooci 之间的逻辑关系的变化,仅需修改结点CC中的指针域即可。
假设p为指向结点CC的指针，如下图：
![图6.png](https://img.haomeiwen.com/i4801273/438f7c694dd9b247.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
下面，我们通过代码来进行操作：
/*
 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
 */

Status ListDelete(LinkList *L,int i,ElemType *e){
    
    int j;
    LinkList p,q;
    p = (*L)->next;
    j = 1;
    
    //查找第i-1个结点,p指向该结点
    while (p->next && j<(i-1)) {
        p = p->next;
        ++j;
    }
    
    //当i>n 或者 i<1 时,删除位置不合理
    if (!(p->next) || (j>i-1)) return  ERROR;
    
    //q指向要删除的结点
    q = p->next;
    //将q的后继赋值给p的后继
    p->next = q->next;
    //将q结点中的数据给e
    *e = q->data;
    //让系统回收此结点,释放内存;
    free(q);
    
    return OK;
}
2.4.2.3 单链表的前插法与后插法
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(LinkList L)
{
    LinkList p=L->next;
    while(p)
    {
        printf("%d\n",p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList *L)
{
    LinkList p,q;
    p=(*L)->next;           /*  p指向第一个结点 */
    while(p)                /*  没到表尾 */
    {
        q=p->next;
        free(p);
        p=q;
    }
    (*L)->next=NULL;        /* 头结点指针域为空 */
    return OK;
}
a. 前插法

所谓前插法，就是我们将每一个新创建的结点都插入在头结点之后，如下图


图7.png 
//3.1 单链表前插入法
/* 随机产生n个元素值,建立带表头结点的单链线性表L(前插法)*/
void CreateListHead(LinkList *L, int n){
    
    LinkList p;
    
    //建立1个带头结点的单链表
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    //循环前插入随机数据
    for(int i = 0; i < n;i++)
    {
        //生成新结点
        p = (LinkList)malloc(sizeof(Node));
       
        //i赋值给新结点的data
        p->data = i;
        //p->next = 头结点的L->next
        p->next = (*L)->next;
        
        //将结点P插入到头结点之后;
        (*L)->next = p;
        
    }
}
b. 后插法

所谓后插法，就是在最后一个结点后插入新的结点，ps：后插法插入的结点，指针最后一定要指向空，不然会报错哦 😊。

//3.2 单链表后插入法
/* 随机产生n个元素值,建立带表头结点的单链线性表L(后插法)*/
void CreateListTail(LinkList *L, int n){
    
    LinkList p,r;
 
    //建立1个带头结点的单链表
    *L = (LinkList)malloc(sizeof(Node));
    //r指向尾部的结点
    r = *L;
    
    for (int i=0; i<n; i++) {
        
        //生成新结点
        p = (Node *)malloc(sizeof(Node));
        p->data = i;
        
        //将表尾终端结点的指针指向新结点
        r->next = p;
        //将当前的新结点定义为表尾终端结点
        r = p;
    }
    
    //将尾指针的next = null
    r->next = NULL;
    
}

2.4.3 链表结构与顺序存储结构优缺点对⽐

存储分配⽅方式
• 顺序存储结构⽤用⽤用⼀一段连续的存储单元依次存储线性表的数据元素;
• 单链表采⽤用链式存储结构,⽤用⼀一组任意的存储单元存放线性表的元素;
时间性能

  • 查找
    •. 顺序存储 O(1)；
    •. 单链表O(n)；
  • 插入和删除
    • 存储结构需要平均移动一个表⻓一半的元素,时间O(n)；
    • 单链表查找某位置后的指针后,插入和删除为 O(1)；
  • 空间性能
    • 顺序存储结构需要预先分配存储空间,分太大,浪费空间;分⼩了,发生上溢出；
    • 单链表不需要分配存储空间,只要有就可以分配, 元素个数也不受限制；

相关文章

网友评论

    本文标题：记录数据结构与算法的学习之路 -----001.数据结构与算法初

    本文链接：https://www.haomeiwen.com/subject/keswuhtx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    数据结构与算法

    关于我们|服务条款|联系我们|记录数据结构与算法的学习之路 -----001.数据结构与算法初|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！