特点：
它是一种动态结构
不需预先分配空间
指针占用额外存储空间
不能随机存取，查找速度慢
带头指针的单链表.png
0、定义
n个结点链结成一个链表，每个结点只包含一个指针域，叫做单链表。
线性链表中第一个结点的存储位置叫做头指针，整个链表的存取必须从头指针开始。 线性链表的最后一个结点指针为“空”（通常用NULL或^表示）。
image.png
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
typedef int ElemType ;//数据类型
typedef struct _LinkList{
ElemType data;//数据域
struct _LinkList *next;//节点
int size;//链表个数
}LinkList;
1、初始化
/**
* 功能：初始化链表
* 参数：链表地址
* 返回值：如果成功，返回链表，失败返回NULL
*/
LinkList* Init_List(){
LinkList *pList;
pList=(LinkList*)malloc(sizeof(LinkList));
if(!pList){
printf("pList动态内存分配失败！\n");
return NULL;
}
pList->next=NULL;
pList->size=0;
printf("初始化成功\n");
return pList;
}
2、获取链表长度
/**
* 功能：获取链表长度
* 参数：链表地址
* 返回值：链表长度
*/
int Length_List(LinkList *head){
LinkList* p=head->next;
int length=0;
while(p){
p=p->next;
length++;
}
printf("链表长度为%d\n",length);
return length;
}
3、插入元素
image.png
/**
* 功能：向链表插入数据元素
* 参数：链表地址 下标 插入的元素
* 返回值：链表长度
*/
bool Insert_List(LinkList *head,int index, ElemType e){
if(head==NULL){
printf("链表未初始化\n");
return false;
}
if(index<1||index>head->size+1){
printf("下标越界\n");
return false;
}
//开始插入
int i;
LinkList* pre=head;
//遍历获取到插入位置的前一个元素
for(i=1;i<index&⪯i++){
pre=pre->next;
}
//校验
if(!pre||i>index){
printf("搜索index位置元素失败\n");//已判断下标越界，不会存在这个问题
return false;
}
LinkList* newNode=(LinkList*)malloc(sizeof(LinkList));
newNode->data=e;
newNode->next=pre->next;
pre->next=newNode;
head->size++;//有效个数加1
return true;
}
5、展示链表数据
/**
* 功能：遍历链表
* 参数：链表地址
*/
void Show_List(LinkList *head){
if(head==NULL){
printf("链表未初始化\n");
return ;
}
if(head->next==NULL){
printf("[]\n");
return;
}
bool flag=true;
printf("[");
LinkList *p=head->next;//第一个节点
while(p){
if(flag){
printf("%d",p->data);
flag=false;
}else{
printf(",%d",p->data);
}
p=p->next;
}
printf("]\n");
}
6、删除元素
image.png
/**
* 功能：删除某个下标的数据元素
* 参数：链表地址 下标 删除的元素
* 返回值：链表长度
*/
bool Delete_List(LinkList *head,int index, ElemType *e){
if(head==NULL){
printf("链表未初始化\n");
return false;
}
if(index<1||index>head->size){
printf("下标越界\n");
return false;
}
//开始删除
int i;
LinkList* pre=head;
//遍历获取到删除的前一个元素
for(i=1;i<index&⪯i++){
pre=pre->next;
}
LinkList* temp=pre->next;
*e=temp->data;
pre->next=temp->next;
free(temp);
head->size--;//有效个数减1
return true;
}
7、判断是否为空表
/**
* 功能：判断链表是否是空表
* 参数：链表头指针
* 返回值：true 是 false 否
*/
bool IsEmpty(LinkList *head){
if(head->next){
return false;
}
return true;
}
8、查找元素
/**
* 功能：查找元素，返回下标
* 参数：链表地址 元素
* 返回值: 下标 -1 为查找不到
*/
int Search_List(LinkList *head,ElemType e){
if(IsEmpty(head)){
return -1;
}
LinkList *p=head->next;//第一个节点
int i=1;
while(p!=NULL){
if(p->data==e){
return i;
}
p=p->next;
i++;
}
return -1;
}
9、获取下标的元素
/**
* 功能：获取某个下标的元素
* 参数：链表地址 下标
* 返回值: true ,false
*/
bool GetElem(LinkList *head,int index,ElemType *e){
if(IsEmpty(head)){
return false;
}
if(index<1||index>head->size){
printf("数组下标越界\n");
return false;
}
LinkList *p=head->next;//第一个节点
//int j=1;
// while(p&&j<index){
// p=p->next;
// j++;
//}
//if(!p||j>index)return false;
//*e=p->data;
for(int i=1;i<=head->size;i++,p=p->next){
if(index==i){
*e=p->data;
return true;
}
}
return false;
}
10、清空链表
/**
* 功能：清空线性表
* 参数：pList：链表地址
*/
bool Clear_List(LinkList *head){
if(head==NULL){
return false;
}
LinkList *temp,*p;
p=head->next;//p指向第一个结点
while(p){//没到表尾
temp=p->next;
free(p);
p=temp;
}
head->next=NULL;
head->size=0;
return true;
}
11、销毁链表
/**
* 功能：清空线性表
* 参数：pList：
*/
bool Destory_List(LinkList *head){
// LinkList *p;
// if(head==NULL)
// return false;
// while(head)
// {
// p=head->next;
// free(head);
// head=p;
// }
Clear_List(head);
free(head);
head=NULL;
return true;
}
main
int main()
{
LinkList* pList=NULL;
pList=Init_List();
Show_List(pList);
Insert_List(pList,1,5);
IsEmpty(pList);
Insert_List(pList,2,6);
printf("搜索6的元素的位置%d\n",Search_List(pList,6));
int index=2,val;
GetElem(pList,index,&val);
printf("获取第%d个的元素是%d\n",index,val);
Clear_List(pList);
Show_List(pList);
if(Delete_List(pList,2,&val)){
printf("删除的元素%d\n",val);
}
Show_List(pList);
printf("搜索5的元素的位置%d\n",Search_List(pList,5));
Length_List(pList);
return 0;
}
