數據結構及演算法

1. 數據結構與演算法

看題可知實際上就是要從表A中刪除出現在表B和表C交集D里的元素
那麼首先肯定是要先確定表B和表C和交集D，由於ABC都是遞增線性表，所以可以確定B和表C和交集D的邊界（可以不用從頭到尾來遍歷表B和表C，屬於優化范疇），之後再遍歷A表刪除其在D中的元素，遍歷時同樣適用上面的邊界處理
既然是要嵌套遍歷三個表那麼時間復雜度自然就是na*nb*nc

2. 演算法和數據結構有什麼區別

一、指代不同

1、演算法：是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令。

2、數據結構：指相互之間存在一種或多種特定關系的數據元素的集合。

二、目的不同

1、演算法：指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始，經過一系列有限而清晰定義的狀態，最終產生輸出並停止於一個終態。

2、數據結構：研究的是數據的邏輯結構和數據的物理結構之間的相互關系，並對這種結構定義相適應的運算，設計出相應的演算法，並確保經過這些運算以後所得到的新結構仍保持原來的結構類型。

三、特點不同

1、演算法：演算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步驟，即每個計算步驟都可以在有限時間內完成。

2、數據結構：核心技術是分解與抽象。通過分解可以劃分出數據的3個層次；再通過抽象，舍棄數據元素的具體內容，就得到邏輯結構。

3. 數據結構與演算法

赤水殘陽 的說法有問題，什麼叫學好數據結構？你能用數據結構的知識實現STL庫、Boost庫、解決實際編程問題。

①要學好數據結構，至少要學好一門計算機語言。

②所以如果你的計算機語言是C++，那麼不學好C++，數據結構絕對無法學好（鐵定）。

③為什麼？
計算機開發領域專業核心課程就幾門：數據結構、操作系統原理、資料庫系統原理、匯編語言程序設計。

而數據結構是這另外幾門核心課程的基礎。
數據結構最終是為了實現，如果你不邊學邊實驗C++代碼，那麼學起來就如走馬觀花，無法從細節上庖丁解牛。

到時候，數據結構會出很多編程要求，假設一個人指針沒學好，單向鏈表、雙向鏈表、二叉樹、圖都沒法編程。

不過，就算你C++之前沒怎麼投入時間，放假半個月到一個月集中精力投入時間，也是可以彌補的，甚至比你們班大多數做得更好：不斷編程實踐。

4. 數據結構和演算法有什麼關系數據結構就是演算法嗎

首先你要弄清楚數據結構是什麼？數據結構呢其實就是一種存儲數據之間的邏輯結構：比如我們學過的線性結構：順序表啦，鏈表啦；層次結構：樹啦。合適的數據結構可以帶來更高的運行效率和存儲效率，與相應解決實際問題演算法的適應性也就越高，這也就是為什麼一些演算法指定了數據存儲必須以某種特定的數據結才行。一般都是根據合適的數據結構來設計演算法，而不是根據演算法來設計數據結構。

演算法和數據結構往往是互不分開的。離開了演算法，數據結構就顯得毫無意義，而沒有了數據結構演算法就沒有實現的條件。良好的數據結構思想就是一種高效的演算法，但是數據結構不等於演算法。只有當數據結構用於處理某個特定問題類型的時候，數據結構才會體現為演算法。要想細致的了解，就要多看書，因為這東西畢竟發展了那麼多年，一兩句話是說不清楚的。想知道更多的數據結構與演算法知識嗎？可以去了解一下小碼哥李明傑。

5. 演算法與數據結構

ListNode.h

template<typename Type> class SingleList;

template<typename Type> class ListNode{
private:
friend typename SingleList<Type>;

ListNode():m_pnext(NULL){}
ListNode(const Type item,ListNode<Type> *next=NULL):m_data(item),m_pnext(next){}
~ListNode(){
m_pnext=NULL;
}

public:
Type GetData();
friend ostream& operator<< <Type>(ostream& ,ListNode<Type>&);

private:
Type m_data;
ListNode *m_pnext;
};

template<typename Type> Type ListNode<Type>::GetData(){
return this->m_data;
}

template<typename Type> ostream& operator<<(ostream& os,ListNode<Type>& out){
os<<out.m_data;
return os;
}

SingleList.h

#include "ListNode.h"

