数据结构第二章 线性表part8.ppt

K1 K2 K3 K6 K4 K8 K7 K5 K9 逻辑结构图如图所示。 开始结点是指无前驱的结点，这里满足该定义的开始结点为k1,k2. 终端结点是指无后继的结点，这里满足该定义的终端结点为k6,k7. 该逻辑结构是非线性结构中的图形结构。 1-2 设有如图所示的逻辑结构图示，给出它的逻辑结构。 K1 K2 K3 K6 K4 K8 K7 K5 K9 本题的逻辑结构如下： B=(K,R) K={K1,K2,…,K9} R={K1,K2,K1,K3,K3,K4,K3,K6,K6,K8, K4,K5,K6,K7,K8,K9} 该逻辑结构是一个树形结构，其树根为K1，叶子结点为K2、K5、K7和K9。 1-3 分析下面程序段的时间复杂度是多少？ i=s=0; while (sn) { i++; s+=i; } s=0; for (i=0;in;i++) for (j=0;jn;j++) s+=B[i][j]; sum=s; i=1; while (i=n) i=i*3; O(n) O(n2) O(log3n) 2-1 已知一个顺序表A，其中的元素按值非递减有序排列，编写一个函数插入一个元素x后保持该顺序表仍按非递减有序排列。 算法思想： 先找到适当的位置，然后后移元素空出一个位置，再将x 插入。 实现本题功能的函数如下： void insert (SqList A, int n, int x) // 表长为n { int i,j; i=1; while (x=A[i]) i++; // 查找插入位置 for (j=n-1;j=i;j--) A[j+1]=A[j]; // 移出插入 x 的位置 A[i]=x; n++; // 将x插入 ，表长增1 } 实现本题功能的又一方法如下： void insert (SqList A, int n, int x) // 表长为n { int i,j; i=n-1; while (xA[i]) i--; // 查找插入位置 for (j=n-1;ji;j--) A[j+1]=A[j]; // 移出插入 x 的位置(i+1) A[i+1]=x; n++; // 将x插入 ，表长增1 } 2-2 已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相同的元素。 算法思想： 由于顺序表中的元素按元素值非递减有序排列，值相同的元素必为相邻的元素。 因此，依次比较相邻两个元素，若值相等，则删除其中一个，否则继续向后查找。 实现本题功能的函数如下： void del (SqList A, int n) // 表长为n { int i=0, j; while (in-2) if (A[i]!=A[i+1]) i++ ; // 元素值不相等，继续向下找 else { for (j=(i+2);j=n;j++) A[j-1]=A[j]; // 删除第i+1个元素 n--; // 表长减1 } } 2-3 已知一个顺序表A中有n个元素，且任何元素均不为0，将A拆成两个线性表B和C，使A中大于0 的元素存放在B中，小于0的元素存放在C中。 算法思想： 依次遍厉A的元素，判断当前的元素值，大于0 者赋给B（假设