当前位置：文档之家 › 线性表的链式存储实现

线性表的链式存储实现

  • 格式：ppt
  • 大小：2.67 MB
  • 文档页数：90

下载文档原格式

  / 90

合集下载

编译技术中常用的数据结构

编译技术中常用的数据结构

编译技术中常用的数据结构一、线性表线性表是编译技术中常用的数据结构之一，它是一种能够按照线性顺序存储数据元素的数据结构。

线性表可以通过顺序存储结构或链式存储结构来实现。

1. 顺序存储结构顺序存储结构是将线性表的元素按照顺序存储在一块连续的存储空间中。

在编译技术中，顺序存储结构常用于存储符号表、常量表等数据结构。

通过数组来实现顺序存储结构，可以快速访问线性表的任意位置元素。

2. 链式存储结构链式存储结构是通过节点之间的指针链接来实现线性表的存储。

在编译技术中，链式存储结构常用于存储中间代码、语法树等数据结构。

链式存储结构灵活性较高，可以动态地分配和释放存储空间。

二、栈栈是一种具有后进先出（LIFO）特性的线性表。

在编译技术中，栈常用于处理函数调用、表达式求值等场景。

栈的基本操作包括入栈和出栈。

入栈将元素压入栈顶，出栈将栈顶元素弹出。

编译技术中，栈还常用于处理函数的局部变量、函数的三、队列队列是一种具有先进先出（FIFO）特性的线性表。

在编译技术中，队列常用于处理优化算法、指令调度等场景。

队列的基本操作包括入队和出队。

入队将元素插入队尾，出队将队头元素移除。

编译技术中，队列还常用于处理指令流水线、任务调度等问题。

四、树树是一种非线性的数据结构，它由若干个节点组成，节点之间通过边连接。

在编译技术中，树常用于构建语法树、抽象语法树等数据结构。

树的基本概念包括根节点、叶子节点和内部节点。

树的遍历方式有前序遍历、中序遍历和后序遍历。

编译技术中，树的遍历常用于语法分析、语义分析等阶段。

五、图图是一种由节点和边组成的非线性数据结构。

在编译技术中，图常用于构建控制流图、数据依赖图等数据结构。

图的基本概念包括顶点、边和路径。

图可以分为有向图和无向图，还可以带有权重。

编译技术中，图的遍历常用于寻找程序中的循环、六、哈希表哈希表是一种通过哈希函数将关键字映射到存储位置的数据结构。

在编译技术中，哈希表常用于符号表、常量表等数据结构。

线性表

线性表

举例:
La=(34，89，765，12，90，-34，22) 数据元素类型为int。 Ls=(Hello,World, China, Welcome) 数据元素类型为 string。 Lb=(book1,book2,...,book100) 数据元素类型为下列所示的结 构类型： struct bookinfo { int No; //图书编号 char *name; //图书名称 char *auther; //作者名称 ...; };
素的方法被称为随机存取法，使用这种存取方法的存储结构被
称为随机存储结构。
在C语言中，实现线性表的顺序存储结构的类型定义
typedef int ElemType; //定义顺序表中元素的类型 #define INITSIZE 100 //顺序表存储空间初始分配量 #define LISTINCREMENT 10 //线性表存储空间的分配增量 typedef struct { ElemType *data; int length; //存储空间的基地址 //线性表的当前长度
说明：
1. 某数据结构上的基本运算，不是它的全部运算，而是一些 常用的基本的运算，而每一个基本运算在实现时也可能根据不 同的存储结构派生出一系列相关的运算来， 没有必要全部定义 出它的运算集。掌握了某一数据结构上的基本运算后，其它的 运算可以通过基本运算来实现，也可以直接去实现。 2. 在上面各操作中定义的线性表Ｌ仅仅是一个抽象在逻辑结 构层次的线性表，尚未涉及到它的存储结构，因此每个操作在 逻辑结构层次上尚不能用具体的某种程序语言写出具体的算法， 而算法的实现只有在存储结构确立之后。
4. 求顺序表的长度 int getlen(sqlist L) { return (L.length); } 5. 判断顺序表是否为空 int listempty(sqlist L) { if (L.length==0) return 1; else return 0; }

专升本数据结构试卷答案

专升本数据结构试卷答案

专升本数据结构试卷答案一、选择题（每题 2 分，共 30 分）1、在数据结构中，从逻辑上可以把数据结构分为（）。

A 动态结构和静态结构B 紧凑结构和非紧凑结构C 线性结构和非线性结构D 内部结构和外部结构答案：C解析：数据结构从逻辑上分为线性结构和非线性结构。

线性结构是数据元素之间存在一对一的关系，如线性表、栈、队列等；非线性结构是数据元素之间存在一对多或多对多的关系，如树、图等。

2、以下数据结构中，（）是非线性数据结构。

A 栈B 队列C 线性表D 二叉树答案：D解析：二叉树是一种非线性数据结构，每个节点最多有两个子节点。

栈、队列和线性表都属于线性数据结构。

3、一个顺序存储的线性表的第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是（）。

A 108B 110C 106D 104答案：A解析：第一个元素地址为 100，每个元素长度为 2，所以第 5 个元素的地址为 100 ＋ 2×（5 1) ＝ 108。

