数据结构实验线性表及其应用

实验日期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的工作环境及其基本操作，进一步掌握了基本函数的调用以及使用方法。

课程题目：数据结构试验学院：班级：姓名：学号：实验题目：线性表的应用实验内容：分数统计实验目的：掌握线性表的概念及原理，运用线性表的原理完成实验题目中的内容。

实验要求：为了使学生更好的掌握与理解课堂上老师所讲的概念与原理，实验前每个学生要认真预习所做的实验内容及编写源程序代码（写在纸上与盘中均可），以便在实验课中完成老师所布置的实验内容。

实验学时：4学时设计原理：本实验的核心部分为对学生成绩从两个角度进行分析，既对学生的成绩进行了排名、求出学生成绩的平均分和分出学生成绩的数值段。

为了处理学生成绩这些数据，首先必须建立一个新的线性表，新表为空，然后经由input函数程序的执行使得学生的成绩可以输入到计算机中，从键盘输入程序所提示的学生人数后，新线性表的长度得以确定，再通过循环命令语句的调用将全部学生的成绩输入。

输入后，调用output函数处理线性表中的数据，通过调用条件语句和设置变量存储次次数的累加，从而在屏幕上输出各个分数段的人数。

这之后，通过冒泡排序法处理学生成绩这些数据，得出结果后，在调用循环语句命令将结果按顺序输出。

然后再对这些数据进行求平均值的运算，处理后输出。

详细程序清单及注释说明：#include<stdio.h>#include<malloc.h>#define list_init_size 100#define listincrement 10typedef struct{int *elem; //存储空间基址int length; //当前长度int listsize; //当前分配的存储空间(以sizeof(ElemType)为单位) }sqlist;void initlist_sq(sqlist &l) //创建一个空的线性表{l.elem=(int *)malloc(list_init_size*sizeof(int));l.length=0; //空表长度为0l.listsize=list_init_size; //初始存储容量}void input(sqlist &l){//输入学生的总人数和每个人的成绩int a,b,c;loop1:printf("输入学生人数：");scanf("%d",&b);if(b<=0){printf("输入错误，请重新输入！！\n");goto loop1; //输入错误时，重新输入}printf("\n");l.length=l.length+b; //由输入的值确定线性表的长度for(a=0;a<b;a++){loop:printf("输入第%d名学生的成绩：",a+1);scanf("%d",&c);l.elem[a]=c;if(c<0 || c>100){printf("输入错误，请重新输入！！\n");goto loop; //输入错误时，重新输入}}}void output(sqlist &l){//输出学生的成绩信息printf("\n");int i,a=0,q=0,w=0,e=0,r=0,t=0,y=0;for(i=0;i<l.length;i++){a=l.elem[i]/10;switch(a) //对成绩分段{case 10:q++;break;case 9:w++;break;case 8:e++;break;case 7:r++;break;case 6:t++;break;default:y++;break;}}printf("成绩为100有%d人\n",q);printf("成绩为90~99有%d人\n",w);printf("成绩为80~89有%d人\n",e);printf("成绩为70~79有%d人\n",r);printf("成绩为60~69有%d人\n",t);printf("不及格的有%d人\n\n",y);}void order(sqlist &l){//对成绩进行排序int i,j,k;for(i=0;i<l.length;i++)for(j=0;j<l.length-i;j++)if(l.elem[j]<l.elem[j+1]){k=l.elem[j];l.elem[j]=l.elem[j+1];l.elem[j+1]=k;}printf("经过排序：\n");for(i=0;i<l.length;i++){printf("第%d名成绩为:%d\n",i+1,l.elem[i]);}}void average(sqlist &l){//求出平均成绩int i;float k=0,j=0;for(i=0;i<l.length;i++){j=j+l.elem[i];}k=j/l.length;printf("平均分为：%5.5f\n",k); }void main(){printf("分数统计\n\n");sqlist l;initlist_sq(l);input(l);output(l);order(l);average(l);}运行与测试及结果：在输入错误情况下：试验中所遇到的问题及解决办法：①、实验当中曾经出现数据结果为乱码的现象，后经查找，原因是两个for循环当中的变量i，j顺序颠倒，从而出现了指针没有指向相应的数据结果，而是指向了未知位置的数据。

实验报告课程名称____数据结构上机实验__________ 实验项目______线性表的应用 ____________实验仪器________PC机___________________系别_____电子信息与通信学院___专业________ ___班级/学号______ __学生姓名______ ___________实验日期_______________________成绩_______________________指导教师_______________________实验一.线性表的应用1.实验目的：掌握线性链表的存储、运算及应用。

利用链表实现一元多项式计算。

2.实验内容：1)编写函数，实现用链表结构建立多项式；2)编写函数，实现多项式的加法运算；3)编写函数，实现多项式的显示；4)测试：编写主函数，它定义并建立两个多项式，显示两个多项式，然后将它们相加并显示结果。

变换测试用的多项式，检查程序的执行结果。

选做内容：修改程序，选择实现以下功能：5)多项式求值：编写一个函数，根据给定的x值计算并返回多项式f(x)的值。

测试该函数（从终端输入一个x的值，调用该函数并显示返回结果）。

6)多项式相减：编写一个函数，求两个多项式相减的多项式。

7)多项式相乘：编写一个函数，求两个多项式的乘积多项式。

3.算法说明：1)多项式的建立、显示和相加算法见讲义。

可修改显示函数，使输出的多项式更符合表达规范。

2)多项式减法：同次项的系数相减（缺项的系数是0）。

例如a(x)=-5x2+2x+3，b(x)= -4x3+3x，则a(x)-b(x)=4x3-5x2-x+3。

提示：a(x)-b(x) = a(x)+(-b(x))。

