数据结构实验报告内容及格式

实验一线性表顺序存储与操作1实验目的编写程序建立顺序存储的线性表L,其数据元素按非递减有序排列，插入一个元素X后，该线性表L仍保持有序。2实验内容/*2005-03-04 实验内容：编写程序建立顺序存储的线性表L，其数据元素按非递减有序排列，插入一个元素X后，该线性表L仍保持有序。实验要求：L的存储结构为：#defineLIST_INIT_SIZE100//顺序表存储空间的初分配量#defineLISTINCREMENT10 //顺序表存储空间的分配增量struct 〃线性表的结构{int*elem; //存储空间的基地址intlength; 〃当前的长度intlistsize;〃当前分配的容量};测试数据：建立：1,3,5,7,9插入：x=-1,6,10 */#include<stdio.h>#include<malloc.h>#include<conio.h>#include<string.h>#defineLIST_INIT_SIZE100//顺序表存储空间的初分配量#defineLISTINCREMENT10 //顺序表存储空间的分配增量typedefstruct //线性表的结构{int*elem; 〃存储空间的基地址intlength; //当前的长度intlistsize;//当前分配的容量}SQLIST;voidCreate(SQLIST&L) 〃建立线性表{L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));if(!L.elem)

printf（”为线性表分配空间失败!”）;L.length=0;L.listsize=LIST_INIT_SIZE;}voidInsert(SQLIST&A,intx) 〃实现有序的插入操作{if(A.length==A.listsize)printf('线性表错误!”)；if(x>A.elem[A.length-1])elseA.elem[A.length]=x; 〃与最大的元素进行判断，以决定是否插在最后elseinti=0;while(x>=A.elem[i])i++; 〃从第一个元素起，寻找正确的插入位置for(intj=A.length;j>=i;j--)A.elem[j+1]=A.elem[j];〃将所找位置后面的所有数据都向右移动一个位A.elem[i]=x;//插入新的数据A.length++;//顺序表的长度加1}voidmain(){printf("程序说明:\n");printf(- 建立顺序存储的单链表，其数据元素按元素值非递减有序排列，插入一个数据元素后，该线性表仍保持有序\n\n");SQLISTs;Create(s); 〃为线性表分配空间s.elem[0]=1;//建表s.elem[1]=3;s.elem[2]=5;s.elem[3]=7;s.elem[4]=9;s.length=5;printf("\n\n已建立的顺序表为：\n");for(inti=0;i<s.length;i++)printf("%d”,s.elem[i]);printf("\n\n请输入要插入的数据:\n");inttmp;scanf("%d”,&tmp);Insert(s,tmp);printf("\n\n插入数据后的顺序表为：\n");for(i=0;i<s.length;i++)printf("%d”,s.elem[i]);_getch();//如果不加如该句，则执行用VisualC++编译后的exe文件，控制台窗口会一闪而过，看不请执行结果:)}3实验结果4实验总结与分析实验二线性表链式存储与操作1实验目的掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在链接存储结构上的运算。2实验内容#include<stdio.h>#include<malloc.h>#include<conio.h>#include<stdlib.h>#include<string.h>#defineERROR0#defineOK1#defineEQUAL1#defineOVERFLOW-1#defineLIST_INIT_SIZE100#defineLISTINCREMENT10structSTU{\\线性表的结构charname[20];charstuno[10];intage;intscore;}stu[50];typedefstructSTUElemType;structLNODE{ElemTypedata;structLNODE*next;};typedefstructLNODELNode;typedefstructLNODE*LinkList;intinit(LinkList*L)\\建表{*L=(LNode*)malloc(sizeof(LNode));if(!L)exit(ERROR);(*L)->next=NULL;returnOK;}/*init*/intListLength(LinkListL)\\返回数据元素个数{intj=0;while(L->next){L=L->next;j++;}returnj;}intGetElem(LinkListL,inti,ElemType*。)\\用e返回L中第i值{LinkListp;intj;p=L->next;j=1;while(p&&j<i){p=p->next;++j;}if(!pllj>1)returnERROR;*e=p->data;returnOK;intEqualList(ElemType*e1,ElemType*e2)\比匕较{if(strcmp(e1->name,e2->name)==0)return1;elsereturn0;}intLess_EqualList(ElemType*e1,ElemType*e2){if(strcmp(e1->name,e2->name)<=0)return1;elsereturn0;}intLocateElem(LinkListLa,ElemTypee,inttype){//inti;LinkListp;p=La;switch(type){caseEQUAL:while(p->next){p=p->next;if(EqualList(&p->data,&e))return1;}return0;break;default:break;}return0;}voidMergeList(LinkListLa,LinkListLb,LinkList*Lc)\\合并表{LinkListpa,pb,pc;pa=La->next;pb=Lb->next;*Lc=pc=La;while(pa&&pb){if(Less_EqualList(&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);\'释放表Lb}voidprintlist(LinkList1)\\输出表{//inti;LinkListp;p=L;printf("namestuno agescore\n");while(p->next){p=p->next;printf("%-10s%s\t%d\t%d\n",p->,p->data.stuno,p->data.age,p->data.score);}printf("\n");}intListInsert(LinkListL,inti,ElemTypee)\插入信息{LinkListp,s;intj;p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!pllj>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;returnOK;}/*ListInsertBeforei*/intmain(){structSTUe;LinkListLa,Lb,Lc;system("cls");\\清屏printf("\n\n ListDemoisrunning... \n\n");printf("FirstisInsertListfunction.\n");init(&La);strcpy(,"stu1”);strcpy(e.stuno,"100001");e.age=80;e.score=1000;ListInsert(La,1,e);\\插入信息1strcpy(,"stu3”);strcpy(e.stuno,"100002");e.age=80;e.score=1000;ListInsert(La,2,e);\\插入信息2printlist(La);\'输出表Lagetch();strcpy(,"stu5”);strcpy(e.stuno,”100003");e.age=80;e.score=1000;ListInsert(La,3,e);\\插入信息3printlist(La);\'输出表Lagetch();init(&Lb);\\建立Lb表strcpy(,"stu2”);strcpy(e.stuno,"100001");e.age=80;e.score=1000;ListInsert(Lb,1,e);\\插入信息1strcpy(,"stu4”);strcpy(e.stuno,"100002");e.age=80;e.score=1000;ListInsert(Lb,2,e);\\插入信息2strcpy(,"stu6”);strcpy(e.stuno,"100001");e.age=80;e.score=1000;ListInsert(Lb,3,e);\\插入信息3printlist(Lb);\'输出表Lbgetch();MergeList(La,Lb,&Lc);\\归并La,LB成为Lcprintlist(Lc);\'输出Lc表getch();}3实验结果4实验总结与分析实验三栈的应用---判断字符串是否中心对称1实验目的掌握栈的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。掌握栈的特点，即先进后出。掌握栈的基本运算，如入栈与出栈等运算在顺序存储结构上的实现。2实验内容/*2005-03-2 实验内容：有n个字符的字符串，判断字符串是否中心对称。如:xyzzyx和xyzyx都是中心对称的字符串实验要求：字符串放在单链表中，内容1由栈实现(存储结构自定)并实现利用栈的入栈和出栈完成判断。 */#include<stdio.h>#include<stdlib.h>#include<string.h>#definemax100//////////////////定义单链表的结点类型////////////////////typedefstructnode{chardata;structnode*next;}LinkList;/////////////////根据输入的字符(存储在字数组中)建立一个不带结点的单链表////////////LinkList*create(chars[])〃函数返回的类型为指针{LinkList*head, 〃头指针*newNode,//newNode始终指向新开的结点*tail; //tail始终指向链表中的最后一个结点for(inti=0;s[i]!='\0';i++){newNode=(LinkList*)malloc(sizeof(LinkList));〃新开一个结点newNode->data=s[i];newNode->next=NULL;if(i==0) 〃如果只输入了一个字符{head=newNode;tail=head;}else{tail->next=newNode;//把新开的结点连接到链表的最后一个结点上tail=newNode;}}returnhead;}////////////////////定义栈的存储类型//////////////////////////typedefstruct{char*base; 〃栈顶指针(始终指向栈顶元素的下一个位置)char*top; 〃栈底指针(始终指向栈底)}stack;voidInitStack(stack&s) 〃栈的初始化{s.base=(char*)malloc(max*sizeof(char));s.top=s.base;}voidpush(stack&s,chare) 〃进栈函数{*s.top++=e;}charpop(stack&s,char&e) 〃出栈函数{e=*--s.top;returne;}///////////////判断以单链表存储的字符串是否对称的函数///////////////intjudge(LinkList*head){stacks;chare;InitStack(s);〃定义一个栈并初始化LinkList*p=head;//把头指针赋给p,即让p指向第一个结点while(p!=NULL){push(s,p->data);p=p->next;}p=head;while(p!=NULL) 〃将栈中的元素弹出，逐个与链表中的元素比较(可以看成是把链表换个方向，然后与原来的链表比较){if(p->data==pop(s,e))p=p->next;elsebreak;〃如果不相等，说明不是对称，调处循环}if(p==NULL)return1;elsereturn0;}voidmain(){printf("程序说明:\n");printf("目的：判断字符串是否关于中心对称.\n");printf(-方法：字符串用单链表实现，将字符串全部入栈然后比较\n\n");charstr[max];//定义一个字符数组，用来存储输入的字符//LinkList*h;while(1){printf("\n\n请输入字符串(输入cls清屏,exit退出):")；gets(str);if(strcmp(str,"exit")==0)break;if(strcmp(str,"cls")==0)system("cls");switch(judge(create(str)))〃根据输入的字符串(存储在字符数组中)建立单链表然后进行判断{case1:printf("\n ・％s是中心对称的的字符串\n",str);break;case0:printf("\n ・％s不是关于中心对称的\n”,str);break;}}}3实验结果4实验总结与分析实验四顺序队列的实现---约瑟夫环问题的实现1实验目的掌握队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。掌握队列的特点，即先进先出。掌握队列的基本运算，如入队与出队等运算在顺序存储结构的实现。2实验内容#include<stdio.h>#include<stdlib.h>structLnodeintnumber;intpa