线性表的顺序表示
线性表的特点 是：表的物理结构是顺序的，元素的 存储也是有顺序的。
要学会使用C语言描述和具体实现顺序表定义和操作的相关算法。
//--------顺序表的存储结构---- #define MAX 100 //顺序表可能达到的最大长度 typedef struct Sq{ Elemtype *elem; //存储空间的基地址 int length; //当前长度 }sqlist; /* <span style="color:#ff0000;">Elemtype是一个抽象数据类型,可以是int,float,double等或者是自定义的数据类型。 在实际使用是可以使用int,float等来代替； </span> */
/* 顺序表的初始化： 1.为顺序表动态分配一个预定义大小的数组空间，使用elem指向这段空间的基地址。 2.将表的当前长度设为0. */ //描述： Status Initsqlist_Sq(sqlist &L){ <span style="color:#ff0000;">//Status英文意思是：地位,状态 </span> //构造一个空的顺序表L L.elem=new Elemtype[MAX]; //为顺序表分配一个MAX大小的数组空间 if(!L.elem) exit(OVERFLOW); //存储分配失败 L.length=0; //空表长度为0 return OK; }
//顺序表的查找 /* 在表L中查找与指定值e相等的元素 遍历顺序表， 将表中的元素与e表示，若L.elem[i]==e,则返回该元素的“位序”i+1 查找失败返回0 */ int LocationElem_Sq(sqlist L,Elemtype e){ for(int i=0;i<L.length;i++){ if(L.elem[i]==e){ return i+1; } } return 0; }
//顺序表的插入 Status ListInsert(sqlist &L,int i,Elemtype e){ //在顺序表L中的第i个位置之前插入新的元素e //i的合法范围是1<=i<=L.length+1 if(i<1||i>L.length+1) return ERROR; //i值不合法 if(L.length==MAX) return ERROR; //当前存储已满 for(int j=L.length-1;j>=i-1;j--){ L.elem[j+1]=L.elem[j]; //插入位置之后的元素后移 } L.elem[i-1]=e;//将新元素插入第i个位置 ++L.length;//表长加1 return OK; }
//顺序表的删除 Status Deletesqlist(sqlist &L,Elemtype e){ //在顺序表中删除第i个元素，并用e返回其值 //i的合法范围1<=i<=L.length if(i<1||i>L.length) return ERROR;//i值不合法 e=L.elem[i-1]; for(int j=i;j<=L.length-1;j++){ L.elem[j-1]=L.elem[j];//被删除元素之后的元素后移 } --L.length;//表长减1 return OK; }
具体实现如下：
#include<stdio.h> #define MAX 100 typedef struct Sq{ int *elem; int length; }sqlist; /* 初始化表 */ int Initsqlist(sqlist &L){ L.elem=new int[MAX]; if(!L.elem){ return 0; }else{ L.length=0; return 1; } } /* 判断表是否为空 */ int ListEmpty(sqlist L){ if(L.length!=0){//表存在且表长不为0，返回非空 return 1; }else if(L.length==0){ return 0;//表为空 } } /* 计算表长 */ int ListLength(sqlist L){ return L.length; } /* 输入操作 */ void Input(sqlist &L){//第一次写L前没加&,出错，待思考？？？ int e; int Loop=1; printf("请输入表的元素值(输入0结束):\n"); int i=0; while(Loop){ //int i=0; scanf("%d",&e); if(e!=0){ L.elem[i++]=e; L.length=i; }else{ Loop=0; } } printf("输入结束!\n"); } /* 输出线性表中的所有值 */ void Output(sqlist L){ printf("顺序表中的元素值为:\n"); for(int i=0;i<L.length-1;i++){ printf("%d ",L.elem[i]); } printf("%d\n",L.elem[L.length-1]); } /* 查询 */ /* 1.查询指定位置的元素的值 */ void SelectByNo(sqlist &L,int location){ //首先判断表是否为空 if(location<=0||location>L.length){ printf("输入错误!\n"); }else if(!ListEmpty(L)){ printf("表为空，查找失败!\n"); }else{ printf("待查找元素的值:%d\n",L.elem[location-1]); } } /* 2.查询某个元素在表中的位置 */ void SelectByValue(sqlist L,int value){ //首先判断表是否为空 if(!ListEmpty(L)){ printf("表为空!\n"); }else{ for(int i=0;i<L.length;i++){ if(L.elem[i]==value){ printf("%d在表中的位置:%d\n",value,i+1); } } } } /* 查找某个值的前驱 */ void PriorElem(sqlist L,int value){ //遍历表，判断value是否是表的元素 //且表的最后一个元素是否==value,表的最后一个元素没有前驱 int count=0; for(int i=0;i<L.length;i++){ if(L.elem[i]==value){ count++; if(L.elem[0]==value){ printf("%d是表的第一个元素，没有前驱.\n",value); }else{ printf("%d的前驱是:%d\n",L.elem[i-1]); } } } if(count==0){ printf("%d不是表中的元素!\n",value); } } /* 查找某个值的后继 */ void NextElem(sqlist L,int value){ //遍历表，判断vale是否是表中的元素 //且是否是表的第一个元素，第一个元素没有后继 int count=0; for(int i=0;i<L.length;i++){ if(L.elem[i]==value){ count++; if(L.elem[L.length-1]==value){ printf("%d是表的最后一个元素，没有后继.\n",value); }else{ printf("%d的后继是:%d\n",L.elem[i+1]); } } } if(count==0){ printf("%d不是表中的元素.\n",value); } } /* 插入操作 在L中第i个位置之前插入元素value 插入后，表长加1，第i及以后的元素位置向后移动1个 */ void ListInsert(sqlist &L,int location,int value){ //首先判断location的位置是否合法 if(location<1||location>L.length+1){ printf("插入位置不合法!\n"); }else{ for(int i=L.length-1;i>=location-1;i--){ L.elem[i+1]=L.elem[i]; } L.elem[location-1]=value; ++L.length; printf("插入成功!\n"); } } /* 删除操作 删除指定位置的元素，表长减1 location及其后的元素的位置向前移动1个 */ void ListDelete(sqlist &L,int location){ //首先判断location是否合法 if(location<1||location>=L.length+1){ printf("要删除的元素不存在!\n"); } else{ printf("要删除的元素的值是:%d\n",L.elem[location-1]); for(int i=location;i<=L.length-1;i++){ L.elem[i-1]=L.elem[i]; } --L.length; printf("删除成功!\n"); } } int main(){ sqlist L; //Initsqlist(L); printf("顺序表的实现和操作:\n"); printf("1.建立顺序表\n"); printf("2.输入表的元素\n"); printf("3.输出表的元素\n"); printf("4.插入操作\n"); printf("5.删除操作\n"); printf("6.查询\n"); printf("0.退出\n"); int choose=-1; while(choose!=0){ printf("请选择:\n"); scanf("%d",&choose); switch(choose){ case 1: if(Initsqlist(L)){ printf("顺序表初始化成功!\n"); }else{ printf("初始化失败!"); } break; case 2: Input(L); break; case 3: Output(L); break; case 4: int location,value; printf("请输入插入的位置和插入元素的数值:\n"); scanf("%d %d",&location,&value); ListInsert(L,location,value); printf("插入后的表是:\n"); Output(L); break; case 5: printf("请输入要删除的元素在表中的位置:\n"); int location1; scanf("%d",&location1); ListDelete(L,location1); printf("删除后的表为:\n"); Output(L); break; case 6: printf("1.查找指定元素的前驱\n"); printf("2.查找指定元素的后继\n"); printf("3.按序号查询某个元素的值\n"); printf("4.按值查询某个元素的位置\n"); printf("请选择:\n"); int choose; scanf("%d",&choose); switch(choose){ case 1: int value; printf("请输入元素值:\n"); scanf("%d",&value); PriorElem(L,value); break; case 2: int value1; printf("请输入元素的值:\n"); scanf("%d",&value1); NextElem(L,value1); break; case 3: printf("输入要查询元素的序号:\n"); int location; scanf("%d",&location); SelectByNo(L,location); break; case 4: printf("输入要查询元素的值:\n"); int value2; scanf("%d",&value2); SelectByValue(L,value2); break; } break; case 0: printf("退出成功!\n"); break; } } return 0; }
