1、数据结构线性表实验报告剖析成绩：实 验 报 告课程名称：数据结构实验名称：线性表的顺序实现和链式实现姓 名：专 业：计算机科学与技术班 级：学 号：计算机科学与技术学院实验教学中心2016 年 11月 29日实验项目名称：线性表的顺序实现和链式实现一、实验目的1理解顺序表的结构特点及有关概念，掌握顺序表建立、插入、删除的基本操作算法。2理解单链表的结构特点及有关概念，掌握单链表建立、插入、删除的基本操作算法。二、实验内容1.顺序表操作内容1.1建立n个元素的顺序表，实现顺序表建立的基本操作。1.2在指定位置插入一个元素，实现顺序表插入的基本操作。1.3在顺序表中删除指定位置上的元素，实现顺序表
2、的删除的基本操作。2.链式表操作内容2.1建立一个包括头结点和3个结点的（4，2，1）的单链表，实现单链表建立的基本操作。2.2在已建好的单链表中的指定位置（x=2）插入一个结点3，实现单链表插入的基本操作。2.3在一个包括头结点和4个结点的（4，3，2，1）的单链表的指定位置删除一个结点，实现单链表删除的基本操作。三、实验用设备仪器及材料计算机及CodeBlocks编程软件。四、实验原理利用C语言实现五、实验操作步骤1.顺序表的实现及操作代码#include#include#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define OK
3、 1#define ERROR -1#define OVERFLOW -2typedef int ElemType;typedef int Status;typedef struct ElemType *elem; int length; int listsize; SqList;Status InitList_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; retur
4、n OK;Status ListInsert_Sq(SqList &L,int i,ElemType e) if(iL.length+1) return ERROR; if(L.length=L.listsize) ElemType *newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType); if(!newbase)exit(OVERFLOW); L.elem=newbase; L.listsize += LISTINCREMENT; ElemType *q=&(L.elemi-1); for(
5、ElemType *p=&(L.elemL.length-1); p=q; -p) *(p+1)=*p; *q=e; +L.length; return OK;Status ListDelete_Sq(SqList &L,int i,ElemType &e) if(iL.length+1) return ERROR; ElemType *p=&L.elemi-1; e=*p; ElemType *q=L.elem+L.length-1; for(+p;p=q;+p) *(p-1)=*p; -L.length; return OK;Status LocateElem_Sq(SqList L,El
6、emType e, Status(*compare)(ElemType,ElemType) int i=1; ElemType *p=L.elem; while(i=L.length&!(*compare)(*p+,e)+i; if(i=L.length) return i; else return 0;Status compare(ElemType a,ElemType b) if(a=b) return OK; else return 0;void MergeList_Sq(SqList La,SqList Lb,SqList&Lc) ElemType *pa=La.elem,*pb=Lb
7、.elem,*pc; Lc.listsize=Lc.length=La.length+Lb.length; Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType); if(!Lc.elem)exit(OVERFLOW); ElemType *pa_last=La.elem+La.length-1; ElemType *pb_last=Lb.elem+Lb.length-1; while(pa=pa_last&pb=pb_last) if(*pa=*pb)*pc+=*pa+; else *pc+=*pb+; while(pa=pa_last)
8、 *pc+=*pa+; while(pb=pb_last) *pc+=*pb+; void ClearList_Sq(SqList &L) if(L.length!=0) L.length=0;void DestoryList_Sq(SqList &L) if(L.elem!=0) free(L.elem); L.elem=NULL;void ListSort_Sq(SqList &L,int Sta,int End) ElemType tmp; for(int i=Sta-1;iEnd-1;i+) for(int j=i+1;jL.elemj) tmp=L.elemi; L.elemi=L.
9、elemj; L.elemj=tmp; void prin(SqList &L) printf(当前线性表元素依次是:n); for(int i=0;iL.length;i+) printf(%d ,L.elemi); printf(nn);int main() int n,m,t; SqList L; InitList_Sq(L); printf(请输入要建立线性表的大小n:n); scanf(%d,&n); printf(请依次输入线性表元素:n); for(int i=1;i=n;i+) scanf(%d,&m); ListInsert_Sq(L,i,m); while(true) pr
10、intf(请选择操作（输入0退出操作）:n1、排序元素; 2、删除元素; 3、插入元素;n); scanf(%d,&t); if(t=0)break; else if(t=1) int Sta,End; printf(请输入要排序元素的起始终止位置：n); scanf(%d%d,&Sta,&End); ListSort_Sq(L,Sta,End); prin(L); else if(t=2) int loc,val; printf(请输入要删除元素的位置：n); scanf(%d,&loc); ListDelete_Sq(L,loc,val); printf(删除元素的值：%dn,val);
11、prin(L); else if(t=3) int loc,val; printf(请输入要插入元素的位置及元素值:n); scanf(%d%d,&loc,&val); ListInsert_Sq(L,loc,val); prin(L); return 0;2.链式表的实现及操作#include#include#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define OK 1#define ERROR -1#define OVERFLOW -2typedef int ElemType;typedef int Status;typedef
12、 struct LNode ElemType data; struct LNode *next;LNode,*LinkList;Status GetElem_L(LinkList L,int i,ElemType &e) LNode *p=L-next; int j=1; while(p&jnext;j+; if(!p|ji) return ERROR; e=p-data; return OK;Status ListInsert_L(LinkList &L,int i,ElemType e) LNode *p=L; int j=0; while(p&jnext;+j; if(!p|ji-1)
13、return ERROR; LNode *s=(LinkList)malloc(sizeof(LNode); s-data=e; s-next=p-next; p-next=s; return OK;Status ListDelete_L(LinkList &L,int i,ElemType &e) LNode *p=L; int j=0; while(p-next&jnext; +j; if(!p-next|ji-1) return ERROR; LNode *q=p-next; p-next=q-next; e=q-data; free(q); return OK;void CreateL
14、ist_L(LinkList &L,int n) L=(LinkList)malloc(sizeof(LNode); L-next=NULL; LNode *q; q=L; for(int i=n;i0;i-) LNode *p=(LinkList)malloc(sizeof(LNode); scanf(%d,&p-data); q-next=p; p-next=NULL; q=p; void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) LNode *pc,*pa=La-next,*pb=Lb-next; Lc=pc=La; whil
15、e(pa&pb) if(pa-datadata) pc-next=pa;pc=pa;pa=pa-next; else pc-next=pb;pc=pb;pb=pb-next; pc-next=pa?pa:pb; free(pb); void prin(LinkList &L) LNode *p=L-next; printf(当前线性表的元素依次是：n); while(p) printf(%d ,p-data); p=p-next; printf(nn);int main() int n,t; LinkList L; printf(请输入要建立线性表的大小n:n); scanf(%d,&n);
16、printf(请依次输入每个元素的值:n); CreateList_L(L,n); while(true) printf(请选择操作（输入0退出操作）:n1、删除元素; 2、插入元素;n); scanf(%d,&t); if(t=0)break; else if(t=1) int loc,val; printf(请输入要删除元素的位置：n); scanf(%d,&loc); ListDelete_L(L,loc,val); printf(删除元素的值：%dn,val); prin(L); else if(t=2) int loc,val; printf(请输入要插入元素的位置及元素值:n); scanf(%d%d,&loc,&val); ListInsert_L(L,loc,val); prin(L); return 0;六、实验结果分析1.顺序表代码运行截图2.链式表代码运行截图
