第三章 线性表的链式存储结构教案
第3章 线性表的链式存储结构
● 线性表的链式存储结构 ● 线性表的应用举例
线性表顺序存储结构的特点 它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。
暴露的问题
● 在做插入或删除元素的操作时，会产生大量的数据元素移动； ● 对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又
得不到充分的利用； ● 线性表的容量难以扩充。
第一节 线性表的链式存储结构
线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表（a,b,c,d ），可用下图所示的形式存储：
存储地址
内容
直接后继存储地
址
100
(120)
... 144 ...
160 ...
术语
表示每个数据元素的两部分信息组合在一起被称为结点； 其中表示数据元素内容的部分被称为数据域（data ）；
表示直接后继元素存储地址的部分被称为指针或指针域（next ）。 单链表简化的图形描述形式 其中，head 是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值NULL 。NULL 值
首元素位置
在图示中常用（^）符号表示。
带头结点的单链表
为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为头结点。这样可以免去对链表第一个结点的特殊处理。如下图所示：
链式存储结构的特点
（1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；
（2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。
在C语言中，实现线性表的链式存储结构的类型定义
typedef strcut node{ //结点类型
EntryType item;
struct node *next;
}NODE;
typedef struct{ //链表类型
NODE *head;
}LINK_LIST;
典型操作的算法实现
（1）初始化链表L
int InitList(LINK_LIST *L)
{
L->head=(*NODE)malloc(sizeof(NODE)); //为头结点分配存储单元
if (L->head) {L->head->next=NULL; return OK;}
else return ERROR ;
}
（2）销毁链表L
void DestoryList(LINK_LIST *L)
{
NODE *p;
while (L->head){ //依次删除链表中的所有结点
p=L->head; L->head=L->head->next;
free(p);
}
}
（3）清空链表L
void ClearList(LINK_LIST *L)
{
NODE *p;
while (L->head->next){
p=L->head->next; //p指向链表中头结点后面的第一个结点
L->head->next=p->next; //删除p结点
free(p); //释放p结点占据的存储空间
}
}
（4）求链表L的长度
int ListLength(LINK_LIST L)
{
NODE *p;
int len;
for(p=L.head, len=0;p->next==NULL; p=p->next,len++);
return(len);
}
（5）判链表L空否。
int IsEmpty(LINK_LIST L)
{
if (L.head->next==NULL) return TRUE;
else return FALSE;
}
（6）通过e返回链表L中第i个数据元素的内容
void GetElem(LINK_LIST L,int i,EntryType *e)
{
NODE *p;
int 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->item; //将第i个结点的内容赋给e指针所指向的存储单元中}
（7）在链表L中检索值为e的数据元素
NODE *LocateELem(LINK_LIST L,EntryType e)
{
NODE *p;
for (p=L.head->next;p&&p->item!=e;p=p->next); //寻找满足条件的结点
return(p);
}
（8）返回链表L中结点e的直接前驱结点
NODE *PriorElem(LINK_LIST L,NODE* e)
{
NODE *p;
if (L.head->next==e) return NULL; //检测第一个结点
for (p=L.head;p->next&&p->next!=e;p=p->next);
if (p->next==e) return p;
esle return NULL;
}
（9）返回链表L中结点e的直接后继结点
NODE *NextElem(LINK_LIST L,NODE* e)
{
NODE *p;
for(p=L.head->next;p&&p!=e;p=p->next);
if (p) p=p->next;
return p;
}
（10）在链表L中第i个数据元素之前插入数据元素e
int ListInsert(LINK_LIST *L,int i,EntryType e)
{
NODE *p,*s;
int j;
if (i<1||i>ListLength(L)+1) return ERROR;
s=(NODE*)malloc(sizeof(NODE));
if (s==NULL) return ERROR;
s->item=e;
for (p=L->head,j=0;p&&j
return OK;
}
（11）将链表L中第i个数据元素删除，并将其内容保存在e中。
int ListDelete(LINK_LIST *L,int i,EntryType *e)
{
NODE *p*s;
int j;
if (i<1||i>ListLength(L)) return ERROR; //检查i值的合理性
for(p=L->head, j=0;j
s=p->next; //用s指向将要删除的结点
*e=s->item;
p->next=s->next; //删除s指针所指向的结点
free(s);
return OK;
}
循环链表
若将链表中最后一个结点的next域指向
图2-7 带头结点的循环链表示意图
实现循环链表的类型定义与单链表完全相同，它的所有操作也都与单链表类似。只是判断链表结束的条件有所不同。下面我们就列举两个循环链表操作的算法示例。
（1）初始化链表CL
int InitList(LINK_LIST *CL) {
CL->head=(*NODE)malloc(sizeof(NODE));
if (CL->head) {CL->head->next=CL->head; return OK;} //让next 域指向它自身 else return ERROR ; }
（2）在循环链表CL 中检索值为e 的数据元素
NODE *LocateELem(LINK_LIST CL,EntryType e) {
NODE *p;
for (p=CL.head->next;(p!=CL.head)&&(p->item!=e);p=p->next); if (p!=CL.head) return p; else return NULL ; }
双向循环链表
在循环链表中，访问结点的特点
访问后继结点，只需要向后走一步，而访问前驱结点，就需要转一圈。
结论：循环链表并不适用于经常访问前驱结点的情况。
解决方法：在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。所谓双向链表。
双向链表就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点。
用C 语言实现双向循环链表的类型定义——
typedef strcut du_node{ //双向链表的结点类型 EntryType item;
struct du_node *prior,*next; }DU_NODE;
typedef struct{ //双向链表类型 DU_NODE *head; }DU_LINK_LIST;
（1）初始化双向循环链表DL
int InitDuList(DU_LINK_LIST *DL) {
DL->head=(DU_NODE*)malloc(sizeof(DU_NODE)); //为头结点分配存储单元 if (DL->head==NULL) return ERROR;
prior
item
next
DL->head->next=DL->head; //让头结点的next域指向自身
DL->head->prior=DL->head; //让头结点的prior域指向自身
return OK;
}
（2）在双向循环链表DL中，第i个数据元素之前插入数据元素e
在一个结点之前插入一个新结点的过程。
p
在双向循环链表中的p结点之前插入s结点应使用下列语句序列：
s->next=p;
s->prior=p->prior;
p->prior->next=s;
p->prior=s;
完整的算法：
int DuListInsert(DU_LINK_LIST *L,int i,EntryType e)
{
DU_NODE *p,*s;
int j;
if (i<1||i>ListLength(DL)+1) return ERROR; //检测i值的合理性
s=(DU_NODE*)malloc(sizeof(DU_NODE)); //为新结点分配存储单元if (s==NULL) return ERROR;
s->item=e;
for (p=L->head,j=0;p&&j
s->next=p; s->prior=p->prior; //将新结点插入
p->prior->next=s; p->prior=s;
return OK;
}
（3）创建双向循环链表DL。
void Create_Du_Link_List(DU_LINK_LIST *DL)
{
if (InitDulist(DL)==ERROR) exit ERROR;
scan f(“%d”,&data);
for (int i=1;data;i++){
DuListInsert(DL,i,data);
scanf(“%d”,&data);
}
}
第二节线性表的顺序与链式存储结构的比较
顺序存储结构特点：用数组实现，操作简便，但如果在操作时插入，删除元素过多，则需要移动大量元素，会降低程序的效率。
链式存储结构特点：用链表实现，操作相对复杂，但对于移动大量元素的情况，可有效地利用空间。
第三节线性表的应用举例
约瑟夫（Joseph）问题：编号为1，2，···，n的n个人按顺时针方向围坐在一张圆桌旁，每个人手中持有一个密码（正整数）。首先输入一个正整数作为报数上限值m，然后，从第一个人开始按顺时针方向自1开始顺序报数，报到m的人离开桌旁，并将他手中的密码作为新的m值，从顺时针方向的下一个就坐在桌旁的人人开始重新从1报数，如此下去，直至所有人全部离开桌旁为止。
假设有7个人，编号从1到7，他们手中的密码分别是3，1，7，2，4，8，4，最初的m=2，通过报数，这7个人离开桌旁的顺序应该是：2，3，5，4，7，6，1。
数据结构的分析
这个问题的主角是n个人，每个人需要描述的信息有：编号、密码和是否在桌旁的状态。假设有7个人，他们的信息可以表示成下面的形式。
编号密码是否在桌旁的状
态
1 3 1
2 1 1
3 7 1
4 2 1
5 4 1
6 8 1
7 4 1
顺序存储结构
算法描述
让n个人围坐在一张圆桌旁；
for (i=1;i<=n;i++){
从1开始报数，报到m停止；
报到m的人离开桌子；
}
最终的算法实现——
#define LIST_MAX_LENGTH 7
#define n LIST_MAX_LENGTH
typedef int EntryType; //将EntryType定义为int类型
void Joseph(int code[],int n)
{//通过一维数组code带入n个人手中的密码，n是开始就坐在桌旁的人数
SQ_LIST people;
int temp,m; //m是报数的上限值
scanf(“%d”,&m); //输入最初的m
if (InitList(&people)==ERROR) exit ERROR;
for (i=1;i<=n;i++)
if (ListInsert(&people,i,code[i-1])==ERROR) exit ERROR;
position=0; //记录当前报数人的编号
for (i=1;i<=n;i++)
{
count=0; //记录当前所报的数目
do{ //报数
position=(position+1)%n;
GetElem(people,position,&temp);
if (temp>0) count++;
}while (count!=m);
printf(“%d”,position); //输出当前离开桌旁人的编号
GetElem(people,position,&m);
people.item[position-1]=-people.item[position-1]; //将密码变为负值
}
}
链式存储结构
使用一个不带头结点的循环单链表结构。结点结构为：
用C语言定义
typedef struct{ //循环链表中每个结点的数据域部分的类型
int No; //编号
int code; //密码
}INFO;
typedef INFO EntryType;
算法
void Joseph(int code[],int n)
{
LINK_LIST people;
NODE *position,*pre; //position指向当前报数的结点
if (InitList(&people)==ERROR) exit ERROR; //初始化链表people
for (i=1;i<=n;i++) //以n个人的信息为数据域内容向链表插入n个结点
if (ListInsert(&people,i,code[i-1])==ERROR) exit ERROR;
position=people.head; //让position指向最后一个结点，以便报数从第一个开始while (position->next!=people.head)
position= NextElem(people,position);
scanf(“%d”,&m); //输入最初的m
for (i=1;i count=0; //报数处理 do{ position=NextElem(people,position); count++; }while (count!=m); printf(“%d”,position->item.No); //离开桌子处理 m=position->item.code; pre=PriorElem(people,position); pre->next=position->next; free(position); position= pre; } printf(“%d”,pos ition->item.No); //处理最后一个人free(position); } 实验项目名称：线性表的顺序存储结构上的基本运算 （所属课程：数据结构--用C语言描述） 院系：计算机科学与信息工程学院专业班级：网络工程 姓名：000000 学号：0000000000 实验日期：2016.10.20 实验地点：A-06 406 合作者：指导教师：孙高飞 本实验项目成绩：教师签字：日期： （以下为实验报告正文） 一、实验目的 本次实验的目的掌握顺序表的存储结构形式及其描述和基本运算的实现；掌握动 态链表结构及相关算法设计 实验要求：输入和验证程序例题。正确调试程序，记录程序运行结果。完成实验报 告。 二、实验条件 Windows7系统的电脑，vc++6.0软件，书本《数据结构--用c语言描述》 三、实验内容 3.1 根据41页代码，用c语言定义线性表的顺序存储结构。 3.2 根据42页算法2.1实现顺序表的按内容查找。 3.3 根据43页算法2.2实现顺序表的插入运算。 3.4 根据45页算法2.3实现顺序表的删除运算。 四、实验步骤 3.2实验步骤 （1）编写头文件，创建ElemType。 （2）根据根据41页代码，“用c语言定义线性表的顺序存储结构”定义顺序表。 （3）根据42页算法2.1实现顺序表的按内容查找，创建Locate函数。 （4）创建main函数，输入SeqList L的数据元素。 （5）输入要查找的数据元素的值，调用Locate函数，输出结果。 3.3实验步骤 （1）编写头文件，创建ElemType。 （2）根据41页代码，“用c语言定义线性表的顺序存储结构”定义顺序表。 （3）根据43页算法2.2实现顺序表的插入运算，创建InsList函数。 （4）创建printList函数，逐项输出顺序表内的元素及顺序表元素的个数。 （5）创建main函数，输入插入的元素和其位置，调用printLinst函数输出顺序表，调用IntList函数，再次调用printLinst函数输出顺序表。 3.4实验步骤 （1）编写头文件，创建ElemType。 （2）根据根据41页代码，“用c语言定义线性表的顺序存储结构”定义顺序表。 （3）根据45页算法2.3实现顺序表的删除运算，创建DelList函数。 （4）创建printList函数，逐项输出顺序表内的元素及顺序表元素的个数。 （5）创建main函数，输入删除元素的位置，调用printLinst函数输出顺序表，调用DelList函数，再次调用printLinst函数输出顺序表。 五、实验结果 （1）实验3.2顺序表的按内容查找 # include 浙江大学城市学院实验报告 课程名称数据结构基础 实验项目名称实验五线性表的链式表示和实现 学生姓名吴奇专业班级信管1204 学号31201403 实验成绩指导老师（签名）日期 一.实验目的和要求 1、掌握线性表的链式存储结构； 2、掌握单链表、循环单链表的一些基本操作实现函数。 二.实验内容 1、设线性表采用带表头附加结点的单链表存储结构，请编写线性表各基本操作的实现函数，把它们存放在头文件LinkList.h中，同时建立一个验证操作实现的主函数文件test2_2.cpp。编译并调试程序，直到正确运行。 2、选做：编写一个函数void MergeList(LNode *&La, LNode *&Lb, LNode *&Lc) ，实现将两个带表头附加结点的有序单链表La和Lb合并成一个新的带表头附加结点的有序单链表Lc的功能，要求利用原存储空间。请把该函数添加到头文件LinkList.h中，并在主文件test2_2.cpp中添加相应语句进行测试。 3、填写实验报告，实验报告文件取名为report5.doc。 4、上传实验报告文件report5.doc、源程序文件test2_2.cpp及LinkList.h 到Ftp服务器上自己的文件夹下。 三. 函数的功能说明及算法思路 void initlist(lnode *&hl) 初始化链表 { hl=new lnode; 新建头节点 if(!hl){ cout<<"储存分配失败，按任意键退出系统!!"< 1.3线性表及其顺序存储结构 1.线性表的基本概念 线性表是由n个数据元素组成的一个有限序列，表中的每一个数据元素，除了每一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表。 显然线性表是一种线性结构，数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。 非空线性表有如下一些结构特征： （1）有且只有一个根结点，它无前件； （2）有且只有一个根结点，它无后件； （3）除了根结点与终端结点外，其他所有结点有且只有一个前件，也只有且只有一个后件。 2.线性表的存储结构 线性表的顺序存储结构具有以下两个特征： （1）线性表中所有元素所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 由此可以看出，在线性表的顺序存储结构中，其前件和后件两个元素在存储空间中是紧邻的，且其前件元素一定存储在后件元素的前面。 在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储看见。因为程序设计语言中的一维数组与计算机中的实际的存储空间结构是类似的，这就便于用程序设计语言对线性表进行各种运算处理。 在线性表的顺序存储结构中，可以对线性表进行各种处理。主要的运算有如下几种： （1）在线性表的指定位置处加入一个新的元素； （2）在线性表中删除指定的元素； （3）在线性表中查找某个特定的元素； （4）对线性表中的元素进行整序； （5）按要求将一个线性表分解成多个线性表； （6）按要求将多个线性表合并成一个线性表； （7）复制一个线性表； （8）逆转一个线性表等。 3.顺序表的插入运算 设长度为n的线性表为 （a1,a2,a3,a4,…,ai, …,an） 现要在线性表的第i个元素ai之前插入一个新元素b,插入后得到长度为n+1的线性表为 （a1,a2,a3,a4,…,aj,aj+1, …,an,an+1） 则插入前后的两线性表中的元素满足如下关系： a j0 实验报告 课程名称：数据结构与算法分析 实验名称：链表的实现与应用 实验日期：班级：数媒1401 姓名：范业嘉学号 08 一、实验目的 掌握线性表的链式存储结构设计与基本操作的实现。 二、实验内容与要求 ⑴定义线性表的链式存储表示； ⑵基于所设计的存储结构实现线性表的基本操作； ⑶编写一个主程序对所实现的线性表进行测试； ⑷线性表的应用：①设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用 线性表L3代表集合C；②（选做）设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中的数据元素也按值非递减有序排列。 ⑸设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④执行两个多项式相减；⑤（选做）执行两个多项式相乘。 三、数据结构设计 1.按所用指针的类型、个数、方法等的不同，又可分为： 线性链表（单链表） 静态链表 循环链表 双向链表 双向循环链表 2.用一组任意的存储单元存储线性表中数据元素，用指针来表示数据元素间的逻辑关系。 四、算法设计 1.定义一个链表 void creatlist(Linklist &L,int n) { int i; Linklist p,s; L=(Linklist)malloc(sizeof(Lnode)); p=L; L->next=NULL; for(i=0;i 重庆交通大学《算法与数据结构》课程 实验报告 班级：计算机科学与技术2014级2班 实验项目名称：线性表的顺序储存结构 实验项目性质： 实验所属课程：算法与数据结构 实验室(中心)：B01407 指导教师：鲁云平 实验完成时间：2016 年 3 月21 日 一、实验目的 1、实现线性表的顺序存储结构 2、熟悉C++程序的基本结构，掌握程序中的头文件、实现文件和主文件之 间的相互关系及各自的作用 3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现 二、实验内容及要求 对顺序存储的线性表进行一些基本操作。主要包括： （1）插入：操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入 （2）删除：操作方式可分为删除指定元素、删除指定位置的元素等，尝试实现逻辑删除操作。 （3）显示数据 （4）查找：查询指定的元素（可根据某个数据成员完成查询操作） （5）定位操作：定位指定元素的序号 （6）更新：修改指定元素的数据 （7）数据文件的读写操作等。 其它操作可根据具体需要自行补充。 要求线性表采用类的定义,数据对象的类型自行定义。 三、实验设备及软件 VC6.0 四、设计方案 ㈠题目 线性表的顺序存储结构 ㈡设计的主要思路 1、新建SeqList.h头文件，定义SeqList模板类 2、设计类数据成员，包括：T *data（用于存放数组）、int maxSize（最 大可容表项的项数）、int last（当前已存表项的最后位置） 3、设计类成员函数，主要包括： int search(T& x)const;//搜索x在表中位置，函数返回表项序号 int Locate(int i)const;//定位第i个表项，函数返回表项序号 bool getData(int i,T& x)const;//去第i个表项的值 void setData(int i,T& x)//用x修改第i个表项的值 bool Insert(int i,T& x);//插入x在第i个表项之后 bool Remove(int i,T& x); //删除第i个表项，通过x返回表项的值 bool IsEmpty();//判表空否，空则返回true；否则返回false bool IsFull();//判表满否，满则返回true；否则返回false void input(); //输入 void output();//输出 void ofile();/存储在文件中 void ifile();//读取文件并显示 ㈢主要功能 1、建立新表 2、对表进行插入（指定元素前、后以及指定位置插入）、删除（指定 元素删除及指定位置删除）、修改等操作 3、显示当前操作表的全部内容 4、存储在文件中 5、从文件中读取表 五、主要代码 ㈠SeqList.h中的主要代码： 1、类成员声明部分： protected: T *data; //存放数组 int maxSize; //最大可容纳表项的项 重庆交通大学 《算法与数据结构》课程 实验报告 班级：计算机科学与技术2014级2班 实验项目名称：线性表的顺序储存结构 实验项目性质： 实验所属课程：算法与数据结构 实验室(中心)： B01407 指导教师：鲁云平 实验完成时间：2016 年 3 月21 日 一、实验目的 1、实现线性表的顺序存储结构 2、熟悉C++程序的基本结构，掌握程序中的头文件、实现文件和主文件之间的相互关系及各自的作用 3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现 二、实验内容及要求 对顺序存储的线性表进行一些基本操作。主要包括： （1）插入：操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入 （2）删除：操作方式可分为删除指定元素、删除指定位置的元素等，尝试实现逻辑删除操作。 （3）显示数据 （4）查找：查询指定的元素（可根据某个数据成员完成查询操作）（5）定位操作：定位指定元素的序号 （6）更新：修改指定元素的数据 （7）数据文件的读写操作等。 其它操作可根据具体需要自行补充。 要求线性表采用类的定义,数据对象的类型自行定义。 三、实验设备及软件 VC6.0 四、设计方案 ㈠题目 线性表的顺序存储结构 ㈡设计的主要思路 1、新建SeqList.h头文件，定义SeqList模板类 2、设计类数据成员，包括：T *data（用于存放数组）、int maxSize（最大可容表项的项数）、int last（当前已存表项的最后位置） 3、设计类成员函数，主要包括： int search(T& x)const;//搜索x在表中位置，函数返回表项序号 int Locate(int i)const;//定位第i个表项，函数返回表项序号 bool getData(int i,T& x)const;//去第i个表项的值 void setData(int i,T& x)//用x修改第i个表项的值 bool Insert(int i,T& x);//插入x在第i个表项之后 bool Remove(int i,T& x); //删除第i个表项，通过x返回表项的值 bool IsEmpty();//判表空否，空则返回true；否则返回false bool IsFull();//判表满否，满则返回true；否则返回false void input(); //输入 void output();//输出 交通大学《算法与数据结构》课程 实验报告 班级：计算机科学与技术2014级2班 实验项目名称：线性表的顺序储存结构 实验项目性质： 实验所属课程：算法与数据结构 实验室(中心)： B01407 指导教师：鲁云平 实验完成时间：2016 年 3 月21 日 一、实验目的 1、实现线性表的顺序存储结构 2、熟悉C++程序的基本结构，掌握程序中的头文件、实现文件和主文件之 间的相互关系及各自的作用 3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现 二、实验容及要求 对顺序存储的线性表进行一些基本操作。主要包括： （1）插入：操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入 （2）删除：操作方式可分为删除指定元素、删除指定位置的元素等，尝试实现逻辑删除操作。 （3）显示数据 （4）查找：查询指定的元素（可根据某个数据成员完成查询操作） （5）定位操作：定位指定元素的序号 （6）更新：修改指定元素的数据 （7）数据文件的读写操作等。 其它操作可根据具体需要自行补充。 要求线性表采用类的定义,数据对象的类型自行定义。 三、实验设备及软件 VC6.0 四、设计方案 ㈠题目 线性表的顺序存储结构 ㈡设计的主要思路 1、新建SeqList.h头文件，定义SeqList模板类 2、设计类数据成员，包括：T *data（用于存放数组）、int maxSize （最大可容表项的项数）、int last（当前已存表项的最后位置） 3、设计类成员函数，主要包括： int search(T& x)const;//搜索x在表中位置，函数返回表项序号 int Locate(int i)const;//定位第i个表项，函数返回表项序号 bool getData(int i,T& x)const;//去第i个表项的值 void setData(int i,T& x)//用x修改第i个表项的值 bool Insert(int i,T& x);//插入x在第i个表项之后 bool Remove(int i,T& x); //删除第i个表项，通过x返回表项的值 bool IsEmpty();//判表空否，空则返回true；否则返回false bool IsFull();//判表满否，满则返回true；否则返回false void input(); //输入 void output();//输出 void ofile();/存储在文件中 void ifile();//读取文件并显示 ㈢主要功能 1、建立新表 2、对表进行插入（指定元素前、后以及指定位置插入）、删除（指定 元素删除及指定位置删除）、修改等操作 3、显示当前操作表的全部容 4、存储在文件中 5、从文件中读取表 五、主要代码 ㈠SeqList.h中的主要代码： 1、类成员声明部分： protected: T *data; //存放数组 int maxSize; //最大可容纳表项 数据结构实验线性表的链式表示和实现（源代码） #include getchar(); p->next=NULL; q->next=p; q=p; i++; } system("cls"); return head; } struct node* clearlist(node *head) { head=NULL; return head; } status destroylist(node *head) { head=NULL; free(head); return OK; } statuslistempty(node *head) { if(head==NULL) return OK; else return ERROR; } statuslistlength(node *head) { inti=0; node *p; p=head->next; while(1) { i++; if(p->next==NULL) break; p=p->next; } 石家庄经济学院 实验报告 学院: 专业: 计算机 班级: 学号: 姓名: 信息工程学院计算机实验中心制 实验题目：线性表的顺序存储结构和实现 实验室：机房4 设备编号：10 完成日期：2012年03月25号 一、实验内容 1.熟悉C 语言的上机环境，掌握C 语言的基本结构。 2.会定义线性表的顺序存储结构。 3.熟悉对顺序表的一些基本操作(建表、插入、删除等)和具体的函数定义。 二、实验目的 掌握顺序存储结构的特点，了解、掌握并实现顺序表的常用的基本算法。 三、实验的内容及完成情况 1. 需求分析 (1)线性表的抽象数据类型ADT的描述及实现。 本实验实现使用Visual c++6.0实现线性表顺序存储结构的表示及操作。具体实现要求： (2)完成对线性表顺序存储结构的表示和实现。 (3)实现对线性表的建立和初始化。 (4)实现对线性表插入和删除部分元素。 2．概要设计 抽象数据类型线性表的定义： ADT LIST{ 抽象对象：D=｛ai|ai<-Elemset,i=1,2,…,n,n>=0｝ 数据关系：R1=｛ 南昌航空大学实验报告 课程名称：数据结构实验名称：实验二线性表的链式存储结构 班级：学生姓名：冯华华学号：11046213 指导教师评定： XXX 签名: XXX 一、问题描述 1单链表的实现与操作。 2设计一个程序求出约瑟夫环的出列顺序。约瑟夫问题的一种描述是：编号为1，2，…， n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整 数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。 报m的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1 报数，如此下去，直到所有人全部出列为止。例如，n=7,7个人的密码依次为： 3,1,7,2,4,8,4,m的初值取6，则正确的出列顺序应为6,1,4,7,2,3,5。要求使用单向循环 链表模拟此出列过程。 二、程序分析 约瑟夫环的大小是变化的，因此相应的结点也是变化的，使用链式存储结构可以动态的 生成其中的结点，出列操作也非常简单。用单向循环链表模拟其出列顺序比较合适。 用结构指针描述每个人： struct Joseph {int num;/*环中某个人的序号*/ int secret;/环中某个人的密码*/ struct Joseph *next;/指向其下一个的指针*/}; 1）初始化约瑟夫环： 调用函数struct Joseph *creat()生成初始约瑟夫环。在该函数中使用head 指向 表头。输入序号为0时结束，指针p1指向的最后结束序号为0的结点没有加入到 链表中，p2 指向最后一个序号为非0 的结点（最后一个结点）。 2）报数出列： 调用函数voil sort(struct Joseph * head,int m)，使用条件p1->next!=p1判断 单向链表非空，使用两个指针变量p1和p2，语句p2=p1;p1=p1->next;移动指针， 计算结点数（报数）；结点p1出列时直接使用语句：p2->next=p1->next，取出该 结点中的密码作为新的循环终值。 三、调试过程及实验结果 最后程序运行结果如下所示： 输入数据：数据格式为序号，密码 输入0，0为结束 1，3↙<回车> 2，1↙<回车> 经济学院 实验报告 学院: 专业: 计算机 班级: 学号: 姓名: 信息工程学院计算机实验中心制 实验题目：线性表的链式存储结构和实现 实验室：机房4 设备编号： 09 完成日期： 2012.04.09 一、实验容 1.会定义线性表的链式存储结构。 2.熟悉对单链表的一些基本操作(建表、插入、删除等)和具体的函数定义。 二、实验目的 掌握链式存储结构的特点，掌握并实现单链表的常用的基本算法。 三、实验的容及完成情况 1. 需求分析 (1)线性表的抽象数据类型ADT的描述及实现。 本实验实现使用Visual c++6.0实现线性表链式存储结构的表示及操作。具体实现要求： (2)完成对线性表链式存储结构的表示和实现。 (3)实现对单链表的创建。 (4)实现对单链表的插入和删除操作。 2．概要设计 抽象数据类型线性表的定义：ADT LIST{ 抽象对象：D=｛ai|ai<-Elemset,i=1,2,…,n,n>=0｝ 数据关系：R1=｛ 1.实验目的 掌握线性表的链式存储结构设计与基本操作的实现。 2.实验内容与要求 ⑴定义线性表的链式存储表示； ⑵基于所设计的存储结构实现线性表的基本操作； ⑶编写一个主程序对所实现的线性表进行测试； ⑷线性表的应用：①设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用线性表L3代表集合C；②设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中的数据元素也按值非递减有序排列。 ⑸设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④执行两个多项式相减； 3.数据结构设计 逻辑结构：线性结构 存储结构：链式存储结构 4.算法设计 #include #include 实验报告三线性表的链式存储 班级：姓名：学号：专业： 一、实验目的： （1）掌握单链表的基本操作的实现方法。 （2）掌握循环单链表的基本操作实现。 （3）掌握两有序链表的归并操作算法。 二、实验内容：（请采用模板类及模板函数实现） 1、线性表链式存储结构及基本操作算法实现 [实现提示] （同时可参见教材p64-p73页的ADT描述及算法实现及ppt）函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。 所加载的库函数或常量定义： （1）单链表存储结构类的定义： （2）初始化带头结点空单链表构造函数实现 输入：无 前置条件：无 动作：初始化一个带头结点的空链表 输出：无 后置条件：头指针指向头结点。 （３）利用数组初始化带头结点的单链表构造函数实现 输入：已存储数据的数组及数组中元素的个数 前置条件：无 动作：利用头插或尾插法创建带头结点的单链表 输出：无 后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据成员。 （４）在带头结点单链表的第i个位置前插入元素e算法 输入：插入位置i，待插入元素e 前置条件：i的值要合法 动作：在带头结点的单链表中第i个位置之前插入元素e 输出：无 后置条件：单链表中增加了一个结点 （５）在带头结点单链表中删除第i个元素算法 输入：删除第i个结点，待存放删除结点值变量e 前置条件：单链表不空，i的值要合法 动作：在带头结点的单链表中删除第i个结点，并返回该结点的值（由e传出）。 输出：无 后置条件：单链表中减少了一个结点 （６）遍历单链表元素算法 输入：无 前置条件：单链表不空 动作：遍历输出单链表中的各元素。 输出：无 后置条件：无 （７）求单链表表长算法。 输入：无 前置条件：无 动作：求单链表中元素个数。 输出：返回元素个数 后置条件：无 （８）判单链表表空算法 输入：无 前置条件：无 动作：判表是否为空。 输出：为空时返回１，不为空时返回0 后置条件：无 （９）获得单链表中第i个结点的值算法 输入：无 前置条件：i不空，i合法 动作：找到第i个结点。 输出：返回第i个结点的元素值。 后置条件：无 (10)删除链表中所有结点算法（这里不是析构函数，但功能相同）输入：无 前置条件：单链表存在 动作：清除单链表中所有的结点。 输出：无 后置条件：头指针指向空 /////////////////////////////////////////////////////////// //--------------------------------------------------------- // 顺序存储结构线性表基本操作纯C语言实现 // // a simple example of Sq_List by C language // // by wangweinoo1[PG] //--------------------------------------------------------- /////////////////////////////////////////////////////////// #include 年南昌航空大学实验报告（用实验报告纸，手写） 课程名称：数据结构实验名称：实验一线性表的顺序存储结构 班级： 080611 学生姓名：赖凌学号： 08061101 指导教师评定：签名: 题目：有两张非递减有序的线性学生表A，B，采用顺序存储结构，两张表合并用c表存，要求C仍为非递减有序的，并删除C中值相同的表。 一、需求分析 ⒈本演示程序根据已有的6位学生的信息，实现两张表的合并及删除值相同元素的操作，不需要用户 重新输入学生的信息。 ⒉在演示过程序中，用户敲击键盘，即可观看演示结果。 ⒊程序执行的命令包括： （1）构造线性表A （2）构造线性表B （3）求两张表的并（4）删除C中值相同的元素 二、概要设计 ⒈为实现上述算法，需要线性表的抽象数据类型： ADT Stack { 数据对象：D={a i:|a i∈ElemSet,i=1…n,n≥0} 数据关系：R1={|a i-1,a i∈D,i=2,…n≥0} 基本操作: init(list *L) 操作结果：构造一个空的线性表L。 ListLength(List *L) 初始条件：线性表L已经存在 操作结果：返回L中数据元素的个数。 GetElem(List L, int i, ElemType *e) 初始条件：线性表L已经存在，1≤i≤ListLength(&L) 操作结果：用e返回L中第i个数据元素的值。 EqualList(ElemType *e1,ElemType *e2) 初始条件：数据元素e1,e2存在 操作结果：以e1,e2中的姓名项作为判定e1,e2是否相等的依据。 Less_EquaList(ElemType *e1,ElemType *e2) 初始条件：数据元素e1,e2存在 操作结果：以e1,e2中的姓名项(为字符串)的≤来判定e1,e2是否有≤的关系。 LocateElem(List *La,ElemType e,int type) 初始条件：线性表La已经存在 操作结果：判断La中是否有与e相同的元素。 第3章 线性表的链式存储结构 ● 线性表的链式存储结构 ● 线性表的应用举例 线性表顺序存储结构的特点 它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。 暴露的问题 ● 在做插入或删除元素的操作时，会产生大量的数据元素移动； ● 对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又 得不到充分的利用； ● 线性表的容量难以扩充。 第一节 线性表的链式存储结构 线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表（a,b,c,d ），可用下图所示的形式存储： 存储地址 内容 直接后继存储地 址 100 (120) ... 144 ... 160 ... 术语 表示每个数据元素的两部分信息组合在一起被称为结点； 其中表示数据元素内容的部分被称为数据域（data ）； 表示直接后继元素存储地址的部分被称为指针或指针域（next ）。 单链表简化的图形描述形式 其中，head 是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值NULL 。NULL 值 首元素位置 在图示中常用（^）符号表示。 带头结点的单链表 为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为头结点。这样可以免去对链表第一个结点的特殊处理。如下图所示： 链式存储结构的特点 （1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致； （2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。 在C语言中，实现线性表的链式存储结构的类型定义 typedef strcut node{ //结点类型 EntryType item; struct node *next; }NODE; typedef struct{ //链表类型 NODE *head; }LINK_LIST; 典型操作的算法实现 （1）初始化链表L int InitList(LINK_LIST *L) { L->head=(*NODE)malloc(sizeof(NODE)); //为头结点分配存储单元 if (L->head) {L->head->next=NULL; return OK;} else return ERROR ; } （2）销毁链表L void DestoryList(LINK_LIST *L) { NODE *p; while (L->head){ //依次删除链表中的所有结点 p=L->head; L->head=L->head->next; free(p); } } （3）清空链表L void ClearList(LINK_LIST *L) { NODE *p; while (L->head->next){ 线性表顺序存储结构插入，删除 (数据结构) 一、实验目的 1.掌握顺序存储结构的特点。 2.掌握顺序存储结构的常见算法。 3.实现顺序表的插入，删除等操作。 二、实验要求 1、用vs6.0 进行线性表程序的编写，用c语言程序开发 三、实验内容 1、定义常量，变量等 2、定义主函数main 3、定义调用函数void Initlist(Sqlist &L)，void Creatlist(Sqlist &L)，void Insertlist(Sqlist &L,int j,int e)，void Deletelist(Sqlist &L,int j) #include int i; scanf("%d\n",&L.length); for(i=0;i线性表顺序存储结构上的基本运算
线性表的链式表示与实现
3线性表及其顺序存储结构
线性表的链式存储结构实验报告
线性表的顺序储存结构
线性表的顺序储存结构
线性表的顺序储存结构
(数据结构)线性表的链式表示和实现(源代码)
线性表的顺序存储结构和实现
实验二 线性表的链式存储结构
线性表的链式存储结构和实现
数据结构线性表的链式存储结构
线性表顺序存储实现、插入、删除操作
实验3 线性表的链式存储
顺序存储结构线性表基本操作 纯C语言实现
线性表的顺序存储结构_实验报告样例
第三章 线性表的链式存储结构教案
线性表顺序存储结构插入-删除 (1)