请教关于尾插法建立单链表的算法
{//用尾插法建立带头结点的单链表
char ch;
LinkList head=(ListNode *)malloc(sizeof(ListNode));//生成头结点
ListNode *s,*r; //工作指针
r=head; // 尾指针初值也指向头结点
while((ch=getchar())!='\n'){
s=(ListNode *)malloc(sizeof(ListNode));//生成新结点
s->data=ch; //将读入的数据放入新结点的数据域中
r->next=s;
r=s;
}
r->next=NULL;//终端结点的指针域置空，或空表的头结点指针域置空
return head;
}
r->next=s;r=s; 关键的这两句不懂，指针r如何工作的，还有链表间的链接我始终没想明白。 展开
tailing是通过在列表尾部逐个插入新节点来创建列表。与前面的插值一样，每次应用新节点时，都会读入相应的数据元素值。不同之处在于，为了将新节点插入表的尾部，需要添加尾部指针r来指向链表的尾部。
[算法步骤]
创建一个只有头节点的空链表。
②尾部指针R的初始化，指向头部节点。
③根据链表创建中包含的元素n的个数，进行n个循环的以下操作：
生成新节点*p；
●将输入元素值赋给新节点*p的数据字段；
●在尾节点*R后插入新节点*P；
●尾部指针R指向新尾部节点*PS
如图所示，线性表（A、B、C、D、E）后插值的创建过程与线性表相同。
【算法描述】
void Createlist_R(Linklist &L, int n) //正位序输入n个元素的值,建立带表头结点的单链表L个人
{
L=new LNode; //先建立一个带头结点的空链表L->next=NULL； //尾指针指向头结点r=L;
for(i=0;i<n:++i) //生成新
{
p=newLNode; //输入元素值赋给新结点p的数据域cin>>p->data; //将新*p插入尾结点*r之后p->next=NULL;r->next=p；
r=p； //r指向新的尾结点*p
}
}
算法时间复杂度为O（n）。
扩展资料：
尾部插入方法从空表开始，重复读取数据，生成新节点，将读取的数据存储在新节点的数据字段中，然后将新节点插入到当前链表的尾部，直到读取标记结束。从空表开始，重复读取数据，生成新节点，将读取的数据存储在新节点的数据字段中，然后将新节点插入到当前链表的末尾，直到读取标志结束。
参考资料来源：
尾插法是通过将新结点逐个插入到链表的尾部来创建链表。同前插法一样,每次申请一个新
结点,读入相应的数据元素值。不同的是,为了使新结点能够插入到表尾,需要增加一个尾指针
r指向链表的尾结点。
【算法步骤】
①创建一个只有头结点的空链表。
②尾指针r初始化,指向头结点。
③根据创建链表包括的元素个数n,循环n次执行以下操作:
●生成一个新结点*p;
●输入元素值赋给新结点*p的数据域;
●将新结点*p插入到尾结点*r之后;
●尾指针r指向新的尾结点*ps
如图所示为线性表(a,b,c,d,e)后插法的创建过程,读入数据的顺序和线性表中的逻辑顺
序是相同的。
【算法描述】
void Createlist_R(Linklist &L, int n) //正位序输入n个元素的值,建立带表头结点的单链表L个人
{
L=new LNode; //先建立一个带头结点的空链表
L->next=NULL； //尾指针指向头结点
r=L;
for(i=0;i<n:++i) //生成新结点
{
p=new LNode; //输入元素值赋给新结点p的数据域
cin>>p->data; //将新结点*p插入尾结点*r之后
p->next=NULL; r->next=p；
r=p； //r指向新的尾结点*p
}
}
算法时间复杂度为O（n）。
扩展资料：
尾插法是从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到读入结束标志为止。
从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到读入结束标志为止。
参考资料来源：百度百科-尾插法
已赞过
已踩过<
