數(shù)據(jù)結(jié)構(gòu)算法數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中的操作對象(結(jié)點)以及它們之間關(guān)系和操作等的學(xué)科。1968年克努思教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系,他所著的《計算機程序設(shè)計藝術(shù)》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。70年代初,數(shù)據(jù)結(jié)構(gòu)作為一門獨立的課程開始進入大學(xué)課堂。下面介紹數(shù)據(jù)結(jié)構(gòu)中常見的一些基本算法我等鞏關(guān)于算法線性表上的常見算法基于隊列的常見算法基于棧的常見算法算法多項式求的兩種方法A(x)=anx"+anx1+…+aoA(x)=(anX+an-1)X+an-2).taotemplate<typenameT>TPoly1(Tall,intn,Tx)intTresult=0:TXO.xxfor(i=0;i<n;i++)A(x)=anxn+an1x1+…+axn=1XXX,for(=0;j<i;j++)xn=XnXXresult=a[]xn+resultreturnresult:template<typenameT>TPoly2Tal,intn,TX)inti,;A(x=((anX+an-1)X+an-2).+aoTresult=0:T<n,XX,result=a[n-1];for(i=n-1;i>0;-)result=result*X+a[i-11returnresult線性表設(shè)計一個時間復(fù)雜度為o(n)的算法,實現(xiàn)將數(shù)組A[m]中所有元素循環(huán)右移K個位置2.已知數(shù)組元素為整型,設(shè)計算法將其調(diào)整為左右兩部分,左邊元素為奇數(shù),右邊元素為偶數(shù)3.設(shè)單鏈表以非遞減有序排列,設(shè)計算法,實現(xiàn)在單鏈表中刪去系統(tǒng)的多余結(jié)點4.設(shè)單鏈表以非遞減有序排列,設(shè)計算法,實現(xiàn)在單鏈表中刪去系統(tǒng)的多余結(jié)點5.已知一個單鏈表中的數(shù)據(jù)元素含有三類字符:數(shù)字、字母和其他字符。編寫算法,構(gòu)造三個循環(huán)鏈表,使得每個循環(huán)鏈表中之包含同一類字符運回設(shè)計一個時間復(fù)雜度為om)的算法,實現(xiàn)將數(shù)組A[m]中所有元素循環(huán)右移K個位置算法分析nk>n。k=k%NA|01234567891011121314B(k=1)|14023415689101213B(k=2)13140123456789101112B(k=3)121314012367891011j=(+k)%Ninti,j,n;int"a,c>>n>>k=k%na〓newint[n];for(i=0;i<n;i++)cIn>>>a[fori=0;i<<n;i++)[時間復(fù)雜度?j=(+k)%n空間復(fù)雜度?b]=a[空間復(fù)雜度更少的方法假設(shè)原數(shù)組序列為abcd1234,循環(huán)右移了4位數(shù)組序列為1234abcd右移后,有兩段的順序是不變的:1234和abcd,可把這兩段看成兩個整體。右移K位的過程就是把數(shù)組的兩部分交換一下。變換的過程通過以下步驟完成1.逆序排列abcd:abcd123