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

标题: 单向链表之--添加结点的程序详解 [打印本页]

作者: 爱51hei 时间: 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);//打印结果

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

欢迎光临 (http://www.51hei.com/bbs/)