百科问答小站 logo
百科问答小站 font logo
首页



真心觉得C语言链表很抽象 难学 该如何学习？ 第1页

  1 

user avatar   tongjingHHU 网友的相关建议: 
      

说说我上课时是怎么讲链表这部分的吧，主要思路是带着同学们step by step地从无到有实现链表，在逐步改进的过程中体会，而不是直接给大家一个最终完善的代码看。


首先，对于这几种操作，数组是有点麻烦的：

删除数组中的一个元素、在数组中插入一个元素、在数组末尾添加一个元素。


因此人们想能否有一个办法，处理上面的问题，实现：

–当需要添加一个元素时，会自动添加；


–当需要减少一个元素时，会自动放弃该元素原来占有的内存；


–可以较方便地插入新的元素。



下面，分步骤实现。


1. 定义链表单个节点的数据结构。

       #include <stdio.h>  struct node {  int data;  node *next; };  int main() {  struct node p;  p.data = 1;  return 0; }


2. 尝试用指针的方式来实现，但下面代码会报错

       #include <stdio.h>  struct node {  int data;  node *next; };  int main() {  struct node *p;  (*p).data = 1;  return 0; }


3. 改进下，使用指针前需要先分配存储空间

       #include <stdio.h> #include <stdlib.h>  struct node {  int data;  node *next; };  int main() {  struct node *p;  p=(node *)malloc(sizeof(node));  (*p).data = 1;  return 0; }


4. 实现两个节点的串联，并可以单步跟踪，观察节点在内存中的链接关系。


       #include <stdio.h> #include <stdlib.h>  struct node {  int data;  node *next; };  int main() {  struct node *p1,*p2;  p1=(node *)malloc(sizeof(node));  (*p1).data = 1;   p2=(node *)malloc(sizeof(node));  (*p2).data = 2;   p1->next = p2;  return 0; }


5. 增加链表最后一个节点的结束标志

       #include <stdio.h> #include <stdlib.h>  struct node {  int data;  node *next; };  int main() {  struct node *p1,*p2;  p1=(node *)malloc(sizeof(node));  (*p1).data = 1;   p2=(node *)malloc(sizeof(node));  (*p2).data = 2;   p1->next = p2;   p2->next = NULL;   return 0; }


6.增加一个变量，记录头指针，实现类似这样的效果：


       #include <stdio.h> #include <stdlib.h>  struct node {  int data;  node *next; };  int main() {  struct node *head;   struct node *p1,*p2;  p1=(node *)malloc(sizeof(node));  (*p1).data = 1;   p2=(node *)malloc(sizeof(node));  (*p2).data = 2;   p1->next = p2;   p2->next = NULL;   head = p1;   return 0; }


7. 尝试利用循环语句，实现多个节点的初始化。可以体会如何利用有限的变量实现更多节点的初始化操作。

       #include <stdio.h> #include <stdlib.h>  struct node {  int data;  node *next; };  int main() {  struct node *head,*p1,*p2;;  int i;  head = 0;   for (i=1;i<=5;i++)  {   p1=(node *)malloc(sizeof(node));   (*p1).data = i;   if(head == 0)   {    head = p1;     p2 = p1;   }   else   {    p2->next = p1;     p2 = p1;   }    }  p2->next = 0;   return 0; }


原理图为：


8. 将上面初始化的链表依次输出

       #include <stdio.h> #include <stdlib.h>  struct node {  int data;  node *next; };  int main() {  struct node *head,*p1,*p2;;  int i;  head = 0;   // 初始化链表  for (i=1;i<=5;i++)  {   p1=(node *)malloc(sizeof(node));   (*p1).data = i;   if(head == 0)   {    head = p1;     p2 = p1;   }   else   {    p2->next = p1;     p2 = p1;   }    }  p2->next = 0;   // 输出链表数据  node *p;  p = head;  printf("链表上各结点的数据为：
");  while(p!=0)  {   printf("%d ",p->data);   p=p->next;  }  printf("
");   return 0; }


9.尝试删除链表中的一个节点。实现过程中发现，需要先找到对应的节点。另外，具体实现时发现，需要记录当前节点的前一个节点。

       #include <stdio.h> #include <stdlib.h>  struct node {  int data;  node *next; };  int main() {  struct node *head,*p1,*p2,*p;  int i;  head = 0;   // 初始化链表  for (i=1;i<=5;i++)  {   p1=(node *)malloc(sizeof(node));   (*p1).data = i;   if(head == 0)   {    head = p1;     p2 = p1;   }   else   {    p2->next = p1;     p2 = p1;   }    }  p2->next = 0;   // 删除数据为2的链表节点  p1 = head;  while (p1->data!=2)  {   p2 = p1;   p1 = p1->next;  }  p2->next = p1->next;  delete p1;    // 输出链表数据  p = head;  printf("链表上各结点的数据为：
");  while(p!=0)  {   printf("%d ",p->data);   p=p->next;  }  printf("
");   return 0; }

实现这一步骤，已经可以体会到链表相对于数组的优点了。

这个例子中仅考虑被删除的节点在链表中间，还有被删除的节点是第一个节点、最后一个节点，没有这个节点的特殊情况，需要考虑。


