第二章第1次作业答案.ppt

在本章的作业中，我们关注的是有序顺序表的操作，主要涵盖了两个重要的知识点：有序顺序表的插入和就地逆置。我们来看有序顺序表的插入。 **有序顺序表插入** 有序顺序表是一种特殊的数据结构，其中元素按照非降序排列。在插入新元素时，需要保持这种排序规则。在提供的代码中，有两个关键步骤： 1. **存储结构定义**：顺序表由一个数组`elem`存储元素，`length`表示当前元素个数，`listsize`表示分配的存储容量。定义如下： ```c typedef struct{ ElemType* elem; // 存储空间基地址 int length; // 表中元素的个数 int listsize; // 表容量大小 }SqList; // 顺序表类型定义 ``` 2. **插入算法**：`ListInsert_SortedSq`函数实现有序插入。检查是否已满，如果满了，则通过`realloc`动态扩展存储空间。然后，从最后一个元素开始，找到合适的位置插入新元素，同时将大于新元素的元素后移。代码如下： ```c Status ListInsert_SortedSq(SqList &L,ElemType e){ // ... if(L.length>=L.listsize){ // 表满，增加存储容量 // ... } // 从最后一个元素开始，只要大于 e 就后移，最后插入当前位置后 p=L.elem+L.length-1; while(p>=L.elem&&*p>e){ *(p+1)=*p; --p; } *(p+1)=e; ++L.length; // 表长加 1 return OK; } ``` **顺序表就地逆置** 就地逆置是指不额外分配存储空间，仅使用原数组空间完成列表的反转。这里使用了双指针的方法，设置`p`指向列表的开始，`q`指向列表的末尾，交换它们所指元素，然后移动指针，直到两者相遇。具体实现如下： ```c Status ListInverse_Sq(SqList &L){ // ... p=L.elem; q=L.elem+L.length-1; while(p<q){ temp=*p; // 保存*p的值 *p=*q; // 将*q的值赋给*p *q=temp; // 将temp的值（原*p的值）赋给*q ++p; // 移动p --q; // 移动q } return OK; } ``` 这个方法有效地实现了顺序表的就地逆置，且效率较高，因为它只需要遍历一次列表。 在实际编程中，理解并熟练掌握这些基本数据结构和算法是非常重要的，它们是构建更复杂数据结构和算法的基础。对于有序顺序表的操作，了解如何高效地进行插入和逆置对于提高程序性能至关重要。在实现这些操作时，注意内存管理和边界条件的处理，以避免潜在的运行错误。