4、在单链表中，增加头结点的目的是（）。

A 方便运算的实现B 使单链表至少有一个结点C 标识表结点中首结点的位置D 说明单链表是线性表的链式存储实现答案：A解析：头结点的作用是方便运算的实现，比如在插入和删除操作时，可以避免对第一个元素的特殊处理。

5、设栈的顺序存储空间为 S(1:m)，初始状态为 top ＝ 0。

现经过一系列入栈与退栈运算后，top ＝ 20，则当前栈中有（）个元素。

A 20B 21C m 20D m 19答案：A解析：栈是一种先进后出的数据结构，top 指向栈顶元素的位置，top ＝ 20 说明当前栈中有 20 个元素。

6、循环队列的存储空间为 Q(1:50)，初始状态为 front ＝ rear ＝ 25。

经过一系列入队与退队运算后，front ＝ 15，rear ＝ 10，则循环队列中的元素个数为（）。

A 5B 6C 16D 49答案：B解析：循环队列中元素个数的计算公式为：（rear front ＋ 50) ％ 50。

第3章线性表的链式存储

第3章线性表的链式存储
L
(a) 空循环链表
L
a1
a2
...
an
(b) 非空循环链表
3.1.3 双向链表
在单链表结点中只有一个指向其后继结点的next 指针域，而找其前驱则只能从该链表的头指针开始，顺 着各结点的next指针域进行查找，也就是说找后继的时 间复杂度是O(1)，找前驱的时间复杂度是O(n)。如果也 希望找前驱像后继那样快，则只能付出空间的代价：每 个结点再加一个指向前驱的指针域prior，结点的结构修 改为下图，这样链表中有两个方向不同的链，用这种结 点组成的链表称为双向链表。
1．带头结点的单链表 2．不带头结点的单链表
3.3.3 单链表插入操作的实现
单链表的插入操作是指在表的第i个位置结点处插入 一个值为data的新结点。插入操作需要从单链表的第一个结 点开始遍历，直到找到第i个位置的结点。插入操作分为在 结点之前插入的前插操作和在结点之后插入的后插操作。
1．前插操作 2．后插操作
2．整数型单链表算法
3．不带头结点的单链表算法
3.2.2 尾插法单链表的创建实现
用头插法实现单链表的创建，比较简单，但读入的 数据元素的顺序与生成的链表中元素的顺序是相反的。若希 望两者次序一致，则用尾插法创建单链表。为了快速找到新 结点插入到链表的尾部位置，所以需加入一个尾指针r用来 始终指向链表中的尾结点。初始状态：头指针L和尾指针r均 为空，把各数据元素按顺序依次读入，申请结点，将新结点 插入到r所指结点的后面，然后r指向新结点，直到读入结束 标志为止。
3.2.2 尾插法单链表的创建实现
L
插入P前的尾指针 插入P后的尾指针
r
3
4
P1
x^
2
3.3 单链表运算的实现

