数据结构学习笔记1---线性表--数组

数据结构学习笔记1---线性表--数组

数据结构思维导图

mark

一些零散的概念

数据结构相关

  • 我们把数据结构分为逻辑结构 和物理结构
  • 逻辑结构：是指数据对象中数据元素之间的相互关系。
  • 物理结构：是指数据的逻辑结构在计算机中的存储形式。
  • 四大逻辑结构：
    • 集合结构：集合结构中的数据元素除了同属于一个集合外没有其他的相互关系。
    • 线性结构：线性结构中的数据元素之间是一对一的关系。
    • 树形结构：树形结构中的元素之间存在一种一对多的层次关系。
    • 图形结构：图形结构的元素之间是多对多的关系。
  • 数据元素的存储形式：
    • 顺序存储：把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
    • 链式存储：把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不联系的。

算法相关

算法的概念和性质略过

  • 算法的复杂度

    • 时间复杂度（常用）
    • 空间复杂度
    例子 时间复杂度 术语
    5201314 O(1) 常数阶
    3n+4 O(n) 线性阶
    3n²+4n+5 O(n²) 平方阶
    3log2n+4 O(logn) 对数阶
    2n+3nlog2n+14 O(nlogn) nlogn阶
    n3+2n2+4n+6 O(n3) 立方阶
    2n O(2n) 指数阶
    • 常见的时间复杂度所耗费的时间从小到大依次是：

    　　　　　　　　O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < (nn)

  • 复杂度分析法则

    1）单段代码看高频：比如循环。
    2）多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
    3）嵌套代码求乘积：比如递归、多重循环等
    4）多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。

  • 时间复杂度分析

    只关注循环执行次数最多的一段代码
    加法法则：总复杂度等于量级最大的那段代码的复杂度
    乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

  • 几个常见例子

    线性阶

int i, n = 100, sum = 0;
for(i = 0; i<n; i++) {
    sum = sum + i;
}

上面这段代码的循环复杂度为O(n)，因为循环体中的代码需要执行n次

平方阶

