数据结构复习(汉口学院).ppt

数据结构复习（HKXY） 1 绪论 例1-2 阅读下列算法，并回答问题。 float what (float x, int n) { float y=x; while(n1) { y= y*x; n=n–1; } return y; } 问题： (1) 该算法的功能是计算 。 (2) 该算法的时间复杂度是 。 2 线性表 #define MAXSIZE 10000 int a[MAXSIZE+1]; /* 线性表的容量 */ int n; /* 线性表的表长 */ （１）插入算法设计 输入：长度为n的线性表a[1]..a[n], 插入位置 i 和插入元素 x 输出：在第i处插入新元素x后，得到长度为n+1的线性表 void list_insert( ) { /* 在长度为n的线性表a[1..n]的第i处插入新元素x */ int j; if (n==MAXSIZE) error(“表满”); else if(i1||in+1)error(“ 插入位置错”); else { for (j=n; j=i; j--) a[j+1]= a[j]; /* 元素后移 */ a[i]= x; /* 在第i处插入x */ n++ ；/* 表长加1 */ } } （２）删除算法设计 输入：长度为n的线性表a[1]..a[n], 删除位置 i ; 　 输出：删除第i个元素后，得到长度为n-1的线性表 void list_delete( ) { /* 删除线性表a[1..n]中的第i个元素 */ int j; if (i1||in) error(“删除位置错”) ; else if (n==0) error(“表空”)； else { for (j=i+1; j=n; j++) a[j-1]=a[j]; /* 元素前移 */ n-- ；/* 表长减1 */ } } 例2.1设线性表存于整型数组 a[1..MAXSIZE]的前n个分量中 且递增有序, 将x插入到线性表的适当位置。 void ins( ) { int i; if （nMAXSIZE）/* 当表不满时 */ { i=n; while (i=1 xa[i] ) { a[i+1]=a[i]; i--; } /* 找插入位置, 并后移 */ a[i+1]=x; n++; } } 例2.2 已知线性表存于 a[1..MAXSIZE]中的前n个分量 中，写一算法删除从第i个元素开始的k个元素。 void del (int k, int i){ /* 本算法删除从第i个元素开始的k个元素 */ /* 将a[k+i]—a[n] 顺序前移k个位置 */ int j; if ( k0 1=i i+k-1=n ) { for (j=i+k; j=n; ++j) a[j-k]=a[j]; /* 前移k个元素，将k个元素一次删除 */ n - = k; /* 表长－k */ } } 3 栈与队列 4 串 5 数组和广义表 （1）对称矩阵和上（或下）三角矩阵的压缩存储。 例：下三角矩阵的存储，按行主序方式。 k=i(i+1)/2+j 当i=j时 0 当ij时 a[i][j] 在一维数组s[k] 中(i=j)或为0(ij)。 （2）对角矩阵 以三对角矩阵为例，按行主序方式存储，仅存储非零部分。 例5-2 将一个a[100][100]