經典數據結構演算法問題

Ⅰ 數據結構與演算法的問題

struct List
{
int data ;
List *next ;
};
typedef struct List List ;

List * ReverseList(List *head)
{
if ( head == NULL || head->next == NULL )
return head;
List *p1 = head ;
List *p2 = p1->next ;
List *p3 = p2->next ;
p1->next = NULL ;
while ( p3 != NULL )
{
p2->next = p1 ;
p1 = p2 ;
p2 = p3 ;
p3 = p3->next ;
}
p2->next = p1 ;
head = p2 ;
return head ;
}
或者這樣吧：
template <class T> class tb
{
public:

//UserInterFace BEGIN:

bool AddData(const T dt,const int position);
bool DeteleData(const int position);

T GetData(const int poistition);

bool Reverse();

tb(int maxp=1) {max=maxp;d=false;ExpandSpace();count=0;}

//UserInterFace END;

private:
T *d;
int count;
int max;
T *newspace;

bool ExpandSpace();
bool ShrinkSpace();
bool DataMove();
};

template<class T> bool tb<T>::ExpandSpace()
{
max++;

int nim=static_cast<int>(pow(2.0,max));
try
{
newspace = new T[nim];
}
catch(...)
{
return false;
}

return DataMove();

}
template<class T> bool tb<T>::ShrinkSpace()
{
if (max>0) max--;
else return false;

try
{
newspace = new T[static_cast<int>(pow(2,max))];
}
catch(...)
{
return false;
}

return DataMove();

}

template<class T> bool tb<T>::DataMove()
{
try
{
if(d)
{
for(int i=1;i<=count;i++)
{
newspace[i-1]=d[i-1];
}
delete[] d;
}

d=newspace;

}
catch(...)
{
return false;
}

return true;
}

template<class T> bool tb<T>::AddData(const T dt,const int position)
{

if(count==pow(2,max))
{
if(ExpandSpace()!=true) return false;

}

int pos=0;
count++;

if(position==0) pos=count-1;
else pos=position;

if(position>count || position <0) return false;

for(int i=count;i>=pos;i--)
{
d[i+1]=d[i];
}

d[position]=dt;

return true;
}

template<class T> bool tb<T>::DeteleData(const int position)
{
if(count==pow(2,max-1))
{
if(ShrinkSpace()!=true) return false;
}

if(position>count || position <0) return false;

for(int i=count;i>=position;i--)
{
d[i]=d[i+1];
}

count--;

return true;
}

template <class T> T tb<T>::GetData(const int position)
{
if(position>count ||position<0) return *d;
else return *(d+position-1);
}

template <class T> bool tb<T>::Reverse()
{
try
{
for(int i=0;i<=count/2;i++)
{
int temp=d[i];
d[i]=d[count-i];
d[count-i]=temp;
}
}
catch(...)
{
return false;
}

return true;
}

int main(int argc, char* argv[])
{
tb<int> lp;

for(int i=1;i<=10;i++)
{
int t;
cout<<lp.AddData(i,1)<<endl;
}
lp.Reverse();

for(int i=2;i<=10;i++)
{
int p = lp.GetData(i);
cout<<i<<'\t'<<p<<endl;
}

while(getchar());
return 0;
}

Ⅱ 數據結構經典演算法有哪些

二叉樹遍歷：
status initqueue(Queue &Q)
{//初始化一個空隊列
Q.base=(QElemtype *)malloc(MAXSIZE*sizeof(QElemtype));
if(!Q.base)
exit(OVERFLOW);
Q.front=Q.rear=0;
return OK;
}

status inqueue(Queue &Q,BiTree e)
{//將元素e入隊
if((Q.rear+1)%MAXSIZE==Q.front)
return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXSIZE;
return OK;
}

status outqueue(Queue &Q,BiTree &e)
{//刪除隊頭元素，並用e返回其值
if(Q.front==Q.rear)
return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXSIZE;
return OK;
}

status emptyqueue(Queue Q)
{//若隊列空，返回TRUE，否則返回FALSE
if(Q.front==Q.rear)
return TRUE;
return FALSE;
}

//以下是二叉樹的演算法
void creattree(BiTree &t)
{//先序順序建立二叉樹t
char ch;
ch=getchar();
if(ch==' ')
{
t=NULL;
return;
}
t=(BiTree)malloc(sizeof(BiNode));
if(!t) exit(OVERFLOW);
t->data=ch;
creattree(t->lchild);
creattree(t->rchild);
}
void print(TElemtype e)
{
printf("%c",e);
}
void pretraverse(BiTree t, void (*visit)(TElemtype e))
{//先序遍歷二叉樹t
if(t)
{
(*visit)(t->data);
pretraverse(t->lchild,visit);
pretraverse(t->rchild,visit);
}
}