线性表的链式存储结构实验报告

线性表的链式存储结构实验报告

实验一：线性表的链式存储结构【问题描述】某项比赛中，评委们给某参赛者的评分信息存储在一个带头结点的单向链表中，编写程序：（1）显示在评分中给出最高分和最低分的评委的有关信息（姓名、年龄、所给分数等）。

（2）在链表中删除一个最高分和一个最低分的结点。

（3）计算该参赛者去掉一个最高分和一个最低分后的平均成绩。

【基本要求】（1）建立一个评委打分的单向链表；（2）显示删除相关结点后的链表信息。

（3）显示要求的结果。

【实验步骤;】（1）运行PC中的Microsoft Visual C++ 6.0程序，（2）点击“文件”→“新建”→对话窗口中“文件”→“c++ Source File”→在“文件名”中输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”，（3）输入程序代码，程序代码如下:head=create(PWRS);printf("所有评委打分信息如下:\n");print(head);//显示当前评委打分calc(head);//计算成绩printf("该选手去掉 1 最高分和 1 最低分后的有效评委成绩:\n");print(head);//显示去掉极限分后的评委打分}void input(NODE *s) #include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <iostream.h>#include <conio.h>#define NULL 0#define PWRS 5 //定义评委人数struct pw //定义评委信息{ char name[6];float score;int age;};typedef struct pw PW;struct node //定义链表结点{struct pw data;struct node * next;};typedef struct node NODE;//自定义函数的声明NODE *create(int m); //创建单链表int calc(NODE *h); //计算、数据处理void print(NODE *h); //输出所有评委打分数据void input(NODE *s);//输入评委打分数据void output(NODE *s);//输出评委打分数据void main(){NODE *head;float ave=0;float sum=0;{printf("请输入评委的姓名: ");scanf("%S",&s->);printf("年龄: ");scanf("%d",&s->data.age);printf("打分: ");scanf("%f",&s->data.score);printf("\n");}void output(NODE *s){printf("评委姓名: %8s ,年龄: %d,打分: %2.2f\n",s->,s->data.age,s->data.score);}NODE *create(int m){NODE *head,*p,*q;int i;p=(NODE*)malloc(sizeof(NODE));head=p;q=p;p->next=NULL;for(i=1;i<=m;i++){p=(NODE*)malloc(sizeof(NODE));input(p);p->next=NULL;q->next=p;q=p;}return (head);}void print(NODE *h){ for(int i=1;((i<=PWRS)&&(h->next!=NULL));i++){h=h->next;output(h); }printf("\n");}int calc(NODE *h){NODE *q,*p,*pmin,*pmax;float sum=0;float ave=0;p=h->next; //指向首元结点pmin=pmax=p; //设置初始值sum+=p->data.score;p=p->next;for(;p!=NULL;p=p->next){if(p->data.score>pmax->data.score) pmax=p;if(p->data.score<pmin->data.score) pmin=p;sum+=p->data.score;}cout<<"给出最高分的评委姓名："<<pmax-><<"年龄： "<<pmax->data.age<<"分值："<<pmax->data.score<<endl;cout<<"给出最低分的评委姓名："<<pmin-><<"年龄： "<<pmin->data.age<<"分值："<<pmin->data.score<<endl;printf("\n");sum-=pmin->data.score;sum-=pmax->data.score;for (q=h,p=h->next;p!=NULL;q=p,p=p->next){if(p==pmin){q->next=p->next; p=q;}//删除最低分结点if(p==pmax) {q->next=p->next; p=q;}//删除最高分结点}ave=sum/(PWRS-2);cout<<"该选手的最后得分是："<<ave<<endl;return 1;}实验结束。

第3章 线性表及其存储结构

第3章 线性表及其存储结构

