当前位置：文档之家› 实验目的：掌握线性表的基本操作：插入、删除、查找在链式存储结构上的实现。

实验目的：掌握线性表的基本操作：插入、删除、查找在链式存储结构上的实现。

洛阳理工学院实验报告

附：源程序：

#include

#include typedef int ElemType;

typedef struct Node {ElemType data; struct Node *next;

}Node ,*LinkList;

InitList(LinkList *L)

{*L=(LinkList)malloc(sizeof(Node)); (*L)->next=NULL;

}

int CreateFromTail(LinkList L)

{ Node *r,*s;

int flag=1;int c;

r=L;

while(flag)

{

scanf("%d",&c);

if(c!=-1)

{s=(Node*)malloc(sizeof(Node));

s->data=c;

r->next=s;

r=s;

}

else

{

flag=0;

r->next=NULL;

}

int output(LinkList L)

{Node *p;

p=L->next;

while(p!=NULL)

{

printf("%4d",p->data);

p=p->next;

}

printf("\n");

}

void Locate(LinkList L,ElemType key)

{Node *p;

int i=1;

p=L->next;

while(p!=NULL)

if(p->data!=key)

{p=p->next;

i++;

}

else

break;

if(p==NULL)

printf("输入查找值不合理\n");

else

printf("查找值位于链表第%d个位置\n",i); }

void insertandsort(LinkList L,ElemType e)

{Node *p,*s,*m,*n;

int i;

p=L;

while(p->next!=NULL)

p=p->next;

s=(Node *)malloc(sizeof(Node));

s->data=e;p->next=s;

s->next=NULL;

for(m=L->next;m!=NULL;m=m->next) {

for(n=m->next;n!=NULL;n=n->next)

{ if(m->data>n->data)

{i=n->data;

n->data=m->data;

m->data=i;

}

printf("插入、排序完成.\n");

}

void DelList(LinkList L,int i)

{

Node *pre,*r;

int k;

pre=L;k=0;

while(pre->next!=NULL&&k

{ pre=pre->next;

k=k+1;

}

if(!(pre->next))

{

printf("删除节点的位置i不合理！");

}

r=pre->next;

pre->next=r->next;

free(r);

}

void main ()

{int flag=1;

ElemType x,z;

int choice,i;

LinkList L;

printf("请输入单链表中数据元素，并以“-1”为结束标记:\n"); InitList(&L);

CreateFromTail(L);

printf("可以执行的操作选项序号.\n");

printf("1.输出表中所有元素的值.\n");

printf("2.查找值为x的元素.\n");

printf("3.插入值为x的元素并保持有序.\n");

printf("4.删除第i个元素.\n");

printf("5.退出.\n");

while(flag)

{

printf("请输入需要进行的的操作选项序号:");

scanf("%d",&choice);

switch(choice)

{

case 1: output(L);break;

case 2:

printf("请输入要查找的值：");

scanf("%d",&x);

Locate(L,x);

break;

case 3:

printf("请输入要插入的值：");

scanf("%d",&z);

insertandsort(L,z);

break;

case 4:

printf("请输入要删除位置i：");

scanf("%d",&i);

DelList(L,i);

printf("删除成功\n");

break;

case 5:flag=0;break;

}

线性表实验报告：针对链式或顺序存储的线性表实现指定的操作(二份)

、格式已经给出，请同学们参考书写。其中，第一项可补充，第二、三项不修改，第四项为可选项，第六项为参考程序，第五、七、八项需自己上机调试程序书写。注意：红色字体为提示内容，大家不要往实验报告上抄。实验一:线性表的顺序存储结构的表示和实验 ——学生成绩管理系统一、实验目的：通过上机调试程序，充分理解和掌握有关线性表的定义、实现及操作。二、实验环境 Win2003/win xp +Visual C++ 三、基本要求：利用顺序表来制作一个学生成绩表 1、建立头文件，包含数据类型定义和基本操作。 2、建立程序文件利用顺序表表完成一个班级的一个学期的所有课程的管理：能够增加、删除、修改学生的成绩记录。四、简要的需求分析与概要设计（本项为可选项，选作时参考课

五、详细的算法描述：六、实验步骤（以下为参考程序，已经调试运行通过）#include #include using namespace std; const int LISTINITSIZE=100; const int LISTINCREMENT=10; struct student { char no[20];

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;

实验二链表操作实现

实验二链表操作实现实验日期： 2017 年 3 月 16 日实验目的及要求 1. 熟练掌握线性表的基本操作在链式存储上的实现； 2. 以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点； 3. 掌握线性表的链式存储结构的定义和基本操作的实现； 4. 通过本实验加深对C语言的使用（特别是函数的参数调用、指针类型的应用）。实验容已知程序文件linklist.cpp已给出学生身高信息链表的类型定义和基本运算函数定义。（1）链表类型定义 typedef struct { int xh; /*学号*/ float sg; /*身高*/ int sex; /*性别，0为男生，1为女生*/ } datatype; typedef struct node{ datatype data; /*数据域*/ struct node *next; /*指针域*/ } LinkNode, *LinkList; （2）带头结点的单链表的基本运算函数原型 LinkList initList();/*置一个空表（带头结点）*/ void createList_1(LinkList head);/*创建单链表*/ void createList_2(LinkList head);/* 创建单链表*/ void sort_xh(LinkList head);/*单链表排序*/ void reverse(LinkList head);/*对单链表进行结点倒置*/ void Error(char *s);/*自定义错误处理函数*/ void pntList(LinkList head);/*打印单链表*/ void save(LinkList head,char strname[]);/*保存单链表到文件*/

3线性表及其顺序存储结构

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

实验二单链表基本操作技巧

实验二单链表基本操作一实验目的 1.学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。 2.掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。二实验要求 1．预习C语言中结构体的定义与基本操作方法。 2．对单链表的每个基本操作用单独的函数实现。 3．编写完整程序完成下面的实验内容并上机运行。 4．整理并上交实验报告。三实验内容 1．编写程序完成单链表的下列基本操作： (1)初始化单链表La。 (2)在La中第i个元素之前插入一个新结点。 (3)删除La中的第i个元素结点。 (4)在La中查找某结点并返回其位置。 (5)打印输出La中的结点元素值。 2 .构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、 Lb合并成一个有序单链表Lc。合并思想是：程序需要3个指针：pa、pb、pc，其中pa，pb分别指向La表与Lb表中当前待比较插入的结点，pc 指向Lc表中当前最后一个结点。依次扫描La和Lb中的元素，比较当前元素的值，将较小者链接到*pc 之后，如此重复直到La或Lb结束为止，再将另一个链表余下的内容链接到pc所指的结点之后。 3．构造一个单链表L，其头结点指针为head，编写程序实现将L逆置。（即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。）四思考与提高 1．如果上面实验内容2中合并的表内不允许有重复的数据该如何操作？ 2．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？

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

实验报告课程名称：数据结构与算法分析实验名称：链表的实现与应用实验日期：班级：数媒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;idata); s->next=NULL; p->next=s; p=s; }

线性表的顺序储存结构

重庆交通大学《算法与数据结构》课程实验报告班级：计算机科学与技术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();//输出

实验二单链表的基本算法

实验二单链表的基本算法一．实验目的：通过上机编程掌握 1．生成单链表的基本算法； 2．在单链表上的插入、删除运算。二．实验要求： 1. 给出程序设计的基本思想、原理和算法描述。 2. 画出程序流程图；根据数据结构有关知识编出算法程序； 3. 源程序给出注释； 4. 保存和打印出程序的运行结果，并结合程序进行分析。三．实验内容： 1.编写函数实现单链表的基本运算： (1)单链表的生成 (2)单链表的插入 (3)单链表的删除 2.编写主函数测试单链表的各种基本运算： (1)生成一个至少包含有5个元素的单链表,元素值由计算机输入 (2)在表中的第5个位置上插入元素”7” (3)删除表中的第6个元素 (4)显示(1)—(3)每一步的操作结果

实验原理：首先建立头结点，形成一个单链表，通过malloc函数创建新的结点单元，将要读取的数据赋值给新结点。其次插入链表，从头结点开始依次延指针域查找需要插入的结点，为插入数据元素x生成一个新结点s，将x插入在s和s-1之间。最后链表结点删除，找到指定结点的前趋结点通过改变连接完成删除。源程序： #include #include typedef int datatype; typedef struct node/*结构体更名为NODE*/ { datatype data; struct node *next; }NODE; NODE *creatlink() /*建立带头结点的单链表*/ { NODE *head,*s ,*p; int x; head=(NODE*)malloc(sizeof(NODE)); /*生成一个NODE型新结点并赋值给head*/ p=head; scanf("%d",&x); while(x!=0) { s=(NODE*)malloc(sizeof(NODE)); /*生成一个NODE型新结点并赋值给s*/

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

南昌航空大学实验报告课程名称：数据结构实验名称：实验二线性表的链式存储结构班级：学生姓名：冯华华学号：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 #include #include typedef struct LNode { int data; struct LNode *next; }LNode; typedef struct Pnode { float coef; int exp; struct Pnode *next; }Polynode; void menu() { printf("******************************* **************\n"); printf("* 作者：Dick *\n"); printf("* 信计1001 xxxxxxxxxx *\n"); printf("*********************MENU**** ***************\n"); printf("1 求A和B的并集C\n"); printf("2 对A和B进行合并,用线性表C保存合并结果(有序)\n"); printf("3 建立一元多项式(两个)\n"); printf("4 两个一元多项式相加\n"); printf("5 两个一元多项式相减\n"); printf("6 退出程序\n"); } void UnionList() { //先输入两个链表，然后判断是否为空，头结点还是要的。 int i; LNode *List1,*List2,*List3,*p,*q,*r; List1 = (LNode *)malloc( sizeof(LNode) ); List2 = (LNode *)malloc( sizeof(LNode) ); List3 = (LNode *)malloc( sizeof(LNode) ); List1->next = List2->next = List3->next = NULL; printf("请输入第一个链表的数据(1~100),以0结束\n"); p = q = r = (LNode *)malloc( sizeof(LNode) ); while(1)