java自学教程|www.konglongmei.com

作者: 小雨敲窗y
查看: 39|回复: 0

more +社区更新Forums

more +随机图赏Gallery

疯狂Java讲义(第4版) PDF 电子书 百度云 网盘下载疯狂Java讲义(第4版) PDF 电子书 百度云 网盘下载
价值825元 牛客算法通关课程视频教程 第六期 百度云 网盘下载价值825元 牛客算法通关课程视频教程 第六期 百度云 网盘下载
Spring 5核心原理与30个类手写实战 PDF 电子书 百度云 网盘下载Spring 5核心原理与30个类手写实战 PDF 电子书 百度云 网盘下载
Spring 5核心原理与30个类手写实战+Spring Boot编程思想核心篇pdfSpring 5核心原理与30个类手写实战+Spring Boot编程思想核心篇pdf
Spring Boot编程思想核心篇+Spring 5核心原理与30个类手写实战pdfSpring Boot编程思想核心篇+Spring 5核心原理与30个类手写实战pdf
java电子书]微服务架构设计模式 PDF 电子书 百度云 网盘下载java电子书]微服务架构设计模式 PDF 电子书 百度云 网盘下载

[技术知识] 数据结构入门-离散存储(链表)

[技术知识] 数据结构入门-离散存储(链表)

[复制链接]
小雨敲窗y | 显示全部楼层 发表于: 7 天前
查看: 39|回复: 0

你还没有注册,无法下载本站所有资源,请立即注册!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
一、预备知识:typedef

基本使用
  1. #include typedef int AAA; // 为int再重新取一个名字,AAA就等于inttypedef 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;}
复制代码
也可以这样使用,这样更加的方便
  1. #include 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;}
复制代码
还可以把上面的两个结合起来
  1. #include typedef struct Student{    int sid;    char name[100];    char sex;}* PST , STU;  // PST等价于 typedef struct *  , STU代表了typedef structint main(void){    STU st;  // 等价于struct Student st    PST ps = &st;    ps->sid = 99;    printf("%d\n", ps->sid);    return 0;}
复制代码
二、离散存储(链表)

定义:n个节点离散分配,彼此通过指针相连,每一个节点只有一个前驱节点和一个后续节点,首节点没有前驱节点,尾节点没有后续节点
专业术语:

  • 首节点:第一个有效节点
  • 尾节点:最后一个有效节点
  • 头节点:首节点前面
  • 头指针:指向头节点的指针变量
  • 尾指针:指向尾节点的指针变量
注意:头节点的数据类型和首节点类型一样,头节点里面没有存放有效数据,没有实际含义,为了方便对链表的操作
如果通过希望一个函数来对链表进行处理,我们至少需要接收链表的那些参数

只需要一个参数:头指针
因为我们可以通过头指针推算出链表的其他所有参数
每一个链表节点的数据类型如何表示
  1. #include typedef struct Node{    int data;  // 数据域    struct Node * pNext; // 指针域 指向了和它本身类型一样的另外一个节点}NODE , *PNODE;// NODE 等价于struct Node// PNODE 等价于struct Node *int main(void){    return 0;}
复制代码
分类:

  • 单链表
  • 双链表:每一个节点有两个指针域
  • 循环链表:能通任何一个节点找到其他所有的节点
  • 非循环链表
算法:

  • 遍历
  • 查找
  • 清空
  • 销毁
  • 求长度
  • 排序
  • 删除节点
  • 插入节点
算法

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

利用某种技术达到的效果就是:不同的存储方式,执行的操作是一样的
多敲代码,熟练的掌握,并进行改进
  1. #include #include #include 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;}
复制代码
鲁班 Java架构师VIP课程一期共89G视频教程 luban it教程下载:http://www.77cxw.com/download/78
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|网站地图|java自学教程|www.konglongmei.com

GMT+8, 2019-12-10 10:17 , Processed in 0.141589 second(s), 47 queries .

快速回复 返回顶部 返回列表