一、为什么要采用链式存储(链表)存在的意义 为什么要采用链式存储:
与数组相比,链式存储(即链表)有如下两个优点:
1、数据元素的个数不确定,随时可能增减。采用固定大小的数组浪费空间。
2、方便排序,对于数组来说,每次插入一个元素都可能导致大量数据的移动。
有缺点吗:
与素族相比,链式存储有一个很大的缺点——读取数据!
对于读取其中指定第N个数据,链表必须从头结点用p = p->next(头结点不存储数据);一直遍历N次或N-1次(头结点存储数据)。所以在需要频繁索取某些指定数据的情况下,牺牲空间为代价换取更优的性能就需要采取数组这种数据结构了。
二、链表的定义和操作
链表的基础——结构体和指针:
懂得结构体,懂得指针,那么学习链表就很简单了。
/*
* 头结点存储数据,即不带头结点的链表
*/
#include <stdio.h>
#include <stdlib.h>
#define OverFlow -1 //定义OverFlow表示内存溢出
#define OK 0 //定义OK表示成功
#define Error -2 //定义操作失败的返回值
#define OverFlow -1; //定义OverFlow表示内存溢出
#define OK 0; //定义OK表示成功
#define Error -2; //定义操作失败的返回值
/*
* 首先定义一个数据类型int的别名ElemType,
* 增强程序的可移植性,注意typedef和define的区别
*/
typedef int ElemType;
/*
* 紧接着定义链表的节点,其实就是>=1个包含数据
* 的元素(类型任意)和一个本结构体类型的Next指
* 针(其值指向链表的下一个节点的地址)
*/
typedef struct node
{
ElemType data;
struct node *next;
} Node, *LinkList;
定义了节点的结构体,我们来进行链表操作的函数编写:
首先来看头结点不存储数据的情况:
我们需要:
1.构造一个空表
构造空表分两种情况,构造头结点不存储数据的空表和头结点存储数据的空表。
/*
* 1.构建头结点不存储数据的空表(相对简单)
* 注意函数参数传递的原理
*/
void Init_LinkList(LinkList *Head_pointer)
{
*Head_pointer = NULL;
}
2.插入一个元素(头插)
插入一个元素分三步:第一步,定义节点p并初始化,包括分配空间和赋值;第二步,找准插入位置,一般找到插入点的前一个元素;第三步,p->next赋值(这一定首先进行,进行此步骤不影响链表中任何信息)等一系列链表操作,这是核心部分。
/*
* 2.插入一个元素(头插)
* 这时候不需要传入位置的数据,只需要传入头指针和数据
*/
int Insert_First(LinkList *Head_pointer, ElemType x)
{
Node *p; //这里考虑为什么不用LinkList
p = (Node *) malloc(sizeof Node);
if (p == NULL)
return OverFlow;
p->data = x;
p->next = *Head_pointer;
*Head_pointer = p;
return OK;
}
3.查找指定的元素(与数组查找元素效率差不多)
/*
* 3.查找指定元素,注意这里用到了LinkList定义数据
* 因为不是要定义一个节点,只是定义一个指针
*/
LinkList Location_LinkList(LinkList Head, ElemType x)
{
LinkList p;
p = Head;
while(p != NULL)
{
if (p->data == x)
break;
p = p->next;
}
return p;
}
4.删除指定的元素
这里要注意头结点就是要删除的元素时,操作代码不一样。建立链表时头结点不存入数据的原因就在这里。
/*
* 4.删除指定的元素
* 有可能改变头结点的值,所以要传入指针
* 对头结点就是要删除的元素进行单独处理
*/
int Delete_LinkList(LinkList *Head_pointer, ElemType x)
{
Node *p, *q;
p = *Head_pointer;
if (p->data == x)//考虑头结点就是要删除的元素
{
*Head_pointer = (*Head_pointer)->next;
free(p);
return OK;
}
else
{
q = p; p = p->next; //q指向前一个节点,p指向下一个节点
while(p != NULL)
{
if (p->data == x)
{
q->next = p->next;
free(p);
return OK;
}
q = p; p = p->next;
}
}
return Error;
}
5.遍历链表
其实就是逐个操作链表,操作可以包括打印每个元素,更改每个元素。
注意如果在linux下面打印中文出现乱码的情况,请更改编码方式。可参考我在163博客中的一篇文章:http://canlynet.blog.163.com/blog/static/25501365200911300521926/
/*
* 5.遍历线性表,打印每个数据
* 只需要传入Head的值即可
* 头结点为空需要打印空表,在linux的超级终端下注意中文编码问题
*/
void Show_LinkList(LinkList Head)
{
LinkList p = Head;
int i = 0;
printf("----链表打印----\n");
if (p == NULL) //处理头结点为空的情况
printf("空表\n");
while (p != NULL)
{
printf("[%d]:%d\t", i++, p->data);
p = p->next;
}
}
6.清空链表
清空链表需要传入头结点指针。
/*
* 6.清空链表
* 清除到头结点为空的状态,也就是一个空表的状态
*/
void SetNull_LinkList(LinkList *Head_pointer)
{
LinkList p, q;
p = *Head_pointer;
while (p != NULL)
{
q = p;
p = p->next;
free(q);
}
}
7.计算链表的长度
注意算法:从Head计算,指针不为空的总数
/*
* 7.计算链表的长度
* 计算方法:从Head开始,计算指针不为空的个数
*/
int Length_LinkList(LinkList Head)
{
LinkList p = Head;
int sum = 0;
while(p != NULL)
{
sum++;
p = p->next;
}
return sum;
}
8.调用单链表操作的主函数
看了下面这个主函数,我们基本上能够感受到c语言编写软件的一种方式。
/*
*8.调用单链表操作的主函数
*/
int main(void)
{
LinkList Head;
int i;
Node *loca;
ElemType x;
Init_LinkList(&Head);
do
{
printf("\n");
printf("1---插入一个元素(Insert)\n");
printf("2---查询一个元素(Locate)\n");
printf("3---删除一个元素(Delete)\n");
printf("4---显示所有元素(Show)\n");
printf("5---计算表的长度(Length)\n");
printf("6---退出\n");
scanf("%d", &i);
switch (i)
{
case 1: printf("请输入要插入的分数:\n");
scanf("%d", &x);
if (Insert_First(&Head, x) != OK)
printf("插入失败\n");
break;
case 2: printf("请输入要查询的分数\n");
loca = Location_LinkList(Head, x);
if (loca != NULL)
printf("查询成功\n");
else
printf("查询失败\n");
break;
case 3: printf("请输入要删除的分数\n");
scanf("%d", &x);
if (Delete_LinkList(&Head, x) != OK)
printf("删除失败\n");
else
printf("删除成功\n");
break;
case 4: Show_LinkList(Head);
break;
case 5: printf("表的长度是:%d", Length_LinkList(Head));
break;
case 6: break;
default: printf("错误选择!请重选");
break;
}
} while (i != 6);
SetNull_LinkList(&Head);
printf("链表已清空,程序退出...\n");
return 0;
}
附件包括了头结点存储数据(即不带头结点的单向链表的操作源码)和头结点不存储数据(即带头结点的单向循环链表)的链表操作的源码。
【完】
更多关于链表操作的算法请继续关注后面的博客文章...
本文所涉及的代码来自《实用数据结构》谭浩强主编,林小茶编著,清华大学出版社出版,作者已对其中bug进行了修正,如果还有问题,恳请赐教,在此谢过!
分享到:
相关推荐
线性表——链表PPT学习教案.pptx
第二节 线性表-链式存储-链表回顾数组时间复杂度:访问:由于可以随机访问,O(1)插入:O(n)删除:O(n)静态操作:常数时间内完成动态操作:线性时间内完成此
链表是我们经常用到的一种数据结构,我们在学习数据结构的时候,第一个接触的一般就是线性表了,线性表...把线性表的链式存储结构,API实现及测试函数上传,配套我的文章《【数据结构】线性表的链式存储API及实现》。
线性表的顺序存储结构及实现 线性表的链表存储结构及实现
线性表的链式存储 单项链表
使用C++类模板实现了线性表的链式存储结构(链表),类中包含了线性表的常用方法:向线性表中插入一个元素、删除一个元素、清空线性表、获取一个元素、获取线性表长度等。大致实现了STL中的链表的基本功能,通过对比...
数据结构_线性表的链式存储 实验目的 1. 掌握线性表的链式存储结构。 2. 能熟练地利用链式存储结构实现线性表的基本操作。 3. 能熟练地掌握链式存储结构中算法的实现。 实验内容 1. 分别用头插法和尾插法建立带头...
数据结构实验报告2线性表的链式存储结构.pdf
对于新手具有参考作用,包括:1.插入一个字符到一个结点中;2.删除一个结点中的字符;3.插入一个结点到链表中;4.删除链表中的一个结点 等
线性表的链式存储结构.doc 线性表的链式存储结构.doc 线性表的链式存储结构.doc
线性表的链式存储,单链表,插入,删除等的C语言实现。
2、已知由单链表表示的线性表中,含有三类字符的数据元素(如:字母、数字和其它字符),设计算法构造三个以循环链表示的线性表,使每一个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的空间。...
这是一个线性表的链式存储程序,DOS界面
数据结构 C语言版 线性表的链式存储 数据结构 C语言版 线性表的链式存储
数据结构 线性表 实验代码 C语言 链表 hust 赵明 一步一步来,不要浮躁啊
2第二章 线性表(顺序表 链表).pdf
这套资料是实现了WindowC++中的数据结构的线性表的链式存储
实验二 线性表的链式存储结构 题目:设计并实现以下算法:给出用单链表存储多项式的结构,利用后接法生成多项式的单链表结构,实现两个多项式相加的运算,并就地逆置相加后的多项式链式。1. 用户可以根据自己的需求...
学院: 专业: 班级: "姓名 " "学号 " "实验组" " "实验时间 "2011-11-11 "指导教师" "成绩 " " "实验项目名称"线性表的链式存储结构 " "实"了解和掌握线性表的逻辑结构和链式存储结构,掌握单链表的基本算法" "验...