【数据结构】静态分配的顺序表插入元素

这篇具有很好参考价值的文章主要介绍了【数据结构】静态分配的顺序表插入元素。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

#include<stdio.h>
#include<stdlib.h>

#define maxSize 10

// listInsert(&L,i,e)	在第i个位置插入指定元素e

typedef struct {
	int data[maxSize];
	int length;
}SqList;

void initList(SqList &L) {
	for(int i=0;i<L.length; i++) {
		L.data[i]=i;
	}
	L.length = 0;	
}

/**
* 思路:第i个元素及其之后的元素都向后移,i-1后面就空出来一个空地址 
* 那么新加元素就变成了第i个,原i就变成了i+1个 
* 在空出来的这个地址,即第i的位置,赋值data[i]=e  
*
*
* 怎么后移:data[i] = data[i-1]   那么i-1的位置不就空出来了吗 
* 注意: i是位序,位序从1开始,下标从0开始,位序和下标是两东西 
* data[下标]获取当前位置的数据元素,
* 也就是说,第i=1个位置的元素是data[0],...第i=L.length个位置的元素是data[L.length-1] 
*/
bool listInsert(SqList &L, int i, int e) {
	/* i是位序,从1开始,
	* 显然:<1或者超过顺序表长度就是不合法的,
	* 因为第1个位置前面没有位置,
	* 第L.length个位置后面插入一个叫做在最后一个元素后面插入,即在第L.length+1个位置 
	* 如果直接跳L.length+1个位置,就是不合法
	* 还有就是,插入新元素之前,要先判断下顺序表的连续存储空间是否还有空位置,如果已经满了,那肯定没法插入
	*/
	// 为了代码的健壮性,要加些判断 
	if(i<1 || i>L.length+1)
		return false;
	
	if(L.length > maxSize)
		return false;
	/** 
	* 假设i=6,就是要在第6个位置插入新元素e
	* 那就要将原i=6位置的元素及其之后的以此向后移,为了拿到原i=6及其之后的元素,此时就要遍历
	* 但是,i=5及其之前的元素是不应该移动的,所以在遍历的时候,j<i=6的元素就不要操作,只操作j>=i的 
	*/
	for(int j=L.length;j>=i;j--) {
		L.data[j] = L.data[j-1];
	} 	
	// for循环执行完后,此时原第i个及其之后的元素已经后移了,目前第i个位置已经空出来了,插入新元素e
	L.data[i-1] = e;		// 第i=6个位置,实际上它的数组下标为5,就是L.data[i-1],将数据项赋值为e
	L.length++;			// 长度加1 
	
	return true;
}

int main() {
	SqList L;
	initList(L);
	for(int k=0;k<maxSize;k++){
		listInsert(L,k,k);
	}

	printf("%d\t数据长度\n",L.length);
	for(int h=0;h<L.length;h++){
		printf("%d\t数组元素依次输出\n",L.data[h]);
	}
	
	return 0;
}

分析一下当前算法的时间复杂度,注意:顺序表的元素移动,是从最后一个元素依次移动的
1、新元素插入到表尾,i=n+1,就不用移动元素,不移动就不要走for循环,for循环0次,时间复杂度为O(1)
2、新元素插入到表头,i=1,就要移动所有元素,有n个元素移动n个,for循环n次,时间复杂度为O(n)
3、随机插入除表头和表尾的任意一个位置,它们的概率都相同,即i=1、2、3...length+1的概率都是P=1/(n+1)
i=1,循环n次,i=2,循环n-1次,...i=n+1,循环0次
平均循环次数=循环总次数*概率= (1+2+3+...+n+1)*1/(n+1)=(n+1)n/2 * 1/(n+1)=n/2
时间复杂度为O(n) 文章来源地址https://www.toymoban.com/news/detail-726396.html

到了这里,关于【数据结构】静态分配的顺序表插入元素的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包