起因
记录一下自己线性表的学习过程,当年大学有老师讲的时候听的一塌糊涂,现在研究生二年级了,自己复习一下,总结一些对本科生可用的经验吧
线性表的单链表存储结构
//线性表的单链表存储结构(教科书恶心版)
typedef struct lnode
{
int data;
struct lnode *next;
}lnode, *linklist;
我没资格抨击教科书这种书写方式,但是我真的觉得很恶心,直到我现在才明白这种写法的真正意图,写一个自己改版的,认为更方便新手理解
//自己改写的单链表存储结构
struct lnode
{
int data;
struct lnode *next;
};
typedef struct lnode lnode;
typedef struct lnode *linklist;
单链表的存储方法
链表的结点结构如图:
链表的结点(Node)包括两个域:
- 数据域 -- 存储数据元素信息的域
- 指针域 -- 存储直接后继或者直接前继的域
n个结点以链接方式存储的线性表称为链表(linked list)
链表的具体存储表示为:
- 用一组任意的存储单元存放线性表的节点(这组存储单元既可以是连续的,也可以是不连续的)
- 链表中节点的逻辑顺序和物理顺序不一定一致。为了能够正确的表示节点间的逻辑顺序,因此增加了后继指针(指向后继节点的地址)
指针变量和结点变量
指针变量p和结点变量*p的关系
|
指针变量P |
结点变量*P |
定义 |
在变量说明部分显示定义 |
在指针变量P使用时,通过标准的mallc生成 |
取值 |
结点的地址 |
结点各个域的内容 |
操作方式 |
指针变量名访问 |
通过*取值运算符访问 |
生成结点变量的标准函数
p = (struct node *)malloc(sizeof(struct node *));
释放结点变量空间的标准函数
- (*p).data和(*p).next
- p->data和p->next
指针变量p和结点变量*p的关系
- 指针变量p的值是结点的地址
- 结点变量*p的值是结点的内容
- *((*p).next)是*p后继结点的内容
头指针head和终端节点指针域的表示
单链表中每个节点的存储地址是存放在其前趋节点next域中,而开始节点无前趋,故设头指针head指向开始节点
终端节点无后继,故终端节点的next域为空
注意:
链表可由头指针唯一确定,单链表可由头指针的名字来命名
创建单链表
头插法创建单链表代码:
/**
* Description:头插法创建单链表
*/
linklist createlisthead()
{
int data;
linklist head, s;
head = NULL;
while(scanf("%d",&data) != EOF)
{
s = (linklist)malloc(sizeof(lnode));
s -> data = data;
s -> next = head;
head = s;
}
return head;
}
注意:该方法生成的链表顺序是与输入顺序相反的
头节点的作用:
头节点就是在链表开始之前附加一个节点,它具有两个优点:
- 由于开始节点的位置被存放在头节点的指针域中,所以在链表的第一个位置操作跟其它位置操作无差别
- 无论链表是否为空,其头指针都是指向头节点的非空指针
带头结点的尾插法建立单链表:
/**
* Description:尾插法创建单链表
*/
linklist createlisttail()
{
int data;
linklist head, s, t;
head = (linklist)malloc(sizeof(lnode));
t = head; //尾指针的初值指向头结点
while(scanf("%d",&n) != EOF)
{
s = (linklist)malloc(sizeof(lnode));
s -> data = data;
t -> next = s;
t = s;
}
t -> next = NULL;
return head;
}
单链表的查找运算
(1)单链表不是随机存储结构
(2)查找代码(带头节点):
/**
* Description:单链表中查找节点
*/
linklist getnode(linklist head, int i)
{
int j;
linklist p;
for(p = head, j = 0; p -> next && j < i; ;)
{
p = p -> next;
j ++;
}
if(i == j)
return p;
else
return NULL;
}
单链表的插入操作
插入代码:
/**
* Description:单链表的插入运算,在位置i之前插入节点
*/
void insertlist(linklist head, int i, int data)
{
linklist p, s;
p = getnode(head, i - 1);
if(!p)
exit("Error Position!\n");
s = (linklist)malloc(sizeof(lnode));
s -> data = data;
s -> next = p -> next;
p -> next = s;
}
单链表的删除操作
删除代码:
/**
* Description:删除单链表head的第i个节点
*/
void deletelist(linklist head, int i)
{
linklist p, s;
p = getnode(head, i - 1);
if(!p)
exit("Error Position!\n");
s = p -> next;
p -> next = s -> next;
free(s);
}
时间复杂度
以上操作的时间复杂度均为O(n)
分享到:
相关推荐
数据结构线性表学习资源
数据结构线性表学习笔记总结 线性表-顺序存储-链式存储-循环链表-双链表 知识点总结-代码实现
01.逻辑结构 02.存储结构 03.两种存储结构的特性对比 04.元素移动次数计算和静态链表 05.线性表元素插入和删除
06.建表 07.表逆置 08.取最值 09.划分 10.归并
数据结构 线性表PPT学习教案.pptx
资源还是比较大的,对我们理解线性表很有用的
可巩固线性表学习的基本概念
线性表——链表PPT学习教案.pptx
定义接口,在泛型类中实现了线性表中的各种操作,包含增、删、改、查等。通过本实例,可以学习C#线性表相关内容,也可以学习到接口、类、泛型、索引器等相关知识,为下一步数据结构的学习打下坚实的基础。
在众多数据结构当中,线性表是最简单、也是最...本实验相对比较简单,通过本实验,对顺序表基本操作及 其组合应用的演练,加深对线性表顺序存储方法及其基本操作的理解,为以后进一步学习更 复杂的数据结构打下基础。
线性表CPPT学习教案.pptx
线性表PPT学习教案.PPTx
线性表PPT学习教案.pptx
本文档参考严蔚敏老师的教材。线性表- 链表 代码包括 前插法,尾插法,链表查看,添加,删除,查找元素位置,查找元素等功能。 已通过VS2015 验证。如有问题通过文档内的联系方式与本人联系。
这是数据结构中C语言版部分线性表的学习记录,有关动态在我的博客里有对应。方便大家参考。
DS线性表PPT学习教案.pptx
广义线性表PPT学习教案.pptx
数学线性表PPT学习教案.pptx
数线性表PPT学习教案.pptx
基本线性表PPT学习教案.pptx