请选择 进入手机版 | 继续访问电脑版
搜索
房产
装修
汽车
婚嫁
健康
理财
旅游
美食
跳蚤
二手房
租房
招聘
二手车
教育
茶座
我要买房
买东西
装修家居
交友
职场
生活
网购
亲子
情感
龙城车友
找美食
谈婚论嫁
美女
兴趣
八卦
宠物
手机

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

[复制链接]
查看: 41|回复: 0

1万

主题

2万

帖子

5万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
52012
发表于 2019-12-3 00:32 | 显示全部楼层 |阅读模式
一、预备常识: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;}
复制代码
免责声明:假如加害了您的权益,请联系站长,我们会实时删除侵权内容,感谢合作!
回复

使用道具 举报

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

本版积分规则

Copyright © 2006-2014 妈妈网-中国妈妈第一,是怀孕、育儿、健康等知识交流传播首选平台 版权所有 法律顾问:高律师 客服电话:0791-88289918
技术支持:迪恩网络科技公司  Powered by Discuz! X3.2
快速回复 返回顶部 返回列表