数据结构实验二试验报告 线性表的基本操作

PAGEPAGE13数据结构试验报告实验二线性表的基本操作实验内容：线性表两种存储结构的基本运算专业班级：网络工程1002班组长：王星（2010100230）组员：郭坤铭（2010100243）张磊（2010100244）2012年实验项目目的和要求掌握线性表的特点。掌握线性表的顺序存储结构和链式存储结构的基本运算。尽可能考虑算法的健壮性。实验报告中要写出测试数据、错误分析以及收获。实验内容1.用结构体类型描述线性表的两种存储结构2.完成课堂上所讲的两种存储结构的基本运算3.要求用二级菜单实现******************************1顺序表**2链表**0退出******************************请输入的选择：(0-2)：线性表的链式存储###############################1前插建立链表##2后插建立链表##3访问第i个元素##4插入##5删除##6求线性表的表长##0退出###############################请输入选择(0-6)：实验代码#include<stdio.h>#include<stdlib.h>//宏定义//#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineLIST_INIT_SIZE50#defineLISTINCREMENT10//结构体//typedefintStatus;typedefintElemType;typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;typedefstructlink{intdata;structlink*next;}link,*linklist;//顺序表中的函数//StatusInitList_Sq(SqList*L) { inti,a; L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));//分配空间 if(!L->elem)exit(OVERFLOW);//若存储分配失败，返回-2 L->length=0;//空表，长度为0 L->listsize=LIST_INIT_SIZE;//初始存储容量 printf("请输入结点数："); scanf("%d",&a); printf("请输入数据：\n");for(i=0;i<a;i++) {scanf("%d",&L->elem[i]); (L->length)++; } returnOK; }voidprintlist_sq(SqListL){ inti; printf("输入的元素为："); for(i=0;i<L.length;i++) printf("%d",L.elem[i]); printf("\n");}StatusListInsert_Sq(SqList*L,inti,ElemTypee){int*q=&(L->elem[i-1]);ElemType*newbase,*p; if(i<1||i>L->length+1)returnERROR;//检查i值是否合理//将线性表第i个元素之后的所有元素向后移动if(L->length>=L->listsize) {newbase=(ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) exit(OVERFLOW); L->elem=newbase; L->listsize+=LISTINCREMENT; }q=&(L->elem[i-1]); for(p=&(L->elem[L->length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L->length;returnOK;}StatusListDelete_Sq(SqList*L,inti,ElemTypee){int*p,*q; if(i<1||(i>L->length))returnERROR;p=&(L->elem[i-1]);e=*p;q=L->elem+L->length-1;for(++p;p<=q;++p)*(p-1)=*p;--L->length;returnOK;}StatusGetElem_Sq(SqList*L,inti,ElemType*e){printf("输入要查找元素的位置:");scanf("%d",&i);if(i<1||i>L->length)returnERROR;//判断i值是否合理，若不合理，返回-else*e=L->elem[i-1];//数组中第i-1的单元存储着线性表中第i个数据元素的内容 printf("该位置的元素为%d",L->elem[i-1]); returnOK;}intListLength_Sq(SqList*L){ printf("该线性表长为：%d",L->length);return(L->length);}//链表中的函数//voidadd_top(link*top) {link*p; intlength,i;top->next=NULL; printf("输入建立链表长度：");scanf("%d",&length);printf("请输入结点元素："); for(i=1;i<=length;i++){ p=(link*)malloc(sizeof(link)); scanf("%d",&i); p->data=i; p->next=top->next; top->next=p; }}voidarrive_end(link*top){link*p=top->next; while(p!=NULL){printf("%d",p->data); p=p->next; }printf("\n");}voidadd_bottom(link*top){link*p,*q; intlength,i;q=top; printf("输入建立链表长度：");scanf("%d",&length);printf("请输入结点元素："); for(i=1;i<=length;i++) { p=(link*)malloc(sizeof(link)); scanf("%d",&i); p->data=i; q->next=p; q=p; }q->next=NULL;}intlength(link*top){ink*p;intlength=0;p=top;while(p->next!=NULL){p=p->next;length++;}returnlength;}voiddelete(link*top,intpos){inti=0;link*p=top,*q;while(p->next!=NULL&&i<pos-1){p=p->next;i++;}q=p->next;p->next=q->next;free(q);}intinsert(link*top,inti,intpos){intj=0;link*p=top,*s;while(j<i-1&&p!=NULL){j++;p=p->next;}if(p==NULL)//未找到第i-1个结点return0;else//找到第i-1个结点*p{s=(link*)malloc(sizeof(link));//创建新结点*ss->data=pos;s->next=p->next;//将*s插入到*p之后p->next=s;return1;}}intGetElem(link*top,inti){intj=0;link*p;p=top; while(p->next&&j<i) { p=p->next; j++; } if(i==j) printf("该位置的元素为%d",p->data);returnOK; }// 主菜单和二级菜单//intmenu_select_list(){intchoice;printf("*****************************************\n");printf("*1顺序表*\n");printf("*2链表*\n");printf("*3退出*\n");printf("*****************************************\n");printf("请输入选择：（1-3）");scanf("%d",&choice);if(choice<1||choice>3) printf("输入选择有误，请重新选择（1-3）：\n");returnchoice;}intmenu_select_2_sqlist(){intchoice; printf("\t^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n"); printf("\t*1建立顺序表*\n");printf("\t*2显示*\n"); printf("\t*3插入*\n"); printf("\t*4删除*\n"); printf("\t*5查找*\n"); printf("\t*6求线性表的长度*\n"); printf("\t*7返回*\n"); printf("\t^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n"); printf("请输入选择（1-7）："); scanf("%d",&choice); if(choice<1||choice>7) printf("输入选择有误，请重新选择（1-7）：\n"); returnchoice;}intmenu_select_2_list(){ intchoice; printf("\t^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n"); printf("\t*1前插建立链表*\n");printf("\t*2显示*\n"); printf("\t*3后插建立链表*\n"); printf("\t*4插入*\n"); printf("\t*5删除*\n"); printf("\t*6查找*\n"); printf("\t*7求线性表的长度*\n"); printf("\t*8返回*\n"); printf("\t^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n"); printf("请输入选择（1-8）："); scanf("%d",&choice); if(choice<1||choice>8)printf("输入选择有误，请重新选择（1-8）：\n");returnchoice;}//调用顺序表中的函数//voidmain(){SqListL;inti,e;linktop,p;intpos;while(1) { switch(menu_select_list()) { while(1){ case1: switch(menu_select_2_sqlist()) {case1:InitList_Sq(&L);system("cls"); break; case2:printlist_sq(L);getch();system("cls"); break; case3:printf("请输入要插入的位置："); scanf("%d",&i); printf("请输入要插入的元素："); scanf("%d",&e); ListInsert_Sq(&L,i,e); printf("插入后的线性表："); printlist_sq(L); getch(); system("cls"); break; case4:printf("请输入被删除的位置："); scanf("%d",&i); ListDelete_Sq(&L,i,e); printf("已成功删除！"); getch(); system("cls"); break; case5:GetElem_Sq(&L,i,&e);getch();system("cls"); break; case6:ListLength_Sq(&L); getch(); system("cls"); break; case7:return0;break;system("cls"); default:printf("\t\t\t输入有误，请重新输入：\n");break; } }break;//调用链表中的函数// while(1) {case2: switch(menu_select_2_list()) {case1:add_top(&top);printf("建立好的链表为："); arrive_end(&top); getch(); system("cls"); break;case2:printf("建立好的链表为："); arrive_end(&top); getch(); system("cls");break; case3:add_bottom(&top); arrive_end(&top); getch(); system("cls");break;case4:printf("请输入插入位置：");scanf("%d",&i);printf("请输入要插入的元素："); scanf("%d",&pos);insert(&top,i,pos); arrive_end(&top); getch();system("cls");break;case5:printf("请输入删除位置：");scanf("%d",&pos);delete(&top,pos); printf("删除后的链表为："); arrive_end(&top); getch(); system("cls");break;case6:printf("请输入查找位置：");scanf("%d",&i);GetElem(&top,i); getch();