【数据结构】【线性表】单链表1—概念即创建(附C语言源码)

单链表的定义，

链表用链式存储的方式实现线性表，链表中每个结点元素中需要指向下一个结点的指针（有时候也要指向上一个结点的指针），链表中的每个结点指针只指向下一结点的被叫为单链表。

单链表的创建和初始化

先定义链表的结点元素

//定义单链表结点
struct LNode{//定义单链表结点类型
EleType deta;//每一个结点存放一个数据元素
struct LNode *next;//指针指向下一个结点
};

由于单链表的物理存储结构是链式的，而不是顺序表的连续空间，因此在表示链表时，只说明头指针，指向链表的第一个结点，结点元素的next指针指向下一个结点构成链表。

对于单链表数据结构，在创建的时候需要强调结点或者强调链表，因此需要两个同类型的不同名字的变量，我们采用typedef进行数据类型重命名。

typedef struct LNode{//定义单链表结点类型
EleType deta;//每一个结点存放一个数据元素
struct LNode *next;//指针指向下一个结点
}LNode,*LinkList;//重命名结构体为LNode,*LinkList

/*LNode = *LinkList = struct LNode，这三个都是一样的，前两个是最后一个的两个别名*/
/*表示一个链表 LNode *L 强调结点  /  LinkList L 强调链表*/

/*功能：定义一个单链表
  输入：
L->单链表结构体
i->链表长度
  输出：
单链表最后一个结点
  说明：
*/
LNode *GetElem(LinkList L,int i){
int j=1;//第一个结点开始
LNode *p = L->next;//初始化p为第一个结点
if(i==0)//链表长度为0
return L;//返回空链表
if(i<0)//链表长度小于0
retuen NULL;//返回空指针
while(p!=NULL && j<i){//遍历构建链表
p=p->next;
j++;
}
return p;//构建完成，返回最后一个结点
}

上述方法定义了**链表关系，但未对链表元素进行定义，也未申请内存空间，最重要的是它返回的是单链表的最后一个结点，单链表又是不可逆的，也就是这返回值没有太大价值。

因此我们需要的是创建一个能够被我们检索使用的单链表，我们需要的是链表的开头而不是结尾。链表的开头分为有头结点和无头结点两种，就链表定义而言，不需要头结点也是一个完整的链表，但在实际的运用中发现，没有头结点的单链表在继续数据运算时代码相对复杂(在链表的插入删除中可以体现，后文会讲），因此我们可以采用有头结点的单链表，使得代码简便的同时更加统一。

/*功能：初始化无头结点的链表
  输入：
L->单链表结构体
  输出：
初始化状况 true：初始化成功 false：初始化失败
  说明：
*/
bool InitList(LinkList &L){
L=NULL;
return true;
}
/*功能：初始化有头结点的链表
  输入：
L->单链表结构体
  输出：
初始化状况 true：初始化成功 false：初始化失败
  说明：
*/
bool InitList(LinkList &L){
L=(LNode *) malloc(sizeof(LNode));//申请头结点内存
if(L==NULL)//判断内存申请情况
return flase;//内存不足，分配失败

L->next=NULL;//分配成功，初始化头节点next指针
return true;//头结点初始化成功
}

由于有头结点的单链表具有天然的代码优势，因此在后续的内容中，如没有特殊说明，则代表该单链表为有头结点的单链表。上面我们在创建单链表时存在链表各结点数据未赋值、链表长度固定，链表返回值为链表结尾结点等问题，为此我们可以采用头插入的方法创建链表，即创建一个头结点，然后不断在头结点后插入新结点进行创建。

/*功能：定义一个单链表
  输入：
L->单链表结构体
  输出：
单链表
  说明：实际返回的是单链表的头结点
*/
LinkList List_HeadInsert(LinkList &L){
LNode *s ; 
int x;
L=(LinkList)malloc(sizeof(LNode));//申请头结点空间

L->next=NULL;//初始化该结点指向NULL
scanf("%d",&x);//输入ｘ
while(x!9999){//ｘ不等于9999则开始创建单链表
s=(LNode*)malloc(sizeof(LNode));//申请一个结点空间
s->data==x;//将输入的x作为该结点数据
s->next=L->next;//将原有结点的next给新结点
L->next=s;//原有结点的next指向新结点，完成结点的连接
scanf("%d",&x);//继续输入
}
return L;//创建完成，返回单链表
}

上述创建方法涉及单链表的插入可能有点难懂，下一篇我们将讲述单链表的插入。

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

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