【数据结构】顺序表的定义和运算

2023-12-15 16:30:31

目录

1.初始化

2.插入

3.删除

4.查找

5.修改

6.长度

7.遍历

8.完整代码


🌈嗨!我是Filotimo__🌈。很高兴与大家相识,希望我的博客能对你有所帮助。

💡本文由Filotimo__??原创,首发于CSDN📚。

📣如需转载,请事先与我联系以获得授权??。

🎁欢迎大家给我点赞👍、收藏??,并在留言区📝与我互动,这些都是我前进的动力!

🌟我的格言:森林草木都有自己认为对的角度🌟。

在C语言中,线性表的顺序存储结构可以使用数组来实现。顺序表是一种将元素按照顺序存储在连续的存储空间中的线性结构。

顺序表可以使用结构体来定义,例如:

#define MAXSIZE 100  // 线性表的最大长度

typedef struct {
    int data[MAXSIZE];  // 存储线性表元素的数组
    int length;         // 当前线性表长度
} List;

以下是顺序表的基本运算:

1.初始化

初始化一个空的顺序表:

void initList(List *L) {
    L->length = 0;
}

L:指向顺序表的指针。

将顺序表的长度length赋值为0,相当于清空了顺序表,使得顺序表L中不再有任何元素。

2.插入

在某个位置插入一个元素,使得该位置原来的元素和之后的元素往后移动:

int listInsert(List *L, int i, int elem) {
    int j;
    if (i < 1 || i > L->length + 1) {
        return 0; // 越界
    }
    if (L->length >= MAXSIZE) {
        return 0; // 线性表已满
    }
    for (j = L->length; j >= i; j--) {
        L->data[j] = L->data[j-1];
    }
    L->data[i-1] = elem;
    L->length++;
    return 1;
}

函数的目的是将一个元素elem插入到顺序表L的第i个位置。

i:要插入的位置

elem:要插入的元素的值

代码的逻辑:

(1)判断要插入的位置i是否越界,即是否小于1或大于线性表的长度加1。如果越界则返回0,表示失败。

(2)判断顺序表L是否已满,即顺序表的长度是否达到了最大容量MAXSIZE。如果已满则返回0,表示失败。

(3)通过一个循环,将从位置i开始的元素都向后移动一位,为要插入的元素留出空位。

(4)将要插入的元素elem赋值给位置i-1的元素。

(5)增加顺序表的长度。

(6)返回1,表示插入成功。

3.删除

删除某个位置的元素,使得该位置后面的元素往前移动:

int listDelete(List *L, int i) {
    int j;
    if (i < 1 || i > L->length) {
        return 0; // 越界
    }
    for (j = i; j < L->length; j++) {
        L->data[j-1] = L->data[j];
    }
    L->length--;
    return 1;
}

i:要删除的元素的位置

代码的逻辑:

(1) 判断要删除的位置i是否越界,即是否小于1或大于顺序表的长度。如果越界则返回0,表示失败。

(2)通过一个循环,将从位置i+1开始的元素都向前移动一位,覆盖了要被删除的元素。

(3)减少顺序表的长度。

(4)返回1,表示删除成功。

4.查找

根据值或位置查找一个元素:

int locateElem(List *L, int elem) {
    int i;
    for (i = 0; i < L->length; i++) {
        if (L->data[i] == elem) {
            return i+1;
        }
    }
    return 0; // 没找到
}

elem:要查找的元素的值

代码的逻辑:

(1)通过一个循环,遍历顺序表L中的每个元素。

(2)在循环中,判断当前元素是否等于要查找的元素elem。如果相等,则返回当前元素的位置(即i+1)。

(3)如果循环结束还没有找到相等的元素,则返回0,表示没有找到。

5.修改

根据位置修改某个元素的值:

int setElem(List *L, int i, int elem) {
    if (i < 1 || i > L->length) {
        return 0; // 越界
    }
    L->data[i-1] = elem;
    return 1;
}

?i:要设置元素的位置

-elem:要设置的新值

代码的逻辑:

