首页 > 其他分享 >数据结构学习笔记-day3

数据结构学习笔记-day3

时间:2023-03-12 22:14:08浏览次数:50  
标签:顺序 return 线性表 day3 笔记 elem 算法 length 数据结构

Day3

一、线性表的定义和特点

由n(n>=0)个数据特性相同的元素构成的有限序列称为线性表。

N为线性表的长度,当n=0时,称其为空表。

   二、线性表的顺序表示和实现

           在C语言中可用动态分配的一维数组表示线性表:

                #define MAXSIZE 100;           //顺序表可能达到的最大长度

                Typedef struct{
                       ElemType  *elem;       //存储空间的基地址

                       Int length;               //当前长度

}SqList;                     //顺序表的结构类型为SqList

           注.(1)数组空间通过动态分配初始化得到,初始化完成后指针elem指向顺序表的基地址;

            (2)元素类型定义中的ElemType数据类型是为了描述统一而自定的,可以根据需要确定为具体的类型。

三、线性表的基本操作

      1.初始化

        算法描述:

           Status  initlist(sqlist  &L)

             {//构造一个顺序表L

               L.elem=new elemtyoe[MAXSIZE];

               If(!L.elem) exit(OVERFLOW);

               L.length=0;

               Return OK;

               }

2.取值(顺序存储有随机存取的特点)

算法描述:

   Status getelem(sqlist L,int I,elemtype &e){

             If(i<1||i>L.length) return ERROR;

             e=L.elem[i-1];

             return OK;

             }

 

算法分析:T(n)=O(1);

3.查找

算法描述:

   Int locateelem(sqlist L,elemtype e){

             for(i=0;i<L.length;i++)

                 if(L.elem[i]==e) return i+1;

             return 0;

             }

 

算法分析:在查找时,为确定元素在顺序表中的位置,需要与给定值进行

比较的元素个数的期望值称为查找算法在查找成功时的平均查找长度(ASL)。

                             ASL=(n+1)/2

          可见顺序表按值查找算法的T(n)=O(n)

4.插入

     算法描述:

         Status listinsert(sqlist L;int I;elemtype e){

                    If((i<1)||(i>L.lengh+1)) return ERROR;

                    If(L.length==MAXSIZE) 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;

                      Return OK;

                      }

 

                 算法分析:Eins为在长度为n的线性表中插入一个元素时所需移动元

素次数的期望值(平均次数)。

                               Eins=n/2

                 可见顺序表插入算法的T(n)=O(n)

5.删除

    算法描述:

        Status listdelete(sqlist &L,int i){

             If(i<1||i>L.length) return ERROR;

             for(j=I;j<L.length;j++)

                  L.elem[j-1]=L.elelm[j];

             --L.length;

             return OK;

             }

 

                 算法分析:Edel为在长度n的线性表中删除一个元素时所需移动元素次数的期望值。

                                      Edel=(n-1)/2

                           可见顺序表删除算法的T(n)=O(n)

标签:顺序,return,线性表,day3,笔记,elem,算法,length,数据结构
From: https://www.cnblogs.com/k4fk4-shaw/p/17209315.html

相关文章

  • 代码随想录算法Day39 | 62.不同路径,63. 不同路径 II
    62.不同路径题目链接:62.不同路径-力扣(LeetCode)思路确定dp数组(dptable)以及下标的含义dp[i][j]:表示从(0,0)出发,到(i,j)有dp[i][j]条不同的路径。确定递推公式......
  • 数论学习笔记
    一、一些基本定义加性函数:\[\forallf\inAdd:\gcd(x,y)=1\impliesf(xy)=f(x)+f(y)\]完全加性函数:\[\forallf\inAdd^*:f(xy)=f(x)+f(y)\]积性函数:\[\forallf\in......
  • 【数据结构入门】带头双向循环链表(List)详解(初始化、增、删、查、改)
    1、链表的种类:总共有8种,以带不带头,单向或者双向,循环或者不循环来组合形成。单向或者双向带头或者不带头循环或者非循环主要学习下面两种链表的功能实现无头单向非循环链表:又......
  • 代码大全 阅读笔记01
    阅读了代码大全,以下是我的收获:松散耦合性:耦合性就是两个子程序之间的紧密程度。要注意耦合的规模:注意两个子程序之间的联系程度。注意两个子程序之间的联系的直接程度,越......
  • 自用nodejs安装笔记
    下载Nodejs进入Nodejs官网https://nodejs.org/zh-cn/下载安装Node.js检查Nodejs和npm包管理器是否安装成功用管理员打开cmd控制台命令行输入node-v查看......
  • 韩顺平java学习笔记——概述
    Java执行流程分析Java文件(源文件)—javac编译->.class文件(字节码文件)--java运行->结果什么是编译Javachello.java1、 有了java源文件,通过编译器将其变异成JVM可以......
  • 数据结构与算法
    释义:数据结构啥指相互之前存在一种或多种特定关系的数据元素的集合算法是规则的有限集合,是为解决特定问题而规定的一系列操作程序=数据结构+算法语句频度:是指该语句......
  • 第一周 数据结构初始
    数据结构部分排序算法共有冒泡、选择、插入、归并、快速排序、堆排序和不基于比较的排序冒泡排序:比较相邻的两个元素、如果前数小就交换两数的位置,这样一组之后就可以......
  • Unity面试题一日一讲 B站游戏石匠视频讲解 学习笔记
    三叶虫也能看懂的Unity面试题一日一讲求最少需要多少场赛跑,可以求出其中跑的最快的三头猪。(最少多少场可以百分百保证求出正确结果)答案:9场。堆栈问题有如下一个类......
  • 【项目实战】基于Python+Flask+MySQL的在线笔记管理系统
    1、项目说明基于python+Flask+mysql的在线笔记管理系统项目实战项目需要安装pycharm专业版,mysql数据库以及项目所需的所有模块创建数据库名称db_online_notes,然后执行sq......