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

实验二 链式存储线性表的基本操作一、 实验目的1. 掌握用Turbo C2.0上机调试线性表的基本方法。

2. 掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在链接存储结构上的运算。

二、 实验内容1.typedef int ElemType;typedef struct LNode { //创建结构体数据类型LNodeElemType data; //存放数值的数据域struct LNode *next; //存放后继结点地址的指针域}LNode;2. 链表的创建：创建n 个结点，利用scanf( )函数为每个结点的数据域赋值，一次将每个结点插入链表，形成一个包含n 个元素的链表。

#define NULL 0#define OVERFLOW 0#define OK 1#define ERROR -1typedef int ElemType;typedef struct LNode { //创建LNode 数据类型ElemType data;struct LNode *next;}LNode;typedef LNode *LinkList; //定义LinkList 指针型数据类型int CreateList_L(LinkList L, int n) { //创建拥有n 个元素的线性链表//int i;struct LNode *p;L->next = NULL; //线性链表初始化，见右图for (i = n; i > 0; --i) { //循环n 次在头结点和第一个结点间插入新结点，形成长度为n 的线性链表p =(LNode*)malloc(sizeof(LNode));scanf("%d",&p->data);p->next = L ->next;L->next =p;}return 1;}data next data nextl1)2)3)int VistList_L(LinkList L) { //遍历链表L中每个结点的函数struct LNode *p;p = L->next;while (p) {printf("%d ",p->data); //访问输出p结点的数据域p = p->next; } //p指针前进一位，指向后继结点printf("\n");return OK;}}lmain(){int m;LNode l;ElemType e;printf("please input the length of the linklist that you want to build");scanf("%d",&m);printf("please give the number that you want to insert");CreateList_L(&l,m); //调用创建链表函数VistList_L(&l); //调用遍历链表结点函数}3. 链表的插入算法：向链表中某个位置上插入一个结点#define NULL 0#define OVERFLOW 0#define OK 1#define ERROR -1typedef int ElemType;typedef struct LNode { //创建LNode 数据类型ElemType data;struct LNode *next;}LNode;typedef LNode *LinkList;int CreateList_L(LinkList L, int n) { //创建包含n 个元素的链表int i;struct LNode *p;L->next = NULL;for (i = n; i > 0; --i) {p =(LNode*)malloc(sizeof(LNode));scanf("%d",&p->data);p->next = L ->next;L->next =p;}return 1;}int ListInsert_L(LinkList L, int i, ElemType e) { //向链表中第i位插入数据e struct LNode *s,*p;int j;p = ; j = 0; //p指针指向线性链表的头结点while (p && j < ) //循环查找第i-1位作为数据e的插入位置{ p = ; ++j; } //p指针向前移动if (!p || j > i-1)return ERROR;s =(LNode*)malloc(sizeof(LNode)); //见下图1）if ( s == NULL) return ERROR;s-> = e; //将插入数据e的值赋值给s结点的数据域1）s->next = ; p->next = ; //旧链断开，新链产生2）3）return OK;}1）2）3）int VistList_L(LinkList L) { //遍历链表所有结点的函数struct LNode *p;p = L->next;while (p) {printf("%d",p->data);p = p->next; }return OK;}main(){int m;LNode l;ElemType e;int i;printf("please input the length of the linklist that you want to build");scanf("%d",&m);printf("please give the number that the initial list have");CreateList_L(&l,m);VistList_L(&l);printf("please input the positon and data of the insert number i&e");scanf("%d,%d",&i,&e);ListInsert_L(&l,i,e);VistList_L(&l);}附：一元多项式的相加#include<stdio.h>#include<stdlib.h>#define LEN sizeof(node)typedef struct polynode /*用单链表存储多项式的结点结构*/{int coef; /*多项式的系数*/int exp; /*指数*/struct polynode *next; /*next是struct polynode类型中的一个成员，它又指向struct polynode类型的数据，以此建立链表*/}node;/*若定为"node,*list;"，意即node*与list同为结构指针类型*/node * create(void) /*指针函数，返回指针类型；用尾插法建立一元多项式的链表的函数*/ {node *h,*r,*s;int c,e;h=(node *)malloc(LEN); /*建立多项式的头结点，为头结点分配存储空间*/r=h; /*r指针始终动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/ printf("coef:");scanf("%d",&c); /*输入系数*/printf("exp: ");scanf("%d",&e); /*输入指针*/while(c!=0) /*输入系数为0时，表示多项式的输入结束*/{s=(node *)malloc(LEN); /*申请新结点*/s->coef=c; /*申请新结点后赋值*/s->exp=e; /*申请新结点后赋值*/r->next=s; /*做尾插，插入新结点*/r=s; /*r始终指向单链表的表尾*/printf("coef:");scanf("%d",&c);printf("exp: ");scanf("%d",&e);}r->next=NULL; /*将表的最后一个结点的next置NULL，以示表结束*/return(h);}void polyadd(node *polya, node *polyb)/*一元多项式相加函数，用于将两个多项式相加，然后将和多项式存放在多项式polya中，并将多项式ployb删除*/{node *p,*q,*pre,*temp;int sum;p=polya->next;/*令p和q分别指向polya和polyb多项式链表中的第一个结点*/q=polyb->next;pre=polya; /*位置指针，指向和多项式polya*/while(p!=NULL&&q!=NULL) /*当两个多项式均未扫描结束时，执行以下操作*/{if(p->exp<q->exp) /*若p指向的多项式指数小于q指的指数*/{pre->next=p; /*将p结点加入到和多项式中*/pre=pre->next;p=p->next;}else if(p->exp==q->exp) /*若指数相等，则相应的系数相加*/{sum=p->coef+q->coef;if(sum!=0){p->coef=sum;pre->next=p;pre=pre->next;p=p->next;temp=q;q=q->next;free(temp);}else /*如果系数和为零，则删除结点p与q，并将指针指向下一个结点*/{temp=p->next;free(p);p=temp;temp=q->next;free(q);q=temp;}}else /*若p指数大于q指数*/{pre->next=q; /*p结点不动，将q结点加入到和多项式中*/pre=pre->next;q=q->next;}}if(p!=NULL) /*多项式A中还有剩余，则将剩余的结点加入到和多项式中*/ pre->next=p;else /*否则将B的结点加入到和多项式中*/pre->next=q;}void print(node * p) /*输出函数，打印出一元多项式*/{while(p->next!=NULL){p=p->next;printf(" %d*x^%d",p->coef,p->exp);}}main() /*主函数*/{node * polya,* polyb;printf("Welcome to use!\n");printf("\nPlease input the ploya include coef && exp:\n");polya=create(); /*调用建立链表函数，创建多项式A*/print(polya);printf("\nPlease input the ployb include coef && exp:\n");polyb=create(); /*同理，创建B*/print(polyb);printf("\nSum of the poly is:\n");polyadd(polya,polyb); /*调用一元多项式相加函数*/print(polya); /*调用输出函数，打印结果*/printf("\n");}。

实验二线性表的链式存储
一、实验目的
1.掌握线性表的链式存储结构。

2.能熟练地利用链式存储结构实现线性表的基本操作。

3.能熟练地掌握链式存储结构中算法的实现。

二、实验内容
1.分别用头插法和尾插法建立带头结点的单链表。

2.实现单链表上的插入、删除、修改、查找、计数、输出等基本操作。

3.解决约瑟夫问题：假设有n个人按1、2、3、…、n的顺序围成一圈，现在，从第s个人开始按1、2、3、…、m的顺序报数，数到m的人出圈，接着从出圈的下一个人开始重复此过程，直到所有人出圈为止。

试用循环链表解决这个问题。

三、算法描述
1.第1题、第2题的算法提示
先定义单链表的数据类型，然后将头插法和尾插法、插入、删除、修改、查找、计数、输出等基本操作都定义成单独的子函数形式，最后在主函数中调用，并将每一种操作前后的结果输出，以查看每一种操作的效果。

2.第3题的算法提示
首先将n个人的信息建立成一个单循环链表，链表中的每个结点信息就是每个人的编号（1～n）。

然后利用循环找到出圈人位置的结
点，输出该结点的信息，再在链表中删除该结点，接着从删除的结点的后面重复此步骤，直到链表中剩下一个结点时停止循环，再把链表中的最后一个结点删除。

实验报告的要求与实验一相同。

实验报告课程名称：数据结构与算法分析实验名称：链表的实现与应用实验日期：班级：数媒1401 姓名：范业嘉学号一、实验目的掌握线性表的链式存储结构设计与基本操作的实现。

二、实验内容与要求⑴定义线性表的链式存储表示；⑵基于所设计的存储结构实现线性表的基本操作；⑶编写一个主程序对所实现的线性表进行测试；⑷线性表的应用：①设线性表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<n;i++){s=(Linklist)malloc(sizeof(Lnode));scanf("%d",&s->data);s->next=NULL;p->next=s; p=s;}}2.（1）两个链表的合并void Mergelist(Linklist &La,Linklist &Lb,Linklist &Lc) {Linklist pa,pb,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else {pc->next=pb;pc=pb;pb=pb->next;} }pc->next=pa?pa:pb;free(Lb);}（2）两个链表的并集Linklist unionlist(Linklist &La,Linklist &Lb){Linklist p1,p2,head,q,s;int flag;head=q=(Linklist)malloc(sizeof(Lnode));p1=La->next;while(p1){flag=0;p2=Lb->next;while(p2){if(p1->data==p2->data){flag=1;break;}p2=p2->next;}if(flag==0){s=(Linklist)malloc(sizeof(Lnode));s->data=p1->data;q->next=s;q=s;}p1=p1->next;}q->next=Lb->next;return head;}3.（1）一元多项式的加法List addpoly(List pa,List pb) //一元多项式的加法{int n;List pc,s,p;pa=pa->next;pb=pb->next;pc=(List)malloc(sizeof(struct Linklist));pc->next=NULL;p=pc;while(pa!=NULL&&pb!=NULL){if(pa->expn>pb->expn){s=(List)malloc(sizeof(struct Linklist));s->expn=pa->expn;s->coef=pa->coef;s->next=NULL;p->next=s;p=s;pa=pa->next;}else if(pa->expn<pb->expn){s=(List)malloc(sizeof(struct Linklist));s->expn=pb->expn;s->coef=pb->coef;s->next=NULL;p->next=s;p=s;pb=pb->next;}else{n=pa->coef+pb->coef;if(n!=0){s=(List)malloc(sizeof(struct Linklist));s->expn=pa->expn;s->coef=n;s->next=NULL;p->next=s;p=s;}pb=pb->next;pa=pa->next;}}while(pa!=NULL){s=(List)malloc(sizeof(struct Linklist));s->expn=pa->expn;s->coef=pa->coef;s->next=NULL;p->next=s;p=s;pa=pa->next;}while(pb!=NULL){s=(List)malloc(sizeof(struct Linklist));s->expn=pb->expn;s->coef=pb->coef;s->next=NULL;p->next=s;p=s;pb=pb->next;}return pc;}（2）一元多项式的减法List subpoly(List pa,List pb) //一元多项式的减法{int n;List pc,s,p;pa=pa->next;pb=pb->next;pc=(List)malloc(sizeof(struct Linklist));pc->next=NULL;p=pc;while(pa!=NULL&&pb!=NULL){if(pa->expn>pb->expn){s=(List)malloc(sizeof(struct Linklist));s->expn=pa->expn;s->coef=pa->coef;s->next=NULL;p->next=s;p=s;pa=pa->next;}else if(pa->expn<pb->expn){s=(List)malloc(sizeof(struct Linklist));s->expn=pb->expn;s->coef=-pb->coef;s->next=NULL;p->next=s;p=s;pb=pb->next;}else{n=pa->coef-pb->coef;if(n!=0){s=(List)malloc(sizeof(struct Linklist));s->expn=pa->expn;s->coef=n;s->next=NULL;p->next=s;p=s;}pb=pb->next;pa=pa->next;}}while(pa!=NULL){s=(List)malloc(sizeof(struct Linklist));s->expn=pa->expn;s->coef=pa->coef;s->next=NULL;p->next=s;p=s;pa=pa->next;}while(pb!=NULL){s=(List)malloc(sizeof(struct Linklist));s->expn=pb->expn;s->coef=-pb->coef;s->next=NULL;p->next=s;p=s;pb=pb->next;}return pc;}（3）一元多项式的乘法void mulpolyn(polynomail pa,polynomail pb,polynomail &pc) {LNode *p,*q,*s,*hc;p=pa->next;q=pb->next;hc=pc;while(p!=NULL){while(q!=NULL){s=(polynomail)malloc(sizeof(LNode));hc->next=s;hc=hc->next;hc->coef=q->coef*p->coef;hc->expn=q->expn+p->expn;q=q->next;}p=p->next;q=pb->next;}hc->next=NULL;}五、测试结果2.3.六、心得体会（包括对于本次实验的小结，实验过程中碰到的问题等）1.首先书上给的链表输入是倒序的，写的时候想都没想就抄上去了，结果运行时发现问题，可是上网百度依然没有把问题解决，导致最后输出链表倒序的，并且链表的合并并集依旧是倒序的。

