鏈表的定義
typedef int ElemType;
typedef struct LNode{
ElemType data; //數(shù)據(jù)域
struct LNode *next; //指針域
}LNode,*LinkList;
一、頭插法
-
什么是頭插法?
在插入時，新的結(jié)點插入到當前鏈表的表頭。 -
怎么實現(xiàn)頭插法?
??思考一：頭插法的核心是什么?
以有頭結(jié)點為例：
只需要將新的節(jié)點插在頭結(jié)點和首元結(jié)點之間。所以核心代碼為:s->next=L->next; ① L->next=s; ②
注意：①②能否交換順序?
假設可以，那么代碼為：② L->next=s; ① s->next=L->next;
先②后①圖：
千萬不能交換呦?? 重點一：以帶頭結(jié)點方式實現(xiàn)頭插法
- 動圖：
- 圖解
- 代碼
LinkList HeadInster(LinkList &L,int n){ LNode *s; int x=1; L= (LinkList)malloc(sizeof(LNode)); //創(chuàng)建頭結(jié)點 L->next=NULL; //初始為空鏈表 while(x!=n){ s=(LNode*) malloc(sizeof(LNode)); //創(chuàng)建新結(jié)點 s->data=x; s->next=L->next; //核心代碼 L->next=s; //核心代碼 x++; } return L; }
?? 重點二：以不帶頭結(jié)點方式實現(xiàn)頭插法
- 動圖解析
- 圖解
- 代碼
LinkList Headinster(LinkList &L,int n){ LNode *s; int x=1; L= (LinkList)malloc(sizeof(LNode)); L->data=x++; L->next=NULL; while(x!=n){ s=(LNode*) malloc(sizeof(LNode)); s->data=x; s->next=L; L=s; x++; } return L; }
- 動圖：
二、尾插法
-
什么是尾插法?
在插入時，新的結(jié)點插入到當前鏈表的表尾，為此必須增加一個尾指針r，使其始終指向當前鏈表的尾結(jié)點。 -
怎么實現(xiàn)頭插法?
??思考二：尾插法的核心是什么?
以有頭結(jié)點為例：
由圖可知，r->next=s; //①r的指針域指向S（讓新結(jié)點插入到鏈表） r=s; //②r指針指向s（保持r指針一直在鏈表尾端，方便插入新的結(jié)點）
那上面兩句可以交換嗎?我們來試一試
還是不能交換呦文章來源：http://www.zghlxwxcb.cn/news/detail-437004.html?? 重點三：以帶頭結(jié)點方式實現(xiàn)尾插法
- 動圖解析
- 圖解
- 代碼
LinkList TailInster(LinkList &L,int n){ int x=1; L= (LinkList)malloc(sizeof(LNode)); LNode *s,*r=L; while(x!=n){ s=(LNode*) malloc(sizeof(LNode)); s->data=x; r->next=s; r=s; x++; } r->next=NULL; return L; }
?? 重點四：以不帶頭結(jié)點方式實現(xiàn)尾插法
- 動圖解析
（略，參考上） - 圖解
- 代碼
LinkList Tailinster(LinkList &L,int n){ int x=1; L= (LinkList)malloc(sizeof(LNode)); L->data=x++; LNode *s,*r=L; while(x!=n){ s=(LNode*) malloc(sizeof(LNode)); s->data=x; r->next=s; r=s; x++; } r->next=NULL; return L; }
- 動圖解析
三、完整代碼
#include "stdio.h"
#include "stdlib.h"
typedef int ElemType;
typedef struct LNode{
ElemType data; //數(shù)據(jù)域
struct LNode *next; //指針域
}LNode,*LinkList;
/*
* 頭插法 有頭結(jié)點
*/
LinkList HeadInster(LinkList &L,int n){
LNode *s;
int x=1;
L= (LinkList)malloc(sizeof(LNode)); //創(chuàng)建頭結(jié)點
L->next=NULL; //初始為空鏈表
while(x!=n){
s=(LNode*) malloc(sizeof(LNode)); //創(chuàng)建新結(jié)點
s->data=x;
s->next=L->next;
L->next=s;
x++;
}
return L;
}
/*
* 頭插法 無頭結(jié)點
*/
LinkList Headinster(LinkList &L,int n){
LNode *s;
int x=1;
L= (LinkList)malloc(sizeof(LNode));
L->data=x++;
L->next=NULL;
while(x!=n){
s=(LNode*) malloc(sizeof(LNode));
s->data=x;
s->next=L;
L=s;
x++;
}
return L;
}
/*
* 尾插法、有結(jié)點
*/
LinkList TailInster(LinkList &L,int n){
int x=1;
L= (LinkList)malloc(sizeof(LNode));
LNode *s,*r=L;
while(x!=n){
s=(LNode*) malloc(sizeof(LNode));
s->data=x;
r->next=s;
r=s;
x++;
}
r->next=NULL;
return L;
}
/*
* 尾插法、無結(jié)點
*/
LinkList Tailinster(LinkList &L,int n){
int x=1;
L= (LinkList)malloc(sizeof(LNode));
L->data=x++;
LNode *s,*r=L;
while(x!=n){
s=(LNode*) malloc(sizeof(LNode));
s->data=x;
r->next=s;
r=s;
x++;
}
r->next=NULL;
return L;
}
/*
* 便利鏈表、頭結(jié)點
*/
void PrintList(LinkList L){
LNode *s;
s=L->next;
while (s!=NULL) {
printf("%d\t",s->data);
s=s->next;
}
}
/*
* 便利鏈表
*/
void Print(LinkList L){
LNode *s;
s=L;
while (s!=NULL) {
printf("%d\t",s->data);
s=s->next;
}
}
int main(){
LinkList L,S,P,Q;
printf("有頭結(jié)點的頭插法：");
HeadInster(L,10);
PrintList(L);
printf("\n無頭結(jié)點的頭插法：");
Headinster(P,10);
Print(P);
printf("\n有頭結(jié)點的尾插法：");
Tailinster(S,10);
Print(S);
printf("\n無頭結(jié)點的尾插法：");
Tailinster(Q,10);
Print(Q);
}
四、運行結(jié)果圖
文章來源地址http://www.zghlxwxcb.cn/news/detail-437004.html
到了這里，關于【數(shù)據(jù)結(jié)構(gòu)】：單鏈表之頭插法和尾插法（動圖+圖解）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
