专做民宿的网站,电子请柬网站开发,小程序wordpress视频,全国文明城市创建标准目录
顺序表的定义
初始化线性表
销毁线性表
求线性表的长度
判断是否为空表
插入数据元素
逻辑序号与物理序号的区别
删除数据元素
输出线性表 按序号求线性表中的元素
按元素值查找
整体上创建顺序表
顺序表实验 线性表的顺序存储是把线性表中的所有元素按照其逻…目录
顺序表的定义
初始化线性表
销毁线性表
求线性表的长度
判断是否为空表
插入数据元素
逻辑序号与物理序号的区别
删除数据元素
输出线性表 按序号求线性表中的元素
按元素值查找
整体上创建顺序表
顺序表实验 线性表的顺序存储是把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的空间。
说直白点就是在内存中找了一块地通过占位的形式把一定的内存空间给占了把你要存的数据元素按照顺序存进这块空间。仔细想想存进一维数组里是不是挺契合的数组下标从0开始存第一数据依次往后存这样就保证了相邻数据元素存在了相邻的位置。
顺序表的定义
#include stdio.h
#define MaxSize 100
typedef char ElemType;
typedef struct
{ElemType data[MaxSize];int length;
}SqList;
typedef struct{ ............} SqList ;是指把结构体类型名struct重命名为SqList,SqList是等价于struct的SqList是类型名
如果没有typedef,直接struct {.......}SqList,那么SqList是结构体变量不是类型名。
开头定义了typedef char ElemType其实就是把char用ElemType表示了ElemType其实就是char。
而#define MaxSize 100等价于MaxSize100
所以ElemType data[MaxSize]其实就是一个大小为100类型为char的数组char data[100]用来存放数据元素
length是这个顺序表已经存了多少元素
初始化线性表
void InitList(Sqlist* L)
{L (SqList*)malloc(sizeof(SqList));L-length 0;
}
用malloc函数给结构体SqList顺序表分配一个空间 以方便给顺序表存元素结构体指针L去接收这片新开辟空间的首地址结构体指针L访问结构体内部成员int length将其初始化为0。为什么顺序表长度length为0呢这个length其实代表的是顺序表已经存了多少个元素此时没有元素所以为0后续增加元素和删除元素操作会改length的值。
这个SqList *L其实是结构体指针SqList *L为什么会写得这么奇怪呢SqList* L这个不是取地址的意思而是引用的意思。c语言里传值传参形参的改变不会影响实参通过引用可以在函数内部修改指针L所指向的结构体而不是仅仅修改指针本身的值。但是需要注意的是c语言没有引用引用是c里面的所以有些纯c语言编译器可能会报错。
同样纯c语言编译器中可以通过用二级指针SqList **L接收L这个指针变量的地址这时也可以在函数内部修改指针L所指向的结构体。
销毁线性表
在上面操作中可以知道malloc分配了空间给线性表存元素用指针L去接收现在要销毁线性表怎么操作。直接把这一片空间全部销毁就行了free(L)意思就是释放了L所指向的空间。
void DestroyList(SqList* L)
{free(L);
}//销毁顺序表
求线性表的长度 结构体SqList里成员length记录的就是线性表的长度直接输出就可以了
void lengtht(SqList*L)
{return L-length;
}
判断是否为空表
依旧要用到lengthlength代表的是顺序表已经存了多少个元素增加元素和删除元素操作会改length的值。 删除就是length--增加就是length。如果为空表要么就是一个也没插进去此时保持初始化length0;要么就是全删完了length--一直到length为0。
所以直接判断length是不是等于0就行
bool ListEmpty(SqList* L)
{if (L-length 0){return 0;}elsereturn 1;
}
其实也可以直接写成这样
bool ListEmpty(SqList* L)
{return (L-length0);
} 返回的是布尔bool值如果为真返回0如果为假返回1。不支持c99标准的c语言编译器使用bool函数会报错。
插入数据元素
逻辑序号与物理序号的区别
我们日常生活中数数都是从1开始的比如排队买东西排在首尾的就是第1位。而数组是从0开始的排在首位的是第0位而不是第1位。
bool ListInsert(SqList* L, int i, ElemType e)
{if (i1 || iL-length 1 || L-length MaxSize)return false;i--;for (int j L-length; j i; j--)L-data[j] L-data[j - 1];L-data[i] e;L-length;return true;
} bool ListInsert(SqList* L, int i, ElemType e) 是指在第i个位置上插入元素e这个i要注意是逻辑序号对应数组0
1.首先要考虑这个位置是不是合适它可以在第一个位置上插进去也可以在最后的位置插进去也就是length1的位置
2.所以合理的范围应该是1ilength1,同时也应该注意存数据是往数组data[MaxSize]里存数组是定长MaxSize大小的超过MaxSize就越界了
写成代码就是这样了 if (i1 || iL-length 1 || L-length MaxSize) return false;
如果在这个范围内那应该怎么存呢举个例子现在有个一个长队买东西王二李明张三李四王五我要插队插在李明后面张三前面该怎么办。张三李四王五挨个往后退就能空出个位置让我插了
i--是将逻辑序号转变为了物理序号毕竟是要存到数组里所以还是用数组下标的物理序号好一点
for (int j L-length; j i; j--) L-data[j] L-data[j - 1];
王二李明张三李四王五 这五个人对应的数组下标为01234
从后往前挪动此时L-length5 L-data[5]L-data[4]这就是把王五往后面挪了一个位置从数组下标为4的位置放到下标为5的位置。
重复上述操作数组下标为2的地方就空出来了L-data[i] e;把值写进去然后length加1就行 L-length;
length是指数组里现在存了多少个元素
这是在中间插的如果是在开头开始插那么后面所有的都得往后挪也是适用于这个循环的要挪动后面n个元素此时是最坏的情况
如果是在最后一个位置插元素那么就直接L-data[i] e; Llength;
删除数据元素
bool ListDelete(SqList* L, int i)
{if (i1 || iL-length || L-length MaxSize){return false;}for (int j i; j L-length; j){L-data[j] L-data[j1];}L-length--;return true;
}
删除数据元素与插入数据元素类似都是不能超过1ilength1这个范围
所以i1 || iL-length || L-length MaxSize过了这个范围直接返回false就行
怎么做到删除呢其实就是把后项的数据直接覆盖前一项的数据然后把length减1就行而不是释放i这个位置的空间。for (int j i; j L-length; j) { L-data[j] L-data[j1]; } L-length--;
从i开始用i后面的数据覆盖i这个位置的数据
有些书上可能会把代码写成这样
bool ListDelete(SqList* L, int i, ElemType e)
{if (i1 || iL-length || L-length MaxSize)return false;i--;e L-data[i];for (int j i; jL-length; j){L-data[j - 1] L-data[j];}L-length--;return true;
}
为什么要用e去保存要删除的值呢使用e来记录删除的元素值的原因是为了给调用者提供该元素的值。在某些情况下当从顺序表中删除一个元素时可能会需要知道该元素的值例如在需要检查被删除元素是否满足特定条件的情况下。通过将删除的元素值赋给e函数调用者可以获得该值并进行进一步的处理或使用
如果你用不到的话用上一个代码也行不过考试还是用下面那个完整的代码
输出线性表
void DispList(SqList* L)
{if (ListEmpty(L))return;for (int i 0; i L-length; i){printf(%c, L-data[i]);printf(\n);}
}
先判断是不是空如果是空就return空剩下的就是打印数组的值这就不加多赘述了 按序号求线性表中的元素
bool GetElem(SqList* L, int i, ElemType e)
{if (i1 || iL-length)return false;e L-data[i - 1];return true;
}
就是直接通过下标去访问数组得到这个下标对应的值
bool GetElem(SqList* L, int i, ElemType e) 意思是去找数组里第i个元素的值并把值用e去接收。第i个元素对应的是逻辑序号物理序号从0开始要转变为数组下标的物理序号需要减1
按元素值查找
int LocateElem(SqList* L, ElemType e)
{ int i 0;while(i L-length L-data[i] ! e)i;if (i L-length)return 0;elsereturn i 1;
} while(i L-length L-data[i] ! e) i;
退出循环有两种条件要么iL-length,意思是查找到表末尾都没有L-data[i]e那么就返回0
要么退出循环就只是因为找到值了因为此时是数组物理下标但是一般要返回逻辑序号所以要加1。
整体上创建顺序表
void CreateList(SqList* L, ElemType a[], int n)
{int i 0; int k 0;L (SqList*)malloc(sizeof(SqList));while (in){L-data[k] a[i];i; k;}L-length k;
}
实质上就是把要存的元素事先先放进一个数组里然后把这个数组整体存进data[MaxSize]数组中也就是从一个数组存到另一个数组
初始化两个整数变量i和k都为0。这两个变量将用于遍历数组和顺序表。使用malloc函数为顺序表分配内存。sizeof(SqList)返回顺序表结构的大小确保足够的空间用于存储数据。使用while循环遍历数组的前n个元素。循环条件是索引i小于n在循环内部将数组元素a[i]赋值给顺序表的当前位置L-data[k]。增加索引i和k的值以便在下一次迭代中处理下一个数组元素和顺序表位置。将顺序表的长度设置为已复制的元素数量即变量k的值 你也可以不用这个直接用ListInsert,把需要的元素一个一个地插进去
顺序表实验
如果你不知道对应的main函数里写什么可以参考我之前写的实验
http://t.csdnimg.cn/leA25