3)多项式乘法：两个多项式的相乘是“系数相乘，指数相加”。

算法思想是用一个多项式中的各项分别与另一个多项式相乘，形成多个多项式，再将它们累加在一起。

例如，a(x)=-5x2+2x+3，b(x)=-4x3+3x，则a(x)*b(x) = (-4x3)*(-5x2+2x+3)+(3x)*(-5x2+2x+3)= (20x5-8x4-12x3) + (-15x3+6x2+9x) =20x5-8x4-27x3+6x2+9x。

实验报告——线性表应用一、实验目的用单链表储存一元多项式，并实现两个多项式的相加运算。

二、实验内容1.先创建链表，存储多项式；2.输出多项式；3.两个多项式相加；4.输出多项式。

三、程序代码#include <stdio.h>#include <stdlib.h>#include <math.h>//一元多项式链式储存的节点结构typedef struct Polynode{float coef;int exp;struct Polynode * next;} Polynode , * Polylist;//建立一元多项式的链表Polylist polycreate(){Polynode * head,* rear,* s;float c;int e;head=(Polynode* )malloc(sizeof(Polynode));rear=head;scanf("%f,%d",&c,&e);while(c!=0){s=(Polynode * )malloc(sizeof(Polynode));s->coef=c;s->exp=e;rear->next=s;rear=s;scanf("%f,%d",&c,&e);}rear->next=NULL;return(head);}//输出多项式void print(Polynode*L){Polynode*p;p=L->next;printf("a=");if(p&&p->coef!=0)printf("%.2f*x^%d",p->coef,p->exp);while(p->next!=NULL){if((p->next->coef)>0&&p)printf("+");elseprintf("-");p=p->next;printf("%.2f*x^%d",fabs(p->coef),p->exp);}}//多项式相加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);}}{tail ->next=q;tail=q;q=q->next;}}if(p!=NULL)tail->next=p;elsetail->next=q;}void main(){Polynode*a,*b;printf("输入a的系数和指数:\n");a = polycreate();print(a);printf("\n");printf("输入b的系数和指数:\n");b = polycreate();print(b);printf("\n");polyadd(a,b);printf("两个多项式的和为:\n");print(a);}四、实验结果五、实验过程中遇到的问题及处理方法程序运行时，在中文状态下输入“，”回车后就不能再输入了，应在英文状态下输入“,”。

数据结构实验报告一实验名称:线性表及其实现栈和队列及其应用1 实验目的及实验要求1.线性表目的要求：（1）熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现，以线性表的各种操作（建立、插入、删除等）的实现为实验重点；（2）通过本次实验帮助学生加深对顺序表、链表的理解，并加以应用；（3）掌握循环链表和双链表的定义和构造方法2.栈和队列目的要求：（1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们；（2）本实验训练的要点是“栈”的观点及其典型用法；（3）掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。

2实验内容及实验步骤（附运行结果截屏）1.线性表实验内容：（1）编程实现线性表两种存储结构（顺序存储、链式存储）中的基本操作的实现（线性表的创建、插入、删除和查找等），并设计一个菜单调用线性表的基本操作。

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

注：（1）为必做题，（2）~（3）选做。

2.栈和队列实验内容：（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）；（2）应用栈的基本操作，实现数制转换（任意进制）；（3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）；（4）利用栈实现任一个表达式中的语法检查（括号的匹配）。

（5）利用栈实现表达式的求值。

注：（1）～（2）必做，（3）～（5）选做。

实验步骤：先编写线性表和栈和队列的类模板，实现各自的基础结构，之后按照要求编写适当的函数方法（公共接口），最后完成封装。

编写主函数直接调用即可。

核心代码：//LinearList.h 顺序表//类的声明1.template<class T>2.class LinearList3.{4.public:5.LinearList(int sz = default_size);6.~LinearList();7.int Length()const; //length of the linear8.int Search(T x)const; //search x in the linear and return its order number9.T GetData(int i)const; //get i th order's data10.bool SetData(int i,T x); //change i th order's data to x11.bool DeleteData(int i);12.bool InsertData(int i,T x);13.void output(bool a,int b,int c); //print the linear14.void ReSize(int new_size);15.16.private:17.T *data;18.int max_size,last_data;19.};//构造函数1.template<class T>2.LinearList<T>::LinearList(int sz)3.{4.if(sz>0)5.{6.max_size = sz;st_data=-1;8.data=new T[max_size];9.if(data == NULL)10.{11.cerr<<"Memory creat error!"<<endl;12.exit(1);13.}14.}15.else16.{17.cerr<<"Size error!"<<endl;18.exit(1);19.}20.}//Qlist.h 链式表//模板类的声明1.template<class T>2.struct LinkNode3.{4.T data;5.LinkNode<T> *link;6.LinkNode(LinkNode<T> *ptr = NULL)7.{8.link = ptr;9.}10.LinkNode(const T item,LinkNode<T> *ptr = NULL)11.{12.data = item;13.link = ptr;14.}15.};16.17.template<class T>18.class Qlist: public LinkNode<T>19.{20.public:21.Qlist();22.Qlist(const T x);23.Qlist(Qlist<T>&L);24.~Qlist();25.void MakeEmpty();26.int Length()const; //length of the linear27.int Search(T x)const; //search x in the linear and return its order number28.LinkNode<T> *Locate(int i);29.T GetData(int i); //get i th order's data30.bool SetData(int i,T x); //change i th order's data to x31.bool DeleteData(int i);32.bool InsertData(int i,T x);33.void output(bool a,int b,int c); //print the linear34.35.protected:36.LinkNode<T> *first;37.};//构造函数1.template<class T>2.Qlist<T>::Qlist(Qlist<T>&L)3.{4.T value;5.LinkNode<T>*src = L.getHead();6.LinkNode<T>*des = first = new LinkNode<T>;7.while(src->link != NULL)8.{9.value = src->link->data;10.des->link = new LinkNode<T>(value);11.des = des->link;12.src = src->link;13.}14.des->link = NULL;15.}截屏：3 实验体会（实验遇到的问题及解决方法）刚开始的时候本想先写线性表的类模板然后分别进行继承写顺序表和链式表甚至是以后的栈和队列。

