线性表的实现问题
- C/C++ code
//C++实验线性表的顺序表示；#include<iostream>#include<string>using namespace std;typedef int Elem;//首先定义一个表的结构struct List{ Elem *list; int lenth; int maxsize;};//1.初始化线性表，及创建一个空表void InitList(List &L,int max){ if(max<=0){cout<<"输入maxsize非法！"<<endl;exit(1);} L.list=0; L.lenth=0; L.maxsize=max; L.list=(Elem *)malloc(L.maxsize*sizeof(Elem));//初始化内存 if(!L.list){cout<<"存储分配失败！"; exit(1);}}//1.11创始一个表，并记录数据！////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////2.定义一个函数扩展存储容量void InitList_List(List &L){ L.list=(Elem *)malloc((100+L.maxsize)*sizeof(Elem)); if(!L.list){cout<<"增加扩展失败！"; exit(1);} L.maxsize=100+L.maxsize;}//3.清除线性表L中的所有元素，释放存储空间，使之成为一个空表void ClearList(List &L){ if(L.list!=NULL) { free(L.list);//释放所分配的内存 L.list=0; L.lenth=0; L.maxsize=0; }}//4.返回线性表L当前的长度，若L为空则返回０ */int sizeList(List &L){ return L.lenth;}// 4.判断线性表L是否为空，若为空则返回1, 否则返回0 int emptyList(List &L){ return L.lenth<=0;}//5.返回线性表L中第pos个元素的值，若pos超出范围，则停止程序运行 Elem getElem(List &L, int pos){ if(pos < 1 || pos > L.lenth){ //若pos越界则退出运行 cout<<"元素序号越界！ "; exit(1); } return L.list[pos-1]; // 返回线性表中序号为pos值的元素值 }//6.顺序扫描（即遍历）输出线性表L中的每个元素 void ShowList(List &L){ int i; for(i=0; i<L.lenth; i++){ cout<<L.list[i]<<" "; } cout<<endl; //return;}// 7.从线性表L中查找值与x相等的元素，若查找成功则返回其位置，否则返回-1 int findList(List &L, Elem x){ int i; for(i=0; i<L.lenth; i++) { if(L.list[i]==x){ return i; } } return -1;}//8.把线性表L中第pos个元素的值修改为x的值，若修改成功返回1，否则返回0int updatePosList(List &L, int pos, Elem x){ if(pos<1||pos>L.lenth){ //若pos越界则修改失败 return 0; } L.list[pos-1]=x; return 1;}//9.向线性表L的表头插入元素x void insertFirstList(List &L, Elem x){ int i; if(L.lenth== L.maxsize){ InitList_List(L); } for(i=L.lenth-1; i>=0; i--){ L.list[i+1]=L.list[i]; } L.list[0]=x; L.lenth++; return;}//10.向线性表L的表尾插入元素x void insertLastList(List &L, Elem x){ if(L.lenth ==L.maxsize){ //重新分配更大的存储空间 InitList_List(L); cout<<"进行了空间扩展(增加100个长度)"<<endl;; } L.list[L.lenth]=x; // 把x插入到表尾 L.lenth++; //线性表的长度增加１ return;}//11.向线性表L中第pos个元素位置插入元素x，若插入成功返回１，否则返回０ int insertPosList(List &L, int pos, Elem x){ int i; if(pos<1||pos>L.lenth+1){ //若pos越界则插入失败 return 0; } if(L.lenth==L.maxsize){ //重新分配更大的存储空间 InitList_List(L); } for(i=L.lenth-1; i>=pos-1;i--){ L.list[i+1]=L.list[i]; } L.list[pos-1]=x; L.lenth++; return 1;}//12.向有序线性表L中插入元素x, 使得插入后仍然有序void insertOrderList(List &L, Elem x){ int i, j; //若数组空间用完则重新分配更大的存储空间 if(L.lenth==L.maxsize){ InitList_List(L); } //顺序查找出x的插入位置 for(i=0;i<L.lenth; i++){ if(x<L.list[i]){ break; } } // 从表尾到下标i元素依次后移一个位置， 把i的位置空出来 for(j= L.lenth-1; j>=i; j--) L.list[j+1] = L.list[j]; //把x值赋给下标为i的元素 L.list[i] = x; // 线性表长度增加1 L.lenth++; return;}//*13从线性表L中删除表头元素并返回它，若删除失败则停止程序运行Elem deleteFirstList(struct List *L){ Elem temp; int i; if(L->lenth==0) { cout<<"线性表为空，不能进行删除操作"; exit(1); } temp=L->list[0]; for(i=1;i<L->lenth;i++) L->list[i-1]=L->list[i]; L->lenth--; return temp;}//*14.从线性表中删除表尾元素并返回它，基删除失败则停止程序运行！Elem deleteLastList(struct List *L){ if(L->lenth==0) { cout<<"线性表为空，不能进行删除操作！"; exit(1); } L->lenth--; return L->list[L->lenth];}//*15,从线性表L中删除第pos个元素并返回它，若删除失败则停止程序运行。 Elem deletePosList(struct List *L,int pos) { Elem temp; int i; if(pos<1||pos>L->lenth) { cout<<"pos值越界，不能进行删除操作!"; exit(1); } temp=L->list[pos-1]; for(i=pos;i<L->lenth;i++) L->list[i-1]=L->list[i]; L->lenth--; return temp; } //16.从线性表中删除值为X的第一个元素，若成功返回1，失败返回0 int deleteValueList(struct List *L,Elem x) { int i,j; for(i=0;i<L->lenth;i++) { if(L->list[i]==x )break; } if(i==L->lenth)return 0; for(j=i+1;j<L->lenth;j++) { L->list[j-1]=L->list[j]; } L->lenth--; return 1; }int main(){ int a[10]={2,4,6,8,10,12,14,16,18,20}; struct List L; InitList(L,5); int i; for(i=0;i<10;i++) { insertLastList(L,a[i]); } cout<<"线性表的长度为："<<L.lenth<<endl; cout<<"线性表的最大值为："<<L.maxsize<<endl; //ShowList(L); for(i=0;i<10;i++) { cout<<L.list[i]<<endl; } return 0;}
[解决办法]
//扩展改如下
malloc--->realloc
///
- C/C++ code
void InitList_List(List &L){ L.list=(Elem *)realloc(L.list,L.maxsize + 100); if(!L.list){cout<<"failure?"; exit(1);} L.maxsize=100+L.maxsize;}