6个有趣的数据结构算法的题.doc

今天给同学写5个数据结构算法的题.感觉很有价值的几个题.感兴趣的坐下。 1.判断一个顺序表是否对称2用向量作存储结构，设计以算法仅用一个辅助结点，实现将线性表中的结点循环右移k位的运算3.已知A【n】中的元素为整形。设计算法将其调整为左右两部分。左边所有元素为奇数，右边所有元素为偶数，4，设计以算法，逆置带头结点的动态链表L，5单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点，6假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，是编写算法将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表的结点空间存放C我写的代码如下1 、/*要求 :判断一个顺序表是否对称 */#include using namespace std ;#define MAX_SIZE 200 template bool IsSymmetrical(T List,int length); /利用模板可以比较任意类型的顺序表void main()int group= 0;bool *pGroup=NULL;/保存的是比较的结果int *pNum =NULL; /这里以整形顺序表为例int nCount=0 ;/每组数据的个数/cout请输入要比较几组数据:group; pGroup=new boolgroup ; /动态分配数组内存保存对称比较结果for(int n=0;nnCount ;pNum=new intnCount ; /动态为每行数据分配内存 for(int m=0;mpNumm; pGroupn=IsSymmetrical(pNum,nCount) ; /直接将函数返回结果的bool值保存在动态分配的数组中delete pNum ;/ 第一组内存使用完毕释放掉 防止内存泄露 for(n=0;ngroup;n+) /输出是否对称Y Nif(pGroupn)coutYendl ;else coutNendl ; delete pGroup ; /最后再次释放堆内存template bool IsSymmetrical(T List,int length) /利用模板可以比较任意类型的顺序表 int l=0;for(int n=0;n=length-1;n+)if(Listn=Listlength-1-n)l+ ;if(l=length)return true ;return false ;2、/*要求:用向量作存储结构，设计以算法仅用一个辅助结点，实现将线性表中的结点循环右移k位的运算 向量即STL中的vector 动态数组 时间原因这里我只弄了一个线性表来循环移动算法在下面注释部分 需要像第一题多组输入的时候只需要将整个实现部分放在一个循环中实现即可 */#include #include using namespace std ;#include windows.hstruct Node /节点数据int data; ;void main() vector List; /向量的定义 int size ;/接收输入的大小cout请输入表中初始数据的个数:size ;Node *pArray=NULL ;/接受输入的数据pArray=new Nodesize ; for(int n=0;nsize;n+) cout请输入第n+1个节点的数据,一次输入一个回车结束输入:pArrayn.data ;List.push_back(pArrayn) ; /插入数据vector:iterator p=List.begin() ;/返回迭代器 我们可以通过迭代器访问vectorsystem(cls);/清除屏幕cout初始表中数据如下:endl;for(n=0;nsize;n+) /通过迭代器输入表中数据coutpn.data ;coutendl ;cout数据输入完成请输入要向右移动的位置k:move ;move=move%size ; /取模Node tem ;List.insert(p,move,tem) ; /在前面插入5个临时节点 p=List.begin(); /迭代到第一个节点/算法实现部分size=List.size();int m=0; for(n=size-move ,m=0;nsize;n+,m+) /对插入的节点进行赋值pm=pn; for(n=0;nmove;n+)List.pop_back() ;/pop出尾部元素 /p=List.begin() ;cout右移后元素位置:endl;for(n=0;nsize;n+) coutpn.data ;coutendl;3、/*3.已知A【n】中的元素为整形。设计算法将其调整为左右两部分。左边所有元素为奇数，右边所有元素为偶数，操作例子 组数 2 第一组 5(个数) 1 2 3 4 5 结果 1 3 5 2 4 然后根据提示继续输入下一组 */#includeusing namespace std;#define MAX_SIZE 100void SetArray(int arr,int length) ;/算法实现函数void main() coutttt操作例子 endl回车 endl回车结束endl; cout显示结果然后继续输入下组endl ; int *pArray=NULL;/动态数组指针int nCount=0;/每行数组的个数int group=0;cout请输入组数:group;for(int i=0;igroup;i+)cout请输入第i+1组的个数以及数据例如: 5 1 2 3 4 5nCount; /输入个数pArray=new intnCount ; for(int n=0;npArrayn;SetArray(pArray,nCount); /调用设置函数 改变奇数偶数位置for(n=0;nnCount;n+)coutpArrayn ;coutendl ;delete pArray ; /释放堆中内存void SetArray(int arr,int length) /算法实现函数char buf1MAX_SIZE ;char buf2MAX_SIZE ;memset(buf1,*,MAX_SIZE); /存放奇数memset(buf2,*,MAX_SIZE);/存放偶数buf2MAX_SIZE-1=0;buf1MAX_SIZE-1=0; /防止越界for(int n=0,m=0,i=0;nlength;n+)if(arrn%2=0)buf2m=0+arrn; /保存偶数asc码m+ ;else buf1i=0+arrn ;/保存奇数asc码i+; for(n=0,m=0,i=0;nlength;n+) if(buf1m!=*) arrn=buf1m-0 ; m+; else arrn=buf2i-0 ; i+; 4、/*，设计以算法，逆置带头结点的动态链表L， 先创建 链表然后 进行反序 */#include using namespace std ;typedef struct Node /链表节点int data ;struct Node*next ;*Head,*LinkNode;Head head;/头结点int length=0 ;Head CreatLinkList() ; /自定义带头链表创建函数 void Reserve(Head head) ; /反序算法的实现 其实是实现数据的反序 void Show(Head head) ;/显示函数 void main() int group ;cout请输入要反序的链表组数group ;Head *pLink=new Headgroup; /保存链表头cout回车endl;for(int n=0;ngroup;n+) head=CreatLinkList();/创建链表 Reserve(head) ;pLinkn=head ; length =0;cout反序后:endl; coutendl ;for( n=0;ngroup;n+)Show(pLinkn); coutendl ;void Reserve(Head head) /反序算法的实现 其实是实现数据的反序 int count=length/2 ; /比较次数LinkNode p1=head,p2=head ;int tem ;for(int n=0;ncount;n+) for(int m=0;mnext ;tem=p1-data ;p1-data=p2-data ;p2-data=tem ;p1=p1-next ;p2=head ;void Show(Head head) /显示函数 while(head!=NULL)coutdatanext;coutp1-data ;if(p1-data=66666)delete p1 ; p1=NULL ; p2=NULL;length-;return NULL ;while(p1-data!=66666) p2=p1 ;p1=new Node ;length+;cinp1-data ;if(p1-data=66666)delete p1 ; p1=NULL ; p2-next=NULL;length-;return head ;p2-next=p1 ;return head ;5、/*单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点， 算法实现 就是用2个循环遍历链表 算法实现在下注释部分*/#include using namespace std ;typedef struct Node /链表节点int data ;struct Node*next ;*Head,*LinkNode;Head head ;/头结点 Head CreatLinkList() ;/自定义带头链表创建函数 void Delete(Head head) ; /删除重复的节点算法实现部分。void Show(Head head) ;/显示函数 void main() head=CreatLinkList() ;system(cls);cout表中数据如下:endl;Show(head) ;Delete(head) ; /删除重复节点cout删除重复节点后的链表:endl; Show(head) ;Head CreatLinkList() /自定义带头链表创建函数 LinkNode p1=NULL,p2=NULL,head =NULL ;p1=new Node ; head=p1 ; p2=p1 ;cout请输入链表节点数据,数据间空格分开 输入66666结束输入 例如 1 2 3 4 5 66666p1-data ;if(p1-data=66666)delete p1 ; p1=NULL ; p2=NULL;return NULL ;while(p1-data!=66666) p2=p1 ;p1=new Node ;cinp1-data ;if(p1-data=66666)delete p1 ; p1=NULL ; p2-next=NULL;return head ;p2-next=p1 ;return head ;/void Delete(Head head) /删除重复的节点算法实现部分。Head p1=head,p2=head ; LinkNode tem=NULL ; /临时节点指针while(p1!=NULL)while(p2-next!=NULL) /当p2的next到达尾部的时候后就要推出否则 下面p2-next-next会崩溃 if(p2-next-data=p1-data)tem=p2-next ;p2-next=p2-next-next ;delete tem ;continue ;elsep2=p2-next ;p1=p1-next;p2=p1 ;/void Show(Head head) /显示函数 while(head!=NULL)coutdatanext;coutendl ; 6、/*6假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，是编写算法将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表的结点空间存放C*/#include using namespace std ;typedef struct Node /链表节点int data ;struct Node*next ;*Head,*LinkNode;LinkNode A =NULL;/表1 LinkNode B =NULL;/表2LinkNode C=NULL; /表3int GetMax(Head head); /返回链表中的最大数据 Head CreatLinkList() ;/自定义带头链表创建函数 Head CombineLinkList(Head A,Head B) ; /合并算法的实现部分void Show(Head head) ;/显示函数 void main() cout表A:endl;A=CreatLinkList(); /创建表A cout表B:next!=NULL) tem=tem-next; tem-next=B ; C=A ;/A B 表连接起来 然后 降序排序 LinkNode p1=C; LinkNode p2=C-next; int inter=C-data ;/用于交换的临时变量 while(p1