线性表的链式存储结构
线性表的链式存储结构
线性表的链式存储结构示意图存储结构：
#include
using namespace std;
template
struct node{
T ele;
node *next;
};
实现线性表的各个函数：template
reacl::reacl()
{
L = new node;
length = 0;
L->next = NULL;
}
template
reacl::~reacl()
{
delete L;
}
template
int reacl::getLength()
{
return length;
}
template
T reacl::getEle(int x)
{
node *p = L;
for (int i = 0; i < x && (p->next != NULL); i++) p = p->next;
return p->ele;
}
template
void reacl::getList(T t)
{
node *p = L;
int i = 0, temp = 0;
while (p->next != NULL)
{
if (p->ele == t)
{
temp = 1;
cout << "位置：" << i << endl; break;
}
i++;
p = p->next;
}
if (temp == 0) cout << "没有" << endl; }
template
void reacl::insertl(T t, int x)
{
node *datal = new node;
node *p = L;
datal->next = NULL;
datal->ele = t;
for (int i = 0; inext != NULL); i++) p = p->next;
datal->next = p->next;
p->next = datal;
length++;
}
template
void reacl::deletel(int x)
{
node *temp = new node; node *p = L;
for (int i = 0; i
p = p->next;
temp = p->next;
p->next = temp->next; length--;
}
template
void reacl::displayl()
{
node *p = L;
while (p->next != NULL) {
p = p->next;
cout << p->ele << " ";
}
}
main函数：
int main()
{
reacl newl;
for (int i = 0; i < 30; i++) //初始线性表
{
newl.insertl(i, i);
}
cout << "线性表长：" << newl.getLength() << endl; newl.displayl();
cout << "得到值是：" << newl.getEle(10) << endl;; newl.getList(25);
newl.insertl(100, 20); //插入
newl.displayl();
cout << "线性表长：" << newl.getLength() << endl; newl.deletel(21); //删除
newl.displayl();
cout << "线性表长：" << newl.getLength() << endl; system("pause");
return 0;
}
运行结果：
填写图片摘要（选填）程序可执行代码：
#include
using namespace std;
template
struct node{
T ele;
node *next;
template
class reacl{
public:
reacl(); //析构函数
~reacl(); //构造函数
int getLength(); //得到线性表的表长
T getEle(int); //得到某个位置的节点值void getList(T); //得到所在的位置void insertl(T, int); //插入
void deletel(int); //删除
void displayl(); //打印输出
private:
node *L;
int length;
template reacl::reacl()
{
L = new node; length = 0;
L->next = NULL;
}
template reacl::~reacl()
{
delete L;
}
template
int reacl::getLength()
return length;
}
template
T reacl::getEle(int x)
{
node *p = L;
for (int i = 0; i < x && (p->next != NULL); i++) p = p->next;
return p->ele;
}
template
void reacl::getList(T t)
{
node *p = L;
int i = 0, temp = 0;
while (p->next != NULL)
{
if (p->ele == t)
{
temp = 1;
cout << "位置：" << i << endl; break;
}
i++;
p = p->next;
}
if (temp == 0) cout << "没有" << endl; }
template
void reacl::insertl(T t, int x)
{
node *datal = new node;
node *p = L;
datal->next = NULL;
datal->ele = t;
for (int i = 0; inext != NULL); i++) p = p->next;
datal->next = p->next;
p->next = datal;
length++;
}
template
void reacl::deletel(int x)
{
node *temp = new node; node *p = L;
for (int i = 0; i
p = p->next;
temp = p->next;
p->next = temp->next; length--;
}
template
void reacl::displayl() {
node *p = L;
while (p->next != NULL) {
p = p->next;
cout << p->ele << " ";
}
}
int main()
{
reacl newl;
for (int i = 0; i < 30; i++) //初始线性表
{
newl.insertl(i, i);
}
cout << "线性表长：" << newl.getLength() << endl; newl.displayl();
cout << "得到值是：" << newl.getEle(10) << endl;; newl.getList(25);
newl.insertl(100, 20); //插入
newl.displayl();
cout << "线性表长：" << newl.getLength() << endl; newl.deletel(21); //删除
newl.displayl();
cout << "线性表长：" << newl.getLength() << endl; system("pause");
return 0;
}
欢迎访问我的博客：https://www.wendangku.net/doc/ee14597488.html,/u/5066584704
顺序存储结构和链式存储结构
第二次作业 1. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 2 .描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？ 3.已知P结点是双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。 a．在P结点后插入S结点的语句序列是-----------。 b．在P结点前插入S结点的语句序列是-----------。 c．删除P结点的直接后继结点的语句序列是----------。 d．删除P结点的直接前驱结点的语句序列是----------。 e．删除P结点的语句序列是------------。 (1)P->next=P->next->next; (10) P->prior->next=P; (2)P->prior=P->prior->prior; (11) P->next->prior =P; (3) P->next=S; (12)P->next->prior=S; (4) P->prior=S; (13) P->prior->next=S; (5)S->next=P; (14) P->next->prior=P->prior (6)S->prior=P; (15)Q=P->next; (7) S->next= P->next; (16)Q= P->prior; (8) S->prior= P->prior; (17)free(P); (9) P->prior->next=p->next; (18)free(Q); 4. 编写程序，将若干整数从键盘输入，以单链表形式存储起来，然后计算单链表中结点的个数（其中指针P指向该链表的第一个结点）。
线性表实验报告：针对链式或顺序存储的线性表实现指定的操作(二份)
、格式已经给出，请同学们参考书写。其中，第一项可补充，第二、三项不修改，第四项为可选项，第六项为参考程序，第五、七、八项需自己上机调试程序书写。注意：红色字体为提示内容，大家不要往实验报告上抄。 实验一:线性表的顺序存储结构的表示和实验 ——学生成绩管 理系统 一、实验目的：通过上机调试程序，充分理解和掌握有关线性表的定义、实现及操作。 二、实验环境 Win2003/win xp +Visual C++ 三、基本要求：利用顺序表来制作一个学生成绩表 1、建立头文件，包含数据类型定义和基本操作。 2、建立程序文件利用顺序表表完成一个班级的一个学期的所有课程的管理：能够增加、删除、修改学生的成绩记录。 四、简要的需求分析与概要设计（本项为可选项，选作时参考课
五、详细的算法描述： 六、实验步骤（以下为参考程序，已经调试运行通过）#include
char name[20]; int english; int math; }; typedef student elemtype; struct sqlist { elemtype *elem; int length; int listsize; int incrementsize; }; //初始化顺序表l void initlist(sqlist &l,int maxsize=LISTINITSIZE,int incresize=LISTINCREMENT) { l.elem=new elemtype[maxsize]; l.length=0; l.listsize=maxsize; l.incrementsize=incresize;
线性表的链式表示与实现
浙江大学城市学院实验报告 课程名称数据结构基础 实验项目名称实验五线性表的链式表示和实现 学生姓名吴奇专业班级信管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<<"储存分配失败，按任意键退出系统!!"<
线性表的链式存储结构实验报告
实验报告 课程名称：数据结构与算法分析 实验名称：链表的实现与应用 实验日期：班级：数媒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
四种基本的存储结构
数据的四种基本存储方法 数据的存储结构可用以下四种基本存储方法得到： （1）顺序存储方法 ???该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。 ???由此得到的存储表示称为顺序存储结构（SequentialStorageStructure），通常借助程序语言的数组描述。 该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。 （2）链接存储方法 ???该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（LinkedStorageStructure）,通常借助于程序语言的指针类型描述。 （3）索引存储方法 ???该方法通常在储存结点信息的同时，还建立附加的索引表。 ???索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（DenseIndex）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引(SpareIndex)。索引项的一般形式是：
????????????????????(关键字、地址) 关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。（4）散列存储方法 ???该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。 四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。 同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。 数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。孤立地去理解一个方面，而不注意它们之间的联系是不可取的。 存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。 【例】线性表是一种逻辑结构，若采用顺序方法的存储表示，可称其为顺序表；若采用链式存储方法，则可称其为链表；若采用散列存储方法，则可称为散列表。
线性表的顺序储存结构
重庆交通大学 《算法与数据结构》课程 实验报告 班级：计算机科学与技术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();//输出
(数据结构)线性表的链式表示和实现(源代码)
数据结构实验线性表的链式表示和实现（源代码） #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; }
实验二 线性表的链式存储结构
南昌航空大学实验报告 课程名称：数据结构实验名称：实验二线性表的链式存储结构 班级：学生姓名：冯华华学号：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↙<回车>
数据结构实验报告 实验一 线性表链式存储运算的算法实现
昆明理工大学信息工程与自动化学院学生实验报告 （201 —201 学年第一学期） 课程名称：数据结构开课实验室：年月日年级、专业、班学号姓名成绩 实验项目名称线性表链式存储运算的算法实现指导教师 教 师 评语教师签名： 年月日 一.实验内容： 线性表链式存储运算的算法实现，实现链表的建立、链表的数据插入、链表的数据删除、链表的数据输出。 二.实验目的： 1.掌握线性表链式存储结构的C语言描述及运算算法的实现； 2.分析算法的空间复杂度和插入和删除的时间复杂度； 3.总结比较线性表顺序存储存储与链式存储的各自特点。 三.主要程序代码分析： LinkList creatListR1() //用尾插入法建立带头结点的单链表 { char *ch=new char(); LinkList head=(LinkList)malloc(sizeof(ListNode)); //生成头结点*head ListNode *s,*r,*pp; r=head; //尾指针初值指向头结点 r->next=NULL; scanf("%s",ch); //读入第一个结点的值 while(strcmp(ch,"#")!=0) { //输入#结束
pp=LocateNode(head,ch); if(pp==NULL) { s=(ListNode *)malloc(sizeof(ListNode)); //生成新的结点*s strcpy(s->data,ch); r->next=s; //新结点插入表尾 r=s; //尾指针r指向新的表尾 r->next=NULL; } scanf("%s",ch); //读入下一个结点的值 } return head; //返回表头指针 } int Insert(ListNode *head) //链表的插入 { ListNode *in,*p,*q; int wh; in=(ListNode *)malloc(sizeof(ListNode));in->next=NULL; //生成新结点p=(ListNode *)malloc(sizeof(ListNode));p->next=NULL; q=(ListNode *)malloc(sizeof(ListNode));q->next=NULL; scanf("%s",in->data); //输入插入的数据 scanf("%d",&wh); //输入插入数据的位置 for(p=head;wh>0;p=p->next,wh--); q=p->next; p->next=in; in->next=q; } void DeleteList(LinkList head,char *key) //链表的删除 { ListNode *p,*r,*q=head; p=LocateNode(head,key); //按key值查找结点的 if(p==NULL) exit(0); //若没有找到结点，退出 while(q->next!=p) //p为要删除的结点，q为p的前结点q=q->next; r=q->next; q->next=r->next; free(r); //释放结点*r } 四.程序运行结果：
线性表的链式存储结构和实现
经济学院 实验报告 学院: 专业: 计算机 班级: 学号: 姓名: 信息工程学院计算机实验中心制
实验题目：线性表的链式存储结构和实现 实验室：机房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 实验报告 题目：完成线性表ADT的顺序存储和链式存储方式的实现 一、需求分析 1、本演示程序中，线性表的数据元素类型限定为整型 2、演示程序以用户和计算机的对话方式执行，即在计算机的终端上显示“提 示信息”之后由用户在键盘上键入演示程序规定的运算命令，相应的输出 结果显示在后面。 3、程序的执行命令包括： 创建、撤销、清空、插入、修改、删除、定位等线性表ADT各项基本操作二、概要设计 为实现上述功能，我们给出线性表的抽象数据类型定义，具体的有单向链，双向 链，顺序表等，同时对于上述功能的实现还采用有/无头结点两种方式来实现 1.线性表的抽象数据类型定义为 ADT List{ 数据对象：D={a i|a i∈ElemSet，i=1,2,…,n,n≥0} 数据关系：R1={|ai-1,ai∈D，i=2,…,n} 基本操作： InitList(&L) 操作结果：构造一个空的线性表L DestroyList(&L) 初始条件：线性表L已存在。 操作结果：销毁线性表L。 ClearList(&L) 初始条件：线性表L已存在。 操作结果：将L重置为空表。 ListEmpty(L) 初始条件：线性表L已存在。 操作结果：若L为空表，则返回TRUE，否则返回FALSE。 ListLength(L) 初始条件：线性表L已存在。 操作结果：返回L中的i个数据元素的值。 GetElem(L,i,&e) 初始条件:线性表L已存在，1≤i≤ListLength（L）。 操作结果：用e返回L中第i个数据元素的值。 LocateElem（L,e,compare()） 初始条件：线性表L已存在，compare()是数据元素判定函数 操作结果：返回L中第一个与e满足compare()的数据元素的位序。 若这样的数据元素不存在，则返回值为0. PriorElem（L,cur_e,&pre_e） 初始条件：线性表已存在 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。 实验报告三线性表的链式存储 班级：姓名：学号：专业： 一、实验目的： （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)删除链表中所有结点算法（这里不是析构函数，但功能相同）输入：无 前置条件：单链表存在 动作：清除单链表中所有的结点。 输出：无 后置条件：头指针指向空 实验1 线性表的基本操作 一、需求分析 目的： 掌握线性表运算与存储概念，并对线性表进行基本操作。 1.初始化线性表； 2.向链表中特定位置插入数据； 3.删除链表中特定的数据； 4.查找链表中的容； 5.销毁单链表释放空间； 二、概要设计 ●基础题 主要函数： 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 实验步骤： 1，初始化顺序表 2，调用插入函数 3，在顺序表中查找指定的元素 4，在顺序表中删除指定的元素 5，在顺序表中删除指定位置的元素 6，遍历并输出顺序表 ●提高题 要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素 方法： 按顺序取出元素并与x、y比较，若小于x且大于y，则存进新表中。 编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。 方法： 分别按顺序取出L1，L2的元素并进行比较，若相等则将L1元素放进L中，否则将L 1，L2元素按顺序放进L。 本程序主要包含7个函数 主函数main() 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计 初始化线性表InitList（List* L，int ms） void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE; 年南昌航空大学实验报告（用实验报告纸，手写） 课程名称：数据结构实验名称：实验一线性表的顺序存储结构 班级： 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相同的元素。 1、试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 答：① 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用 存储单元的地址必须是连续的。 优点：存储密度大（＝1），存储空间利用率高。缺点：插入或删除元素时不方便。 ②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值， 另一部分存放表示结点间关系的指针 优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表； 若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。 顺序表与链表的比较 基于空间的比较 存储分配的方式 顺序表的存储空间是静态分配的 链表的存储空间是动态分配的 存储密度= 结点数据本身所占的存储量/结点结构所占的存储总量 顺序表的存储密度= 1 链表的存储密度< 1 基于时间的比较 存取方式 顺序表可以随机存取，也可以顺序存取 链表是顺序存取的 插入/删除时移动元素个数 顺序表平均需要移动近一半元素 链表不需要移动元素，只需要修改指针 顺序表和链表的比较顺序表和链表各有短长。在实际应用中究竟选用哪一种存储结构呢？这要根据具体问题的要求和性质来决定。通常有以下几方面的考虑：┌───┬───────────────┬───────────────┐││ 顺序表│链表│├─┬─┼───────────────┼───────────────┤│基│分│静态分配。程序执行之前必须明确│动态分配只要内存空间尚有空闲，││于│配│规定存储规模。若线性表长度n变│就不会产生溢出。因此，当线性表││空│方│化较大，则存储规模难于预先确定│的长度变化较大，难以估计其存储││间│式│估计过大将造成空间浪费，估计太│规模时，以采用动态链表作为存储││考││小又将使空间溢出机会增多。│结构为好。 ││虑├─┼───────────────┼───────────────┤││存│为1。当线性表的长 #include "stdio.h" //standard input output的缩写即标准输入输出,它封装了标准输入输出等一些常用函数 #include "stdlib.h" //里面包含有一些通用的工具函数,此程序主要用到了它里面包含的system("cls"),system("cls")和exit()函数 #include "string.h" //里面包含有一些常用的字符串函数,此程序主要用到了它里面包含的strcmp()和strcpy()函数 typedef struct LNode{ int ID; //序号为整型 char name[20]; //姓名为字符型数组 char age[10]; //年龄为字符型数组 struct LNode *next; //struct LNode的直接后继指针 }LNode, *LinkList; //LNode为结构体名,*LinkList为指针型结构体名 int AgeJudge(char ch1[10]){ //输入的ch1必须为大于0的整数 char ch2[10]; //定义ch2字符型数组存放一个整型数据 int a; //用于保存ch1转换为整型的数据 while(1){ //无限循环使用户可以无限输入直到输入正确 scanf("%s",ch1); //输入ch1 a=atoi(ch1); //将ch1转换为整型 itoa(a,ch2,10); //将ch1转换为整型后的数据再存放到ch2当中 if(strcmp(ch1,ch2)==0&&a>0){break;} //当输入的数据为大于0的整数时跳出死循环 else{printf("请输入一个人大于0的整数: ");} //输入数据有误 } return a; //返回输入的大于0的整数 }//AgeJudge void CreateList_L(LinkList &L, int n){ //顺位序输入n个元素的值,建立带表头节点的单链线性表L int i; //用作循环变量 LinkList p,s,p1; //p为第一个节点的结构体指针,s为第一个以后节点的结构体指针,p1为临时结构体指针 L=(LinkList)malloc(sizeof(LNode)); //生成头结点 if(!L){printf("空间申请失败!");} //生成头结点失败 L->next=NULL; //先建立一个带头结点的空的单链表 for(i=0;i 贵州大学实验报告 学院：计算机科学与信息学院专业：信息安全班级： chaintable *Buildtable(int x[],int y) { chaintable *p,*head; p=new chaintable; head=p; p->data=x[0]; for(int i=1;i delete relief; return true; } else return false; } } bool Inserttable(chaintable *&head,int x,int y) { if(y<0) return false; chaintable *p=head,*t=new chaintable; t->data=x; t->next=NULL; if(y==0) { t->next=head; head=t; return true; } else { for(int i=0;i 实验一线性表的链式存储 【实验时间】 【实验地点】 【实验目的和要求】 1．掌握线性表的结构特点和表示方法； 2．掌握线性表链式存储结构特性和基本操作算法； 3．掌握用指针实现单链表的建立、输出、插入和删除的算法。 【实验类型】验证性 【实验时数】2学时 【实验设备】计算机 【参考资料】 1．数据结构题解 2．C程序设计 【实验内容】 熟练掌握线性表的链式表示和实现方法，利用其定义具体的链表结点；利用链表的结构特点，建立单链表；利用链表结点间的指针关系，实现链表的插入和删除。 [具体要求] (1) 建立单链表时，要首先输入链表长度，根据输入值来确定所建链表的结点个数； (2) 在单链表中插入新结点时，要给出结点的插入位置和数据域的值； (3) 在单链表中删除某个结点时，要给出要删结点的位置； (4) 要编写单链表的输出函数，以便能验证程序的执行结果。 【实验分析】 1、实验的第一步应该建立单链表结点类型和程序所需的宏或数据类型，例如： #define NULL 0 //宏定义NULL的值为0 #define LEN sizeof(struct node) //宏定义LEN，为申请结点空间时做准备 typedef struct { int a; float b; } elemtype; //定义elemtype类型，这里同学们可以根据自己的情况来自行定义。 typedef struct node {elemtype data; //data域为elemtype类型的，它应该包含两个子域：a和b struct node *next; }NODE , *NODEPTR; //定义了单链表结点类型和单链表结点指针类型 2、对单链表的四种操作进行实现。 (1) NODEPTR creatlink() 建立单链表的函数 很明显这个函数的返回值时结点指针类型的，所以这个函数应该返回的时建立的单链表的头指针。同学们可以根据自己的构思，从前往后或从后往前建立单链表。此外，提醒同学们最好建立带有附加头结点的单链表。 (2)void print(NODEPTR Lh) 输出单链表的函数 这个函数主要是将单链表中各结点的数据域的信息输出出来，输出数据的格式要根据同学们对于链表结点的data域所属的elemtype类型来设定。 (3) void del(NODEPTR Lh,int i) 删除结点的函数 这个函数完成的是在链表Lh中删除指定位置i的结点。i的值是在执行删除操作之前通过键盘输入的。 (4) void insert (NODEPTR Lh, int i) 插入结点的函数 这个函数完成的是在链表Lh中在指定位置i的结点前或后面插入新建结点。i的值是在执行插入操作之前通过键盘输入的。同学们可以根据自己的情况选择是在结点前面插入还是在后面插入。 3、第二步应该构思程序主界面。 本实验要求实验单链表的建立、输出、插入和删除四种具体操作，因此可以主界面中可以给出相应的这四种操作的标题，用户在运行时可以根据自己的需要来选择要进行的操作，形式可以如下： ************************ Creat: 1 Print: 2 Delete: 3 Insert: 4 Esc: 0 ************************ please input your choice (0-4):数据结构线性表的链式存储结构
线性表ADT的顺序存储与链式存储实验报告
实验3 线性表的链式存储
数据结构_实验1_线性表的基本操作
线性表的顺序存储结构_实验报告样例
比较顺序存储结构和链式存储结构 (1)
线性表的链式存储结构完整版-数据结构版
线性表的链式存储结构实验报告
实验一 线性表的链式存储 (1)