template<typename Type> class SingleList{
public:
SingleList():head(new ListNode<Type>()){}
~SingleList(){
MakeEmpty();
delete head;
}

public:
void MakeEmpty(); //make the list empty
int Length(); //get the length
ListNode<Type> *Find(Type value,int n); //find thd nth data which is equal to value
ListNode<Type> *Find(int n); //find the nth data
bool Insert(Type item,int n=0); //insert the data in the nth position
Type Remove(int n=0); //remove the nth data
bool RemoveAll(Type item); //remove all the data which is equal to item
Type Get(int n); //get the nth data
void Print(); //print the list

private:
ListNode<Type> *head;
};

template<typename Type> void SingleList<Type>::MakeEmpty(){
ListNode<Type> *pdel;
while(head->m_pnext!=NULL){
pdel=head->m_pnext;
head->m_pnext=pdel->m_pnext;
delete pdel;
}
}

template<typename Type> int SingleList<Type>::Length(){
ListNode<Type> *pmove=head->m_pnext;
int count=0;
while(pmove!=NULL){
pmove=pmove->m_pnext;
count++;
}
return count;
}

template<typename Type> ListNode<Type>* SingleList<Type>::Find(int n){
if(n<0){
cout<<"The n is out of boundary"<<endl;
return NULL;
}
ListNode<Type> *pmove=head->m_pnext;
for(int i=0;i<n&&pmove;i++){
pmove=pmove->m_pnext;
}
if(pmove==NULL){
cout<<"The n is out of boundary"<<endl;
return NULL;
}
return pmove;
}

template<typename Type> ListNode<Type>* SingleList<Type>::Find(Type value,int n){
if(n<1){
cout<<"The n is illegal"<<endl;
return NULL;
}
ListNode<Type> *pmove=head;
int count=0;
while(count!=n&&pmove){
pmove=pmove->m_pnext;
if(pmove->m_data==value){
count++;
}

}
if(pmove==NULL){
cout<<"can't find the element"<<endl;
return NULL;
}
return pmove;
}

template<typename Type> bool SingleList<Type>::Insert(Type item, int n){
if(n<0){
cout<<"The n is illegal"<<endl;
return 0;
}
ListNode<Type> *pmove=head;
ListNode<Type> *pnode=new ListNode<Type>(item);
if(pnode==NULL){
cout<<"Application error!"<<endl;
return 0;
}
for(int i=0;i<n&&pmove;i++){
pmove=pmove->m_pnext;
}
if(pmove==NULL){
cout<<"the n is illegal"<<endl;
return 0;
}
pnode->m_pnext=pmove->m_pnext;
pmove->m_pnext=pnode;
return 1;
}

template<typename Type> bool SingleList<Type>::RemoveAll(Type item){
ListNode<Type> *pmove=head;
ListNode<Type> *pdel=head->m_pnext;
while(pdel!=NULL){
if(pdel->m_data==item){
pmove->m_pnext=pdel->m_pnext;
delete pdel;
pdel=pmove->m_pnext;
continue;
}
pmove=pmove->m_pnext;
pdel=pdel->m_pnext;
}
return 1;
}

template<typename Type> Type SingleList<Type>::Remove(int n){
if(n<0){
cout<<"can't find the element"<<endl;
exit(1);
}
ListNode<Type> *pmove=head,*pdel;
for(int i=0;i<n&&pmove->m_pnext;i++){
pmove=pmove->m_pnext;
}
if(pmove->m_pnext==NULL){
cout<<"can't find the element"<<endl;
exit(1);
}
pdel=pmove->m_pnext;
pmove->m_pnext=pdel->m_pnext;
Type temp=pdel->m_data;
delete pdel;
return temp;
}

template<typename Type> Type SingleList<Type>::Get(int n){
if(n<0){
cout<<"The n is out of boundary"<<endl;
exit(1);
}
ListNode<Type> *pmove=head->m_pnext;
for(int i=0;i<n;i++){
pmove=pmove->m_pnext;
if(NULL==pmove){
cout<<"The n is out of boundary"<<endl;
exit(1);
}
}
return pmove->m_data;
}

template<typename Type> void SingleList<Type>::Print(){
ListNode<Type> *pmove=head->m_pnext;
cout<<"head";
while(pmove){
cout<<"--->"<<pmove->m_data;
pmove=pmove->m_pnext;
}
cout<<"--->over"<<endl<<endl<<endl;
}

6. 什麼是數據結構和演算法

數據結構，Data_Structure，其中D是數據元素的集合，R是該集合中所有元素之間的關系的有限集合。數據結構則是指相互之間存在一種或多種特定關系的數據元素的集合。通常情況下，精心選擇的數據結構可以帶來更高的運行或者存儲效率。數據結構往往同高效的檢索演算法和索引技術有關。

