线性表-单链表存储

/** 链表是由N个结点链接起来的
 *  单链表 ： 每个结点只有一个指针域,（单方向）
 *
 *  结点由两部分组成：数据域和指针域
 *  数据域 -> 存储数据元素
 *  指针域 -> 存储结点之间的位置关系。 如单链表 只存储后继位置的指针
 *
 */


/** 头结点和头指针的异同
 *
 *  头指针 是指向链表第一个结点的指针；若链表有头结点，则是指向头结点的指针
 *        头指针具有标识的作用，常用来指代链表的名字
 *        无论链表是否为空，头指针均不为空。<头指针必须存在>
 *
 *  头结点 是为了操作的统一和方便而设立的，放在第一元素的结点之前 方便在第一元素前插入结点和删除第一结点
 *        <头结点不是必须存在的要素>
 */

1.插入结点

插入结点

1.s->next = p->next  先让p的后续结点改为s的后续结点
2.p->next = s   再把s变为p的后续结点

2.头插法

头插法

3.结点删除

删除结点

#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
typedef int ElemType;
typedef struct node {
    ElemType data;
    struct node *next;
} Node,*LinkList;

/** 此处的小写 node代表结构体的标签名，Node和*LinkList代表新类型 */

/**  用指针引用结构体变量的方式是 ==>  (*指针变量).成员名  or  指针变量名->成员名 or  结构体变量.成员名
 *   注意：*p两边的括号不可省略， 因为成员运算符 '.' 的优先级高于指针运算符'*'
 *   指针变量 p 指向的是结构体变量Node第一个成员的地址，
 *   ->是指向结构体成员运算符，它的优先级 同结构体成员运算符'.' 一样高
 *
 */


/** 头插法初始化 头插法是创建了一个节点 一直放在头部*/
void createList_Head (LinkList *list, int n) {
    
    *list = (LinkList)malloc(sizeof(Node));
    (*list)->next = NULL;
   
    for (int i =0; i < n; i++) {
        LinkList p = (LinkList)malloc(sizeof(Node));
        p->data = I;
        p->next = (*list)->next;
        (*list)->next = p;
        printf("create address %d %p\n",i,p);
    }
}


/** 尾插法初始化*/
void createList_tail(LinkList *list, int n) {
    *list = (LinkList)malloc(sizeof(Node));
    (*list)->next = NULL;
    
    LinkList p = (*list);
    
    for (int i = 0; i < n; i++) {
        LinkList node = (LinkList)malloc(sizeof(Node));
        node->data = I;
        p->next = node;
        p = node;
    }
    p->next = NULL;
}

/** 遍历数据*/
void iteraotrList (LinkList *list) {
    LinkList p = *list;
    p=p->next;
    while (p) {
        printf("++current is data is %d,address is %p\n",p->data,p);
        p=p->next;
    }
}

/** 查找第i个位置的元素*/
Status GetElem(LinkList list, int i, ElemType *e) {
    int j;
    LinkList p;
    p = list->next;
    j = 1;
    
    while (p && j<i) {
        p = p->next;
        ++j;
    }
    
    if (!p || j>i) {
        return ERROR;
    }
    *e = p->data;
    return OK;
}

/** 插入*/
Status insertElem(LinkList *list,int i,ElemType e) {
    
    int j = 1;
    LinkList p,insertNode;
    p = *list;
    
    while (p && j < i) {
        p= p->next;
        ++j;
    }
    
    if (!p || j > i) {
        return ERROR;
    }
    
    insertNode =(LinkList)malloc(sizeof(Node));
    insertNode->data = e;
    insertNode->next = p->next;
    p->next = insertNode;
    return OK;
}


/** 删除第i个位置的节点，并返回删除的元素*/
Status list_delete(LinkList *list,int i, ElemType *e) {
    
    LinkList p,q;
    p = *list;
    int j = 1;
    while (p->next && j < i) {
        p = p->next;
        ++j;
    }
    
    if (j > i || !(p->next)) {
        return ERROR;
    }
    
    q = p->next;
    *e = q->data;
    p->next = q->next;
    free(q);
    return OK;
}

/** 清链表的时候 用了两个指针，一个指向将要删除的节点，另一个指向下一个节点*/
Status clearList(LinkList *list) {
    LinkList p,q;
    p = (*list)->next;
    while (p) {
        q = p->next;
        free(p);
        p=q;
    }
    (*list)->next = NULL;
    return OK;
}

#pragma mark - 敲黑板  这是重点
/**     翻转链表
 *  需要借助两个指针
 *  一个指针负责指向next去递归剩下的数据;
 *  一个指针负责指向当前的结点,将当前结点的指针反指 相当于重新生成一个链表 然后执行头插法
 */
LinkList k_reverseList(LinkList header) {
    LinkList currentNodel = header;
    header = NULL;
    while (currentNodel) {
        //取出当前结点，next反指与原来链表断开联系,并移动头结点
        LinkList m = currentNodel;
        m->next = header;
        header = m;

        //移动到下一个结点
        currentNodel = currentNodel->next;
    }
    return header;
}

#pragma mark -使用
void k_node_test() {
    
    LinkList list;
    //头插法生成链表，并遍历
    createList_Head(&list, 10);
    iteraotrList(&list);
    

//    //翻转链表
    printf("\n\n");
    list = k_reverseList(list);
    iteraotrList(&list);
    
//    //尾插法生成链表，并遍历
//    printf("\n\n");
//    createList_tail(&list, 10);
//    iteraotrList(&list);
//
//    //在某个位置插入数据
//    printf("\n\n");
//    insertElem(&list, 2, 20);
//    iteraotrList(&list);
//
//    //删除某个位置的数据，并返回元素
//    printf("\n\n");
//    ElemType deleteEle;
//    list_delete(&list, 5, &deleteEle);
//    iteraotrList(&list);
    
//    printf("清空链表\n");
//    clearList(&list);
}