int i,j,n = 100;
for(i = 0; i < n; i++) {
    for(j = 0; j < n; j++) {
        printf("aaaaaaaaaaaa
");
    }
}

上面这段代码的时间复杂度为O(n²)

int i,j,n = 100;
for(i = 0; i < n; i++) {
    for(j = i; j < n; j++) {
        pringtf("aaaaaaaaaaaaaa
");
    }
}

分析，由于当i=0时，内循环执行了n次，当i=1时，内循环则执行n-1次。。。。。。当i=n-1时，内循环执行1次，所以总的执行次数应该是n+(n-1)+(n-2)+...+1=n(n+1)/2用上面的简化方法来简化½n²+½n，这个式子中没有常数项不用考虑第一条，根据第二条只保留最高项，去掉½n这一项，根据第三条去掉与最高项相乘的常数½，最终得到O(n²)

对数阶

int i = 1, n = 100;
while(i < n) {
    i = i*2;
}

由于每次i2之后就距离n更近一步，假设有x个2相乘后大于或等于n，则会退出循环。于是由2^x=n

得到x=log2n，所以这个循环的时间复杂度为O(logn)。

ADT（抽象数据结构）

抽象数据类型的定义格式如下：

ADT抽象数据类型名{

    数据对象：（数据对象的定义〉
    数据关系：（数据关系的定义〉
    基本操作：（基本操作的定义〉
    
}ADT抽象数据类型名

基本操作的定义格式为：

​ 基本操作名（参数表）

​ 初始条件：（初始条件描述〉

​ 操作结果：（操作结果描述〉

基本操作有两种参数： 赋值参数只为操作提供输入值；引用参数以"&"打头，除可提供输

入值外，还将返回操作结果。

线性表之数组

mark

什么是线性表

对非空的线性表或线性结构， 其特点是：

  1. 存在唯一的一个被称作 “第一个＂ 的数据元素；
  2. 存在唯一的一个被称作 “最后一个＂ 的数据元素；
  3. 除第一个之外， 结构中的每个数据元素均只有一个前驱；
  4. 除最后一个之外，结构中的每个数据元素均只有一个后继。

线性表的抽象数据类型

ADT List{ 
    数据对象： D={ai|ai E ElemSet, i=l, 2, …n， n>=0} 
    数据关系： R=(<ai-1,ai> ai-1,aiE D, i=2, …, n} 
    基本操作：
    InitList (&L) 
        操作结果：构造一个空的线性表L。

    DestroyList(&L) 
        初始条件：线性表L已存在。
        操作结果：销毁线性表L。
    
    ClearList (&L) 
        初始条件：线性表L已存在。
        操作结果：将L重置为空表。
        
    ListEmpty(L)
        初始条件：线性表L已存在。
        操作结果：若L为空表， 则返回true, 否则返回false。
        
    ListLength(L) 
        初始条件：线性表L已存在。
        操作结果：返回L中数据元素个数。
        
    GetElem(L,i,&e) 
        初始条件：线性表L巳存在
        操作结果：用e返回L中第i个数据元素的值。
        
    LocateElem(L,e) 
        初始条件：线性表L已存在。
        操作结果：返回L中第1个 值与e相同的元素在 L中的位置 。若这样的数据元素不存在 ， 则返回值为0。
        
    PriorElem(r,,cur_e,&pre_e) 
        初始条件：线性表L已存在。
        操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回其前驱，否则操作失败，pre_e无定义。
    NextElem(L,cur_e,&next_e) 
        初始条件：线性表L已存在。
        操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败，next_e无定义。
        
    Listinsert(&L,i,e) 
        初始条件：线性表L已存在，且1:,s;i:os;ListLength (L) +l。
        操作结果：在 L中第1个位置之前插入新的数据元素 e, L的长度加1。
        
    ListDelete(&L,i) 
        初始条件：线性表L已存在且非空 ，且l:os;i:os;ListLength(L)。
        操作结果：删除L的第1个数据元素，L的长度减1。
        
    TraverseList(L) 
        初始条件：线性表L已存在。
        操作结果：对线性表L进行遍历，在遍历过程中对 L的每个结点访问一次。
        
) ADT List

顺序表

//－－－－－ 顺序表的存储结构－－－－－ //

#define MAXSIZE 100 //顺序表可能达到的最大长度
typedef struct {
     ElemType  *elem           //声明了一个名为elem的长度不确定的数组，也叫“动态数组”,也可以声明为                                //data[MAXSIZE];   
	int  Length；      		 //当前长度    
}SqList；                      //顺序表的结构类型为SqList

几种典型算法

初始化

算法步骤:：

  1. 为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址。
  2. 将表的当前长度设为0。

算法描述:

Status InitList(SqList &L){
    //构造一个空的顺序表
    L.elem=(ElemType *)malloc(MAXSIZE*sizeof(ElemType));  //为顺序表分配空间,也可以用new
    if (!L.elem) exit(OVERFLOW);                          //分配空间失败，退出
    L.Length=0;                                           //初始化长度为0
    return OK;
}

取值

算法步骤 ：

  1. 判断指定的位置序号 i 值是否合理 (I<=i<=L.length), 若不合理，则返回ERROR。
  2. 若 i 值合理，则将第 i 个数据元素 L.elem[i-1]赋给参数 e, 通过 e返回第 1 个数据元素的传值。

算法描述:

Status GetElem(SqList L,int i,ElemType &e){
    if (i<1||i>L.Length) return ERROR；   //判断数据不合理
     e=L.elem[i-1];
    return OK;  
}

查找：

算法步骤 ：

  1. 从第一个元素起，依次和 e相比较，若找到与 e相等的元素 L.elem[i], 则查找成功，返回该元素的位置 i+l。

  2. 若查遍整个顺序表都没有找到，则查找失败， 返回0。

算法描述:

int  LocateELem(SqList L,ElemType e){
    //在顺序表1中查找值为e的数据元素， 返回其序号
    for (i=0;i<L.Length;i++){
        if (L.elem[i]==e)  return i+1；       //查找成功
    }
    return 0；                                //查找失败
}

插入

算法步骤 ：

  1. 先判断插入位置是否合理（1<=i<=n+1）
  2. 判断顺序表的存储空间是否已满，;
  3. 若满见肤返回 ERROR。
  4. 将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置(i =n+l 时无需移动）。
  5. 将要插入的新元素e放入第i个位置。
  6. 表长加1。

算法描述:

Status ListInit(SqList &L,int i,ElemType e){
    if (i<1||i>L.Length+1)  return ERROR;     //插入位置不合理
    if (L.Length==MaixSize)  return ERROR;   //顺序表已满
    for (j=L.Length-1;j>=i-1;j--){
        L.elem[j+1]= L.elem[j];               //从后向前依次后移
	}
    L.elem[i-1]=e                             //插入新元素
    L.Length++;								//长度加1
    return OK;   
}

删除

算法步骤 ：

  1. 先检查删除的位置是否合理（1<=i<=n）
  2. 将第i+1个至第n个的元素依次向前移动一个位置 (i = n时无需移动）。
  3. 表长减 1。

算法描述:

Status ListDelete(SqList &L,int i){
    if (i<1||i>L.Length)    return ERROR;         //插入位置不合理
    for (j=i;j<=L.Length-1;j++){
        L.elem[j-1]=L.elme[j];
    }
    --L.Length;
    return OK;  
}

c语言实现

#include <stdio.h>
#include <stdlib.h>
#define Size 5
typedef struct Table{
    int * head;
    int length;
    int size;
}table;

//初始化顺序表
table initTable(){
    table t;
    t.head=(int*)malloc(Size*sizeof(int));
    if (!t.head)
    {
        printf("初始化失败");
        exit(0);
    }
    t.length=0;
    t.size=Size;
    return t;
}

//添加元素
table addTable(table t,int elem,int add)
{
    if (add>t.length+1||add<1) {
        printf("插入位置有问题");
        return t;
    }
    if (t.length>=t.size) {
        t.head=(int *)realloc(t.head, (t.size+1)*sizeof(int));
        if (!t.head) {
            printf("存储分配失败");
        }
        t.size+=1;
    }
    for (int i=t.length-1; i>=add-1; i--) {
        t.head[i+1]=t.head[i];
    }
    t.head[add-1]=elem;
    t.length++;
    return t;
}

//删除元素
table delTable(table t,int add){
    if (add>t.length || add<1) {
        printf("被删除元素的位置有误");
        exit(0);
    }
    for (int i=add; i<t.length; i++) {
        t.head[i-1]=t.head[i];
    }
    t.length--;
    return t;
}

//查找元素
int selectTable(table t,int elem){
    for (int i=0; i<t.length; i++) {
        if (t.head[i]==elem) {
            return i+1;
        }
    }
    return -1;
}

//修改元素
table amendTable(table t,int elem,int newElem){
    int add=selectTable(t, elem);
    t.head[add-1]=newElem;
    return t;
}

//遍历输出
void displayTable(table t){
    for (int i=0;i<t.length;i++) {
        printf("%d ",t.head[i]);
    }
    printf("
");
}


int main(){
    table t1=initTable();
    for (int i=1; i<=Size; i++) {
        t1.head[i-1]=i;
        t1.length++;
    }
    printf("原顺序表：
");
    displayTable(t1);
  
    printf("删除元素1:
");
    t1=delTable(t1, 1);
    displayTable(t1);
  
    printf("在第2的位置插入元素5:
");
    t1=addTable(t1, 5, 2);
    displayTable(t1);
  
    printf("查找元素3的位置:
");
    int add=selectTable(t1, 3);
    printf("%d
",add);
  
    printf("将元素3改为6:
");
    t1=amendTable(t1, 3, 6);
    displayTable(t1);
    return 0;
}

输出：

原顺序表：
1 2 3 4 5
删除元素1:
2 3 4 5
在第2的位置插入元素5:
2 5 3 4 5
查找元素3的位置:
3
将元素3改为6:
2 5 6 4 5
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/wind-zhou/p/12873273.html