數據結構是計算機專業學生在大學期間都會學習的一門課程，但是由於課程偏理論，缺乏實際操作的學習體驗，而讓大家產生了一種「數據結構不重要，我只要學習了Java/C語言/Python同樣能敲代碼」的錯覺，但其實它是一門集技術性、理論性和實踐性於一體的課程。

演算法是某一系列運算步驟，它表達解決某一類計算問題的一般方法，對這類方法的任何一個輸入，它可以按步驟一步一步計算，最終產生一個輸出。

小碼哥的李明傑也說過所有的計算問題，都離不開要計算的對象或者要處理的信息，如何高效的把它們組織起來，就是數據結構關心的問題，所以演算法是離不開數據結構的，這就是數據與演算法。

7. 演算法和數據結構

給你貼USACO這一題的通關報告，英文的啊：

We use a recursive complete search to simply test all boards. The search proceeds by trying to put one checker in each row. We keep track of which columns and diagonals already have checkers on them in the "col", "updiag", and "downdiag" arrays.

Since we generate solutions in increasing order, we record the first 3 in the "sol" array.

Symmetry enables us to count the first half of the solutions double and avoid calculating the second half. An exception happens when N is odd; the odd row needs to be counted once.

The N>6 lines get the program out of trouble when N==6, because at that point, the first 3 solutions include one of the symmetric answers.

Since we number rows from 0 to N-1 rather than 1 to N, we need to add 1 to each digit as we print (in "printsol").

/*
TASK: checker
LANG: C
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define MAXN 16

int n;
int nsol, nprinted;
char row[MAXN];
FILE *fout;

void
solution() {
int i;
for(i=0; i<n; i++) {
if(i != 0) fprintf(fout, " ");
fprintf(fout, "%d", row[i]+1);
}
fprintf(fout, "\n");
}

/* Keep track of whether there is a checker on each column, and diagonal. */
char col[MAXN]; /* (i, j) -> j */
char updiag[2*MAXN]; /* (i, j) -> i+j */
char downdiag[2*MAXN]; /* (i, j) -> i-j + N */

/*
* Calculate number of ways to place checkers
* on each row of the board starting at row i and going to row n.
*/
void
nway(i, lim) {
int j;

if(i == n) {
nsol++;
if (n > 6 && row[0] < n/2) nsol++;
if (nprinted++ < 3) solution();
return;
}

for(j=0; j<lim; j++){
if(!col[j] && !updiag[i+j] && !downdiag[i-j+MAXN]){
row[i] = j;

col[j]++;
updiag[i+j]++;
downdiag[i-j+MAXN]++;

nway(i+1,n);

col[j]--;
updiag[i+j]--;
downdiag[i-j+MAXN]--;
}
}
}

main(void) {
FILE *fin = fopen("checker.in", "r");
fout = fopen("checker.out", "w");
fscanf(fin, "%d", &n);
nway(0, n>6?(n+1)/2:n);
fprintf(fout, "%d\n", nsol);
exit (0);
}

Clever Michael Rybak's Solution
The Ukraine's Michael Rybak removed the 'this row is used' search (which obviously at the end of the recursion is a lot of wasted iterating) and replaced it with a list of valid rows to use (which presumably has but a single element at the end of the recursion). His program runs almost 4x faster then N==13.
Program Checker;
Var diagPLUS: Array[2..30] Of Boolean;
diagMINUS: Array[-15..15] Of Boolean;
sol: Array[1..15] Of ShortInt;
i,n,found: Longint;
stop: Boolean;
next,prev: Array[0..16] Of ShortInt;
sy: ShortInt;

Procere Search0(y:ShortInt);
Var x,i:ShortInt;
Begin
If stop Then Exit;
If y=n+1 Then Begin
Inc(found);
If found<4 Then Begin
For i:=1 To n-1 Do
Write(sol[i],' ');
Writeln(sol[n]);
End Else
stop:=True;
Exit;
End;
If sol[y]<>0 Then Begin
Search0(y+1);
Exit;
End;
x:=next[0];
While x<=n Do Begin
If Not ((diagPLUS[x+y]) Or (diagMINUS[x-y])) Then Begin
sol[y]:=x;
diagPLUS[x+y]:=True;
diagMINUS[x-y]:=True;
next[prev[x]]:=next[x];
prev[next[x]]:=prev[x];
Search0(y+1);
diagPLUS[x+y]:=False;
diagMINUS[x-y]:=False;
next[prev[x]]:=x; prev[next[x]]:=x;
End;
x:=next[x];
End;
sol[y]:=0;
End;

