《数据结构实例教程（C语言版）：第2章 线性表的结构分析与应用》由会员分享，可在线阅读，更多相关《数据结构实例教程（C语言版）：第2章 线性表的结构分析与应用（22页珍藏版）》请在装配图网上搜索。
1、数据结构实例教程（数据结构实例教程（C语言版）语言版）第第2 2章线性表的结构分析与应用章线性表的结构分析与应用 学习目标学习目标 了解线性表的逻辑结构。熟练掌握线性表的顺序存储结构及顺序表的基 本操作实现。熟练掌握线性表的链式存储结构单链表以 及单链表上的基本操作实现。掌握顺序表和单链表的各自特点和适用场合。数据结构实例教程（数据结构实例教程（C语言版）语言版）2.12.1线性表的逻辑结构线性表的逻辑结构 一、线性表的逻辑定义 线性表是由n（n0）个数据元素（结点）a1，a2，an组成的有限序列。a1 a2 a3 a4 a5 a2a2是是a3a3的直接前趋，的直接前趋，a3a3是是a2a2的
2、直接后继。的直接后继。a1a1没有直接前趋，没有直接前趋，a5a5没有直接后继。没有直接后继。数据结构实例教程（数据结构实例教程（C语言版）语言版）2.12.1线性表的逻辑结构线性表的逻辑结构 二、线性表的基本运算 1、InitList（L）：表的初始化。2、ListLength（L）：求表长。3、GetNode（L，i）：取线性表L中的第i个结点。4、LocateNode（L，x）：在L中查找值为x 的结点。5、InsertList（L，x，i）：在表L的第i个位置上插入一个值x。6、DeleteList（L，i）：删除线性表L的第i个结点。数据结构实例教程（数据结构实例教程（C语言版）语言
3、版）2.22.2线性表的顺序存储结构线性表的顺序存储结构 一、顺序表定义及地址计算 1、顺序表的定义：用顺序存储方法存储的线性表。逻辑上连续的学生连续的坐在座位上数据结构实例教程（数据结构实例教程（C语言版）语言版）2.22.2线性表的顺序存储结构线性表的顺序存储结构 一、顺序表定义及地址计算 2、顺序表的地址计算每个元素占用4个存储单元a1a2a3a4a5100a4a4的地址为的地址为100+(3100+(3*4)=1124)=112 地址计算公式：LOC(ai)=LOC(a1)+(i-1)*c (c为存储单元)3、顺序表类型定义typedef struct typedef struct i
4、nt data10 int data10；/向量向量datadata用于存放表结点用于存放表结点 int length int length；/当前的表长度当前的表长度 SeqListSeqList；/结构体类型结构体类型112数据结构实例教程（数据结构实例教程（C语言版）语言版）2.22.2线性表的顺序存储结构线性表的顺序存储结构 二、顺序表基本运算 1、插入运算举例：举例：X=X=11插入到下标为插入到下标为1 1的位置的位置10 012341312143号学生要坐在4号的座位11数据结构实例教程（数据结构实例教程（C语言版）语言版）2.22.2线性表的顺序存储结构线性表的顺序存储结构 二
5、、顺序表基本运算 插入运算的算法如下：void InsertList(SeqList void InsertList(SeqList*L L，DataType xDataType x，int i)int i)/将新结点将新结点 x x插入插入L L所指的顺序表的第所指的顺序表的第i i个结点个结点ai ai的位置上的位置上 int j;int j;if(iL-length+1)Error(“position error”);/if(iL-length+1)Error(“position error”);/非法位置非法位置 if(L-length=ListSize)Error(“overflow
6、”);/if(L-length=ListSize)Error(“overflow”);/表空间溢出表空间溢出 for(j=L-length-1;j=i-1;j-)for(j=L-length-1;j=i-1;j-)L-dataj+1=L-dataj;/L-dataj+1=L-dataj;/结点后移结点后移 L-datai-1=x;/L-datai-1=x;/插入插入x x L-Length+;/L-Length+;/表长加表长加1 1 数据结构实例教程（数据结构实例教程（C语言版）语言版）2.22.2线性表的顺序存储结构线性表的顺序存储结构 二、顺序表基本运算 2、删除运算举例：删除下标为举例
7、：删除下标为1 1的数据的数据10 012341211133号学生转本离开14数据结构实例教程（数据结构实例教程（C语言版）语言版）2.22.2线性表的顺序存储结构线性表的顺序存储结构 二、顺序表基本运算 删除运算的算法如下：void DeleteList(SeqList void DeleteList(SeqList*L,int i)L,int i)/从从L L所指的顺序表中删除第所指的顺序表中删除第i i个结点个结点ai ai int j;int j;if(iL-length)if(iL-length)Error(position error);/Error(position error)
8、;/非法位置非法位置 for(j=i;jlength-1;j+)for(j=i;jlength-1;j+)L-dataj-1=L-dataj;/L-dataj-1=L-dataj;/结点前移结点前移 L-length-;/L-length-;/表长减小表长减小 数据结构实例教程（数据结构实例教程（C语言版）语言版）2.32.3线性表的链式存储结构线性表的链式存储结构 一、链表的定义链表的定义：用链接方式存储的线性表。同一宿舍的5名同学未必坐在连续的座位上，通过心将每一位宿舍成员连接在一起。数据结构实例教程（数据结构实例教程（C语言版）语言版）2.32.3线性表的链式存储结构线性表的链式存储结构
9、 二、单链表1、单链表结点类型定义 typedef struct nodetypedef struct node DataType data;/DataType data;/结点的数据域，结点的数据域，DataTypeDataType为数据类型为数据类型 struct node struct node*next;/next;/结点的指针域结点的指针域ListNode;ListNode;数据域 指针域datanext结点空间开辟：p=(ListNode p=(ListNode*)malloc(sizeof(ListNode)malloc(sizeof(ListNode)数据结构实例教程（数据结构
10、实例教程（C语言版）语言版）2.32.3线性表的链式存储结构线性表的链式存储结构 二、单链表2、单链表的建立 a1a2a3head采用尾插法建表:该方法是将新结点插到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。rs数据结构实例教程（数据结构实例教程（C语言版）语言版）2.32.3线性表的链式存储结构线性表的链式存储结构 二、单链表尾插法建立带头结点的单链表算法如下：LinkList CreatList()LinkList CreatList()char ch;char ch;ListNode ListNode*head=(ListNode head=(ListNo
11、de*)malloc(sizeof(ListNode);/)malloc(sizeof(ListNode);/头结点头结点 ListNode ListNode*s,s,*r;/r;/工作指针工作指针 r=head;/r=head;/尾指针初值也指向头结点尾指针初值也指向头结点 while(ch=getchar()!=n)while(ch=getchar()!=n)s=(ListNode s=(ListNode*)malloc(sizeof(ListNode);/)malloc(sizeof(ListNode);/生成新结点，第生成新结点，第1 1步步 s-data=ch;/s-data=ch;
12、/将读入的数据放入新结点的数据域中，第将读入的数据放入新结点的数据域中，第2 2步步 r-next=s;/r-next=s;/第第3 3步步 r=s;/r=s;/第第4 4步步 r-next=NULL;/r-next=NULL;/终端结点的指针域置空终端结点的指针域置空 return head;return head;数据结构实例教程（数据结构实例教程（C语言版）语言版）2.32.3线性表的链式存储结构线性表的链式存储结构 二、单链表3、插入运算 a1ai-1aihead插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。pxs数据结构实例教程（数据结构实例教程
13、（C语言版）语言版）2.32.3线性表的链式存储结构线性表的链式存储结构 二、单链表插入运算的算法如下：/在带头结点的单链表在带头结点的单链表headhead中查找第中查找第i i个结点个结点ListNodeListNode*GetNode(ListNode GetNode(ListNode*head,int i)head,int i)int j;int j;ListNode ListNode*p;p;p=head;j=0;/p=head;j=0;/从头结点开始扫描从头结点开始扫描 while(p-next&jnext&jnext;p=p-next;j+;j+;if(i=j)if(i=j)re
14、turn p;/return p;/找到了第找到了第i i个结点个结点 else return NULL;/else return NULL;/当当i0inin时，找不到第时，找不到第i i个结点个结点 数据结构实例教程（数据结构实例教程（C语言版）语言版）2.32.3线性表的链式存储结构线性表的链式存储结构 二、单链表插入运算的算法如下：/将值为将值为x x的新结点插入到带头结点的单链表的第的新结点插入到带头结点的单链表的第i i个结点的位置上个结点的位置上void InsertList(ListNode void InsertList(ListNode*head,DataType x,in
15、t i)head,DataType x,int i)ListNode ListNode*p,p,*s;s;p=GetNode(head,i-1);/p=GetNode(head,i-1);/寻找第寻找第i-1i-1个结点个结点 if(p=NULL)/i1 if(p=NULL)/in+1in+1时插入位置时插入位置i i有错有错 Error(position error);Error(position error);s=(ListNode s=(ListNode*)malloc(sizeof(ListNode);/)malloc(sizeof(ListNode);/第第1 1步步 s-data=
16、x;/s-data=x;/第第2 2步步 s-next=p-next;/s-next=p-next;/第第3 3步步 p-next=s;/p-next=s;/第第4 4步步 数据结构实例教程（数据结构实例教程（C语言版）语言版）2.32.3线性表的链式存储结构线性表的链式存储结构 二、单链表4、删除运算 a1ai-1aihead删除运算是将表的第i个结点删去。通过执行free(r)释放ai位置结点的空间，节省内存空间。pxr数据结构实例教程（数据结构实例教程（C语言版）语言版）2.32.3线性表的链式存储结构线性表的链式存储结构 二、单链表删除运算的算法如下：/在带头结点的单链表在带头结点的单
17、链表headhead中查找第中查找第i i个结点个结点void DeleteList(ListNode void DeleteList(ListNode*head,int i)head,int i)/删除带头结点的单链表删除带头结点的单链表headhead上的第上的第i i个结点个结点 ListNode ListNode*p,p,*r;r;p=GetNode(head,i-1);/p=GetNode(head,i-1);/找到第找到第i-1i-1个结点个结点,第第1 1步步 if(p=NULL|p-next=NULL)/inext=NULL)/inin时，删除位置错时，删除位置错 Error(
18、position error);/Error(position error);/退出程序运行退出程序运行 r=p-next;/r=p-next;/使使r r指向被删除的结点指向被删除的结点a i,a i,第第2 2步步 p-next=r-next;/p-next=r-next;/将将a ia i从链上跨过从链上跨过 ,第第3 3步步 free(r);/free(r);/释放结点释放结点a i a i 的空间的空间,第第4 4步步 数据结构实例教程（数据结构实例教程（C语言版）语言版）2.32.3线性表的链式存储结构线性表的链式存储结构 三、循环链表1、循环链表的定义：循环链表是一种首尾相接的链
19、表。同一宿舍的5名同学未必坐在连续的座位上，通过心将 5位同学首尾连接。数据结构实例教程（数据结构实例教程（C语言版）语言版）2.32.3线性表的链式存储结构线性表的链式存储结构 三、循环链表2、循环链表示意图如下：数据结构实例教程（数据结构实例教程（C语言版）语言版）2.42.4顺序表和链表的比较顺序表和链表的比较 一、基于空间考虑 存储密度是指结点数据本身所占的存储量和整个结点结构所占的存储总量之比，即存储密度=（结点数据本身所占的存储量）/（整个结点结构所占的存储总量）顺序表的存储密度为1，而链表的存储密度小于1。由此可知，当线性表的长度变化不大，易于事先确定其大小时，为了节约 存储空间，宜采用顺序表作为存储结构。数据结构实例教程（数据结构实例教程（C语言版）语言版）2.42.4顺序表和链表的比较顺序表和链表的比较 二、基于时间的考虑 顺序表是一种随机存取结构，对表中任一结点都可在O(1)时间内直接地存取，而链表中的结点，需从头指针起顺着链扫描才能取得。因此，若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜。在链表中的任何位置上进行插入和删除，都只需要修改指针，而在顺序表中进行插入和删除，需要移动大量结点，花费更多时间，因此，对于频繁进行插入和删除的线性表，宜采用链表做存储结构。
数据结构实例教程（C语言版）：第2章 线性表的结构分析与应用
