怎样用尾插法建立链表？

每次将待插入的结点链在单链表的最后一个结点的后面

void creatlist(LinkList *LDatatype a[10])

{ L = (LinkList *) malloc (sizeof(struct node))

L->next = NULL                  //生成头结点    

r = L                           //r为指向表尾的指针

for(i = 0i<=9i++)

{ p = (LinkList *) malloc (sizeof(struct node))

p->data = a[i]         //生成新的结点

p->next = NULL

r->next = p            //将新生成的结点插在表尾

r = p                  //将表尾指针指向新插入的结点

}

}

第一个问题：

#include "stdio.h"

typedef struct lnode

{

int data

struct lnode *next

}lnode,*link

lnode *creat()用尾插入元素创建一个单链表函数；

{

link La,p,qint i,n

La=(link)malloc(sizeof(lnode))创建头结点

La->next=NULL

q=La

printf("input the number of element n:\n")

scanf("%d",&n)输入创建元素的个数n

for(i=1i<=n++i)

{

p=(link)malloc(sizeof(lnode))生成结点并用p指向

printf("input the value of %dth:\n",i)

scanf("%d",&p->data)输入元素的值

printf("\n")

q->next=pq=p

}

q->next=NULL将最后一个结点的next指向空

return (La)返回头结点的指针

}

void out(lnode *La)完成链表的输出函数

{

link p

p=La->next

printf("success output the every element:\n")

while(p)

{

printf("%d",p->data)

p=p->next

}

printf("\n")

}

void main()

{

lnode *Lc,*Ld

Lc=creat()

out(Lc)

}

我用的版本stdio里面包函了malloc函数，如果你用的没有的话，需在最前面引用到源程序文件中去；程序的功能是尾插入法创建一个大小由你输入的n的大小决定的一个带头结点的单链表；运行的时候，先提示你输入n,（n就是要创建的元素个数），然后提示你输入每个元素（由于为了方便，定义元素为int型,当你输入n个数后；则显示创建结果；

第二个问题：

#include "stdio.h"

typedef struct lnode

{

int data

struct lnode *next

}lnode,*link

lnode *creat()

{

link La,p,qint i,n

La=(link)malloc(sizeof(lnode))

La->next=NULL

q=La

printf("input the number of element n:\n")

scanf("%d",&n)

for(i=1i<=n++i)

{

p=(link)malloc(sizeof(lnode))

printf("input the value of %dth:\n",i)

scanf("%d",&p->data)

printf("\n")

q->next=pq=p

}

q->next=NULL

return (La)

}

void out(lnode *La)

{

link p

p=La->next

printf("success output the every element:\n")

while(p)

{

printf("%d",p->data)

p=p->next

}

printf("\n")

}

lnode *lizhi(lnode *Lb)与上一个程序不同之处是多了这个函数，实现单链表

{ lnode *p,*s的就地逆置；

p=Lb->next

Lb->next=NULL

s=p->next

while(p)

{

p->next=Lb->next

Lb->next=p

p=p->next

p=s

s=s->next

}

return (Lb)

}

void main()

{

lnode *Lc,*Ld

Lc=creat()

out(Lc)

Ld=lizhi(Lc)

out(Ld)

}

与上一个程序差不多，唯一不同的是多了一个逆置函数；

以上两个程序都可以成功运行的，你拿去试试吧，祝你成功。

双端链表与传统的链表非常相似，但是它有一个新增的特性：即对最后一个链接点的引用，就像对第一个链接点的引用一样

对最后一个链接点的引用允许项在表头一样，在表尾直接插入一个链接点。当然，仍然可以在普通的单链表的表尾插入一个链接带你，方法是遍历整个链表直到直达表尾，但是这种方法效率很低

像访问表头一样访问表尾的特性，使双端链表更适合于一些普通链表不方便 *** 作的场合，比如频繁要插入队尾元素的场合

双端链表的示例程序

这个程序在表头和表尾各插入三个连点，显示插入后的链表。然后删除头两个链接点，再次显示

表头在重复插入 *** 作会颠倒链接点进入的顺序，而在表尾重复插入则保持链接点进入的顺序

双端链表有两个项，first和last，一个指向链表中的第一个链接点，另一个指向最后一个链接点。如果链表中只有一个链接点，first和last都指向它，如果没有链接点，两者都为null值

插入和删除方法和普通链表的相应部分类似。然而，两个插入方法都要考虑一种特殊情况，即插入前链表是空的，如果isEmpty（）是真，那么insertFirst必须把last指向新的链接点，insertLast也必须把first指向新的链接点

如果用insertFirst （）方法实现在表头插入，first就指向新的链接点，用insertLast()方法实现在表尾插入，last就指向新的链接点。如果链表只有一个链接点，那么从表头删除也是一种特殊情况，last必须被赋值为null值

不幸的是，用双端链表也不能有助于删除最后一个链接点，因为没有一个引用指向倒数第二个链接点，如果最后一个链接点被删除，倒数第二个链接点的next字段应该变成null值，为了删除最后一个链接点，需要一个双向链表，下篇会讨论它

在表头插入和删除速度很快，仅需要改变一两个引用值，所以花费O(1)的时间

平均起来，查找，删除和在指定链接点后面插入都需要搜索链表中一半链接点。需要O(N)此比较，在数组中执行这些 *** 作也需要O(N)次比较，但是链表仍然要快一些，因为当插入和删除链接点时，链表不需要移动任何东西，增加的效率是很明显的，特别是当复制时间远远大于比较时间的时候

当然，链表比数组优越的另外一个重要方面是链表需要多少内存就可以用多少内存，冰倩可以扩展到所有可用内存。数组的大小在它创建的时候就固定了；所以经常由于数组太大导致效率低下，或者数组太小导致空间溢出。向量是一种可扩展的数组，它可以通过可变长度解决这个问题，但是它经常只允许以固定大小的增量扩展（例如快要溢出的时候，就增加一倍数组容量），这个解决方案在内存使用效率上来说还是比链表的低

---