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

1. 内容

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

2.代码

#include<stdio.h>
#include<stdlib.h> //函数结果状态代码
#define OK 1
#define OVERFLOW -2
#define ERROR 0
#define MAXSIZE 100typedef 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;  //空间创建失败返回OVERFLOWL.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;
}

运行结果：