void intraverse(BiTree t, void (*visit)(TElemtype e))
{//中序遍歷二叉樹t
if(t)
{
intraverse(t->lchild,visit);
(*visit)(t->data);
intraverse(t->rchild,visit);
}
}

void posttraverse(BiTree t, void (*visit)(TElemtype e))
{//後序遍歷二叉樹t
if(t)
{
posttraverse(t->lchild,visit);
posttraverse(t->rchild,visit);
(*visit)(t->data);
}
}

void leveltraverse(BiTree t, void (*visit)(TElemtype e))
{//層次遍歷二叉樹t
BiNode *p;
Queue Q;
//if(!t) return;
initqueue(Q);
p=t;
inqueue(Q,p);
while(!emptyqueue(Q))
{
outqueue(Q,p);
if(p)
{

(*visit)(p->data);
inqueue(Q,p->lchild);
inqueue(Q,p->rchild);
}
}

}

void destroytree(BiTree &t)
{
if(t==NULL) return;
else if(t->lchild==NULL&&t->rchild==NULL)
{
free(t);
return;
}
else{
destroytree(t->lchild);
destroytree(t->rchild);
free(t);
return;
}
}

Ⅲ 關於數據結構排序演算法的問題

選擇排序

插入排序：每次比較後最多移掉一個逆序，因此與冒泡排序的效率相同。但它在速度上還是要高點，這是因為在冒泡排序下是進行值交換，而在插入排序下是值移動，所以直接插入排序將要優於冒泡排序。直接插入法也是一種對數據的有序性非常敏感的一種演算法。在有序情況下只需要經過n-1次比較，在最壞情況下，將需要n(n-1)/2次比較。

選擇排序：簡單的選擇排序，它的比較次數一定：n(n-1)/2。也因此無論在序列何種情況下，它都不會有優秀的表現（從上100K的正序和反序數
據可以發現它耗時相差不多，相差的只是數據移動時間），可見對數據的有序性不敏感。它雖然比較次數多，但它的數據交換量卻很少。所以我們將發現它在一般情
況下將快於冒泡排序。

冒泡排序：在最優情況下只需要經過n-1次比較即可得出結果，（這個最優情況那就是序列己是正序，從100K的正序結果可以看出結果正是如此），但在最壞情況下，即倒序（或一個較小值在最後），下沉演算法將需要n(n-1)/2次比較。所以一般情況下，特別是在逆序時，它很不理想。它是對數據有序性非常敏感的排序演算法。
堆排序：由於它在直接選擇排序的基礎上利用了比較結果形成。效率提高很大。它完成排序的總比較次數為O(nlog2n)。它是對數據的有序性不敏感的一種演算法。但堆排序將需要做兩個步驟：－是建堆，二是排序（調整堆）。所以一般在小規模的序列中不合適，但對於較大的序列，將表現出優越的性能。

基數排序：在程序中採用的是以數值的十進制位分解，然後對空間採用一次性分配，因此它需要較多的輔助空間(10*n+10), （但我們可以進行其它分解，如以一個位元組分解，空間採用鏈表將只需輔助空間n+256）。基數排序的時間是線性的(即O(n))。由此可見，基數排序非常吸引人，但它也不是就地排序，若節點數據量大時宜改為索引排序。但基數排序有個前提，要關鍵字能象整型、字元串這樣能分解，若是浮點型那就不行了。

Ⅳ 數據結構演算法有哪些

數據結構是一門研究非數值計算的程序設計問題中的操作對象，以及它們之間的關系和操作等相關問題的學科。

可以理解為：程序設計 = 數據結構 + 演算法

數據結構演算法具有五個基本特徵：輸入、輸出、有窮性、確定性和可行性。

1、輸入：一個演算法具有零個或者多個輸出。以刻畫運算對象的初始情況，所謂0個輸入是指演算法本身定出了初始條件。後面一句話翻譯過來就是，如果一個演算法本身給出了初始條件，那麼可以沒有輸出。比如，列印一句話：NSLog(@"你最牛逼！");

2、輸出：演算法至少有一個輸出。也就是說，演算法一定要有輸出。輸出的形式可以是列印，也可以使返回一個值或者多個值等。也可以是顯示某些提示。

3、有窮性：演算法的執行步驟是有限的，演算法的執行時間也是有限的。

4、確定性：演算法的灶舉每個步驟都有確定的含義，不會出現二義性。

5、可行性：演算法是可用的，也就是能夠解決當前問題。慧辯弊

數據結果的基本演算法有：

1、圖搜索（廣度優先、深度優先）深度優前族先特別重要

2、排序

3、動態規劃

4、匹配演算法和網路流演算法

5、正則表達式和字元串匹配

6、三路劃分-快速排序

7、合並排序（更具擴展性，復雜度類似快速排序）

