数据结构·顺序表

乌衣巷2025-10-312025-10-31

😂C语言基本架构

#include<stdio.h>
int main(){   //主函数main
    return 0;  //;一定不要忘了！！！
}

ok那么好，了解完这些后我们来学习线性表

😀顺序表的逻辑定义

线性表是由 n (n>=0)个数据元素(节点)a1,a2,a3…an组成的有限序列。

只有开始节点a1没有直接前趋，只有一个直接后继a2。只有一个终结节点an没有直接后继，只有一个直接前趋an-1

其余的内部节点都有且仅有一个直接前趋和一个直接后继。

😀顺序表的基本运算

InitList( L ):构造一个空的线性表L，即表的初始化。

ListLength( L ):求线性表L中的结点个数，即求表长。

GetNode( L , i ):取线性表中第i个结点。

LocateNode( L , x )在L表中查找值为x的结点，并返回x在L中的位置，如果L中没有节点的值为x,那么就返回一个特殊值表示查找失败。

InsertList( L , x , i ):在表L中的第i个位置插入一个值为x的结点

DeleteList( L , i ):删除线性表L的第i个结点。

案例-顺序表

宏定义

先宏定义一个值来限定顺序表的最大长度

1	#define ListSize 10 //宏定义

结构体的定义

定义顺序表的结构体，包含数组和记录长度的变量

typedef struct {
    int data[ListSize];
    int length;
}SeqList;

函数的调用和实现

1.printList打印顺序表

void printList(SeqList L){
    printf("顺序表表长:%d\n",L.length);
    for (int i = 0; i < L.length; i++) {
        printf("%d",L.data[i]);
        printf("\n");
    }
}

代码解释：先定义了一个无返回值的函数printLis，参数是SeqList L（顺序表结构体）

for循环这里着重讲一下，for循环的作用是循环遍历顺序表中的所有元素，从索引0开始到L.length-1

L.data[ i ]是访问顺序表的第 i+1 个位置的元素

2.initList初始化顺序表

1
2
3

void initList(SeqList* L){  //指针接收地址
    L->length = 0;
}

代码解释：先定义了一个无返回值的函数 initList，参数是SeqList* L，指向顺序表结构体的指针（指针用于接受地址参数）

L->length = 0;是先将顺序表的长度成员设置为0；->是指针访问结构体成员的运算符

🤔何时使用指针？值or指？

当只需要读取数据但是不需要修改时用值，如果需要修改原数据时用指针

值传递（不修改）

void modifyValue(SeqList L) {
    L.length = 100;  // 只修改副本，原数据不变
}

int main() {
    SeqList list;
    list.length = 5;
    modifyValue(list);    // 传递值
    printf("%d", list.length);  // 输出5，未被修改
}

指针传递（修改源数据）

void modifyPointer(SeqList* L) {
    L->length = 100;  // 修改原数据
}

int main() {
    SeqList list;
    list.length = 5;
    modifyPointer(&list); // 传递地址
    printf("%d", list.length);  // 输出100，已被修改
}

3.locateList查找元素位置

int locateList(SeqList L ,int val){
    for(int i = 0;i < L.length;i++)
        if(L.data[i] == val)
            return i;
    return -1;
}

代码解释:int 表示找到返回索引，未找到返回 -1。SeqList L表示顺序表(值传递)，int val表示要查找的目标。

for循环作用为遍历顺序表中的所有元素，从索引0开始，到L.length-1结束。

第三行的if判断是判断当前元素是否等于目标值，如果相等返回 i ，循环结束后如果没有找到目标值，返回 -1 表示查找失败。

😉地址计算公式：

loc(aj) = (j - i) × L + loc(ai)

//loc(ai)：已知元素 ai 的地址

//loc(aj)：要计算的元素 aj 的地址

//i, j：元素的位置索引

//L：每个元素占用的字节数（元素长度）

//j - i：两个元素之间的位置差

4.insertList插入元素

int insertList(SeqList *L,int index,int val){
    if(index < 1 || index > L->length + 1 || index > ListSize)
        return -1;
    for (int j = L->length - 1; j > index - 1; j--) {
        L->data[j+1] = L->data[j];
    }
    L->data[index - 1] = val;
    L->length++;
    return index -1;
}

代码解释：SeqList *L使用指针传递，因为要修改数据表中的内容。

