静态分配只需在内存中开辟一个数组空间,数组空间的大小固定,不能更改;而动态分配需要使用malloc函数,在内存中随机开辟一块地址,如需要增加线性表的空间,只需重新再开辟一块空间,然后把原来的使用的线性表空间用free函数把它释放出来。下面是静态和动态分配实现线性表的创建过程。
#include<stdlib.h> #include<stdio.h> //顺序表静态分配 #define Maxsize 100 //表空间的最大长度 typedef struct{ int data[Maxsize]; int length; //当前顺序表内数据的长度 }SqList; //顺序表的类型定义(静态分配) //初始化线性表 void InitList(SqList &L){ for(int i=0;i<Maxsize;i++) L.data[i]=0; //将所有数据元素设置为默认值 L.length=0; //顺序表初始长度为0 } //在顺序表中插入数据 void ListIn(SqList &L,int n) { printf("输入你想插入的数字:\n"); int x; for(int i=0;i<n;i++){ scanf("%d",&x); L.data[i]=x; L.length++; } } //顺序表的指定位置插入 bool ListInsert(SqList &L,int i,int e){ if(i<1||i>L.length+1) //判断i的范围是否有效 return false; if(L.length>=Maxsize) //判断存储空间已满,不能插入 return false; for(int j=L.length;j>=i;j--) //将要插入位置的元素及其后面的元素往后移 L.data[j]=L.data[j-1]; L.data[i-1]=e; //在指定位置放入插入的元素 L.length++; //顺序表现有数据长度加一 return true; } bool ListDelete(SqList &L,int i,int &e){ //传输的是引用型e,在内存中处理的是同一份数据 if(i<1||i>L.length+1) //判断i的范围是否有效 return false; e=L.data[i-1]; //将被删除的元素赋值给e for(int j=i;j<L.length;j++) //将第i个位置后的元素前移 L.data[j-1]=L.data[j]; L.length--; //将顺序表现有数据长度减一 return true; } //按位查找顺序表内的数据元素的值 int GetElem(SqList L,int i){ return L.data[i-1]; //数组元素下标是从0开始所以查找位置得减一 } //在顺序表中查找元素,返回它的位置 int LocateElem(SqList L,int e){ for(int i=0;i<L.length;i++) if(L.data[i]==e) return i+1; //数组元素下标从0开始,返回的位置得加一 return 0; //退出循环,说明查找失败 } //打印顺序表 void PrintList(SqList L) { printf("您的顺序表为:\n"); for(int i = 0; i < L.length; i++) { printf("%d ", L.data[i]); } printf("\n"); } int main(){ SqList L; //申明一个顺序表 InitList(L); //初始化顺序表 int n; printf("输入你要插入的数据位数:\n"); scanf("%d",&n); ListIn(L,n); printf("%d",L.length); PrintList(L); ListInsert(L,3,100); //已给定初值,如果需要可自行修改 PrintList(L); printf("第2位的元素的值为%d\n",GetElem(L,2)); //查找顺序表内第2位元素的值 printf("元素1的位置是%d\n",LocateElem(L,1)); //查找顺序表内元素1的位置 int e=-1; //用变量e把删除的元素“带回来” if(ListDelete(L,3,e)) printf("已删除第3个元素,删除元素值为=%d\n",e); else printf("位序i不合法,删除失效\n"); PrintList(L); return 0; }
#include<stdio.h> #include<stdlib.h> //顺序表动态分配 #define InitSize 10 //顺序表的初始长度 typedef struct{ int *data; //动态分配数组的指针,指向顺序表的表头,进行后续操作需要使用,E int MaxSize; //顺序表的最大容量(可用malloc动态分配地址进行最大容量的扩充) int length; //顺序表当前的长度 }SeqList; //顺序表的类型定义(动态分配方式) //key讲解: malloc函数的作用用于动态申请内存空间;free函数的作用用于动态释放内存空间 //初始化线性表 void InitList(SeqList &L){ //用malloc函数申请一片连续的存储空间 L.data=(int *)malloc(InitSize*sizeof(int)); //开辟的空间一个字节占4B,需要开辟10*4B的空间(不同编译环境下,int所占的空间不同) L.length=0; //开辟的空间中还未存入数据,所以当前长度为0 L.MaxSize=InitSize; //当前的空间还未扩容,所以顺序表的最大容量为初始长度 } //增加动态数组的长度 void IncreaseSize(SeqList &L,int len){ int *p=L.data; //把data指针的值赋值给指针p(说明p指针和data指针指向同一个位置) L.data=(int *)malloc((L.MaxSize+len)*sizeof(int)); //重新申请一片大的内存空间,此时的data指针指向新的空间的首地址 for(int i=0;i<L.length;i++){ L.data[i]=p[i]; //将数据复制到新开辟的扩容新区域 } L.MaxSize=L.MaxSize+len; //顺序表最大长度增加len free(p); //释放原来的内存空间 } //在顺序表中插入数据 void ListIn(SeqList &L,int n) { printf("输入你想插入的数字:\n"); int x; for(int i=0;i<n;i++){ scanf("%d",&x); L.data[i]=x; L.length++; } } //顺序表的指定位置插入 void ListInsert(SeqList &L,int i,int e){ for(int j=L.length;j>=i;j--) //将要插入位置的元素及其后面的元素往后移 L.data[j]=L.data[j-1]; L.data[i-1]=e; //在指定位置放入插入的元素 L.length++; //顺序表现有数据长度加一 } //按位查找顺序表内的数据元素的值 int GetElem(SeqList L,int i){ return L.data[i-1]; //数组元素下标是从0开始所以查找位置得减一 } //在顺序表中查找元素,返回它的位置 int LocateElem(SeqList L,int e){ for(int i=0;i<L.length;i++) if(L.data[i]==e) return i+1; //数组元素下标从0开始,返回的位置得加一 return 0; //退出循环,说明查找失败 } bool ListDelete(SeqList &L,int i,int &e){ //传输的是引用型e,在内存中处理的是同一份数据 if(i<1||i>L.length+1) //判断i的范围是否有效 return false; e=L.data[i-1]; //将被删除的元素赋值给e for(int j=i;j<L.length;j++) //将第i个位置后的元素前移 L.data[j-1]=L.data[j]; L.length--; //将顺序表现有数据长度减一 return true; } //打印顺序表 void PrintList(SeqList L) { printf("您的顺序表为:\n"); for(int i = 0; i < L.length; i++) { printf("%d ", L.data[i]); } printf("\n"); } int main(){ SeqList L; //申明一个顺序表 InitList(L); //初始化顺序表 IncreaseSize(L,5); //动态给顺序表扩容 int n; printf("输入你要插入的数据位数:\n"); scanf("%d",&n); ListIn(L,n); printf("%d",L.length); PrintList(L); ListInsert(L,3,100); //已给定初值,如果需要可自行修改 PrintList(L); printf("第2位的元素的值为%d\n",GetElem(L,2)); //查找顺序表内第2位元素的值 printf("元素1的位置是%d\n",LocateElem(L,1)); //查找顺序表内元素1的位置 int e=-1; //用变量e把删除的元素“带回来” if(ListDelete(L,3,e)) printf("已删除第3个元素,删除元素值为=%d\n",e); else printf("位序i不合法,删除失效\n"); PrintList(L); return 0; }