设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › 数据结构与算法 › 非循环单链表及操作
返回列表 发新帖
查看: 1199|回复: 0

[学习笔记] 非循环单链表及操作

[复制链接]
Julia999
发表于 2019-8-1 16:18:22 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
本帖最后由 Julia999 于 2019-8-1 16:18 编辑
离散存储【链表】定义：n个结点离散分配
           彼此通过指针项链
           每个结点只有一个前驱节点，一个后续节点
           首节点没有前驱节点，尾节点没有后续节点

专业术语：
首节点：第一个有效的节点
尾节点：最后一个个有效的节点
头结点：第一个有效节点前面的节点，并不存放有效数据，加头结点的主要目的是方便对链表的操作
头节点的数据类型和首节点的一样
头指针：指向头结点的指针变量（存放头结点的地址）
尾指针：指向尾节点的指针

如果希望通过一个函数对链表进行处理，我们至少需要哪一些参数：
只需要一个：头指针，因为我们通过头指针，可以推算出链表的所有信息
  1. //构造节点
  2. typedef struct Node
  3. {
  4.         int data;   //数据域
  5.         //指针指向的是跟自己本身类型相同的一个节点
  6.          struct Node *pNext;  //指针域
  7. }NODE, *PNODE;  //NODE 等于与struct Node  PNODE 等价于stru
复制代码


创建一个单链表并遍历：
  1. #include<stdio.h>
  2. #include<malloc.h>
  3. #include<stdlib.h>

  5. //构造节点
  6. typedef struct Node
  7. {
  8.         int data;   //数据域
  9.         //指针指向的是跟自己本身类型相同的一个节点
  10.         struct Node *pNext;  //指针域
  11. }NODE, *PNODE;  //NODE 等于与struct Node  PNODE 等价于struct Node*

  13. PNODE creat_list(void)
  14. {
  15.         int len;  //用来存放有效节点的个数
  16.         int val; //用来临时存放节点的值
  17.    
  18.         //分配了一个不存放有效数据的头结点
  19.         PNODE pHead=(PNODE)malloc(sizeof(NODE));
  20.         if(NULL==pHead)
  21.         {
  22.                 printf("分配失败！");
  23.                 exit(-1);
  24.         }
  25.    

  27.         //使pTail永远指向尾节点
  28.         PNODE pTail=pHead;
  29.         pTail->pNext=NULL;

  31.         printf("请输入你需要生成链表节点的个数:");
  32.         scanf("%d",&len);

  34.         //每循环一次，就用pNew生成了一个节点，并将节点的数据域赋值
  35.         for(int i=0;i<len;i++)
  36.         {
  37.                 printf("请输入第%d个节点的值");
  38.                 scanf("%d",&val);

  40.                 PNODE pNew=(PNODE)malloc(sizeod(NODE));
  41.                 if(NULL==pNew)
  42.                 {
  43.                     printf("分配失败！");
  44.                 exit(-1);
  45.                 }
  46.                 pNew->data=val;

  48.                 pTail->pNext=pNew;
  49.                 pNew->pNext=NULL;
  50.                 pTail=pNew;

  52.         }
  53.         return pHead;
  54. }

  56. void traverse_list(PNODE pHead)  //遍历
  57. {
  58.         //使p指向第一个有效节点
  59.         PNODE p=pHead->next;
  60.         while(NULL!=p)
  61.         {
  62.                 //当链表不为空的时候
  63.                 printf("%d  ",p->data);
  64.                 p=p->pNext;
  65.         }
  66.         printf("\n");
  67. }

  69. int main()
  70. {
  71.         PNODE pHead=NULL;  //等价于 struct Node *pHead=NULL
  72.         pHead=creat_list();  //创建一个非循环单链表，并将该链表的头结点的地址赋给pHead   
  73.     traverse_list(pHead);

  75.         return 0;
  76. }
复制代码


分类：
单链表
双链表：每一个节点有两个指针域
循环链表：能通过任何人一个节点找到其他所有的节点
非循环链表


算法：
遍历
查找
清空
销毁
求长度
排序
删除节点（删除p指向的节点之后的那一个节点）
  1. r=p->next;   //必须将p->next给r，这样方便释放
  2.         p->next=p->next->next;  //p->next保存的是下一个节点的地址，也就是下一个节点，p->next->next表示的是下一个节点的指针域，也就是保存了下下个结点的地址，也就是下下个节点，直接将p的指针域指向下下个结点
  3.         free(r);
复制代码
插入节点
（将q指向的节点放在p指向的节点之后）
  1. q->next=p->next;  //将q的指针域指向p的下一个节点(q是一个指针变量，储存的是q的地址，所以q->next就是q的指针域，p->next存储的是p的下一个节点的地址，也就是p的下一个节点)
  2.         p->next=q;
复制代码

