线性表的单向链表实现

线性表的实现方式有很多,可以选择,数组实现,也可以选择链表实现,同时,链表实现上又可以分两种:
一种是单向链表,一种是双向链表.
本篇我们选择单向链表来实现:

#include <stdio.h>
#include <stdlib.h>


typedef int ElementType;
typedef struct Node {
    ElementType data;
    struct Node *pre; //若果有这个指针域,表示的是双向链表
    struct Node *next;//单独有一个指针域表示的是单向链表
} *PNode;

//声明一个线性表类型
typedef PNode List;


/**
 * 查找线性表里指定位置上的数据
 * @param pos
 * @param L
 * @return
 */
PNode findPNode(int pos, List L) {
    List p = L;
    if (p == NULL) return NULL;
    int i = 0;
    while (p != NULL && i < pos) {
        i++;
        p = p->next;
    }
    return p;
}

/**
 * 在线性表指定位置上插入一个数据
 * 这个是单向链表的实现,如果是双向链表的实现,就少了一步查找
 * @param e
 * @param pos
 * @param L
 * @return 返回插入完成之后链表的头指针
 */
List insertData(ElementType e, int pos, List L) {
    List s;
    if (pos < 0) {
        printf("插入位置有误\n");
        return L;
    }
    if (pos == 0) {
        s = (List) malloc(sizeof(struct Node));
        s->data = e;
        s->data = L;
        return s;
    }
    PNode preNode = findPNode(pos - 1, L);
    if (preNode == NULL) {
        return NULL;
    }
    s = (PNode) malloc(sizeof(struct Node));
    s->data = e;
    s->next = preNode->next;
    preNode->next = s;
    return L;
}

//删除方法
List deleteNode(int pos, List L) {

    if (pos < 0 || L == NULL) {
        printf("删除失败\n");
        return L;
    }
    if (pos == 0) {
       PNode deleteNode = L;
        L = L->next;
        free(deleteNode);
        return L;
    }

    //找到要删除节点的上一个节点
    PNode preNode =  findPNode(pos - 1, L);

    if(preNode == NULL){
        printf("删除位置有误\n");
        return L;
    }

    PNode deleteNode = preNode->next;
    if(deleteNode == NULL){
        printf("没有要删除的节点\n");
        return L;
    }
    preNode->next = deleteNode->next;
    free(deleteNode);
    printf("删除成功\n");
    return L;
}

测试代码:

int main() {
    //定义并初始化一个线性表
    List L = NULL;

    for (int i = 0; i < 10; i++) {
        L = insertData(i * 2, i, L);
    }
    printf("-----------打印线性表数据-------------\n");
    PNode p = L;
    for (int i = 0; i < 10; i++) {
        if(p == NULL) break;
        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n-----------开始删除节点-------------\n");
    deleteNode(5,L);
     p = L;
    for (int i = 0; i < 10; i++) {
        if(p == NULL) break;
        printf("%d\t", p->data);
        p = p->next;
    }
    return 0;
}