数据结构线性表——顺序表

#define Maxsize 22
typedef int ElemType;
typedef struct {
	ElemType data[Maxsize];
	int length;

}Sqlist;


#define InitSize 100
typedef struct {
	ElemType *data;
	int Max_size, length;
}Seqlist;

//顺序表插入
bool ListInsert(Sqlist &L, int i, ElemType e) {
	if (i<1 || i>L.length)
	{
		return false;
	}
	if (L.length >= Maxsize)
	{
		return false;
	}
	for (int j = L.length; j >= i; j--)
	{
		L.data[j] = L.data[j - 1];//第i个元素及以后依次后移
	}

	L.data[i - 1] = e;//在位置i插入元素e;
	L.length++;//线性表长度加1
	return true;
}
/*算法分析:表尾插入 i=n+1; 时间复杂度:O(1)
       表头插入 i=1;   时间复杂度 O(n)
	   平均时间复杂度: O(n)
	   */

bool ListDelete(Sqlist &L, int i, ElemType &e)
{
	if (i<1 || i>L.length)
	{
		return false;
	}
	e = L.data[i];			//将被删除的元素赋值给e
	for (int j = i; j < L.length; j++)
	{
		L.data[j - 1] = L.data[j];	//将第i个位置后的元素前移
	}
	L.length--;					//线性表长度减1
	return true;
}

/*算法分析:表尾删除 i=n; 时间复杂度:O(1)
		  表头删除 i=1;   时间复杂度 O(n)
		  平均时间复杂度: O(n)
	   */


int LocateElem(Sqlist L, ElemType e) {

	int i;
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] == e) {
			return i + 1;
		}
	}
	return 0;

}
/*算法分析:表头查找 : 时间复杂度:O(1)
	      表尾查找 :  时间复杂度 O(n)
	   平均时间复杂度: O(n)
	   */

 

上一篇:自用数据结构


下一篇:队列基本操作以及用队列实现杨辉三角