Procere Search;
Var x:ShortInt;
Begin
If sy=n+1 Then Begin
Inc(found);
Exit;
End;
If sol[sy]<>0 Then Begin
Inc(sy);
Search;
Dec(sy);
Exit;
End;
x:=next[0];
While x<=n Do Begin
If Not ((diagPLUS[x+sy]) Or (diagMINUS[x-sy])) Then Begin
sol[sy]:=x;
diagPLUS[x+sy]:=True;
diagMINUS[x-sy]:=True;
next[prev[x]]:=next[x];
prev[next[x]]:=prev[x];
Inc(sy);
Search;
Dec(sy);
diagPLUS[x+sy]:=False;
diagMINUS[x-sy]:=False;
next[prev[x]]:=x;
prev[next[x]]:=x;
End;
x:=next[x];
End;
sol[sy]:=0;
End;

Procere Search2(miny:Longint);
Var x,y,i:ShortInt;
curf:Longint;
Begin
x:=n Div 2+1;
For y:=miny To n Div 2 Do
If Not (diagPLUS[x+y] Or diagMINUS[x-y]) Then Begin
curf:=found;
sol[y]:=x;
diagPLUS[x+y]:=True;
diagMINUS[x-y]:=True;
next[prev[x]]:=next[x]; prev[next[x]]:=prev[x];
sy:=1;
Search;
If y>miny Then
found:=found+(found-curf);
sol[y]:=0;
diagPLUS[x+y]:=False;
diagMINUS[x-y]:=False;
next[prev[x]]:=x; prev[next[x]]:=x;
End;
End;

Procere Search1;
Var x,y,i:ShortInt;
Begin
y:=n Div 2+1;
For x:=1 To n Div 2 Do Begin
sol[y]:=x;
diagPLUS[x+y]:=True;
diagMINUS[x-y]:=True;
next[prev[x]]:=next[x]; prev[next[x]]:=prev[x];
Search2(x);
diagPLUS[x+y]:=False;
diagMINUS[x-y]:=False;
next[prev[x]]:=x; prev[next[x]]:=x;
End;
sol[y]:=0;
found:=found*4;
x:=n Div 2+1;
sol[y]:=x;
diagPLUS[x+y]:=True;
diagMINUS[x-y]:=True;
next[prev[x]]:=next[x]; prev[next[x]]:=prev[x];
sy:=1;
Search;
End;

Begin
Assign(Input,'checker.in'); Reset(Input);
Assign(Output,'checker.out'); Rewrite(Output);
Read(n);
found:=0;
FillChar(diagPLUS,SizeOf(diagPLUS),False);
FillChar(diagMINUS,SizeOf(diagMINUS),False);
FillChar(sol,SizeOf(sol),0);
For i:=0 To n+1 Do Begin
prev[i]:=i-1;
next[i]:=i+1;
End;
If n Mod 2=0 Then Begin
stop:=False;
Search0(1);
sy:=1;
found:=0;
Search;
End Else Begin
stop:=False;
Search0(1);
found:=0;
Search1;
End;
Writeln(found);
Close(Output);
End.

Clever Romanian Solution
Submitted by several from Romania, this solution uses bitmasks instead of a list to speed searching:
#include <stdio.h>
#include <stdlib.h>
#include <fstream.h>
#define MAX_BOARDSIZE 16
typedef unsigned long SOLUTIONTYPE;
#define MIN_BOARDSIZE 6
SOLUTIONTYPE g_numsolutions = 0;

