实现顺序表的各种基本运算的算法（超详细） |
您所在的位置：网站首页 › 长度单位从小到大顺序表 › 实现顺序表的各种基本运算的算法（超详细） |
实现顺序表的各种基本运算的算法（超详细）
|
线性表（List）：零个或多个数据元素的有限序列 线性表的顺序存储结构简称为顺序表（sequential list） 数组大小MaxSize一般定义为一个整型常量。如果估计一个线性表不会超过50个元素，则可以把MaxSize定义为50： #define MaxSize 50 在声明线性表的顺序存储类型时，定义一个data数组来存储线性表中的所有元素，还定义一个整型变量length来存储线性表的实际长度，并采用结构体类型SqList表示如下： typedef struct { ElemType data[MaxSize]; //数组，存储数据元素 int length; //存放顺序表的长度 } SqList; //顺序表的类型注意：线性表元素的逻辑序号是从1开始的，而对应顺序表的data[]数组下标是从0开始的（物理序号)
L=(SqList *)malloc(sizeof(SqList)); 由sizeo分配所需空间大小，malloc开辟(new)sizeof那么大的空间，这是指向SqList的指针，最后把该地址交给了指针L 调用CreateList算法创建好L所指的顺序表后，需要回传给对应的实参，也就是说，L是输出型参数，所有在形参上L的前面需要加上引用符“&” 参考博客 [1].指针 [2].动态内存分配与指向它的指针变量 [3].SqList *&L与SqList *L的区别 Code: #include #include #define MaxSize 50 //存储空间初始分配量 typedef char ElemType; //ElemType类型根据实际情况而定，这里为char typedef struct { ElemType data[MaxSize]; //数组，存储数据元素 int length; //存放顺序表的长度 } SqList; //顺序表的类型 /*建立顺序表CreateList，将数组a中的每个元素依次放入到顺序表中，并将n赋给顺序表的长度 由a中的n个元素建立顺序表*/ void CreateList(SqList *&L,ElemType a[],int n)//形参 { L=(SqList *)malloc(sizeof(SqList)); //相当于new，出来一个sizeof这么大的空间，把它指向SqList这样的一个指针,把地址交给了L for (int i=0;idata[i]=a[i]; L->length=n; //设置L的长度n } //1、初始化线性表InitList，构造一个空的线性表L，只需分配线性表的存储空间并将length域设置为0即可 void InitList(SqList *&L) { L=(SqList *)malloc(sizeof(SqList)); L->length=0; } //2、销毁线性表DestroyList，释放线性表L占用的内存空间 void DestroyList(SqList *&L) { free(L); //释放L所指的顺序表空间 } //3、判断线性表是否为空表ListEmpty， 返回一个布尔值是否为空表。若L为空表，则返回true，否则返回false。 bool ListEmpty(SqList *L) { return(L->length==0); } //4、求线性表的长度ListLength，返回顺序表L的长度，返回length域的值即可 int ListLength(SqList *L) { return(L->length); } //5、输出线性表DispList void DispList(SqList *L) { for (int i=0;ilength;i++) printf("%d ",L->data[i]); printf("\n"); } //6、求线性表中的某个数据元素值GetElem，该运算用引用型参数e返回L中第i（1data[i-1]; //取元素值 return true; //成功找到元素时返回true } //7、按元素值查找LocateELem int LocateElem(SqList *L, ElemType e) { int i=0; while (ilength && L->data[i]!=e)//i在length域里，而且i里面的元素都不等于e i++; if (i>=L->length) //第一种情况，i都不在范围内 return 0; else return i+1; //找到e后，返回其逻辑序号 } //8、插入数据元素ListInsert,就是五个人，有一个人插进来了，往后移，变六个人了， bool ListInsert(SqList *&L,int i,ElemType e) { int j; if (iL->length+1) //在顺序表L第i(1i;j--) //将data[i]及后面元素后移一个位置 L->data[j]=L->data[j-1]; //如果线性表长度(1开始)大于数组长度(0开始) L->data[i]=e; //插入元素e L->length++; //顺序表长度增1 return true; //成功插入返回true } /* i=4,表示是第4个元素,但是数组里面是data[3],所以i-- j=5,j>i,原来data[4]是第五个元素'e', 顺序表长度增1,data[5]=e为第六个元素最后一个元素，以此类推。 */ //9、删除数据元素ListDelete bool ListDelete(SqList *&L,int i,ElemType &e) { int j; if (iL->length) //(1data[2] for (j=i;jlength-1;j++) //j=2;jdata[j]=L->data[j+1]; //2=3 e=f L->length--; //顺序表长度减1 return true; } int main(){ SqList *L; //定义一个指向SqList的地址，要不然地址怎么过来 InitList(L); // printf("%d",L->length); //测试 ElemType e; printf("顺序表的基本运算如下:\n"); printf("1.初始化顺序表L\n"); InitList(L); printf("2.依次采用尾插法插入a,b,c,d,e元素\n"); ListInsert(L,1,'a'); ListInsert(L,2,'b'); ListInsert(L,3,'c'); ListInsert(L,4,'d'); ListInsert(L,5,'e'); printf("3.输出顺序表:"); DispList(L); printf("4.顺序表L长度=%d\n",ListLength(L)); printf("5.顺序表L为%s\n",(ListEmpty(L)?"空":"非空")); GetElem(L,3,e); printf("6.顺序表L的第3个元素=%c\n",e); printf("7.元素a的位置=%d\n",LocateElem(L,'a')); printf("8.在第4个元素位置上插入f元素\n"); ListInsert(L,4,'f'); printf("9.输出顺序表L:"); DispList(L); printf("10.删除L的第3个元素\n"); ListDelete(L,3,e); printf("11.输出顺序表L:"); DispList(L); printf("12.释放顺序表L\n"); DestroyList(L); return 0; }result： |
定义方式为：SqList *L 采用顺序表指针，主要是为了方便顺序表的释放算法设计，并且在函数之间传递顺序表指针时会节省为形参分配的空间。
【本文地址】
今日新闻 |
推荐新闻 |