第二章线性表
用动态数组实现线性表。
void InitList(SqList &L)；初始化表。构造一个空表。
bool List_input(SqList &L,int n)；键入数据元素，n为你想键入的个数。
void IncreaseSize(SeqList &L,int len)动态增加数组的长度。
bool PrintfList(SqList &L)；输出操作，按先后顺序输出线性表的所有元素。
int Length(SqList L)；求表长。返回L中元素个数
int LocateElem(SqList L,int e)；按值查找操作。e是你想要找的值。
int GetElem(SqList L,int i)；按位查找操作。i为要查找到第i个元素。
bool ListInsert(SqList &L,int i,int e)；插入操作。在L中第i位上插入指定元素e。
bool ListDelete(SqList &L,int i,int &e)；删除操作。删除第i位上的元素，并用e返回被删除元素的值。
#include<stdio.h>
#include<stdlib.h>
#define InitSize 10//默认的长度
typedef struct{
int * data;
int MaxSize;
int length;
}SeqList;
//初始化一个动态数组
void InitList(SeqList &L){
//用malloc函数申请一片连续的存储空间
L.data=(int *)malloc(InitSize*sizeof(int));
L.length=0;
L.MaxSize=InitSize;
}
//动态增加数组的长度
/*重新赋值是因为要申请一片更大的空间，
为什么不紧挨着之前的地方开空间呢?
是因为紧挨的空间可能不够用或者根本没有空间了。*/
void IncreaseSize(SeqList &L,int len){
int * p=L.data;
L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
for(int i=0;i<L.length;i++){
L.data[i]=p[i];
}
L.MaxSize=L.MaxSize+len;
free(p);//把之前的空间给释放掉。
}
//求表长
int Length(SeqList &L){
return L.length;
}
//按值查找
int LocateElem(SeqList L,int e){
for(int i=0;i<L.length;i++){
if(L.data[i]==e)
return i+1;
}
return 0;
}
//按位查找
int GetElem(SeqList &L,int i){
if(i<0||i>L.length) return 0;//如果返回0查找失败
else
return L.data[i-1];
}
//插入操作，在表L中的i位置上插入一个元素e
bool ListInsert(SeqList &L,int i,int e){
if(i<1||i>L.length+1)
return false;
if(L.length>=InitSize)
return false;
for(int j=L.length;j>=i;j--){
L.data[j]=L.data[j-1];
}
L.data[i]=e;
L.length++;
return true;
}
//删除操作
bool ListDelete(SeqList &L,int i,int &e){
if(i<1||i>L.length+1)
return false;
e=L.data[i];
for(int j=i;j<L.length;j++){
L.data[j]=L.data[j+1];
}
L.length--;
return true;
}
//输入数据元素
bool List_input(SeqList &L,int n){
if (n<0 || n>InitSize)
return false;
printf("please input elem data:");
for (int i = 0; i<n; i++)
{
scanf("%d", &L.data[i]);
L.length++;
}
return true;
}
//输出所有数据
bool PrintfList(SeqList &L){
for(int i=0;i<L.length;i++){
printf("第%d个数据是:%d\n",i,L.data[i]);
}
return true;
}
int main(){
SeqList L;
InitList(L);
IncreaseSize(L,5);
List_input(L,8);
printf("表长为%d\n",Length(L));
printf("第5个数据为%d\n",GetElem(L,5));
PrintfList(L);
}
运行结果
