顺序表实验报告

重庆科技学院学生实验报告课程名称算法与数据结构实验项目名称顺序表的实现开课院系及实验室数理学院实验室I217实验日期9.24学生姓名冯帅学号2009443411专业班级应数09指导教师陈小强实验成绩教师评语：教师签字：批改时间：一、实验目的和要求1、掌握线性表的链式存储结构及其基本操作，学会定义线性表的链式存储结构类型——单链表。2、掌握单链表的插入、删除、查找以及求表长算法的实现二、实验内容1、单链表的C实现1)．问题描述根据教材采用C语言实现单链表类型（包括类型定义，各种基本运算的实现）2)．类型定义/*Common.h*/#defineOK1//状态，成功#defineFAILURE0//状态，未成功#defineERROR-1//状态，失败#defineOVERFLOW1//溢出typedefintStatus;/*List_sq.h*/#include<stdio.h>#include<stdlib.h>#include"common.h" #defineLIST_INIT_SIZE80//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefintElemType;//顺序表typedefstruct{ ElemType*elem;//存储空间基址 intlength;//当前长度 intcurrentsize;//当前分配的长度}SqList;/*构造一个空的线性表*/SqList*CreateList();/*销毁线性表*/voidDestroy(SqList*L);/*在顺序表中查询第一个满足判定条件的数据元素，若存在，返回它的位序，否则返回0*/intLocate(SqList*L,ElemTypee,Status(*compare)(ElemType,ElemType));/*在顺序表L的第i个元素之前插入新的元素e,i的合法范围为1≤i≤L.length+1*/StatusInsert(SqList*L,inti,ElemTypee);/*删除顺序表L的第i个元素，返回第i个元素e,i的合法范围为1≤i≤L.length+1*/StatusDelete(SqList*L,inti,ElemType*e);/*遍历*/voidTraverse(SqList*L,void(*visit)(ElemType,int));/*List_sq.c*/#include<stdio.h>#include<stdlib.h>#include"common.h"#include"List_SQ.h"/*构造一个空的线性表*/SqList*CreateList(){ SqList*L=(SqList*)malloc(sizeof(SqList)); if(L==NULL) { exit(OVERFLOW); } L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(L->elem==NULL) { exit(OVERFLOW); } L->length=0; L->currentsize=LIST_INIT_SIZE; returnL;}/*销毁线性表*/voidDestroy(SqList*L){ if(L!=NULL) { if(L->elem!=NULL) { free(L->elem); } L->elem=NULL; }}/*在顺序表中查询第一个满足判定条件的数据元素，若存在，返回它的位序，否则返回0*/intLocate(SqList*L,ElemTypee,Status(*compare)(ElemType,ElemType)){ inti=1;//i的初值为第1元素的位序 ElemType*p=L->elem;//p的初值为第1元素的存储位置 while(i<=L->length&&(*compare)(*p++,e)!=OK) { ++i; } if(i<=L->length) { returni; } else { return0; }}/*在顺序表L的第i个元素之前插入新的元素e,i的合法范围为1≤i≤L.length+1*/StatusInsert(SqList*L,inti,ElemTypee){ ElemType*q; ElemType*p; if(i<1||i>L->length+1)//插入位置不合法 { returnERROR; } if(L->length>=L->currentsize)//当前存储空间已满，增加分配 { ElemType*newbase=(ElemType*)realloc(L->elem,(L->currentsize+LISTINCREMENT)*sizeof(ElemType)); if(newbase==NULL)//存储分配失败 { exit(OVERFLOW); } L->elem=newbase;//新基址 L->currentsize+=LISTINCREMENT;//增加存储容量 } q=&(L->elem[i-1]);//q指示插入位置 for(p=&(L->elem[L->length-1]);p>=q;--p) { *(p+1)=*p;//插入位置及之后的元素右移 } *q=e;//插入e ++L->length;//表长增1 returnOK;}/*删除顺序表L的第i个元素，返回第i个元素e,i的合法范围为1≤i≤L.length+1*/StatusDelete(SqList*L,inti,ElemType*e){ ElemType*p; ElemType*q; if(i<1||i>L->length+1)//删除位置不合法 { returnERROR; } p=&(L->elem[i-1]);//p为被删除元素的位置 *e=*p;//被删除元素的值赋给e q=L->elem+L->length-1;//表尾元素的位置 for(++p;p<=q;++p) { *(p-1)=*p;//被删除元素之后的元素左移 } --L->length;//表长减1 returnOK;}/*遍历*/voidTraverse(SqList*L,void(*visit)(ElemType,int)){ inti; for(i=0;i<L->length;i++) { (*visit)(L->elem[i],i+1); }}/*测试主程序Main.c*/#include<stdio.h>#include<stdlib.h>#include"common.h"#include"List_sq.h"voidoutput(ElemTypee,inti);voidmain(void){SqList*L;ElemTypee;L=CreateList();Insert(L,1,1);Insert(L,2,5);Insert(L,3,8);Insert(L,4,52);Insert(L,5,200);{inti;for(i=1;i<=L->length;++i){ if(i==5) Delete(L,5,200); Insert(L,5,100); printf("%d\n",L->elem[i-1]);}else printf("L:%d\n",L->elem[i-1]); printf("\n");}Traverse(L,output); Destroy(L);}voidoutput(ElemTypee,inti){printf("e:%d\n",i,e);}三、实验记录///////DS.h///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineINFEASIBLE-1

