宁波网站建站,医院网站开发,哪家建公司网站,wordpress 论坛模板语言#xff1a;C语言软件#xff1a;Visual Studio 2022笔记书籍#xff1a;数据结构——用C语言描述如有错误#xff0c;感谢指正。若有侵权请联系博主
一、线性表的逻辑结构
线性表是n个类型相同的数据元素的有限序列#xff0c;对n0#xff0c;除第一元素无直接…语言C语言软件Visual Studio 2022笔记书籍数据结构——用C语言描述如有错误感谢指正。若有侵权请联系博主
一、线性表的逻辑结构
线性表是n个类型相同的数据元素的有限序列对n0除第一元素无直接前驱、最后一个元素无直接后继外其余的每个元素只有一个直接前驱和一个直接后继。 线性表逻辑结构 线性表的特点
同一性。线性表由同类数据元素组成每一个aⁱ必须属于同一数据类型。有穷性。线性表由有限个数据组成表长度就是表中数据元素的个数。 有序性。线性表中相邻数据元素之间存在着序偶关系aⁱaⁱ1
由此可以看出线性表既是一种最简单的数据结构数据元素之间由前驱/后继直观、有序的关系确定又是一种常见的数据结构矩阵、数组、字符串、堆栈、队列等都符合线性条件。
二、线性表的抽象数据定义
线性表的抽象数据类型定义如下
ADT LinearList{数据对象D{aⁱ|aⁱ∈D₀,i1,2,...,n,n≥0,D₀为某一数据对象}结构关系R{aⁱ,aⁱ1|aⁱ,aⁱ1∈D,i1,2,...,n-1}基本操作1.InitList(L)操作前提L为未初始化线性表。操作结果将L初始化为空表。2.ListLength(L)操作前提线性表L已存在。操作结果如果L为空表则返回0否则返回表中的元素的个数。3.GetData(L,i)操作前提表L存在且1≤i≤ListLength(L)。操作结果返回线性表L中第i个合法元素的值。4.InsList(L,i,e)操作前提表L已存在e为合法元素值且1≤i≤ListLength(L)1。操作结果在L中第i个位置之前插入新的数据元素eL的长度加1。5.DelList(L,i,e)操作前提表L已存在且非空1≤i≤ListLength(L)。操作结果删除L的第i个数据元素并用e返回其值L的长度减1。6.Locate(L,e)操作前提表L已存在e为合法数据元素值。操作结果如果L中存在数据元素e则返回e在L中的位置否则返回空位置。7.DestroyList(L)操作前提线性表已存在。操作结果将L销毁。8.ClearList(L)操作前提线性表L已存在。操作结果将L置为空表。9.EmptyList(L)操作前提线性表L已存在。操作结果如果L为空表则返回TRUE否则返回FALSE。
}ADT LinearList; 以上仅为一个抽象数据类型。因为一个抽象数据类型仅是一个模型的定义并不设计模型的具体实现因此这里使用参数不考虑具体类型。在实际问题中对线性表的运算可能很多例如有时需要将多个线性表合并成一个线性表以及在此问题基础之上进行的有条件合并等。像合并分拆/复制/排序等复合运算问题都可以利用基本运算的组合来实现。 三、线性表的顺序存储结构的具体实现使用数组即栈内存
1、线性表顺序存储的表示
#define MAXSIZE 100 //此处的宏定义常量表示线性表的最大长度
typedef struct
{ElemType elem[MAXSIZE]; //线性表占用的数组空间int last; //记录线性表中最后一个元素在数组elem[]中的位置(下标值)空表置为-1
}SeqList;
说明
节点类型定义中ElemType数据类型是为了描述的统一而自定。在实际应用中用户可根据实际需要具体定义顺序表中的数据类型。
注意类型与变量的区别。类型是模板变量是真正的存储空间。
利用定义的顺序表的数据类型SeqList就可以定义变量了。变量L的定义与使用方法有一下两种
通过变量定义语句SeqList L;将L定义为SeqList类型的变量。可通过L.elem[i-1]访问顺序表中序号为i的元素aⁱ;通过L.last得到顺序表中最后一个元素的下标而L.last1就是顺序表的长度。通过指针变量定义语句SeqList L₁*LlL₁将L定义为指向SeqList类型的指针变量。使用时可通过L-elem[i-1]访问顺序表中序号为i的元素aⁱ使用L-last1得到顺序表的长度。
2、线性表初始化函数InitList(L) 算法思想先使用memset初始化函数将开辟的数组空间初始化为指定的NULL值。再将记录线性表中最后一个元素在数组中的位置的值last置为-1。
/*初始化函数*/
int InitList(SeqList *L)
{memset(L-elem,NULL,sizeof(L-elem)); //初始化数据为NULLL-last -1; //空表为-1return 0;
} 第四行使用了memset函数它的作用将数组内的每个空间初始化它有三个参数数组名需要填充的数据此处填充的是NULL值数组空间的大小。 第五行将线性表最后一个元素的下标值置-1为什么要为-1嘞因为当有数据加入的时候先将last值加一然后把last值当做数组的下标值-1去1刚好是0 数组起始下标就是0。 第六行函数返回结果为0结束函数。 3、返回线性表中元素的个数ListLength(L)
算法思想返回表中元素个数即返回最后一个下标值last1的值 /*返回表中元素个数*/
int ListLength(SeqList L)
{return L.last1;
} 第四行直接返回下标值1 4、返回线性表中第i个合法元素的值GetData(L)
算法思想先判断这个i是否在这个线性表范围内即1≤i≤ListLength(L)没有超出返回其值超出范围返回-1。
/*返回线性表中第i个合法元素的值*/
ElemType GetData(SeqList L,int i) { //ElemType是一个宏定义的量在这篇中是用它来代替int代码编译的时候后自动进行转换的if ((1 i) (i ListLength(L))) {return L.elem[i - 1];}else {printf(超出线性表的范围);return -1; //若ElemType发生改变这里需要改变}
} 第三行判断传入的参数i是否合法即他要在这个数组拥有的数据范围内即1ListLengthL之间也可以把这个函数改成1last1之间为短路与即它前边和后边都满足才执行后续大括号内的代码当第一个条件不满足时 直接结束判断进入大括号后边代码不再去判断第二个条件了。 第四行返回数组中i位置的值因为数组开始是0开始的 我们数个数是从1开始的 所以第i个数据在数组中的位置为i-1。 第五行即判断条件为假执行该行代码。 第六行用于方便观察代码执行情况 可去掉。 第八行索引不再数据范围内返回结果-1。 5、将新的元素e插入表尾 InsListEnd(L,e)
算法思想先判断表有没有满满了输出表已满。没满的话将下标值last1将e存入数组中 /*将新的元素e插入表尾*/
int InsListEnd(SeqList* L, ElemType e) {if (L-last MAXSIZE - 1) {printf(表已插满);return 0;}L-last;L-elem[L-last] e;return 0;
} 第三行判断数组是否满了即看下标值是否等于数组内的最后一个下标。当数组大小为50时最后一个下标为49 因为下标是从0开始的故这行代码比较下标和数组大小-1的值进行比较。 第四行便于函数执行过程观察 可去除。 第五行函数返回结果0 结束函数的执行。 第七行第三行判断为假执行该行即数组没满将下标值1。 第八行将新的last值作为数组的下标值将传入的数据存入数组中。 第九行表示数据插入成功 返回结果0函数执行结束。 6、将一个新元素e插入表头 InsListStart(L,e)
算法思想先判断表有没有满满了返回表已满。若没有将数组中的所有元素往后移一位将e放到elem[0]的位置下标长度last1。
/*将一个新元素e插入表头*/
int InsListStart(SeqList* L, ElemType e) {if (L-last MAXSIZE - 1) {printf(表已插满);return 0;}for (int k L-last; k 0; k--) {L-elem[k 1] L-elem[k];}L-elem[0] e;L-last;return 0;
} 第三、四、五行同上第三、四、五行判断表有没有满。 第七行因为要插入到表头所以需要将数组内的所有数据往后移一个位置腾出第一个位置用于存储新的数据这里从后边开始移将最后一个下标值赋值给一个新的变量用做计数器即每变一次值小一个同时这个计数器的值也可以当做下标值进行变化也保证了last不会变化。 第八行即将当前下标的值赋给后一位下标。 第十行数据移完了然后将新数据存入第一个空间中。 第十一行将表长度last1。 7、在第i个元素值之前插入新的数据元素 InsList(L,I,e)
算法思想先判断表有没有满若满了输出打印表已满返回0结束。再判断插入位置是否合法若不合法输出插入不合法返回0结束。若均满足将从i开始数据都往后移一位再将e存入第i处即下标为i-1处记录下标值的last值1。 /*在第i个元素值之前插入新的数据元素*/
int InsList(SeqList *L,int i, ElemType e) {if (L-last MAXSIZE - 1) {printf(表已满无法插入);return 0;}/*判断插入位置是否合法*/if ((i 1) || (i L-last 2)) {printf(插入位置i值不合法);return 0;}for (int k L-last; k i - 1; k--) {L-elem[k 1] L-elem[k];}L-elem[i - 1] e;L-last;printf(插入完成);return 1;
} 第三六行同上判断表有没有满。 第八行判断插入位置是否合法因为我们数个数从1开始数故插入位置最少是1即小于1为假同时最后一个数为last1这是最后最后一个下标值按照正常数数位于的地方但这个地方还有数据所以插入的最后一个位置按照数数来算应该是last1个不能超过这个超过这个了中间就有空的位置了线性表是连续的有空位置就不连续了无意义。 第九行便于观察代码执行过程可去除。 第十行代表插入地址无意义 没必要执行函数内的后续代码了直接结束函数返回结果0。 第十二行同上的第七行将从续插入数据的位置开始往后的数据都往后移一位包括需插入数据的位置。 第十四行将需要存入的数据存入想存的位置。 第十五行将线性表长度last1。 第十六行便于函数执行观察可去除。 第十七行函数执行完毕返回结果1。 8、删除L的第i个数据元素 DelList(L,i)
算法思想先判断需删除位置i是否合法若不合法输出打印输入位置i不合法返回0结束。合法的话将需删除的数据存入一个变量中将从需要删除的位置起之后的数据都往前移一位。将last小标值-1返回删除的数据e的值。 /*删除L的第i个数据元素*/
ElemType DelList(SeqList* L, int i) {ElemType e;if ((i1) || (iL-last1)) {printf(输入位置i不合法);return 0; //若ElemType发生改变这里需要改变}e L-elem[i-1];for (; i L-last; i) {L-elem[i - 1] L-elem[i];}L-last--;return e;
} 第三行定义一个变量用于存储删除数据的值最后返回这个值。 第四七行用于判断插入地址是否合法||为短路或即有一个为真即为真当第一个为真时就不判断第二个条件了需要删除的值应该在1last1范围内即下标值是0last范围内。 第八行将第i个元素取出即下标为i-1。实在理解不了的可以对比这代码行数想第几行第几行是我们数的即从1开始但下标是从0开始的。也就是第一行下标是为0第二行下标为1这个学计算机的是必须得去理解的。 第九行for循环将从删除地方开始的后续数据都往前移一位以覆盖的形式去删除数据最后一个数据会有俩但只要将表长度减一即可虽然最后一个数据还在那但当有新的数据存入时会去覆盖它的而且表中是用last值作为下标去访问故最后一个元素是不可见的。 第十一行将表长last-1使原最后一个数据不可见。 第十二行结束函数 返回取出的结果。 9、顺序表的按内容查找数据元素 Locate(L,e)
算法思想从第一个数据遍历直到表中最后一个数据非数组中最后一个数据每次循环加一个判断语句判断数据是否和需查找一致。存在则返回下标值last1即所处位置非下标位置下标是从0开始位于第几个是从1开始。
/*顺序表的按内容查找数据元素如果L中存在数据元素e则返回e在L中的位置否则返回空位置
*/
int Locate(SeqList L, ElemType e) {for (int i 0; i L.last; i) {if (L.elem[i] e) {return i1;}}printf(数据不在表中\n);return -1;
} 第五行for循环去遍历整个表。 第六行在遍历的时候增加一个判断条件不做无意义的遍历将数组中的各个节点与需查找的数据进行匹配判断。 第七行返回匹配的位置结果。 第十行便于函数执行过程观察可去除。 第十一行无匹配结果返回-1。 10、将线性表L置为空表 ClearList(L)
算法思想直接调用初始化线性表函数即可
/*将线性表L置为空表*/
int ClearList(SeqList* L) {InitList(L);return 0;
} 第三行初始化线性表函数中有一个memset函数能够将数组内所有空间置为同一个数据这里同置NULL也将下标置为了-1。 11、判断表是否为空 EmptyList(L)
算法思想判断last值是否为-1即可
/*判断表是否为空表*/
bool EmptyList(SeqList L) {if (L.last -1)return true;return false;
} 第三行判断下标是否为-1这是顺序线性表的一个标准性。下标为-1即表为空。 第四行判断为真执行结束函数 返回bool类型ture。 第五行判断为假执行结束函数 返回bool类型 false。 12、打印输出顺序表 PrintList(L)
算法思想若为空表则返回0即可否则遍历循环打印输出数组中在last范围内的值。
int PrintList(SeqList L) {if (L.last 0) {return 0;}printf([);for (int i 0; i L.last-1; i) { //遍历到last-1是因为最后一个数据输出后不需要逗号需要一个返回来的]符号printf(%d,, L.elem[i]);}printf(%d], L.elem[L.last]);return 0;
} 该函数为我自定义便于观察的函数不做说明可不要。 13、销毁线性表 DestroyList(L)
顺序表是静态存储分配在顺序表变量退出作用域时自动释放该变量所占的内存单元。因此顺序表无须销毁。(若使用malloc函数分配的堆内存使用free函数进行销毁即可)
四、顺序表全部代码及每个模块测试
#include iostream#define MAXSIZE 100
#define ElemType int //若改变数据类型GetDataDelList函数的返回值需改变typedef struct
{ElemType elem[MAXSIZE];int last;
}SeqList;/*初始化函数*/
int InitList(SeqList *L)
{memset(L-elem,NULL,sizeof(L-elem)); //初始化数据为NULLL-last -1; //空表为-1return 0;
}/*返回表中元素个数*/
int ListLength(SeqList L)
{return L.last1;
}/*返回线性表中第i个合法元素的值*/
ElemType GetData(SeqList L,int i) {if ((1 i) (i ListLength(L))) {return L.elem[i - 1];}else {printf(超出线性表的范围);return -1; //若ElemType发生改变这里需要改变}
}/*将新的元素e插入表尾*/
int InsListEnd(SeqList* L, ElemType e) {if (L-last MAXSIZE - 1) {printf(表已插满);return 0;}L-last;L-elem[L-last] e;return 0;
}/*将一个新元素e插入表头*/
int InsListStart(SeqList* L, ElemType e) {if (L-last MAXSIZE - 1) {printf(表已插满);return 0;}for (int k L-last; k 0; k--) {L-elem[k 1] L-elem[k];}L-elem[0] e;L-last;return 0;
}/*在第i个元素值之前插入新的数据元素*/
int InsList(SeqList *L,int i, ElemType e) {if (L-last MAXSIZE - 1) {printf(表已满无法插入);return 0;}/*判断插入位置是否合法*/if ((i 1) || (i L-last 2)) {printf(插入位置i值不合法);return 0;}for (int k L-last; k i - 1; k--) {L-elem[k 1] L-elem[k];}L-elem[i - 1] e;L-last;printf(插入完成);return 1;
}/*删除L的第i个数据元素*/
ElemType DelList(SeqList* L, int i) {ElemType e;if ((i1) || (iL-last1)) {printf(输入位置i不合法);return 0; //若ElemType发生改变这里需要改变}e L-elem[i-1];for (; i L-last; i) {L-elem[i - 1] L-elem[i];}L-last--;return e;
}/*顺序表的按内容查找数据元素如果L中存在数据元素e则返回e在L中的位置否则返回空位置
*/
int Locate(SeqList L, ElemType e) {for (int i 0; i L.last; i) {if (L.elem[i] e) {return i1;}}printf(数据不在表中);return -1;
}/*将线性表L置为空表*/
int ClearList(SeqList* L) {InitList(L);return 0;
}/*判断表是否为空表*/
bool EmptyList(SeqList L) {if (L.last -1)return true;return false;
}/*打印输出顺序表*/
int PrintList(SeqList L) {if (L.last 0) {return 0;}printf([);for (int i 0; i L.last-1; i) {printf(%d,, L.elem[i]);}printf(%d], L.elem[L.last]);return 0;
}int main()
{SeqList list,*L;L list;printf(————————初始化线性表—————-—————\n);printf(初始化返回结果%d, InitList(L));printf(\n——————返回线性表中元素的个数——————\n);printf(线性表中元素个数为%d,ListLength(list));printf(\n——————返回线性表中第i元素——————\n);printf(返回结果%d,GetData(list,2));printf(\n——————将线性表中表尾插入法插入十个元素——————\n);for (int i 0; i 10; i)InsListEnd(L, i * 2);printf(插入结果为);PrintList(list);printf(\n——————再次返回线性表中元素的个数——————\n);printf(线性表中元素个数为%d, ListLength(list));printf(\n——————将新元素77插入表头——————\n);InsListStart(L,77);printf(插入结果为);PrintList(list);printf(\n——————将新元素99插入第7的位置——————\n);InsList(L, 7, 99);printf(插入结果为);PrintList(list);printf(\n——————将新元素100插入第50的位置——————\n);InsList(L, 50, 100);printf(\n—————-删除第3个元素——————\n);printf(删除的数为%d, DelList(L, 3));printf(删除后表为为);PrintList(list);printf(\n—————-判断表是否为空表——————\n);printf(空为1不空为0%d, EmptyList(list));printf(\n—————-查找1250位于表的哪个位置——————\n);printf(12位于第%d个元素。\n,Locate(list,12));printf(50位于第%d个元素。,Locate(list, 50));printf(\n—————-将线性表置为空表——————\n);ClearList(L);printf(置后结果为);PrintList(list);printf(\n—————-再次判断表是否为空表——————\n);printf(空为1不空为0%d, EmptyList(list));
}
测试结果为
