数据结构常见算法.ppt

数据结构算法 数据结构 数据结构是一门研究非数值计算的程序设计问题中的操作对象（结点）以及它们之间关系和操作等的学科。 1968 年克努思教授开创了数据结构的最初体系，他所著的《计算机程序设计艺术》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。 70 年代初，数据结构作为一门独立的课程开始进入大学课堂。 下面介绍数据结构中常见的一些基本算法 关于算法 线性表上的常见算法 基于队列的常见算法 基于栈的常见算法 算法 多项式求的两种方法 A(x)=anxn+an-1xn-1+…+a0 A(x)=((anx+an-1)X+an-2)…+a0 A(x)=anxn+an-1xn-1+…+a0 A(x)=((anx+an-1)X+an-2)…+a0 线性表 设计一个时间复杂度为O(n)的算法，实现将数组A[n]中所有元素循环右移K个位置 算法分析 kn kn。 k=k%N int i,j,n; int *a; cinnk; k=k%n; a=new int[n]; for (i=0;in;i++) cin a[i]; for (i=0;in;i++){ j=(i+k)%n; b[j]=a[i]; } 空间复杂度更少的方法 假设原数组序列为abcd1234，循环右移了4位 数组序列为1234abcd。 右移后，有两段的顺序是不变的：1234和abcd，可把这两段看成两个整体。右移K位的过程就是把数组的两部分交换一下。变换的过程通过以下步骤完成： 1.?? 逆序排列abcd：abcd1234 → dcba1234； 2.?? 逆序排列1234：dcba1234 → dcba4321； 3.?? 全部逆序：dcba4321 → 1234abcd。 更一般的情况： void convert(int a[], int start, int end) { int k, temp; for (k = 0; k (end-start+1)/2; k++) { temp = a[start+k]; a[start+k] = a[end-k]; a[end-k] = temp; } } void yiwei(int a[], int n, int k) { convert(a,0,k-1); convert(a,k,n-1); convert(a,0,n-1); } 已知数组元素为整型，设计算法将其调整为左右两部分，左边元素为奇数，右边元素为偶数 算法分析 设计两个工作指针，分别指向数组的两端（I=0；j=n-1）.然后，重复的进行以下工作： 如果ij: 从左向后扫描数组，直到遇到第一个偶数 从右向左扫描数组，直到遇到第一个奇数 如果ij 交换a[i]、 a[j]的数据，，同时修改i，j的值，继续进行2的工作 int n,*a; cinn; a=new int [n]; int i=0,j=n-1; for (i=0;in;i++) cina[i]; i=0; while (ij){ while(a[i]%2==1) i++; while(a[j]%2==0) j--; if (ij){ temp=a[i];a[i]=a[j];a[j]=temp;i++;j--} } #include stdafx.h #include iostream.h class change { private: int *a,length; public: change() { coutPlease input the length of the array:; cinlength; a=new int[length]; coutPlease input the data of the array:; for(int i=0;ilength;i++) cina[i]; } void trans() { int i=0,j=length-1; int temp; while (ij){ while(a[i]%2==1) i++; while(a[j]%2==0) j--; if (ij) { temp=a[i]; a[i]=a[j]; a[j]=temp; i++; j--; } } return; } void display() { int i=0; for(i=0;ilength;i++) cout a[i] ; cout endl; } }; int main(int argc, char* argv[]) { chang