#defineOVERFLOW-2

typedefintStatus;///////////////////////////////////////////////////////////////////////////////////#include"DS.h"

typedef

int

ElemType;

typedefstructLNode{

ElemType

data;

structLNode*next;

}LNode,*LinkList;

voidCreateList_L(LinkList&L,intn);

voidDestroyList_L(LinkList&L);

StatusListInsert_L(LinkList&L,inti,ElemTypee);

StatusListDelete_L(LinkList&L,inti,ElemType&e);

LNode*LocateElem_L(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType));

intListLength_L(LinkListL);

voidPrintList_L(LinkListL);///////////////////////LinkList.cpp///////////////////////////////////////////////#include<stdio.h>

#include<stdlib.h>

#include"LinkList.h"

voidCreateList_L(LinkList&L,intn){

LNode*p;

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL;

for(inti=n;i>0;--i){

p=(LinkList)malloc(sizeof(LNode));

scanf("%d",&p->data);

p->next=L->next;

L->next=p;

}

}

voidDestroyList_L(LinkList&L)

{

LNode*p,*q;

p=L;

L=NULL;

while(p)

{

q=p;

p=p->next;

free(q);

}}

StatusListInsert_L(LinkList&L,inti,ElemTypee)

{

intj;

LNode*p,*s;

p=L;

j=0;

while(p&&j<i-1)

{

p=p->next;

++j;

}

if(!p||j>i-1)

returnERROR;

s=(LinkList)malloc(sizeof(LNode));

s->data=e;

s->next=p->next;

p->next=s;

returnOK;

}

StatusListDelete_L(LinkList&L,inti,ElemType&e)

{

intj;

LNode*p,*q;

p=L;

j=0;

while(p->next&&j<i-1)

{

p=p->next;

++j;

}

if(!(p->next)||j>i-1)

returnERROR;

q=p->next;

p->next=q->next;

e=q->data;

free(q);

returnOK;

}

LNode*LocateElem_L(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType))

{

LNode*p;

p=L->next;

while(p&&!(*compare)(p->data,e))

p=p->next;

returnp;

}

intListLength_L(LinkListL){

LNode*p=L;

int

j=0;

while(p->next)

{

p=p->next;

j++;

}

returnj;

}

voidPrintList_L(LinkListL)

{

LNode*p;

p=L->next;

while(p)

{

printf("%d",p->data);

p=p->next;

}

printf("\n");

}

/////////////main.cpp////////////////////////////////////////////////#include<stdio.h>

#include<conio.h>

#include"LinkList.h"

Statuscompare(ElemTypex,ElemTypey)

{

if(x==y)

returnTRUE;

else

returnFALSE;

}

intmain()

{

inta,e;

LNode*p;

LinkListL;

clrscr();

CreateList_L(L,3);

PrintList_L(L);

ListInsert_L(L,1,10);

PrintList_L(L);

ListInsert_L(L,2,12);

PrintList_L(L);

ListDelete_L(L,1,e);

PrintList_L(L);

p=LocateElem_L(L,1,compare);

DestroyList_L(L);

PrintList_L(L);

a=ListLength_L(L);

printf("%d",a);

return0;

}///////DS.h/////////////////////////////////////////////////////////////////////////////////////////////////////////#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineINFEASIBLE-1

#defineOVERFLOW-2

typedefintStatus;///////////SqList.h/////////////////#include"DS.h"

typedefintElemType;

#defineLIST_INIT_SIZE100#defineLISTINCREMENT10

typedefstruct{

ElemType*elem;

intlength;

intlistsize;

}SqList;Statusequal(ElemType,ElemType);

StatusInitList_Sq(SqList&);

voidCreateList_Sq(SqList&,int);

intLocateElem_Sq(SqList,ElemType,Status(*compare)(ElemType,ElemType));

StatusListInsert_Sq(SqList&,int,ElemType);

StatusListDelete_Sq(SqList&,int,ElemType&);

voidPrintList_Sq(SqList);

voidDestroyList_Sq(SqList&);//////////////////SqList.cpp//////////////////////////#include"DS.h"

#include"SqList.h"

#include"stdlib.h"

#include<stdio.h>

Statusequal(ElemTypex,ElemTypey)