8、DF/BF 搜索 （要知道使用場景）

9、Prim / Kruskal （最小生成樹）

10、Dijkstra （最短路徑演算法）

11、選擇演算法

Ⅳ 數據結構串匹配十大經典演算法

1。
int Index(SString S,SString T,int pos)
{
//返回子串T在主串S中第pos個字元之後的位置。若不存在，則函數值為0。
//其中，T非空，1〈=pos<=Stringlength(S).
i=pos;j=1;
while(i<=S[0] && j<=T[0])
{
if (S[i]== T[i]) {++i;++j;}
else { i=i-j+2;j=1;}
}
if(j>T[0]) return i-T[0];
else return 0;
}//Index
2。

int Index-KMP(SString S,SString T,int pos)
{
//利用模式串T的next函數值求T在主串S中第pos 個字元之後的位置的KMP演算法。其中，T非空，1<=pos<=Stringlength(S)
i=pos;
j=1;
while(i<=S[0] && j<=T[0])
{
if (j==0 || S[i]==T[j]) {++i; ++j;}
else j=next[j];
}
if (j>T[0]) return i-T[0];
else return 0;
//Index}
下面是next函數：
void next(SString S,ing next[])
{
i=1;
next[1]=0;
j=0;
while (i<T[0])
{
if (j==0 || T[i]==T[j]){ ++i; ++j;
next[j]=i;}
else j=next[j];
}
}//next

我現在只有這兩個答案。

Ⅵ 請教4道數據結構的演算法題

按順序從上到下：

1.

#include<stdio.h>
#include<stdlib.h>
structSet{
intelement;
structSet*next;
}

Set*Intersection(Set純橘*A,Set*B)
{
Set*p,*q,*node=NULL;
if(!A||!B)returnNULL;
p=A;
q=B;
while(q)
{
if(p.element==q.element)
{
break;
}
q=q->next;
}
if(q)
{
洞禪node=(Set*)malloc(sizeof(Set));
if(node)
{
node->做顫團element=p.element;
node->next=Intersection(p->next,B);
}else
{
returnNULL;
}
}
else
{
returnIntersection(p->next,B);
}
returnnode;
}

intCardinality(Set*A)
{
inti=0;
Set*p;
p=A;
while(p)
{
p=p->next;
i++;
}
returni;
}

2.

#include<stdio.h>
#include<stdlib.h>
typedefstruct_Node
{
	charChar;
	intNum;
	struct_Node*next;	
}Node;
intis_same_char(char,char);
Node*Statistics(char*Str)
{
	char*string;
	Node*p,*q,*head,*tmp,*pre;
	head=(Node*)malloc(sizeof(Node));
	head->next=NULL;
	head->Num=0;
	p=head;printf("%s
",Str);
	string=Str;
	while(*string!='')
	{
		tmp=head;
		while(tmp)
		{
			if(is_same_char(tmp->Char,*string)==0)
			{
				tmp->Num++;
				break;
			}
			tmp=tmp->next;
		}
		if(!tmp)
		{
			p->Char=*string;
			p->Num=1;
			q=(Node*)malloc(sizeof(Node));
			q->next=p->next;
			p->next=q;
			pre=p;
			p=q;
		}
		string++;
	}
	//刪除最後一個無效節點
	pre->next=NULL;
	free(p);
	returnhead;
}
doubleProbability(Node*List,charChar)
{
	doubletotal=0.0;
	intcount=0;
	Node*p;
	if(List==NULL)return-1;
	p=List;
	while(p)
	{
		if(is_same_char(p->Char,Char)==0)
		{
			count=p->Num;
		}
		total+=p->Num;
		printf("%c%d
",p->Char,p->Num);
		p=p->next;
	}
	returncount/total;
}
//字母變為小寫比較，其他字元ASCII碼比較
intis_same_char(chars,chart)
{
	if(t>96&&t<123)t-=32;
	if(s>96&&s<123)s-=32;
	returns-t;
}
intmain(intargc,charconst*argv[])
{
	Node*L1;
	L1=Statistics("3Ada3#helloworld");
	printf("
%f",Probability(L1,'l'));
	return0;
}

3.

#include<stdio.h>
#include<stdlib.h>
typedefstruct_Element
{
	intelement;
	struct_Element*next;	
}Element;
typedefstruct_Elements
{
	intelement1,element2;
	struct_Elements*next;	
}Elements;
intNumber(Elements*C)
{
	Elements*p;
	inti=0;
	p=C;
	while(p)
	{
		p=p->next;
		i++;
	}
	returni;
}
Elements*Descartes(Element*A,Element*B)
{
	Elements*q,*node,*head;
	Element*p;
	if(A==NULL||B==NULL)returnNULL;
	p=B;
	head=(Elements*)malloc(sizeof(Elements));
	head->next=NULL;
	q=head;
	while(p)
	{
		q->element1=A->element;
		q->element2=p->element;
		node=(Elements*)malloc(sizeof(Elements));
		node->next=q->next;
		q->next=node;
		q=node;
		p=p->next;
	}
	q->next=Descartes(A->next,B);
	returnhead;
}
intmain(intargc,charconst*argv[])
{
	/*code*/
	return0;
}

4.

#include<stdio.h>
#include<stdlib.h>
typedefstruct_Element
{
	intelement;
	struct_Element*next;	
}Element;
//考慮去除重復元素，如果不去重的話，直接將B鏈接在A後面即可
Element*Union(Element*A,Element*B)
{
	Element*p,*q,*head;
	if(A==NULL)returnB;
	p=B;
	q=B;
	while(p)
	{
		if(p->element==A->element)
		{
			break;
		}
		p=p->next;
	}
	if(p)
	{
		q=Union(A->next,B);
	}else
	{
		q=(Element*)malloc(sizeof(Element));
		q->element=A->element;
		q->next=Union(A->next,B);
	}
	returnq;
}
voidDisplay(char*Name,Element*A)
{
	Element*p;
	printf("%s",Name);
	if(A==NULL)
	{
		printf("{}");
		return;
	}
	printf("{");
	p=A;
	while(p)
	{
		printf("%d",p->element);
		if(p->next)
		{
			printf(",");
		}
		p=p->next;
	}
	printf("}");
	return;
}
intmain(intargc,charconst*argv[])
{
	/*code*/
	return0;
}

Ⅶ 數據結構中的演算法問題

這個程序應該不是「把b中a沒有的數據插入a中，另外新建c表。」而是"La和lb中的數據元素非遞歷好減排列，歸並LA和謹褲LB得到新的線性表LC，LC的數據元素也按值非遞減排列"《數據結構》（嚴蔚敏版）P21

用I和J來存儲LA和LB中選來比較的兩個元素的位置，用K來指示插入到LC中的哪個位置
while((i<=la_len)&&(j<=lb_len))表示當選出的相比較的兩個元素都在LA和LB的長度之內時就用執行後面的內容：
GetElem(La,i,ai);GetElem(Lb,j,bj);選出用來作比較的兩個元素
if(ai<=bj){ListInsert(Lc,++k,ai);++i;}如果ai不大於bi時就將其插入到LC中，相應的LA中元素向後移一個位置；同理有當bi小於等於ai時的情況else {ListInsert(Lc,++k,bj);++j;}

你應該注意到了這個祥爛簡兩個語句後面有個I++和J++
也就是說如果當插入的是LA中的最後一個元素時，這時i==la_len,而後面有I++，所以I的值應該比LA的長度長1
這時就無法進入while((i<=la_len)&&(j<=Lb_len))
但若這時LB中還有元素沒有插完怎麼辦？所以就有
while(i<=Lb_len){
GetElem(Lb,i++,bj);ListInsert(Lc,++k,bj);
}
同理：while(i<=La_len){
GetElem(La,i++,ai);ListInsert(Lc,++k,ai);
}
這下應該明白了吧？

不過編了這么大一天才5分，你也夠扣的

Ⅷ 面試經典數據結構和演算法匯總

如果說數據結構是骨架，那麼演算法就是靈魂。沒了骨架，靈魂沒有實體寄託；沒了靈魂，骨架也是個空殼。兩者相輔相成，缺一不可，在開發中起到了砥柱中流的作用。

現在我對各種數據結構和演算法做一總結，對比一下它們的效率

1.數據結構篇
1. 如果讓你手寫個棧和隊列，你還會寫嗎？
2. 開發了那麼多項目，你能自己手寫個健壯的鏈表出來嗎？
3. 下次面試若再被問到二叉樹，希望你能對答如流！
4. 面試還在被紅-黑樹虐？看完這篇輕松搞定面試官 ！

2.排序演算法篇
1. 幾個經典的基礎排序演算法，你還記得嗎？
2. 手把手教你學會希爾排序，很簡單！
3. 快速排序演算法到底有多快？
4. 五分鍾教你學會歸並排序
5. 簡單說下二叉樹排序
6. 學會堆排序只需要幾分鍾
7. 圖，這個玩意兒竟然還可以用來排序！

掌握了這些經典的數據結構和演算法，面試啥的基本上沒什麼問題了，特別是對於那些應屆生來說。接下來再總結一下不同數據結構和演算法的效率問題，做一下對比，這也是面試官經常問的問題。

數據結構常用操作效率對比：

常用排序演算法效率的對比：

關於經典的數據結構和演算法，就總結到這，本文建議收藏，利用等公交、各種排隊之時提升自己。這世上天才很少，懶蛋卻很多，你若對得起時間，時間便對得起你。