经典数据结构算法问题

Ⅰ 数据结构与算法的问题

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. 图，这个玩意儿竟然还可以用来排序！

掌握了这些经典的数据结构和算法，面试啥的基本上没什么问题了，特别是对于那些应届生来说。接下来再总结一下不同数据结构和算法的效率问题，做一下对比，这也是面试官经常问的问题。

数据结构常用操作效率对比：

常用排序算法效率的对比：

关于经典的数据结构和算法，就总结到这，本文建议收藏，利用等公交、各种排队之时提升自己。这世上天才很少，懒蛋却很多，你若对得起时间，时间便对得起你。