实验报告二：线性表及其基本操作实验(2学时)

实验日期2010.4.19 教师签字成绩实验报告【实验名称】第二章线性表的基本操作及应用【实验目的】（1）熟练掌握线性表的基本操作的实现；（2）以线性表的各种操作（建立、插入、删除等）的实现为重点；（3）通过本次实验加深对C语言的使用（特别是函数的参数调用、指针类型的应用和链表的建立等各种基本操作）。

【实验内容】1.顺序表的基本操作（顺序表的插入、访问、删除操作）#include <stdio.h>#include <stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW -1typedef int ElemType;typedef int Status;#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct{ElemType *elem;int length;int listsize;}SqList;Status InitList_Sq(SqList *L){int i,n;L->elem = (ElemType * )malloc(LIST_INIT_SIZE*sizeof(ElemType));if (! L->elem) exit (OVERFLOW);printf("您希望您的顺序表有几个元素: ");scanf("%d",&n);printf("\n");printf("输入您的%d个元素，以构建顺序表: \n",n);for(i=1;i<=n;i++)scanf("%d",&L->elem[i-1]);L->length = n;L->listsize = LIST_INIT_SIZE;return OK;}//InitList_SqStatus PrintList_Sq(SqList L){int i;printf("顺序表中的元素为：");for (i=1;i<=L.length;i++)printf("%d ",L.elem[i-1]);printf("\n");return OK;}//PrintList_Sqint ListInsert_Sq(SqList* L,int i,ElemType x) //对顺序表进行插入操作{int j;if (L->length==L->listsize){printf("\t\t\t顺序表已满");return 0;}else{if (i<1||i>L->length){printf("\t\t\t位置不合法");return 0;}else{for(j=L->length-1;j>=i-1;--j)L->elem[j+1]=L->elem[j];L->elem[i-1]=x;L->length++;return 1;}}}int ListDelete_Sq(SqList* L,int i) //对顺序表进行删除操作{int j;if (i<1||i>L->length){printf("\t\t\t不存在第i个元素");return 0;}else{for (j=i-1;j<L->length;j++){L->elem[j]=L->elem[j+1];}L->length--;return 1;}}int LocateElem(SqList *L, int i) {if(i<1||i>L->length)return ERROR;else return L->elem[i-1];}int scan(){int choose;printf("选择要执行的基本操作:\n1.插入元素；2.删除元素；3.访问元素.\n");printf("输入其他值退出程序……\n");scanf("%d",&choose);return(choose);}void main(){SqList L;ElemType e;int i;int quit=0;if (InitList_Sq(&L)==OVERFLOW)printf("分配失败，退出程序！");printf("输出程序中的元素\n");PrintList_Sq(L);while(!quit)switch(scan()){case 1:printf("\n请输入你所需要插入的位置和你要插入的元素:");printf("\n请输入i和e的值:");scanf("%d%d",&i,&e);if (ListInsert_Sq(&L,i,e)==OK) PrintList_Sq(L);break;case 2:printf("\n请输入你所需要删除元素的位置:");scanf("%d",&i);if(ListDelete_Sq(&L,i)==OK) PrintList_Sq(L);break;case 3:printf("请输入所要查找元素的位置:\n");scanf("%d",&i);if(LocateElem(&L,i))printf("该位置元素的值为:%d!\n",LocateElem(&L,i));else printf("该位置的元素不存在!\n");break;default:quit=1;printf("操作结束!");printf("\n");}}2.单向链表的基本操作（单向链表的插入、删除、查找以及并表操作）#include<stdio.h>#include<malloc.h>typedef int ElemType;#define OK 1#define ERROR 0#define flag 0typedef struct LNode{ElemType data;struct LNode *next;} LNode,*LinkList;LinkList InitLinkList(){LinkList L;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;return L;}LinkList LocateLinkList(LinkList L,int i){LinkList p;int j;p=L->next;j=1;while(p!=NULL&&j<i){p=p->next; j++;}if (j==i)return p;else return NULL;}void LinkListInsert(LinkList L, int i, ElemType e)//插入元素{LinkList p,s;int j;j=1;p=L;while(p&&j<i){p=p->next;j++;}if(p==NULL||j>i)printf("插入位置不正确\n");else {s=(LNode *)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;printf("%d已插入到链表中\n",e);}}void LinkListDelete(LinkList L,int i) //删除元素{LinkList p,q;int j;j=1;p=L;while(p->next&&j<i){p=p->next;j++;}if(p->next==NULL)printf("删除位置不正确\n");else{q=p->next;p->next=q->next;free(q);printf("第%d个元素已从链表中删除\n",i);}}LinkList CreatLinkList( )//建立单向链表{LinkList L=InitLinkList(),p,r;ElemType e;r=L;printf("请依次输入链表中的元素,输入0结束\n"); scanf("%d",&e);while (e!=flag){p=(LinkList)malloc(sizeof(LNode));p->data=e;r->next=p;r=p;scanf("%d",&e);}r->next=NULL;return L;}int LinkListLength(LinkList L){LinkList p;int j;p=L->next;j=0;while(p!=NULL){j++;p=p->next;}return j;}void LinkListPrint(LinkList L){LinkList p;p=L->next;if(p==NULL) printf("单链表为空表\n");else{printf("链表中的元素为:\n");while(p!=NULL){printf("%d ",p->data);p=p->next;}}printf("\n");}void Mergelist_L(LinkList La,LinkList Lb,LinkList Lc) {LNode *pa,*pb,*pc,*p;pa=La->next;pb=Lb->next;Lc=La;pc=Lc;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;p=Lc->next;printf("合并结果:");while(p) {printf("%4d",p->data);p=p->next;}free(Lb);}int scan(){int d;printf("请选择你所要执行的单向链表的基本操作:\n1.插入元素;2.删除元素;3.访问元素;4.两个单向链表的合并.\n");printf("其他键退出程序……");printf("\n");scanf("%d",&d);return(d);}void main(){ LinkList La,Lb,Lc;int quit=0;int i,locate;ElemType e;LinkList L,p;L=CreatLinkList();while(!quit)switch(scan()){case 1:printf("请输入插入元素的位置和值(中间以空格或回车分隔):\n");scanf("%d%d",&i,&e);LinkListInsert(L,i,e);LinkListPrint(L);break;case 2:if(LinkListLength(L)==0)printf("链表已经为空,不能删除\n\n");else{printf("请输入待删除元素的位置:\n");scanf("%d",&i);LinkListDelete(L,i);}LinkListPrint(L);break;case 3:printf("请输入待查询元素在链表中的位置:");scanf("%d",&i);p=LocateLinkList(L,i);if(p)printf("链表中第%d个元素的值为:%d\n",i,p->data);elseprintf("查询位置不正确\n\n");break;case 4:La=CreatLinkList();Lb=CreatLinkList();Mergelist_L( La, Lb, Lc);printf("\n");break;default:quit=1;printf("操作结束!");printf("\n");}}3.单向循环链表的基本操作（单向链表的插入、删除、查找操作）#include<stdio.h>#include<malloc.h>typedef int ElemType;#define OK 1#define ERROR 0#define flag 0typedef struct LNode{ElemType data;struct LNode *next;} LNode,*LinkList;LinkList InitLinkList(){LinkList L;L=(LinkList)malloc(sizeof(LNode));L->next=L;return L;}LinkList LocateLinkList(LinkList L,int i){LinkList p;int j;p=L->next;j=1;while(p!=L&&j<i){p=p->next; j++;}if (j==i)return p;else return NULL;}void LinkListInsert(LinkList L, int i, ElemType e)//插入元素{LinkList p,s;int j;j=1;p=L;while(p->next!=L&&j<i){p=p->next;j++;}if(p==L||j>i)printf("插入位置不正确\n");else {s=(LNode *)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;printf("%d已插入到链表中\n",e);}}void LinkListDelete(LinkList L,int i) //删除元素{LinkList p,q;int j;j=1;p=L;while(p->next!=L&&j<i){p=p->next;j++;}if(p->next==L)printf("删除位置不正确\n");else{q=p->next;p->next=q->next;free(q);printf("第%d个元素已从链表中删除\n",i);}}LinkList CreatLinkList( )//建立单向链表{LinkList L=InitLinkList(),p,r;ElemType e;r=L;printf("请依次输入链表中的元素,输入0结束\n"); scanf("%d",&e);while (e!=flag){p=(LinkList)malloc(sizeof(LNode));p->data=e;r->next=p;r=p;scanf("%d",&e);}r->next=L;return L;}int LinkListLength(LinkList L){LinkList p;int j;p=L->next;j=0;while(p!=L){j++;p=p->next;}return j;}void LinkListPrint(LinkList L){LinkList p;p=L->next;printf("链表中的元素为:\n");while(p!=L){printf("%d ",p->data);p=p->next;}printf("\n");}int scan(){int d;printf("请选择你所要执行的单向链表的基本操作:\n1.插入元素;2.删除元素;3.访问元素.\n");printf("其他键退出程序……");printf("\n");scanf("%d",&d);return(d);}void main(){int quit=0;int i;ElemType e;LinkList L,p;L=CreatLinkList();while(!quit)switch(scan()){case 1:printf("请输入插入元素的位置和值(中间以空格或回车分隔):\n");scanf("%d%d",&i,&e);LinkListInsert(L,i,e);LinkListPrint(L);break;case 2:if(LinkListLength(L)==0)printf("链表已经为空,不能删除\n\n");else{printf("请输入待删除元素的位置:\n");scanf("%d",&i);LinkListDelete(L,i);}LinkListPrint(L);break;case 3:printf("请输入待查询元素在链表中的位置:");scanf("%d",&i);p=LocateLinkList(L,i);if(p)printf("链表中第%d个元素的值为:%d\n",i,p->data);elseprintf("查询位置不正确\n\n");break;default:quit=1;printf("操作结束!");printf("\n");}}4.双向链表的基本操作（双向链表的插入、删除、查找以及并表操作）#include<stdio.h>#include<malloc.h>#define flag 0typedef int status;typedef int ElemType;typedef struct DuLNode{ElemType data;struct DuLNode *prior;struct DuLNode *next;}DuLNode,*DuLinkList;DuLinkList InitDuLinkList(){DuLinkList L;L=(DuLinkList)malloc(sizeof(DuLNode));L->next=L->prior=NULL;return L;}DuLinkList CreatDuLinkList(){DuLinkList L=InitDuLinkList(),p,r;ElemType e;r=L;printf("请依次输入链表中的元素,输入0结束\n");scanf("%d",&e);while (e!=flag){p=(DuLinkList)malloc(sizeof(DuLNode));p->data=e;r->next=p;p->prior=r->next;r=p;scanf("%d",&e);}r->next=NULL;return L;}void ListInsert_DuL(DuLinkList L, int i, ElemType e){ DuLinkList p,s;int j;j=1;p=L;while(p&&j<i){p=p->next;j++;}if(p==NULL||j>i)printf("插入位置不正确\n");else {s=(DuLinkList)malloc(sizeof(DuLNode));s->data=e;s->next=p->next; p->next->prior=s;s->prior=p; p->next=s;printf("%d已插入到双向链表中\n",e); }}void ListDelete_DuL(DuLinkList L,int i) //删除元素{DuLinkList p,q;int j;j=1;p=L;while(p->next&&j<i){p=p->next;j++;}if(p->next==NULL)printf("删除位置不正确\n");else{q=p->next;p->next=q->next;q->next->prior=p;free(q);printf("第%d个元素已从链表中删除\n",i); }}void LinkListPrint_DuL(DuLinkList L){DuLinkList p;p=L->next;if(p==NULL) printf("双链表为空表\n");else{printf("链表中的元素为:\n");while(p!=NULL){printf("%d ",p->data);p=p->next;}}printf("\n");}int DuLinkListLength(DuLinkList L){DuLinkList p;int j;p=L->next;j=0;while(p!=NULL){j++;p=p->next;}return j;}DuLinkList LocateDuLinkList(DuLinkList L,int i) {DuLinkList p;int j;p=L->next;j=1;while(p!=NULL&&j<i)p=p->next; j++;}if (j==i)return p;else return NULL;}void Mergelist_L(DuLinkList La,DuLinkList Lb,DuLinkList Lc){DuLNode *pa,*pb,*pc,*p;pa=La->next;pb=Lb->next;Lc=La;pc=Lc;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;p=Lc->next;printf("合并结果:");while(p) {printf("%4d",p->data);p=p->next;}free(Lb);}int scan(){int d;printf("请选择你所要执行的双向链表的基本操作:\n1.插入元素;2.删除元素;3.访问元素;4.两个双向链表的合并.\n");printf("其他键退出程序……");printf("\n");scanf("%d",&d);return(d);}void main(){int quit=0;int i;ElemType e;DuLinkList L,p;DuLinkList La,Lb,Lc;L=CreatDuLinkList();while(!quit){switch(scan())case 1:printf("请输入插入元素的位置和值(中间以空格或回车分隔):\n");scanf("%d%d",&i,&e);ListInsert_DuL(L,i,e);LinkListPrint_DuL(L);break;case 2:if(DuLinkListLength(L)==0)printf("链表已经为空,不能删除\n\n");else{printf("请输入待删除元素的位置:\n");scanf("%d",&i);ListDelete_DuL(L,i);}LinkListPrint_DuL(L);break;case 3:printf("请输入待查询元素在链表中的位置:");scanf("%d",&i);p=LocateDuLinkList(L,i);if(p)printf("链表中第%d个元素的值为:%d\n",i,p->data);elseprintf("查询位置不正确\n\n");break;case 4:La=CreatDuLinkList();Lb=CreatDuLinkList();Mergelist_L( La, Lb, Lc);printf("\n");break;default:quit=1;printf("操作结束!");printf("\n");}}5.双向循环链表的基本操作（双向循环链表的插入、删除以及访问操作）#include<stdio.h>#include<malloc.h>#define flag 0typedef int status;typedef int ElemType;typedef struct DuLNode{ElemType data;struct DuLNode *prior;struct DuLNode *next;}DuLNode,*DuLinkList;DuLinkList InitDuLinkList(){DuLinkList L;L=(DuLinkList)malloc(sizeof(DuLNode));L->next=L; L->prior=L;return L;}DuLinkList CreatDuLinkList(){DuLinkList L=InitDuLinkList(),p,r;ElemType e;r=L;printf("请依次输入链表中的元素,输入0结束\n"); scanf("%d",&e);while (e!=flag){p=(DuLinkList)malloc(sizeof(DuLNode));p->data=e;r->next=p;p->prior=r->next;r=p;scanf("%d",&e);}r->next=L; L->prior=r;return L;}void ListInsert_DuL(DuLinkList L, int i, ElemType e){ DuLinkList p,s;int j;j=1;p=L;while(j<i){p=p->next;j++;}if(j>i)printf("插入位置不正确\n");else {s=(DuLinkList)malloc(sizeof(DuLNode));s->data=e;s->next=p->next; p->next->prior=s;s->prior=p; p->next=s;printf("%d已插入到双向循环链表中\n",e); }}void ListDelete_DuL(DuLinkList L,int i) //删除元素{DuLinkList p,q;int j;j=1;p=L;while(p->next!=L&&j<i){p=p->next;j++;}if(p->next==L)printf("删除位置不正确\n");else{q=p->next;p->next=q->next;q->next->prior=p;free(q);printf("第%d个元素已从双向循环链表中删除\n",i); }}void LinkListPrint_DuL(DuLinkList L){DuLinkList p;p=L->next;if(p->next==L) printf("双链表为空表\n");else{printf("链表中的元素为:\n");while(p!=L){printf("%d ",p->data);p=p->next;}}printf("\n");}int DuLinkListLength(DuLinkList L){DuLinkList p;int j;p=L->next;j=0;while(p->next!=L){j++;p=p->next;}return j;}DuLinkList LocateDuLinkList(DuLinkList L,int i){DuLinkList p;int j=1;p=L->next;while(p->next!=L&&j<i){p=p->next; j++;}if (j==i)return p;else return NULL;}int scan(){int d;printf("请选择你所要执行的双向链表的基本操作:\n1.插入元素;2.删除元素;3.访问元素.\n");printf("其他键退出程序……");printf("\n");scanf("%d",&d);return(d);}void main(){ int quit=0;int i,locate;ElemType e;DuLinkList L,p;L=CreatDuLinkList();while(!quit)switch(scan()){case 1:printf("请输入插入元素的位置和值(中间以空格或回车分隔):\n");scanf("%d%d",&i,&e);ListInsert_DuL(L,i,e);LinkListPrint_DuL(L);break;case 2:if(DuLinkListLength(L)==0)printf("链表已经为空,不能删除\n\n");else{printf("请输入待删除元素的位置:\n");scanf("%d",&i);ListDelete_DuL(L,i);}LinkListPrint_DuL(L);break;case 3:printf("请输入待查询元素在链表中的位置:");scanf("%d",&i);p=LocateDuLinkList(L,i);if(p)printf("链表中第%d个元素的值为:%d\n",i,p->data);elseprintf("查询位置不正确\n\n");break;default:quit=1;printf("操作结束!");printf("\n");}}【小结讨论】1.通过实验，我加深了对C的工作环境及其基本操作，进一步掌握了基本函数的调用以及使用方法。

