学习笔记:2.单链表的实现和代码

自己学习数据结构的笔记，看的是王道的视频，写了源代码在最下面，有详细的注释，可以直接跑。（要保存成c++文件)希望对大家学习数据结构有所帮助。

1.定义单链表

typedef struct LNode{
	int data;  				//数据域
	struct  LNode *next;	//指针域 
}LNode,*LinkList;
//LNode      强调节点
/
		
		s->data = x;		 
		r->next = s;		//令s的指针指向L的下一个节点 
		r = s;				//令表尾指针指向s
		scanf("%d",&x);
	}
	r->next = NULL;
	return L; 
} 

2.头插法建立单链表 [平均时间复杂度O(n)]

//头插法创建单链表
LinkList HeadInsert(LinkList &L){
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	LNode *s;

	int x;
	scanf("%d",&x);			//输入插入单链表的元素
	while(x != 9999){		//当输入9999时,结束单链表创建 
		LNode *s = (LNode*)malloc(sizeof(LNode));

		s->data = x;		
		s->next = L->next;	//当不带头结点时,操作为 s->next = L; 
		L->next = s;		//当不带头结点时,操作为 L = s; 
		scanf("%d",&x);
	}
	return L; 
}

1.不能随机存取。

2.存储密度低,节点处除了存放数据外还需要额外的内存空间存储指针。

3.优点是方便扩展容量,插入删除操作简单。

4.引入头结点的好处:对单链表第一个节点进行操作无需特殊处理。

带头结点的实现方式

#include 
#include 
#include 


//单链表的定义 
typedef struct  LNode{
	int data;  //表示数据域
	struct  LNode *next;//指向下一个节点的指针
}LNode,*LinkList;
//LNode     强调节点
/
		
		s->data = x;		 
		r->next = s;		//令s的指针指向L的下一个节点 
		r = s;				//令表尾指针指向s
		scanf("%d",&x);
	}
	r->next = NULL;
	return L; 
}  


//求单链表表长
int LinkListlength(LinkList L){
	int len = 0;
	LNode *p = L;
	while(p->next != NULL){	//当不带头结点时,判断条件为 p != NULL
		len++;
		p = p->next; 
	}
	printf("单链表表长为:%dn",len); 
	return len; 
} 


//单链表的遍历
void LinkListPrint(LinkList L){
	LNode *s = L;
	printf("==================n"); 
	printf("单链表的遍历结果为:"); 
	while(s->next != NULL){
		s = s->next;
		printf("%d ",s->data);
	}
	printf("n");
	LinkListlength(L);
	printf("==================n");  
}