数据结构-线性表的单链表的基本操作以及实现(C语言)

单链表存储结构的特点

• 用一组任意的存储单元存储线性表的数据元素（这组存储dan元可以是连续的，也可以是不连续的）。
• 在线性表的单链表存储结构中，每一个结点有两个域，一个是 数据域 ,用于存储数据元素值本身，另一个是指针域，用于存储后继结点的地址。
• 链表的每个结点只包含一个指针域，所以成为单链表

知识点

链表增加头节点的作用

• 便于首元结点的处理 。
• 便于空表和非空表的统一处理。

链表特点

• 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
  原文链接：https://blog.csdn.net/Marmara01/article/details/89067123

单链表

单链表的基本操作代码实现

#include <stdio.h>
#define  Status  int
#define  OK 1
#define  ERROR 0
#define maxSize 20
typedef struct Node {
    int data;
    struct Node *next;
} Node, *NodeList;

int insertData(NodeList &list, int i, int data);
int size(NodeList &list);
void showData(NodeList &list);
void initData(NodeList &list) {
    list = new Node;
    list->data = NULL;
}
//求数据域大小函数  根据指针域的下一指针是否NULL 来确定size
int size(NodeList &list) {
    NodeList p;
    p = list;
    int size = 0;
    while (p) {
        p = p->next;
        size++;
    }
    return size-1;
}
//节点插入函数   
int insertData(NodeList &list, int i, int data) {
    NodeList p;  
    p = list;

    int size1 = size(list);

    if (i > size1 + 1) {
        return ERROR;
    }
    for (int j = 0; j < i - 1; ++j) {
        p = p->next;  //找到第i-1的结点（需要插入的位置，原来那位结点之前）  
    }
    NodeList pre = new Node;  
    pre->data = data  //新结点数据域赋值
    pre->next = p->next;;//新结点的next指向i-1位置的next(i结点)
   
    p->next = pre; //将i-1的下一节点指向pre结点
}

void showData(NodeList &list) {
    NodeList p;
    p = list;
    if (size(p) > 0) {
        int i = 0;
        printf("\n数据为:");
        while (p->next) {
            printf("%d\t", p->next->data);
            p = p->next;
        }
    }
}
//删除位置结点   找到需要删除的结点前一位，将找到这一位结点的next指向下一位next
int deleteData(NodeList list, int i) {
    NodeList p;
    p = list;
    if (i < 1 || i > size(list)) {
        return ERROR;
    } else {
        for (int j = 0; j < i - 1; ++j) {
            p = p->next;
        }
        p->next = p->next->next;
    }
}
//求位置结点的数据域值
int getData(NodeList list, int i) {
    NodeList p = list;
    if (i < 1 || i > size(list)) {
        return ERROR;
    } else {
        int j = 0;
        while (j < i) {
            p = p->next;
            j++;
        }
        return p->data;
    }
}


int main() {
    NodeList list;
    initData(list);
    insertData(list, 1, 1);
    insertData(list, 2, 2);
    insertData(list, 3, 3);
    insertData(list, 4, 4);
    insertData(list, 5, 5);
    insertData(list, 6, 6);
    printf("添加完成数据显示\t");
    showData(list);
    deleteData(list, 1);
    printf("\n删除后数据显示\t");
    showData(list);
    int data = getData(list, 4);
    printf("\n取值为%d", data);
}

打印结果显示

添加完成数据显示    
数据为:1   2   3   4   5   6   
删除后数据显示 
数据为:2   3   4   5   6   
取值为5