一．实验名称1.线性表基本操作；2.处理约瑟夫环问题二．试验目的：1．熟悉C语言的上机环境，掌握C语言的基本结构。

2．定义单链表的结点类型。

3．熟悉对单链表的一些基本操作和具体的函数定义。

4．通过单链表的定义掌握线性表的链式存储结构的特点。

5．熟悉对单链表的一些其它操作。

三．实验内容1.编制一个演示单链表初始化、建立、遍历、求长度、查询、插入、删除等操作的程序。

2.编制一个能求解除约瑟夫环问题答案的程序。

实验一线性表表的基本操作问题描述：1. 实现单链表的定义和基本操作。

该程序包括单链表结构类型以及对单链表操作的具体的函数定义程序中的单链表（带头结点）结点为结构类型，结点值为整型。

/* 定义DataType为int类型*/typedef int DataType;/* 单链表的结点类型*/typedef struct LNode{DataType data;struct LNode *next;}LNode,*LinkedList;LinkedList LinkedListInit() //初始化单链表void LinkedListClear(LinkedList L) // 清空单链表int LinkedListEmpty(LinkedList L)//检查单链表是否为空void LinkedListTraverse(LinkedList L)// 遍历单链表int LinkedListLength(LinkedList L)//求单链表的长度/* 从单链表表中查找元素*/LinkedList LinkedListGet(LinkedList L,int i)/* 从单链表表中查找与给定元素值相同的元素在链表中的位置*/int LinkedListLocate(LinkedList L, DataType x)void LinkedListInsert(LinkedList L,int i,DataType x) //向单链表中插入元素/* 从单链表中删除元素*/void LinkedListDel(LinkedList L,DataType x)/* 用尾插法建立单链表*/LinkedList LinkedListCreat( )2. 约瑟夫环问题：任给正整数N和K，按下述方法可以得到1,2, …,n的一个置换，将数字1,2,…,n环形排列，按顺时针方向自1开始报数，报到K时输出该位置上的数字，并使其出列。