链式存储结构，既可用来表示线性结构， 也可用来表示非线性结构。线性表的链式存 储结构，称为线性链表。 对线性链表而言，它不要求逻辑上相邻的 元素在物理位置上也相邻。其存储单元既可 以是连续的，也可以是不连续的，甚至可以 零散分布在内存中的任何位置上。 通常，为了适应线性链表的存储，计算机 的存储空间被划分成一个一个的小块，每一 小块占若干字节，这些小块就是存储结点。 存储结点的结构，如图 3-2 所示。
在稍微复杂的线性表中，一个数据元素还 可以由若干个数据项组成。例如，某班的学 生情况登记表是一个复杂的线性表，表中每 一个学生的情况就组成了线性表中的每一个 元素，每一个数据元素包括学号、姓名、性 别、入学成绩4个数据项。
3.2线性表的顺序存储及其运算
3.2.1 线性表的顺序存储 线性表的顺序存储结构称为顺序表。
第3章 线性表及其存储结构
3.1线性表的基本 概念 3.2线性表的顺序 存储及运算 3.3线性表的链式 存储及运算
3.1 线性表的基本概念
线性表是由 n (n≥0)个数据元素 a1 ,a2 ,…,an 组成的一个有限序列。表中的每一个数据元 素，除了第一个外，有且只有一个前件；除 了最后一个外，有且只有一个后件。即线性 表或是一个空表或可以表示为：
（a1 ,a2 ,…,ai ,…,an）其中 ai（i=1,2,…,n) 是属于数据对象的元素，通常也称其为线性 表中的一个结点。
数据元素在线性表中的位置，只取决于它们 自己的序号 。 非空线性表的结构特征为： ① 有且只有一个根结点a1 ,它无前件；
② 有且只有一个终端结点an ,它无后件；
③ 除根结点与终端结点外，其他所有结点 有且只有一个前件，也有且只有一个后件。线 性表中结点的个数n称为线性表的长度。当 n=0时，称为空表。

实验五__线性表的链式表示和实现

浙江大学城市学院实验报告课程名称数据结构基础实验项目名称实验五线性表的链式表示和实现学生姓名专业班级学号实验成绩指导老师（签名）日期一.实验目的和要求1、了解线性表的链式存储结构，学会定义线性表的链式存储结构。

2、掌握单链表、循环单链表的一些基本操作实现函数。

二.实验内容1、设线性表采用带表头附加结点的单链表存储结构，请编写线性表抽象数据类型各基本操作的实现函数，并存放在头文件LinkList.h中（注：教材上为不带表头附加结点）。

同时建立一个验证操作实现的主函数文件test5.cpp，编译并调试程序，直到正确运行。

