1. 数据结构——顺序表的主要操作

1. 内容

顺序表的初始化、插入、删除、按值查找、输出以及其时间复杂度的计算。

2.代码

#include<stdio.h>
#include<stdlib.h> 
 
//函数结果状态代码
#define OK 1
#define OVERFLOW -2
#define ERROR 0
#define MAXSIZE 100
 
typedef int ElemType;  //顺序表每个数据元素存储类型
typedef int Status; 
 
//定义顺序表的结构体SqList 
typedef struct sqlist{
	ElemType *elem;  //存储空间的基地址
	int length;    //当前长度 
}SqList; 
 
//1.顺序表的初始化
Status InitList(SqList &L){
//	L.elem=new ElemType[MAXSIZE];  //c++开辟空间 
    L.elem=(ElemType *)malloc(sizeof(ElemType)*MAXSIZE); 
	if(!L.elem) return OVERFLOW;  //空间创建失败返回OVERFLOW
	L.length=0;
	return OK; 
} 
 
//2.顺序表插入(在顺序表L的第i个位置插入e)
//插入的位置范围可以是1到length+1(末尾位置之后也可) 
Status ListInsert(SqList &L,int i,ElemType e){
	if(i<1||i>L.length+1)  //判断i是否有效 
		return ERROR;  
	if(L.length>=MAXSIZE)  //判断存储空间是否已满 
		return ERROR; 
	//需要将length-1到i-1位置上的值全部往后移一位
	for(int j=L.length;j>=i;j--){
		L.elem[j]=L.elem[j-1];
	} 
	L.elem[i-1]=e;
	L.length++;
	return OK;
} 
//若线性表长度为n,则： 
//最好情况：直接在表尾插入，时间复杂度O(1)
//最坏情况：在表头插入，需要将n个全部后移一位，时间复杂度O(n)
//平均情况：第一个移动n,第二个移动n-1,......第n个移动1，第n+1移动0个 
//n(n+1)/2 * 1/(n+1) =n/2 
 
//3.删除操作(删除顺序表L第i个位置上的值,并将其值返回给e)
Status ListDelete(SqList &L,int i,ElemType &e){
	if(i<1||i>L.length)  //判断i是否合法 
		return ERROR;
	e=L.elem[i-1];
	//将i到L.length-1位置上的值统统往前移
	for(int j=i;j<L.length;j++)
		L.elem[j-1]=L.elem[j];
	L.length--;
	return OK; 
}
//最好情况：直接删除表尾元素，时间复杂度O(1)
//最坏情况：删除表头元素，需要将n-1个全部前移一位，时间复杂度O(n)
//平均情况：第一个移动n-1,第二个移动n-2,......第n个移动0
//(n-1)*n/2 * (1/n) =(n-1)/2
 
 
//4.按值查找(在顺序表L中查找第一个值为e的元素，并返回其位序)
Status LocateElem(SqList L,ElemType e){
	for(int i=0;i<L.length;i++){
		if(L.elem[i]==e)
			return i+1;
	}
	return ERROR; 
}
//最好情况：第一个就查找到了，时间复杂度O(1)
//最坏情况：最后才查找到或者未查找到，时间复杂度O(n)
//平均情况：在第一个位置1，第二个位置2，...，第n个位置n 
//n*(1+n)/2 * (1/n)= (n+1)/2
 
//5. 输出顺序表
void TraverseList(SqList L){
	for(int i=0;i<L.length;i++){
		printf("%-4d",L.elem[i]);
	}
	printf("\n");
} 
 
int main(void){
	SqList L;
	ElemType e;
	InitList(L);
	ListInsert(L,1,3);
	ListInsert(L,2,4);
	ListInsert(L,3,5);
	printf("插入后顺序表中的元素有:\n");
	TraverseList(L);
	ListDelete(L,1,e);
	printf("第1个位置删除的值为：%d\n",e);
	printf("删除后顺序表中的元素有:\n");
	TraverseList(L);
	int t=LocateElem(L,3);
	if(t==ERROR)
		printf("3在顺序表中不存在");
	else 
		printf("3存在于顺序表的第%d位置上"); 
	return 0;
} 
 

运行结果：

我代码的主程序仅仅只是简单验证了一下代码的正确性，并不全面，可以根据功能函数设计主菜单使其更加完备。