(1)判断要设置的位置i是否越界,即是否小于1或大于线性表的长度。如果越界则返回0,表示失败。

(2)将线性表L的第i个位置的元素值设置为elem。

(3)返回1,表示设置成功。

6.长度

返回顺序表的长度:

int listLength(List *L) {
    return L->length;
}

直接返回顺序表L的长度L->length。

7.遍历

依次访问顺序表中的每个元素:

void traverseList(List *L) {
    int i;
    for (i = 0; i < L->length; i++) {
        printf("%d ", L->data[i]);
    }
    printf("\n");
}

代码的逻辑:

(1)通过一个循环,遍历顺序表L中的每个元素。

(2)在循环中,使用printf函数依次将每个元素的值输出到屏幕上,并在元素之间添加一个空格。

(3)在循环结束后,输出一个换行符,以便下一行输出。

8.完整代码

这里顺序表中的元素均设为 int 类型:

#include <stdio.h>

#define MAXSIZE 100  // 线性表的最大长度

typedef struct {
    int data[MAXSIZE];  // 存储线性表元素的数组
    int length;         // 当前线性表长度
} List;

// 初始化线性表
void initList(List *L) {
    L->length = 0;
}

// 在第 i 个位置插入元素 elem
int listInsert(List *L, int i, int elem) {
    int j;
    if (i < 1 || i > L->length + 1) {
        return 0; // 越界
    }
    if (L->length >= MAXSIZE) {
        return 0; // 线性表已满
    }
    for (j = L->length; j >= i; j--) {
        L->data[j] = L->data[j-1];
    }
    L->data[i-1] = elem;
    L->length++;
    return 1;
}

// 删除第 i 个元素
int listDelete(List *L, int i) {
    int j;
    if (i < 1 || i > L->length) {
        return 0; // 越界
    }
    for (j = i; j < L->length; j++) {
        L->data[j-1] = L->data[j];
    }
    L->length--;
    return 1;
}

// 查找第一个等于 elem 的元素
int locateElem(List *L, int elem) {
    int i;
    for (i = 0; i < L->length; i++) {
        if (L->data[i] == elem) {
            return i+1;
        }
    }
    return 0; // 没找到
}

// 返回第 i 个元素的值
int getElem(List *L, int i) {
    if (i < 1 || i > L->length) {
        return 0; // 越界
    }
    return L->data[i-1];
}

// 修改第 i 个元素的值为 elem
int setElem(List *L, int i, int elem) {
    if (i < 1 || i > L->length) {
        return 0; // 越界
    }
    L->data[i-1] = elem;
    return 1;
}

// 返回线性表的长度
int listLength(List *L) {
    return L->length;
}

// 遍历线性表
void traverseList(List *L) {
    int i;
    for (i = 0; i < L->length; i++) {
        printf("%d ", L->data[i]);
    }
    printf("\n");
}

int main() {
    List L;
    initList(&L);
    listInsert(&L, 1, 1);
    listInsert(&L, 2, 2);
    listInsert(&L, 3, 3);
    printf("插入 1, 2, 3 后的线性表:");
    traverseList(&L);  // 打印:1 2 3
    listDelete(&L, 2);
    printf("删除第 2 个元素后的线性表:");
    traverseList(&L);  // 打印:1 3

    int elem = getElem(&L, 2);
    printf("第 2 个元素的值为%d\n", elem);  // 打印:第 2 个元素的值为3
    setElem(&L, 1, 4);
    printf("修改第 1 个元素的值为 4 后的线性表:");
    traverseList(&L);  // 打印:4 3
    printf("线性表的长度为 %d\n", listLength(&L)); // 打印:线性表的长度为 2
    int pos = locateElem(&L, 3);
    if (pos) {
        printf("元素 3 的下标为 %d\n", pos);  // 打印:元素 3 的下标为 2
    } else {
        printf("元素 3 没有找到\n");
    }
    return 0;
}

输出结果如下:

文章来源:https://blog.csdn.net/m0_71369515/article/details/134889458
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。