#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> /* * 2.1 线性表:零个或多个数据元素的有限序列 特点:数据元素有序的 数据元素是一对一的关系 数据元素个数是有限的 注意:数据元素的个数为0是空表 线性表有哪些常见操作? 创建和初始化 查找 插入 删除 清空(增删改查) ADT 线性表(SequenceList) Data 1.线性表的数据元素是一个集合{a_1....a_n},数据元素的类型DataType 2.除了第一个元素a_1无直接前驱元素外,每一个元素有且仅有一个直接的前驱元素 3.后继最后一个元素a_n外,每一个元素有且仅有一个直接的后继元素 4。每个数据元素之间的关系是一一对应的关系 Operation 初始化线性表,创建一个空的线性表List InitList(*List) 插入 在线性表List的index下标处插入元素elem InsertElement(*List,index,elem) 删除 删除线性表List表中第i个元素,并返回删除元素的指针e DeleteElement(*List,index,*elem) 长度 GetLength(*List) 线性表是否为空 IsEmpty(*List) 查找 给了下标返回数据 ClearList(*List,index,*elem) endADT *2.2 线性表的顺序存储结构,指的是用一段地址连续的存储单元一次存储线性表的数据元素{数组} 程序实现: 1.我们需要定义线性表的最大空间 #define MAX_SIZE 255 2.线性表里需要有统一类型的元素集合 typedef int ElementType; typedef struct{ int id; char *name; }ElementType; 3.定义顺序结构 typedef struct{ ElementType datas[MAX_SIZE]; int length; }Sqlist; 描述线性表的顺序存储结构的三个要素 存储空间的起始位置:数组datas的存储位置 线性表的最大存储容量:数组的长度MAX_SIZE 线性表的当前长度:length 地址的计算方法: 第n个数据元素的内存地址=数组的内存地址+第n个元素的下标n-1 <=>datas+i 访问元素*(datas+n-1); postion 位置,从1开始 index 下标,从0开始 2.3 */ #define MAX_SIZE 255 //typedef int ElementType; typedef struct { int id; char * name; }ElementType; typedef struct { ElementType datas[MAX_SIZE]; int length; }SeqList; /** *初始化顺序表 * seqlist 要初始化的是顺序表 * elemArray 初始化要添加的元素内存数组 * length 初始化要添加的元素个数 */ int test(); int InsertElement(SeqList* seqlist, int index, ElementType element); int InitList(SeqList* seqlist, ElementType* elemArray, int length); int InitList(SeqList* seqlist, ElementType * elemArray, int length) { if (length > MAX_SIZE) { printf("越界,超出数组的最大容量,初始化失败\n"); return 0; } seqlist->length = 0;//初始化之前顺序表长度置0 int m; for ( m = 0; m < length - 1; m++)//每次循环都在下标i处插入数据 { InsertElement(seqlist, m, elemArray[m]); } printf("初始化成功\n"); } //实现任意位置添加 /*像顺序表中的index下标处插入元素 *seqlist 要插入的是顺序表 * index 要插入的下标 * element 要插入的元素 */ /* 假设在第i个位置插入一个元素 *下标i以及i以后的所有数据元素后移 注意:除非i=n+1,否则必须移动数据元素的位置来适应逻辑结构的改变 *下标i的位置放入数据元素a 注意: 1.数据元素后的顺序表长度为n+1 2.插入元素后,最后一个元素的下标变为n 3.c语言数组实现规则,顺序表续航都不能超过它的最大长度 */ int InsertElement(SeqList * seqlist, int index, ElementType element) { /*插入算法的举例解释 index=2插入888//index:下标 从length-1开始,到index,前面一个元素赋值给后面一个元素将插入的元素赋值给下标为index的元素 45,89,90,111,112 45,89,888,90,111,112 */ /*算法描述*/ //1.插入后的元素空间是否超过最大空间MAX_SIZE //2.index的值是否合法(0,MAX_SIZE-1) //3.插入的index应该在length之内 //4.从length-1开始复制到length元素 if (seqlist->length + 1 >= MAX_SIZE)//length顺序表的长度是从1开始的 { printf("无法插入,空间不足,数组已经满了\n"); return 0; } if (index<0 || index>MAX_SIZE - 1) { printf("要插入的位置不合法\n"); printf("只能插入允许的下标内的范围%d这样大\n", MAX_SIZE - 1); return 0; } for (int j = seqlist->length; j >= index; j--)//seqlist->length是已经加1的数组最后一个元素 seqlist->datas[j] = seqlist->datas[j - 1]; seqlist->datas[index] = element;//将元素element插入到index位置 seqlist->length + 1; //表长加1 return 0; } int printlist(SeqList* seqlist) { for (int i = 0; i < seqlist->length; i++) { printf("%d \t %s \n", seqlist->datas[i].id, seqlist->datas[i].name); } return 0; } ElementType elemArray[] = { { 1,},{2,}, {3,}}; int main() { SeqList seqlist; // InitList(&seqlist,elemArray,3); InitList(&seqlist,elemArray,sizeof(elemArray)/sizeof(elemArray[0])); printlist(&seqlist); return 0; } |