YIXIU

C语言数据结构顺序表和链表

9/2/2023 C语言数据结构

# C 语言数据结构顺序表和链表

# 线性表

线性表 linear list 是 n 个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结

构，常见的线性表:顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

![image-20230902204328051](/Users/mac/Library/Application Support/typora-user-images/image-20230902204328051.png)

# 顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

  • 静态顺序表:使用定长数组存储元素。
  • 动态顺序表:使用动态开辟的数组存储。

顺序表的实现：

#include "SeqList.h"

void SLInit(SL *ps) {
    assert(ps != NULL);
    ps->a = NULL;
    ps->size = ps->capacity = 0;
}

void SLPrint(SL *ps) {
    assert(ps != NULL);
    for (int i = 0; i < ps->size; ++i) {
        printf("%d ", ps->a[i]);
    }
    printf("\n");
}

void SLCheckCapacity(SL *ps) {
    if (ps->size == ps->capacity) {
        int capacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        SLDataType *pr = (SLDataType *) realloc(ps->a, capacity * sizeof(SLDataType));
        if (pr == NULL) {
            perror("SLPushBack:realloc");
            exit(1);
        }
        ps->a = pr;
        ps->capacity = capacity;
    }
}

void SLPushBack(SL *ps, SLDataType x) {
    assert(ps);
    SLCheckCapacity(ps);

    ps->a[ps->size] = x;
    ps->size++;
}

void SLPopBack(SL *ps) {
    assert(ps->size > 0);
    ps->size--;
}

void SLPushFront(SL *ps, SLDataType x) {
    assert(ps);
    SLCheckCapacity(ps);

    for (int i = ps->size; i >= 0; --i) {
        ps->a[i] = ps->a[i - 1];
    }
    ps->a[0] = x;
    ps->size++;
}

void SLPopFront(SL *ps) {
    assert(ps->size > 0);
    for (int i = 0; i < ps->size - 1; ++i) {
        ps->a[i] = ps->a[i + 1];
    }
    ps->size--;
}

int SLFind(SL *ps, SLDataType x) {
    assert(ps);
    for (int i = ps->size; i >= 0; --i) {
        if (ps->a[i] == x) {
            return i;
        }
    }
    return -1;
}

void SLInsert(SL *ps, size_t pos, SLDataType x) {
    assert(pos >= 0 && pos <= ps->size);
    SLCheckCapacity(ps);
    for (int i = ps->size; i >= (int) pos; --i) {
        ps->a[i] = ps->a[i - 1];
    }
    ps->a[pos] = x;
}

void SLErase(SL *ps, size_t pos) {
    assert(pos >= 0 && pos < ps->size);
    for (int i = (int) pos; i < ps->size - 1; ++i) {
        ps->a[i] = ps->a[i + 1];
    }
    ps->size--;
}

void SLDestory(SL *ps) {
    free(ps->a);
    ps->a = NULL;
    ps->size = ps->capacity = 0;
}

# 链表

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链 接次序实现的 。

# 链表的分类

单向或双向

![image-20230902205023638](/Users/mac/Library/Application Support/typora-user-images/image-20230902205023638.png)

带头或不带头

![image-20230902205100788](/Users/mac/Library/Application Support/typora-user-images/image-20230902205100788.png)

循环或非循环

![image-20230902205942486](/Users/mac/Library/Application Support/typora-user-images/image-20230902205942486.png)

链表最常用的两种结构：

  1. 无头单向非循环链表:结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结 构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  2. 带头双向循环链表:结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向 循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而 简单了，后面我们代码实现了就知道了。

# 单向链表

回文结构

![image-20230906153355723](/Users/mac/Library/Application Support/typora-user-images/image-20230906153355723.png)

相交链表

![image-20230906153458736](/Users/mac/Library/Application Support/typora-user-images/image-20230906153458736.png)

环形链表

![image-20230906154459493](/Users/mac/Library/Application Support/typora-user-images/image-20230906154459493.png)

单向链表的实现：

#include "SList.h"

SLTNode *BuySListNode(SLTDataType x) {
    SLTNode *newNode = (SLTNode *) malloc(sizeof(SLTNode));
    assert(newNode);
    newNode->data = x;
    newNode->next = NULL;
    return newNode;
}

