第四讲-顺序表的简单应用

1、数据结构数据结构2021-11-5滨州学院信息工程系1第二章第二章 线性表线性表顺序表的简单应用顺序表的简单应用数据结构数据结构2021-11-52复习复习#define LIST_INIT_SIZE 100 / 线性表存储空间的初始分配量线性表存储空间的初始分配量typedef struct ElemType *elem; /存放线性表的数组空间基地址存放线性表的数组空间基地址 int length; / 当前长度当前长度 int listsize; / 当前分配的容量当前分配的容量 SqList; / 顺序表顺序表数据结构数据结构2021-11-53顺序表的应用实例顺序表的应用实例例例1

2、顺序结构线性表顺序结构线性表LA与与LB的结点关键字的结点关键字为整数。为整数。LA与与LB的元素按非递减有序，线的元素按非递减有序，线性表空间足够大。性表空间足够大。 试用类试用类C语言给出一种语言给出一种高效高效算法，将算法，将LB中元素合到中元素合到LA中，使新的中，使新的LA的元素仍保持的元素仍保持非递减有序。高效指最大限度的避免移动元非递减有序。高效指最大限度的避免移动元素。素。数据结构数据结构2021-11-54void Union(SqList &LA , SqList LB) / LA和和LB是顺序存储的线性表，元素按非递减有序排列，本算是顺序存储的线性表，元素按非递减

3、有序排列，本算 /法将法将LB合并到合并到LA中中，元素仍非递减有序。，元素仍非递减有序。 m = LA.length; n = LB.length; /m，n分别为线性表分别为线性表LA和和LB的长度的长度 k = m+n-1; /k为结果线性表的工作指针（下标）为结果线性表的工作指针（下标） i = m-1; j = n-1; /i，j分别为分别为LA和和LB的工作指针（下标）的工作指针（下标） while (i=0 & j=0) if (LA.elemi = LB.elemj) LA.elemk- - = LA.elem i- -; else LA.elemk- - = LB.e

4、lemj- -; while (j = 0) LA.elemk- - = LB.elemj- -; LA.length = m+n; 数据结构数据结构2021-11-55例例2 请写一个算法将顺序存储结构的请写一个算法将顺序存储结构的线性表（线性表（a1.an）逆置为）逆置为(an.a1)数据结构数据结构2021-11-56顺序存储结构的线性表的逆置，只需一个变量辅助空间。顺序存储结构的线性表的逆置，只需一个变量辅助空间。算法核心是选择循环控制变量的初值和终值。算法核心是选择循环控制变量的初值和终值。void SeqInvert（SqList &A）A是顺序存储的线性表，本算法将其逆置

5、。是顺序存储的线性表，本算法将其逆置。for（i = 0；i = A.length/2-1；i+） t = A.elemi； A.elemi = A.elemA.length-1-i； A.elemA.length-1-i = t； 数据结构数据结构算法讨论算法讨论 算法中循环控制变量的初值和终算法中循环控制变量的初值和终值是关键。数组从下标值是关键。数组从下标0开始，第开始，第n个元素的个元素的下标是下标是n-1。因为首尾对称交换，所以控制。因为首尾对称交换，所以控制变量的终值是线性表长度的一半。当变量的终值是线性表长度的一半。当n为偶为偶数，数，“一半一半”恰好是线性表长度的二分之一；恰好

6、是线性表长度的二分之一；若若n是奇数，是奇数，“一半一半”是小于是小于n/2的最大整数，的最大整数，这时取大于这时取大于1/2的最小整数的位置上的元素，的最小整数的位置上的元素，恰是线性表中间位置的元素，不需要逆置恰是线性表中间位置的元素，不需要逆置2021-11-57数据结构数据结构2021-11-58 例例3 已知顺序表已知顺序表L，每个元素都是互不，每个元素都是互不相等的整数，将所有奇数移动到所有相等的整数，将所有奇数移动到所有偶数前面。要求时间最少，辅助空间偶数前面。要求时间最少，辅助空间最少。最少。数据结构数据结构2021-11-59void move(SqList &L)

