C语言——线性表 (数据结构)

时间:2025-03-14 08:06:58
#include<> #include<> #include<> //函数返回状态代码 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define INFEASIBL E -1 #define OVERFLOW -2 //运用动态分配的顺序存储结构 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef int ElemType; typedef int Status; typedef struct{ ElemType *elem; int length; int listsize;}SqList; Status InitList(SqList &L){ //初始化一个顺序表; L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; }//InitSqList Status ListInsert(SqList &L,int i,ElemType e){ //在第i个元素前插入一个新的元素 if(i<1||i> ++L.length){ return ERROR; } if(L.length==L.listsize){ ElemType*newbase=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) { exit(OVERFLOW); } L.elem=newbase; L.listsize=LIST_INIT_SIZE+LISTINCREMENT;} for (int j=L.length;j>=i;--j) L.elem[j]=L.elem[j-1]; L.elem[i-1]=e; return OK; }//ListInsert Status GetElem(SqList L,int i,ElemType &e){ //返回顺序表中的第i个元素 if(i<1||i>L.length){ return ERROR;} e=L.elem[i-1]; return OK; }//GetElem Status ListDelete(SqList &L,int i,ElemType&e){//删除顺序表中的第i个元素 if(i<1||i>L.length){ return ERROR; } e=L.elem[i-1]; for(i;i<L.length;i++){ L.elem[i-1]=L.elem[i]; } --L .length; return OK; }//ListDelete Status PriorElem(SqList L,ElemType cur_e,ElemType &pre_e){ //返回一个不是首元素的前驱 int i=2; if(cur_e==L.elem[0]) { return ERROR; } while(i<=L.length&&(L.elem[i-1]!=cur_e)){ i++; } if(i==L.length+1){ return ERROR; } else { pre_e=L.elem[i-2]; } return OK; }//PriorElem Status NextElem(SqList L,ElemType cur_e,ElemType &next_e){ //返回一个不是末元素的后继 int i=1; while(i<L.length&&(L.elem[i-1]!=cur_e)){ i++; } if(i==L.length){ return ERROR; } else{ next_e=L.elem[i]; } return OK; }//NextElem Status ListEmpty(SqList L){ return L.length==0; //ListEmpty } //判断顺序表是否为空 Status ListLength(SqList L){ //求顺序表的长度 return L.length; }//ListLength Status DestroyList(SqList &L){ //销毁一个顺序表 if (L.elem){ free(L.elem); } L.elem=NULL; printf("此顺序表已被销毁。"); printf("\n"); return OK; }//DestroyList Status ClearList(SqList &L ){ //清空一个顺序表 L.length=0; return OK; }//ClearList Status ListPrint(SqList &L) { printf("顺序表为:"); if (ListEmpty(L)){ printf("空。\n"); return ERROR;} for (int i=0; i<L .length; ++i){ printf("%-4d ", L.elem[i]);} printf("\n"); return OK;} int main() { SqList L; ElemType a,b,c,d,e,f,pre_e,next_e; int i,j,k,l,m,menu; char p,q,r,s; int is_stop_; InitList(L); is_stop_= FALSE; while (!is_stop_){ printf("\n" " 1.添加元素 2.查看指定位置的元素\n" " 3.删除元素 4.查找元素前驱\n" " 5.查找元素后继 6.检查是否为空\n" " 7.列出所有元素 8.查看列表长度\n" " 9.清空表 \n" " 0.释放列表内存(退出)\n"); printf( "***请选择***:\n"); scanf("%d" ,&menu); switch (menu) { // "1. 添加元素;\n" case 1: printf("请输入你想创建的顺序表中元素的个数:\n"); scanf("%d",&i); if(i<1) printf("您输入的值有误,无法创建顺序表。\n"); else { printf( "请您依次输入您想创建的顺序表的元素:\n"); for(j=1;j<=i;j++){ scanf(" %d",&a); ListInsert(L,L.length+1,a); }} printf("\n"); ListPrint(L); printf("\n"); break; // "2.查看指定位置的元素\n" case 2: printf("请输入您想获取的元素的位序:\n"); scanf("%d" ,&k); if(GetElem(L,k,b)) { printf("\n"); printf( "获得的元素为:%d\n" ,b); } else{ printf("\n"); printf("您输入的值有误,无法获取元素。\n"); } printf("\n"); break; // "3.删除元素\n" case 3: printf("请输入您想删除的元素的位序:\n"); scanf("%d",&l); if(ListDelete(L,l,c)) { printf("删除的元素为:%d\n" ,c); printf("\n"); printf("删除元素后的顺序表为:\n"); ListPrint(L);} else { printf("\n"); printf("您输入的值有误,无法删除元素。\n"); } printf("\n"); break; // "4.查找元素前驱\n" case 4: printf("您想返回那个元素的前驱:\n"); scanf("%d",&d); if(PriorElem(L,d,pre_e)) { printf("\n"); printf( "元素%d的前驱为%d\n'",d,pre_e); } else{ printf("\n"); printf("您输入的值有误,无法返回前驱。\n"); } printf("\n"); break; // "5.查找元素后继\n" case 5: printf("您想返回那个元素的后继:\n"); scanf("%d",&e); if(NextElem(L,e,next_e)){ printf("\n"); printf("元素%d的后继为%d\n",e,next_e); } else{ printf("\n"); printf("您输入的值有误,无法返回后继。\n"); } break; // "6.检查是否为空\n" case 6: if(ListEmpty(L)){ printf("\n"); printf("此顺序表为空。\n"); } else{ printf("\n"); printf("此顺序表不为空。\n"); } printf("\n"); break; // "7.列出所有元素\n" case 7: ListPrint(L); break; //"8.查看列表长度\n" case 8: printf("\n"); printf("此顺序表的长度为:%d\n",ListLength(L)); printf("\n"); break; // " 9.清空表\n" case 9: ClearList(L); printf("\n"); printf( "顺序表已清空。\n"); printf("\n"); break; // "0.释放列表内存\n" case 0: printf("\n"); printf("Bye"); printf("\n"); DestroyList(L); is_stop_ = TRUE; break;} } DestroyList(L);}