数据结构入门-离散存储(链表)

一、预备知识：typedef

基本使用

#include <stdio.h>

typedef int AAA; // 为int再重新取一个名字，AAA就等于int

typedef struct Student
{
    int sid;
    char name[100];
    char sex;
}ST;

int main(void)
{

    int i = 10; // 等价于 AAA = 10; 

    struct Student st;  // 等价于  ST st;
    struct Student * ps = &st;  // 等价于 ST * ps = &st;


    ST st2;
    st2.sid = 10;

    printf("%d \n", st2.sid);

    return 0;
}

也可以这样使用，这样更加的方便

#include <stdio.h>


typedef struct Student
{
    int sid;
    char name[100];
    char sex;
}* PST;  // PST等价于 typedef struct * 

int main(void)
{
    struct Student st;
    PST ps = &st;

    ps->sid = 99;
    printf("%d\n", ps->sid);

    return 0;
}

还可以把上面的两个结合起来

#include <stdio.h>


typedef struct Student
{
    int sid;
    char name[100];
    char sex;
}* PST , STU;  // PST等价于 typedef struct *  , STU代表了typedef struct

int main(void)
{
    STU st;  // 等价于struct Student st
    PST ps = &st;

    ps->sid = 99;
    printf("%d\n", ps->sid);

    return 0;
}

二、离散存储(链表)

定义：n个节点离散分配，彼此通过指针相连，每一个节点只有一个前驱节点和一个后续节点，首节点没有前驱节点，尾节点没有后续节点

专业术语：

1. 首节点：第一个有效节点
2. 尾节点：最后一个有效节点
3. 头节点：首节点前面
4. 头指针：指向头节点的指针变量
5. 尾指针：指向尾节点的指针变量

注意：头节点的数据类型和首节点类型一样，头节点里面没有存放有效数据，没有实际含义，为了方便对链表的操作

如果通过希望一个函数来对链表进行处理，我们至少需要接收链表的那些参数

只需要一个参数：头指针

因为我们可以通过头指针推算出链表的其他所有参数

每一个链表节点的数据类型如何表示

#include <stdio.h>

typedef struct Node
{
    int data;  // 数据域
    struct Node * pNext; // 指针域 指向了和它本身类型一样的另外一个节点
}NODE , *PNODE;
// NODE 等价于struct Node
// PNODE 等价于struct Node *

int main(void)
{
    return 0;
}

分类：

1. 单链表
2. 双链表：每一个节点有两个指针域
3. 循环链表：能通任何一个节点找到其他所有的节点
4. 非循环链表

算法：

1. 遍历
2. 查找
3. 清空
4. 销毁
5. 求长度
6. 排序
7. 删除节点
8. 插入节点

算法

狭义的算法是与数据的存储方式密切相关

广义的算法与数据的存储方式无关

泛型

利用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的

多敲代码，熟练的掌握，并进行改进

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



typedef struct Node
{
    int data;
    struct Node * pNext;
}NODE , *PNODE;   // NODE等价于struct Node ， PNODE等价于struct Node *


PNODE create_list(void);
void traverse_list(PNODE pHead);
bool is_empty(PNODE pHead);
int length_list(PNODE pHead);
bool insert_list(PNODE , int ,int); // 第二个是插入位置，第三个是插入的值
bool delete(PNODE , int, int*); // 第二个是删除的位置，第三个是所删除位置的值
void sort_list(PNODE pHead);



int main(void)
{
    PNODE pHead = NULL; // 等价于struct Node * pHead = NULL;

    pHead = create_list(); // 创建一个非循环单链表，并将该链表的头节点地址付给pHead

    // if(is_empty(pHead))
    //  printf("链表为空\n");
    // else
    //  printf("链表不为空\n");

    // printf("链表的长度为%d\n", length_list(pHead) );
    // sort_list(pHead);
    insert_list(pHead , 4, 99);

    int val;
    if(delete(pHead, 1 , &val))
    {
        printf("删除成功，你删除的是%d\n", val);
    }
    else
    {
        printf("删除失败\n");
    }
    
    traverse_list(pHead);


    return 0;
}


// 构建一个链表，并把头节点地址值返回
PNODE create_list(void)
{
    int len;
    int i;
    int val; // 用来临时存放用户输入的节点的值

    // 分配了一个不存放数据的头结点
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (pHead == NULL)
    {
        printf("分配失败，程序终止！\n");
        exit(-1);
    }

    // pTail始终执行的都是尾结点
    PNODE pTail = pHead;
    pTail->pNext = NULL;


    printf("请输入你需要生成的链表节点的个数：\n");
    scanf("%d" , &len);

    for (i = 0; i < len; ++i)
    {
        printf("请输入第%d个节点的值:", i+1);
        scanf("%d" , &val);

        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if (pNew == NULL)
        {
            printf("分配失败，程序终止！\n");
            exit(-1);
        }

        pNew->data = val;
        pTail->pNext = pNew;
        pNew->pNext = NULL;
        pTail = pNew;
    }

    return pHead;
}

// 进行遍历
void traverse_list(PNODE pHead)
{
    // 自定义一个指针用于遍历
    PNODE p = pHead->pNext;
    while(p != NULL){
        printf("%d ",p->data );
        p = p->pNext;
    }
    return;
}


// 判断链表是否为空
bool is_empty(PNODE pHead)
{
    if (pHead->pNext == NULL)
        return true;
    else
        return false;
}

// 链表的长度
int length_list(PNODE pHead)
{
    // 自定义一个指针用于计算链表的长度
    PNODE p = pHead->pNext;
    int len = 0;

    while(NULL != p)
    {
        ++len;
        p = p->pNext;
    }
    return len;
}

// 进行排序
void sort_list(PNODE pHead)
{
    // 这里和数组的排序差不多，思想是一样的


    int i , j , t;
    PNODE p , q;

    int len = length_list(pHead);

    for (i = 0 , p = pHead->pNext; i < len -1; ++i , p = p->pNext)
    {
        for (j = i+1 , q = p->pNext; j < len; ++j , q = q->pNext)
        {
            if (p->data > q->data)
            {
                t = p->data;
                p->data = q->data;
                q->data = t;
            }
        }
    }

    return;

}



// 插入操作
// 在pHead所指向链表的第pos个节点的前面插入一个新的结点，该结点的值是val，pos从1开始
bool insert_list(PNODE pHead, int pos , int val)
{

    int i = 0;
    PNODE p = pHead;

    while(NULL != p && i < pos-1)
    {
        p = p->pNext;
        ++i;
    }

    if (i > pos-1 || NULL == p)
        return false;


    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if (NULL == pNew)
    {
        printf("动态分配内存失败\n");
        exit(-1);
    }
    pNew->data = val;
    PNODE q = p->pNext;
    p->pNext = pNew;
    pNew->pNext = q;

    return true;
}

// 删除操作
bool delete(PNODE pHead , int pos, int * pval)
{

    int i = 0;
    PNODE p = pHead;

    while(NULL != p->pNext && i < pos-1)
    {
        p = p->pNext;
        ++i;
    }

    if (i > pos-1 || NULL == p->pNext)
        return false;



    PNODE q = p->pNext;
    *pval = q->data;

    // 删除p结点后面的结点
    p->pNext = p->pNext->pNext;
    free(q);
    q = NULL;

    return true;
}