数据结构与算法(一) - 霜冷的秘密基地

数据结构与算法(一)

程序设计 1 评

前言:本文是学习数据结构与算法的学习笔记,教材为《大话数据结构》

【STEP1】

1.解释

数据结构指的是“一组数据的存储结构”,算法指的是“操作数据的一组方法”。
数据结构是为算法服务的,算法是要作用再特定的数据结构上的。

2.常用算法和结构

  • 数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Tire树
  • 算法: 递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法

【STEP2】

1.线性表

线性表就是数据排成像一条线一样的结构.每个现行表上的数据最多只有前和后两个方向.常见的线性表结构:数组,链表、队列、栈等。

(1)并集程序
功能:将La与Lb集合进行并集操作,结果存储在La中

void unionL(List *La, list Lb)
{
    int La_len, Lb_len, i;
    
    ElemType e;
    La_len = ListLength(*La);
    Lb_len = ListLength(Lb);
    
    for(i=1; i<=Lb_len, i++){        //遍历Lb
        GetElem(Lb, i, &e);        //在Lb中寻找i并存在e里面
        if(!LocateElem(*La, e)){    //判断La中是否有e(Lb中的元素)
            ListInsert(La, ++La_len, e);    //La不存在Lb[i] => e则插入到线性表末尾
        }
    }
}

(2)存储结构
顺序存储:用一段地址连续的存储单元依次存储线性表的数据元素,例如[a1, a2, ..., ai-1, ai, ai+1, ..., an]

1)线性表顺序存储的结构代码:

#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
    ElemType data[MAXSIZE];
    int length;    //线性表当前长度
} SqList;

实际上就是对数组的封装,加上了当前长度变量。顺序存储结构封装需要三个属性:

  • 存储空间的起始位置[数组data的存储位置]
  • 线性表的最大存储容量[数组的最大长度:MAXSIZE]
  • 线性表的当前长度[length]

注意:数组的长度是存放在线性表的存储空间的总长度,初始化后一段不变,而线性表的当前长度是线性表中的元素个数,是会变化的。

2)地址计算方法:

LOC() //获取存储位置的函数

假设ElemType占用的是c个存储单元(字节),则线性表中第i+1个元素和第i个数据元素的存储位置关系为:

LOC(ai+1) =LOC(ai) + c

可以推算出对于第i个元素ai的存储位置可以用a1计算得出[存储时间复杂度为O(1),随机存储结构]:

LOC(ai) =LOC(a1) + (i-1)c

GetElem()操作实现代码[将线性表中第i个元素返回,即返回数组中第i-1下标的值即可]

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

typedef int Status;

Status GetElem(SqList L, int i, ElemType *e)
{
    if(L.length == 0 || i < 1 || i > L.length){
        return ERROR;
    }
    *e = L.data[i-1];
    
    return OK;
}

注意:线性表从1开始,自然计数,数组从0下标开始

ListInsert()插入元素实现代码:

Status ListInsert(SqList *L, int i, ElemType e)
{
    int k;
    
    if(L->length == MAXSIZE){    //顺序线性表已满
        return ERROR;
    }
    if(i < 1 || i > L->length+1){
        return ERROR;            //插入位置i不在范围内
    }
    if(i <= L->lenght){            //插入的位置不在表尾
        /* 将要插入的位置后面的元素向后移动一位 */
        for(k = L->lenght-1; k >= i-1; k--){
            L->data[k+1] = L->data[k];
        }
    }
    
    L->data[i-1] = e;
    L->length++;
    
    return OK;
}
Android Studio - 学习笔记(JetPack)
1 评论
    阿布Chrome 85Android
    2021年01月08日回复
    向往光明Chrome 93Windows 10
    2021年09月24日回复

    还没更新完吧,阿sir

0:00