数据结构线性表试验报告（最终定稿）第一篇：数据结构线性表试验报告线性表上机实习1、实验目的（1）熟悉将算法转换为程序代码的过程。

（2）了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C 语言描述方法。

（3）熟练掌握顺序表的基本运算：查找、插入、删除等，掌握顺序表的随机存取特性。

（4）了解线性表的链式存储结构，熟练掌握线性表的链式存储结构的C语言描述方法。

（5）熟练掌握线性链表（单链表）的基本运算：查找、插入、删除等，能在实际应用中灵活选择适当的链表结构。

2、实验要求（1）熟悉顺序表的插入、删除和查找。

（2）熟悉单链表的插入、删除和查找。

3、实验内容: ① 顺序表（1）抽象数据类型定义typedef struct {TypeData data[maxsize];//容量为maxsize的静态顺手表int n;//顺序表中的实际元素个数}SeqList;//静态顺序表的定义在本次实验中，首先建立一个空的静态顺序表，然后键盘输入数据存入表中，然后进入菜单选择界面，通过不同的数字输入，实现对顺序表，删除，插入，查找，显示等操作。

（2）存储结构定义及算法思想在顺序表结构体的定义中，typedef int TypeData 为整型，存储结构如下：for(n=0;ncout<<“请输入线性表数据”<cin>>L.data[n];//顺序将数据存入顺序表}//其他存储与此类似，都是直接赋值与数组的某一位插入版块子函数：void insert(SeqList &L)//插入数据 {int a,b,c,k;cout<<“请输入插入的数及其插入的位置”<cin>>a>>b;if(b<=0||b>(L.n+1)){cout<<“不能在该位置插入”<k=L.data[b-1];L.data[b-1]=a;c=L.n;L.n=L.n+1;while(c>b){L.data[c]=L.data[c-1];c--;//通过循环，实现插入位置后的数据挨个往后移动一位}L.data[b]=k;} 顺序表的插入与删除操作类似，在插入与删除后，都要循环调整后面数组的每一位元素，同时记录数据元素的长度的标示符也要跟着改变。

HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY
数据结构
实验报告
实验项目实验一实验类别基础篇
学生姓名宋大超学生学号201501149 完成日期2016-10-9
指导教师袁科
实验成绩评阅日期
评阅教师
实验一线性表基本操作的编程实现
【实验目的】
线性表基本操作的编程实现
要求：
线性表基本操作的编程实现（2学时，验证型），掌握线性表的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、逆序、排序等操作，存储结构可以在顺序结构或链表结构中任选，可以完成部分主要功能，也可以用菜单进行管理完成大部分功能。

还鼓励学生利用基本操作进行一些更实际的应用型程序设计。

【实验性质】
验证性实验（学时数：2H）
【实验内容】
把线性表的顺序存储和链表存储的数据插入、删除运算其中某项进行程序实现。

建议实现键盘输入数据以实现程序的通用性。

为了体现功能的正常性，至少要编制遍历数据的函数。

【注意事项】
1.开发语言：使用C。

2.可以自己增加其他功能。

实验报告实验二线性表及其基本操作实验(2学时)实验目的：(1) 熟练掌握线性表ADT和相关算法描述、基本程序实现结构；(2) 以线性表的基本操作为基础实现相应的程序；(3) 掌握线性表的顺序存储结构和动态存储结构之区分。

实验内容：(类C算法的程序实现，任选其一。

具体要求参见教学实验大纲)(1)一元多项式运算的C语言程序实现(加法必做，其它选做)；(2) 有序表的合并；(3)集合的并、交、补运算；(4)约瑟夫问题的求解。

注：存储结构可以选用静态数组、动态数组、静态链表或动态链表之一。

对链表也可以采用循环链表（含单向或双向）。

实验准备：1) 计算机设备；2) 程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。

