数据结构-链表

1.链表

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

链表节点分为两个域

数据域：存放各种实际的数据，如：num、score等

指针域：存放下一节点的首地址，如：next等.

struct Node{
	int data;			//数据域
	struct Node* next   //指针域
}

2.链表创建

创建链表（创建一个表头表示整个链表）

//表头
struct Node *createList()
{
    struct Node *head = (struct Node*)malloc(sizeof (struct Node));
    //head成为了结构体变量
    head->next = NULL;
    return head;
}

创建结点

//创建结点
struct Node* createNode(int data)
{
    struct Node *node = (struct Node*)malloc(sizeof (struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

插入结点

//头部插入结点
void insertNodeHead(struct Node *head, int data)
{
    //创建插入的结点
    struct Node *new = createNode(data);

    new->next = head->next;
    head->next = new;
}

删除结点

//指定位置删除
void deleteNode(struct Node *head, int index)
{
    struct Node *pos = head->next;
    struct Node *posFront = head;
    if (pos == NULL)
        return;     //链表为空
    while(pos ->data != index)
    {
        posFront = pos;
        pos = pos->next;
        if (pos == NULL)  //表尾
            return;
    }
    posFront->next = pos->next;
    free(pos);
}

注意：链表的每一个结点都是动态开辟(malloc)出来的，删除结点后需要释放掉。

打印遍历链表

void printList(struct Node *node)
{
    struct Node *p = node->next;
    while(p->next != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

3.测试代码

#include "stdio.h"

struct  Node
{
    int data;
    struct Node *next;
};

struct Node *createList()
{
    struct Node *head = (struct Node*)malloc(sizeof (struct Node));
    //head成为了结构体变量
    head->next = NULL;
    return head;
}

struct Node* createNode(int data)
{
    struct Node *node = (struct Node*)malloc(sizeof (struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

void printList(struct Node *node)
{
    struct Node *p = node->next;
    while(p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
//头部插入节点
void insertNodeHead(struct Node *head, int data)
{
    //创建插入的节点
    struct Node *new = createNode(data);

    new->next = head->next;
    head->next = new;
}

//指定位置删除
void deleteNode(struct Node *head, int index)
{
    struct Node *pos = head->next;
    struct Node *posFront = head;
    if (pos == NULL)
        return;     //链表为空
    while(pos ->data != index)
    {
        posFront = pos;
        pos = pos->next;
        if (pos == NULL)  //表尾
            return;
    }
    posFront->next = pos->next;
    free(pos);
}

int main()
{
    struct node *list = createList();
    insertNodeHead(list,1);
    insertNodeHead(list,2);
    insertNodeHead(list,3);
    insertNodeHead(list,4);
    printList(list);
    deleteNode(list,2);
    printList(list);
    //printf("Hello World!\n");
    return 0;
}