• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

线性表的基本操作

开发技术 开发技术 4小时前 1次浏览

线性表的基本操作

顺序表的实现——静态分配

#define Maxsize 10 				//定义最大的长度 
typedef struct{					
	ElemType data[MaxSize];		//用静态的数组存放数据元素
	int length;					//顺序表的当前长度
}SqList;						//顺序表的类型定义(静态分配方式)
  • 具体代码
#include<stdio.h>
#define MaxSize 10						//定义最大长度
typeof struct{							
    int data[MaxSize];					//用静态数组存放数据,数据的大小为最大长度
    int length;							//顺序表的当前长度,就是当前存放了多少个数据
}SqList;								//顺序表的类型定义
										
//基本操作——初始化一个顺序表
void IniList(SqList &L){				
   /* for(int i = 0; i < MaxSize; i++)	这里也可以省略,虽然内存中会遗留脏数据,但是我们访问只会访问小于顺序表长度的数据,并不会访问的后面的脏数据
		L.data[i] = 0;	*/				//将所有数据元素设置成默认初始值
        L.length = 0;					//顺序表初始长度为0,这个是不能省略的
}	

int main(){
	SqList L;							//声明一个顺序表
    InitList(L);   						//初始化顺序表
    .......								
    return 0;							
}

顺序表的实现——动态分配

#define InitList 10			//顺序表的初始长度
typedef struct{				
	ElemType *data;			//指示动态分配数组的指针
	int MaxSize;			//顺序表的最大容量
	int length;				//顺序表的当前长度
}SqList;					//顺序表的类型定义(动态分配的方式)
  • key:动态申请和释放内存空间
c—— malloc、free函数
	L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize);
c++——new、delete关键字
  1. ElemType:malloc函数返回一个指针,需要强制转换为你定义的数据元素类型的指针
  2. InitSize:malloc函数的参数,指明要分配多大的连续内存空间
  • 具体代码
#define InitSize 10	//默认的最大长度
typedef struct{
	int *data;//指示动态分配数组的指针
    int MaxSize;//顺序表的最大容量
    int length;//顺序表的当前长度
}SeqList;

