个人主页:
仍有未知等待探索_小项目,数据结构,洛谷刷题-CSDN博客
专题分栏---数据结构:
数据结构_仍有未知等待探索的博客-CSDN博客
目录
一、引例
1.顺序存储结构
2.链式存储结构
二、链表的创建和初始化
1.链表创建的分析
1)头插法
过程:
代码的实现:
2)尾插法
过程+代码实现:
三、未完待续 。。。
今天,我们来讲解顺序表的链式存储结构。在讲解顺序表的链式存储结构的之前,我们要先讲讲问什么要引入链式存储结构。
一、引例
顺序存储的优点 链式存储的优点 1.容易读取数据 1.节省空间 2.创建和初始化简单 2.插入和删除元素简单 1.顺序结构在物理层面上相邻,在逻辑层面上也是相邻的。
2.链式结构在物理层面上不相邻,在逻辑层面上是相邻的。
通过上述对不同的存储结构的优点的描述,我们也明白了在什么情况下用什么存储结构来实现我们的功能。
1.顺序存储结构
顺序存储结构就会像这样一样,将数据存在数组中。 会在内存中开辟一块连续的空间,然后将数组存在上面的数组中,然后再用一个变量来存储最后一个元素的下标。
2.链式存储结构
链式存储结构像上述一样,会开辟一个个的节点,每个节点有数据域和指针域,数据域会存放数据而指针域则是存放下一个节点的地址,来方便找下一个节点。链式存储结构就是像图片画的一样,再内存的随机地方开辟一个空间来作为节点,这样避免的了内存空间的浪费,用多少就开辟多少空间,灵活度高。
二、链表的创建和初始化
1.链表创建的分析
链表是什么连上的呢?
一开始,先创建一个节点,让一个head指针指向这个节点,然后再创建一个节点,就会产生一个分歧,那是将新创建的节点再逻辑层面上放在head所指向的左边还是右边呢?那就会分成两个创建链表的方法---头插法,尾插法。
1)头插法
头插法就是在逻辑层面上最先开辟的节点放在最右边。
过程:
先创建一个节点,然后用head指针(也就是头指针)指向这个节点。然后再开辟一个节点,让这个节点的指针域存放head指针指向的节点的地址,然后让head指向这个新开辟的节点。
注:红色的是第一步,蓝色的是第二步。
代码的实现:
在代码实现的前面,你要知道节点的类型是什么,节点里面包含数据域和指针,这是两个类型的数据,怎么将这两个数据合在一块呢?
typedef struct Node { int data; struct Node* next; }Node;
像这样就可以将两个数据类型合成为一个数据类型。 这里的typedef/用来将这个节点类型struct Node重命名为Node。
然后准备工作就做完了,接下来就开始链表的创建。
Node* ListCreate1(Node* L) { int data; scanf("%d", &data); Node* head=NULL, * p; //data为0结束 while (data) { //开辟空间 p = (Node*)malloc(sizeof(Node)); //赋值 p->data = data; //将head里的地址赋值到开辟的节点的指针域 p->next = head; //然后将head(头指针)指向第一个节点 head = p; scanf("%d", &data); } return head; }
输入数据:
链表:
从上面也能清楚的看出来,数据正着输入,逆序存储,这也是头插法的特点。
2)尾插法
过程+代码实现:
这个尾插,需要用到三个指针head,q,p来进行循环完成操作。同样,先创建一个节点,然后让head指针指向这个节点,让q也指向这个节点。
尾插法的创建需要进行讨论。q就相当于一个尾指针。
当head==NULL的时候,你需要让head=p;q=p;
if (head == NULL) { head = p; q=p; }
当head!=NULL的时候让q->next=p;q =p;
if(head!=NULL) { q->next = p; q=p; }
最后进行合并一下就行了。
Node* ListCreate2(Node* L) { int data; scanf("%d", &data); Node* head=NULL, * p, * q=NULL; while (data) { //data输入0的时候结束 p = (Node*)malloc(sizeof(Node)); p->data = data; if (head == NULL) { head = p; } else { q->next = p; } q = p; q->next=NULL; scanf("%d", &data); } return head; }
输入数据:
链表:
从上面能清晰的看见链表是正着输入,正着存储的。文章来源:https://www.toymoban.com/news/detail-726977.html
三、总代码(声明+定义)
#include<stdio.h> #include<stdlib.h> //创建一个节点类型,typedef用来将这个节点类型struct Node重命名为Node typedef struct Node { int data; struct Node* next; }Node; Node* ListCreate1(Node* L); Node* ListCreate2(Node* L); Node* L1,L2; int main() { L1=ListCreate1(L); L2=ListCreate2(L); return 0; } Node* ListCreate1(Node* L) { int data; scanf("%d", &data); Node* head=NULL, * p; //data为0结束 while (data) { p = (Node*)malloc(sizeof(Node)); p->data = data; p->next = head; head = p; scanf("%d", &data); } return head; } Node* ListCreate2(Node* L) { int data; scanf("%d", &data); Node* head=NULL, * p, * q=NULL; while (data) { //data输入0的时候结束 p = (Node*)malloc(sizeof(Node)); p->data = data; if (head == NULL) { head = p; } else { q->next = p; } q = p; q->next = NULL; scanf("%d", &data); } return head; }
四、未完待续 。。。
谢谢大家的支持!!!文章来源地址https://www.toymoban.com/news/detail-726977.html
到了这里,关于C/C++数据结构---顺序表---链式存储结构1(不带头节点)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!