实验一线性表及其应用一、实验目的1.熟悉C语言的上机环境，进一步掌握C语言的构造特点。

2.掌握线性表的顺序存储构造的定义及C语言实现。

3.掌握线性表的链式存储构造——单链表的定义及C语言实现。

4.掌握线性表在顺序存储构造即顺序表中的各种根本操作。

5.掌握线性表在链式存储构造——单链表中的各种根本操作。

二、实验容1.顺序线性表的建立、插入及删除。

2.链式线性表的建立、插入及删除。

三、实验步骤1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。

2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。

3.建立一个带头结点的单链表，结点的值域为整型数据。

要求将用户输入的数据按尾插入法来建立相应单链表。

四、实现提示1.由于C语言的数组类型也有随机存取的特点，一维数组的机表示就是顺序构造。

因此，可用C语言的一维数组实现线性表的顺序存储。

在此，我们利用C语言的构造体类型定义顺序表：#define MAXSIZE 1024typedef int elemtype; /* 线性表中存放整型元素*/typedef struct{ elemtype vec[MAXSIZE];int len; /* 顺序表的长度*/}sequenlist;将此构造定义放在一个头文件sqlist.h里，可防止在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。

2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序〔顺序表中元素的次序〕的区别。

3.单链表的结点构造除数据域外，还含有一个指针域。

