顺序表的建立及遍历用last指针

顺序表是一种线性数据结构，它的元素按照一定的顺序存储在一个连续的内存区域。建立顺序表通常涉及以下几个步骤：

1. 定义数组：首先需要预先确定序列的大小，然后动态分配一段内存用于存储元素，创建一个空的数组。

2. 初始化：如果数组已初始化为空，则将第一个元素放在第一个位置，同时设置`last`指针指向该元素，表示当前访问的最后一个元素。

3. 插入元素：当需要添加新元素时，在`last`指针之后插入，更新`last`指针指向新的元素。

4. 遍历操作：遍历顺序表通常是通过`last`指针从头到尾依次访问每个元素。开始时，`last`指针指向第一个元素，然后每次循环都移动`last`指针到下一个元素的位置，并处理相应的元素内容。

5. 删除元素：若要删除某个元素，需找到它并将其前一个元素替换为删除元素，同时更新`last`指针，除非删除的是最后一个元素，此时可能需要调整`last`指针。

遍历过程如下：

while (last != NULL) {  // last != NULL 或者 last != nullptr，取决于语言
    // 处理当前元素
    process_element(*last);
    
    // 移动到下一个元素
    last = last->next;  // 如果是链表，这里应该是 last = last->next;
}

相关问题

假设以顺序表ST表示一棵完全二叉树，ST.data[ST.last]中存放二叉树中各结点的数据元素。试设计算法由此顺序存储结构建立该二叉树的二叉链表LT。

算法如下：

1. 初始化二叉链表LT和顺序表ST，分别用指针和数组表示。
2. 如果ST为空，则返回空链表。
3. 从ST的第一个元素开始遍历，对于每个元素，先将其存入新建的二叉树结点中。
4. 如果该结点是根节点，则直接将其插入到LT中。
5. 否则，找到该结点的双亲结点p，将该结点作为p的左孩子或右孩子插入到LT中。
6. 重复步骤3-5，直到遍历完ST中所有元素。
7. 返回二叉链表LT。

算法描述中用到了二叉树结点的双亲结点，因此需要先定义一个二叉树结点的数据类型，包含数据元素、左孩子指针、右孩子指针和双亲结点指针。具体实现代码如下：

typedef struct BiTNode {
    ElemType data; // 数据元素
    struct BiTNode *lchild, *rchild, *parent; // 左孩子、右孩子、双亲结点指针
} BiTNode, *BiTree;

// 初始化二叉链表LT和顺序表ST
BiTree LT = NULL;
ElemType ST[MAXSIZE];

// 建立二叉链表LT
void CreateBiTree(BiTree &T, int i) {
    if (ST[i] == NULL) {
        T = NULL;
    } else {
        T = (BiTree)malloc(sizeof(BiTNode));
        T->data = ST[i];
        CreateBiTree(T->lchild, 2 * i); // 左孩子结点在数组中的下标为 2i
        CreateBiTree(T->rchild, 2 * i + 1); // 右孩子结点在数组中的下标为 2i+1
        if (T->lchild != NULL) {
            T->lchild->parent = T; // 左孩子结点的双亲结点为 T
        }
        if (T->rchild != NULL) {
            T->rchild->parent = T; // 右孩子结点的双亲结点为 T
        }
    }
}

// 主函数
int main() {
    // 读入顺序表ST和最后一个元素的下标last
    int last;
    scanf("%d", &last);
    for (int i = 1; i <= last; i++) {
        scanf("%d", &ST[i]);
    }
    // 建立二叉链表LT
    CreateBiTree(LT, 1);
    // 输出二叉链表LT
    printf("二叉链表LT：\n");
    PrintBiTree(LT, 0);
    return 0;
}

其中，CreateBiTree函数用于建立二叉链表LT，PrintBiTree函数用于输出二叉链表LT，具体实现代码见下：

// 输出二叉链表LT
void PrintBiTree(BiTree T, int depth) {
    if (T == NULL) {
        return;
    }
    // 先输出右子树
    PrintBiTree(T->rchild, depth + 1);
    // 再输出根节点
    for (int i = 0; i < depth; i++) {
        printf("    ");
    }
    printf("%d\n", T->data);
    // 最后输出左子树
    PrintBiTree(T->lchild, depth + 1);
}

这样，就可以通过顺序表ST构建二叉链表LT了。

1、已知顺序表数据类型定义为： #define MAX 100 typedef struct{ int data[MAX]; int last; /*顺序表长度*/ }SeqList; （1）设计一个函数float avgList(SeqList *lp)，统计lp指向的顺序表中元素的平均值并返回。 （2）设计一个函数void splitList(SeqList *lp)，把lp指向的顺序表中的整数拆分成一个所有奇数在前、所有偶数在后的顺序表。 （3）设计一个函数void deleX(SeqList *lp， int x)，在lp指向的顺序表中删除所有值为x的元素。

（1）函数float avgList(SeqList *lp)的实现如下：

float avgList(SeqList *lp) {
float sum = 0;
for (int i = 0; i <= lp->last; i++) {
sum += lp->data[i];
}
return sum / (lp->last + 1);
}

该函数遍历顺序表中的所有元素，求出它们的和，然后除以顺序表的长度得到平均值，最后返回该平均值。

（2）函数void splitList(SeqList *lp)的实现如下：

void splitList(SeqList *lp) {
int i = 0, j = lp->last;
while (i < j) {
while (i < j && lp->data[i] % 2 != 0) {
i++;
}
while (i < j && lp->data[j] % 2 == 0) {
j--;
}
if (i < j) {
int temp = lp->data[i];
lp->data[i] = lp->data[j];
lp->data[j] = temp;
}
}
}

该函数维护两个指针i和j，分别指向顺序表的头和尾。在循环过程中，i指针向右移动，直到指向一个偶数，j指针向左移动，直到指向一个奇数。然后交换i和j指针所指向的元素。重复执行上述过程，直到i和j指针相遇。此时，顺序表中所有奇数都在偶数的前面。

（3）函数void deleX(SeqList *lp, int x)的实现如下：

void deleX(SeqList *lp, int x) {
int k = 0;
for (int i = 0; i <= lp->last; i++) {
if (lp->data[i] != x) {
lp->data[k++] = lp->data[i];
}
}
lp->last = k - 1;
}

该函数遍历顺序表中的所有元素，如果元素的值不等于x，则将该元素复制到顺序表的前面，并将指针k指向下一个位置。最后，将顺序表的长度设为k-1即可。这样，顺序表中所有值为x的元素都被删除了。