顺序表和单链表实验报告

.Word文档数据结构实验报告一、顺序表操作验证1.实验目的⑴掌握线性表的顺序存储结构；⑵验证顺序表及其基本操作的实现；⑶掌握数据结构及算法的程序实现的基本方法。2.实验内容⑴建立含有若干个元素的顺序表；⑵对已建立的顺序表实现插入、删除、查找等基本操作。3.设计与编码#include<stdio.h>#include<stdlib.h>#include<malloc.h>structLinearList{ int*list; intsize;intMaxSize;};typedefstructLinearListLIST;voidInitList(LIST*L,intms){ if((L->list=(int*)malloc(ms*sizeof(int)))==NULL){ printf("内存申请错误！\n"); exit(1); } L->size=0; L->MaxSize=ms;}intInsertList(LIST*L,intitem,intrc){inti; if(L->size>=L->MaxSize) return-1; if(rc<0) rc=0; if(rc>L->size) rc=L->size; for(i=L->size-1;i>=rc;i--) L->list[i+1]=L->list[i]; L->list[rc]=item; L->size++; return0;}voidOutputList(LIST*L){ inti; for(i=0;i<L->size;i++) printf("%d",L->list[i]); printf("\n");}intFindList(LIST*L,intitem){ inti; for(i=0;i<L->size;i++) if(item==L->list[i]) returni; return-1;}intDeleteList1(LIST*L,intitem){ inti,n; for(i=0;i<L->size;i++) if(item==L->list[i]) break; if(i<L->size){ for(n=i;n<L->size-1;n++) L->list[n]=L->list[n+1]; L->size--; returni; } return-1;}intDeleteList2(LIST*L,intrc){ inti,n; if(rc<0||rc>=L->size) return-1; for(n=rc;n<L->size-1;n++) L->list[n]=L->list[n+1]; L->size--; return0;}voidmain(){LISTLL;inti,r;printf("listaddr=%p\tsize=%d\tMaxSize=%d\n",LL.list,LL.size,LL.MaxSize);InitList(&LL,100);printf("listaddr=%p\tsize=%d\tMaxSize=%d\n",LL.list,LL.size,LL.MaxSize); while(1) { printf("请输入元素值，输入0结束插入操作："); fflush(stdin); scanf("%d",&i); if(i==0) break; printf("请输入插入位置："); scanf("%d",&r); InsertList(&LL,i,r-1); printf("线性表为："); OutputList(&LL); } while(1) { printf("请输入查找元素值，输入0结束查找操作："); fflush(stdin); scanf("%d",&i); if(i==0) break; r=FindList(&LL,i); if(r<0) printf("没找到\n"); else printf("有符合条件的元素，位置为：%d\n",r+1); } while(1) { printf("请输入删除元素值，输入0结束查找操作："); fflush(stdin); scanf("%d",&i); if(i==0) break; r=DeleteList1(&LL,i); if(r<0) printf("没找到\n"); else{ printf("有符合条件的元素，位置为：%d\n线性表为：",r+1); OutputList(&LL); } } while(1) { printf("请输入删除元素位置，输入0结束查找操作："); fflush(stdin); scanf("%d",&r); if(r==0) break; i=DeleteList2(&LL,r-1); if(i<0) printf("位置越界\n"); else{ printf("线性表为："); OutputList(&LL); } }}4.运行结果单链表操作验证1.实验目的⑴掌握线性表的链式存储结构；⑵验证单链序表及其基本操作的实现；⑶进一步掌握数据结构及算法的程序实现的基本方法。2.实验内容⑴用头插法（或尾插法）建立带头结点的单链表；⑵对已建立的单链表实现插入、删除、查找等基本操作。3.设计与编码#include<stdio.h>#include<malloc.h>typedefstructlist{ intdata; structlist*next;}LIST;voidInitList(LIST**p){ *p=NULL;}voidInsertList1(LIST**p,intitem,intrc){ inti; LIST*u,*q,*r; u=(LIST*)malloc(sizeof(LIST)); u->data=item; for(i=0,r=*p;i<rc&&r!=NULL;i++){ q=r; r=r->next; } if(r==*p) *p=u; else q->next=u; u->next=r;}voidInsertList2(LIST**p,intitem){ LIST*u,*q,*r; u=(LIST*)malloc(sizeof(LIST)); u->data=item; for(r=*p;r!=NULL&&r->data<item;q=r,r=r->next); if(r==*p) *p=u; else q->next=u; u->next=r;}intDeleteList(LIST**p,intitem){ LIST*q,*r; q=*p;r=q; if(q==NULL) return1; if(q->data==item){ *p=q->next; free(r); return0; } for(;q->data!=item&&q->next!=NULL;r=q,q=q->next); if(q->data==item){ r->next=q->next; free(q); return0; } return1;}intFindList(LIST*p,intitem){ inti; for(i=1;p->data!=item&&p!=NULL;p=p->next,i++); return(p==NULL)?-1:i;}voidOutputList(LIST*p){ while(p!=NULL){ printf("%4d",p->data); p=p->next; } printf("\n");}voidFreeList(LIST**p){ LIST*q,*r; for(q=*p;q!=NULL;){ r=q; q=q->next; free(r); } *p=NULL;}intmain(){ LIST*p; intop,i,rc; InitList(&p); while(1) { printf("请选择操作1：指定位置追加2：升序追加3：查找结点\n"); printf("4：删除结点5：输出结点6：清空链表0：退出\n"); fflush(stdin); scanf("%d",&op); switch(op){ case0: return-1; case1: printf("请输入新增结点键值和位置："); scanf("%d%d",&i,&rc); InsertList1(&p,i,rc); break; case2: printf("请输入新增结点键值："); scanf("%d",&i); InsertList2(&p,i); break; case3: printf("请输入要查找结点的键值："); scanf("%d",&i); rc=FindList(p,i); if(rc>0) printf("位置为[%d]\n",rc); else printf("没找到\n"); break; case4: printf("请输入要删除结点的键值："); scanf("%d",&i); rc=DeleteList(&p,i); if(rc==0) printf("删除成功\n",rc); else printf("没找到\n"); break; case5: pr