实验三线性表的链式存储【实验目的】1.掌握基本线性链式存储的类型定义及C语言实现；2.掌握基本线性表在链式存储结构中的各种基本操作。

【实验要求】1.学会定义一个链式存储结构体LNode；2.学会链式存储结构的初始化、清空、求线性表的长度、遍历、改值、插入（头插、尾插、固定位置插入）、删除（删头、删尾、固定位置删除）；3.学会用main函数调用定义的各个函数；【实验环境】VC++运行的环境【实验步骤及代码】一、创建VC工程环境二、编写、调试程序//一、包含库文件和类型定义#include <stdio.h>#include <stdlib.h>typedef char ElemType;//二、定义结构typedef struct LNode{ElemType data;struct LNode *next;}LNode,*LinkList;//三、基本操作函数的定义//(1)创建一个带头结点的链表LinkList CreateList_L(int n){//逆序输入如n个元素的值，建立一个带表头结点的单链表LinkList L=(LinkList)malloc(sizeof(LNode));L->next=NULL;char ch;for(int i=n;i>0;--i){scanf("%c",&ch);p->data=ch;p->next=L->next;L->next=p;}return L;}//(2)链表的遍历函数void travel_L(LinkList s){LinkList p=s->next;while(p){printf("%c",p->data);p=p->next;}printf("\n");}//(3)返回链表L的第i个元素的值ElemType GetElem_L(LinkList L,int i){ LNode *p=L->next;int j=1;while (p&&j<i) {p=p->next;++j;}if (!p||j>i) {printf("i越界！");exit(1);}elsereturn p->data;}//(4)链表的i个位置插入一个值为e的节点void ListInsert_L(LinkList L,int i,ElemType e){ LinkList p=L;int j=0;while (p&&j<i-1) {p=p->next;++j;}if (!p||j>i-1) exit(1);else{s->data=e;s->next=p->next;p->next=s;}return;}//(5)链表中删除第i个元素void ListDelete_L(LinkList L,int i){LNode *p=L;int j=0;while (p->next&&j<i-1) {p=p->next;++j;}if(!(p->next)||j>i-1) exit(1);LNode *q=p->next;p->next=q->next;free(q);return;}//(6)删除链表的第一个节点void ListDeleteFist_L(LinkList L){ListDelete_L(L,1);}//(7)求一个链表的长度int ListLength_L(LinkList L){LNode *p=L;int j=0;while (p->next) {p=p->next;++j;}return j;}//(8)在一个链表的尾部查入一个值为e的节点void ListInsertLast_L(LinkList L,ElemType e){ ListInsert_L(L,ListLength_L(L)+1,e);}//(9)删除链表的尾节点void ListDeleteLast_L(LinkList L){ListDelete_L(L,ListLength_L(L));}//(10)把链表的第i个值改为evoid Listchange(LinkList L,int i,ElemType e){LNode *p=L;int j=0;while (p->next&&j<i) {p=p->next;++j;}if(!(p->next)||j>i) exit(1);p->data=e;return;}//(11)链表中找值为e的节点的位置int ListFind(LinkList L,ElemType e){LNode *p=L;int j=0;while (p->next&&(p->data!=e)) {p=p->next;++j;}if(!(p->next)||j>ListLength_L(L)) exit(1);elsereturn j;}//(12)清空一个链表void ListClear_L(LinkList L){while (L->next) {ListDeleteLast_L(L);}}//四、主调函数void main(){LinkList L=CreateList_L(6);travel_L(L);printf("链表的第2个元素是：");printf("%c\n",GetElem_L(L,2));printf("链表的第2个位置插入值为w后的链表：");ListInsert_L(L,2,'w');travel_L(L);printf("删除链表的第2个位置上的节点后的链表：");ListDelete_L(L,2);travel_L(L);printf("删除链表的头节点后的链表：");ListDeleteFist_L(L);travel_L(L);printf("\n");printf("当前链表的长度为：");printf("%d",ListLength_L(L));printf("\n");printf("链表的尾部插入z后：");ListInsertLast_L(L,'z');travel_L(L);printf("\n");printf("删除链表的尾节点后：");ListDeleteLast_L(L);travel_L(L);printf("\n");printf("把第二个节点的值改为Y后：");Listchange(L,2,'Y');travel_L(L);printf("\n");printf("找链表中值为Y的位置：");printf("%d",ListFind(L,'Y'));printf("\n");printf("清空链表：");ListClear_L(L);travel_L(L);printf("\n");}【实验结果】输入abcdef六个元素时的运行结果：。

