C语言数据结构不挂科指南之线性表详解

本篇攻略将为大家介绍C语言数据结构中的线性表，包括定义、实现和应用。希望能够为初学者提供帮助，让大家轻松学习和掌握线性表的相关知识。

一、线性表的定义

线性表是由一组元素构成的有限序列，其中每个元素可以有零个或一个前驱元素，也可以有零个或一个后继元素。线性表通常用于存储和处理具有相同类型的数据元素。

线性表的实现方式有多种，包括顺序表、链表等。其中，顺序表采用数组来实现，链表采用指针来实现。

二、线性表的实现

1. 顺序表

顺序表是线性表的一种实现方式，它将元素存储在一段连续的内存空间中，支持随机存取和顺序存取等操作。

顺序表的定义如下：

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

顺序表的主要操作包括：

• 初始化列表
• 插入元素
• 删除元素
• 查找元素
• 遍历元素

示例代码如下：

SeqList initSeqList()
{
    SeqList list;
    list.length = 0;
    return list;
}

int insertElem(SeqList *list, int index, int elem)
{
    // 判断插入位置是否合法
    if (index < 0 || index > list->length || list->length == MAX_SIZE)
        return 0;
    // 将插入位置后面的元素依次往后移动一位
    for (int i = list->length - 1; i >= index; i--)
        list->data[i + 1] = list->data[i];
    // 插入元素
    list->data[index] = elem;
    list->length++;
    return 1;
}

int deleteElem(SeqList *list, int index)
{
    // 判断删除位置是否合法
    if (index < 0 || index >= list->length)
        return 0;
    // 将删除位置后面的元素依次往前移动一位
    for (int i = index + 1; i < list->length; i++)
        list->data[i - 1] = list->data[i];
    list->length--;
    return 1;
}

int searchElem(SeqList list, int elem)
{
    for (int i = 0; i < list.length; i++)
    {
        if (list.data[i] == elem)
            return i;
    }
    return -1;
}

void traverse(SeqList list)
{
    for (int i = 0; i < list.length; i++)
        printf("%d ", list.data[i]);
    printf("\n");
}

2. 链表

链表是线性表的另一种实现方式，它将元素存储在一堆不连续的内存空间中，每个元素都包含一个指向下一个元素的指针。

链表的定义如下：

typedef struct linkNode
{
    int data; // 数据元素
    struct linkNode *next; // 指向下一个元素的指针
} LinkNode, *LinkList;

链表的主要操作包括：

• 初始化列表
• 插入元素
• 删除元素
• 查找元素
• 遍历元素

示例代码如下：

LinkList initLinkList()
{
    LinkList list = (LinkList)malloc(sizeof(LinkNode));
    list->next = NULL;
    return list;
}

int insertElem(LinkList list, int index, int elem)
{
    // 遍历到插入位置的前一个元素
    LinkList p = list;
    for (int i = 0; i < index && p != NULL; i++)
        p = p->next;
    // 判断插入位置是否合法
    if (p == NULL)
        return 0;
    // 创建新节点
    LinkList newNode = (LinkList)malloc(sizeof(LinkNode));
    newNode->data = elem;
    // 将新节点插入到链表中
    newNode->next = p->next;
    p->next = newNode;
    return 1;
}

int deleteElem(LinkList list, int index)
{
    // 遍历到删除位置的前一个元素
    LinkList p = list;
    for (int i = 0; i < index && p->next != NULL; i++)
        p = p->next;
    // 判断删除位置是否合法
    if (p->next == NULL)
        return 0;
    // 删除节点
    LinkList q = p->next;
    p->next = q->next;
    free(q);
    return 1;
}

int searchElem(LinkList list, int elem)
{
    LinkList p = list->next;
    int index = 0;
    while (p != NULL)
    {
        if (p->data == elem)
            return index;
        p = p->next;
        index++;
    }
    return -1;
}

void traverse(LinkList list)
{
    LinkList p = list->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

三、线性表的应用

线性表在实际编程中应用广泛，包括列表、堆栈、队列等。以堆栈为例，堆栈是一种后进先出（LIFO）的数据结构，可以使用线性表实现。

堆栈的主要操作包括：

• 初始化堆栈
• 压入元素
• 弹出元素
• 获取栈顶元素
• 判断堆栈是否为空
• 清空堆栈

示例代码如下：

typedef struct stack
{
    SeqList list;
} Stack;

void initStack(Stack *s)
{
    s->list = initSeqList();
}

int push(Stack *s, int elem)
{
    return insertElem(&(s->list), s->list.length, elem);
}

int pop(Stack *s)
{
    return deleteElem(&(s->list), s->list.length - 1);
}

int top(Stack s)
{
    return s.list.data[s.list.length - 1];
}

int isEmpty(Stack s)
{
    return s.list.length == 0;
}

void clear(Stack *s)
{
    s->list.length = 0;
}

四、结语

以上就是C语言数据结构不挂科指南之线性表详解的全部内容。希望本篇攻略能够对初学者有所帮助，让大家更好地理解和掌握线性表的相关知识。