顺序表的定义及基本操作和单链表的定义及基本操作.doc

数据结构实验报告 壹 题目一：顺序表的定义及基本操作题目二：单链表的定义及基本操作 班级： 信息一班 姓名： 学号： 得分： _ （满分2.5分）线性表#include#define OVERFLOW -2#define OK 1#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef int ElemType;typedef int status;typedef structElemType *elem;int length;int listsize;sqlist; status lnitlist_sq(sqlist &L)L.elem=new ElemTypeLIST_INIT_SIZE;if(!L.elem)coutOVERFLOW;L.length=0;L.listsize=LIST_INIT_SIZE;return OK; int LocateElem(sqlist L, ElemType e) int *p ;p=L.elem; int i=1;while(i=L.length & *p+!=e) i+;return i=L.length ? i : 0;status GetElem(sqlist L, int i, ElemType &e) if(iL.length) return ERROR; /i非法 e=*(L.elem + i - 1); return OK;status ListInsert(sqlist &L, int i, ElemType e) /前插操作int *newbase,*q,*p; if(iL.length+1) return ERROR; / i非法 if(L.length=L.listsize) /需要扩展数组 newbase=new ElemTypeL.listsize+LISTINCREMENT; if(!newbase) cout=q; p-) *(p+1)=*p; /右移一位 *q=e; /将e放入第i个元素的位置上 +L.length; return OK; /ListInsert status ListDelete(sqlist &L, int i, ElemType &e) /删除顺序表的第 i 个元素，用e返回被删元素的值int *p;if(iL.length) return ERROR; /i非法p=&(L.elemi-1); /令指针p指向aie=*p;for(+p; p=L.elem+L.length-1; +p) *(p-1)=*p; /ai+1an左移一位 -L.length ; /表的长度减1return e; /ListDelete status DestroyList(sqlist &L)delete L.elem;return OK;void ListTraverse(sqlist L)if(L.length)for(int i=0;iL.length;i+)coutL.elemit;else cout此顺序表为空！endl; void main() int m,n; sqlist a;lnitlist_sq(a); cout线性表初始长度：a.lengthendl; cout请输入线性表的10个元素:endl; for(int i=0;ia.elemi ; cout线性表当前长度：a.lengthendl; cout调用遍历函数endl; ListTraverse(a ); cout调用定位函数endl;coutLocateElem(a,9)endl;cout调用读表元函数endl;coutGetElem(a, 5, m)endl;cout在第五个元素前插入8endl;coutListInsert(a, 5, 8)endl;ListTraverse(a );coutendl;cout删除第五个元素并返回endl;coutListDelete(a, 5, n)endl;ListTraverse(a );coutendl;cout销毁线性表DestroyList(a)endl; 单链表#include#define OVERFLOW -2#define OK 1#define ERROR 0#define LIST_INIT_SIZE 10 typedef int status;typedef struct LNode int data ; struct LNode *next ; LNode, *LinkList;status InitList ( LinkList &L ) /L是带头结点的单链表的头指针L=new LNodeLIST_INIT_SIZE; /申请头结点if(!L)coutnext=NULL;return OK;status GetElem (LinkList L, int i, int &e) /L是带头结点的单链表，读L的第i个元素，用e返回其值LNode *p;int j; p=L-next; j=1; /指针p指向a1 while(p & jnext; j+; /指针p右移i1次 if(!p|ji)return ERROR; /i非法 !p-i太大,ji-i太小 e=p-data; return e; /GetElem status ListLength ( LinkList L ) / L是带头结点的单链表int n;LNode *p;p=L-next; n=0;while(p) n+; p=p-next;coutn;return OK; /ListLength O(n) status ListInsert( LinkList &L, int i, int e ) / L是带头结点的单链表,在ai之前插入新结点eLNode *s;LNode *p;int j; p=L; j=0; /p指向头结点，j是计数器 while(p & jnext; j+; /令p指向ai-1 if (!p | ji-1) return ERROR; /i非法 s=new LNodeLIST_INIT_SIZE+2; s-data=e; s-next=p-next; p-next=s; /修改指针 return OK; / ListInsertstatus ListDelete( LinkList &L, int i, int &e ) / L是带头结点的单链表,删除ai，用参数e返回被删结点的值LNode *q,*p;int j; p=L; j=0; /p指向头结点，j是计数器 while(p & jnext; j+; /p指向ai-1 if (!(p-next) | ji-1) return ERROR; / i非法 q=p-next; e=q-data; p-next=q-next; delete(q); /修改指针 return OK; / ListInsert O(n) int LocateElem(LinkList L, int e) LNode *p;p=L-next ;int i=1;while(i & p-data!=e) i+;*p+;return i; void main() int m,n ;LinkList a;LNode s1, s2, s3, s4, s5;InitList (a );a-next=&s1 ;s1.next=&s2 ;s2.next=&s3;s3.next=&s4;s4.next=&s5;cout请输入5个元素：s1.datas2.datas3.datas4.datas5.data;cout执