c數據結構演算法題
#include<stdio.h>
intmain()
{
doubles=0.00,w=1.00,p=1.00,f=0.00;
inti=0;
doubler0=0.00,r1=0.02,r2=0.05,r3=0.08,r4=0.10,r5=0.15;
printf("pleaseinputs: ");
scanf("%d",&s);
if(s>=3000)
i=5;
else
i=(int)s/250;
switch(i)
case0:f=p*w*s*(1.0-r0);break;
case1:f=p*w*s*(1.0-r1);break;
case2:f=p*w*s*(1.0-r2);break;
case3:f=p*w*s*(1.0-r3);break;
case4:f=p*w*s*(1.0-r4);break;
case5:f=p*w*s*(1.0-r5);break;
default:printf("inputerror");
printf("allfaref=%f",f);
return0;
}
『貳』 數據結構（C語言版） 中一題目的演算法
演算法我覺得只用一個一個的查，比較是否合題意，其時間復雜度為O(N),如果覺得這個復雜也可以用二分法，時間復雜度就只有O(log2n)
『叄』 數據結構c語言版 ：演算法設計題 求大神解答。。在線等。。。
/*判斷一段字元串是不是迴文,所謂迴文，也就
是正讀反讀都一樣，如asdffdsa*/
#include<iostream>
#include<stdio.h>
using namespace std;
const int size=100;
class HuiWen
{
private:
char ch[100];
int top;
public:
HuiWen(){top = -1;};
void input(char c);
bool isHuiWen();
bool empty();
};
void HuiWen::input(char c)
{
//if(top==size-1) throw"上溢";
top++;
//cin>>ch[top];
ch[top]= c;
}
bool HuiWen::isHuiWen()
{
for(int i=0;i<top;i++)
if(ch[top--]!=ch[i])
return 0;
return 1;
}
bool HuiWen::empty()
{
if(top==-1)
return 1;
return 0;
}
int main()
{
HuiWen hw;
cout<<"請輸入字元串，以回車鍵結束"<<endl;
int c;
while((c=getchar())!='\n')
hw.input(c); //主要就是這里做了修改。
if(hw.empty())
cout<<"對不起，無字元"<<endl;
else
{
if(hw.isHuiWen())
cout<<"該字元串是迴文"<<endl;
else
cout<<"該字元串不是迴文"<<endl;
}
return 0;
}
『肆』 19年3月二級C--數據結構與演算法
1.假設線性表的長度為n，則最壞情況下:
冒泡排序: 需要經過n/2遍的從前往後掃描和n/2遍從後往前掃描，需要比較的次數為n(n-1)/2。總的時間復雜度為O(n的平方)。
快速排序: 比較次數也是n(n-1)/2。總的時間復雜度為O(n的平方)。
直接插入排序: 所需要比較的次數為n(n-1)/2。總的時間復雜度為O(n的平方)。
希爾排序所需要比較的次數為O(n的1.5次方)。(時間復雜度小於以上三種)
堆排序: 最壞情況下，其時間復雜度為O(nlogn)。(小於O(n的平方))。
2.根據數據結構中各元素之間前後關系的復雜程度，一般數據結構分為兩大類: 線性結構和非線性結構。
如果一個非空的數據結構滿足下列兩個條件，①有且只有一個根結點 ②每個結點最多有一個前件，也最多有一個後件。則稱該數據結構為線性結構，又稱線性表。
3.演算法時間復雜度與空間復雜度沒有關系。
4.所謂演算法的時間復雜度，是指執行演算法所需要的計算工作量。
為了能夠比較客觀的反映出一個演算法的效率，在度量一個演算法的工作量時，不僅應該與所用的計算機程序設計語言，以及程序編制者無關，而且還應該與演算法實現過程中的許多細節無關。
5.同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程序的效率。
演算法分析的目的在於選擇合適演算法和改進演算法。
6.堆排序在平均情況下的時間復雜度與最壞情況下的時間復雜度都是O(nlogn)。
7.二叉鏈表: 以二叉鏈表作為樹的存儲結構。鏈表中結點的兩個鏈域分別指向該結點的第一個孩子結點和第一個孩子下的一個兄弟結點。
循環鏈表是鏈式存儲結構，循環隊列是線性存儲結構。( 【×】循環鏈表是循環隊列的鏈式存儲結構)
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點都有兩個指針，分別指向直接後繼和直接前驅，所以從雙鏈表中的任意一個結點開始都可以很方便地訪問它的前驅結點和後繼結點。
8.數據的邏輯結構由兩個要素: 一是數據元素的集合，通常記為D。二是D上的關系，它反映了D中各元素之間的前後件關系，通常記為R。
即一個數據結構可以表示成B=(D,R)，其中B表示數據結構，為了反映D中各元素之間的前後件關系，一般用二元組來表示。例如，假如a與b是D中的兩個數據，則二元組表示a是b的前件，b是a的後件。
線性結構用圖形表示更加直觀。例如: R=｛(5,1)，(7,9)，(1,7)，(9,3)｝，結構為: 5→1→7→9→3
9.快速排序法是一種互換類的排序方法，但由於比冒泡排序的速度快，因此稱為快速排序。
其基本思想是從線性表中選擇一個元素設為t，將線性表後面小於t的元素移到前面，而前面大於t的元素移到後面，結果就將線性表分成了兩部分，t插入到分界線的位置處，這個過程稱為線性表的分割。
簡單插入排序法，是指將無序序列中的各元素依次插入到已經有序的線性表中。
冒泡排序法是一種最簡單的交換類排序方法，它是通過相鄰數據元素的交換，逐步將線性表變為有序。
後兩種元素的移動過程中不會產生新的逆序。
10.程序可作為演算法的一種描述。
11.為了降低演算法的空間復雜度，要求演算法盡量採用原地工作，所謂的原地工作是指執行演算法時所使用的額外空間固定。
一個演算法的空間復雜度一般是指執行這個演算法所需要的內存空間，一個演算法所佔用的存儲空間包括程序所佔的空間，輸入的初始數據所佔的空間以及演算法執行過程中所需要的額外空間。
12.能從任意一個結點開始沒有重復的掃描到所有結點的數據結構是循環鏈表。
13.循環隊列是隊列的一種存儲結構
14.演算法的設計要求包括效率與低存儲量，即要考慮演算法的時間復雜度與空間復雜度。
演算法的復雜度包括時間復雜度和空間復雜度。
時間復雜度: 是指執行演算法所需要的計算工作量。
空間復雜度: 一般是指執行這個演算法所需要的內存空間。
15.棧是一種特殊的線性表。鏈式結構把每一個存儲結點分為數據域與指針域，帶鏈的棧可以通過指針域的變化改變原有的棧的組織數據原則; 而順序棧的棧底指針不變，棧頂指針改變。
16.堆排序在最壞的情況下需要比較nlogn次。
快速排序，在最壞情況下需要比較n(n-1)/2次。
順序查找，在最壞情況下需要比較n次。
最壞情況下，二分查找需要log2n(小於n-1)
在長度為n的順序表中尋找最大項/最小項時，比較次數最少為1，最多為n-1。
17.如果一個非空的數據結構滿足下列兩個條件，①有且只有一個根節點 ②每一個結點最多有一個前件，也最多有一個後件，則稱該數據結構為線性結構。如果一個數據結構不是線性結構，則稱為非線性結構。
18.帶鏈棧空的條件是 top=bottom=NULL
19.滿二叉樹也是完全二叉樹，完全二叉樹不一定是滿二叉樹。對於滿二叉樹和完全二叉樹來說，可以按照程序進行順序存儲，不僅節省了空間，又能方便地確定每一個結點的父結點等於左右子結點的位置，但順序存儲結構對於一般的二叉樹不適用。
20.帶鏈棧隊頭指針與隊尾指針相同，且不為空時，隊列元素個數為1; 若為空時，隊列元素個數為0。
帶鏈棧的棧底指針是隨棧的操作而動態變化的。
21.二叉樹的鏈式存儲結構，也稱為二叉鏈表。在二叉樹中，由於每一個元素可以有兩個後件，因此用於存儲二叉樹的存儲結點的指針域有兩個，所以二叉鏈表屬於非線性結構。
22.線性表由一組元素數據元素構成，各元素的數據類型必須相同，矩陣是一個比較復雜的線性表，線性表除了插入和刪除運算之外，還可以查找，排序，分解，合並等。數組是長度固定的線性表。
23.冒泡排序中，在互換兩個相鄰元素時，只能消除一個逆序; 快速排序及希爾排序中，一次交換可以消除多個逆序。
24.二分法檢索的效率比較高，設線性表有n個元素，則最多的比較次數為log2n，最少檢索次數為1。
25.循環鏈表的結構具有以下兩個特點。一，在循環鏈表中，增加了一個表頭結點，其數據域為任意或者根據需要來設置指針域指向線性表的第一個元素的結點。循環鏈表的頭指針指向表頭結點。二、循環鏈表中最後一個節點的指針域不是空，而是指向表頭結點，即在循環鏈表中所有的結點指針構成一個環狀鏈。
26.二叉樹的存儲結構是非線性結構，而完全二叉樹是特殊形態的二叉樹。採用順序存儲的完全二叉樹屬於非線性結構。
27.時間復雜度和計算機運行速度以及存儲空間無關。
演算法的空間復雜度和存儲結構無關。
數據處理效率與數據的存儲結構有關。
28.線性表，向量，棧，隊列都屬於線性結構的順序存儲。
29.循環隊列是隊列的存儲結構。
循環鏈表是另一種形式的念式存儲結構。
(✘循環鏈表是循環隊列的鏈式存儲結構。✘)
30.完全二叉樹的總結點為奇數時，葉子結點是總結點加一再除以二。
31.在實際處理中，可以用一位數組來存儲堆序列中的元素，也可以用完全二叉樹來直觀的表示堆的結構。在用完全二叉樹表示堆時，樹中所有非葉子結點值均不小於其左，右子樹的根結點值，因為堆頂元素必須為序列的n個元素的最大項，因此其中序並不是有序序列。
多重鏈表指表中每個結點由兩個或兩個以上的指針域的鏈表。如果一個非空的數據結構滿足下列兩個條件，①有且只有一個根結點，②每個結點最多有一個前件，也最多有一個後件，則稱該數據結構為線性結構，所以多重鏈表不一定是非線性結構。
在計算機中二叉樹通常採用鏈式存儲結構，對於滿二叉樹和完全二叉樹來說，可以按層次進行順序存儲。
排序二叉樹的中序遍歷序列是有序序列。
32.對於一個固定的規模，演算法所執行的基本運算次數還可能與特定的輸入有關。
33.在線性表中尋找最大項時，平均情況下和最壞情況下比較次數都是n-1。
34.在長度為n的順序表中查找一 個元素， 假沒需要查找的元素有一半的機會在表中，並且如果元素在表中，則出現在表中每個位置上的可能性是相
同的。則在平均情況下需要比較的次數大約為_
A.3n/4 B.n C.n/2 D.n/4
本題的考查知識點是順序表的存儲結構。
因為需要查找的元素有一半機會在表中，所以二分之一的情況下平均比較次數為n/2，另二分之一的情況下平均比較次數為n。總的平均比較次數為(n/2+n) /2-3n/4。
故本題答案為A。
35.設數據結構B=(D, R)，其中
D={a,b,c,d，e，f}
R={(a，b)，(b，c)，(c，d)，(d，e)，(e，f)，(f,a)}該數據結構為
A.線性結構 B.循環隊列
C.循環鏈表 D.非線性結構
本題的考查知識點是數據結構。
如果一個非控的數據結構滿足下列兩個條件: 1) 有且只有一個根節點; 2) 每一一個結點最多有一一個前件，也最多有一一個後件。則稱該數據結構為線性結構。如果一個數據結構不是線性結構，則稱之為非線性結構。
數據結構B=(D, R)中， 每一個結點均有一個前件，不符合「有且只有一個根節點」的條件，所以為非線性結構。故本題答案選D。
36.某帶鏈的隊列初始狀態為front=rear=NULL。經過一系列正常的入隊與退隊操作後，front=rear=10。 該隊列中的元素個數為_
A.1 B.0 C.1或0 D.不確定
本題的考查知識點是帶鏈隊列。
在初始狀態為front=rear=NULL的帶鏈隊列入隊時，如果插入的結點既是隊首結點又是隊尾結點，則rear和front同時指向這個結點;否則在循環隊列的隊尾加入一一個新元素，rear指向新增結點的數據域，rear+1, front不變。 退隊時，在循環隊列的排頭位置退出一個元素並賦給指定的變數，front指向第二個結點的數據域，front+1, rear不變。當front=rear=10時， front和rear同時指向這個唯一 元素，所以該隊列中的元素個數為1。
故本題答案為A。
37.若二叉樹沒有葉子結點，則為空二叉樹。
38.某帶鏈棧的初始狀態為top=bottom=NULL, 經過一系列正 常的入棧與退棧操作後，top=10, bottom=20。 該棧中的元素個數為_____。
A.不確定 B. 10 C.1 D.0
本題考查的知識點是棧。
帶鏈的棧是具有棧屬性的鏈表，線性鏈表的存儲單元是不連續的，為把存儲空間中一-些離散的空閑存 儲結點利用起來，把所有空閑的結點組織成一個帶鏈的棧，稱為可利用棧。
線性鏈表執行刪除操作運算時， 被刪除的結點可以」回收到可利用棧，對應於可利用棧的入棧運算;線性鏈表執行插入運算時，需要一個新的結點，可以在可利用棧中取棧頂結點，對應於可利用棧的退棧運算。
可利用棧的入棧運算和退棧運算只需要改動top指針即可。因為是不連續的存儲空間，所以top指針將不會有規律地連續變化，因此無法據此判斷棧中的元素個數。
所以本題答案為A。
『伍』 求助數據結構題用C語言做
1: 因為要刪除那些即在B表又在C表中的元素，所以A,B，C三個表中都會有這個元素。那麼用指針遍歷A表，用另外兩個指針遍歷B,C。查找B,C中同A的元素，因為3個表都是有序的，可以採用些簡單的比較。找到後刪除。
2：void AE(stack &s)
{
int stack (s); //得到傳遞過來的棧
push(s,3); // 3進棧
push(s,4); // 4進棧
int x=pop(s)+2*pop(s); // x = 3 + 2 * 4
push(s,x); // x 進棧
int a[5]={2,5,8,22,15};
for(j=0;j<5;j++)
push(s,a[i]) // A數組進棧
while(!stackempty(s)) // 直到棧空
printf("%d",2*pop(s)); //輸出 2*棧中每個元素
結果自己想了。
『陸』 數據結構（C語言版） 中一題目的演算法
/***
*
*題目：已知
線性表
中的元素以值遞增有序排列，並以
單鏈表
做存儲結構。試寫一高效的演算法，
*
刪除表中所有值大於
mink
且小於
maxk
的元素（若表中存在這樣的元素）,同時釋放
*
被刪除節點空間，並分析你的演算法的
時間復雜度
（注意：mink
和
maxk
是給定的兩個
*
參變數，它們的值可以和表中的元素相同，也可以不同）
*
****/
#include
#include
#include
"DynaLinkList.h"
void
DelMminMax(LinkList
*L,
int
min,
int
max)
{
LinkList
p
=
(*L)->next,
q
=
(*L),
r;
while
(p
&&
p->data
<=
min)
{
q
=
p;
p
=
p->next;
}
while
(
p
&&
p->data
<
max)
{
r
=
p;
p
=
p->next;
q->next
=
p;
free(r);
}
}
//演算法的時間復雜度為O(n)
int
main()
{
LinkList
L;
ElemType
e,
min,
max;
InitList(&L);
printf("輸入8個元素建立線性表L(元素遞增有序):\n");
for
(int
i=1;
i<=8;
i++)
{
scanf("%d",
&e);
ListInsert(&L,
i,
e);
}
printf("表L是：\n");
ListTraverse(L,
visit);
printf("請輸入待刪除的元素的區間是(min,max):\n");
scanf("%d%d",
&min,
&max);
DelMminMax(&L,min,max);
printf("刪除(%d,%d)之間的元素後表L是：\n",min,max);
ListTraverse(L,
visit);
return
0;
}
『柒』 數據結構(C語言版）課後題－關於串的演算法
演算法如下：
int strReplace(SString S,SString T, SString V)
{/*用串V替換S中的所有子串T */
int pos,i;
pos=strIndex(S,1,T); /*求S中子串T第一次出現的位置*/
if(pos = = 0) return(0);
while(pos!=0) /*用串V替換S中的所有子串T */
{
switch(T.len-V.len)
{
case 0: /*串T的長度等於串V的長度*/
for(i=0;i<=V.len;i++) /*用V替換T*/
S->ch[pos+i]=V.ch[i];
case >0: /*串T的長度大於串V的長度*/
for(i=pos+t.ien;i<S->len;i--) /*將S中子串T後的所有字元
S->ch[i-t.len+v.len]=S->ch[i]; 前移T.len-V.len個位置*/
for(i=0;i<=V.len;i++) /*用V替換T*/
S->ch[pos+i]=V.ch[i];
S->len=S->len-T.len+V.len;
case <0: /*串T的長度小於串V的長度*/
if(S->len-T.len+V.len)<= MAXLEN /*插入後串長小於MAXLEN*/
{ /*將S中子串T後的所有字元後移V.len-T.len個位置*/
for(i=S->len-T.len+V.len;i>=pos+T.len;i--)
S->ch[i]=S->ch[i-T.len+V.len];
for(i=0;i<=V.len;i++) /*用V替換T*/
S->ch[pos+i]=V.ch[i];
S->len=S->len-T.len+V.len; }
else
{ /*替換後串長>MAXLEN,但串V可以全部替換*/
if(pos+V.len<=MAXLEN)
{ for(i=MAXLEN-1;i>=pos+T.len; i--)
S->ch[i]=s->ch[i-T.len+V.len]
for(i=0;i<=V.len;i++) /*用V替換T*/
S->ch[pos+i]=V.ch[i];
S->len=MAXLEN;}
else /*串V的部分字元要舍棄*/
{ for(i=0;i<MAXLEN-pos;i++)
S->ch[i+pos]=V.ch[i];
S->len=MAXLEN;}
}/*switch()*/
pos=StrIndex(S,pos+V.len,T); /*求S中下一個子串T的位置*/
}/*while()*/
return(1);
}/*StrReplace()*/
『捌』 請C語言版數據結構高手幫幫忙！
第一題：
#include<iostream.h>
struct list
{
int num;
struct list *next;
}head={0,0};
void push(struct list *head,int num)
{
struct list *p=head;
while(p->next&&p->next->num<num)
{
p=p->next;
};
struct list *p1=new list;
p1->num=num;
p1->next=p->next;
p->next=p1;
}
void pop(struct list *head,int num1,int num2)//num1<num2
{
struct list *p=head,*q,*q1;
while(p->next&&p->next->num<=num1)
{
p=p->next;
//cout<<endl<<p->num;
};
q=p;
p=p->next;
while (p&&p->num<num2)
{
q1=p;
p=p->next;
delete q1;
}
q->next=p;
}
void print(struct list *head)
{
struct list *p=head->next;
while (p)
{
cout<<p->num<<ends;
p=p->next;
}
}
void main()
{
push(&head,1);
push(&head,4);
push(&head,6);
push(&head,2);
push(&head,3);
push(&head,7);
push(&head,-1);
print(&head);
cout<<endl;
pop(&head,1,6);
print(&head);
}
第二題：
#include<iostream.h>
void change(unsigned int num,char str[])
{
unsigned int temp;
int i=0;
char te[100];
do
{
//temp=num/8;
te[i++]=num%8+48;
num=num/8;
} while(num);
for (int j=0;j<i;j++)
{
str[j]=te[i-j-1];
}
str[j]=0;
}
void main()
{
unsigned int num;
char str[100];
cin>>num;
change(num,str);
cout<<str;
}
第三題：
#include<iostream.h>
struct list
{
int num;
struct list *next;
}head1={0,0},head2={0,0},head3={0,0};
void push(struct list *head,int num)
{
struct list *p=head;
while(p->next&&p->next->num<num)
{
p=p->next;
};
struct list *p1=new list;
p1->num=num;
p1->next=p->next;
p->next=p1;
}
void print(struct list *head)
{
struct list *p=head->next;
while (p)
{
cout<<p->num<<ends;
p=p->next;
}
}
void hebing(struct list *head1,struct list *head2,struct list *head3)
{
struct list *p1=head1->next,*p2=head2->next,*p3=head3,*p4;
while (p1||p2)
{
if (p1&&p2&&p1->num==p2->num)
{
p4=p1;
p1=p1->next;
p2=p2->next;
}
else if (p1&&!p2||((p1&&p2)&&p1->num<p2->num))
{
p4=p1;
p1=p1->next;
}
else
{
p4=p2;
p2=p2->next;
}
struct list *p=new struct list;
p->num=p4->num;
p->next=p3->next;
p3->next=p;
p3=p3->next;
}
}
void main()
{
push(&head1,1);
push(&head1,4);
push(&head1,6);
push(&head1,2);
push(&head1,3);
push(&head1,7);
push(&head1,-1);
push(&head2,3);
push(&head2,1);
push(&head2,9);
push(&head2,-2);
push(&head2,-3);
push(&head2,7);
push(&head2,-1);
print(&head1);
cout<<endl;
print(&head2);
cout<<endl;
hebing(&head1,&head2,&head3);
print(&head3);
}
//最近要考試，有空把後面幾個寫給你。
//妄我專門騰出那麼多時間幫你寫。竟不加分。
『玖』 C數據結構題目
一維數組類型Array1D的定義：
typedef ElemType Array1D[MAXLEN];
void Rotate(Array1D &a, int n, int k)
/* a[n] contains the elements, */
/* rotate them right circlely by k sits */
{
int round,pos1,pos2,i,temp;
for(i=1;i<=k;i++)
if(k%i==0&&n%i==0) round=i;
for(i=0;i<round;i++)
{
pos1=pos2=(n+(i-k)%n)%n;
temp=a[pos1];
for(;;)
{
if(pos1!=i)
{
pos1=(n+(pos1-k)%n)%n;
a[pos2]=a[pos1]; //a[pos1]存放即將替換a[pos2]的數值
pos2=pos1;
}
else break;
}
a[pos1]=temp;
}
}
n=15,k=6,則p=3.
第一條鏈:A[0]->A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0].
第二條鏈:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1].
第三條鏈:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2].
pos1=(n+(pos1-k)%n)%n;逆推上去 9->3->12->6->0 pos1=(n+pos1-k&n)%n
順推 pos1=(pos1+k)%n
只用一個元素大小的附加存儲，元素移動或交換次數為O(n) 所以只能逆推
循環次數為n和k的最大公約數
『拾』 數據結構c語言題目 求大神解一下。
#include<iostream>
usingnamespacestd;
constintMaxSize=200;
classSeqList
{public:
SeqList(inta[],intn);
intLength();
voidInsert(intb[],intlength2);
voidPrintList();
private:
intdata[MaxSize];
intlength;
};
SeqList::SeqList(inta[],intn)
{inti;
if(n>MaxSize)throw"
參數非法
";
for(i=0;i<n;i++)
data[i]=a[i];
length=n;
}
intSeqList::Length()
{
returnlength;
}
voidSeqList::Insert(intb[],intlength2)
{intj,h,i=0;
for(j=0;j<length&&i<length2;++j)
{if(b[i]<data[j])
{for(h=length;h!=j;--h)
data[h]=data[h-1];
data[j]=b[i];
++length;
++i;
}
elseif(j==length-1&&b[i]>data[length-1])
{
data[length]=b[i];
length++;
++i;
}
}
}
voidSeqList::PrintList()
{for(inti=0;i<length;i++)
cout<<data[i]<<"";
cout<<endl;
}
voidmain()
{
inta[6]={1,5,8,10,15,21};
intb[3]={6,13,18};
SeqLists(a,6);
SeqListc(b,3);
cout<<"
合並前的順序表
A"<<endl;
s.PrintList();
cout<<"
合並前的順序表
B"<<endl;
c.PrintList();
cout<<"
合並後的順序表
C"<<endl;
intx=c.Length();
s.Insert(b,x);
s.PrintList();
}