实验步骤：1.录入程序代码并进行调试和算法分析；2.编写实验报告。

实验过程：（一元多项式的加法）【算法描述】定义两个指针qa和qb，分别指向多项式A和多项式B当前进行比较的某个结点，然后比较2个结点中的指数项，则有以下三种结果：1、指针qa所指结点的指数值小于指针qb所指结点的指数值，则应摘取指针qa 所指的结点插入到“和多项式”链表当中去；2、指针qa所指结点的指数值大于指针qb所指结点的指数值，则应摘取指针qb 所指的结点插入到“和多项式”链表当中去；3、指针qa所指结点的指数值等于指针qb所指结点的指数值，则将两个结点的系数相加，若和数不等于零，则修改qa所指结点的系数值，同时释放qb所指结点。

反之，从多项式A的链表删除相应结点，并释放指针qa和qb所指结点。

【源程序】#include <stdlib.h>#include <stdio.h>typedef struct{float coef;int expn;}term;typedef struct LNode{term data;struct LNode *next;}LNode,*LinkList;typedef LinkList polynomial;int cmp(term a,term b){int flag;if (a.expn<b.expn) flag=-1;else if (a.expn==b.expn) flag=0;else flag=1;return flag;}void CreatPoly(polynomial *p,int m){int i;polynomial r,s;term para;(*p)=(LNode *)malloc(sizeof(LNode));r=(*p);for( i=0;i<m;i++){s=(LNode *)malloc(sizeof(LNode));printf("please input coef and expn:\n");scanf("%f %d",&para.coef,&para.expn);s->data.coef=para.coef;s->data.expn=para.expn;r->next=s;r=s;}r->next=NULL;}polynomial AddPoly(polynomial *pa,polynomial *pb) {polynomial newp,p,q,s,r;float sum;p=(*pa)->next;q=(*pb)->next;newp=(LNode *)malloc(sizeof(LNode));r=newp;while(p&&q){switch(cmp(p->data,q->data)){case -1:s=(LNode *)malloc(sizeof(LNode));s->data.coef=p->data.coef;s->data.expn=p->data.expn;r->next=s;r=s;p=p->next;break;case 0:sum=p->data.coef+q->data.coef;if(sum!=0.0){s=(LNode *)malloc(sizeof(LNode));s->data.coef=sum;s->data.expn=q->data.expn;r->next=s;r=s;}p=p->next;q=q->next;break;case 1:s=(LNode *)malloc(sizeof(LNode));s->data.coef=q->data.coef;s->data.expn=q->data.expn;r->next=s;r=s;q=q->next;break;}}while(p){s=(LNode *)malloc(sizeof(LNode));s->data.coef=p->data.coef;s->data.expn=p->data.expn;r->next=s;r=s;p=p->next;}while(q){s=(LNode *)malloc(sizeof(LNode));s->data.coef=q->data.coef;s->data.expn=q->data.expn;r->next=s;r=s;q=q->next;}r->next=NULL;return newp;}void Poly(polynomial p){polynomial s;s=p->next;while(s){printf("%.2fx^%d ",s->data.coef,s->data.expn);s=s->next;}printf("\n");}void main(){int m,n;polynomial p,q,newp;clrscr();printf("please input pa's item:\n");scanf("%d",&m);CreatPoly(&p,m);printf("please input pb's item:\n");scanf("%d",&n);CreatPoly(&q,n);Poly(p);Poly(q);printf("the finally answer:");Poly(AddPoly(&p,&q));}【程序结果与分析】分析：在编写过程中，出现了一些问题，如果输入的数过大，最终显示的结果就是一串地址值，后经过该进，就得到上述结果。

