算法与数据结构
① 算法和数据结构有什么区别
其实两者可以说关联不大。
算法就是一个处理的方法，比如大学里基础的排序算法，就是为了完成对一组数据排序。查找算法，就是为了在一个集合中查找需要的项。除此之外，还有很多算法，比方说，加密、压缩、图像处理。
而数据结构就是数据的结构。比方说队列、堆、栈、链表、树等等。
大学里的《算法与数据结构》这门课是个入门的算法课和数据结构课程。教授针对不同的数据结构进行的排序、查找、遍历的不同算法。仅是算法基础，就象大学里都是以C语言作为入门语言一样的。
② 什么是数据结构和算法
数据结构，Data_Structure，其中D是数据元素的集合，R是该集合中所有元素之间的关系的有限集合。数据结构则是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
数据结构是计算机专业学生在大学期间都会学习的一门课程，但是由于课程偏理论，缺乏实际操作的学习体验，而让大家产生了一种“数据结构不重要，我只要学习了Java/C语言/Python同样能敲代码”的错觉，但其实它是一门集技术性、理论性和实践性于一体的课程。
算法是某一系列运算步骤，它表达解决某一类计算问题的一般方法，对这类方法的任何一个输入，它可以按步骤一步一步计算，最终产生一个输出。
小码哥的李明杰也说过所有的计算问题，都离不开要计算的对象或者要处理的信息，如何高效的把它们组织起来，就是数据结构关心的问题，所以算法是离不开数据结构的，这就是数据与算法。
③ 算法和数据结构
给你贴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就行
④ 数据结构和算法有什么关系数据结构就是算法吗
首先你要弄清楚数据结构是什么？数据结构呢其实就是一种存储数据之间的逻辑结构：比如我们学过的线性结构：顺序表啦，链表啦；层次结构：树啦。合适的数据结构可以带来更高的运行效率和存储效率，与相应解决实际问题算法的适应性也就越高，这也就是为什么一些算法指定了数据存储必须以某种特定的数据结才行。一般都是根据合适的数据结构来设计算法，而不是根据算法来设计数据结构。
算法和数据结构往往是互不分开的。离开了算法，数据结构就显得毫无意义，而没有了数据结构算法就没有实现的条件。良好的数据结构思想就是一种高效的算法，但是数据结构不等于算法。只有当数据结构用于处理某个特定问题类型的时候，数据结构才会体现为算法。要想细致的了解，就要多看书，因为这东西毕竟发展了那么多年，一两句话是说不清楚的。想知道更多的数据结构与算法知识吗？可以去了解一下小码哥李明杰。
⑤ 算法和数据结构有什么区别
一、指代不同
1、算法：是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。
2、数据结构：指相互之间存在一种或多种特定关系的数据元素的集合。
二、目的不同
1、算法：指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。
2、数据结构：研究的是数据的逻辑结构和数据的物理结构之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。
三、特点不同
1、算法：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成。
2、数据结构：核心技术是分解与抽象。通过分解可以划分出数据的3个层次；再通过抽象，舍弃数据元素的具体内容，就得到逻辑结构。
⑥ 算法与数据结构
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;
}
⑦ 算法和数据结构的关系
任何程序都是由数据和处理这些数据的方法组成的。
就像烹饪菜肴一样，食材（数据）和烹饪方法（处理这些食材的方法，诸如煎炒煮炸蒸焗焖炖之类的）两者必不可少。而所谓数据结构就是组织（大量）数据的方法，所谓算法就是处理这些数据的方法。
////////////////////////////////////////////////////////////////////////////
杭州巨立安（JulianTec）是杭州市场上
唯一由资深研发工程师所创办的机构。所以：
就专业程度和实在程度而言，杭州巨立安(JulianTec)
是您在arm架构下学习嵌入式Linux研发的上佳指导！