单链表的基本操做

2021年09月15日 阅读数:1
这篇文章主要向大家介绍单链表的基本操做,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

单链表的基本操做

/#include <stdio.h>
/#include <stdlib.h>
/#include <malloc.h>ide

typedef struct LNode{
int data;
struct LNode *next;
}LNode, *LinkList;指针

//初始化一个链表
bool InitList(LinkList &L){
L = (LNode *)malloc(sizeof(LNode));
if(L==NULL)
return false;
L->next = NULL;
return true;
}blog

//头插法录入数据 须要设置一个指针r始终指向最后一个元素。
LinkList List_TailInsert(LinkList &L){
int x,j;//x用来保存输入数据的数量
L = (LNode *)malloc(sizeof(LNode));
LNode s,r=L;//s为新节点
printf("请输入你要输入数据的数量:\n");
scanf("%d",&x);
printf("请输入一组数据:\n");
for(int i=0; i<x; i++){
s = (LNode *)malloc(sizeof(LNode));
scanf("%d",&j);//定义一个变量j用来保存每次输入的值
s->data = j;
r->next = s;//使头指针和s节点之间创建链接。
r = s;
}it

	r->next = NULL;
	return L;
}

//输出一个链表
PrintList(LinkList &L){
LNode *p=L->next;//P须要指向L的next
// printf("22\n");
// for(p=L->next;p!=NULL;p=p->next)
// printf("%d ",p->data);
while(p!=NULL){ //这个地方是p!=NULL (P的指针域为NULL)
printf("%d\n",p->data);
p=p->next;
}
// printf("22\n");
}io

//按位查找 (第几个位置对应的值)
LinkList FindElemList(LinkList &L,int x){
int j=0;
LNode *p;
p=L;
if(x<0)
return NULL;
while(p!=NULL&&j<x){
p=p->next;
j++;
// printf("%d\n",j);
}
// printf("22\n");
printf("对应的节点为:");
printf("%d\n",p->data);
printf("~~~~~~~~~~~~~~~~~\n");
return p;
}class

//删除指定位序节点 并返回节点对应的值
bool DeleteList(LinkList &L,int i){
if(i<0)//能够加上链表的长度进行限制 稍后实现
return false;
LNode *s;
int y;
s=L;
for(int j=0; j<i; j++){
s=s->next;
}
printf("%d节点对应的数据为:",i);
printf("%d\n",s->data);//此时 s节点即为要删除的节点,
LNode *q;
q = s->next;//用q节点指向s的下一个节点
s->data = q->data;//把q的值赋给s(此时s的值被覆盖,且s保存的是s的下一个节点的值)
s->next = q->next;//此时让s指向q的下一个节点。
free(q); //释放q节点。
}变量

//求链表的长度
int LenthList(LinkList L){
int j=0;
LNode *s;
s=L->next;
while(s!=NULL){
s=s->next;
j++;
}
printf("链表的长度为:%d\n",j);
// return j;List

}遍历

int main(){
LinkList L;
InitList(L);//初始化链表
List_TailInsert(L);// 头插法录入数据。
printf("顺序输出:\n");
PrintList(L);//输出链表
int x,y,i;
printf("请输入你要查询的位序\n");
scanf("%d",&x);
FindElemList(L,x);//查询指定位序对应的元素
printf("请输入你要删除的位序\n");
scanf("%d",&y);
DeleteList(L,y);//删除指定位序的数据 !这种删除元素的方法 有缺陷如果删除的元素为最后一个元素则程序出错。
printf("删除后的链表为:\n");
PrintList(L);//输出链表
LenthList(L);
return 0;
}bug

单链表的基本操做_单链表

<注:单链表的删除操做(俗称变相删除法),用要删除的节点的下一个节点覆盖此节点的值,再改变指针指向下下个节点,并释放中间的节点。这种操做会出现bug状况(当要删除的节点为最后一个节点时,程序出错!!!)能够用头指针遍历找到要删除节点的前一个节点位序,修改其p->next = p->next->p->next>