提示：⑴单向链表的存储结构可定义如下：struct LNode { // 定义单链表节点类型ElemType data; // 存放结点中的数据信息LNode *next; // 指示下一个结点地址的指针}⑵线性表基本操作可包括如下一些：①void InitList (LNode *&H) //初始化单链表②void ClearList(LNode *&H) //清除单链表③int LengthList (LNode *H) //求单链表长度④bool EmptyList (LNode *H) //判断单链表是否为空表⑤ElemType GetList (LNode *H, int pos)//取单链表第pos 位置上的元素⑥void TraverseList(LNode *H) //遍历单链表⑦bool InsertList ( LNode *&H, ElemType item, int pos)//向单链表插入一个元素⑧bool DeleteList ( LNode *&H, ElemType &item, int pos)//从单链表中删除一个元素⑶带表头附加结点的单链表初始化操作的实现可参考如下：void InitList(LNode *&H){ //构造一个空的线性链表H，即为链表设置一个头结点，//头结点的data数据域不赋任何值，头结点的指针域next则为空H=(LNode *)malloc(sizeof(LNode)); // 产生头结点Hif (!H) exit(0); // 存储分配失败，退出系统H->next=NULL; // 指针域为空}2、选做部分：编写一个函数void MergeList(LNode *&La, LNode *&Lb, LNode *&Lc)，实现将两个有序单链表La和Lb合并成一个新的有序单链表Lc，同时销毁原有单链表La和Lb。

数据结构（二）：线性表的链式存储结构

数据结构（⼆）：线性表的链式存储结构1、为什么要使⽤链式存储结构？因为我们前⾯讲的线性表的顺序存储结构，他是有缺点的。

最⼤的缺点就是插⼊和删除时需要移动⼤量元素，这显然就需要耗费时间。

要解决这个问题，我们就需要分析⼀下为什么当插⼊和删除时，就要移动⼤量元素，因为相邻两元素的存储位置也具有相邻关系，它们在内存中的位置也是挨着的，中间没有空隙，当然就⽆法快速介⼊，⽽删除之后。

当中就会留出空隙，⾃然就需要弥补。

问题就出在这⾥。

为了解决这个问题，⾃然⽽然的就出现了链式存储结构。

2、线性表链式存储结构的特点：线性表的链式存储结构不考虑元素的存储位置，⽽是⽤⼀组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，这就意味着，这些数据元素可以存在内存未被占⽤的任意位置。

顺序存储结构：只需要存储数据元素信息。

链式存储结构：除了要存储数据元素信息之外，还要存储⼀个指⽰其直接后继元素的存储地址。

3、关键词：数据域：存储数据元素信息的域。

指针域：存储直接后继位置的域。

指针或链：指针域中存储的信息。

结点（Node）：指针域+数据域组成数据元素的存储映像。

头指针：链表中第⼀个结点的存储位置。

头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。

头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。

4、单链表：定义：n个结点链成⼀个链表，即为线性表的链式存储结构，因此此链表的每个结点中只包含⼀个指针域，所以叫做单链表。

PS：线性链表的最后⼀个结点指针为“空”,通常⽤NILL或“^”符号表⽰。

头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。

头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。

5、头结点与头指针的异同（1）头结点头结点是为了操作的统⼀和⽅便⽽设⽴的，放在第⼀个元素的结点之前，其数据域⼀般⽆意义（也可存放链表的长度）有了头结点，对第⼀元素结点前插⼊和删除第⼀结点，其操作就统⼀了头结点不⼀定是链表的必要素（2）头指针头指针式指向第⼀个结点的指针，若链表有头结点，则是指向头结点的指针。

线性表的链式存储结构

1
线性表的链式存储结构
线性表的链式存储结构是指用一组任意的存储单 元（可以连续，也可以不连续）存储线性表中的数据 元素。为了反映数据元素之间的逻辑关系，对于每个 数据元素不仅要表示它的具体内容，还要附加一个表 示它的直接后继元素存储位置的信息。假设有一个线 性表（a,b,c,d），可用下图2所示的形式存储：
27
p
s
图 2-9
28
完整的算法：
int DuListInsert(DuLinkList *L,int i,EntryType e)
if (L.head->next==NULL) return TRUE; else return FALSE; }
12
6. 通过e返回链表L中第i个数据元素的内容 void GetElem(LinkList L,int i,EntryType *e) {
LNode *p; int j; //j为计数器，记载所经过的结点数目 if (i<1||i>ListLength(L)) exit ERROR; //检测i值的合理性 for (p=L.head,j=0; j!=i;p=p->next,j++); //找到第i个结点 *e=p->data; //将第i个结点的内容赋给e指针所指向的存储单元中 }
10
4. 求链表L的长度
int ListLength(LinkList L)
{
LNode *p;
int len;
for(p=L.head, len=0;p->next==NULL; p=p->next,len++);
return(len);
循环条件表达式 重复执行的语句

第3章数据结构基本类型3.1线性表-高中教学同步《信息技术-数据与数据结构》(教案)

学生预习：
布置预习任务，要求学生提前阅读线性表的基础知识和概念。
发放预习材料，如PPT、视频教程或预习习题。
课堂讨论引导：
准备引导性问题，鼓励学生积极参与课堂讨论。
设计小组活动，促进学生之间的合作与交流。
课后反馈：
设计课后习题和作业，以检验学生的学习效果。
准备课后答疑和辅导，为学生提供必要的帮助和支持。
确保教学环境中网络连接稳定，以便在需要时展示在线资源或示例。
教学媒体
教学媒体
PPT演示文稿：
线性表的基本概念、定义、特点和示例的幻灯片。
顺序存储和链式存储的对比图示。
线性表基本操作（如初始化、查找、插入、删除）的动画或图解。
代码编辑器/IDE：
演示顺序表和链表的实现代码（如Python）。
允许学生直接看到、理解和操作代码。
情感、态度与价值观：
激发学生的学习兴趣和创造力，培养学生的探索精神和创新精神。
引导学生认识到数据结构在解决实际问题中的重要性，形成合理的计算机思维观念。
学习重难点
教学重点
线性表的基本概念：理解线性表是什么，它如何表示具有相同பைடு நூலகம்型数据元素的有限序列，并理解其特点，包括唯一的首尾元素以及除首尾外每个元素有且仅有一个前驱和后继。
准备用于课堂讨论的实例和问题，如通信录的设计和实现。
准备教学用计算机和相关编程环境（如Python环境），以便现场演示代码和执行结果。
教学流程设计：
设计教学流程，从线性表的基础概念引入，逐步深入到线性表的存储方式和操作。
设计课堂互动环节，如提问、小组讨论等，鼓励学生积极参与和表达。
安排编程实践环节，让学生亲自编写线性表相关操作的代码，加深理解。
线性表的应用场景：通过通信录的实例，了解线性表在实际问题中的应用，并理解如何根据需求选择合适的数据结构和存储方式。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
i
结点 数据域 指针域
链式存储
h
1345
存储地址 1345 1346 ……. 1400 ……. 1536
存储内容 元素1 元素4 …….. 元素2 …….. 元素3
指针 1400 ∧ ……. 1536 ……. 1346
h
元素1 1400
元素2 1536
元素3 1346
元素4
特点：
•存储空间不一定连续 •逻辑关系是由指针来体现的； •逻辑上相邻，物理上不一定相邻 •非随机存取（顺序存取），即访问任何一个元素的 时间不同
p ai-1
u ai ai+1
单链表的基本算法描述
P
ai-1
6、删除
×
ai
ai+1
分析：
A、搜索位置； while (p!=NULL&& k!=i-1){p=p->next;k++;}
if (!p ||p->next==NULL) return ERROR;
//在带头结点的单链线性表L中删除第i个位置之 前元素 void List_delete(node *L,int i) { LinkList p=L,u; int k=0; node s; //k计数
2.3线性表的链式存储实现
一、单链表基本结构
二、单链表的实现
三、单链表的基本算法描述
2.3.1 线性表的链式存储结构 存储方式
•用一组地址任意的存储单元存储线性表的数 据元素 •利用指针实现了用不相邻的存储单元存放逻 辑上相邻的元素 •每个数据元素a ，除存储本身信息外，还需 存储其直接后继的信息 其中：元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点(表示数据元素及其映象)
头指针
头结点
线性表为空表时， 头指针 头结点的指针域为空
空指针

a1
a2
… ...
an ^
以线性表中第一个数据元素 a1 的存储 地址作为线性表的地址，称作线性表的 头指针。
有时为了操作方便，在第一个结点之 前虚加一个“头结点”，以指向头结点 的指针为链表的头指针。
何谓头指针、头结点和首元结点？
L 21
i=3 p
18
p
30
p
75
42 j 1 3 2
56 ∧
单链表的运算的实现
算法演示
L a b …… m i=13 j=13 p j=1 j=2
node * GetElem_L(LinkList L,int i)
{node *p=L->next;int j=1;
while(p&&j<i){ p=p->next;++j;} return p;}
x
ai
分析：
A、搜索位置； while (p&& k<i-1) {p=p->next;k++;}
if (!p ||j>i-1) return ERROR;
//在带头结点的单链线性表L中第i个位置之前 插入元素x void ListInsert_L(node L,int i,elementtype x) { LinkList p=L; int k=0; node s; //k计数
•C语言实现
typedef struct node { elementtype data; // 数据域 struct node *next; // 指针域
} node, *LinkList;
LinkList L； // L 为单链表的头指针
知识回顾
node *L,*p;
<=>LinkList L,p
结点
next
L
a1
a2
a3
…...
an
^
P
如图所示,在当前的情况下: ： P->data是什么？ P->next是什么？ P->next ->data是什么？ 使P指向下一个结点的语句是什么? 如何判断已到表尾?
2.3.2
单链表的基本算法描述
• 初始化单链表（建空表） • 求单链表表长 • 查找(取第i个数据元素\按内容查找) • 插入 • 删除 • 链表的构造
一种较简便的插入方法是：先将qtr所指的结点插入到ptr所指结点 的后面,然后再将这两个结点的内容进行交换，从而达到在指定位 置前面插入的目的。
① qtr->Next = ptr->Next; ③temp = ptr->Data; ⑤qtr->Data = temp;
ptr
②ptr->Next = qtr ;
注意：初始条件和书上的不一样。结束条件也不一样。
return(P);
单链表的运算的实现
按内容查找
算法描述：设置一个跟踪链表结点的指针P， 初始时P指向表的的第一个结点，然后顺着 next域依次指向每一个结点，每指向一个结点 就判断是否等于e。若是则返回该结点的地址， 否则继续往后搜索，直到P为null，表示链表 L中无此元素，返回NULL。
有序对<ai-1, ai> 和 <ai, ai+1>
改变为 <ai-1, ai+1> ai-1 ai ai+1
单链表的基本算法描述
在单链表中删除第 i 个结点的基本
操作为:找到线性表中第i-1个结点，修 改其指向后继的指针。
u = p->next; p->next = u->next;
e = u->data; free(u);
a b …… e ……
p
n
^
单链表的运算的实现
4、按值查询 —— 返回元素结点指针，否则返回NULL；
P L a1
P=L->next; P!=NULL
Y
a2
a3
^
N
P->data!=x
Y
N
node *locate(node *L,elementtype x) { P=L->next; return(P); while(P!=NULL&&P->data!=x) P=P->next; return(P); return(P); }
L
P=L->next; len=0; P!=NULL
Y N
NO.1
P
a1
len=0 len=1 P P a2 a3
len=2 P ^
len=3
return(len);
P=P->next; len++;
int list_length(node *L) {P=L->next; len=0; while(P!=NULL) {P=P->next; len++;} return(len); }
头指针 头结点 首元结点 a1
头指针是指向链表中第一个结点（或为头结点 或为首元结点）的指针。 单链表可由一个头指针唯一确定。 头结点是在链表的首元结点之前附设的一个结 点；数据域内只放空表标志和表长等信 息; 首元结点是指链表中存储线性表第一个数据元 素a1的结点。
例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)
21
18
30
75
42
e=30
56 ∧
p
p
p
单链表的运算的实现
L
LinkList locateElem_L(LinkList L, int e) {p = L->next; // 初始化，p指向第一个结 点 while (p &&p->data!=e) { // 顺指针向后查找，直到p指向元素e或p 为空 p = p->next;} return p; } // locateElem_L
存储地址
头指针 H 31 1 7 13 19 25 31 37 43
数据域 LI QIAN SUN
指针域 43 13 1
WANG WU ZHAO ZHENG ZHOU
NULL 37 7 19 25
H ZHAO ZHOU QIAN SUN ZHENG
LIWLeabharlann NGWU^• 线性链表定义及C语言实现
– 定义：结点中只含一个指针域的链表叫~，也叫单 链表
B、删除结点；u=p->next; //指向待删除的结点
p->next=u->next; //绕过待删除的结点
C、释放结点；free(u); //释放所删除结点的存储空间
}
单链表的基本算法描述
在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
//在带头结点的单链线性表L中，删除第i个元 素，并由e返回其值 status ListDelete_L(LinkList L,int i,elementtype *e) { Linklist p=L;int j=0; while (p->next && j<i-1) { p=p->next; ++j;} if (!(p->next) ||j>i-1) return ERROR; q=p->next; p->next=q->next; e=q->data; free(q); return OK; }//list_delete_L
2.3单链表的基本算法描述 （有头结点）
L
1、初始化单链表（建空表） void initial_list(node *&L) { L=(LinkList )malloc(sizeof(node)); L = new node; L -> next = NULL; }