实验1_链表的操作实验
实验B01: 链表的操作实验
一、实验名称和性质
二、实验目的
1．掌握线性表的链式存储结构的表示和实现方法。
2．掌握链表基本操作的算法实现。
三、实验内容
1．建立单链表，并在单链表上实现插入、删除和查找操作（验证性内容）。
2．建立双向链表，并在双向链表上实现插入、删除和查找操作（设计性内容）。
3．计算已知一个单链表中数据域值为一个指定值x的结点个数（应用性设计内容）。
四、实验的软硬件环境要求
硬件环境要求：
PC机（单机）
使用的软件名称、版本号以及模块：
Windows环境下的TurboC2.0以上或VC++ 等。
五、知识准备
前期要求熟练掌握了C语言的编程规则、方法和单链表和双向链表的基本操作算法。
六、验证性实验
1．实验要求
编程实现如下功能：
（1）根据输入的一系列整数，以0标志结束，用头插法建立单链表，并输出单链表中各元素值，观察输入的内容与输出的内容是否一致。
（2）在单链表的第i个元素之前插入一个值为x的元素，并输出插入后的单链表中各元素值。
（3）删除单链表中第i个元素，并输出删除后的单链表中各元素值。
（4）在单链表中查找第i个元素，如果查找成功，则显示该元素的值，否则显示该元素不存在。
2. 实验相关原理：
线性表的链式储结构是用一组任意的存储单元依次存放线性表中的元素，这组存储单元可以是连续的，也可以是不连续的。为反映出各元素在线性表中的前后逻辑关系，对每个数据元素来说，除了存储其本身数据值之外，还需增加一个或多个指针域，每个指针域的值称为指针，又称作链，它用来指示它在线性表中的前驱或后继的存储地址。这两个部分的的一起组成一个数据元素的存储映像，称为结点，若干个结点链接成链表。如果一个结点中只含
一个指针的链表，则称单链表。单链表的存储结构描述如下：
typedefstructLnode{
Elemtype data;/*数据域*/
structLnode *next;/*指针域*/
}LNODE,*Linklist; /*其中LNODE为结点类型名，Linklist为指向结点的指针类型名*/
【核心算法提示】
1．链表建立操作的基本步骤：链表是一个动态的结构，它不需要予分配空间，因此建立链表的过程是一个结点“逐个插入”的过程。先建立一个只含头结点的空单链表，然后依次生成新结点，再不断地将其插入到链表的头部或尾部，分别称其为“头插法”和“尾插法”。
2．链表查找操作的基本步骤：因链表是一种"顺序存取"的结构，则要在带头结点的链表中查找到第i个元素，必须从头结点开始沿着后继指针依次"点数"，直到点到第i个结点为止,如果查找成功，则用e返回第i个元素值。头结点可看成是第0个结点。
3．链表插入操作的基本步骤：先确定要插入的位置，如果插入位置合法，则再生成新的结点，最后通过修改链将新结点插入到指定的位置上。
4．链表删除操作的基本步骤：先确定要删除的结点位置，如果位置合法，则再通过修改链使被删结点从链表中“卸下”，最后释放被删结点的空间。
【核心算法描述】
void creat1(Linklist&L) /*输入一系列整数，以0标志结束，将这些整数作为data域并用头插
法建立一个带头结点的单链表的函数*/
{ L=(Linklist)malloc(sizeof(LNODE));/*生成头结点*/
L->next=NULL;/*头结点的指针域初始为空*/
scanf("%d",&node);
while(node!=0)
{p=(Linklist)malloc(sizeof(LNODE));/*为一个新结点的分配空间*/
p->data=node; /*为新结点数据域赋值*/
p->next=L->next;/*新结点指针域指向开始结点*/
L->next=p; /*头结点指针域指向新结点，即新结点成为开始结点*/
scanf("%d",&node);
}
}
void creat2(Linklist&L) /*输入一系列整数，以0标志结束，将这些整数作为data域并用尾插
法建立一个带头结点的单链表的函数*/
{ L=(Linklist)malloc(sizeof(LNODE));/*为头结点分配空间*/
L->next=NULL; /*头结点的指针域初始为空*/
r=L; /*尾指针初始指向头结点*/
scanf("%d",&node);
while(node!=0)
{ p=(Linklist)malloc(sizeof(LNODE));/*为一个新结点分配空间*/
p->data=node; /*新结点数据域赋值*/
p->next=NULL; /*新结点指针域为空*/
r->next=p;/*尾结点指针域指向新结点*/
r=p; /*尾指针指向新结点，即新结点成为尾结点*/
scanf("%d",&node);
}
}
statuslist_search(Linklist L, inti;Elemtype&e)
/*在带头结点的单链表L中查找第i个元素，如果查找成功则用e返回其值*/ { p=L->next; /*使指针p指向第1个元素结点*/
j=1; /*计数器赋初值为1*/
while (p&& j { p=p->next; j++; } if (!p&& j>i) return ERROR; /*如果i值不合法，即i值小于1或大于表长，则出错*/ e=p->data; /*如果第i个元素存在，则将该元素值赋给e*/ return OK; } statuslist_insert(Linklist&L,inti;Elemtype x) /*在带头结点的单链表L中第i个位置之前插入新元素x*/ {p=L; j=0; while(p!=NULL&&j ++j; } if(p==NULL||j>i-1) return ERROR; /*若位置不正确,即i小于1或大于表的长度加1，则出错*/ s=(Linklist)malloc(sizeof(LNODE)); /*分配一个新结点的空间*/ s->data=x; /*为新结点数据域赋值*/ /*下面两条语句就是完成修改链，将新结点s插入到p结点之后*/ s->next=p->next; /*新结点指针域指向p的后继结点*/ p->next=s; /*新结点成为p的后继结点*/ return OK; } status list_delete(Linklist&L,inti,Elemtype&x) /*在带头结点的单链表L中，删除第i个元素结点,并用x返回其值*/ {p=L;j=0; while(p->next!=NULL&&j {p=p->next; ++j; } if (p->next==NULL||j>i-1) return ERROR; /*若位置不正确，即i小于1或大于表长，则出错*/ q=p->next; /* q指向p的后继结点*/ p->next=q->next; /*q的后继结点成为p的后继结点*/ x=q->data; /*用x返回第i个位置的元素*/ free(q); /*释放q所指的被删结点的空间*/ return OK; } 3．源程序代码参考 #include #include typedefstructLnode { int data; structLnode *next; } LNODE,*Linklist; Linklistcreat(Linklist L) /*单链表建立函数*/ {int node; Linklist p; L=(Linklist)malloc(sizeof(LNODE)); L->next=NULL; printf("\nplease input the node(end with 0):\n "); /*请求输入线性表中各个元素，以0结束*/ scanf("%d",&node); while(node!=0) {p=(Linklist)malloc(sizeof(LNODE)); if (!p) exit(); p->data=node; p->next=L->next; L->next=p; scanf("%d",&node); } return L; } Linklist insert(LinklistL,inti,int x) /*单链表插入函数*/ { intj;Linklistp,s; p=L; j=0; while (p!=NULL&&j { p=p->next; ++j; } if (p==NULL||j>i-1) printf("\n ERROR position!\n"); else { s=(Linklist)malloc(sizeof(LNODE)); s->data=x; s->next=p->next; p->next=s; } return L; } Linklist delete(LinklistL,inti) /*单链表删除函数*/ { intj,x; Linklistp,q; p=L; j=0; while(p->next!=NULL&&j {p=p->next; ++j; } if(p->next==NULL||j>i-1) printf("\n ERROE position!\n"); else { q=p->next; p->next=q->next; x=q->data; printf("the delete data is:%d\n",x); free(q); } return L; } int search(Linklist L, inti) /*单链上的查找函数*/ { Linklist p; int j; p=L->next; j=1; while (p&& j { p=p->next; j++; } if (!p&& j>i) return 0; /*如果i值不合法，即i值小于1或大于表长，则函数返回0值*/ else return(p->data); /*否则函数返回第i个元素的值*/ } void display(Linklist L) /*单链表元素输出函数*/ { Linklist p; p=L->next; while(p!=NULL) { printf("%4d",p->data); p=p->next; } printf("\n"); } main()/*主函数*/ {Linklist L=NULL; inti,x; L=creat(L);/*调用单链表建立函数*/ printf("the Linklist is:\n"); display(L); /*调用单链表元素输出(遍历)函数*/ printf("please input the position you want to insert:");/*请求输入插入操作位置*/ scanf("%d",&i); printf("please input the node you want to insert:");/*请求输入需要插入的元素*/ scanf("%d",&x); L=insert(L,i,x);/*调用单链表插入函数*/ printf("the Linklist after inserted is:\n"); display(L);/*调用单链表元素输出(遍历)函数*/ printf("please input the node position you want to delete:"); /*请求输入删除操作位置*/ scanf("%d",&i); L=delete(L,i); /*调用单链表删除函数*/ printf("the Linklist after deleted is:\n"); display(L); /*调用单链表元素输出(遍历)函数*/ printf("please input the position you want to search:"); /*请求输入待查找元素的位置*/ scanf("%d",&i); x=search(L,i); /*调用单链表查找函数*/ if (x) /*如果查找成功，则显示第i个元素的值，否则显示第i个元素不存在*/ printf(" the %dthelem is %d\n",i,x); else printf(" the %dthelem is not exsit\n"); } 4．运行结果参考如图2-1所示： 图2-1: 验证性实验运行结果 七、设计性实验 1. 编程实现在双向循环链表上的插入、删除和查找操作 ⑴实验要求 （1）输入链表的长度和各元素的值，用尾插法建立双向循环链表，并输出链表中各元素值，观察输入的内容与输出的内容是否一致。 （2）在双向循环链表的第i个元素之前插入一个值为x的元素，并输出插入后的链表中各元素值。 （3）删除双向循环链表中第i个元素，并输出删除后的链表中各元素值。 （4）在双向循环链表中查找值为x元素，如果查找成功，则显示该元素在链表中的位置，否则显示该元素不存在。 ⑵核心算法提示 双向循环链表采用的存储结构描述如下： typedefstruct DULNODE { Elemtype data; /*数据域*/ struct DULNODE *prior; /*指向前驱结点的指针域*/ struct DULNODE *next;/*指向后继结点的指针域*/ }DULNODE,*DuLinklist; typedefintElemtype; 不论是建立双向循环链表还是在双向循环链表中进行插入、删除和查找操作，其操作方法和步骤都跟单链表类似。只不过要注意两点： （1）凡是在操作中遇到有修改链的地方，都要进行前驱和后继两个指针的修改。 （2）单链表操作算法中的判断条件：p= =NULL 或p!=NULL ,在循环链表的操作算法中则需改为：p!= L,其中L为链表的头指针。 ⑶核心算法描述 void DuList_creat (DuLinklist&L,int n) /*输入n个整数（其中n为表长），将这些整数作为data 域并用尾插法建立一个带头结点的双向循环链表的函数*/ { L=( DuLinklist)malloc(sizeof(DULNODE));/*为头结点分配空间*/ L->next=L->prior=L; /*使头结点的后继指针和前驱指针都指向自身，形成空的双向循环链表*/ r=L; /*尾指针初始指向头结点*/ for (i=0;i { p=(DuLinklist)malloc(sizeof(DULNODE));/*为一个新结点分配空间*/ scanf("%d",&p->data); /*从键盘输入值，并保存在新结点数据域中*/ p->next=r->next; /*新结点后继指针指向尾结点r的后继结点*/ p->prior=r; /*新结点的前驱指针指向尾结点r*/ r->next=p; /*尾结点的后继指针指向新结点*/ r=p; /*尾指针指向新结点，即新结点成为尾结点*/ } L->prior=r; /*使尾结点成为头结点的前驱结点*/ } statusDuList_search(DuLinklist L, inti;Elemtype&e) /*在带头结点的双向循环链表L中查找第i个元素，如果查找成功则用e返回其值*/ { p=L->next; /*使指针p指向第1个元素结点*/ j=1; /*计数器赋初值为1*/ while (p!=L && j { p=p->next; j++; } if (j!=i) return ERROR; /*如果i值不合法，即i值小于1或大于表长，则出错*/ e=p->data; /*如果第i个元素存在，则将该元素值赋给e*/ return OK; } statusDuList_insert(DuLinklist&L,inti;Elemtype x) /*在带头结点的双向循环链表L中第i个位置之前插入新元素x*/ {p=L->next; j=1; while(p!=L &&j ++j; } if(j!=i) return ERROR; /*若位置不正确,即i小于1或大于表的长度加1，则出错*/ s=(DuLinklist)malloc(sizeof(DULNODE)); /*为一个新结点s分配空间*/ s->data=x; /*为新结点数据域赋值*/ /*下面四条语句就是完成修改链，将新结点s插入到p结点之前*/ s->next=p; p->prior->next=s; s->prior=p->prior; p->prior=s; return OK; } status DuList_delete(DuLinklist&L,inti,Elemtype&x) /*在带头结点的双向循环链表L中，删除第i个元素结点，并用x返回其值*/ {p=L->next;j=1; while(p!=L&&j {p=p->next; ++j; } if (j!=i) return ERROR; /*若位置不正确，即i小于1或大于表长，则出错*/ q=p; /*记下被删结点*/ p->prior->next=p->next; /*修改链使得p结点从链中脱离*/ p->next->prior=p->prior; x=q->data; printf("the delete data is:%d\n",x); free(q); //释放被删结点空间 return OK; } 提醒:请将上述算法与单链表上相应操作的算法对照学习，特别注意它们不相同的地方。 八、应用性设计实验 编写一个程序，计算出一个单链表中数据域值为一个指定值x的结点个数。 实验要求： ⑴从键盘输入若干个整数，以此序列为顺序建立一个不带头结点的单链表； ⑵输出此单链表中的各个数据元素值； ⑵给定一个x的具体整数值，计算并返回此单链表中数据域值为x的结点个数值。 2014-2015学年第一学期实验报告 课程名称：算法与数据结构 实验名称：城市链表 一、实验目的 本次实验的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为侧重点。同时，通过本次实验帮助学生复习高级语言的使用方法。 二、实验内容 （一）城市链表： 将若干城市的信息，存入一个带头结点的单链表。结点中的城市信息包括：城市名，城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。 (二) 约瑟夫环 m 的初值为20；密码：3，1，7，2，6，8，4（正确的结果应为6，1，4，7，2，3，5）。三、实验环境 VS2010 、win8.1 四、实验结果 （一）城市链表: （1）创建城市链表； （2）给定一个城市名，返回其位置坐标； （3）给定一个位置坐标P 和一个距离D，返回所有与P 的距离小于等于 D 的城市。 （4）在已有的城市链表中插入一个新的城市； （5）更新城市信息； （6）删除某个城市信息。 (二) 约瑟夫环 m 的初值为20；密码：3，1，7，2，6，8，4 输出6，1，4，7，2，3，5。 五、附录 城市链表： 5.1 问题分析 该实验要求对链表实现创建，遍历，插入，删除，查询等操作，故使用单链表。 5.2 设计方案 该程序大致分为以下几个模块： 1.创建城市链表模块，即在空链表中插入新元素。故创建城市链表中包涵插入模块。 2.返回位置坐标模块。 3.计算距离模块 4.插入模块。 5.更新城市信息模块 6.删除信息模块。 5.3 算法 5.3.1 根据中心城市坐标，返回在距离内的所有城市： void FindCityDistance(citylist *L){ //根据距离输出城市 ……//输入信息与距离 L=L->next; w hile(L != NULL){ if(((L->x-x1)*(L->x-x1)+(L->y-y1)*(L->y-y1 )<=dis*dis)&&(((L->x-x1)+(L->y-y1))!=0 )){ printf("城市名称%s\n",L->Name); printf("城市坐标%.2lf,%.2lf\n",L->x,L->y); } L=L->next; } } 该算法主要用到了勾股定理，考虑到不需要实际数值，只需要大小比较，所以只用 横坐标差的平方+纵坐标差的平方<= 距离的平方判定。 C语言程序设计实验报告 实验一：链表的基本操作一·实验目的 1.掌握链表的建立方法 2.掌握链表中节点的查找与删除 3.掌握输出链表节点的方法 4.掌握链表节点排序的一种方法 5.掌握C语言创建菜单的方法 6.掌握结构化程序设计的方法 二·实验环境 1.硬件环境：当前所有电脑硬件环境均支持 2.软件环境：Visual C++6.0 三.函数功能 1. CreateList // 声明创建链表函数 2.TraverseList // 声明遍历链表函数 3. InsertList // 声明链表插入函数 4.DeleteTheList // 声明删除整个链表函数 5. FindList // 声明链表查询函数 四．程序流程图 五．程序代码 #include r=head;//r指向头结点 printf("输入数字:\n"); for(i=n;i>0;i--)//for 循环用于生成第一个节点并读入数据{ scanf("%d",&x); p=(node *)malloc(sizeof(node)); p->data=x;//读入第一个节点的数据 r->next=p;//把第一个节点连在头结点的后面 r=p;//循环以便于生成第二个节点 } r->next=0;//生成链表后的断开符 return head;//返回头指针 } void output (linklist head)//输出链表 { linklist p; p=head->next; do { printf("%3d",p->data); p=p->next; } while(p); printf("\n") } Status insert ( linklist &l,int i, Elemtype e)//插入操作 { int j=0; linklist p=l,s; while(j 实验一顺序表与链表 一、实验目的 1、掌握线性表中元素的前驱、后续的概念。 2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。 3、对线性表相应算法的时间复杂度进行分析。 4、理解顺序表、链表数据结构的特点（优缺点）。 二、实验预习 说明以下概念 1、线性表：线性表是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限 序列。 2、顺序表：线性表的顺序存储结构或顺序映像，通常，称这种存储结构的线性表为顺序表。 3、链表：指针域中存储的信息称作指针或链。N个接点连接成一个链表，故又称线性链表。 三、实验内容和要求 1、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。 ●#include 计算机与信息技术学院综合性、设计性实验报告 一、实验目的 (1)熟悉顺序表的创建、取值、查找、插入、删除等算法，模块化程序设计方法。 二、实验仪器或设备 (1)硬件设备：CPU为Pentium 4 以上的计算机，内存2G以上 (2)配置软件：Microsoft Windows 7 与VC++6.0 三、总体设计(设计原理、设计方案及流程等) 设计原理： 单链表属于线性表，线性表的存储结构的特点是：用一组任意存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。因此，对于某个元素来说，不仅需要存储其本身的信息，还需要存储一个指示其直接后继的信息。 设计方案： 采用模块化设计的方法，设计各个程序段，最终通过主函数实现各个程序段的功能。设计时，需要考虑用户输入非法数值，所以要在程序中写入说可以处理非法数值的代码。 设计流程： 1. 引入所需的头文件； 2. 定义状态值； 3. 写入顺序表的各种操作的代码； 写入主函数，分别调用各个函数。在调用函数时，采用if结构进行判断输 入值是否非法，从而执行相应的程序 四、实验步骤(包括主要步骤、代码分析等) #include 实验报告 课程名称：数据结构 题目：链表实现多项式相加 班级： 学号： 姓名： 完成时间：2012年10月17日 1、实验目的和要求 1）掌握链表的运用方法； 2）学习链表的初始化并建立一个新的链表； 3）知道如何实现链表的插入结点与删除结点操作； 4）了解链表的基本操作并灵活运用 2、实验内容 1）建立两个链表存储一元多项式； 2）实现两个一元多项式的相加； 3）输出两个多项式相加后得到的一元多项式。 3、算法基本思想 数降序存入两个链表中，将大小较大的链表作为相加后的链表寄存处。定义两个临时链表节点指针p,q,分别指向两个链表头结点。然后将另一个链表中从头结点开始依次与第一个链表比较，如果其指数比第一个小，则p向后移动一个单位，如相等，则将两节点的系数相加作为第一个链表当前节点的系数，如果为0，则将此节点栓掉。若果较大，则在p前插入q,q向后移动一个，直到两个链表做完为止。 4、算法描述 用链表实现多项式相加的程序如下： #include void add_node(struct node*h1,struct node*h2); void print_node(struct node*h); struct node*init_node() { struct node*h=(struct node*)malloc(sizeof(struct node)),*p,*q; int exp; float coef=1.0; h->next=NULL; printf("请依次输入多项式的系数和指数(如:\"2 3\"；输入\"0 0\"时结束):\n"); p=(struct node*)malloc(sizeof(struct node)); q=(struct node*)malloc(sizeof(struct node)); for(;fabs(coef-0.0)>1.0e-6;) { scanf("%f %d",&coef,&exp); if(fabs(coef-0.0)>1.0e-6) { q->next=p; p->coef=coef; p->exp=exp; p->next=NULL; add_node(h,q); } } free(p); free(q); return(h); } void add_node(struct node*h1,struct node*h2) { struct node*y1=h1,*y2=h2; struct node*p,*q; y1=y1->next; y2=y2->next; for(;y1||y2;) if(y1) { if(y2) { if(y1->exp 链表实验报告 ————————————————————————————————作者: ————————————————————————————————日期： 《数据结构》实验报告二 系别:嵌入式系统工程系班级:嵌入式1１0０3班 学号:１1160400３１4姓名：孙立阔 日期：2012年４月９日指导教师:申华 一、上机实验的问题和要求： 单链表的查找、插入与删除。设计算法,实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求: 1.从键盘输入1０个字符，产生不带表头的单链表，并输入结点值。 2.从键盘输入1个字符,在单链表中查找该结点的位置。若找到,则显示“找到了”；否则, 则显示“找不到”。 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出单链表所有结点值,观察输出结果。 4.从键盘输入１个整数,表示欲删除结点的位置，输出单链表所有结点值,观察输出结果。 5.将单链表中值重复的结点删除,使所得的结果表中个结点值均不相同,输出单链表所有结 点值,观察输出结果。 6.删除其中所有数据值为偶数的结点，输出单链表所有结点值,观察输出结果。 7.（★)将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元素, 而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表Ａ和单链表B的所有结点值，观察输出结果。 二、程序设计的基本思想，原理和算法描述: (包括程序的结构,数据结构，输入/输出设计,符号名说明等） 创建一个空的单链表，实现对单链表的查找，插入,删除的功能。 三、源程序及注释： #dｅfiｎｅOK 1 #defｉne EＲＲOR 0 #ｄefiｎe INFEASIBLE －1 #defｉne OVEＲFＬOW －2 #deｆine TRUE 1 . 实验一、单链表的插入和删除 一、目的 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 二、要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 三、程序源代码 #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表 ListNode *LocateNode(); //函数，按值查找结点 void DeleteList(); //函数，删除指定值的结点void printlist(); //函数，打印链表中的所有值 void DeleteAll(); //函数，删除所有结点，释放内存 //==========主函数============== void main() { char ch[10],num[10]; LinkList head; head=CreatListR1(); //用尾插入法建立单链表，返回头指针printlist(head); //遍历链表输出其值 printf(" Delete node (y/n):");//输入“y”或“n”去选择是否删除结点scanf("%s",num); if(strcmp(num,"y")==0 || strcmp(num,"Y")==0){ printf("Please input Delete_data:"); scanf("%s",ch); //输入要删除的字符串 DeleteList(head,ch); printlist(head); } DeleteAll(head); //删除所有结点，释放内存 } //==========用尾插入法建立带头结点的单链表 实 验 报 告 年级 班号 学号 姓名 实验名称： 第一次实验：简单学生管理系统 实验日期 2016年11月25日 计算机科学与技术系 2016年制 一、实验环境 Windows32位系统Microsoft Visual C++ 二、实验目的 掌握链表的使用 三、实验内容 用单向链表实现的简单学生管理系统 四、数据结构与算法思想描述 对单链表的增删查改 五、程序清单 /* 函数信息： 菜单选项 void Menu()； 初始化链表 void InitLink(node *head)； 输出单个学生信息 void SingleShow(node *p)； 尾插法 node* AddLink(node *p,char *num)； 建立链表,并输入学生信息。 node *CreateLink(node *head)； 查找学生信息，查找则返回查找位置前一个点 node *SearchLink(node *head, char *num)； 增加学生信息，先进行查找，若已有则提示用户是否修改,否则增加void InsertLink(node *head, char *num)； 修改学生信息,先进行查找，若已有则提示用户修改,否则退出 void ModifyLink(node *head, char *num)； 删除学生信息 void DeleteLink(node *head, char *num)； 显示所有学生信息 void Display(node *head) */ #include 链表实验报告 一、实验名称 链表操作的实现--学生信息库的构建 二、实验目的 （1）理解单链表的存储结构及基本操作的定义 （2）掌握单链表存储基本操作 （3）学会设计实验数据验证程序 【实验仪器及环境】计算机 Window XP操作系统 三、实验内容 1、建立一个学生成绩信息（学号，姓名，成绩）的单链表，按学号排序 2、对链表进行插入、删除、遍历、修改操作。 3、对链表进行读取（读文件）、存储（写文件） 四、实验要求 （1）给出终结报告（包括设计过程，程序）-打印版 （2）对程序进行答辩 五、实验过程、详细内容 1、概念及过程中需要调用的函数 （1）链表的概念结点定义 结构的递归定义 struct stud_node{ int num; char name[20]; int score; struct stud_node *next; }; （2）链表的建立 1、手动输入 struct stud_node*Create_Stu_Doc() { struct stud_node *head,*p; int num,score; char name[20]; int size=sizeof(struct stud_node); 【链表建立流程图】 2、从文件中直接获取 先建立一个 (3)链表的遍历 （4 ）插入结点 （5）删除结点 （6）动态储存分配函数malloc （） void *malloc(unsigned size) ①在内存的动态存储区中分配一连续空间，其长度为size ②若申请成功，则返回一个指向所分配内存空间的起始地址的指针 ③若申请不成功，则返回NULL （值为0） ④返回值类型：(void *) ·通用指针的一个重要用途 ·将malloc 的返回值转换到特定指针类型，赋给一个指针 【链表建立流程图】 ptr ptr ptr->num ptr->score ptr=ptr->next head pt r s s->next = ptr->next ptr->next = s 先连后断 ptr2=ptr1->next ptr1->next=ptr2->next free （ptr2） #include void Display(DuLinkList L,int n){ int i; for(i=0;i 实验2 链表基本操作实验 一、实验目的 1． 定义单链表的结点类型。 2． 熟悉对单链表的一些基本操作和具体的函数定义。 3． 通过单链表的定义掌握线性表的链式存储结构的特点。 二、实验内容与要求 该程序的功能是实现单链表的定义和主要操作。如：单链表建立、输出、插入、删除、查找等操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。程序中的单链表（带头结点）结点为结构类型，结点值为整型。 要求： 同学们可参考指导书实验2程序、教材算法及其他资料编程实现单链表相关操作。必须包括单链表创建、输出、插入、删除操作，其他操作根据个人情况增减。 三、 算法分析与设计。 头结点 ...... 2.单链表插入 s->data=x; s->next=p->next; p->next=s; 3.单链表的删除： p->next=p->next->next; 四、运行结果 1.单链表初始化 2.创建单链表 3.求链表长度 4.检查链表是否为空 5.遍历链表 6.从链表中查找元素 7.从链表中查找与给定元素值相同的元素在顺序表中的位置 8.向链表中插入元素 插入元素之后的链表 9.从链表中删除元素 删除位置为6的元素(是3) 10.清空单链表 五、实验体会 经过这次单链表基本操作实验，自己的编程能力有了进一步的提高，认识到自己以前在思考一个问题上思路不够开阔，不能灵活的表达出自己的想法，虽然在打完源代码之后出现了一些错误，但是经过认真查找、修改，最终将错误一一修正，主要是在写算法分析的时候出现了障碍，经过从网上查找资料，自己也对程序做了仔细的分析，对单链表创建、插入、删除算法画了详细的N-S流程图。 13软工转本1 钱剑滨实验报告 双向链表实验报告 信息工程系 13软工转本1 日期 2016年03月12日 姓名钱剑滨学号 13131116 电话 一、实验内容 编写关于双向链表操作的C语言程序，要求包含双向链表的创建（生成）、输出（遍历）、查找、任意位置插入、有顺序插入、删除、等。 二、实验步骤 1.分析操作所需思路，熟练运用单链表的各种特点。 2.编写程序，利用函数特性进行操作。 3.运行程序，纠正错误，对预测结果进行验证。 4.分析总结单链表的优缺点，并可以做到熟练掌握双向链表的各种 操作。 三、设计概要 1.本实验包含了7个函数： a)主函数main() b)创建链表函数Listcreate() c)数据输出函数Listprint() d)查找数据函数Listlocate() e)无序插入函数Listinsert_discretion () f)有序插入函数Listinsert_order g)删除数据函数Listdelete() 2.明确函数的功能； a)Listcreate() 创建一个可控长度的斐波那契数列的双向链表。 b)Listprint() 将此链表中的数据全部输出。 c)Listlocate() 查找此链表中任意位置元素的值。 d)Listinsert_discretion ()向此链表的某个位置插入一组数据。 e)Listinsert_order() 向数列中插入一个数，使插入后的数列任 然有序 f)Listdelete() 将此链表的某个位置的一组数据删除。 四、程序设计 1.函数前包含的头文件名、结点类型定义、全局变量和函数声明 #include 大学数据结构实验报告 课程名称数据结构实验第（四）次实验实验名称链表的基本操作 学生姓名于歌专业班级学号 实验成绩指导老师（签名）日期2018年10月01日 一、实验目的 1. 学会定义单链表的结点类型，实现对单链表的一些基本操作和具体 的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。 2. 掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。 二、实验要求 1．预习C语言中结构体的定义与基本操作方法。 2．对单链表的每个基本操作用单独的函数实现。 3．编写完整程序完成下面的实验内容并上机运行。 4．整理并上交实验报告。 三、实验内容： 1．编写程序完成单链表的下列基本操作： （1）初始化单链表La （2）在La中插入一个新结点 （3）删除La中的某一个结点 （4）在La中查找某结点并返回其位置 （5）打印输出La中的结点元素值 （6）清空链表 （7）销毁链表 2 .构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、 Lb合并成一个有序单链表Lc。 四、思考与提高： 1．如果上面实验内容2中合并的表内不允许有重复的数据该如何操作？ 2．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？五、实验设计 1．编写程序完成单链表的下列基本操作： （1）初始化单链表La LinkList InitList() { int i,value,n; LinkList H=(LinkList)malloc(sizeof(LNode)); LinkList P=H; P->next=NULL; do{ printf("请输入链表的长度:"); scanf("%d",&n); if(n<=0) printf("输入有误请重新输入！\n"); }while(n<=0); printf("请输入各个元素:\n"); for(i=0; i 实验2 链表基本操作实验 一、实验目的 1． 定义单链表的结点类型。 2． 熟悉对单链表的一些基本操作和具体的函数定义。 3． 通过单链表的定义掌握线性表的链式存储结构的特点。 二、实验容与要求 该程序的功能是实现单链表的定义和主要操作。如：单链表建立、输出、插入、删除、查找等操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。程序中的单链表（带头结点）结点为结构类型，结点值为整型。 要求： 同学们可参考指导书实验2程序、教材算法及其他资料编程实现单链表相关操作。必须包括单链表创建、输出、插入、删除操作，其他操作根据个人情况增减。 三、 算法分析与设计。 头结点 2.单链表插入 s->data=x; s->next=p->next; p->next=s; 3.单链表的删除： p->next=p->next->next; 四、运行结果 1.单链表初始化 2.创建单链表 3.求链表长度 4.检查链表是否为空 5.遍历链表 6.从链表中查找元素 7.从链表中查找与给定元素值相同的元素在顺序表中的位置 8.向链表中插入元素 插入元素之后的链表 9.从链表中删除元素 删除位置为6的元素(是3) 10.清空单链表 五、实验体会 经过这次单链表基本操作实验，自己的编程能力有了进一步的提高，认识到自己以前在思考一个问题上思路不够开阔，不能灵活的表达出自己的想法，虽然在打完源代码之后出现了一些错误，但是经过认真查找、修改，最终将错误一一修正，主要是在写算法分析的时候出现了障碍，经过从网上查找资料，自己也对程序做了仔细的分析，对单链表创建、插入、删除算法画了详细的N-S流程图。 江南大学物联网工程学院上机报告 单链表实验报告 ————————————————————————————————作者：————————————————————————————————日期： 计算机与信息技术学院综合性、设计性实验报告 专业：网络工程年级／班级：大二 2016—2017学年第一学期 课程名称数据结构指导教师李四 学号姓名16０8３2４０XX 张三 项目名称单链表的基本操作实验类型综合性／设计性实验时间2017.10.3 实验地点216机房 一、实验目的 （１）熟悉顺序表的创建、取值、查找、插入、删除等算法，模块化程序设计方法。 二、实验仪器或设备 (1)硬件设备：CＰU为Pｅntium 4以上的计算机,内存２G以上 （２）配置软件:Microsｏft Windｏws 7与VC++6．０ 三、总体设计（设计原理、设计方案及流程等) 设计原理： 单链表属于线性表,线性表的存储结构的特点是：用一组任意存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。因此,对于某个元素来说，不仅需要存储其本身的信息,还需要存储一个指示其直接后继的信息。 设计方案: 采用模块化设计的方法，设计各个程序段,最终通过主函数实现各个程序段的功能。设计时，需要考虑用户输入非法数值,所以要在程序中写入说可以处理非法数值的代码。 设计流程: 1.引入所需的头文件; 2.定义状态值； 3.写入顺序表的各种操作的代码； 写入主函数,分别调用各个函数。在调用函数时，采用iｆ结构进行判断输入值是否非法,从而执行相应的程序 四、实验步骤（包括主要步骤、代码分析等） #inclｕdｅ<ｓtdio．h＞／/ EOF(=^Z或F6）,ＮUＬL #inclｕde＜ｓtdlｉb.ｈ＞ // sｒand（），raｎd（）,eｘｉt(n) #inｃlude＜ｍalloｃ.h> // mａlloc( )，alloc( ),ｒｅａllｏc（）等 ＃iｎcluｄe 数据结构实验报告 题目：双链表的操作 班级： 姓名： 学号： 一、实验要求和目的 1.理解双链表的基本操作 2.了解双链表的建立和输出 3.掌握双链表的插入、删除等实现方法 二、实验内容 编写一个程序，实现双链表的各种基本运算（假设双链表的元素类型为char），并在此基础上设计一个程序，完成如下功能： （1）初始化双链表h； （2）采用尾插法依次插入元素a，b，c，d，e； （3）输出双链表h； （4）输出双链表h长度； （5）判断双链表h是否为空； （6）输出双链表h的第3个元素； （7）输出元素a的位置； （8）在第4个位置上插入元素f； （9）输出双链表h； （10）删除h的第3个元素； （11）输出双链表h； （12）释放双链表h。 三、设计思想 本次实验主要考察了多双链表的基本操作，包括初始化链表，插入节点，删除节点，寻找元素的位置，判断链表是否为空，输出链表等。本次实验在逻辑上没有什么难度，首先是构造一个结构体，包括向前的指针和向后的指针，其次是构造函数来实现不同的功能，最后是在主函数中初始化链表，再调用构造函数。 四、主要源代码 #include 湖南第一师范学院信息科学与工程系实验报告 课程名称：数据结构与算法成绩评定： 实验项目名称：单链表的基本操作指导教师： 学生姓名：沈丽桃学号： 10403080118 专业班级： 10教育技术 实验项目类型：验证实验地点：科B305 实验时间： 2011 年 10 月20 日一、实验目的与要求： 实验目的：实现线性链表的创建、查找、插入、删除与输出。 基本原理：单链表的基本操作 二、实验环境：（硬件环境、软件环境） 1.硬件环境：奔ⅣPC。 2.软件环境：Windows XP 操作系统，TC2.0或VC＋＋。 三、实验内容：（原理、操作步骤、程序代码等） #include 线性表 一、实验目的 1. 了解线性表的逻辑结构特征，以及这种特性在计算机内的两种存储结构。 2. 掌握线性表的顺序存储结构的定义及其C语言实现。 3. 掌握线性表的链式村粗结构——单链表的定义及其C语言实现。 4. 掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5. 掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验要求 1. 认真阅读和掌握本实验的程序。 2. 上机运行本程序。 ) 3. 保存和打印出程序的运行结果，并结合程序进行分析。 4. 按照对顺序表和单链表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 三、实验内容 请编写C程序，利用链式存储方式来实现线性表的创建、插入、删除和查找等操作。具体地说，就是要根据键盘输入的数据建立一个单链表，并输出该单链表；然后根据屏幕菜单的选择，可以进行数据的插入或删除，并在插入或删除数据后，再输出单链表；然后在屏幕菜单中选择0，即可结束程序的运行。 四、解题思路 本实验要求分别写出在带头结点的单链表中第i（从1开始计数）个位置之后插入元素、创建带头结点的单链表中删除第i个位置的元素、顺序输出单链表的内容等的算法。 五、程序清单 #include<> #include<> #include<> typedef int ElemType; ~ typedef struct LNode { ElemType data; struct LNode *next; }LNode; LNode *L; LNode *creat_L(); void out_L(LNode *L); void insert_L(LNode *L,int i,ElemType e); ElemType delete_L(LNode *L,int i); int locat_L(LNode *L,ElemType e); $城市链表实验报告
链表实验报告
实验一 顺序表与链表 成品
单链表实验报告
链表实现多项式相加实验报告
链表实验报告
单链表的插入和删除实验报告
长沙理工大学数据结构链表的实现及应用实验报告
C语言链表实验报告
双向链表的创建
链表基本操作实验报告
双向链表实验报告
链表的基本操作-数据结构实验报告
链表基本操作实验报告
实验三四 链表的实现和应用
课程名称 班 级 数据结构 上机名称 姓 名 链表的实现和应 用 上机日期 学 号 2016.3.11 上机报告要求 1．上机名称 2．上机要求 3．上机环境 4．程序清单（写明运行结果） 5．上机体会
1．上机名称
链表的实现和应用
2．上机要求
⑴定义线性表的链式存储表示； ⑵基于所设计的存储结构实现线性表的基本操作； ⑶编写一个主程序对所实现的线性表进行测试； ⑷线性表的应用：①设线性表 L1和 L2分别代表集合 A 和 B，试设计算法求 A 和 B 的并集 C，并用线 性表 L3代表集合 C；②设线性表 L1和 L2中的数据元素为整数，且均已按值非递减有序排列，试 设计算法对 L1和 L2进行合并，用线性表 L3保存合并结果，要求 L3中的数据元素也按值非递减 有序排列。 ⑸设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式 相加；④执行两个多项式相减；⑤（选做）执行两个多项式相乘。
3．上机环境
Visual C++ 6.0
4．程序清单（写明运行结果）
（1） #include单链表实验报告
数据结构实验三——双链表的操作 初始化 插入 输出
单链表的基本操作实验报告
单链表操作实验报告