{

if(x==y)

returnOK;

else

return

ERROR;

}

StatusInitList_Sq(SqList&L)

{

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

if(!L.elem)exit(OVERFLOW);

L.length=0;

L.listsize=LIST_INIT_SIZE;

returnOK;

}StatusListInsert_Sq(SqList&L,inti,ElemTypee)

{

ElemType*newbase,*q,*p;

if(i<1||i>L.length+1)returnERROR;

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;

}voidCreateList_Sq(SqList&L,intn)

{

inti;

inta[8]={12,13,21,24,28,30,42,77};

for(i=1;i<=n;++i)

{

L.elem[i-1]=a[i-1];

L.length=n;

}

}voidPrintList_Sq(SqListL)

{

inti;

for(i=1;i<=L.length;++i)

printf("%d

",L.elem[i-1]);

printf("\n");

}StatusListDelete_Sq(SqList&L,inti,ElemType&e)

{

ElemType*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;

}intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType))

{

inti;

ElemType*p;

i=1;

p=L.elem;

while(i<=L.length&&!(*compare)(*p++,e))

++i;

if(i<=L.length)

returni;

else

return0;

}voidDestroyList_Sq(SqList&L)

{

free(L.elem);

L.elem=NULL;

}///////////////main.cpp///////////////////////#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#include"DS.h"

#include"SqList.h"

intmain()

{

inte;

Statusresult;

SqListL;

clrscr();

InitList_Sq(L);

CreateList_Sq(L,8);

PrintList_Sq(L);

ListInsert_Sq(L,5,25);

PrintList_Sq(L);

ListDelete_Sq(L,4,e);

printf("e=%d\n",e);

PrintList_Sq(L);

result=LocateElem_Sq(L,28,equal);

if(result!=0)

printf("Yes!\n");

else

printf("No!\n");

DestroyList_Sq(L);

getch();

return0;

}//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

顺序表操作

作者:王鹤QQ:583241212VC++6.0调试通的代码://Sq_List.cpp:Definestheentrypointfortheconsoleapplication.

//信阳师范学院华锐学院数学与计算机科学系2006级王鹤#include"stdafx.h"

#include"malloc.h"

#include"string.h"constintMAXLISTSIZE=80;

#definetrue1

#definefalse0typedefcharElemType;typedefstruct

{

ElemType*elem;

intlength;

intlistsize;

}SqList;voidInitList(SqList&L,intmaxsize)

{

if(maxsize==0)

maxsize=MAXLISTSIZE;

L.elem=newElemType[maxsize];

if(!L.elem)return;

L.length=0;

L.listsize=maxsize;

}//初始列表函数,时间复杂度O(1).Createdby:王鹤QQ:583241212intListInsert(SqList&L,intpos,ElemTypee)

{

if(pos<1||pos>L.length+1)returnfalse;

if(L.length>=L.listsize)returnfalse;

for(intj=L.length-1;j>=pos-1;--j)

L.elem[j+1]=L.elem[j];

L.elem[pos-1]=e;

++L.length;returntrue;

}//此函数用于向顺序表中插入元素intListDelete(SqList&L,intpos,ElemType&e)

{

if((pos<1)||(pos>L.length))returnfalse;

e=L.elem[pos];

for(intj=pos;j<L.length;++j)

L.elem[j-1]=L.elem[j];

--L.length;

returntrue;

}//Thisfunctionusedtodeleteelementsandgetthedeletedelements.voidDestroyList(SqList&L)

{

delete[]L.elem;

L.listsize=0;

L.length=0;

}//DestroytheSq_ListvoidDisp_SqList(SqListL)

{

intn=L.length;

for(inti=0;i<n;i++)

printf("顺序表中的元素为:%c\n",L.elem[i]);

}//Showelementsinthecompare(ElemTypememb1,ElemTypememb2)

{

if(memb1==memb2)return1;

return0;

}//ComparetwoelementsintLocateElem(SqListL,ElemTypee,int(*compare)(ElemType,ElemType))

{

inti=1;

ElemType*p=L.elem;

while(i<=L.length&&!(*compare)(*p++,e))

++i;

if(i<=L.length)returni;

elsereturn0;

}//Findelement,toensureitinthesetandRetrivetheelementsindex.

void

MergeList_Sq(SqListLa,SqListLb,SqList*Lc)//归并顺序表

{

//已知顺序线性表La和Lb的元素按值非递减排序

//归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排序

ElemType*pa,*pb,*pc,*pa_last,*pb_last;

pa=La.elem;

pb=Lb.elem;

Lc->length=La.length+Lb.length;

Lc->listsize=Lc->length;

Lc->elem=(ElemType*)malloc(Lc->listsize*sizeof(ElemType));

pc=Lc->elem;

if(!Lc->elem)

{

printf("AA");

return;

}

pa_last=La.elem+L