【数据结构】【线性表】单链表4—单链表的建立(附C语言源码)

单链表的建立

单链表的建立其实就是一个结点插入的过程，首先构建链表的结点结构体，并进行初始化，然后再不断插入结点，我们需要解决的问题是：

• 用什么插入方式？
• 在哪个位置插入？
• 程序如何设计：要不要头结点？单链表的长度是多少？链表每个元素内容又是什么？

[!插入方式的选用]
我们首先回答是选用哪种插入方式的问题？如果只看结果的话，构建单链表无所谓其哪种插入方式，只要能实现单链表的建立，都可以选用。但不同的插入方式有不同特点，在实际使用中，面对同一个问题的编程难易程度不一样，时间复杂度或者空间复杂度也会不一样。
回顾我们关于单链表的插入问题，我们一般有按位序插入和指定结点的前插和后插。按位序插入，位序说明本身就链表就已经存在，一般是用在某一个单链表的某个位置进行插入，指定结点插入分前插和后插，由于单链表的不可逆性，前插操作需要找到前驱结点，这个过程需要经过类似于按位序插入的遍历结点的过程，比较复杂，而指定结点的后插只需要指定结点，一切顺理成章，操作简单，时间复杂度低。

[!] 插入位置的选用
在哪个位置插入，无非就是，头部、尾部和中间。每次我们都将结点插入到头部，相当于一个倒序插入，而每次插入到尾部即为顺序插入，如果插入到中间则是无序，无序的线性表一般来说没有意义，因此我们用的最多的是头部插入和尾部插入，同时尾部插入又是最常用的插入方式。

[!如何设计程序]
当我们建立链表的时候，我们需要解决三个问题，第一个是要不要头结点？另一个是链表有多长？最后一个是链表的结点数据是什么？其实在这里就会出现很多结果，例如：有头结点和没有头结点，长度已知和长度未知都是有可能的，每一个结点数据是什么，是传递结点还是传递结点数据，理论上各有写法。
但在实际的应用中，我们希望我们的程序，结构简单，逻辑清晰，还有就是可拓展性强。考虑到这些，我们一般设计成一个动态长度，且传递结点元素的有头结点的单链表。
有头结点的在程序设计上相对简单，动态长度在一定程度上能够实现静态长度的功能，传递结点数据，比传递结点更具有实际应用意义也兼容传递结点的功能（此段有疑惑可以在评论区讨论或者私信我，在此不作大篇幅的论述）

结合上述回答，在此，我们设计尾插和头插两个单链表建立的程序

//首先，无论用什么方法，我们先建立单链表的结点结构体
typedef struct LNode{//定义单链表结点类型
EleType deta;//每一个结点存放一个数据元素
struct LNode *next;//指针指向下一个结点
}LNode,*LinkList;

LinkList List_TailInsert(LinkList &L){
char flag='s';//链表创建标志，s表示开始/继续创建链表结点

ElemType x;//结点数据，ElemType指代任意数据类型，例如int

L=(LinkList)malloc(sizeof(LNode));//创建头结点
L->next=NULL;
LNode *s,*r=L;//s表示需要创建的当前结点，r指向尾结点

scanf("%s",flag);//接收标志符
while(flag=='s'){//标志符为 s 则创建结点
scanf("%e",x);//输入结点数据 %e指代任意数据类型，例如%d，%s %f
//在r结点后插入元素x
s=(LNode *)malloc(sizeof(LNode))//申请结点空间
s->data=x;//将接收数据赋值给创建的当前结点s
s->next=NULL;//当前结点为末尾结点，后续暂时无结点
r->next=s;//此时s为尾结点

r=s;//更新尾结点，r始终指向尾结点
scanf("%s",flag);//继续输入标志符，判断是否继续创建新结点
}
r->next=NULL;//为结点指针置空
return L;//返回链表头结点
}

如果该链表没有头结点，则需要在创建第一个结点时特殊处理，同时将创建头结点的代码删除，并在第一次接收标志符之前加入下述代码

scanf("%s",flag);
if(flag=='s'){
scanf("%e",x);//输入结点数据 %e指代任意数据类型，例如%d，%s %f
//插入第一个元素x
s=(LNode *)malloc(sizeof(LNode))//申请结点空间
s->data=x;//将接收数据赋值给创建的当前结点s
s->next=NULL;//当前结点为末尾结点，后续暂时无结点
L=s;//链表头指针指向第一个结点
r=s;//更新尾结点
}else{
return NULL;
}

