数据结构常见算法ppt课件.ppt

《数据结构常见算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构算法数据结构数据结构是一门研究非数值计算的程序设计问题中的操作对象（结点）以及它们之间关系和操作等的学科。1968年克努思教授开创了数据结构的最初体系，他所著的《计算机程序设计艺术》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。70年代初，数据结构作为一门独立的课程开始进入大学课堂。下面介绍数据结构中常见的一些基本算法关于算法线性表上的常见算法基于队列的常见算法基于栈的常见算法数据结构常见算法算法多项式求的两种方法A(x)=anxn+an-1xn-1+…+a0A(x)=((anx+an-1)X+an-2

2、)…+a0A(x)=anxn+an-1xn-1+…+a0templateTPoly1(Ta[],intn,Tx){inti,j;Tresult=0;Txn,xx;for(i=0;iTPoly2(Ta[],intn,Tx){inti,j;Tresult=0;Txn,xx;re

3、sult=a[n-1];for(i=n-1;i>0;i--)result=result*x+a[i-1];returnresult;}线性表设计一个时间复杂度为O(n)的算法，实现将数组A[n]中所有元素循环右移K个位置已知数组元素为整型，设计算法将其调整为左右两部分，左边元素为奇数，右边元素为偶数设单链表以非递减有序排列，设计算法，实现在单链表中删去系统的多余结点设单链表以非递减有序排列，设计算法，实现在单链表中删去系统的多余结点已知一个单链表中的数据元素含有三类字符：数字、字母和其他字符。编写算法，构造三个循环链表，使得每个循环链表中之包

4、含同一类字符返回设计一个时间复杂度为O(n)的算法，实现将数组A[n]中所有元素循环右移K个位置算法分析kn。k=k%N01234567891011121314140123456789101112131314012345678910111212131401234567891011AB(k=1)B(k=2)B(k=3)j=(i+k)%Ninti,j,n;int*a;cin>>n>>k;k=k%n;a=newint[n];for(i=0;i>>a[i];for(i=0;i<

5、=a[i];}时间复杂度？空间复杂度？空间复杂度更少的方法假设原数组序列为abcd1234，循环右移了4位数组序列为1234abcd。右移后，有两段的顺序是不变的：1234和abcd，可把这两段看成两个整体。右移K位的过程就是把数组的两部分交换一下。变换的过程通过以下步骤完成：1.  逆序排列abcd：abcd1234→dcba1234；2.  逆序排列1234：dcba1234→dcba4321；3.  全部逆序：dcba4321→1234abcd。更一般的情况：012345678910111213141401234567891011121

6、31314012345678910111212131401234567891011根据K%N的大小，将数据分成两段，第一段长度为N-K个数据，第二段中有K个数据然后分别将两段逆序，最后将整个数组逆序voidconvert(inta[],intstart,intend){intk,temp;for(k=0;k<(end-start+1)/2;k++){temp=a[start+k];a[start+k]=a[end-k];a[end-k]=temp;}}voidyiwei(inta[],intn,intk){convert(a,0,k-1);c

7、onvert(a,k,n-1);convert(a,0,n-1);}已知数组元素为整型，设计算法将其调整为左右两部分，左边元素为奇数，右边元素为偶数算法分析设计两个工作指针，分别指向数组的两端（I=0；j=n-1）.然后，重复的进行以下工作：如果i>n;a=newint[n];inti=0,j=n-1;for(i=0;i>a[i];i=0;wh

8、ile(i