数据结构..实验报告线性表的基本操作数据结构实验报告线性表的基本操作1.引言本实验报告旨在介绍线性表的基本操作。

线性表是一种常见的数据结构，它是一组有限元素的有序集合，其中每个元素之间存在一个特定的顺序关系。

线性表的操作包括插入、删除、查找等，这些操作对于有效地管理和利用数据非常重要。

2.实验目的本实验的目的是通过实践理解线性表的基本操作，包括初始化、插入、删除、查找等。

通过编写相应的代码，加深对线性表的理解，并掌握相应的编程技巧。

3.实验内容3.1 初始化线性表初始化线性表是指创建一个空的线性表，为后续的操作做准备。

初始化线性表的方法有多种，如顺序表和链表等。

下面以顺序表为例进行说明。

顺序表的初始化包括定义表头指针和设置表的长度等操作。

3.2 插入元素插入元素是指将一个新的元素插入到线性表的指定位置。

插入元素有两种情况：插入到表的开头和插入到表的中间。

插入元素的操作包括移动其他元素的位置以腾出空间，并将新的元素插入到指定位置。

3.3 删除元素删除元素是指将线性表中的某个元素删除。

删除元素有两种情况：删除表的开头元素和删除表的中间元素。

删除元素的操作包括将被删除元素的前一个元素与后一个元素进行连接，断开被删除元素与表的联系。

3.4 查找元素查找元素是指在线性表中寻找指定的元素。

查找元素的方法有多种，如遍历线性表、二分查找等。

查找元素的操作包括比较目标元素与线性表中的元素进行匹配，直到找到目标元素或遍历完整个线性表。

4.实验步骤4.1 初始化线性表根据线性表的类型选择相应的初始化方法，如创建一个空的顺序表并设置表的长度。

4.2 插入元素输入要插入的元素值和插入的位置，判断插入的位置是否合法。

如果合法，移动其他元素的位置以腾出空间，将新的元素插入到指定位置。

如果不合法，输出插入位置非法的提示信息。

4.3 删除元素输入要删除的元素值，判断元素是否在线性表中。

如果在，则找到目标元素的前一个元素和后一个元素，进行连接删除操作。

数据结构--实验报告线性表的基本操作数据结构--实验报告线性表的基本操作一、引言本实验报告旨在通过实际操作，掌握线性表的基本操作，包括初始化、插入、删除、查找等。

线性表是最基本的数据结构之一，对于理解和应用其他数据结构具有重要的作用。

二、实验目的1·了解线性表的定义和基本特性。

2·掌握线性表的初始化操作。

3·掌握线性表的插入和删除操作。

4·掌握线性表的查找操作。

5·通过实验巩固和加深对线性表的理解。

三、线性表的基本操作1·初始化线性表线性表的初始化是将一个线性表变量设置为空表的过程。