对单链表的各种操作例子：
  1. #include<stdio.h>
  2. #include<malloc.h>
  3. #include<stdlib.h>

  5. //构造节点
  6. typedef struct Node
  7. {
  8.         int data;   //数据域
  9.         //指针指向的是跟自己本身类型相同的一个节点
  10.         struct Node *pNext;  //指针域
  11. }NODE, *PNODE;  //NODE 等于与struct Node  PNODE 等价于struct Node*

  13. PNODE creat_list(void)
  14. {
  15.         int len;  //用来存放有效节点的个数
  16.         int val; //用来临时存放节点的值
  17.    
  18.         //分配了一个不存放有效数据的头结点
  19.         PNODE pHead=(PNODE)malloc(sizeof(NODE));
  20.         if(NULL==pHead)
  21.         {
  22.                 printf("分配失败！");
  23.                 exit(-1);
  24.         }
  25.    

  27.         //使pTail永远指向尾节点
  28.         PNODE pTail=pHead;
  29.         pTail->pNext=NULL;

  31.         printf("请输入你需要生成链表节点的个数:");
  32.         scanf("%d",&len);

  34.         //每循环一次，就用pNew生成了一个节点，并将节点的数据域赋值
  35.         for(int i=0;i<len;i++)
  36.         {
  37.                 printf("请输入第%d个节点的值");
  38.                 scanf("%d",&val);

  40.                 PNODE pNew=(PNODE)malloc(sizeod(NODE));
  41.                 if(NULL==pNew)
  42.                 {
  43.                     printf("分配失败！");
  44.                 exit(-1);
  45.                 }
  46.                 pNew->data=val;

  48.                 pTail->pNext=pNew;
  49.                 pNew->pNext=NULL;
  50.                 pTail=pNew;

  52.         }
  53.         return pHead;
  54. }

  56. void traverse_list(PNODE pHead)  //遍历
  57. {
  58.         //使p指向第一个有效节点
  59.         PNODE p=pHead->next;
  60.         while(NULL!=p)
  61.         {
  62.                 //当链表不为空的时候
  63.                 printf("%d  ",p->data);
  64.                 p=p->pNext;
  65.         }
  66.         printf("\n");
  67. }


  70. bool is_empty(PNODE pHead)
  71. {
  72.         if(pHead->pNext==NULL)
  73.                 return true
  74.         else
  75.         return false;
  76. }

  78. int lenght_list(PNODE pHead)
  79. {
  80.         PNODE p=pHead->pNext;
  81.         int len=0;
  82.         while(NULL!=p)
  83.         {
  84.                 ++len;
  85.                 p=p->pNext;
  86.         }
  87.         return len;
  88. }

  90. //在pHead所指向链表的第pos个结点的前面插入一个新的节点，这个节点的值是val，并且pos的值是从1开始
  91. bool insert_list(PNODE pHead,int pos,int val)
  92. {
  93.         int i=0;
  94.         PNODE p=pHead;
  95.         while(NULL!=p&&i<pos-1)
  96.         {
  97.                 p=p->pNext;
  98.                 ++i;
  99.         }
  100.         if(i>pos-1||NULL=p)
  101.                 return false;

  103.         PNODE pNew=(PNODE)malloc(sizeof(NODE));
  104.         if(NULL=pNew)
  105.         {
  106.                 printf("动态分配内存失败");
  107.                 exit(-1);
  108.         }
  109.         pNew->data=val;
  110.         PNODE p=p->pNext;
  111.         p->pNext=pNew;
  112.         pNew->pNext=q;

  114.         return true;

  116. }

  118. bool delete_list(PNODE pHead,int pos,int *pVal)
  119. {
  120.         int i=0;
  121.         PNODE p=pHead;
  122.         while(NULL!=p->pNext&&i<pos-1)
  123.         {
  124.                 p=p->pNext;
  125.                 ++i;
  126.         }
  127.         if(i>pos-1||NULL==p->pNext)
  128.                 return false;

  130.         //保存要删的节点
  131.         PNODE q=p->pNext;
  132.         *pVal=q->data;

  134.         //删除p节点后面的节点
  135.         p->pNext=p->pNext->pNext;
  136.         free(q);
  137.         q=NULL;

  139.         return true;

  141. }

  143. void sort_list(PNODE pHead)
  144. {
  145.         int len=length_list(pHead);
  146.         PNODE p,q;
  147.         for(int i=0,p=pHead->pNext;i<len-1;i++,p=p->pNext)
  148.         {
  149.                 for(int j=i+1,q=p->pNext;j<len;j++,q=q->qNext)
  150.                 {
  151.                         if(p->data>q->data)
  152.                         {
  153.                                 t=p->data;
  154.                                 p->data=q->data;
  155.                                 q->data=t;
  156.                         }

  158.                 }
  159.         }
  160.         return;

  162. }


  165. int main()
  166. {
  167.         int val;
  168.         PNODE pHead=NULL;  //等价于 struct Node *pHead=NULL
  169.         pHead=creat_list();  //创建一个非循环单链表，并将该链表的头结点的地址赋给pHead   
  170.     traverse_list(pHead);

  172.         sort_list(pHead);
  173.         traverse_list(pHead);

  175.         insert_list(pHead,4,33);
  176.         traverse_list(pHead);

  178.         delete_list(pHead,2,&val);
  179.         traverse_list(pHead);

  181.         return 0;
  182. }
复制代码




想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-4-29 01:21

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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