C语言线性表全面梳理操作方法

线性表概述

线性表是一种常用的数据结构，是指数据元素之间存在一定逻辑顺序，每个元素都有唯一的前驱和后继。

线性表有两种存储方式： 顺序存储结构 和 链式存储结构。

顺序存储结构

顺序存储结构是指采用顺序存储方式存储线性表，即将线性表的元素依次存储在一段连续的存储空间内。

代码示例：创建顺序存储线性表

#define MaxSize 100   // 定义线性表最大长度
typedef struct{
    int data[MaxSize]; // 存储顺序表的元素
    int length; // 当前线性表的长度
} SeqList;

void CreateSeqList(SeqList *L, int n){
    int i;
    printf("请输入%d个元素：\n", n);
    for(i=0; i<n; i++){
        scanf("%d", &L->data[i]); // 输入数据
    }
    L->length = n; // 修改线性表长度
}

代码示例：访问顺序表元素

int GetElem(SeqList *L, int i){
    if(i<1 || i>L->length){ // i值不合法
        printf("查找位置不合法\n");
        return -1;
    }
    return L->data[i-1]; // 返回第i个位置上的元素
}

链式存储结构

链式存储结构是指采用链式存储方式存储线性表，即将线性表的元素存储在多个存储空间中，两个相邻元素之间通过指针相连。

代码示例：创建链式存储线性表

typedef struct ListNode{
    int data; // 数据域
    struct ListNode *next; // 指针域
} ListNode, *LinkList;

void CreateLinkList(LinkList *L, int n){
    int i;
    ListNode *p;
    *L = (LinkList)malloc(sizeof(ListNode)); // 创建头结点
    (*L)->next = NULL; // 空链表
    printf("请输入%d个元素：\n", n);
    for(i=0; i<n; i++){
        p = (ListNode*)malloc(sizeof(ListNode));
        scanf("%d", &p->data); // 输入数据
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

代码示例：访问链式表元素

int GetElem(LinkList L, int i){
    int j = 1;
    ListNode *p = L->next;
    while(p && j<i){ // 寻找第i个结点
        p = p->next;
        j++;
    }
    if(!p || j>i){ // i不合法
        printf("查找位置不合法\n");
        return -1;
    }
    return p->data;
}

操作方法

C语言提供了丰富的线性表操作方法，以下是常用的操作方法：

1. 插入操作

在线性表的指定位置插入一个元素，需要将插入位置后续的元素依次后移。

顺序存储结构的插入操作：

void Insert(SeqList *L, int i, int x){
    int j;
    if(L->length==MaxSize){ // 线性表已满，不能插入
        printf("线性表已满，不能插入\n");
        return;
    }
    if(i<1 || i>L->length+1){ // i值不合法
        printf("插入位置不合法\n");
        return;
    }
    for(j=L->length; j>=i; j--){ // 将第i个位置后的元素依次后移
        L->data[j] = L->data[j-1];
    }
    L->data[i-1] = x; // 在位置i插入x
    L->length++; // 线性表长度+1
}

链式存储结构的插入操作：

int Insert(LinkList *L, int i, int x){
    int j = 0;
    ListNode *p = *L, *s;
    while(p && j<i-1){ // 寻找第i-1个结点
        p = p->next;
        j++;
    }
    if(!p || j>i-1){ // i不合法
        printf("插入位置不合法\n");
        return 0;
    }
    s = (ListNode*)malloc(sizeof(ListNode)); // 创建新结点
    s->data = x;
    s->next = p->next; // 插入结点
    p->next = s;
    return 1;
}

2. 删除操作

删除线性表中指定位置的元素，需要将删除位置后续的元素依次前移。

顺序存储结构的删除操作：

int Delete(SeqList *L, int i){
    int j;
    if(i<1 || i>L->length){ // i不合法
        printf("删除位置不合法\n");
        return 0;
    }
    for(j=i; j<L->length; j++){ // 将第i个位置后的元素依次前移
        L->data[j-1] = L->data[j];
    }
    L->length--; // 线性表长度-1
    return 1;
}

链式存储结构的删除操作：

int Delete(LinkList *L, int i){
    int j = 0;
    ListNode *p = (*L), *q;
    while(p->next && j<i-1){ // 寻找第i-1个结点
        p = p->next;
        j++;
    }
    if(!(p->next) || j>i-1){ // i不合法
        printf("删除位置不合法\n");
        return 0;
    }
    q = p->next;
    p->next = q->next; // 删除结点
    free(q);
    return 1;
}

总结

本文介绍了线性表的概念和两种存储方式，以及几种常用的操作方法。顺序存储结构的插入和删除操作需要将后续元素依次前移或后移，效率较低；链式存储结构的插入和删除操作则只需修改指针域，效率较高。对于不同的应用场景选择合适的存储方式和操作方法，可以提高程序的效率。