设有一线性表e=（e1 e2 … en-1 en) 其逆线性表定义为e'=（en en-1 … e2 e1) 请设
已帮助 人
设有一线性表e=（e1 , e2 , … , en-1 , en)，其逆线性表定义为e"=（en , en-1 , … , e2 , e1)，请设计一个算法，将线性表逆置，要求逆线性表仍占用原线性表的空间，并且用顺序表和单链表两种方法来表示，写出不同的处理函数。
回答
共1条回复-
(1)数据结构 采用顺序表的定义。 (2)思路 考虑对数组element[]进行置逆，即把第一个元素和最后一个元素换位置，把第二个元素和倒数第二个元素换位置…… [注意] 这种调换的工作只需对数组的前一半元素进行，所以设置整数变量count用于存放数组长度的一半的值。读者可以考虑一下：为什么不能对整个数组进行如上的对元素“换位置”的工作?(提示：这样会将本来已经置逆的线性表又置逆回来，即又变成了原来的表。) (3)顺序表的置逆算法 void rev_seq(PSeqList palist){ DataType x; int count,i; if(palist-＞n==0&&palist-＞n==1)return; /*空表或只有一个元素，直接返回*/ count=palist-＞n/2; for(i=0;i＜count;i++){ /*只需调换半个表的元素*/ x=palist-＞element[i]; palist-＞element[i]=palist-＞element[palist-＞n-1-i]; palist-＞element[palist-＞n-1-i]=x; } } (4)代价分析 该算法中包含一个for循环，其循环次数为n/2。因此，算法的时间代价为O(n)。