找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
查看: 3542|回复: 0
收起左侧

单向链表之--添加结点的程序详解

[复制链接]
ID:91442 发表于 2015-10-29 15:32 | 显示全部楼层 |阅读模式
文章目录:
解析uc/os-ii操作系统之-写在前面:http://www.51hei.com/bbs/dpj-39350-1.html
解析uc/os-ii操作系统--之创建一个单向链表:http://www.51hei.com/bbs/dpj-39833-1.html
单向链表之--添加结点的程序详解:http://www.51hei.com/bbs/dpj-39834-1.html
什么是“堆”和“栈”? 动态内存分配? :http://www.51hei.com/bbs/dpj-39835-1.html
C语言函数指针,函数动态回调:http://www.51hei.com/bbs/dpj-39836-1.html

    上一个例程是创建并从头指针开始遍历链表的每一个结点;今天是在此基础上添加或者说插入结点。能看懂本例程并能独自敲出来,说明C语言水平已经达到一定境界了,这是一个大牛人说的。

    C源码:

#include"stdio.h"
#include"malloc.h"

struct node
{
   int num;
   node *next;

};
/*通过3个指针变量*head,*p1,*p2,创建一个若干长的单向链表*/
node* creat()
{
  node *head,*p1,*p2;//声明3个指向结点空间的指针,注意,这里没有赋值指针指向的可能是乱码  
  p1=new node; //给p1赋值,p1先行开辟空间

  scanf("%d",&p1->num);//通过PC键盘给结点数据域变量赋值,p1用来连接结点,因为只有p1已经有明确的指向
  head=p2=p1;//3个指针指向相同的node空间,能不能写成head=p1=p2?
  while(p1->num!=0)
  {
    p1=new node;//通过循环不断开辟新的结点p1,
    scanf("%d",&p1->num);//给新的结点p1数据域变量赋值,该句决定while循环何时结束
    p2->next=p1;//让p2成为链表连接的桥梁,循环刚开始时“ head=p2=p1”所以p2指向第一个结点,有所指向!
    p2=p1;//这两句是本程序的核心思想所在,让p2也指向新开辟出来的结点空间,此时p2有了新的指向!

  }
  p2->next=NULL;//当程序跳出while循环后,说明创建链表已经结束;此时就将最后一个结点指针域指向NULL!
  return head;//返回链表头指针,为什么返回头指针?有了这个链表的头指针,就可以遍历任意一个结点

}
void display(node* head)//链表头指针作为传递参数
{
   node *p=head;
   while(p->next!=NULL)//
   {
     printf("%d\t",p->num);
p=p->next;//这一步很关键!要理解!将下一个结点的指针传递给p,此时p就指向了下一个结点。

   }
   if(p->num!=0)//不输出0
   printf("%d\t",p->num);
}

node * insert(node *head)//传入的是头结点的指针变量,以传入的头结点num变量大小作为插入操作的位置参考
{
   node *p=head;  //生成p保存head结点
   node *newnode=new node;//生成一个新对象或class(类),感觉有点java的意思
   printf("请输入要插入的新结点的值:\n");
   scanf("%d",&newnode->num);//给新结点数据域变量赋值
   newnode->next=NULL;//给新开辟的结点指针域指针赋值NULL,相当于初始化,生成的指针都应该初始化,这样安全!
      //为下一步给它赋值做准备,相当于给新开辟的结点数据域和指针域都初始化
     //判断插入的元素是否是第一个
   if(p->num>newnode->num)//这是本例程的思想,新结点变量赋值与传入的头结点变量做比较
   {
    printf("要插入的结点应该放在第一个上面!\n");
    newnode->next=p;//保存后续结点;将传入的头指针赋值给插入的结点指针域,也就是说newnode成为头指针
    head=newnode;//更新head的值,这一步很值得思考!

   }
   else//如果插入的位置是其他位置的话
   {
bool flag=false;//记录是中间结点还是最后结点
      p=head;
//循环查找
while(p->next->next!=NULL)//p->next->next指的是head后的第二个结点,即判断后续第二个结点是否是尾结点
{
if(p->next->num>newnode->num)
{
printf("插入的是中间位置");
newnode->next=p->next;
    p->next=newnode;
         flag=true;
         break;

}
       p=p->next;
}
if(flag==false)//如果最后一个结点
{
        p->next=newnode;

}
  }


  return head;
}


void main()
{
  node *head=creat();//创建链表头指针
  display(head);//打印结果
  node *head2=insert(head);
  display(head2);//打印结果

}
//这个程序一定要搞懂,通过仿真现象分析代码
回复

使用道具 举报

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

本版积分规则

手机版|小黑屋|51黑电子论坛 |51黑电子论坛6群 QQ 管理员QQ:125739409;技术交流QQ群281945664

Powered by 单片机教程网

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