用C语言描述结点构造如下：typedef int elemtype;typedef struct node{ elemtype data; //数据域struct node *next; //指针域}linklist;注意结点的建立方法及构造新结点时指针的变化。

第二章线性表及其应用【实验目的】1. 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；2. 以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；3. 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；4. 通过本章实验帮助学生加深对C语言的使用（特别是函数的参数调用、指针类型的应用和链表的建立等各种基本操作）。

第一节知识准备一、线性表的逻辑结构线性表是由一组具有相同特性的数据元素组成的有限序列。

至于每个数据元素，它可以是一个数，一个符号，也可以是一页书，甚至更复杂的信息。

例如：26个英文字母构成一个线性表（A，B，C，…，Y，Z）一串数字构成另一个线性表（45，45，32，65，123）每个数据元素可以由若干数据项组成，常把此数据元素称为记录。

能唯一标识一个记录的数据项的值称为关键字。

如：一个学校的学生情况表如表2-1所示，表中每个学生的情况为一个记录，它由学号、姓名、性别、年龄、年级等五个数据项组成。

学号姓名性别年龄年级96001 张平女 21 大二96002 王极男 20 大一96003 膨磊男 23 大三96004 严正英女 19 大一96005 李强男 20 大二综上所述，线性表有如下特性：1．除第一个和最后一个元素以外，每个元素有且仅有一个直接前趋和一个直接后继；第一个结点只有直接后继，最后一个结点只有直接前趋。

2．线性表中的每个数据元素，其数据类型是一致的。

3．数据元素之间的相对位置是线性的，结构中的数据元素之间存在一个对一个的关系。

二、线性表的顺序表示和实现计算机的内存是由有限多个存储单元组成的，每个存储单元都有对应的整数地址，各存储单元的地址是连续编号的。

对于一个线性表，如果用一组连续的存储单元依次存放它的各个数据元素，这就是线性表的顺序分配。

也就是说，在线性表的顺序分配结构中，逻辑结构上相邻的数据元素，其物理位置也是相邻的。

若一个数据元素只占用一个存储单元，则这种分配方式如图2-1所示。

数据结构实验报告线性表数据结构实验报告：线性表引言：数据结构是计算机科学中的重要概念，它涉及到如何组织和存储数据，以及如何有效地操作和管理这些数据。

线性表是数据结构中最基本的一种，它是一种有序的数据元素集合，其中的元素之间存在着一对一的关系。

一、线性表的定义和特点线性表是由n个数据元素组成的有限序列，其中n为表的长度。

这些数据元素可以是相同类型的，也可以是不同类型的。

线性表中的数据元素按照一定的顺序排列，并且每个数据元素都有唯一的前驱和后继。

线性表的特点有以下几个方面：1. 数据元素之间是一对一的关系，即每个数据元素只有一个直接前驱和一个直接后继。

2. 线性表中的元素是有序的，每个元素都有一个确定的位置。

3. 线性表的长度是有限的，它的长度可以是0，也可以是任意正整数。

二、线性表的实现方式线性表可以使用不同的数据结构来实现，常见的实现方式有数组和链表。

1. 数组实现线性表：数组是一种连续存储的数据结构，它可以用来存储线性表中的元素。

数组的优点是可以快速访问任意位置的元素，但是插入和删除操作需要移动其他元素，效率较低。

2. 链表实现线性表：链表是一种非连续存储的数据结构，它通过指针将线性表中的元素链接起来。

链表的优点是插入和删除操作简单高效，但是访问任意位置的元素需要遍历链表，效率较低。

三、线性表的基本操作线性表的基本操作包括插入、删除、查找和修改等。

1. 插入操作：插入操作用于向线性表中插入一个新元素。

具体步骤是先将插入位置后面的元素依次后移，然后将新元素插入到指定位置。

2. 删除操作：删除操作用于从线性表中删除一个元素。

具体步骤是先将删除位置后面的元素依次前移，然后将最后一个元素删除。

3. 查找操作：查找操作用于在线性表中查找指定元素。

具体步骤是从线性表的第一个元素开始逐个比较，直到找到匹配的元素或者到达线性表的末尾。

4. 修改操作：修改操作用于修改线性表中的某个元素的值。

具体步骤是先查找到要修改的元素，然后将其值更新为新值。

数据结构实验线性表及其应用在计算机科学的领域中，数据结构是一门极其重要的基础学科，它为我们有效地组织和管理数据提供了理论和方法。

而线性表作为一种常见且基础的数据结构，在实际的程序设计和算法应用中有着广泛的应用。

线性表是一种最基本的数据结构，它是由零个或多个数据元素组成的有限序列。

在这个序列中，每个元素都有其特定的位置和值。

从存储结构上来看，线性表可以分为顺序存储和链式存储两种方式。

顺序存储的线性表，就像是一排紧密排列的格子，每个格子里存放着一个数据元素。

这种存储方式的优点是可以随机访问表中的任意元素，时间复杂度为 O(1)。

比如说，如果我们要获取顺序表中第 5 个元素的值，只需要通过简单的计算就能直接找到对应的位置并获取其值。

然而，顺序存储也有它的不足之处。

当需要插入或删除元素时，可能需要移动大量的元素，以保持数据的连续性，这会导致时间复杂度较高，为 O(n)。

相比之下，链式存储的线性表则更加灵活。

它就像是一串珍珠项链，每个珍珠（数据元素）通过一根线（指针）与下一个珍珠相连。

在链式存储中，插入和删除元素相对较为方便，只需要修改相关指针的指向即可，时间复杂度通常为 O(1)。

但是，由于无法直接通过计算得到某个元素的位置，所以随机访问的效率较低，时间复杂度为 O(n)。

在实际应用中，线性表有着多种多样的用途。

比如，我们可以用线性表来实现一个学生成绩管理系统。

将每个学生的成绩作为一个元素存储在线性表中，可以按照学号或者成绩进行排序。

当有新的学生成绩需要添加时，根据具体的存储方式选择合适的插入操作；当需要删除某个学生的成绩时，也能快速准确地进行删除。

再比如，在一个购物网站的商品列表中，也可以使用线性表来存储商品的信息。

用户可以按照价格、销量、评价等因素对商品进行排序和筛选。

而网站后台在处理商品的上下架、库存管理等操作时，也会频繁地对线性表进行插入、删除和修改等操作。

此外，在文本编辑软件中，我们输入的文字也可以看作是一个线性表。

数据结构实验报告实验一线性表的应用一、实验目的：1．掌握线性表的两种存储结构及实现方式；2．熟练掌握顺序表和链表的建立、插入和删除的算法。

二、实验要求：1．C完成算法设计和程序设计并上机调试通过。

2．撰写实验报告，提供实验结果和数据。

3．写出算法设计小结和心得。

三、实验内容：1．用顺序表表示集合，编写程序以实现集合的交、并、差运算。

2．设带头结点的单链表ha和hb中结点数据域值按从小到大顺序排列，且各自链表内无重复的结点，要求：（1）建立两个按升序排列的单链表ha和hb。

（2）将单链表ha合并到单链表hb中，且归并后的hb链表内无重复的结点，结点值仍保持从小到大顺序排列。

（3）输出合并后单链表hb中每个结点的数据域值。

四、程序源代码：1.#include<stdio.h>#include<stdlib.h>#define LIST_INIT_CAPACITY 100 typedef int ElementType;typedef struct List{ElementType elem[LIST_INIT_CAPACITY]; int nLength;}SqList;void init(struct List*L)//初始化顺序表{if(L)L->nLength=0;}int visit(SqList*L,ElementType e)//遍历顺序表{for(int i=0;i<L->nLength;i++){if(L->elem[i]==e){return 0;break;}elsecontinue;return 1;}}SqList*jiao(SqList*L1,SqList*L2,SqList*L3)//求两个集合的交集{int n=0;for(int i=0;i<L1->nLength;i++){for(int j=0;j<L2->nLength;i++){if(L1->elem[i]==L2->elem[j]){L3->elem[n]=L1->elem[i];n++;}elsecontinue;}}printf("集合的交集：\n");return L3;}SqList*bing(SqList*L1,SqList*L2,SqList*L3)//求两个集合的并集{int j=0;for (int i=0;i<L1->nLength;i++){if (visit(L2,L1->elem[i])){L3->elem[j]=L1->elem[i];L3->nLength++;j++;}elsecontinue;}printf("集合的并集：\n");return L3;}SqList*cha(SqList*L1,SqList*L2,SqList*L3)//求两个集合的差集{int j=0;for(int i=0;i<L1->nLength;i++){if(visit (L2,L1->elem[i])){L3->elem[j]=L1->elem[i];j++;L3->nLength++;}elsecontinue;}printf("集合的差集：\n");return L3;}void show(SqList *list)//显示线性表元素{for (int i=0;i<list->nLength;i++){printf(" %d",list->elem[i]);}printf("\n");}void main(){SqList*list1,*list2,*list3;list1=(SqList*)malloc(sizeof(SqList));list2=(SqList*)malloc(sizeof(SqList));list3=(SqList*)malloc(sizeof(SqList));init(list1);init(list2);init(list3);intstr1[6]={1,2,3,4,5,6},str2[7]={1,3,4,5,7,9,10};for(int i=0;i<6;i++){list1->elem[i]=str1[i];list1->nLength=i+1;}for(i=0;i<7;i++){list2->elem[i]=str2[i];list2->nLength++;}printf("初始集合：\n");show(list1);show(list2);list3=jiao(list1,list2,list3);show(list3);init(list3);list3=bing(list1,list2,list3);show(list3);init(list3);list3=cha(list1,list2,list3);show(list3);}2.#include <stdio.h>#include<stdlib.h>typedef int ElementType;typedef struct ListNode{ElementType data;struct ListNode *next;}sLinkList;sLinkList*create(ElementType i)//创建接点{sLinkList *p;p=(sLinkList*)malloc(sizeof(sLinkList));if(!p)exit(0);elsep->data=i;return p;}void anotherorder(sLinkList*head){sLinkList*P;P=head->next;if(head!=NULL)//头指针不为空{while (P->next!=NULL){sLinkList*q;//p的后继指针sLinkList*t;q=P->next;t=P->next->next;q->next=head->next;head->next=q;P->next=t;}}}void print(sLinkList*head)//输出链表{if(head==NULL){exit(0);}sLinkList*p=head->next;while(p!=NULL){printf("%4d",p->data);p=p->next;}printf("\n");}void hebing(sLinkList *p,sLinkList *q,sLinkList *l)//将两个链表合并{ sLinkList*z;q=q->next;l=l->next;while(q!=NULL&&l!=NULL){if(q->data>l->data){z=create(l->data);p->next=z;z->next=NULL;p=z;l=l->next;}elseif(q->data<l->data){z=create(q->data);p->next=z;z->next=NULL;p=z;q=q->next;}elseif(q->data==l->data){for(int i=0;i<2;i++){z=create(q->data);p->next=z;z->next=NULL;p=z;}q=q->next;l=l->next;}}if(q==NULL){while (l!=NULL){z=create(l->data);p->next=z;z->next=NULL;p=z;l=l->next;}}if(l==NULL){while (q!=NULL){z=create(q->data);p->next=z;z->next=NULL;p=z;q=q->next;}}printf("合并后：\n");}void deletelist(sLinkList*p)//删除多余元素节点{if(p!=NULL)p=p->next;sLinkList*q;//中间指针while (p!=NULL){int i=p->data;sLinkList*head=p;while (head->next!=NULL){if(i==head->next->data){q=head->next;head->next=q->next;free(q);}elsehead=head->next;}p=p->next;}printf("最终结果：\n");}void main(){sLinkList *ha; ha=(sLinkList*)malloc(sizeof(ListNode)); if(ha!=NULL)//判空{ha->next=NULL;ha->data=-1;}sLinkList *p;sLinkList *q=ha;int a[5]={2,4,6,8,10};for (int i=0;i<5;i++){p=create(a[i]);q->next=p;p->next=NULL;q=p;}printf("初始：\n");print(ha);sLinkList *hb;hb=(sLinkList*)malloc(sizeof(ListNode)); if(hb!=NULL)//判空{hb->next=NULL;hb->data=-1;}q=hb;int b[6]={1,4,5,8,9,10};for (i=0;i<6;i++){p=create(b[i]);q->next=p;p->next=NULL;q=p;}print(hb);//构建ha,hbsLinkList *hc;hc=(sLinkList*)malloc(sizeof(ListNode)); hebing(hc,ha,hb);print(hc);deletelist(hc);print(hc);}五、测试结果：1.2.六、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）经过这次实验，我对线性表的两种形式顺序表和链表有了进一步的了解，对线性表之间的运算及线性表的简单应用有了更深的体会。

计算机系数据结构实验报告（1）实验目的：帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。

问题描述：1、构造一个空的线性表L。

2、在线性表L的第i个元素之前插入新的元素e；3、在线性表L中删除第i个元素，并用e返回其值。

实验要求：1、分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线性表的基本操作算法。

2、在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。

算法分析：由于两种存储结构都用来创建线性结构的数据表，可采用相同的输出模式和整体结构类似的算法，如下：v1.0 可编辑可修改实验内容和过程：顺序存储结构线性表程序清单：//顺序存储结构线性表的插入删除#include <iostream>#include <>using namespace std;# define LISTSIZE 100# define CREMENTSIZE 10typedef char ElemType; //定义数据元素类型为字符型typedef struct {ElemType *elem; //数据元素首地址int len; //当前元素个数int listsize; //当前存储最大容量}SqList;//构造一个空的线性表Lint InitList(SqList &L){=(ElemType *)malloc(LISTSIZE*sizeof(ElemType));if (! exit(-2); //分配空间失败=0;=LISTSIZE;}//在顺序线性表L中第i个位置之前插入新的元素eint ListInsert(SqList &L,int i,ElemType e){if (i<1||i>+1) return -1; //i值不合法if >={ElemType *newelem=(ElemType *)realloc,+CREMENTSIZE)*sizeof(ElemType));//存储空间已满，增加分配if(!newelem) exit (-2); //分配失败=newelem;+=CREMENTSIZE;}ElemType *q=&[i-1]) ;for (ElemType *p=&[]);p>=q;--p) *(p+1)=*p; //插入位置及其后的元素后移 *q=e; ++;return 1;}//在顺序线性表L中删除第i个元素，并用e返回其值int ListDelete(SqList &L,int i,ElemType&e){if (i<1||i> return -1; //i值不合法ElemType *p=&[i-1]);e=*p; ElemType*q=+;for (++p;p<=q+1;++p) *(p-1)=*p; //被删除元素之后的元素前移;return 1;}int main (){SqList L; char e,ch;int i,j,state;InitList(L); //构造线性表printf("请输入原始数据(字符串个数0~99)：L="); //数据初始化gets;for ( j=1;[j-1]!='\0';j++) =j; //获取表长[j]='\0';printf("操作：插入（I）还是删除(D)\n"); //判断进行插入还是删除操作AGAIN:cin>>ch;if(ch=='I'){cout<<"插在第几个元素之前:"; //插入操作cin>>i; cout<<"输入要插入的新元素:";cin>>e;cout<<endl;printf("输入数据：L=(%s) ListInsert(L,%d,%c)",,i,e);state=ListInsert (L,i,e);}else if (ch=='D'){cout<<"删除第几个元素："; //删除操作cin>>i;cout<<endl;printf("输入数据：L=(%s) DeleteList(L,%d,e)",,i);state=ListDelete(L,i,e);}else goto AGAIN; //操作指示符输入错误处理cout<<endl<<"正确结果：";if(state==-1) cout<<"ERROR,";printf("L=(%s) ",; //输出结果if(ch=='D'&&state!=-1) cout<<",e="<<e;}链式存储结构线性表程序清单：// - - - - -单链存储结构线性表的插入删除 - - - - -#include <iostream>#include <>using namespace std;#define null 0typedef char ElemType; //定义数据元素类型为字符型typedef struct LNode{ElemType data;struct LNode *next;}LNode,*LinkList;int GetElem(LinkList L,int i,ElemType &e) //获取第i个元素的值 {LinkList p;int j;p=L->next; j=1;while(p&&j<i){p=p->next; ++j; //寻找第i个元素}if(!p||j>i) return -1; //寻找失败e=p->data;return 1;}int ListInsert(LinkList &L,int i,ElemType e){//在带头结点的单链线性表L中第i个元素之前插入元素eLinkList p,s; int j;p=L;j=0;while(p&&j<i-1) {p=p->next;++j;}if(!p||j>i-1) return -1;s=(LinkList) malloc( sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return 1;}int ListDelete(LinkList&L,int i,ElemType&e){//在带头结点的单链线性表L中,删除第i个元素，并由e返回其值LinkList p,q; int j;p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1) return -1;q=p->next;p->next=q->next;e=q->data;free(q);return 1;}int newdata(LinkList&L,char *ch){int k;printf("请输入原始数据(字符串个数0~99)：L="); //数据初始化gets(ch);for (k=0;ch[k]!='\0';k++) ListInsert(L,k+1, ch[k]); //将初始化数据插入链表L中cout<<"OK"<<endl;return k; //返回链表中的元素个数}int main (){char *ch;ch=(char *)malloc(100*sizeof(char)); //定义数组用来辅助数据初始化LinkList L; //头指针LNode head; //头结点L=&head; =null;int i,k,state; char e,CH,f;k=newdata(L,ch); //调用函数使链表数据初始化=k; //将元素个数存入头结点的数据域printf("操作：插入（I）还是删除(D)\n"); //判断进行插入还是删除操作AGAIN:cin>>CH;if(CH=='I'){cout<<"插在第几个元素之前:"; //插入操作cin>>i; cout<<"输入要插入的新元素:";cin>>e;cout<<endl;printf("输入数据：L=(%s) ListInsert(L,%d,%c)",ch,i,e);state=ListInsert(L,i,e);++;}else if (CH=='D'){cout<<"删除第几个元素："; //删除操作cin>>i;cout<<endl;printf("输入数据：L=(%s) DeleteList(L,%d,e)",ch,i);state=ListDelete(L,i,e);--;}else goto AGAIN; //操作指示符输入错误处理cout<<endl<<"正确结果：";if(state==-1) cout<<"ERROR,"; //输出结果cout<<"L=(";for(int m=1;>=m;m++) //一一输出数据{GetElem(L,m,f);cout<<f;}cout<<")";if(CH=='D'&&state!=-1) cout<<",e="<<e; //删除操作反馈e }实验结果：由于两个程序的输出模式相同，在此只列一组测试数据：L = () ListInsert (L, 1, 'k')L = (EHIKMOP) ListInsert (L, 9, 't')L = (ABCEHKNPQTU) ListInsert(L, 4, 'u') L = () ListDelete (L, 1, e)L = (DEFILMNORU) ListDelete_Sq(L, 5, e) L = (CD) ListDelete_Sq(L, 1, e)测试过程中所注意到的问题主要还是输出与输入界面的问题，通过灵活使用cout和cin函数来不断改进。

数据结构实验报告（⼀）线性表的应⽤实验说明数据结构实验⼀ 线性表的实验——线性表的应⽤⼀、实验⽬的通过本实验使学⽣了解线性表的⼀种简单应⽤，熟悉线性表顺序存储与链式存储的特性，特别训练学⽣编程灵活控制链表的能⼒，为今后编程控制更为复杂的数据结构奠定基础。

⼆、实验内容1.⽤顺序表和链表分别分别编程实现教材中例⼦2-1与2-2。

要求：（1）只能⽤C语⾔编程实现；（2）完全保持书中算法2.1与算法2.2形式，不允许有任何变化，除⾮语法上不允许;所调⽤各函数参照书中19页的功能描述，其中函数名、参数个数及性质、函数功能必须与书中完全⼀致，不能有变化。

2.利⽤线性表表⽰⼀元多项式完成多项式的加、减、乘、求导、求值运算。

要求：（1）输⼊的⼀元多项式可以采⽤只输⼊各项的系数与指数这种简化的⽅式。

如对于多项式2x2+6x5，输⼊可为： 2,2 6,5 这样的简单形式。

（2）遇到有消项时应当处理，如2x2+6x5与3x2-6x5进⾏相加时，结果为5*x^2。

（3）当给定x的值时，能计算表达式相加或相减的结果。

（4）操作的结果放⼊⼀个新线性表中，原来的两个表达式存储表⽰不变，也可以不是产⽣新的线性表，⽽是将两上线性表合并为⼀个。

（5）要求程序功能模块划分合理（每个函数功能单⼀、可重⽤性好），使⽤空间尽可能少，算法尽可能⾼效。

实验报告1.实现功能描述使⽤线性表表⽰⼀元多项式完成多项式的加、减，乘，求导、求值运算。

2.⽅案⽐较与选择（1）因为使⽤的是线性表，所以主要⽅案有数组法和链表法。

（2）从时间复杂度来说，使⽤数组法更优；从空间复杂度来说，链表法更优。

因为数组法是指定好空间的，若式⼦⼤⼩超出设置⼤⼩，那程序必然出错；若式⼦⼤⼩⼩于设置⼤⼩，那就意味着有多余的空间被浪费了。

综合来讲，若计算式⼦较为庞⼤，使⽤链表法更佳；相反，若计算式⼦较⼩，数组法更佳。

3.设计算法描述（1）单个项式的数据存储使⽤了结构体，数组法是在⼀个结构体中定义两个⼀维数组；链表法是通过⼀个结构体作为⼀个节点，通过next指针连接起来。

数据结构实验报告实验名称：线性表及其应用班级：12级电气本2学号：2012081227姓名：赵雪磊指导教师：梁海丽日期：2013年9月9日数学与信息技术学院一、实验目的1、掌握线性表的概念，理解线性表的顺序、链式存储。

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

二、实验要求1、建立顺序存储的线性表，并对之进行插入、删除操作。

2、建立链式存储的线性表，并对之进行插入、删除操作。

；三、算法描述#include <cstdlib>#include <iostream>#include "myList.h"using namespace std;template <class T> class Link {public:T data; // 用于保存结点元素的内容Link * next; // 指向后继结点的指针Link(const T info, Link* nextValue = NULL) { // 具有两个参数的Link构造函数data = info;next = nextValue;}Link(Link* nextValue = NULL) { // 具有一个参数的Link构造函数next = nextValue;}}// 【代码2.7】单链表的类型定义template <class T>class lnkList : public List<T> {protected:Link<T>* head, tail; // 单链表的头、尾指针public:lnkList(); // 构造函数~lnkList(); // 析构函数bool isEmpty(); // 判断链表是否为空void clear(); // 将链表存储的内容清除，成为空表int length(); // 返回此顺序表的当前实际长度bool append(T value); // 在表尾添加一个元素value，表的长度增1 bool insert(int p, T value); // 在位置p上插入一个元素value，表的长度增1 bool delete(int p); // 删除位置p上的元素，表的长度减 1int getPos(const T value); // 查找值为value的元素，并返回第1次出现的位置Link<T> setPos(int p); // 返回线性表指向第p个元素的指针值}template <class T>class lnkList:: lnkList() {head = tail = new Link<T>;}template <class T>class lnkList:: ~lnkList() {Link tmp;while (head != NULL) {tmp = head;head = head->next;delete tmp;}}template <class T> // 假定线性表的元素类型为TLink lnkList :: setPos(int i) {int count = 0;Link *p;if (i == -1) // i为-1则定位到"虚"头结点return head;p = head->next; // 若i为0则定位到第一个结点while (p != NULL && count < i) {p = p-> next;count++;};return p; // 指向第 i 结点，i＝0,1,…，当链表中结点数小于i时返回NULL }template <class T> // 假定线性表的元素类型为Tbool lnkList :: insert (int i, T value) {Link *p, *q;q = new Link<T>;p = setPos(i-1); // p是第i个结点的前驱if (p == NULL ) {cout << " the inserted point is illegal"<<endl;return false;}q->next = p->next;q->data = value;p->next = q;if (q->next == NULL ) // 插入点在链尾，插入结点成为新的链尾tail = q;return true;}// delete a node from singly linked listtemplate <class T> // 假定线性表的元素类型为Tbool lnkList :: delete(int i) {Link *p, *q;p = setPos(i-1); // p是第i个结点的前驱if (p == NULL ) {cout << " the deletion point is illegal"<<endl;return false;}q = p->next; // q是真正待删结点if (q == tail) // 待删结点为尾结点，则修改尾指针tail = p;if (q != NULL) { // 删除结点q 并修改链指针p->next = q->next;delete q;}return true;}template <class T> // 假定顺序表的元素类型为Tvoid lnkList<T> :: print() {while (head != NULL) {cout << head->data;cout << endl; // 从位置p开始每个元素左移直到curLen, tmp = head;head = head->next;}}四、程序清单#include <iostream.h>#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #defineOVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_SIZE 10 #define LISTINCREMENT 2typedef struct shunxubiao{ ElemType *list;int size;int Maxsize; }SqList;int InitList_Sq(SqList &L) {// 构造一个空的线性表L。

1 线性表1. 实验题目与环境1.1实验题目及要求（1）顺序表的操作利用顺序存储方式实现下列功能：根据键盘输入数据建立一个线性表，并输出该线性表；对该线性表进行数据的插入、删除、查找操作，并在插入和删除数据后，再输出线性表。

（2）单链表的操作利用链式存储方式实现下列功能：根据键盘输入数据建立一个线性表，并输出该线性表；对该线性表进行数据的插入、删除、查找操作，并在插入和删除数据后，再输出线性表。

（3）线性表的应用约瑟夫环问题。

有n个人围坐一圈，现从某个人开始报数，数到M的人出列，接着从出列的下一个人开始重新报数，数到M的人又出列，如此下去，直到所有人都出列为止。

要求依次输出出列人的编码。

2.问题分析（1）顺序表的操作利用一位数组来描述顺序表，即将所有元素一词储存在数组的连续单元中，要在表头或中间插入一个新元素时，需要将其后的所有元素都向后移动一个位置来为新元素腾出空间。

同理，删除开头或中间的元素时，则将其后的所有元素向前移动一个位置以填补空位。

查找元素时，则需要利用循环语句，一一判断直到找出所要查找的元素（或元素的位置），输出相关内容即可（2）单链表的操作利用若干个结点建立一个链表，每个节点有两个域，即存放元素的数据域和存放指向下一个结点的指针域。

设定一个头指针。

在带头结点的单链表中的第i个元素之前插入一新元素，需要计数找到第i-1个结点并由一指针p指向它，再造一个由一指针s指向的结点，数据为x，并使x的指针域指向第i个结点，最后修改第i-1个结点的指针域，指向x结点。

删除第i个元素时，需要计数寻找到第i个结点，并使指针p指向其前驱结点，然后删除第i个结点并释放被删除结点的空间。

查找第i个元素，需从第一个结点开始计数找到第i个结点，然后输出该结点的数据元素。

（3）线性表的应用程序运行之后，首先要求用户指定初始报数的上限值，可以n<=30,此题中循环链表可不设头结点，而且必须注意空表和"非空表"的界限。

实验报告课程名称数据结构__________实验项目线性表的实现及应用实验仪器PC机一台_________学院 ____________________________ 专业 ____________________________ 班级/学号__________________________ 姓名 ______________________________ 实验日期____________________________ 成绩 ____________________________指导教师___________________________北京信息科技大学信息管理学院(数据结构课程上机)实验报告1. 实验目的：(1)理解用顺序表实现线性表的特点；熟练掌握顺序表的基本操作；学会利用顺序表解决实际应用问题 (2)熟练掌握单链表的使用；理解用链表实现线性表的特点；了解链表的多种形式；学会利用单链表解决实际应用问题。

2. 实验要求：(1) 学时为8学时；(2) 能在机器上正确、调试运行程序； (3) 本实验需提交实验报告；(4)实验报告文件命名方法：数据结构实验 —信管16xx_学号J 生名.doc 。

3. 实验内容和步骤:第一部分顺序表的实现与应用(1)基于顺序表实现线性表的以下基本操作:T 表示数据元素的数据类型〃判断线性表是否空 //返回线性表长度//返回第i (i > 0)个元素 〃设置第i 个元素值为x〃插入x 作为第i 个元素//在线性表最后插入x 元素 〃删除第i 个元素并返回被删除对象 int search(T key); 〃查找，返回首次出现的关键字为 key 的元素的位序 void removeAII(); 〃删除线性表所有元素public String toString();//返回顺序表所有元素的描述字符串，形式为 }要求：实现后应编写代码段对每个基本操作做测试。

数据结构线性表实验报告五篇第一篇：数据结构线性表实验报告实验报告课程名：数据结构实验名：线性表及其操作姓名：班级：学号：撰写时间：2014.09.24一实验目的与要求1.掌握线性表的实现2.掌握线性表的基本操作的实现二实验内容• 分别完成线性表的顺序表示及链式表示• 在两种表示上, 分别实现一些线性表的操作, 至少应该包括–在第i个位置插入一个元素–删除第i个元素–返回线性表长–返回第i个元素的值三实验结果与分析#include #include //---------线性表链式表示-----------struct V//声明一个结构体类型struct V { int value;struct V * next;//定义结构体变量};void PrintLink(struct V*p)//定义一个结构体指针{ while(p!=NULL)//只要指针指向的变量不为NULL；就会一直循环链表指向下一个结构体{printf(“%d, ”,(*p).value);p=(*p).next;//指针指向下一个结构体} printf(“n”);} void Link(){struct V*head;head=(struct V*)malloc(sizeof(struct V));//开辟一个长度为size的内存(*head).value=-100;//表头为-100(*head).next=NULL;printf(“------------线性表链式表示------------n”);int i,n=10;struct V*p=head;printf(“10个数据:n”);for(i=0;i(*p).next=(struct V*)malloc(sizeof(struct V));p=(*p).next;(*p).value=2*i;(*p).next=NULL;} PrintLink(head);//调用PrintLink函数printf(“删除第四个数据:n”);int k=4;p=head;for(i=1;ip=(*p).next;} struct V*temp=(*p).next;//k表示插入和删除的位置(*p).next=(*temp).next;free(temp);PrintLink(head);printf(“插入第十个数据:n”);k=10;p=head;for(i=1;ip=(*p).next;} temp=(*p).next;(*p).next=(struct V*)malloc(sizeof(struct V));(*(*p).next).value=-99;(*(*p).next).next=temp;PrintLink(head);}//---------线性表顺序表示-----------void seq1(){ int i,n=10,k=4;int a[10];//---------输出数组元素------------printf(“-------------线性表顺序表示---------n”);for(i=0;ia[i]=i;} printf(“数组元素为:n”);for(i=0;iprintf(“%3d”,a[i]);} printf(“n”);//--------插入一个数组元素---------int m=n+1,j=12;//插入元素12 int b[20];for(i=0;i if(i{b[i]=a[i];}else if(i==k){b[i]=j;}else{b[i]=a[i-1];} } printf(“输出插入一个元素的数组:n”);for(i=0;i{if(i{c[i]=a[i];}else{c[i]=a[i+1];} } printf(“输出删除一个元素的数组:n”);for(i=0;i printf(“数组元素为:n”);for(i=1;i<=a[0];i++){a[i]=i;} for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);} printf(“n”);//-----在k 位置插入一个元素------------for(i=a[0];i>=k;i--){a[i+1]=a[i];} a[k]=-100;++a[0];for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);} printf(“n”);//-------在k---------------for(i=0;i>k;i++){a[i]=a[i+1];} a[k]=-1;a[0]=n;--a[0];for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);} printf(“n”);} int main(int argc,char *argv[]){ seq1();seq2();Link();return 0;} 图1：实验结果截图实验分析：已在程序中按规定格式标注。