美文网首页
数据结构与算法之基础篇

数据结构与算法之基础篇

作者: 原来是泽镜啊 | 来源:发表于2020-05-06 22:18 被阅读0次

    写在前面

    对于很对人而言，“算法”和“数据结构”给人的第一印象就是很难懂，对于算法小白的我来说，更是一脸问号，但是作为一个优秀的开发者，不会数据结构和算法，还算是优秀发开发者吗？那么什么是数据？什么是数据结构？什么是算法？一个编写一个好的算法呢？一个好的算法怎么测评呢？接下来，来分析一下。

    1.  相关概念

    1.1  数据结构基本术语

    数据：程序可以操作的对象，用于描述客观事物。

    数据元素：组成数据的对象的基本单位

    数据对象：性质相同的数据元素的集合(类似于数组)

    数据结构：指的数据对象中的数据元素之间的关系

    数据类型：一组性质相同值的集合以及定义在此集合的一些总称

    图形示例：

    作为一个开发者，有一个学习的氛围跟一个交流圈子特别重要，这是一个我的iOS交流群：413038000，不管你是小白还是大牛欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！

    推荐阅读：iOS开发——2020 最新 BAT面试题合集（持续更新中）

    代码示例：

    //声明一个结构体类型
struct Teacher{     //一种数据结构
    char *name;     //数据项--名字
    char *title;    //数据项--职称
    int  age;       //数据项--年龄
};

struct Teacher t1;     //数据元素;
struct Teacher tArray[10]; //数据对象;

复制代码

    1.2  逻辑结构和物理结构

    逻辑结构：描述的数据与数据的逻辑关系

    包括： 集合结构、线性结构（一对一的关系，比如字链表、数组、符串、栈、队列、字典等）、树形结构（一对多）、图形结构（多对多）

    物理结构：顺序存储结构、链式存储结构（不需要提前开辟连续的存储空间）

    1.3  数据结构和算法直接的关系

    [图片上传中...(image-985646-1588230717375-5)]

    <figcaption></figcaption>

    1.4  算法

    算法： 解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每个指令表示一个或多个操作。

    特性：有输入输出、有穷性、可行性、确定性

    算法设计要求：正确性、可读性、健壮性、时间效率高和储存量低

    2.  时间复杂度和空间复杂度

    大O表示法：

      1. 用常数1取代运行时间中所有常数 3->1 O(1)
      1. 在修改运行次数函数中，只保留最高阶项 n3+2n2+5 -> O(n^3)
      1. 如果在最高阶存在且不等于1，则去除这个项目相乘的常数 2n^3 -> n^3

    2.1 常见的时间复杂度

    [图片上传中...(image-8960bd-1588230717375-4)]

    <figcaption></figcaption>

    代码示例：

    /* 1\. 常数阶时间复杂度计算 O(1) */
//1+1+1 = 3 O(1)
void testSum1(int n){
    int sum = 0;                //执行1次
    sum = (1+n)*n/2;            //执行1次
    printf("testSum1:%d\n",sum);//执行1次
}

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

}
//x=x+1; 执行1次
void add(int x){
    x = x+1;
}

/*2.线性阶时间复杂度*/
//x=x+1; 执行n次 O(n)
void add2(int x,int n){
    for (int i = 0; i < n; i++) {
        x = x+1;
    }
}

//1+(n+1)+n+1 = 3+2n -> O(n)
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次
}

/*3.对数阶*/
/*2的x次方等于n x = log2n  ->O(logn)*/
void testA(int n){
    int count = 1;         //执行1次
    //n = 10
    while (count < n) {
        count = count * 2;
    }

}

/*4.平方阶*/
//x=x+1; 执行n*n次 ->O(n^2)
void add3(int x,int n){
    for (int i = 0; i< n; i++) {
        for (int j = 0; j < n ; j++) {
            x=x+1;
        }
    }
}

//n+(n-1)+(n-2)+...+1 = n(n-1)/2 = n^2/2 + n/2 = O(n^2)
//sn = n(a1+an)/2
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);

}

//1+(n+1)+n(n+1)+n^2+n^2 = 2+3n^2+2n -> O(n^2)
void testSum5(int n){
    int i,j,x=0,sum = 0;           //执行1次
    for (i = 1; i <= n; i++) {     //执行n+1次
        for (j = 1; j <= n; j++) { //执行n(n+1)
            x++;                   //执行n*n次
            sum = sum + x;         //执行n*n次
        }
    }
    printf("testSum5:%d\n",sum);
}

/*5.立方阶*/
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次
            }
        }
    }
}
复制代码

    2.2 空间复杂度

    在考量算法的空间复杂度，主要考虑算法执行时所需要的辅助空间。

        // 数组逆序,将一维数组a中的n个数逆序存放在原数组中.
    int n = 5;
    int a[10] = {1,2,3,4,5,6,7,8,9,10};

    //算法实现(1)  O(1)
    int temp;
    for(int i = 0; i < n/2 ; i++){
        temp = a[i];
        a[i] = a[n-i-1];
        a[n-i-1] = temp;
    }

    for(int i = 0;i < 10;i++)
    {
        printf("%d\n",a[i]);

    }

    //算法实现(2)  O(n)
    int b[10] = {0};
    for(int i = 0; i < n;i++){
        b[i] = a[n-i-1];
    }
    for(int i = 0; i < n; i++){
        a[i] = b[i];
    }
    for(int i = 0;i < 10;i++)
    {
        printf("%d\n",a[i]);

    }