昆明理工大学信息工程与自动化学院学生实验报告（201 —201学年第一学期）
课程名称：数据构造开课实验室：
年级、专业、班学号姓名
实验项目名称线性表链式储存运算的算法实现指导教师
年
成绩
月日
教
师
评教师署名：
语年月日一. 实验内容：
线性表链式储存运算的算法实现，实现链表的成立、链表的数据插入、链表的数据删除、链表的数据输出。

二.实验目的：
1.掌握线性表链式储存构造的 C语言描绘及运算算法的实现；
2.剖析算法的空间复杂度和插入和删除的时间复杂度；
3.总结比较线性表次序储存藏储与链式储存的各自特色。

三. 主要程序代码剖析：
LinkList creatListR1()序运转结果：
五. 实验总结：
经过线性表链式储存运算的算法实现的上机实验，我认识了链式的基来源理和方法，能编程对数据进行链式储存。

因为次序储藏是用物理地点上的毗邻关系来表示结点间的逻
辑关系，其插入或删除运算不方便，并且当表长变化较大时，难以确立适合的储存规模，
为认识决这些问题，我们采纳链接方式储存线性表。

因此，当线性表的长度变化较大，难
以预计其储存规模时，以采纳动向链表作为储存构造为好；假如关于屡次进行插入删除的
线性表，以采纳链表做储存构造。

