单链表
2026/4/9大约 4 分钟
LNode *(强调返回的是一个结点)=LinkList(强调这是一个单链表)
单链表的定义
typedef struct LNode{ //定义单链表结点类型
ElemType data; //每个结点存放一个数据元素
struct LNode *next; //指针指向下一个结点
}LNode,*LinkList;
//初始化一个空的单链表
//不带头结点的单链表
bool InitList(LinkList &L){
L=NULL; //空表，暂时还没有任何结点
return true;
}
/*
//带头结点的单链表
bool InitList(LinkList &L){
L=(LNode *)malloc(sizeof(LNode)); //分配一个头结点
if(L=NULL) //内存不足，分配失败
return false;
L->next=NULL; //头结点之后暂时还没有结点
return true;
}
*/单链表的插入
//在第一个i位置插入元素e（带头结点）
bool ListInsert(LinkList &L,int i,ElemType e){
if(i<1)
return false;
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p=L; //L指向头结点，头节点是第0个节点（不存数据）
while(p!=NULL && j<i-1){//循环找到i-1个结点
p=p->next;
j++;
}
if(p==NULL) //i值不合法
return false;
LNode *s=(LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s; //将结点s连到p后
return true;
}
/*
//在第一个i位置插入元素e（不带头结点）
bool ListInsert(LinkList &L,int i,ElemType e){
if(i<1)
return false;
if(i==1){ //插入第1个结点的操作与其他结点操作不同
LNode *s=(LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = L;
L=s; //头指针指向新结点
return true;
}
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p=L; //L指向头结点，头节点是第0个节点（不存数据）
while(p!=NULL && j<i-1){//循环找到i-1个结点
p=p->next;
j++;
}
if(p==NULL) //i值不合法
return false;
LNode *s=(LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s; //将结点s连到p后
return true;
}
*/
/*
//后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode *p,ElemType e){
if(p==NULL) //i值不合法
return false;
LNode *s=(LNode *)malloc(sizeof(LNode));
if(s==NULL)
return false;
s->data = e; //用结点s保存数据元素e
s->next = p->next;
p->next = s; //将结点s连到p后
return true;
}
*/
/*
//前插操作：在p结点之后插入元素e
bool InsertPriorNode(LNode *p,ElemType e){
if(p==NULL) //i值不合法
return false;
LNode *s=(LNode *)malloc(sizeof(LNode));
if(s==NULL)
return false;
s->next = p->next;
p->next = s; //将断点s连到p后
s->data = p->data; //将p中元素复制到s中
p->data = e; //p中元素覆盖维e
return true;
}
*/单链表的删除
//在第一个i位置删除元素e（带头结点）
bool ListDelete(LinkList &L,int i,ElemType &e){
if(i<1)
return false;
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p=L; //L指向头结点，头节点是第0个节点（不存数据）
while(p!=NULL && j<i-1){//循环找到i-1个结点
p=p->next;
j++;
}
if(p==NULL) //i值不合法
return false;
if(p->next==NULL) //第i-1个结点之后无其他结点
return false;
LNode *q=p->next //令q指向被删除结点
e=q->data; //用e返回元素的值
p->next = q->next; //将*q结点从链表中断开
free(q); //释放结点的存储空间
return true; //删除成功
}
/*
//删除指定结点p
bool DeleteNode(LNode *p){
if(p==NULL) //i值不合法
return false;
LNode *q=p->next //令q指向*p的后继结点
p->data=p->next->data; //和后继结点交换数据域
p->next = q->next; //将*q结点从链表中断开
free(q); //释放结点的存储空间
return true; //删除成功
}
*/单链表按位查找
//按位查找
LNode * GetElem(LinkList L,int i){
if(i<0)
return NULL;
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p=L; //L指向头结点，头节点是第0个节点（不存数据）
while(p!=NULL && j<i){//循环找到i个结点
p=p->next;
j++;
}
return p;
}
//按值查找
LNode * LocateElem(LinkList L,ElemType e){
LNode *p=L->next;
while(p!=NULL && p->data!=e)
p=p->next;
return p;
}单链表长度
int Length(LinkList L){
int len =0;
LNode *p=L;
while(p->next !=NULL){
p=p->next;
len++;
}
return len;
}尾插法建立单链表
LinkList List_Taillnsert(LinkList &L){ //正向建立单链表
int x; //设ElemType为整形
L=(LinkList)malloc(sizeof(LNode)); //建立头结点
LNode *s,*r=L; //r为表尾指针
scanf("%d",&x); //输入结点的值
while(x!=9999){ //输入9999表示结束
s=(LNode)malloc(sizeof(LNode));
s->data=x;
r->next=s;
r=s; //r指向新的表尾结点
scanf("%d",&x);
}
r->next=NULL; //尾结点指针置空
return L;
}头插法建立单链表
LinkList List_Taillnsert(LinkList &L){ //逆向建立单链表
LNode *s;
int x; //设ElemType为整形
L=(LinkList)malloc(sizeof(LNode)); //建立头结点
L->next=NULL; //初始为空链表
scanf("%d",&x); //输入结点的值
while(x!=9999){ //输入9999表示结束
s=(LNode)malloc(sizeof(LNode)); //创建新结点
s->data=x;
s->next=L->next;
L->next=s; //将新结点插入表中，L为头指针
scanf("%d",&x);
}
return L;
}