我们观察一下可以得知，没有头结点的第一个结点创建时，由于没有前驱结点，r->next=s中的r->next不存在，因此需要将该语句改为L=s，表示链表头指针指向当前结点s(第一个结点);因此s为尾结点其实还有一个更简单的方式，只需要引入一个变量length，表示当前链表长度，在length=1时作特殊处理。程序可以改为如下：

LinkList List_TailInsert(LinkList &L,int &length){
char flag='s';//链表创建标志，s表示开始/继续创建链表结点
ElemType x;//结点数据，ElemType指代任意数据类型，例如int
LNode *s,*r=L;//s表示需要创建的当前结点，r指向尾结点
length =0;

scanf("%s",flag);//接收标志符
while(flag=='s'){//标志符为 s 则创建结点
length++;//结点长度+1
scanf("%e",x);//输入结点数据 %e指代任意数据类型，例如%d，%s %f
//在r结点后插入元素x
s=(LNode *)malloc(sizeof(LNode))//申请结点空间
s->data=x;//将接收数据赋值给创建的当前结点s
s->next=NULL;//当前结点为末尾结点，后续暂时无结点
if(length==1)
L=s;链表头指针指向第一个结点
else
r->next=s;//此时s为尾结点

r=s;//更新尾结点，r始终指向尾结点
scanf("%s",flag);//继续输入标志符，判断是否继续创建新结点
}
r->next=NULL;//为结点指针置空
return L;//返回链表头结点
}

该函数不仅减少了代码量，同时可以获取链表长度，但length++和多加了一条判断语句，一定程度上增加了算法的时间复杂度。
接下来简单介绍一下头插法的单链表的创建，头插法就是在头结点后面不断插入新结点，由于新结点每次都插入在头结点之后，所以获得的链表数据的顺序和输入的顺序是相反的。头插法和尾插法相识，但不需要r一直指向表尾了，因为链表开始创建之后头结点一般不会发生改变即表头不变，只需要尾插法的代码作个小小改进即可。

LinkList List_HeadInsert(LinkList &L){
char flag='s';//链表创建标志，s表示开始/继续创建链表结点

ElemType x;//结点数据，ElemType指代任意数据类型，例如int

L=(LinkList)malloc(sizeof(LNode));//创建头结点
L->next=NULL;
LNode *s;//s表示需要创建的当前结点

scanf("%s",flag);//接收标志符
while(flag=='s'){//标志符为 s 则创建结点
scanf("%e",x);//输入结点数据 %e指代任意数据类型，例如%d，%s %f
//在头结点后插入元素x
s=(LNode *)malloc(sizeof(LNode))//申请结点空间
s->data=x;//将接收数据赋值给创建的当前结点s
s->next=L->next;//当前结点的next继承头结点的next，指向原来的第一个结点
L->next=s;//更新头节点的next指针，s为新的第一个结点

scanf("%s",flag);//继续输入标志符，判断是否继续创建新结点
}
return L;//返回链表头结点
}

尾插法的链表各个结点数据与数据输入顺序一致，而头插法刚好相反，如果相同的结点数据，分别用头插法和尾插法创建一个链表，头插法的链表为尾插法链表的逆置。
如何将尾插法的顺序链表逆置呢？只需要将尾插法的按顺序读取并采用头插的方式重新创建链表：

LinkList List_Tail_Head(LinkList &T,LinkList,&H){
char flag='s';//链表创建标志，s表示开始/继续创建链表结点

ElemType x;//结点数据，ElemType指代任意数据类型，例如int
if(T->next==NULL)//判断链表是否为空表
return NULL;//链表为空表返回空链表
H=(LinkList)malloc(sizeof(LNode));//创建头结点
H->next=NULL;
LNode *s,*r=T->next;//s表示需要创建的当前结点,s表示尾插法的当前结点

scanf("%s",flag);//接收标志符
while(r!=NULL){//尾插法当前结点数据存在则取出放头插法
//在头结点后插入尾插法的对应元素
s=(LNode *)malloc(sizeof(LNode))//申请结点空间

s->data=r->data;//将尾插法的当前结点数据给创建的当前结点s

s->next=H->next;//当前结点的next继承头结点的next，指向原来的第一个结点
H->next=s;//更新头节点的next指针，s为新的第一个结点

r=r->next;//尾插法当前结点移动一位
}
return H;//返回链表头结点
}

如果没有头结点，就对第一个结点特殊操作，方法与尾插法一致，这里就不作赘述了，有需要或者有问题评论区留言或者私信我。

原文地址：https://blog.csdn.net/weixin_58498967/article/details/143721016

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！