7、/将顺序表将顺序表L中的所有奇数移动到偶数的前面中的所有奇数移动到偶数的前面 i = 0; j = L.length-1; while(i = j) /从前向后查询从前向后查询偶偶数数 while( L.elemi%2 = 1) i+; /从后向前查询从后向前查询奇奇数数 while( L.elemj%2 = 0) j-; if ( i j ) L.elemi L.elemj; i+; j-; 数据结构数据结构2021-11-510例例4 已知线性表（已知线性表（a1 a2 a3 an）按顺）按顺序存于内存，每个元素都是整数，试序存于内存，每个元素都是整数，试设计用最少时间把所有值为负数的元设

8、计用最少时间把所有值为负数的元素移到全部正数值元素前边的算法：素移到全部正数值元素前边的算法：例：（例：（x,-x,-x,x,x,-x x）变为（）变为（-x,-x,-xx,x,x）。）。 数据结构数据结构2021-11-511题目分析题目分析可采用快速排序的思想来实现，只是提出暂存的第一个元素（枢轴）并不可采用快速排序的思想来实现，只是提出暂存的第一个元素（枢轴）并不作为以后的比较标准，比较的标准是元素是否为负数，即与作为以后的比较标准，比较的标准是元素是否为负数，即与0比较。比较。int Rearrange（int a, int n)a是具有是具有n个元素的数组，线性表的元素是整数。本算法

9、重排顺序表个元素的数组，线性表的元素是整数。本算法重排顺序表a，/所有值为负数的元素移到所有值为正数的数的前面。所有值为负数的元素移到所有值为正数的数的前面。 i = 0; j = n-1; i, j 初始值为初始值为a的第的第1个和第个和第n个元素下标个元素下标 t = a0; 暂存枢轴元素。暂存枢轴元素。 while( ij ) while( i=0) j-; 若当前元素为大于等于零，则指针前移。若当前元素为大于等于零，则指针前移。 if( ij ) ai+ = aj; 找到负数将其前移。找到负数将其前移。 while(ij &ai0) i+; 当前元素为负数时指针后移。当前元素为

10、负数时指针后移。 if( ij ) aj- = ai; 找到正数将其后移。找到正数将其后移。 ai = t; 将原第一元素放到最终位置。将原第一元素放到最终位置。 数据结构数据结构算法讨论算法讨论 本算法时间复杂度为本算法时间复杂度为O(n)。算法只是按。算法只是按题目要求把正负数分开，题目并未提及零的题目要求把正负数分开，题目并未提及零的问题，将零放到了正数一边。对此问题的扩问题，将零放到了正数一边。对此问题的扩充是若元素包含正数、负数和零，并要求按充是若元素包含正数、负数和零，并要求按负数、零、正数的顺序重排线性表，统计负负数、零、正数的顺序重排线性表，统计负数、零、正数的个数。数、零、正

11、数的个数。2021-11-512数据结构数据结构2021-11-513例例5 已知长度为已知长度为n的线性表的线性表A采用顺序存储采用顺序存储结构，请写一时间复杂度为结构，请写一时间复杂度为O(n)、空间复、空间复杂度为杂度为O(1)的算法，该算法删除线性表中的算法，该算法删除线性表中所有值为所有值为item的数据元素。（的数据元素。（O(1)表示算表示算法的辅助空间为常量）。法的辅助空间为常量）。 【北京航空航天大学北京航空航天大学 2000 五（五（10分）分）】数据结构数据结构题目分析题目分析 在顺序存储的线性表上删除元素，在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第

12、通常要涉及到一系列元素的移动（删第i个个元素，第元素，第i+1至第至第n个元素要依次前移）。本个元素要依次前移）。本题要求删除线性表中所有值为题要求删除线性表中所有值为item的数据元的数据元素，并未要求元素间的相对位置不变。因此素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（可以考虑设头尾两个指针（i=0，j=n-1），），从两端向中间移动，凡遇到值从两端向中间移动，凡遇到值item的数据元的数据元素时，直接将右端元素左移至值为素时，直接将右端元素左移至值为item的数的数据元素位置。据元素位置。2021-11-514数据结构数据结构2021-11-515void Delete（SqList &A）A是是n个元素的顺序表，本算法删除个元素的顺序表，本算法删除A中所有值为中所有值为item的元素。的元素。 i = 0；j = A.length - 1；设置数组低、高端指针（下标）设置数组低、高端指针（下标） while（ij） while（ij & A.elemi != item） i+； /从前向后找到从前向后找到item元素元