10. 还有插入节点、新增节点、链表排序等功能，利用上面的思路，大家可以自行逐步实现。最后，贴一下相对完整的链表代码。

       // // 实现链表的基本操作 // #include <stdio.h> #include <malloc.h>  struct node // 链表上结点的数据结构 {  int data;  node *next; };  struct node *Create(void)  // 产生一条无序链表 {  struct node *p1,*p2,*head;  // p2指向最后一个结点, p1指向插入结点，head指向头结点  int a;  head = 0;  printf("产生一条无序链表，请输入数据，以-1结束：
");  scanf("%d",&a);  while(a!=-1)   // 1，3，2，4，-1  {   p1 = (node *)malloc(sizeof(node));   p1->data=a;   if(head == 0)  // 插入链表的首部   {    head = p1; p2 = p1;   }   else  // 插入链表尾   {     p2->next = p1; p2 = p1;   }   scanf("%d",&a);  }  if(head)    p2->next = 0;  return (head); }  void Print(struct node *head)  // 输出链表上各结点的数据 {  struct node *p;  p = head;  printf("链表上各结点的数据为：
");  while(p!=0)  {   printf("%d  ",p->data);   p=p->next;  }  printf("
"); }  struct node *Delete_one_node(struct node *head,int num)  // 根据数据值删除链表中的一个结点 {  struct node *p1,*p2;  if(head == 0)  {    printf("链表为空，无结点可删除!
");   return 0;  }  if(head->data == num)  //删除首结点  {       p1 = head;       head = head->next;       free( (void *)p1 );   printf("删除了一个结点!
");  }  else  {               p1 = head;       p2 = head->next;  // p1指向比较节点的前一个结点   while(p2->data != num && p2->next != 0)  // 找到要删除的结点   {      p1 = p2;        p2 = p2->next;   }   if(p2->data == num)  // 删除找到的结点   {     p1->next = p2->next;     free( (void *)p2 );    printf("删除了一个结点!
");   }   else    printf("链表上没有找到要删除的结点!
");  }  return head; }  struct node *Insert(struct node *head,struct node *p)  // 将一个结点插入链表中 {  struct node *p1,*p2;  if(head == 0 )  // 空链表，插入链表首结点  {         head = p;     p->next = 0;   return head;  }  if(head->data >= p->data)  // 非空链表，插入到链表的首结点  {   p->next = head;      head = p;   return head;  }  p2 = p1 = head;  while(p2->next && p2->data <p->data)  // 找到要插入的位置  {   p1 = p2;     p2 = p2->next;  }  if(p2->data < p->data)  // 插入链表尾  {   p2->next = p;    p->next = 0;  }  else  // 插入在p1和p2所指向的结点之间  {   p->next = p2;    p1->next = p;  }  return head; }  struct node *Create_sort(void)  // 产生一条有序链表 {  struct node *p1,*head = NULL;  int a;  printf("产生一条有序链表，请输入数据，以-1结束：
");  scanf("%d",&a);  while(a!=-1)  {   p1 = (node *)malloc(sizeof(node));  // 产生一个新结点   p1->data=a;   head = Insert(head,p1);  // 将新结点插入链表中   scanf("%d",&a);  }  return head; }   void deletechain(struct node *head)  // 释放链表上各结点占用的内存空间 {  struct node *p1;  while(head)  {   p1 = head;   head = head->next;   free( (void *)p1 );  } }  ///////////////////////////////////////////////////////////////////////////// int main() {  struct node * head;  int num;  head = Create();                       // 产生一条无序链表   1，3，2，5，-1   Print(head);                           // 输出链表上的各结点值   printf("输入要删除结点上的整数：
");  scanf("%d",&num);            head = Delete_one_node(head,num);      // 删除链表上具有指定值的结点   2，1  Print(head);       struct node *p1 = (node *)malloc(sizeof(node));  p1->data=4;  head = Insert(head,p1);                // 将新结点插入链表中  Print(head);   deletechain(head);                     // 释放整个链表的结点空间   head = Create_sort();                  // 产生一条有序链表   1，3，2，5，-1  Print(head);  deletechain(head);                     // 释放链表上各结点占用的内存空间   return 0; }


其他相对复杂的知识，包括网上找到的较复杂的源代码，大家都可以用这种方式来学习。先看代码，理解，然后自己尝试step by step地实现，逐渐转换为自己的知识。
真心觉得C语言链表很抽象 难学 该如何学习？ 的其他答案 点击这里
  1 

相关话题

  孙卓养父母按照法律程序，已被采取相应措施，对此你怎么看？ 
  C++ 中，如果指针换了被指向的东西，那被指向的原来的东西（是被 new 出来的）所占的内存会立刻被释放吗？ 
  C 语言用 换行后就无法再回到上一行了吗? 
  为什么说 C/C++ 不适合做 Web 开发？ 
  为什么程序代码被编译成机器码就不能跨平台运行？ 
  i＝1，为什么 (++i)+(++i)＝6？ 
  Visual Studio 2019可以用来玩C语言吗？ 
  这个如此诡异的C语言「怪事」是怎么回事？ 
  c/c++怎么把一个bool数组（刚好8个元素）转换成char？ 
  为什么从机器码反推出C代码是不可能的？ 
前一个讨论
被一个男孩亲吻到天亮是个什么样的感觉？
下一个讨论
微信公众平台插入清晰的数学公式？



服务条款
联系我们
关于我们
隐私政策


© 2024-11-25 - tinynew.org. All Rights Reserved.
© 2024-11-25 - tinynew.org. 保留所有权利