链接储存是最常用的储存方法之一，它不单能够表示线
性表，还能够用来表示各样非线性的数据构造。

实验一线性表的链式存储【实验时间】【实验地点】【实验目的和要求】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和bstruct node *next;}NODE , *NODEPTR; //定义了单链表结点类型和单链表结点指针类型2、对单链表的四种操作进行实现。

(1) NODEPTR creatlink() 建立单链表的函数很明显这个函数的返回值时结点指针类型的，所以这个函数应该返回的时建立的单链表的头指针。

同学们可以根据自己的构思，从前往后或从后往前建立单链表。

此外，提醒同学们最好建立带有附加头结点的单链表。

线性表的链式存储
一、目的：
1.顺序表链式存储结构的运算；
2.顺序表空间分配好后的各个运算的执行；
3.顺序表中的打印、输入、置空表、长度、插入、删除的运算等
二、功能层次图：
三、运行结果：
主菜单：
建立链表：
打印 线性表的链式存储
输入 置空表 长度 插入 删除
打印链表：
链表查询：
四、小结：
1.线性表的线性存储是将线性表中的结点采用连接的方式存储；
2.链式存储是用任意的存储单元来存储数据的，这个单元可以使连续的也可以是不连续的，所以链表的结点的逻辑次序和物理次序不一定相同；
3.链表中每个结点的的存储地址是放在前一个前驱的next，而第一个结点无前驱则头指针是head；
4.链表在查找运算中耗时较多，在查找是链表必须从头指针开始扫描才能获得；
5.链表在进行插入和输出运算，都只用修改指针的存放地址的单元。

一、实验目的通过本次实验，使学生掌握数据结构中存储结构的基本概念，了解不同存储结构的特点和适用场景，能够根据具体问题选择合适的存储结构，提高编程能力和问题解决能力。

二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发环境：Visual Studio 2019三、实验内容1. 线性表的存储结构描述（1）顺序存储结构：使用数组实现线性表的存储结构，通过数组的索引来访问元素。

顺序存储结构具有以下特点：优点：存储密度高，空间利用率高；随机访问速度快。

缺点：插入和删除操作需要移动大量元素，效率较低。

（2）链式存储结构：使用链表实现线性表的存储结构，每个节点包含数据和指向下一个节点的指针。

链式存储结构具有以下特点：优点：插入和删除操作效率高，只需修改指针；支持动态内存分配。

缺点：存储密度低，空间利用率较低；随机访问速度慢。

2. 栈的存储结构描述（1）顺序存储结构：使用数组实现栈的存储结构，栈顶元素位于数组的最后一个位置。

顺序存储结构具有以下特点：优点：存储密度高，空间利用率高；随机访问速度快。

缺点：插入和删除操作需要移动大量元素，效率较低。

（2）链式存储结构：使用链表实现栈的存储结构，每个节点包含数据和指向下一个节点的指针。

