数据结构之线性表---顺序表的逆置

亦凉 2022-08-03 05:27 134阅读 0赞

问题：试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,a2,...,an)逆置为(an,an-1,...,a1)

算法思想：观察原表和新表顺序，逆置后的线性表是将原表相应位置的元素进行交换，即交换第一个和最后一个，第二个和倒数第二个，依此类推

源码

//顺序表结构体，表中的元素以整数为例

typedef struct

int \*elem;

int length;

// int listsize;该项为顺序表的大小，本题中未使用

\}SqList;

//逆置算法

void InverseLinearList(SqList \*list)  
\{  
 int i=0;  
  
 for (i=0; i<list->length/2; ++i)  
 \{

//因为要求用原表空间，所以交换时可以使用以下两种方法

//据说这种交换方式，在有些面试当中会考查  
 /\*list->elem\[i\] = list->elem\[i\] +  
list->elem\[list->length-i-1\];  
list->elem\[list->length-i-1\] = list->elem\[i\] -  
list->elem\[list->length-i-1\];  
list->elem\[i\] = list->elem\[i\] -  
list->elem\[list->length-i-1\];\*/

list->elem\[i\] = list->elem\[i\] ^  
list->elem\[list->length-i-1\];  
list->elem\[list->length-i-1\] = list->elem\[i\] ^  
list->elem\[list->length-i-1\];  
list->elem\[i\] = list->elem\[i\] ^  
list->elem\[list->length-i-1\];  
\}  
\}

//主函数，顺序表的初始化及销毁直接在主函数中实现了

void main()  
\{

//个人建议：在定义变量时，尽量进行初始化，避免以后带来不必要麻烦  
int i=0;  
  
SqList \*list;  
list = (SqList\*)malloc(sizeof(SqList));  
  
//输入元素个数  
printf("please input the number of elements:");  
scanf("%d", &list->length);  
list->elem = (int\*)malloc(sizeof(int)\*list->length);  
  
//输入元素  
printf("please input elements:\\n");  
for (i=0; i<list->length; ++i)  
scanf("%d", &list->elem\[i\]);  
  
//逆置顺序表  
printf("Old linear list:\\n");  
PrintElem(\*list);  
InverseLinearList(list);  
printf("New linear list:\\n");  
PrintElem(\*list);  
  
//释放开辟的空间，不要忘记结构体中的指针  
free(list->elem);  
free(list);  
  
return ;  
\}

//测试结果

please input the number of elements:9  
please input elements:  
1 2 3 4 5 6 7 8 9  
Old linear list:  
1 2 3 4 5 6 7 8 9  
New linear list:  
9 8 7 6 5 4 3 2 1