void SListPrint(SLTNode *phead) {
    SLTNode *cur = phead;
    while (cur != NULL) {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

// 为什么初始化头节点的时候是指针而不是结构体？
// 假设初始化头节点为结构体
// SLTNode head;
// SListPushBack(&head, 1);
// 当传入结构体的指针后，无法判断head为空：
//   if(*plist == NULL) { // 编译报错
//        plist = newNode;
//        return;
//    }
//  if((plist->data) == NULL) {
//      plist = newNode; // plist为形参，使用完就销毁了
//      return;
//  }
//  假设初始化头节点为指针
// SLTNode* head;
//  传入指针
// SListPushBack(head, 1);
//  if(plist == NULL) {
//      plist = newNode; // plist为形参数，使用完就销毁了
//      return;
//  }
//  传入指针的地址
// SListPushBack(&head, 1);
//  if(*pphead == NULL) { // *pphead得到指针，合法
//      *pphead = newNode; // *pphead得到plist，可以赋值
//      return;
//  }
void SListPushBack(SLTNode **pphead, SLTDataType x) {
    SLTNode *newNode = BuySListNode(x);
    if (*pphead == NULL) {
        *pphead = newNode;
        return;
    }
    SLTNode *cur = *pphead;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;
}

void SListPushFront(SLTNode **pphead, SLTDataType x) {
    SLTNode *newNode = BuySListNode(x);
    newNode->next = *pphead;
    *pphead = newNode;
}

void SListPopBack(SLTNode **pphead) {
    assert(*pphead);
    if ((*pphead)->next == NULL) {
        free(*pphead);
        *pphead = NULL;
        return;
    }
    SLTNode *prev = NULL;
    SLTNode *tail = *pphead;
    while (tail->next != NULL) {
        prev = tail;
        tail = tail->next;
    }
    free(tail);
    prev->next = NULL;
}

void SListPopFront(SLTNode **pphead) {
    assert(*pphead);
    SLTNode *next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
}

SLTNode *SListFind(SLTNode *plist, SLTDataType x) {
    // 如果头节点就是查找的值
    if (plist->data == x) {
        return plist;
    }
    SLTNode *cur = plist;
    while (cur != NULL) {
        if (cur->data == x) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

void SListInsertBefore(SLTNode **pphead, SLTNode *pos, SLTDataType x) {
    assert(pos);
    assert(pphead);
    if (pos == *pphead) {
        SListPushFront(pphead, x);
    } else {
        SLTNode *newNode = BuySListNode(x);
        SLTNode *cur = *pphead;
        while (cur->next != pos) {
            cur = cur->next;
        }
        cur->next = newNode;
        newNode->next = pos;
    }
}

void SListInsertAfter(SLTNode *pos, SLTDataType x) {
    assert(pos);
    SLTNode *newNode = BuySListNode(x);
    SLTNode *next = pos->next;
    pos->next = newNode;
    newNode->next = next;
}

void SListErase(SLTNode **pphead, SLTNode *pos) {
    if (pos == *pphead) {
        SListPopFront(pphead);
        return;
    }
    SLTNode *prev = *pphead;
    while (prev->next != pos) {
        prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    pos = NULL;
}

void SListEraseAfter(SLTNode *pos) {
    assert(pos);
    SLTNode *next = pos->next->next;
    free(pos->next);
    pos->next = next;
}

# 双向链表

![image-20230907225451766](/Users/mac/Library/Application Support/typora-user-images/image-20230907225451766.png)

双向链表的实现：

//
// Created by yixiu on 2023/9/7.
//
#include "List.h"

LTNode *BuyListNode(LTDataType x) {
    LTNode *node = (LTNode *) malloc(sizeof(LTNode));
    if (node == NULL) {
        perror("BuyListNode:malloc");
        exit(1);
    }
    node->data = x;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

// 创建返回链表的头结点.
LTNode *ListInit() {
    LTNode *phead = BuyListNode(-1);
    phead->prev = phead;
    phead->next = phead;
    return phead;
}

// 双向链表销毁
void ListDestory(LTNode *phead) {
    LTNode *cur = phead->next;
    while (cur != phead) {
        LTNode * next = cur->next;
        ListErase(cur);
        cur = next;
    }
    free(cur);
    cur = NULL;
}

// 双向链表打印
void ListPrint(LTNode *phead) {
    LTNode *cur = phead->next;
    while (cur != phead) {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

// 双向链表尾插
void ListPushBack(LTNode *phead, LTDataType x) {
    assert(phead);
    LTNode *node = BuyListNode(x);
    LTNode *tail = phead->prev;
    tail->next = node;
    node->prev = tail;
    node->next = phead;
    phead->prev = node;
}

// 双向链表尾删
void ListPopBack(LTNode *phead) {
    assert(phead);
    assert(phead->next != phead);
    LTNode *tail = phead->prev;
    phead->prev = tail->prev;
    tail->prev->next = phead;
    free(tail);
    tail = NULL;
}

// 双向链表头插
void ListPushFront(LTNode *phead, LTDataType x) {
    assert(phead);
    LTNode *node = BuyListNode(x);
    node->prev = phead;
    node->next = phead->next;
    phead->next->prev = node;
    phead->next = node;
}

// 双向链表头删
void ListPopFront(LTNode *phead) {
    assert(phead);
    assert(phead->next != phead);
    LTNode *nnext = phead->next->next;
    nnext->prev = phead;
    LTNode *node = phead->next;
    free(node);
    node = NULL;
    phead->next = nnext;
}

// 双向链表查找
LTNode *ListFind(LTNode *phead, LTDataType x) {
    assert(phead);
    assert(phead->next != phead);
    LTNode *cur = phead->next;
    while (cur != phead) {
        if (cur->data == x) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

// 双向链表在pos的前面进行插入
void ListInsert(LTNode *pos, LTDataType x) {
    assert(pos);
    LTNode *node = BuyListNode(x);
    pos->prev->next = node;
    node->prev = pos->prev;
    node->next = pos;
    pos->prev = node;
}

// 双向链表删除pos位置的节点
void ListErase(LTNode *pos) {
    assert(pos);
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    free(pos);
    pos = NULL;
}
Last Updated: 3/20/2024, 8:15:43 AM
강남역 4번 출구
Plastic / Fallin` Dild