17-数据结构常见算法

数据结构算法数据结构•数据结构是一门研究非数值计算的程序设计问题中的操作对象（结点）以及它们之间关系和操作等的学科。•1968年克努思教授开创了数据结构的最初体系，他所著的《计算机程序设计艺术》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。70年代初，数据结构作为一门独立的课程开始进入大学课堂。•下面介绍数据结构中常见的一些基本算法•关于算法•线性表上的常见算法•基于队列的常见算法•基于栈的常见算法算法•多项式求的两种方法–A(x)=anxn+an-1xn-1+…+a0–A(x)=((anx+an-1)X+an-2)…+a0–A(x)=anxn+an-1xn-1+…+a0templatetypenameTTPoly1(Ta[],intn,Tx){inti,j;Tresult=0;Txn,xx;for(i=0;in;i++){xn=1;xx=x;for(j=0;ji;j++)xn=xn*xx;result=a[i]*xn+result;}returnresult;}–A(x)=((anx+an-1)X+an-2)…+a0templatetypenameTTPoly2(Ta[],intn,Tx){inti,j;Tresult=0;Txn,xx;result=a[n-1];for(i=n-1;i0;i--)result=result*x+a[i-1];returnresult;}线性表1.设计一个时间复杂度为O(n)的算法，实现将数组A[n]中所有元素循环右移K个位置2.已知数组元素为整型，设计算法将其调整为左右两部分，左边元素为奇数，右边元素为偶数3.设单链表以非递减有序排列，设计算法，实现在单链表中删去系统的多余结点4.设单链表以非递减有序排列，设计算法，实现在单链表中删去系统的多余结点5.已知一个单链表中的数据元素含有三类字符：数字、字母和其他字符。编写算法，构造三个循环链表，使得每个循环链表中之包含同一类字符返回设计一个时间复杂度为O(n)的算法，实现将数组A[n]中所有元素循环右移K个位置•算法分析knkn。k=k%N01234567891011121314140123456789101112131314012345678910111212131401234567891011AB(k=1)B(k=2)B(k=3)j=(i+k)%Ninti,j,n;int*a;cinnk;k=k%n;a=newint[n];for(i=0;in;i++)cina[i];for(i=0;in;i++){j=(i+k)%n;b[j]=a[i];}时间复杂度？空间复杂度？空间复杂度更少的方法•假设原数组序列为abcd1234，循环右移了4位–数组序列为1234abcd。•右移后，有两段的顺序是不变的：1234和abcd，可把这两段看成两个整体。右移K位的过程就是把数组的两部分交换一下。变换的过程通过以下步骤完成：•1.逆序排列abcd：abcd1234→dcba1234；•2.逆序排列1234：dcba1234→dcba4321；•3.全部逆序：dcba4321→1234abcd。•更一般的情况：01234567891011121314140123456789101112131314012345678910111212131401234567891011根据K%N的大小，将数据分成两段，第一段长度为N-K个数据，第二段中有K个数据然后分别将两段逆序，最后将整个数组逆序voidconvert(inta[],intstart,intend){intk,temp;for(k=0;k(end-start+1)/2;k++){temp=a[start+k];a[start+k]=a[end-k];a[end-k]=temp;}}voidyiwei(inta[],intn,intk){convert(a,0,k-1);convert(a,k,n-1);convert(a,0,n-1);}已知数组元素为整型，设计算法将其调整为左右两部分，左边元素为奇数，右边元素为偶数•算法分析1.设计两个工作指针，分别指向数组的两端（I=0；j=n-1）.然后，重复的进行以下工作：2.如果ij:①从左向后扫描数组，直到遇到第一个偶数②从右向左扫描数组，直到遇到第一个奇数③如果ij交换a[i]、a[j]的数据，，同时修改i，j的值，继续进行2的工作intn,*a;cinn;a=newint[n];inti=0,j=n-1;for(i=0;in;i++)cina[i];i=0;while(ij){while(a[i]%2==1)i++;while(a[j]%2==0)j--;if(ij){temp=a[i];a[i]=a[j];a[j]=temp;i++;j--}}#includestdafx.h#includeiostream.hclasschange{private:int*a,length;public:change(){coutPleaseinputthelengthofthearray:;cinlength;a=newint[length];coutPleaseinputthedataofthearray:;for(inti=0;ilength;i++)cina[i];}voidtrans(){inti=0,j=length-1;inttemp;while(ij){while(a[i]%2==1)i++;while(a[j]%2==0)j--;if(ij){temp=a[i];a[i]=a[j];a[j]=temp;i++;j--;}}return;}voiddisplay(){inti=0;for(i=0;ilength;i++)couta[i];coutendl;}};intmain(intargc,char*argv[]){changea;coutbeforechange:;a.display();a.trans();coutafterchange:;a.display();return0;}返回设单链表以非递减有序排列，设计算法，实现在单链表中删去系统的多余结点•基本思想：•从头结点出发，进行链表的遍历，在遍历的过程中，设置两个工作指针p和q（q=p-next），•比较p、q所指向的节点的值，如果相同，则删除q所指向的节点，b带头结点的单链表Ha1a2…an算法描述•设置工作指针p、q，并进行初始化：–p=list.head-next;•if(!p)return•elseq=p-next;–在q!=NULL的情况下，重复进行以下工作：•if(p-data==q-data)–temp=q;–p-next=q-next;–q=p-next;–deletetemp•elsep=q;q=q-next;templateclassTvoidDeleteSame(LinkListTa){NodeT*p,*q,*temp;p=a.GetHead()-next;if(!p){coutThisisaemptylist!!;return;}else{q=p-next;}while(q){if(p-data==q-data){temp=q;p-next=q-next;q=p-next;deletetemp;}else{p=q;q=q-next;}}return;}判断带头节点的双循环链表是否对称•设置两个工作指针p=首元节点,q=尾节点,•重复进行以下工作：–比较p和q的值，•如果不想等，停止比较，返回false•如果相等，–观察p、q是否相邻（p-right==q,p-right-right==q）,如果相邻，返回true,否则–p=p-right,q=q-left,firsta1a2an•1.定义两个工作指针ｐ、ｑ，并进行初始化：–ｐ=list.first-right;q=list.first-left;•2.重复进行以下工作(while(1))–if(p-data!=q-datareturnfalse;–else{•if(p-right==q||p-right-right==q)–returntrue;•else{p=p-right;q=q-left;}返回已知一个单链表中的数据元素含有三类字符：数字、字母和其他字符。编写算法，构造三个循环链表，使得每个循环链表中之包含同一类字符•基本思想–每个链表都带有头结点。原始链表为A，分类之后新增B,C，使得A存放字母，B存放数字，C存放其他字符–基本过程：在A中进行遍历，并检查遍历到的符号，•如果是字符，不做任何处理（继续后移指针）；•如果是数字，则将其采用尾插法加入到B中（继续后移指针），•如果是第三类符号，则将其采用尾插法插入到C中（继续后移指针）算法分析•已知链表A，构造两个空循环链表B(数字），C（其他字符）•设置工作指针p;p=A.first(头结点)•定义一个辅助指针q，完成工作:q=p-next;•如果q!=A.first–IsDigital(q-data)，则将q从A中删除，并将其链入B中•temp=q;p-next=q-next,q=p-next;•temp-next=B.first;•B.rear-next=temp;•B.rear=p;–q-data是其他字符，则将其从A中删除，并将其链入C中–重复进行上述工作，直到A链表遍历结束templateclassTstructNode{Tdata;NodeT*next;};templateclassTclassCycleList{NodeT*head,*rear;intLength;public:CycleList(){head=newNodeT;head-next=head;rear=head;}CycleList(intn);voidDisplay();NodeT*GetHead(){returnhead;}voidappend(NodeT*p);friendvoidSegment(CycleListTa);};templateclassTvoidCycleListT::append(NodeT*p){p-next=rear-next;rear-next=p;rear=p;return;}templateclassTCycleListT::CycleList(intn){Tinput;NodeT*s;head=newNodeT;head-next=head;rear=head;Length=n;inti=0;for(i=0;iLength;i++){cininput;s=newNodeT;s-data=input;append(s);}}templateclassTvoidCycleListT::Display(){NodeT*p;p=head-next;while(p!=head){coutp-data;p=p-next;}coutendl;}templateclassTvoidSegment(CycleListTA){NodeT*p,*q,*ahead,*temp;CycleListTB,C;coutthelistis:;A.Display();p=A.GetHead();ahead=p;q=p-next;templateclassTwhile(q!=ahead){if(q-data='0'&&q-data='9'){temp=q;p-next=q-next;q=p-next;B.append(temp);}else{if(q-data='a'&&q-data