【数据结构】【线性表】单链表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)						//链表长度为0return L;					//返回空链表if(i<0)							//链表长度小于0retuen 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;								//初始化该结点指向NULLscanf("%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;									//创建完成，返回单链表
}

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