链式存储结构具有以下特点：优点：插入和删除操作效率高，只需修改指针；支持动态内存分配。

缺点：存储密度低，空间利用率较低；随机访问速度慢。

3. 队列的存储结构描述（1）顺序存储结构：使用数组实现队列的存储结构，队首元素位于数组的第一个位置，队尾元素位于数组的最后一个位置。

顺序存储结构具有以下特点：优点：存储密度高，空间利用率高；随机访问速度快。

缺点：插入和删除操作需要移动大量元素，效率较低。

（2）链式存储结构：使用链表实现队列的存储结构，队首元素位于链表的第一个节点，队尾元素位于链表的最后一个节点。

链式存储结构具有以下特点：优点：插入和删除操作效率高，只需修改指针；支持动态内存分配。

石家庄经济学院实验报告学院: 信息工程学院专业: 计算机信息工程学院计算机实验中心制一 实验内容1.进一步熟悉C 语言的上机环境，掌握C 语言的基本结构。

2.会定义线性表的链式存储结构。

3.熟悉对单链表的一些基本操作(建表、插入、删除等)和具体的函数定义。

二 实验目的掌握链式存储结构的特点，了解、掌握并实现单链表的常用的基本算法。

三 需求设计线性表抽象数据类型的描述及实现ADT List{数据对象： {|,,,,,0}i i D a a ElemSet i 12n n =∈=≥数据关系： {,|,,,,}i 1i i 1i R a a a a D i 2n --=<>∈=基本操作：构造一个空的线性表L InitList();销毁线性表L DestroyList();将L 重置为空表 ClearList();判断L 是否为空 ListEmpty();求表长 ListLength();查找元素 LocateElem();求前驱 PriorElem();求后继 NextElem();插入元素ListInsert();删除元素ListDelete();元素调用visit()函数ListTraverse(L,visit())}ADT List;程序具体实现要求：1.创建一个线性表2.能输出所有数据元素3.能求线性表长度4.能插入删除元素5.能查找元素6.能求元素的前驱和后继7.用户操作界面如下：*********************************** 1. 构造线性表* 2. 插入元素* 3. 删除元素* 4. 查找元素* 5. 显示表长* 6. 求后继* 7. 求前驱* 8. 输出所有元素* 0. 结束程序运行*********************************** 请输入您的选择(0,1,...,8):四详细设计步骤4：上机编程与调试主程序如下：#include "stdafx.h"#include "stdio.h"#include "LinkList0515.h"#include "user.h"#include "Fun.h"int main(int argc, char* argv[]){CLinkList0515 L;LinkList l;int flag,flag1=0,loc,e,next_e,pre_e;printf("\n**************************************"); printf("\n* 1. 构造单链表");printf("\n* 2. 插入元素");printf("\n* 3. 删除元素");printf("\n* 4. 查找元素");printf("\n* 5. 显示表长");printf("\n* 6. 求后继");printf("\n* 7. 求前驱");printf("\n* 8. 输出所有元素");printf("\n* 0. 结束程序运行");printf("\n**************************************");while(1){printf("\n请输入您的选择(0,1,...,8): ");scanf("%d",&flag);switch(flag){case 0:++flag1;break;case 1:if(OK==L.InitList_L(l))printf("\n成功完成单链表初始化操作!\n");elseprintf("\n操作失败，内存溢出!\n");break;case 2:printf("\n 请输入插入元素的位序,值（空格隔开）: ");scanf("%d %d",&loc,&e);if(ERROR==L.ListInsert_L(l,loc,e))printf("\n操作失败，可能是插入位序不合理!\n");elseprintf("\n成功完成操作!\n");L.ListTraverse_L(l,DisplayData);break;case 3:printf("\n 请输入被删除元素的位序: ");scanf("%d",&loc);if(ERROR==L.ListDelete_L(l,loc,e))printf("\n操作失败,可能是位序不合理!\n");else{ printf("\n元素 %d 成功被删除!\n",e);L.ListTraverse_L(l,DisplayData);}break;case 4:printf("\n 请输入待查找的元素的值: ");scanf("%d",&e);loc=L.LocateElem_L(l,e,compare);if(!loc)printf("\n表中不存在元素 %d !\n",e);elseprintf("\n找到了，元素 %d 在表中的位置是: %d \n",e,loc);break;case 5:printf("\n表长为: %d \n",L.ListLength_L(l));break;case 6:printf("\n 请输入元素的值: ");scanf("%d",&e);if(ERROR==L.NextElem_L(l,e,next_e))printf("\n表中元素 %d 没有后继!\n",e);elseprintf("\n表中元素%d 的后继是: %d\n",e,next_e);break;case 7:printf("\n 请输入元素的值: ");scanf("%d",&e);if(ERROR==L.PriorElem_L(l,e,pre_e))printf("\n表中元素 %d 没有前驱!\n",e);elseprintf("\n表中元素%d 的前驱是: %d \n",e,pre_e);break;case 8:L.ListTraverse_L(l,DisplayData);break;default:break;} //switchif(flag1==1) break;}//whileprintf("\n结束!\n\n\n");return 0;}运行结果如下：图3.1五实验总结1. 基本掌握线性表链式存储结构的特点；2. 基本掌握单链表的常用的基本操作算法；3. 通过线性表的抽象数据类型的学习，进一步掌握抽象数据类型的定义方法；4. 对于同一个线性表，用顺序结构和链式存储结构实现，算法也不同；从而可知，逻辑结构依赖于物理结构；。

