数据结构C语言版--动态顺序表的基本功能实现（二）

"." * 若为：*L（即取地址符加变量）则结构体变量访问结构体成员变量使用"->" * malloc()和free()是C++/C语言的标准库函数， * new()和delete()是C++的运算符它们都可用于申请动态内存和释放内存 * 动态分配内存 */ #include<stdio.h> #include<stdlib.h> typedef int ElemType; #define LIST_INIT_SIZE 5 typedef struct { //结构体 ElemType *elem; int length; int listsize; }SqList; //1.初始化 int InitList_Sq(SqList &L){ //构造一个空的线性表 L.elem=new ElemType[LIST_INIT_SIZE];//申请动态空间 //L.elem = (int *)malloc(LIST_INIT_SIZE * sizeof(int)); if (L.elem==0) //申请动态空间未成功 { printf("failure! "); return 0; } else { //空间申请成功 L.length=0; //初始化表的实际长度为0 L.listsize=LIST_INIT_SIZE; //初始化表的最大长度100 return 1; } } //2.插入表尾 int ListEndInsert_Sq(SqList &L,ElemType e){ int *newbase; //在表尾插入数据 if(L.length==L.listsize) //实际长度等于最大长度 ，空间不足，再做插入 { newbase = (int *)realloc(L.elem,(L.listsize+LIST_INIT_SIZE)*sizeof(int)); //动态分配内存 L.elem = newbase; //内存分配成功之后再次指向 L.listsize+=LIST_INIT_SIZE; } if(!newbase){ printf("overflow! "); //输出溢出 return -1; } L.elem[L.length]=e; //若空间足够，在表尾插入数据 L.length++; //实际长度加一 return 1; } //3.插入i位置 int ListInsert_Sq(SqList &L,int i,ElemType e){ //在动态顺序表L的第i个位置插入元素e ElemType *p,*q; //定义两个指针变量，一个用于指向要插入的数据，一个指向要插入的位置的数据 int *newbase; //用于扩展内存 if (i<=0 || i>L.length+1) //若插入位置不合法 { printf("error! "); //输出错误 return 0; } if(L.length==L.listsize) //实际长度等于最大长度 ，空间不足，再做插入 { newbase = (int *)realloc(L.elem,(L.listsize+LIST_INIT_SIZE)*sizeof(int)); //动态分配内存 L.elem = newbase; //内存分配成功之后再次指向基地址 L.listsize+=LIST_INIT_SIZE; } if(!newbase){ printf("overflow! "); //输出溢出 return -1; } q=&(L.elem[i-1]); //q指针指向要插入的位置 for(p=&(L.elem[L.length-1]);p>=q;--p)//循环从表尾开始，直到q指针所指的位置 { *(p+1)=*p; //利用指针元素依次后移 } *q=e; //把移出的位置插入输入的数据 L.length++; //长度加一 return 1; } //4.输出 void Print_Sq(SqList &L){ //输出动态线性表元素 ElemType *p; for(p = &(L.elem[0]); p <= &(L.elem[L.length-1]); p++)//利用指针从表头开始循环，到表尾结束 { printf("%d ",*p); //输出每个元素的值 } printf(" "); } //5.删除表头 int DelHeadList_Sq(SqList &L){ //删除表头数据元素 ElemType *p; //定义一个指针变量，用于移动元素 if(L.length == 0){ //若为空表则输出UNDERFLOW！ printf("UNDERFLOW!"); return -1; } else { for(p = &(L.elem[1]); p <= &(L.elem[L.length-1]); p++){ //从第二个元素开始，依次向前移一位。 *(p-1) = *p; //后一个元素赋到前一个元素上 } L.length--; //长度减一 return 1; } } //6.删除表尾 int DelEndList_Sq(SqList &L){ if(L.length == 0){ //若为空表 printf("UNDERFLOW!"); //输出溢出 return -1; } else{ L.length--; //表长度减一 return 1; } } //7.删除第i个元素 int DelList_Sq(SqList &L,int i){ ElemType *p; //定义一个指针，用于循环移动表元素 if(i <= 0 || i > L.length){ //若i的位置小于0或大于表长度，输出Error printf("Error!"); return 0; } if(L.length == 0){ //若长度为0输出溢出 printf("UNDERFLOW!"); return -1; }else{ for(p = &(L.elem[i]); p <= &(L.elem[L.length-1]); p++){//循环从指定删除数据的位置开始，依次前移 *(p-1) = *p; //后一个元素覆盖前一个元素 } L.length--; //长度减一 return 1; } } //8.查询 int FindList_Sq(SqList &L, ElemType e){ ElemType *p; int i=0; for(p = &(L.elem[0]); p <= &(L.elem[L.length-1]); p++){ if(*p == e){ //在顺序表L中查找元素e是否存在， return (i+1); //如果存在返回对应的下标i+1 } i++; } return 0; //否则返回0 } //主函数 int main(void){ SqList SSL; //结构体变量，若SSL为指针则访问结构体成员变量需要使用SSL->elem、SSL->length或者(*SSL).elem、(*SSL).length int i,x,m; InitList_Sq(SSL); //初始化线性表 printf("Enter Numbers: "); while(1) //直到你输入9999时才结束输入 { scanf("%d",&x); if(x==9999) break; else { ListEndInsert_Sq(SSL,x);//插入数据 } } printf("The array elems: "); Print_Sq(SSL); //输出表元素 printf("(1).请输入要插入数据的位置i: "); scanf("%d",&i); //输入你要插入的位置 printf("请输入要插入的数据x:"); scanf("%d",&x); //输入你要插入的数据 ListInsert_Sq(SSL,i,x); printf("The new array elems: "); Print_Sq(SSL); //再次输出插入数据后的表 printf("删除表头后： "); DelHeadList_Sq(SSL); //删除表头元素 Print_Sq(SSL); //再次输出删除的后的表 printf("删除表尾后： "); DelEndList_Sq(SSL); //删除表尾元素 Print_Sq(SSL); //再次打印删除删除后的表 printf("(2).请输入要删除数据的位置i："); scanf("%d",&i); DelList_Sq(SSL,i); //删除指定位置的元素 printf("删除指定位置数据后： "); Print_Sq(SSL); //再次打印删除删除后的表 printf("(3).请输入要查询的数据X："); //指定要查询的 数据 scanf("%d",&x); m = FindList_Sq(SSL,x); // 调用查询方法 if(m!=0){ printf("found:位置：%d 数据：%d ",m,x); }else{ printf("no-found:数据：%d ",x); } return 0; }