实验三、线性表的链式存储

实验报告题目：完成线性表ADT的顺序存储和链式存储方式的实现一、需求分析1、本演示程序中，线性表的数据元素类型限定为整型2、演示程序以用户和计算机的对话方式执行，即在计算机的终端上显示“提示信息”之后由用户在键盘上键入演示程序规定的运算命令，相应的输出结果显示在后面。

3、程序的执行命令包括：创建、撤销、清空、插入、修改、删除、定位等线性表ADT各项基本操作二、概要设计为实现上述功能，我们给出线性表的抽象数据类型定义，具体的有单向链，双向链，顺序表等，同时对于上述功能的实现还采用有/无头结点两种方式来实现1.线性表的抽象数据类型定义为ADT List{数据对象：D={a i|a i∈ElemSet，i=1,2,…,n,n≥0}数据关系：R1={<a i-1,a i>|ai-1,ai∈D，i=2,…,n}基本操作：InitList(&L)操作结果：构造一个空的线性表LDestroyList(&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.熟悉掌握多项式加法的算法。

二、实验原理顺序存储的线性表有一些弱点，其一，插入与删除元素需要大量移动元素；其二，预先分配存储空间时必须按最大的空间来分配。

其三，表长难以扩充。

所以，必须引入链式存储结构。

链式存储结构的特点是用一组任意的存储单元存储线性链表的数据元素，与顺序表的区别在于链式存储的存储单元可以是连续的，也可以是不连续的。

为了实现这种结构，链表采取由两部分信息组成数据元素a i的存储映像，称为结点。

结点包括两个域，其中存储数据信息的域称为数据域，存储直接后继信息的称为指针域。

指针域中存储的信息叫做指针或链。

这样，n个结点链接成一个链表，即为线性表（a1,a2,a3,···,a n）。

1.符号多项式的操作，已经成为表处理的典型用例，在数学上，一个一元多项式pn(x)可以按升幂写成：pn(x)=p0+p1·x+p2·（x的2次幂）+···+p n·（x的n次幂）。

它由n+1个系数唯一确定。

因此，在计算机里，它可用一个线性表P来表示：P=(p0,p1,p2,···,p n), 显然，此种表示仅适于顺序存储结构，在通常的应用中，多项式的次数变化很高且很大，将造成内存的很大浪费。

2.实现单链表就地逆置。

三、实验要求1．参照书上的原理说明分析程序，深入理解链表的物理存储模式和逻辑模式。

2．看懂书上算法，参考实验程序编出程序上机调试。

3．参考书上的程序，编写建立链表存储多项式，并实现两多项式相加。

四、代码实现：1.# include<stdio.h># include<stdlib.h>typedef struct Polynode{int coef;int exp;Polynode *next;}Polynode,* Polylist;Polylist polycreate(){Polynode * head,*rear,*s;int c,e;head=(Polynode *)malloc(sizeof(Polynode)); rear=head;scanf("%d,%d",&c,&e);while(c!=0){s=(Polynode *)malloc(sizeof(Polynode));s->coef=c;s->exp=e;rear->next=s;rear=s;scanf("%d,%d",&c,&e);}rear->next=NULL;return (head);}void polyadd(Polylist polya,Polylist polyb) {Polynode *p,*q,*tail,*temp;int sum;p=polya->next;q=polyb->next;tail=polya;while(p!=NULL && q!=NULL){if (p->exp<q->exp){tail->next=p;tail=p;p=p->next;}else if (p->exp==q->exp){sum=p->coef+q->coef;if (sum!=0){p->coef=sum;tail->next=p;tail=p;p=p->next;temp=q;q=q->next;free(temp);}else{temp=p;p=p->next;free(temp);temp=q;q=q->next;free(temp);}}else{tail->next=q;tail=q;q=q->next;}}if(p==NULL)tail->next=p;elsetail->next=q;}void main(){Polynode *p;printf("请输入第一个多项式,次数从低到高:\n"); Polylist A=polycreate();printf("\n多项式创建完成!\n");printf("\n请输入第二个多项式,次数从低到高:\n"); Polylist B=polycreate();printf("\n多项式创建完成!\n\n");polyadd(A,B);p=A->next;while(p!=NULL){printf("[%d %d] ",p->coef,p->exp);p=p->next;}printf("\n\n");}2.# include<stdio.h># include<stdlib.h>typedef struct Node{char data;struct Node * next;}Node,* Linklist;void Initlist(Linklist *L){*L=(Linklist)malloc(sizeof(Node));(*L)->next=NULL;}void CreateFromHead(Linklist L){Node *s;char c;int flag=1;while(flag){c=getchar();if (c!='$'){s=(Node *)malloc(sizeof(Node));s->data=c;s->next=L->next;L->next=s;}else flag=0;}}void Reverselist(Linklist L){Linklist p,q;p=L->next;L->next=NULL;while(p!=NULL){q=p->next;p->next=L->next;L->next=p;p=q;}}void main (){Linklist p;Linklist L;Initlist(&L);printf("Please input datas:\n");CreateFromHead(L);p=L;while (p->next!=NULL){p=p->next;printf("%c ",p->data);}Reverselist(L);printf("\n\n");}五：结果验证：1.2。

实验报告课程名称：数据结构与算法分析实验名称：链表的实现与应用实验日期：班级：数媒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六个元素时的运行结果：。

实验三链式存储一、实验目的和要求掌握线性表链式存储结构的描述，学会针对链式存储线性表的基本操作。

二、实验内容和原理C语言结构化程序设计思想，结构体及指针的应用。

三、主要仪器设备装有Visual C++/Turbo C++等C程序编译软件的计算机。

四、实验中程序的源码1. 设计一个算法，利用单链表原来的结点空间将一个单链表就地逆转。

程序代码如下：#include “linklist.h”V oid verge(linklist head ){ Linklist p,q;P->next=null;Head->next=null;While(p){q=p;P=p->next;q->next=head->next;Head->next=q;}}Int main(){Linklist head;Head=creatlinklist();Print(head);Verge()head;Print(head);}1.建立两个指针struct* p，q，p=head,q=p->next,即最开始p指向链表的第1项，q指向第2项2.if q->next !=NULL,p=p->next,q=q->next 3.endif q->next ==NULL,即q指向最后一项，p 指向倒数第二项新建一个指针，保存原表尾的地址struct*t=q4.q->next=p,q=p //倒数第一项指向倒数第二项，将q指向倒数第二项5.p=head //p重新重表头开始遍历6.if p->next !=q,p=p->next //如果p 指向的不是q指向的前一项，则p继续向后遍历7.endif p->next ==q //q指向p的前一项8. q->next =p,q=p //重复第4步9.p=head //重复第5步。

N. until q=p=head 至此，原链表已经完全逆转，然后让头指针指向原链表的表尾，即指向新链表的表头head=t，这样就搞定了这里写出程序源代码2. 设计一个算法，将一个结点值为自然数的单链表拆分成两个单链表，原表中保留值为偶数的结点，而值为奇数的结点按它们在原表中的相对次序组成一个新的单链表。

数据结构（⼆）：线性表的链式存储结构1、为什么要使⽤链式存储结构？因为我们前⾯讲的线性表的顺序存储结构，他是有缺点的。

最⼤的缺点就是插⼊和删除时需要移动⼤量元素，这显然就需要耗费时间。

要解决这个问题，我们就需要分析⼀下为什么当插⼊和删除时，就要移动⼤量元素，因为相邻两元素的存储位置也具有相邻关系，它们在内存中的位置也是挨着的，中间没有空隙，当然就⽆法快速介⼊，⽽删除之后。

当中就会留出空隙，⾃然就需要弥补。

问题就出在这⾥。

为了解决这个问题，⾃然⽽然的就出现了链式存储结构。

2、线性表链式存储结构的特点：线性表的链式存储结构不考虑元素的存储位置，⽽是⽤⼀组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，这就意味着，这些数据元素可以存在内存未被占⽤的任意位置。

顺序存储结构：只需要存储数据元素信息。

链式存储结构：除了要存储数据元素信息之外，还要存储⼀个指⽰其直接后继元素的存储地址。

3、关键词：数据域：存储数据元素信息的域。

指针域：存储直接后继位置的域。

指针或链：指针域中存储的信息。

结点（Node）：指针域+数据域组成数据元素的存储映像。

头指针：链表中第⼀个结点的存储位置。

头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。

头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。

4、单链表：定义：n个结点链成⼀个链表，即为线性表的链式存储结构，因此此链表的每个结点中只包含⼀个指针域，所以叫做单链表。

PS：线性链表的最后⼀个结点指针为“空”,通常⽤NILL或“^”符号表⽰。

头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。

头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。

5、头结点与头指针的异同（1）头结点头结点是为了操作的统⼀和⽅便⽽设⽴的，放在第⼀个元素的结点之前，其数据域⼀般⽆意义（也可存放链表的长度）有了头结点，对第⼀元素结点前插⼊和删除第⼀结点，其操作就统⼀了头结点不⼀定是链表的必要素（2）头指针头指针式指向第⼀个结点的指针，若链表有头结点，则是指向头结点的指针。

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

石家庄经济学院实验报告学院: 信息工程学院专业: 计算机信息工程学院计算机实验中心制一 实验内容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. 对于同一个线性表，用顺序结构和链式存储结构实现，算法也不同；从而可知，逻辑结构依赖于物理结构；。

贵州大学实验报告学院：计算机科学与信息学院专业：信息安全班级：chaintable *Buildtable(int x[],int y) {chaintable *p,*head;p=new chaintable;head=p;p->data=x[0];for(int i=1;i<y;i++){p->next=new chaintable;p=p->next;p->data=x[i];}p->next=NULL;return head;}bool Deltable(chaintable *&head,int x) {if(x<1)return false;chaintable *relief,*p=head;for(int i=0;i<x-2;i++){if(p->next==NULL)return false;p=p->next;}if(x==1){relief=head;head=head->next;delete relief;if(head!=NULL)return true;elsereturn false;}else{if(p->next!= NULL){relief=p->next;p->next=p->next->next;delete relief;return true;}elsereturn 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<y-1;i++){if(p->next==NULL)return false;p=p->next;}t->next=p->next;p->next=t;return true;}}void Disptable(chaintable *p){while(p!=NULL){cout<<p->data<<' ';p=p->next;}cout<<endl;}bool Searchtable(chaintable *p,int &y,int x) {if(x>=1){for(int i=0;i<x-1;i++){if(p->next==NULL)return false;p=p->next;}y=p->data;return true;}elsereturn false;}int Location(chaintable *p,int x){int i=1;while(p!=NULL){if(p->data==x)return i;i++;p=p->next;}return 0;}void main(){int x,*temp,result;chaintable *head;cin>>x;temp=new int[x];for(int i=0;i<x;i++)cin>>temp[i];head=Buildtable(temp,x);if(Deltable(head,2)){cout<<"删除操作结果：";Disptable(head);}elsecout<<"操作失败！"<<endl;if(Inserttable(head,23,5)){cout<<"将23插入到第五个数字后面的操作结果：";Disptable(head);}elsecout<<"操作失败！"<<endl;if(Searchtable(head,result,4)){cout<<"链表的第四个数是：";cout<<"Search result:"<<result<<endl;}elsecout<<"操作失败！"<<endl;cout<<"Please input your integer:";cin>>x;cout<<"Location:"<<Location(head,x)<<endl;}实验结果：实验总结结果说明:1、第一行的8表示链表初始有8个数2、第二行的8个数是链表初始化的8个数3、第三行的结果是从链表删除了第二个数后的结果4、第五行的结果是搜索链表第四个数5、第六行是输入一个数要搜索的数（图中为25），第七行得出了搜索的结果。

线性表的链式存储结构实验报告实验一：线性表的链式存储结构【问题描述】某项比赛中，评委们给某参赛者的评分信息存储在一个带头结点的单向链表中，编写程序：（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. 通过实验，成功实现了线性表的链式存储结构，包括创建、插入、删除、查找和遍历等基本操作。

《数据结构B》实验报告系计算机与电子专业电子科学与技术2008级01 __班姓名岳恒学号20081185028 2010年1 0月9日上机题目：链式存储实验1.详细设计实验目的：理解链表的逻辑结构和存储结构，熟练掌握链表的相关操作。

1、问题描述链表是用一组任意的存储单元来依次存储线性表中的各个数据元素，这些存储单元可以是连续的，也可以是不连续的。

用链接存储结构表示线性表的一个元素时至少要有两部分信息:一是这个数据元素的值，二是这个数据元素的直接后继的存储地址。

这两部分信息一起组成了链表的一个结点。

数据域用来存放数据元素的值；指针域（又称链域）用来存放该数据元素的直接后继结点的地址。

链表正是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接成为一个整体。

通常用箭头表示链域中的指针，于是单链表就可以直观地画成用箭头链接起来的结点序列，单链表中每个结点的存储地址存放在其直接前驱的指针域中，因此访问单链表的每一个结点必须从表头指针开始进行。

对单链表的操作主要有：建立单链表、查找（按序号查找、按值查找）、插入一个结点、删除一个结点、求表长等。

2、数据结构设计单链表的结点结构如下：typedef struct node{ /*单链表结点结构*/ElemType data; /*ElemType可以是任何相应的数据类型如int,char等*/struct node *next;} LinkList;3、功能（函数）设计链表的基本操作：InitList1(LinkList *&head)//初始化不带头结点的链表头指针AddHead1(LinkList *&head, ElemType x)//使用表首添加法，向头指针为head的链表中插入一个结点，其值为xInitList(LinkList *&head)//初始化带头结点的链表头指针AddHead(LinkList *head, ElemType x)//使用表尾添加法，向头指针为head的链表中插入一个结点，其值为xCreatList(LinkList *head,int n)//生成含有n个结点的单链表output(LinkList *head)//输出单链表GetNode(LinkList *head, int i)//在带头结点的单链表中查找第i个结点，找到返回该结点指针，否则返回NULLLocateNode(LinkList *head, ElemType x)//在带头结点的单链表中查找值为x的结点，找到返回结点指针，否则返回NULLInsertNode(LinkList *head, int i, ElemType x)//在带头结点的单链表中第i个结点位置上插入值为x的结点DeleteNode1(LinkList *head, ElemType x)//在带头结点的单链表中删除值为x的结点DeleteNode(LinkList *head, int i)//在带头结点的单链表中删除第i个结点Length(LinkList *head)//在带头结点的单链表中求表的长度InsertOrder(LinkList *head,int x)//在有序单链表L中插入值为x的结点，插入后仍然有序union1(LinkList *head,LinkList *B,LinkList *&C)//A和B是两个带头结点的递增有序的单链表，本算法将两表合并成，一个带头结点的递增有序单链表C，利用原表空间。

实验报告三线性表的链式存储班级: 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）初始化带头结点空单链表构造函数实现输入：无前置条件: 无动作: 初始化一个带头结点的空链表输出：无后置条件: 头指针指向头结点。

南昌航空大学实验报告课程名称：数据结构实验名称：实验一线性表的链式存储结构班级：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相同的元素。