void InitList(SeqList &L){
    //用malloc函数申请一片连续的存储空间
	L.data = (int *)malloc(InitSize*sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;
}
//增加动态数组的长度
void IncreaseSize(SeqList &L, int len){
	int *p = L.data;
    L.data = (int *)malloc((L.MaxSize+len)*sizeof(int));//另为开辟一片连续的新区域
    for(int i = 0; i < L.length; i++){
		L.data[i] = p[i];//将数据复制到新区域
    }
    L.MaxSize = L.MaxSize +len;//顺序表最大长度增加len
    free(p);//释放原来的内存空间
}

int main(){
	SeqList L;//声明一个顺序表
    InitList(L);//初始化顺序表
    ......//往顺表中插入几个元素
    IncreaseSize(L,5);
    return 0;
}

顺序表的基本操作——插入

  • ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。
#define MaxSize 10//定义最大长度
typedef struct{
	ElemType data[MaxSize];//用静态的数组存放数据元素
	int length;//顺序表的当前长度
}SqList;//顺序表的类型定义

线性表的基本操作

  • 具体代码
#define MaxSize 10 //定义最大长度
typedef struct{
	int data[MaxSize];//用静态的数组存放数据元素
	int length;//顺序表的长度
}SqList;//顺序表的类型定义

//插入代码不够健壮,因为如果i大于length,就会出现问题
void ListInsert(SqList &L, int i , int e){
	for(int j = L.length; j >= i; j--)//将第i个元素及之后的元素后移,从最后一个元素开始移动
    	L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;//循环结束后,在位置i处放入e
    L.length++;//长度加1
}

int main(){
	SqLlist L;//声明一个顺序表
    InitList(L);//初始化顺序表
    //。。。。。插入几个元素
    ListInsert(L,3,3);
    return 0;
}

修改插入操作代码:

bool ListInsert(SqList &L,int i, int e){//bool类型的函数,返回值是false或true
	if(i < 1 || i > L.length + 1)//判断i的范围是否有效
        return false;
    if( L.length >= MaxSize)//当前的存储空间已满,不能插入
        return false;
    for(int j = L.length; j >=i; j--)//将第i个元素及之后的元素后移
        L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;//在位置i处放入e
    L.length++;//长度加1
    return true;
}
  • 时间复杂度:问题规模n = L.length
    • 最好情况:新元素插入到表尾,不需要移动元素O(1)
    • 最坏情况:新元素插入到表头,每个元素都需要移动O(n)
    • 平均情况:新元素插入到任何一个位置的概率相同O(n/2)

顺序表的基本操作——删除

  • ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值

线性表的基本操作

bool ListDelete(Sq.List &L, int i, int &e){
	if(i < 1 || i > L.length)//判断i的范围是否有效
        return false;
    e = L.data[i - 1];//将被删除的元素赋值给e
    for(intn j  = i; j < L.length; i++)//将第i个位置后的元素前移,前移操作从前到后依次进行
        L.data[j - 1] = L.data[j];
    L.length--;//线性表长度减1
    return true;
}

int main(){
	SqList L;//声明一个顺序表
    InitList(L);//初始化顺序表
    //插入几个元素
    int e = -1;//用变量e把删除的元素“带回来”
    if(ListDelete(L,3,e))
        printf("已删除第3个元素,删除元素值为=%dn", e);
    else
        printf("位序i不合法,删除失败n");
    return 0;
}
  • 时间复杂度:

    • 最好情况:删除表位元素,不需要移动其他元素O(1)
    • 最坏情况:删除表头元素,需要将后续的n-1个元素全都向前移动O(n)
    • 平均情况:删除任何一个元素的概率相同O((n-1)/2)
  • 代码要点:

    • 代码中注意位序i和数组下标的区别
    • 算法要有健壮性,注意判断i的合法性
    • 注意移动元素的时候,从考前的元素开始,还是从表尾开始

顺序表的按位查找

  • GetElem(L,i)/;按位查找。获取表L中第i个位置的元素的值。

  • 静态分配下的按位查找

    #define MaxSize 10
    typedef struct{
    	ElemType data[MaxSize];
    	int length;
    }SqList;
    
    ElemType GetElem(SqList L, int i){//这里还可以判断一下i的值是否合法
    	return L.data[i-1];
    }
    
  • 动态分配下的按位查找

    #define InitSize 10
    typedef struct{
    	ElemType *data;
        int MaxSize;
        int length;
    }SeqList;
    
    ElemType GetElem(SeqList L, int i){
    	return L.data[i - 1];//和访问普通数组的方法一样
    }
    

    动态分配的指针指向的是连续地址的初始位置,在加入下标之后,电脑是自动按指针类型来访问相应位置所以对用的数据。如下图

    线性表的基本操作

  • 时间复杂度:O(1)

顺序表中的按值查找

  • LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素

    #define InitSize 10
    typedef struct{
    	ElemType *data;
    	int MaxSize;
    	int length;
    }SeqList;
    
    //在顺序表L中查找第一个元素值等于e的元素,并返回其位序
    int LocateElem(SeqList L,ElemType e){
    	for(int i = 0; i < L.length; i++)
    		if(int L.data[i] == e)//基本数据类型:int、char、double、float等可以直接用运算符“==”比较,但是结构类型是不能用“==”进行比较的
    			return i+1;//数组下标为i的元素值等于e,返回其位序i-1
    	return 0;//退出循环,说明查找失败
    }
    
    

    如果是比较结构体,需要依次对比各个分量来判断两个结构体是否相等

    if(a.num == b.num && a.people == b.people){
    	printf("相等");
    }else{
    	printf("不相等");
    }
    

    更好的方法:定义一个函数

    bool isCustomerEqual(Customer a, Customer b){
    	if(a.num == b.num && a.people == b.people)
    		return true;
    	else
    		return false;c
    }
    

    在数据结构考研初试中,手写代码可以直接用==,无论是基本数据类型还是结果类型

    时间复杂度

  • 时间复杂度:

    • 最好情况:目标出现在表头:O(1)
    • 最坏情况:目标元素在表尾:O(n)
    • 平均情况:目标元素在每个位置的概率相同O(n)

程序员灯塔
转载请注明原文链接:线性表的基本操作
喜欢 (0)