单链表的建立(C语言):头插法和尾插法建立单链表
下面说一下如果用C语言建立单链表,分为头插法和尾插法两种。
图2-4 头插法建立单链表
头插法建立单链表的算法如下:
图2-5 尾插法建立单链表
尾插法建立单链表的算法如下:
采用头插法建立单链表
该方法从一个空表开始,生成新结点,并将读取到的数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头,即头结点之后,如图2-4所示。图2-4 头插法建立单链表
头插法建立单链表的算法如下:
LinkList CreatList1(LinkList &L){ //从表尾到表头逆向建立单链表L,每次均在头结点之后插入元素 LNode *s;int x; L=(LinkList)malloc(sizeof(LNode)); //创建头结点 L->next=NULL; //初始为空链表 scanf("%d", &x); //输入结点的值 while(x!=9999) { //输入 9999 表示结束 s=(LNode*)malloc(sizeof(LNode) ); //创建新结点 s->data-x; s->next=L->next; L->next=s; //将新结点插入表中,L为头指针 scanf ("%d", &x); } //while 结束 return L; }釆用头插法建立单链表,读入数据的顺序与生成的链表中元素的顺序是相反的。每个结点插入的时间为O(1),设单链表长为n,则总的时间复杂度为O(n)。
采用尾插法建立单链表
头插法建立单链表的算法虽然简单,但生成的链表中结点的次序和输入数据的顺序不一致。若希望两者次序一致,可采用尾插法。该方法是将新结点插入到当前链表的表尾上,为此必须增加一个尾指针r,使其始终指向当前链表的尾结点,如图2-5所示。图2-5 尾插法建立单链表
尾插法建立单链表的算法如下:
LinkList CreatList2(LinkList &L){ //从表头到表尾正向建立单链表L,每次均在表尾插入元素 int x; // 设元素类型为整型 L=(LinkList)malloc(sizeof(LNode)); LNode *s, *r=L; //r 为表尾指针 scanf ("%d", &x); //输入结点的值 while (x!=9999) { //输入 9999 表示结束 s=(LNode *)malloc(sizeof(LNode)); s->data=x; r->next=s; r=s; //r指向新的表尾结点 scanf ("%d", &x); } r->next = NULL; //尾结点指针置空 return L; }因为附设了一个指向表尾结点的指计,故时间复杂度和头插法相同。