线性表的链式存储结构实验报告实验一：线性表的链式存储结构【问题描述】某项比赛中，评委们给某参赛者的评分信息存储在一个带头结点的单向链表中，编写程序：（1）显示在评分中给出最高分和最低分的评委的有关信息（姓名、年龄、所给分数等）。

（2）在链表中删除一个最高分和一个最低分的结点。

（3）计算该参赛者去掉一个最高分和一个最低分后的平均成绩。

【基本要求】（1）建立一个评委打分的单向链表；（2）显示删除相关结点后的链表信息。

（3）显示要求的结果。

【实验步骤;】（1）运行PC中的Microsoft Visual C++ 6.0程序，（2）点击“文件”→“新建”→对话窗口中“文件”→“c++ Source File”→在“文件名”中输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”，（3）输入程序代码，程序代码如下:head=create(PWRS);printf("所有评委打分信息如下:\n");print(head);//显示当前评委打分calc(head);//计算成绩printf("该选手去掉 1 最高分和 1 最低分后的有效评委成绩:\n");print(head);//显示去掉极限分后的评委打分}void input(NODE *s) #include#include#include#include#include#define NULL 0#define PWRS 5 //定义评委人数struct pw //定义评委信息{ char name[6];float score;int age;};typedef struct pw PW;struct node //定义链表结点{struct pw data;struct node * next;};typedef struct node NODE;//自定义函数的声明NODE *create(int m); //创建单链表int calc(NODE *h); //计算、数据处理void print(NODE *h); //输出所有评委打分数据void input(NODE *s);//输入评委打分数据void output(NODE *s);//输出评委打分数据void main(){NODE *head;float ave=0;float sum=0;{printf("请输入评委的姓名: ");scanf("%S",&s->/doc/433085523.html,); printf("年龄: ");scanf("%d",&s->data.age);printf("打分: ");scanf("%f",&s->data.score);printf("\n");}void output(NODE *s){printf("评委姓名: %8s ,年龄: %d,打分: %2.2f\n",s->/doc/433085523.html,,s->data. age,s->data.score);}NODE *create(int m){NODE *head,*p,*q;int i;p=(NODE*)malloc(sizeof(NODE));head=p;q=p;p->next=NULL;for(i=1;i<=m;i++){p=(NODE*)malloc(sizeof(NODE));input(p);p->next=NULL;q->next=p;q=p;}return (head);}void print(NODE *h){ for(int i=1;((i<=PWRS)&&(h->next!=NULL));i++){h=h->next;output(h); }printf("\n");}int calc(NODE *h){NODE *q,*p,*pmin,*pmax;float sum=0;float ave=0;p=h->next; //指向首元结点pmin=pmax=p; //设置初始值sum+=p->data.score;p=p->next;for(;p!=NULL;p=p->next){if(p->data.score>pmax->data.score) pmax=p;if(p->data.scoredata.score) pmin=p;sum+=p->data.score;}cout<<"给出最高分的评委姓名："</doc/433085523.html,<<"年龄："<data.age<<"分值："<data.score<<endl;< bdsfid="172" p=""></endl;<>cout<<"给出最低分的评委姓名："</doc/433085523.html,<<"年龄："<data.age<<"分值："<data.score<<endl;< bdsfid="177" p=""></endl;<>printf("\n");sum-=pmin->data.score;sum-=pmax->data.score;for (q=h,p=h->next;p!=NULL;q=p,p=p->next){if(p==pmin){q->next=p->next; p=q;}//删除最低分结点if(p==pmax) {q->next=p->next; p=q;}//删除最高分结点}ave=sum/(PWRS-2);cout<<"该选手的最后得分是："<<ave<<endl;< bdsfid="188" p=""></ave<<endl;<>return 1;}实验结束。

线性表的链式存储结构实验报告文件编码（008-TTIG-UTITD-GKBTT-PUUTI-WYTUI-8256）实验报告课程名称：数据结构与算法分析实验名称：链表的实现与应用实验日期：班级：数媒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<n;i++){s=(Linklist)malloc(sizeof(Lnode));scanf("%d",&s->data);s->next=NULL;p->next=s; p=s;}}2.（1）两个链表的合并void Mergelist(Linklist &La,Linklist &Lb,Linklist &Lc) {Linklist pa,pb,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else {pc->next=pb;pc=pb;pb=pb->next;} }pc->next=papa:pb;free(Lb);}（2）两个链表的并集Linklist unionlist(Linklist &La,Linklist &Lb){Linklist p1,p2,head,q,s;int flag;head=q=(Linklist)malloc(sizeof(Lnode));p1=La->next;while(p1){flag=0;p2=Lb->next;while(p2){if(p1->data==p2->data){flag=1;break;}p2=p2->next;}if(flag==0){s=(Linklist)malloc(sizeof(Lnode));s->data=p1->data;q->next=s;q=s;}p1=p1->next;}q->next=Lb->next;return head;}3.（1）一元多项式的加法List addpoly(List pa,List pb)3.六、心得体会（包括对于本次实验的小结，实验过程中碰到的问题等）1.首先书上给的链表输入是倒序的，写的时候想都没想就抄上去了，结果运行时发现问题，可是上网百度依然没有把问题解决，导致最后输出链表倒序的，并且链表的合并并集依旧是倒序的。

实验名称：线性表的链式存储结构实验日期：2022年X月X日班级：XX班姓名：XXX学号：XXXXXXX指导教师：XXX一、实验目的1. 理解线性表的链式存储结构及其特点。

2. 掌握链表的基本操作，如创建、插入、删除、查找和遍历等。