具体步骤如下：（1）创建一个线性表的数据结构，包括表头指针和数据元素的存储空间。

（2）将表头指针指向一个空的数据元素。

2·插入元素插入元素是向线性表中指定位置插入一个元素的操作。

具体步骤如下：（1）判断线性表是否已满，如果已满则无法插入元素。

（2）判断插入位置是否合法，如果不合法则无法插入元素。

（3）将插入位置及其后面的元素都向后移动一个位置。

（4）将待插入的元素放入插入位置。

3·删除元素删除元素是从线性表中删除指定位置的元素的操作。

具体步骤如下：（1）判断线性表是否为空，如果为空则无法删除元素。

（2）判断删除位置是否合法，如果不合法则无法删除元素。

（3）将删除位置后面的元素都向前移动一个位置。

（4）删除最后一个元素。

4·查找元素查找元素是在线性表中查找指定元素值的操作。

具体步骤如下：（1）从线性表的第一个元素开始，逐个比较每个元素的值，直到找到目标元素或遍历完整个线性表。

（2）如果找到目标元素，则返回该元素的位置。

（3）如果未找到目标元素，则返回找不到的信息。

四、实验步骤1·初始化线性表（1）定义线性表的数据结构，包括表头指针和数据元素的存储空间。

（2）将表头指针指向一个空的数据元素。

2·插入元素（1）判断线性表是否已满。

实验二线性表及其实现一．实验目的及要求（1）熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现，以线性表的各种操作（建立、插入、删除等）的实现为实验重点；（2）通过本次实验帮助学生加深对顺序表、链表的理解，并加以应用；（3）掌握循环链表和双链表的定义和构造方法二.实验内容：（1）编程实现线性表两种存储结构（顺序存储、链式存储）中的基本操作的实现（线性表的创建、插入、删除和查找等），并设计一个菜单调用线性表的基本操作。

（2）建立一个按元素递增有序的单链表L，并编写程序实现：a）将x插入其中后仍保持L的有序性；b）将数据值介于min和max之间的结点删除，并保持L的有序性；c）将单链表L逆置并输出；（3）编程实现将两个按元素递增有序的单链表合并为一个新的按元素递增的单链表。

三.实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现线性表两种存储结构（顺序存储、链式存储）中的基本操作的实现（线性表的创建、插入、删除和查找等），并设计一个菜单调用线性表的基本操作。

