数据结构—单链表的基本操作
目录
1.单链表的初始化
2.求表长操作
3.按序号查找结点
4.按值查找表结点
5.插入结点操作
6.删除结点操作
7.头插法建立单链表
8.尾插法建立单链表
1.单链表的初始化
带头结点：
bool InitList(LinkList &L) { //带头结点的单链表的初始化
L=(LNode*)malloc(sizeof(LNode)); //创建头结点，仍是指针类型，不是具体数据
L->next=NULL; //头结点之后暂时还没有元素结点
return true;
}
不带头节点：
bool InitList(LinkList &L) { //不带头结点的单链表的初始化
L=NULL;
return true;
}
2.求表长操作
int Length(LinkList L) {
int len=0; //计数变量，初始为0
LNode *p=L;
while(p->next!=NULL){
p=p->next;
len++; //每访问一个结点，计数加1
}
return len;
}
3.按序号查找结点
LNode *GetElem(LinkList L,int i){
LNode *p=L; //指针p指向当前扫描到的结点
int j=0; //记录当前结点的位序，头结点是第0个结点
while(p!=NULL&&j<i){ //循环找到第i个结点
p=p->next;
j++;
}
return p; //返回第i个结点的指针或 NULL
}
4.按值查找表结点
LNode *LocateElem(LinkList L,ElemType e){
LNode *p=L->next;
while(p!=NULL&&p->data!=e) //从第一个结点开始査找数据域为e的结点
p=p->next;
return p; //找到后返回该结点指针，否则返回 NULL
}
5.插入结点操作
bool ListInsert(LinkList &L,int i, ElemType e){
LNode *p=L; //指针p指向当前扫描到的结点
int j=0; //记录当前结点的位序，头结点是第0个结点
while(p!=NULL&&j<i-1)( //循环找到第i-1个结点
p=p->next;
j++;
}
if(p==NULL)
return false;
LNode *s=(LNode*)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
return true;
}
6.删除结点操作
bool ListDelete(LinkList &L,int i,ElemType &e){
LNode *p=L; //指针p指向当前扫描到的结点
int j=0; //记录当前结点的位序，头结点是第0个结点
while(p!=NULL&&j<i-1){ //循环找到第 i-1个结点
p=p->next;
j++;
}
if(p==NULL||p->next==NULL)
return false;
LNode *q=p->next; //令q指向被删除结点
e=q->data; //用e返回元素的值
p->next=q->next; //将*q结点从链中“断开”
free (q); //释放结点的存储空间
return true;
}
7.头插法建立单链表
Linkiist List_HeadInsert(Linklist &L){ //逆向建立单链表
LNode *s; int x; //设元素类型为整型
L=(LNode*)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;
}
8.尾插法建立单链表
LinkList List_TailInsert(LinkList &L){ //正向建立单链表
int x; //设元素类型为整型
L=(LNode*)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;
}
