数据结构与算法学习记录（二）顺序表的结构以及基本操作

骑猪看日落 2023-05-21 11:50 19阅读 0赞

### 1、顺序表的概述 ###

顺序表就是按照顺序存储方式存储的线性表，该线性表的结点按照逻辑次序依次存放在计算机的一组连续的存储单元中。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dhb1hpUg_size_16_color_FFFFFF_t_70]  
由于顺序表示依次存放的，只要知道了该顺序表的首地址及每个数据元素所占用的存储长度，那么就很容易计算出任何一个数据元素的位置。  
一般的，其中第一个单元的存储地址则为该结点的存储地址，并设顺序表中开始结点a1的存储地址，简称为基址。

### 2、顺序表的基本操作 ###

1、准备数据  
定义在顺序表操作中需要用到的变量及数据结构。

//定义顺序表的最大长度
    static final int MAXLEN = 100; 
    
    class DATA{ 
    	//结点的关键字
    	String key; 
    	String name;
    	int age;
    }
    
    class SLType{ 
    	//保存顺序表的结构数组
    	DATA[] ListData = new DATA[MAXLEN+1];
    	//顺序表已存结点的数量，即顺序表的长度。
    	int ListLen;
    }

2、初始化顺序表

void SLInit(SLType SL){ 
    	//初始化为空表
    	SL.ListLen = 0;
    }

需要注意的是，这里并没有清空一个顺序表。读者也可以采用相应的程序代码来清空，只需简单地将就结点数量ListLen设置为0即可，这样如果顺序表中原来已有数据，也会被覆盖，并不影响操作，反而提高了处理的速度。  
3、计算顺序表的长度  
计算顺序表的长度即计算线性表L中结点的个数。

int SLLength(SLType SL){ 
    	//返回顺序表的元素数量
    	return (SL.ListLen)
    }

4、插入结点

插入结点就是在线性表L的第i个位置插入一个新的结点，使得其后的结点编号依次加1。这时，插入一个新结点之后，线性表L的长度将变为n+1。插入结点的操作的难点在于随后的每个结点数据都要进行移动，计算量比较大。

int SLInsert(SLType SL,int n,DATA data){ 
    	int i;
    	//顺序表结点数量已超过最大数量
    	if(SL.ListLen>=MAXLEN){ 
    		System.out.print("顺序表已满，不能插入结点！");
    		return 0;
    	}
    	//插入结点序号不正确
    	if(n<1||n>SL.ListLen-1){ 
    		System.out.print("插入元素序号错误，不能插入元素！");
    		return 0;
    	}
    	for(i=SL.ListLen;i>n;i--){ 
    		SL.ListData[i+1] = SL.ListData[i];
    	}
    	//插入结点
    	SL.ListData[n] = data;
    	//顺序表结点数量增加1
    	SL.ListLen++;
    	return 1;
    }

在上述代码中，在程序中首先判断顺序表结点数量是否已经超过最大数量，以及插入结点序号是否正确。所有条件都满足后，然而将顺序表中的数据向后移动，同时插入结点，并更新结点数量ListLen.

5、追加结点  
追加结点并不是一个基本的数据结构运算，其可以看做插入结点的一种特殊形式，相当于在顺序表的末尾新增一个数据结点。由于追加结点的特殊性，其代码实现相比插入结点要简单，因为不必进行大量数据的移动，因此这里单独给出其实现的程序。

//追加元素到顺序表尾部
    int SLAdd(SLType SL,DATA data){ 
    	//顺序表已满
    	if(SL.ListLen>=MAXLEN){ 
    		System.out.print("顺序表已满，不能再添加结点了！");
    		return 0;
    	}
    	SL.ListData[++SL.ListLen] = data;
    	return 1;
    }

在上述代码中，仅简单判断这个顺序表是否已经满了，然后便追加该结点，并更新结点数量ListLen.  
6、删除结点  
删除结点即删除线性表中的第i个结点，使得其后的所有结点编号依次减1.删除一个结点之后，线性表L的长度将变为n-1.删除结点和插入结点类似，都需要进行大量数据的移动。

//删除顺序表中的数据元素
    int SLDelete(SLType SL,int n){ 
    	int i;
    	//删除结点序号不正确
    	if(n<1||n>SL.ListLen+1){ 
    		System.out.print("删除结点序号错误，不能删除结点");
    		return 0;
    	}
    	//将顺序表中的数据向前移动
    	for(i=n;i<SL.ListLen;i++){ 
    		SL.ListData[i]=SL.ListData[i+1];
    	}
    	//顺序表元素数量减1
    	SL.ListLen--;
    	//成功删除，返回1
    	return 1;
    }

在上述代码中，首先判断待删除的结点序号是否正确，然后开始移动数据，并更新结点数量ListLen。

7、查找结点  
查找结点即在线性表L中查找值为x的结点，并返回该结点在线性表L中的位置。如果，在线性表中没有找到值为x的结点，则返回一个错误标志。根据值x类型的不同，查找结点可以分为按照序号查找结点和按照关键字查找结点两种方法。  
1）按照序号查找结点  
对于一个顺序表，序号就是数据元素在数组中的位置，也就是数组下标标号。按照序号查找结点是顺序表查找结点最常用的方法，这是因为顺序表的存储本身就是一个数组。

//根据序号返回数据元素
    DATA SLFindByNum(SLType SL,int n){ 
    	//元素序号不正确
    	if(n<1||n>SL.ListLen+1){ 
    		System.out.print("结点序号错误，不能返回结点");
    		return 0;
    	}
    	return SL.ListData[n];
    }

2)按照关键字查找结点  
关键字可以是数据元素结构中的任意一项。这里以key为关键字介绍。由前面知道的key可以看作学生的学号。

//按照关键字查询结点
    int SLFindByCont(SLType SL,String key){ 
    	int i;
    	for(i=1;i<=SL.ListLen;i++){ 
    		//如果找到所需结点
    		if(SL.ListData[i].key.compareTo(key)==0)			      { 
    		return i;
    		}
    	}
    	//搜索整个表后仍没有找到，则返回0
    	return 0;
    }

8、显示所有结点  
显示所有结点数据并不是一个数据结构基本的运算，因为其可以简单的逐个引用结点来实现。不过为了方便，还是将其单独列为一个方法。

//显示顺序表中的所有的结点
    int SLAll(SLType SL){ 
    	int i;
    	for(i=1;i<=SL.ListLen;i++){ 
    		System.out.printf("(%s,%s,%d)\n",SL.ListData[i].key,SL.ListData[i].name,SL.ListData[i].age);
    	}
    	return 0;
    }

至此顺序表的介绍结束，欢迎共同学习交流。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dhb1hpUg_size_16_color_FFFFFF_t_70]: /images/20230521/099ffe052f58480fa0f0986e05fc5287.png