➢程序代码：顺序存储：头文件：#define INIT_SIZE 100#define INCREMENT 10#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct{ElemType *elem;int length;int listsize;}Sq;Status Init_Sq(Sq &L);Status Insert_Sq(Sq &L,int i,ElemType e);Status Delete_Sq(Sq &L,int i,ElemType &e);主函数：#include"stdio.h"#include"1.h"#include"stdlib.h"int main(){Sq L;printf("是否建立顺序表？\n");printf("1、建立\n");printf("2、退出程序\n");int a;//选择是否建立scanf("%d",&a);switch(a){case 1:Init_Sq(L);break;case 2:printf("程序结束！\n");exit(OVERFLOW);default:printf("输入错误！\n");}printf("请输入要放入顺序表中的元素个数(不要超过100)\n");scanf("%d",&L.length);int i;//进行用户输入循环printf("请输入具体元素\n");for(i=0;i<L.length;i++){scanf("%d",&L.elem[i]);}int b;//选择操作do{printf("请选择下列操作\n");printf("1、向表中添加元素\n");printf("2、删除表中某一元素\n");printf("3、退出程序\n");scanf("%d",&b);switch(b){case 1:ElemType x;//新元素int c;//新元素位置printf("请输入要添加的元素，和添加的位置(空格隔开)\n");scanf("%d%d",&x,&c);Insert_Sq(L,c,x);int j;//新表输出循环printf("新表为：\n");for(j=0;j<L.length;j++){printf("%d ",L.elem[j]);}printf("\n");break;case 2:int d;//需要删除元素的位置ElemType y;//被删除的元素printf("请输入删除元素的位置\n");scanf("%d",&d);Delete_Sq(L,d,y);printf("被删除的元素是%d\n",y);printf("剩下的元素为：\n");int f;//输出循环for(f=0;f<L.length;f++){printf("%d ",*(L.elem+f));}printf("\n");break;case 3:printf("程序结束！\n");exit(OVERFLOW);default:printf("输入出错！\n");}}while(b!=3);return 0;}功能函数：#include"stdio.h"#include"stdlib.h"#include"1.h"Status Init_Sq(Sq &L){L.elem=(ElemType *)malloc(INIT_SIZE*sizeof(ElemType));if(!L.elem) exit(OVERFLOW);L.length=0;L.listsize=INIT_SIZE;return OK;}Status Insert_Sq(Sq &L,int i,ElemType e){if(L.length==100){int *newpase;newpase=(ElemType *)realloc(L.elem,(L.length+INCREMENT)*sizeof(ElemType));if(!newpase) exit(OVERFLOW);L.elem=newpase;L.listsize+=INCREMENT;}if(i<1||i>L.length+1){return ERROR;}L.length+=1;int b=L.length;//用于循环while(i<=b){L.elem[b]=L.elem[b-1];b--;}L.elem[i-1]=e;return OK;}Status Delete_Sq(Sq &L,int i,ElemType &e){if(i<1||i>L.length+1){return ERROR;}e=L.elem[i-1];int j;for(j=i-1;j<L.length-1;j++){L.elem[j]=L.elem[j+1];}L.length-=1;return OK;}链式存储：头文件：#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct LNode{ElemType data;struct LNode *next;}LNode,*LinkList;void Create_L(int n,LinkList &L);Status Insert_L(LinkList &L,int i,ElemType e); Status Delete_L(LinkList &L,int i,ElemType &e); Status GetElem_L(LinkList L,int i,ElemType &e);主函数：#include"stdio.h"#include"1.h"int main(){printf("是否建立链表\n");int a;//选择printf("1、建立\n");printf("2、退出程序\n");scanf("%d",&a);switch(a){case 1:LinkList L;printf("请输入链表长度（不计算头结点）\n");int n;//数据容纳度scanf("%d",&n);Create_L(n,L);int b;//选择功能printf("请选择以下功能：\n");do{printf("1、查找某位置元素\n");printf("2、在某位置插入元素\n");printf("3、删除某位置元素\n");printf("4、结束程序\n");scanf("%d",&b);switch(b){case 1:{printf("请输入查找位置\n");int c;//查找位置ElemType d;//数据容器scanf("%d",&c);if(c>n){printf("该位置大于数据个数，请重新选择\n");break;}GetElem_L(L,c,d);printf("第%d个数据为：%d\n",c,d);break;}case 2:{printf("请输入在什么位置插入什么数据（空格隔开）\n");int f,g;//位置、数据scanf("%d %d",&f,&g);Insert_L(L,f,g);printf("此时的数据为：\n");int h;n=n+1;LinkList l=L;for(h=0;h<n;h++){printf("%d ",l->next->data);l=l->next;}printf("\n");break;}case 3:{printf("请输入需要删除的位置\n");int m;ElemType o;scanf("%d",&m);Delete_L(L,m,o);n=n-1;printf("此时的数据还有：\n");int q;LinkList r=L;for(q=0;q<n;q++){printf("%d ",r->next->data);r=r->next;}printf("\n");break;}case 4:printf("程序结束\n");break;default:printf("输入出错\n");}}while(b!=4);break;case 2:printf("程序退出\n");break;default:printf("输入错误\n");}}#include"1.h"#include"stdio.h"#include"stdlib.h"void Create_L(int n,LinkList &L){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;printf("请逆序输入相应个数的数据\n");int i;//用于循环LinkList p;for(i=n;i>0;i--){p=(LinkList)malloc(sizeof(LNode));scanf("%d",&p->data);p->next=L->next;L->next=p;}}Status GetElem_L(LinkList L,int i,ElemType &e) {int j;//用于循环LinkList p=L;if(p){for(j=0;j<i;j++){p=p->next;}e=p->data;}return OK;}Status Insert_L(LinkList &L,int i,ElemType e) {LinkList p;p=L;int j=0;while(p&&j<i-1){p=p->next;}if(!p||j>i-1)return ERROR;LinkList s;s=(LinkList) malloc (sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return OK;}Status Delete_L(LinkList &L,int i,ElemType &e) {LinkList p=L;int j=0;while(p->next&&j<i-1){p=p->next;j++;}if(!(p->next)||j>i-1)return ERROR;LinkList q;q=p->next;p->next=q->next;e=q->data;printf("被删除的元素为：%d\n",e);free(q);return OK;}➢运行结果：（2）建立一个按元素递增有序的单链表L，并编写程序实现：a）将x插入其中后仍保持L的有序性；b）将数据值介于min和max之间的结点删除，并保持L 的有序性；c）将单链表L逆置并输出；程序代码部分：头文件：#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -1#define INFEASIBLE -2typedef int ElemType;typedef int Status;typedef struct LNode{ElemType data;struct LNode *next;}LNode,*LinkList;Status Create(LinkList &L,int n);Status Insert(LinkList &L,ElemType e,int n);Status Delete(LinkList &L,int min,int max,int &n);Status Reverse(LinkList L,int n);主函数：#include"stdio.h"#include"1.h"int main(){printf("是否建立单链表？\n");printf("1、建立\n");printf("2、不建立并结束程序\n");int a;//判断是否建立链表scanf("%d",&a);switch(a){case 1:{LinkList L,p;printf("请确定单链表的节点个数\n");int node_num;//节点个数scanf("%d",&node_num);Create(L,node_num);p=L;printf("现在的单链表为：\n");for(int i=0;i<node_num;i++){p=p->next;printf("%d ",p->data);}printf("\n");printf("请选择下列操作\n");int b;//选择操作do{printf("1、插入一个元素\n");printf("2、删除某个范围内的元素（不删除上下限）\n");printf("3、逆置单链表中的元素\n");printf("4、结束程序\n");scanf("%d",&b);switch(b){case 1:{int insert;//插入的元素printf("请输入要插入的元素\n");scanf("%d",&insert);Insert(L,insert,node_num);LinkList p=L;printf("此时单链表中的元素为：\n");for(int i=0;i<node_num+1;i++){printf("%d ",p->next->data);p=p->next;}printf("\n");}node_num+=1;break;case 2:{printf("请输入删除范围的上下限（空格隔开）\n");int min,max;scanf("%d %d",&min,&max);printf("被删除的元素有：\n");Delete(L,min,max,node_num);printf("此时的单链表元素有：\n");LinkList p=L;for(int i=0;i<node_num;i++){printf("%d ",p->next->data);p=p->next;}printf("\n");}break;case 3:{Reverse(L,node_num);}break;case 4:printf("程序结束！\n");break;default:printf("输入错误！\n");}}while(b!=4);}break;case 2:printf("程序结束！\n");break;default: printf("输入错误！\n");}}功能函数：#include"stdio.h"#include"stdlib.h"#include"1.h"//顺序输入N个元素建立单链表与书上30页的2.10是不同的方法Status Create(LinkList &L,int n){L=(LinkList) malloc (sizeof(LNode));if(!L) exit(OVERFLOW);L->next=NULL;LinkList q=L;printf("请输入具体元素\n");for(int i=0;i<n;i++){LinkList p=(LinkList) malloc (sizeof(LNode));scanf("%d",&p->data);//与30页不同之处q->next=p;p->next=NULL;q=q->next;}return OK;}Status Insert(LinkList &L,ElemType e,int n){LinkList p;p=L;LinkList s=(LinkList) malloc (sizeof(LNode));if(!s) exit(OVERFLOW);s->data=e;for(int i=0;i<n;i++){if(e<=p->next->data){s->next=p->next;p->next=s;break;}p=p->next;}if(p->next==NULL){p->next=s;s->next=NULL;}return OK;}Status Delete(LinkList &L,int min,int max,int &n){ElemType e;//显示被删除的元素int a=n;//判别n是否变化LinkList p=L;for(int i=0;i<a;i++){if(p->next!=NULL){if(min<p->next->data&&max>p->next->data){n--;LinkList q;q=p->next;p->next=q->next;e=q->data;printf("%d ",e);free(q);}else if(p->next->data>=max)break;//如果一个元素大于等于max,说明后面的元素一定大于等于max，就没必要进行比较了}p=p->next;}if(n==a)//说明元素没变化,是min大于等于所有元素（或者max小于等于所有元素）造成的结果{printf("单链表在该范围内没有元素\n");return ERROR;}printf("\n");return OK;}Status Reverse(LinkList L,int n){LinkList w,p,q=L;//用于承载逆置的单链表q=q->next;w=(LinkList) malloc (sizeof(LNode));w->next=NULL;for(int i=n;i>0;i--){p=(LinkList) malloc (sizeof(LNode));p->data=q->data;q=q->next;p->next=w->next;w->next=p;}printf("逆置后的单链表中元素为：\n"); LinkList y;y=w;for(int j=0;j<n;j++){y=y->next;printf("%d ",y->data);}printf("\n");return OK;}➢运行结果：（3）编程实现将两个按元素递增有序的单链表合并为一个新的按元素递增的单链表。

