最近在复习数据结构，参考资料为王道数据结构
/*********************************************************//*Project: sequence_list(数据结构-顺序表) Date: /07/22Author: CWSCreatList(SqList &L,int n) 参数：顺序表L，顺序表长度n 功能：创建长度为的顺序表 时间复杂度：O(n)InitList(SqList &L) 参数：顺序表L 功能：初始化 时间复杂度:O(1)InsertList(SqList &L,int i,ElemType e) 参数:顺序表L,位置i,元素e 功能：位置i处插入元素e 时间复杂度:O(n)ListDelete(SqList &L,int i) 参数:顺序表L,位置i 功能：删除位置i处元素 时间复杂度:O(n)LocateElem(SqList L,ElemType e) 参数:顺序表L,元素e 功能：返回第一个等于e的元素的位置 时间复杂度:O(n)PrintList(SqList L) 参数:顺序表L 功能：遍历L，并输出*/#include<stdio.h>#include<string.h>#define MaxSize 100 //定义线性表的最大长度#define ElemType int //假定表中元素类型是int#define Status int//定义一个结构体，表示了顺序表的类型//数组是静态分配的（大小固定）typedef struct{ElemType data[MaxSize]; //顺序表的元素（开辟int类型的数组，数组名叫data，数组名就是数组的起始位置，数组大小就是MaxSize）int length; //顺序表的当前长度}SqList; //顺序表的类型定义//*******基本操作函数*********////初始化顺序表函数，构造一个空的顺序表Status InitList(SqList &L){memset(L.data,0,sizeof(L)); //初始化数据为0L.length=0;return 0;}//创建顺序表函数 初始化前n个数据bool CreatList(SqList &L,int n){if(n<0||n>MaxSize)return false; //非法for(int i=0;i<n;i++){scanf("%d",&L.data[i]);L.length++;}return true;}//插入 顺序表插入算法的平均时间复杂度为O(n)/*算法流程：在顺序表L的第i(1<=i<=length+1 )个位置插入新元素e，如果i的输入不合法，则返回false，表示插入失败；否则，将顺序表的第i个元素以及其后的所有元素向右移一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true算法思路：1.判断i的值是否正确2.判断表长是否超过数组长度3.从后向前到第i个位置，分别将这些元素都向后移动一位返回类型 函数名 参数列表(&L 带引用符号& 因为要对这个表进行修改)*/bool InsertList(SqList &L,int i,ElemType e){if(i<1||i>L.length+1)//判断i的范围是否有效{printf("位置无效！\n");return false;}if(L.length>=MaxSize)//当前存储空间已满，不能插入{printf("当前存储空间已满！！！\n");return false;}//表中最后一个元素的下标是length-1，再后一位是lengthfor(int j=L.length;j>=i;j--)L.data[j]=L.data[j-1];L.data[i-1]=e;//在位置i处放入eL.length++;//线性表长度加1return true;}//删除/*算法流程：删除顺序表L中第i(1<=i<=L.length)个位置的元素，成功则返回true,否则返回false算法思路：1.判断i的值是否正确2.取删除的元素3.将被删元素后面的所有元素都依次向前移动一位 4.修改表长*/bool ListDelete(SqList &L,int i){if(i<1||i>L.length){printf("位置无效！");return false;}for(int j=i;j<=L.length-1;j++){L.data[j-1]=L.data[j];}L.length--;return true;}//查找函数int LocateElem(SqList &L,ElemType e){for(int i=0;i<L.length;i++) //从低位置查找{if(e==L.data[i]) return i+1;//下标为i的元素值等于e，返回其位序i+1}return 0;//退出循环，说明查找失败}//*******功能函数**********////输出功能函数，按位置从小到大输出顺序表所有元素void PrintList(SqList L){printf("当前顺序表所有元素:");for(int i=0;i<L.length;i++){printf("%d ",L.data[i]);//依次输出}printf("\n");}//创建顺序表函数void Create(SqList &L){int n;bool flag;printf("请输入要创建的顺序表长度(>1):");scanf("%d",&n);printf("请输入%d个数（空格隔开）:",n);flag=CreatList(L,n);if(flag){printf("创建成功！\n");PrintList(L);}else printf("输入长度非法！\n");}//插入功能函数 调用InsertList完成顺序表元素插入 调用PrintList函数显示插入成功后的结果void Insert(SqList &L){int place;ElemType e;bool flag;printf("请输入要插入的位置(从1开始)及元素:\n");scanf("%d%d",&place,&e);flag=InsertList(L,place,e);if(flag){printf("插入成功！\n");PrintList(L);}}//删除功能函数 调用ListDelete函数完成顺序表的删除 调用PrintList函数显示插入成功后的结果void Delete(SqList &L){int place;bool flag;printf("请输入要删除的位置(从1开始):\n");scanf("%d",&place);flag=ListDelete(L,place);if(flag){printf("删除成功！！！\n");PrintList(L);}}//查找功能函数 调用LocateElem查找元素void Search(SqList L){ElemType e;int flag;printf("请输入要查找的值：");scanf("%d",&e);flag=LocateElem(L,e);if(flag){printf("该元素位置为：%d\n",flag);}else{printf("未找到该元素！\n");}}//菜单void menu(){printf("********1.创建 2.插入*********\n");printf("********3.删除 4.查找*********\n");printf("********5.输出 6.退出*********\n");}int main(){SqList L;int choice;InitList(L);//初始化顺序表while(1){menu();printf("请输入菜单序号：\n");scanf("%d",&choice);if(6==choice) break;//退出switch(choice){case 1:Create(L);//创建break;case 2:Insert(L);//插入break;case 3:Delete(L);//删除break;case 4:Search(L);//查找break;case 5:PrintList(L);//输出break;default:printf("输入错误！\n");}}return 0;}
