数据结构__头插法建立单链表、尾插法建立单链表

单链表定义、头插法建表、尾插法建表

一、单链表的定义

        单链表是线性表的链式存储，是指通过一组任意的存储单元来存储线性表中的数据元素。

        单链表结构定义为：

         其中data为数据域，用来存放数据；next为指针域，用来存放后继结点的地址。

单链表优缺点：

        优点：插入、删除方便；无需大量连续的存储单元。

        缺点：附加指针域，增加了对存储空间的消耗；查找速度慢，不支持随机存取。

通常用头指针来标识一个单链表，如单链表L，头指针为NULL时表示一个空表。

此外，为了操作方便，在单链表第一个结点之前附加一个结点，称为头结点。

头结点的数据域可以不设任何信息，也可以记录表长等信息。

头结点的指针域指向线性表的第一个元素结点，如图：

二、头插法建立单链表

        先建立一个空链表，然后创建新结点，将输入的数据存放在新结点的数据域中，再将新结点插入到当前链表的表头，即头结点之后。如图：

#include<iostream> using namespace std;typedef struct LNode{ //定义单链表结点类型int data; //数据域struct LNode *next; //指针域 }LNode, *LinkList;void List_HeadInster(LinkList &L){ //头插法函数LNode *s; int x; //定义一个指向LNode的指针sL=(LinkList)malloc(sizeof(LNode)); //创建头结点L->next=NULL; //初始为空链表while(cin >> x){ //输入新结点的值s=(LNode*)malloc(sizeof(LNode)); //创建新结点s->data=x;s->next=L->next;L->next=s; //将新结点插入表中，L为头指针if(getchar()=='\n'){ //遇到换行跳出break;}}while(L->next) { //输出单链表中结点的值cout<<L->next->data<<" ";L->next=L->next->next;} }int main(){LinkList L;List_HeadInster(L);return 0; }

三、尾插法建立单链表

        尾插法是将新结点插入到当前链表的表尾，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点，如图：

 

#include<iostream> using namespace std;typedef struct LNode{ //定义单链表结点类型int data; //数据域struct LNode *next; //指针域 }LNode, *LinkList;void List_TailInsert(LinkList &L){ //正向建立单链表int x; //设元素类型为整型4L=(LinkList)malloc(sizeof(LNode));LNode *s, *r = L; //r为表尾指针 while(cin >> x){ //输入结点的值 s=(LNode *)malloc(sizeof(LNode));//生成一个LNode型的结点//并把该结点的起始位置赋给指针变量ss->data=x;r->next=s;r=s; //r指向新的表尾结点if (getchar() == '\n')break;}r->next=NULL; //尾结点指针置空while(L->next) { //输出单链表中结点的值cout<<L->next->data<<" ";L->next=L->next->next;} }int main(){LinkList L;List_TailInsert(L);return 0; }

 

两种方法时间复杂度都为O(n)

总结

以上是生活随笔为你收集整理的数据结构__头插法建立单链表、尾插法建立单链表的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。