数据结构--实验报告线性表的基本操作数据结构实验报告[引言]在本次实验中,我们将学习线性表的基本操作,包括插入、删除、查找等。

通过实践操作,加深对线性表的理解和掌握。

[实验目的]1．学习线性表的基本概念和操作。

2.熟悉线性表的插入、删除和查找等基本操作。

3.掌握线性表的实现方式及其相应的算法。

［实验内容]１.线性表的定义与表示1．1 线性表的定义1.2 线性表的顺序存储结构１.3 线性表的链式存储结构2.线性表的基本操作２．１初始化线性表2.２判断线性表是否为空2.3 插入操作２.3.1 在指定位置插入元素2.3.2 在表尾插入元素2．4 删除操作2．4.1 删除指定位置的元素2．４．2 删除指定值的元素2．5 查找操作2.5.1 按位置查找元素2．5.2 按值查找元素２．6 修改操作2．６．１修改指定位置的元素 2.6.2 修改指定值的元素2.7 清空线性表2．8 销毁线性表[实验步骤]1.初始化线性表1.1 创建一个空的线性表对象１.2 初始化线性表的容量和长度2.插入操作2.１在指定位置插入元素2.1.1 检查插入位置的合法性2.1.2 将插入位置后的元素依次后移2.1．３在指定位置插入新元素2.2 在表尾插入元素２.2．1 将表尾指针后移2.2.2 在表尾插入新元素３.删除操作3.1 删除指定位置的元素３.1.1 检查删除位置的合法性3.１．2 将删除位置后的元素依次前移3.1.3 修改线性表的长度3.2 删除指定值的元素3.2.1 查找指定值的元素位置3.２.２调用删除指定位置的元素操作4.查找操作４.1 按位置查找元素4．1．1 检查查找位置的合法性4.1.2 返回指定位置的元素4.2 按值查找元素4.2．1 从头到尾依次查找元素4.2．2 返回第一个匹配到的元素5.修改操作5.１修改指定位置的元素５.１.1 检查修改位置的合法性5.1.２修改指定位置的元素值5.２修改指定值的元素5.2．1 查找指定值的元素位置5．２．２调用修改指定位置的元素操作6.清空线性表6．1 设置线性表长度为07.销毁线性表７.1 释放线性表的内存空间[实验结果]使用线性表进行各种基本操作的测试,并记录操作的结果和运行时间。

数据结构线性表实验报告数据结构线性表实验报告实验目的：本次实验主要是为了学习和掌握线性表的基本操作和实现方式。

通过实验，我们可以加深对线性表的理解，并能够熟悉线性表的基本操作。

实验设备与环境：本次实验所需的设备包括计算机和编程环境。

我们选择使用C语言来实现线性表的操作，并在Visual Studio Code编程软件中进行编写和调试。

实验内容：1.线性表的定义和基本操作1.1 线性表的定义：线性表是一种有序的数据结构，其中的元素按照一定的顺序存储，可以插入、删除和访问元素。

1.2 线性表的基本操作：1.2.1 初始化线性表：创建一个空的线性表。

1.2.2 判断线性表是否为空：判断线性表是否不含有任何元素。

1.2.3 获取线性表的长度：返回线性表中元素的个数。

1.2.4 在线性表的指定位置插入元素：在线性表的第i个位置插入元素x，原第i个及其之后的元素依次后移。

1.2.5 删除线性表中指定位置的元素：删除线性表中第i个位置的元素，原第i+1个及其之后的元素依次前移。

1.2.6 获取线性表中指定位置的元素：返回线性表中第i个位置的元素的值。

1.2.7 清空线性表：将线性表中的元素全部删除，使其变为空表。

2.线性表的顺序存储结构实现2.1 线性表的顺序存储结构：使用数组来实现线性表的存储方式。

2.2 线性表的顺序存储结构的基本操作：2.2.1 初始化线性表：创建一个指定长度的数组，并将数组中的每个元素初始化为空值。

2.2.2 判断线性表是否为空：判断线性表的长度是否为0。

2.2.3 获取线性表的长度：返回线性表数组的长度。

2.2.4 在线性表的指定位置插入元素：将要插入的元素放入指定位置，并将原位置及其之后的元素依次后移。

2.2.5 删除线性表中指定位置的元素：将指定位置的元素删除，并将原位置之后的元素依次前移。

2.2.6 获取线性表中指定位置的元素：返回指定位置的元素的值。

2.2.7 清空线性表：将线性表数组中的每个元素赋空值。