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

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

二、实验内容与要求⑴定义线性表的链式存储表示；⑵基于所设计的存储结构实现线性表的基本操作；⑶编写一个主程序对所实现的线性表进行测试；⑷线性表的应用：①设线性表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;in;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-expnpb-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-expnpb-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=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-expnpb-expn){s=(List)malloc(sizeof(struct Linklist));s-expn=pa-expn;s-coef=pa-coef;s-next=NULL;p=s;pa=pa-next;}else if(pa-expnpb-expn){s=(List)malloc(sizeof(struct L(转载于: 写论文网:线性表的链式存储,实验报告)inklist));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=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;}篇二：《线性表的链式存储》实验报告《线性表的链式存储》实验报告1.需解决的的问题利用线性表的链式存储结构，设计一组输入数据。

实验二线性表的链式存储
一、实验目的
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）。

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

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

实验三线性表的链式存储【实验目的】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六个元素时的运行结果：。

实验一线性表的链式存储【实验时间】【实验地点】【实验目的和要求】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() 建立单链表的函数很明显这个函数的返回值时结点指针类型的，所以这个函数应该返回的时建立的单链表的头指针。

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

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