数据结构及算法

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 为止。
复杂的算法比如一个强连通带权网络,求两点间的最短路径,这个很有用啊....比如采用广度优先算法,或深度优先算法
数据结构指数据在计算机中存储存在的方式。
比如文件在硬盘中,有二进制,文本等形式存放, 程序中的一组数字可能放在数组里面,也可能在栈里面,也肯能在链表里面