/******************************************************************************************************第一章 绪论*数据结构 data structure*数据 data*数据元素 data element*算法 algorithm*时间复杂度 time complexity*空间复杂度 space complexity*时间复杂度比较*O(1) O( logn) O(n) O(nlogn) O(n²)*O(2^n) O(n!) O(n^n)*****************************************************************************************************//***************************************************************************************************** *第二章 线性表 *线性表 linear list *线性链表 link list *循环链表 circular linked lists *双向循环链表 double circular linked list *****************************************************************************************************//***************************************************************************************************** *顺序存储的线性表 *概念 *顺序存储的线性表是将逻辑上相邻的节点存储在物理位置相邻的存储单元中通常用数组来实现顺序存储的线性表简称顺序线性表 *顺序存储的线性表的基本操作有插入、删除、查找、遍历等 *****************************************************************************************************///顺序线性表BEGIN#defineMAX100//线性表可能的最大长度typedefstruct{charelement[MAX];//存放线性表数据intnum;//数据个数}LIST;/***************************************************************************************************** *函数名称:sequenceListInsert *功能描述:插入元素要在长度为n的顺序线性表的第m个元素之前插入一个新的数据元素x需要将第n到第m共n-m1个元素向后移动一个位置从而空出一个位置放入新增加的数据元素 *输入参数:LIST*现有列表 int m:插入位置 char x:插入数据 *返 回 值:-1线性表已满无法插入 -2:插入位置有误MAXm0 -3:线性表元素个数有误 0插入成功 *作 者:zj *日 期:2024-12-12 *备 注: *****************************************************************************************************/intsequenceListInsert(LIST*list,constintm,constcharx){intcurNumlist-num;if(curNumMAX){return-1;}if(m1||mMAX){return-2;}if(curNum0){return-3;}while(curNumm){list-element[curNum--]list-element[curNum];}list-element[m-1]x;list-num;return0;}/***************************************************************************************************** *函数名称:sequenceListDelete *功能描述:删除元素在顺序线性表中要删除第m个元素需要将第m1到第n共n-m个元素依次向前移动一个位置填补被删除元素的位置 *输入参数:LIST*:现有列表 m:删除位置 *返 回 值:-1:顺序线性表元素个数有误 -2:删除元素下标有误 0:删除成功 *作 者:zj *日 期:2024-12-12 *备 注: *****************************************************************************************************/intsequenceListDelete(LIST*list,intm){intcurNumlist-num;if(curNum0){return-1;}if(m1||mMAX){return-2;}while(mcurNum){list-element[m-1]list-element[m];}list-num--;return0;}/***************************************************************************************************** *函数名称:sequenceListFind *功能描述:查找元素在一个顺序线性表中查找特定值的数据元素可以从第一个元素开始逐个与需查找的值比较。顺序查找 *输入参数:LIST*:现有顺序线性表 x:待查找元素 *返 回 值:-1:未查找到 查找到后返回下标 *作 者:zj *日 期:2024-12-12 *备 注: *****************************************************************************************************/intsequenceListFind(LIST*list,charx){intcurNumlist-num;if(curNum0){return-1;}for(inti0;icurNum;i){if(list-element[i]x){returni1;}}return-1;}/***************************************************************************************************** *函数名称:sequenceListUnion *功能描述:计算source与target的并集,将结果保存到target中 *输入参数:target:目标集合 source:需要合并的集合 *返 回 值:无 *作 者:zj *日 期:2024-12-12 *备 注: *****************************************************************************************************/voidsequenceListUnion(LIST*target,LIST*source){for(inti0;isource-num;i){if(sequenceListFind(target,source-element[i])-1){sequenceListInsert(target,target-num1,source-element[i]);}}}//顺序线性表END/***************************************************************************************************** *线性表-向前链表的存储结构 *概念 *它不要求逻辑上相邻的元素在物理地址上也相邻因此可以避免顺序线性表的弱点 *向前链表的基本操作有插入、删除、查找、遍历等 *****************************************************************************************************///向前链式线性表BEGIN/***************************************************************************************************** *数据域info存放线性表元素的值指针域link保存下一个元素的指针 *****************************************************************************************************/typedefstructnode{charinfo;//数据域structnode*link;//指针域}NODE;//向前链式线性表END//测试代码BEGINvoidprintList(LIST*list){for(inti0;ilist-num;i){std::coutlist-element[i];}std::coutstd::endl;}voidprintNode(NODE*head){NODE*ithead-link;while(it){std::coutit-info;itit-link;}std::coutstd::endl;}intmain(intargc,char**argv){for(inti0;iargc;i){std::coutargv[i]std::endl;}LIST*listnew LIST;LIST*list1new LIST;list-num0;memset(list-element,0,MAX);list1-num0;memset(list1-element,0,MAX);for(inti0;i10;i){sequenceListInsert(list,i,i0);}printList(list);sequenceListDelete(list,2);printList(list);sequenceListInsert(list1,1,]);sequenceListUnion(list,list1);printList(list);system(pause);return0;}//测试代码END
数据结构绪论及线性表的实践
/******************************************************************************************************第一章 绪论*数据结构 data structure*数据 data*数据元素 data element*算法 algorithm*时间复杂度 time complexity*空间复杂度 space complexity*时间复杂度比较*O(1) O( logn) O(n) O(nlogn) O(n²)*O(2^n) O(n!) O(n^n)*****************************************************************************************************//***************************************************************************************************** *第二章 线性表 *线性表 linear list *线性链表 link list *循环链表 circular linked lists *双向循环链表 double circular linked list *****************************************************************************************************//***************************************************************************************************** *顺序存储的线性表 *概念 *顺序存储的线性表是将逻辑上相邻的节点存储在物理位置相邻的存储单元中通常用数组来实现顺序存储的线性表简称顺序线性表 *顺序存储的线性表的基本操作有插入、删除、查找、遍历等 *****************************************************************************************************///顺序线性表BEGIN#defineMAX100//线性表可能的最大长度typedefstruct{charelement[MAX];//存放线性表数据intnum;//数据个数}LIST;/***************************************************************************************************** *函数名称:sequenceListInsert *功能描述:插入元素要在长度为n的顺序线性表的第m个元素之前插入一个新的数据元素x需要将第n到第m共n-m1个元素向后移动一个位置从而空出一个位置放入新增加的数据元素 *输入参数:LIST*现有列表 int m:插入位置 char x:插入数据 *返 回 值:-1线性表已满无法插入 -2:插入位置有误MAXm0 -3:线性表元素个数有误 0插入成功 *作 者:zj *日 期:2024-12-12 *备 注: *****************************************************************************************************/intsequenceListInsert(LIST*list,constintm,constcharx){intcurNumlist-num;if(curNumMAX){return-1;}if(m1||mMAX){return-2;}if(curNum0){return-3;}while(curNumm){list-element[curNum--]list-element[curNum];}list-element[m-1]x;list-num;return0;}/***************************************************************************************************** *函数名称:sequenceListDelete *功能描述:删除元素在顺序线性表中要删除第m个元素需要将第m1到第n共n-m个元素依次向前移动一个位置填补被删除元素的位置 *输入参数:LIST*:现有列表 m:删除位置 *返 回 值:-1:顺序线性表元素个数有误 -2:删除元素下标有误 0:删除成功 *作 者:zj *日 期:2024-12-12 *备 注: *****************************************************************************************************/intsequenceListDelete(LIST*list,intm){intcurNumlist-num;if(curNum0){return-1;}if(m1||mMAX){return-2;}while(mcurNum){list-element[m-1]list-element[m];}list-num--;return0;}/***************************************************************************************************** *函数名称:sequenceListFind *功能描述:查找元素在一个顺序线性表中查找特定值的数据元素可以从第一个元素开始逐个与需查找的值比较。顺序查找 *输入参数:LIST*:现有顺序线性表 x:待查找元素 *返 回 值:-1:未查找到 查找到后返回下标 *作 者:zj *日 期:2024-12-12 *备 注: *****************************************************************************************************/intsequenceListFind(LIST*list,charx){intcurNumlist-num;if(curNum0){return-1;}for(inti0;icurNum;i){if(list-element[i]x){returni1;}}return-1;}/***************************************************************************************************** *函数名称:sequenceListUnion *功能描述:计算source与target的并集,将结果保存到target中 *输入参数:target:目标集合 source:需要合并的集合 *返 回 值:无 *作 者:zj *日 期:2024-12-12 *备 注: *****************************************************************************************************/voidsequenceListUnion(LIST*target,LIST*source){for(inti0;isource-num;i){if(sequenceListFind(target,source-element[i])-1){sequenceListInsert(target,target-num1,source-element[i]);}}}//顺序线性表END/***************************************************************************************************** *线性表-向前链表的存储结构 *概念 *它不要求逻辑上相邻的元素在物理地址上也相邻因此可以避免顺序线性表的弱点 *向前链表的基本操作有插入、删除、查找、遍历等 *****************************************************************************************************///向前链式线性表BEGIN/***************************************************************************************************** *数据域info存放线性表元素的值指针域link保存下一个元素的指针 *****************************************************************************************************/typedefstructnode{charinfo;//数据域structnode*link;//指针域}NODE;//向前链式线性表END//测试代码BEGINvoidprintList(LIST*list){for(inti0;ilist-num;i){std::coutlist-element[i];}std::coutstd::endl;}voidprintNode(NODE*head){NODE*ithead-link;while(it){std::coutit-info;itit-link;}std::coutstd::endl;}intmain(intargc,char**argv){for(inti0;iargc;i){std::coutargv[i]std::endl;}LIST*listnew LIST;LIST*list1new LIST;list-num0;memset(list-element,0,MAX);list1-num0;memset(list1-element,0,MAX);for(inti0;i10;i){sequenceListInsert(list,i,i0);}printList(list);sequenceListDelete(list,2);printList(list);sequenceListInsert(list1,1,]);sequenceListUnion(list,list1);printList(list);system(pause);return0;}//测试代码END