复制代码

    3. 线性表

    非空的线性表和线性结构特点：

    • 存在唯一的一个被称作“第一个”的数据元素
    • 存在唯一的一个被称为“最后一个”的数据元素
    • 除了第一个之外，结构中的每个数据远程均有一个前驱
    • 除了最后一个之外，结构中的每个数据远程均有一个后继

    3.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;

复制代码

    顺序表初始化:

    Status InitList(Sqlist *L){
    //为顺序表分配一个大小为MAXSIZE 的数组空间
    L->data =  malloc(sizeof(ElemType) * MAXSIZE);
    //存储分配失败退出
    if(!L->data) exit(ERROR);
    //空表长度为0
    L->length = 0;
    return OK;
}
复制代码

    顺序表的插入:

     初始条件：顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
 */
Status ListInsert(Sqlist *L,int i,ElemType e){

    //i值不合法判断
    if((i<1) || (i>L->length+1)) return ERROR;
    //存储空间已满
    if(L->length == MAXSIZE) return ERROR;

    //插入数据不在表尾,则先移动出空余位置
    if(i <= L->length){
        for(int j = L->length-1; j>=i-1;j--){

            //插入位置以及之后的位置后移动1位
            L->data[j+1] = L->data[j];
        }
    }

    //将新元素e 放入第i个位置上
    L->data[i-1] = e;
    //长度+1;
    ++L->length;

    return OK;

}
复制代码

    顺序表的取值

    //顺序表的取值
Status GetElem(Sqlist L,int i, ElemType *e){
    //判断i值是否合理, 若不合理,返回ERROR
    if(i<1 || i > L.length) return  ERROR;
    //data[i-1]单元存储第i个数据元素.
    *e = L.data[i-1];

    return OK;
}
复制代码

    顺序表删除

    
/*
 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 操作结果: 删除L的第i个数据元素,L的长度减1
 */
Status ListDelete(Sqlist *L,int i){

    //线性表为空
    if(L->length == 0) return ERROR;

    //i值不合法判断
    if((i<1) || (i>L->length+1)) return ERROR;

    for(int j = i; j < L->length;j++){
        //被删除元素之后的元素向前移动
        L->data[j-1] = L->data[j];
    }
    //表长度-1;
    L->length --;

    return OK;

}
复制代码

    清空顺序表

    /* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(Sqlist *L)
{
    L->length=0;
    return OK;
}
复制代码

    判断顺序表清空

    /* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(Sqlist L)
{
    if(L.length==0)
        return TRUE;
    else
        return FALSE;
}
复制代码

    获取顺序表长度

    // 获取ListEmpty元素个数
int ListLength(Sqlist L)
{
    return L.length;
}
复制代码

    顺序输出List

    /* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status TraverseList(Sqlist L)
{
    int i;
    for(i=0;i<L.length;i++)
        printf("%d\n",L.data[i]);
    printf("\n");
    return OK;
}
复制代码

    顺序表查找元素并返回位置

    /* 初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int LocateElem(Sqlist L,ElemType e)
{
    int i;
    if (L.length==0) return 0;

    for(i=0;i<L.length;i++)
    {
        if (L.data[i]==e)
            break;
    }

    if(i>=L.length) return 0;
    return i+1;
}
复制代码

    3.2  线性表链式存储（单链表）

    1. 单链表节点示意图

    [图片上传失败...(image-b9e99b-1588230717374)]

    <figcaption></figcaption>

    1. 单链表逻辑状态示意图[图片上传中...(image-ed6e96-1588230717369-1)]
    <figcaption></figcaption>
    1. 增加头节点的单链表逻辑状态示意图[图片上传中...(image-a13dd9-1588230717369-0)]
    <figcaption></figcaption>

增加头节点的好处：便于首元节点处理，便于空表和非空表的统一处理， 头结点的数据域可以存储链表的长度等一些辅助信息

    4.代码演示

    // 相关定义
#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;
复制代码

    初始化单链表线性表

    Status InitList(LinkList *L){

    //产生头结点,并使用L指向此头结点
    *L = (LinkList)malloc(sizeof(Node));
    //存储空间分配失败
    if(*L == NULL) return ERROR;
    //将头结点的指针域置空
    (*L)->next = NULL;

    return OK;
}

Status iStatus;
LinkList L1,L;
iStatus = InitList(&L);
printf("L 是否初始化成功?(0:失败,1:成功) %d\n",iStatus);
复制代码

    单链表遍历打印

    /* 初始条件：顺序线性表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已存在,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;
}

//调用
Status iStatus;
LinkList L1,L;

// 单链表插入数据
for(int j = 1;j<=10;j++)
{
    iStatus = ListInsert(&L, 1, j);
}
printf("L 插入后\n");
复制代码

    单链表删除元素

    删除示意图

    [图片上传失败...(image-b7806f-1588230717373)]

    <figcaption></figcaption>

    
/*
 初始条件：顺序线性表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已存在,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;

}
复制代码

    置空

    /* 初始条件：链性表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;
}
复制代码

    5 头插法 & 尾插法

    • 头插法

      创建新结点，赋值，新节点next指向头结点的next，头结点的next指向新节点

      代码示例：

    /* 随机产生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;

    }
}
// 结果是倒序
复制代码

    • 尾插法：

      创建新结点，赋值，表终端结点的next指向新结点，新节点定义为表终端结点，最后将尾指针的next = NULL

      代码示例：

    /* 随机产生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;

}

    作者：亮亮不想说话
    来源：掘金

    相关文章

      网友评论

          本文标题：数据结构与算法之基础篇

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

          延伸阅读

          深度阅读

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

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|数据结构与算法之基础篇|投稿指南|网站地图|RSS订阅|排版工具|手机版

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

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

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

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

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