if判断是对插入位置的合法性检查，分别为：位置不能小于1，不能跳过空位插入，不能超过最大容量。

for循环：移动元素（从后往前移动），j从最后一个元素开始，移动到j > index-1（插入位置的前一个）,每个元素向后移动一位，为插入腾出空间。

L->data[index - 1] = val;是在腾出来的位置插入新的值。

一切结束之后要记得更新表长length

😉其他小知识点

1.顺序表的插入时间复杂度为O(n)

2.在一个长度为n的顺序表中的第 i 个元素(1<=i<=n+1)之前插入一个元素时，需向后移动 n - i + 1个元素

3.在表长为n的顺序表上做插入运算，平均要移动的结点数为 n/2

平均移动结点数 = 所有可能情况的移动次数总和 ÷ 情况总数，
可以插入的位置有n + 1个，
移动次数之和为n + (n-1) + (n-2) + ... + 1 + 0=n(n+1)/2，
[n(n+1)/2] ÷ (n+1) = n/2，

5.deleteList删除元素

int deleteList(SeqList *L,int index){
    if(index<1||index>L->length)
        return -1;
    //后继的位置向前移动，从插入的位置到表的最后
    for(int i = index;i<L->length;i++)
        L->data[i-1] = L->data[i];
    L->length --;
    return L->data[index-1];
}

代码解释：SeqList *L是指针传递，因为要修改顺序表。index表示的是删除的位置

if判断：删除位置的合法性检查，分别是位置不能小于 1 ，不能删除不存在的元素。

for循环:移动元素（从前往后移动），i 从删除位置开始(index)，移动到i < L->length，每个后续元素向前移动一位，覆盖被删除的元素

最后记得更新表长length

😉其他小知识点

1.删除第 i 个元素需要移动 n - i个元素

2.顺序表的删除时间复杂度为O(n)

3.在表长为n的顺序表上做删除运算，平均要移动的结点数为 n-1/2

平均移动结点数 = 所有可能情况的移动次数总和 ÷ 情况总数，
可以插入的位置有n个，
移动次数之和为(n-1) + (n-2) + ... + 1 + 0=n(n-1)/2，
[n(n-1)/2] ÷ n = (n-1)/2，

最终的代码奉上

#include<stdio.h>
#define ListSize 10 //宏定义
typedef struct {
    int data[ListSize];//顺序表的数据
    int length; //顺序表的长度
}SeqList;

void printList(SeqList L){
    printf("顺序表表长:%d\n",L.length);
    for (int i = 0; i < L.length; i++) {
        printf("%d",L.data[i]);
        printf("\n");
    }
}

int insertList(SeqList *L,int index,int val){
    if(index<1||index>L->length+1||index>ListSize)
        return -1;
    for (int j = L->length-1; j > index-1; j--) {
        L->data[j+1] = L->data[j];

    }
    L->data[index - 1] = val;
    L->length++;
    return index -1;
}


void initList(SeqList* L){  //指针接收地址
    L->length = 0;
}

int locateList(SeqList L ,int val){
    for(int i = 0;i < L.length;i++)
        if(L.data[i] == val)
            return i;
    return -1;
}

int deleteList(SeqList *L,int index){
    if(index<1||index>L->length)
        return -1;
    //后继的位置向前移动，从插入的位置到表的最后
    for(int i = index;i<L->length;i++)
        L->data[i-1] = L->data[i];
    L->length --;
    return L->data[index-1];
}
int main(){
    SeqList L;  //声明一个SeqList数据容器
    //顺序表的初始化
    initList(&L);


    //顺序表的插入
    insertList(&L,1,1);
    insertList(&L,2,2);
    insertList(&L,3,3);


    //顺序表的打印
    printList(L);//传入值   对数据修改用'&' 传是指针

    deleteList(&L,2);
    printList(L);
    //获取元素的指定下标
    printf("%d\n",locateList(L,1));
    return 0;
};

😂C语言基本架构

😀顺序表的逻辑定义

😀顺序表的基本运算

案例-顺序表

宏定义

结构体的定义

函数的调用和实现

1.printList打印顺序表

2.initList初始化顺序表

🤔何时使用指针？值or指？

3.locateList查找元素位置

😉地址计算公式：

4.insertList插入元素

😉其他小知识点

5.deleteList删除元素

😉其他小知识点

最终的代码奉上

能够耐心看到这里已经打败 99% 的人了!!!🤣

乌衣巷