数据结构——顺序表-创新互联

• 顺序表类型定义
• 数组定义
• C++的动态存储分配
• C++中的参数传递
• 操作算法中补充内容
• 顺序表基本操作
• • 算法1 线性表L的初始化
  • 算法2 顺序表的取值
  • 算法3 顺序表的查找
  • 算法4 顺序表的插入（时间复杂度为O(n)）
  • 算法5 顺序表的删除（时间复杂度为O(n)）
• 顺序存储分析

typedef char ElemType; //定义为char

typedef struct{ElemType data[];
	int length;
}SqList;	// 顺序表类型

// 数组静态分配
typedef struct{ElemType data[MaxSize];
	int length;
}SqList;	//顺序表类型


// 数组动态分配
typedef struct{ElemType *data;
	int length;
}SqList;	//顺序表类型

SqList L;
L.data = (ElemType*)malloc(sizeof(ElemType)*MaxSize);

内存分配函数（需要加载头文件）

1. malloc(m)函数，开辟m字节长度的地址空间，并返回这段空间的首地址。
2. sizeof(x)运算，计算变量x的长度。
3. free(p)，释放指针p所指变量的存储空间，即彻底删除一个变量。

new 类型名T (初值列表)
// 功能：申请用于存放T类型对象的内存空间，并依初值列表赋初值
// 结果值：
//   成功：T类型的指针，指向新分配的内存
//   失败：0 (NULL)

delete 指针P
// 功能：释放指针p所指向的内存，p必须是new操作的返回值。

1. 函数调用时传送给形参表的实参必须与形参的类型、个数、顺序一致。
2. 参数传递的两种方式：传值&传地址。

// 函数结果状态代码
# define OK		1
# define ERROR	0
# define INFEASIBLE	-1
# define OVERFLOW 	-2

// Status是函数的类型，其值是函数结果状态代码
typedef int Status;
typedef char ElemType;

// 销毁线性表L
void DestroyList(SqList &L){if(L.elem) delete L.elem;
}
// 清空线性表L
void ClearList(SqList &L){L.length = 0;
}
// 求线性表的长度
int GetLength(SqList L){return(L.length);
}
// 判断线性表L是否为空
int IsEmpty(SqList L){if(L.length==0) return 1;
	else return 0;
}

Status IniList Sq(sqList &L){L.elem = new ElemType[MAXSIZE];		// 分配空间
	if(!L.elem) exit(OVERFLOW);			// 分配失败
	L.length = 0;						// 空表长度为0
	return OK;

int GetElem(SqList L, int i, ElemType &e){if(i<1||i>L.length) return ERROR;	// 判断是否合理
	e = L.elem[i-1];	// i-1的单元存储着第i个数据
	return OK;

平均查找长度ASL（Average Search Length）：为确定记录在表中的位置，需要与给定值进行比较的关键字的个数的期望值。对含有n个记录的表，查找成功时：
A S L = ∑ i = 1 n P i C i ASL = \sum_{i=1}^{n}P_iC_i ASL=i=1∑n​Pi​Ci​

// 在L中查找与指定值e相同的数据元素的位置
int LocateElem(SqList L, ElemType e){for(i=0; i

Status ListInsert_Sq(SqList &L, int i, ElemType e){if(i<1||i>L.length+1) return ERROR;		// i值不合法
	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;

Status ListDelete_Sq(SqList &L, int i){if(i<1||i>L.length) return ERROR;		// i值不合法
	if(L.length == MAXSIZE) return ERROR;	// 存储空间已满
	for(j=i; j>=L.length-1; j++)
		L.elem[j-1] = L.elem[j];			// 插入位置及之后的元素后移
	L.length--;
	return OK;