void Nqueen(int board_size) {
int aQueenBitRes[MAX_BOARDSIZE]; /* results */
int aQueenBitCol[MAX_BOARDSIZE]; /* marks used columns */
int aQueenBitPosDiag[MAX_BOARDSIZE]; /* marks used "positive diagonals" */
int aQueenBitNegDiag[MAX_BOARDSIZE]; /* marks used "negative diagonals" */
int aStack[MAX_BOARDSIZE + 2]; /* a stack instead of recursion */
int *pnStack;

int numrows = 0; /* numrows rendant - could use stack */
unsigned int lsb; /* least significant bit */
unsigned int bitfield; /* set bits denote possible queen positions */
int i;
int odd = board_size & 1; /* 1 if board_size odd */
int board_m1 = board_size - 1; /* board size - 1 */
int mask = (1 << board_size) - 1; /* N bit mask of all 1's */

aStack[0] = -1; /* sentinel signifies end of stack */
for (i = 0; i < (1 + odd); ++i) {
bitfield = 0;
if (0 == i) {
int half = board_size>>1; /* divide by two */
bitfield = (1 << half) - 1;
pnStack = aStack + 1; /* stack pointer */
aQueenBitRes[0] = 0;
aQueenBitCol[0] = aQueenBitPosDiag[0] = aQueenBitNegDiag[0] = 0;
} else {
bitfield = 1 << (board_size >> 1);
numrows = 1; /* prob. already 0 */

aQueenBitRes[0] = bitfield;
aQueenBitCol[0] = aQueenBitPosDiag[0] = aQueenBitNegDiag[0] = 0;
aQueenBitCol[1] = bitfield;

aQueenBitNegDiag[1] = (bitfield >> 1);
aQueenBitPosDiag[1] = (bitfield << 1);
pnStack = aStack + 1; /* stack pointer */
*pnStack++ = 0; /* row done -- only 1 element & we've done it */
bitfield = (bitfield - 1) >> 1;
/* bitfield -1 is all 1's to the left of the single 1 */
}
for (;;) {
lsb = -((signed)bitfield) & bitfield;
/* this assumes a 2's complement architecture */
if (0 == bitfield) {
bitfield = *--pnStack; /* get prev. bitfield from stack */
if (pnStack == aStack) /* if sentinel hit.... */
break;
--numrows;
continue;
}
bitfield &= ~lsb; /* bit off -> don't try it again */
aQueenBitRes[numrows] = lsb; /* save the result */
if (numrows < board_m1) { /* more rows to process? */
int n = numrows++;
aQueenBitCol[numrows] = aQueenBitCol[n] | lsb;
aQueenBitNegDiag[numrows] = (aQueenBitNegDiag[n] | lsb) >> 1;
aQueenBitPosDiag[numrows] = (aQueenBitPosDiag[n] | lsb) << 1;
*pnStack++ = bitfield;
bitfield = mask & ~(aQueenBitCol[numrows] |
aQueenBitNegDiag[numrows] | aQueenBitPosDiag[numrows]);
continue;
} else {
++g_numsolutions;
bitfield = *--pnStack;
--numrows;
continue;
}
}
}
g_numsolutions *= 2;
}

int main(int argc, char** argv) {
ifstream f("checker.in");
ofstream g("checker.out");
long boardsize,s[20],ok,k,i,sol=0;
f>>boardsize;
Nqueen (boardsize);
k=1;
s[k]=0;
while (k>0) {
ok=0;
while(s[k]<boardsize && !ok) {
ok=1;
s[k]++;
for(i=1;i<k;i++)
if(s[i]==s[k] || abs(s[k]-s[i])==abs(k-i))
ok=0;
}
if(sol!=3)
if(!ok)
k--;
else
if(k==boardsize) {
for(i=1;i<boardsize;i++) {
for(int j=1;j<=boardsize;j++)
if(s[i]==j) g<<j<<" ";
}
for(i=1;i<=boardsize;i++)
if(s[boardsize]==i) g<<i;
g<<"\n";
sol++;
} else {
k++;
s[k]=0;
} else break;
}
g<<g_numsolutions<<"\n";
f.close();
g.close();
return 0;
}

這些程序你要先輸入一個數字，皇後數量，輸入8就行

8. 數據結構和演算法

數據結構和演算法不是一個概念。
Data structure
and
Algorithm

書名字是兩種的話說裡面都有，一般的話這兩種是分不開的。如果只說數據結構的話書中比名字是兩種的少一部分內容，應該可以這樣理解。
單純的演算法有動態規劃，貪心，枚舉之類的，不需要比較麻煩的數據結構。
另外大部分的演算法都需要數據結構輔助，比如說搜索（隊列，棧或其它），單源最短路演算法（需要圖的結構，這部分應該屬於數據結構與演算法），還有些比較麻煩的。

數據結構中一般會存在演算法，比如二叉樹，平衡二叉樹，堆，棧，隊列……還有些比較麻煩的，線段樹，紅黑樹…………這之類的，裡面的數據結構的操作往往會涉及到一些精心設計的演算法來達到高效的目的。

二者不能是包含關系。

9. 什麼是數據結構和演算法

演算法就是計算機處理解決問題的計算機能理解的方法。
比如算一個階乘 , 計算機的演算法就是寫一個循環,從高到底, 一直乘下去,直到 1 為止。
復雜的演算法比如一個強連通帶權網路,求兩點間的最短路徑,這個很有用啊....比如採用廣度優先演算法,或深度優先演算法
數據結構指數據在計算機中存儲存在的方式。
比如文件在硬碟中,有二進制,文本等形式存放, 程序中的一組數字可能放在數組裡面,也可能在棧裡面,也肯能在鏈表裡面