3. 通过实际编程实现链表，加深对链式存储结构概念的理解。

二、实验内容与要求1. 定义线性表的链式存储表示，包括节点结构和链表结构。

2. 实现链表的基本操作，如创建链表、插入节点、删除节点、查找节点和遍历链表等。

3. 编写测试代码，验证链表操作的正确性。

三、实验步骤1. 定义链表节点结构体，包含数据和指向下一个节点的指针。

2. 创建链表结构体，包含指向头节点的指针和节点数量。

3. 实现链表创建操作，初始化链表。

4. 实现链表插入操作，包括在链表头部、尾部和指定位置插入节点。

5. 实现链表删除操作，包括删除链表头部、尾部和指定位置的节点。

6. 实现链表查找操作，根据节点数据查找节点在链表中的位置。

7. 实现链表遍历操作，打印链表中的所有节点数据。

8. 编写测试代码，验证链表操作的正确性。

四、实验代码```c#include <stdio.h>#include <stdlib.h>// 定义链表节点结构体typedef struct Node {int data;struct Node next;} Node;// 创建链表Node createList() {Node head = (Node)malloc(sizeof(Node));if (head == NULL) {printf("Memory allocation failed!\n"); return NULL;}head->next = NULL;return head;}// 在链表头部插入节点void insertAtHead(Node head, int data) {Node newNode = (Node)malloc(sizeof(Node)); if (newNode == NULL) {printf("Memory allocation failed!\n"); return;}newNode->data = data;newNode->next = head->next;head->next = newNode;}// 在链表尾部插入节点void insertAtTail(Node head, int data) {Node newNode = (Node)malloc(sizeof(Node)); if (newNode == NULL) {printf("Memory allocation failed!\n"); return;}newNode->data = data;newNode->next = NULL;Node current = head;while (current->next != NULL) {current = current->next;}current->next = newNode;}// 删除链表头部节点void deleteAtHead(Node head) {if (head->next == NULL) {printf("List is empty!\n");return;}Node temp = head->next;head->next = temp->next;free(temp);}// 删除链表尾部节点void deleteAtTail(Node head) {if (head->next == NULL) {printf("List is empty!\n");return;}Node current = head;while (current->next->next != NULL) { current = current->next;}Node temp = current->next;current->next = NULL;free(temp);}// 删除指定位置的节点void deleteAtPosition(Node head, int position) {if (head->next == NULL || position < 0) {printf("Invalid position!\n");return;}Node current = head;int index = 0;while (current->next != NULL && index < position - 1) { current = current->next;index++;}if (current->next == NULL) {printf("Invalid position!\n");return;}Node temp = current->next;current->next = temp->next;free(temp);}// 查找节点Node findNode(Node head, int data) {Node current = head->next;while (current != NULL) {if (current->data == data) { return current;}current = current->next;}return NULL;}// 遍历链表void traverseList(Node head) {Node current = head->next;while (current != NULL) {printf("%d ", current->data); current = current->next;}printf("\n");}// 释放链表内存void freeList(Node head) {Node current = head;while (current != NULL) {Node temp = current;current = current->next;free(temp);}}int main() {Node head = createList();insertAtHead(head, 3);insertAtHead(head, 2);insertAtHead(head, 1);insertAtTail(head, 4);insertAtTail(head, 5);printf("Original list: ");traverseList(head);deleteAtHead(head);deleteAtTail(head);printf("List after deleting head and tail: ");traverseList(head);deleteAtPosition(head, 1);printf("List after deleting node at position 1: ");traverseList(head);Node node = findNode(head, 3);if (node != NULL) {printf("Node with data 3 found at position: %d\n", (head->next == node ? 1 : (head->next != NULL ? 2 : 3)));} else {printf("Node with data 3 not found.\n");}freeList(head);return 0;}```五、实验结果与分析1. 通过实验，成功实现了线性表的链式存储结构，包括创建、插入、删除、查找和遍历等基本操作。

一、实验目的1. 掌握线性链式结构的定义和特点。

2. 理解线性链式结构的存储方式及其优缺点。

3. 学会使用C语言实现线性链式结构的基本操作，如插入、删除、查找等。

4. 提高编程能力和问题解决能力。

二、实验内容与要求1. 定义线性链式结构的节点结构体。

2. 实现线性链式结构的创建、插入、删除、查找、遍历等基本操作。

3. 编写主函数，通过菜单选择不同的操作，验证实验效果。

