数据结构线性表的实现

#include <bits/stdc++.h> using namespace std; #define LIST_INIT_SIZE 100//线性表存储空间初始分配量 #define LISTINCREMENT 10 //增量 #define OK 1 #define ERROR -1 //定义线性表 typedef int ElemType; typedef struct { ElemType *elem;//存储空间地址 int length;//表长 int listsize;//当前分配的存储容量 }SqList; //编写功能函数 typedef int status; //函数要更改L，就要使用&L，不更改L，就直接用L //初始化 status InitList(SqList &L) { L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//malloc.h if(!L.elem) exit(OVERFLOW); //存储分配失败 L.length=0;//当前表长为0 L.listsize=LIST_INIT_SIZE; return OK; } //销毁 status DestroyList(SqList &L) //思路：让表的长度和初始内存为0即销毁 { free(L.elem);//释放内存 L.elem=NULL;//null空地址 L.length=0; L.listsize=0; return OK; } //清空列表 status ClearList(SqList &L) //思路：长度等于0就行 { L.length=0; return OK; } //判断空表 status ListEmpty(SqList L) //长度为0即为空 { if(L.length==0) return true; else return false; } //求表长 status ListLength(SqList L) { return L.length; } //取元素操作，将顺序表第i个元素赋值给e //e要改变，因此是&e status GetElem(SqList L,int i,ElemType &e) { if((i<1)||(i>L.length)) return ERROR;//判断i是否合法(计数从1开始) e=L.elem[i-1]; return e; } //查找函数 //compare函数：元素判定函数，满足为1否则为0,满足的条件在compare函数里自定 status LocateElem(SqList L,ElemType e,status (*compare)(ElemType,ElemType)){ //在顺序表L中查找第一个 值与e满足compare()的元素位序 int i=1;//位序 ElemType *p=L.elem; while(i<=L.length&&!compare(*p++,e)) ++i; if(i<=L.length)return i; else return 0; } status compare(ElemType c1,ElemType c2){ if(c1==c2*c2)return true; else return false; } //求元素前驱 status PriorElem(SqList L,ElemType cur_e,ElemType &pre_e) //第一个元素没有前驱 ,前驱为该元素前一位的元素 { int i=2,*p=L.elem+1; while(i<=L.length&&*p!=cur_e) { i++; p++; } if(i>L.length) return ERROR; else { pre_e=*(p-1); return OK; } } //求后继 status NextElem(SqList L,ElemType cur_e,ElemType &next_e) { int i=1,*p=L.elem; while(i<L.length&&*p!=cur_e) { i++; p++; } if(i==L.length) return ERROR; else { next_e=*(p+1); return OK; } } //插入 status ListInsert(SqList &L,int i,ElemType e)//在表第i个位置之前插入e，表长加一 { //判断i值是否合法 if(i<1||i>L.length+1) return ERROR; //判断表的内存空间是否足够 if(L.listsize<L.length+1) { ElemType *newbase; newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase)exit(OVERFLOW); // 存储分配失败 L.elem=newbase; L.listsize+=LISTINCREMENT; // 增加存储容量 } //插入操作 ElemType *q,*p; q=&L.elem[i-1];//i-1表示位置，这里和数组类似，从0计数 for (p=&L.elem[L.length-1];q<=p;p--)//移位操作 { *(p+1)=*p; } *q=e;//赋值 L.length++;//表长加一 return OK; } //删除 status ListDelete(SqList &L,int i,ElemType &e)//删除第i个位置的元素，并将删除元素赋给e { if(i<1||i>L.length+1) return ERROR;//判断i值是否合法 ElemType *q,*p; p=&(L.elem[i-1]); e=*p; q=&(L.elem[L.length]); for (;p<q;p++) { *p=*(p+1); } L.length--; return OK; } //输出 void ListTraverse(SqList L) { int i; printf("顺序表遍历："); for(i = 0; i < L.length; i++) { printf("%d ",L.elem[i]) ; } printf("\n"); } //主函数 int main() { int j,k,i; ElemType e,e0; SqList L; printf("初始化前，L.length=%d,L.listsize=%d,L.elem=%u\n",L.length,L.listsize,L.elem); InitList (L); printf("初始化后，L.length=%d,L.listsize=%d,L.elem=%u\n",L.length,L.listsize,L.elem); //想要往线性表里放元素需要插入,此时需注意插入算法里i的含义 for(j=1;j<=5;j++){ ListInsert(L,1,j);//表头插入 } printf("头插法插入结果："); for(j=1;j<=5;j++){ printf("%d ",*(L.elem+j-1)); } printf("\n"); //遍历 ListTraverse(L); //测空,清空 j=ListEmpty(L); printf("清空前，L.length=%d,L.listsize=%d,L.elem=%u\n",L.length,L.listsize,L.elem); printf("j为1为空，j=%d\n",j); ClearList (L); j=ListEmpty(L); printf("清空后，L.length=%d,L.listsize=%d,L.elem=%u\n",L.length,L.listsize,L.elem); printf("j为1为空，j=%d\n",j); //尾插法 for(j=1;j<=10;j++){ ListInsert(L,j,j); } printf("尾插法插入结果："); for(j=1;j<=10;j++){ printf("%d ",*(L.elem+j-1)); } printf("\n插入后，L.length=%d,L.listsize=%d,L.elem=%u\n",L.length,L.listsize,L.elem); //表头插0，增加存储空间 ListInsert(L,1,0); ListTraverse(L); printf("插入后，L.length=%d,L.listsize=%d,L.elem=%u\n",L.length,L.listsize,L.elem); //取元素 printf("第五个元素值为%d\n",GetElem(L,5,e)); //查找 与j^2相等的元素，将其位序赋给k for(j=3;j<=4;j++){ k=LocateElem(L,j,compare); if(k)printf("第%d个元素的值为%d\n",k,j*j); else printf("没有值为%d的元素\n",j*j); } //前驱，测试头两个元素 for(j=1;j<=2;j++){ GetElem(L,j,e0); i=PriorElem(L,e0,e); if(i==ERROR)printf("元素%d无前驱\n",e0); else printf("元素%d的前驱为%d\n",e0,e); } //后继，测试后两个元素 for(j=ListLength(L)-1;j<=ListLength(L);j++){ GetElem(L,j,e0); i=NextElem(L,e0,e); if(i==ERROR)printf("元素%d无后继\n",e0); else printf("元素%d的后继为%d\n",e0,e); } //删除 i=ListDelete(L,5,e); if(i==ERROR)printf("删除第5个元素失败\n"); else printf("删除第5个元素成功，其值为%d\n",e); i=ListDelete(L,12,e); if(i==ERROR)printf("删除第12个元素失败\n"); else printf("删除第12个元素成功，其值为%d\n",e); //遍历 ListTraverse(L); //销毁 DestroyList(L); printf("销毁L后，L.length=%d,L.listsize=%d,L.elem=%u\n",L.length,L.listsize,L.elem); return 0; }

运行结果：

初始化前，L.length=4257081,L.listsize=0,L.elem=1 初始化后，L.length=0,L.listsize=100,L.elem=1793376 头插法插入结果：5 4 3 2 1 顺序表遍历：5 4 3 2 1 清空前，L.length=5,L.listsize=100,L.elem=1793376 j为1为空，j=0 清空后，L.length=0,L.listsize=100,L.elem=1793376 j为1为空，j=1 尾插法插入结果：1 2 3 4 5 6 7 8 9 10 插入后，L.length=10,L.listsize=100,L.elem=1793376 顺序表遍历：0 1 2 3 4 5 6 7 8 9 10 插入后，L.length=11,L.listsize=100,L.elem=1793376 第五个元素值为4 第10个元素的值为9 没有值为16的元素 元素0无前驱 元素1的前驱为0 元素9的后继为10 元素10无后继 删除第5个元素成功，其值为4 删除第12个元素失败 顺序表遍历：0 1 2 3 5 6 7 8 9 10 销毁L后，L.length=0,L.listsize=0,L.elem=0 -------------------------------- Process exited after 0.1572 seconds with return value 0 请按任意键继续. . .