java自学教程|www.konglongmei.com

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

more +社区更新Forums

more +随机图赏Gallery

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

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

[复制链接]
小雨敲窗y | 显示全部楼层 发表于: 2019-12-3 00:32:32
小雨敲窗y 发表于: 2019-12-3 00:32:32 | 显示全部楼层 |阅读模式
查看: 68|回复: 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, 2020-7-16 01:47 , Processed in 0.097504 second(s), 27 queries .

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