三、实验环境1. 操作系统：Windows 102. 编程语言：C语言3. 开发环境：Visual Studio 2019四、实验步骤1. 定义线性链式结构的节点结构体```ctypedef struct LNode {int data; // 数据域struct LNode next; // 指针域} LNode, LinkList;```2. 创建线性链式结构```cLinkList createList(int n) {LinkList head = (LinkList)malloc(sizeof(LNode)); if (head == NULL) {exit(1);}head->next = NULL;LNode tail = head;for (int i = 0; i < n; i++) {LNode newNode = (LNode )malloc(sizeof(LNode)); if (newNode == NULL) {exit(1);}scanf("%d", &newNode->data);newNode->next = NULL;tail->next = newNode;tail = newNode;}return head;}```3. 插入节点```cvoid insertNode(LinkList head, int i, int e) {if (i < 1) {return;}LNode p = head;int k = 1;while (p != NULL && k < i - 1) {p = p->next;k++;}if (p == NULL || p->next == NULL) {return;}LNode newNode = (LNode )malloc(sizeof(LNode)); if (newNode == NULL) {exit(1);}newNode->data = e;newNode->next = p->next;p->next = newNode;}```4. 删除节点```cvoid deleteNode(LinkList head, int i) {if (i < 1 || head == NULL) {return;}LNode p = head;int k = 1;while (p->next != NULL && k < i - 1) { p = p->next;k++;}if (p->next == NULL) {return;}LNode delNode = p->next;p->next = delNode->next;free(delNode);}```5. 查找节点```cint findNode(LinkList head, int e) {LNode p = head->next;int k = 1;while (p != NULL) {if (p->data == e) {return k;}p = p->next;k++;}return 0;}```6. 遍历链表```cvoid traverseList(LinkList head) { LNode p = head->next;while (p != NULL) {printf("%d ", p->data);p = p->next;}printf("\n");}```7. 主函数```cint main() {LinkList head = NULL;int n, i, e, result;printf("请输入链表长度：");scanf("%d", &n);head = createList(n);printf("请输入要插入的元素和位置："); scanf("%d %d", &e, &i);insertNode(head, i, e);printf("请输入要删除的位置：");scanf("%d", &i);deleteNode(head, i);printf("请输入要查找的元素：");scanf("%d", &e);result = findNode(head, e);if (result != 0) {printf("元素在位置：%d\n", result); } else {printf("元素不存在\n");}printf("链表元素：");traverseList(head);return 0;}```五、实验结果与分析通过本次实验，成功实现了线性链式结构的基本操作，包括创建、插入、删除、查找和遍历。

实验报告三线性表的链式存储班级: 2010XXX 姓名: HoogLe 学号: 2010XXXX 专业: XXXX*****************（1）实验目的:（2）掌握单链表的基本操作的实现方法。

（3）掌握循环单链表的基本操作实现。

（4）掌握两有序链表的归并操作算法。

实验内容: （请采用模板类及模板函数实现）1.线性表链式存储结构及基本操作算法实现[实现提示] （同时可参见教材p64-p73页的ADT描述及算法实现及ppt）函数、类名称等可自定义, 部分变量请加上学号后3位。

也可自行对类中所定义的操作进行扩展。

所加载的库函数或常量定义:#include <iostream>using namespace std;（1）单链表存储结构类的定义:template<class T>class LinkList{public:LinkList(); //初始化带头结点空单链表构造函数实现LinkList(T a[],int n);//利用数组初始化带头结点的单链表构造函数实现~LinkList();int length(); //求单链表表长算法T get(int i); //获得单链表中第i个结点的值算法int locate(T temp);void insert(int i,T temp); //在带头结点单链表的第i个位置前插入元素e算法T Delete(int i); //在带头结点单链表中删除第i个元素算法void print(); //遍历单链表元素算法bool isEmpty(); //判单链表表空算法void deleleAll(); //删除链表中所有结点算法（这里不是析构函数, 但功能相同）private:Node<T> *head;};（2）初始化带头结点空单链表构造函数实现输入：无前置条件: 无动作: 初始化一个带头结点的空链表输出：无后置条件: 头指针指向头结点。

实验一线性表一．目的与要求本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。

要求仔细阅读并理解下列例题，上机通过，并观察其结果，然后独立完成后面的实习题。

二．例题[问题描述]用链表形式存储一个字符串，插入、删除某个字符，最后按正序、逆序两种方式输出字符串。

[输入]初始字符串，插入位置，插入字符，删除字符。

[输出]已建立链表（字符串），插入字符后链表，删除字符后链表，逆转后链表。

[存储结构]采用链式存储结构[算法的基本思想]建立链表：当读入字符不是结束符时，给结点分配存储空间，写数据域，将新结点插到表尾；插入字符：根据读入的字符在链表中找插入位置，将新结点插入到该位置之前；删除字符：根据读入的删除字符在链表中找到被删结点后，将其从链表中删除；链表逆转：从链表的第一个结点开始对所有结点处理，将每个结点的前驱变为它的后继；打印链表：从链表的第一个结点开始，依次打印各个结点的数据域。

[参考源程序]#define NULL 0typedef struct node{char a;struct node *link;}node,*nodelink;void readlink(nodelink head){nodelink p,q;char c;p=head;printf("Input a linktable(a string):");scanf("%c",&c);if (c=='\n') printf("This string is empty。

");while(c!='\n'){q=(nodelink)malloc(sizeof(node));q->a=c;p->link=q;p=q;scanf("%c",&c);}p->link=NULL;}void writelink(nodelink head){nodelink q;if (head->link==NULL) printf(" This link is empty。

南昌航空大学实验报告课程名称：数据结构实验名称：实验一线性表的链式存储结构班级：080611 学生姓名：冯武明学号：16 指导教师评定：XXX 签名: XXX题目：设计并实现以下算法：给出用单链表存储多项式的结构，利用后接法生成多项式的单链表结构，实现两个多项式相加的运算，并就地逆置相加后的多项式链式。

一、需求分析⒈先构造两个多项式链表，实现两个多项式的和及删除和值为零元素的操作，不同用户输入的多项式不同。

⒉在演示过程序中，用户需敲击键盘输入多项式，即可观看结果。

⒊程序执行的命令包括：（1）构造多项式链表pa （2）构造多项式链表pb （3）求两张链表的和（4）删除和值为零元素，即不创建链表结点。

二、概要设计⒈为实现上述算法，需要线性表的抽象数据类型：ADT Stack {数据对象：D={a i:|a i∈ElemSet,i=1…n,n≥0}数据关系：R1={<a i-1,a i>|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相同的元素。