数据结构设计性实验-线性表 .doc
《数据结构设计性实验-线性表 .doc》由会员分享,可在线阅读,更多相关《数据结构设计性实验-线性表 .doc(11页珍藏版)》请在沃文网上搜索。
1、数据结构设计性实验采用字符类型为元素类型和无头结点单链表为存储结构,实现抽象数据类型List。 ADT List 数据对象:D ai | aiElemSet, i=1,2,.,n, n0 数据关系:R1 |ai-1, aiD, i=2,.,n 基本操作: SetEmpty(&L) 操作结果:构造一个空的线性表L。 Destroy(&L) 初始条件:线性表L已存在。 操作结果:销毁线性表L。 Length(L) 初始条件:线性表L已存在。 操作结果:返回L中元素个数。 Get(L, i, &e) 初始条件:线性表L已存在,1iLengthList(L)。 操作结果:用e返回L中第i个元素的值。
2、Locate(L, e, compare() 初始条件:线性表L已存在,compare()是元素判定函数。 操作结果:返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在,则返回值为0。 Insert(&L, i, e) 初始条件:线性表L已存在,1iLengthList(L)+1。 操作结果:在L的第i个元素之前插入新的元素e,L的长度加1。 Delete(&L, i, &e) 初始条件:线性表L已存在且非空,1iLengthList(L)。 操作结果:删除L的第i个元素,并用e返回其值,L的长度减1。 Display(L) 初始条件:线性表L已存在。 操作结果:依次
3、输出L的每个元素。 ADT List2存储结构定义公用头文件DS0.h:#include #include #include #include #include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define IBFEASIBLE -1#define OVERFLOW -2 #define MAXLEN 20#define MAXSIZE 20typedef int Status;typedef char ElemType; /* 元素类型为字符类型*/(1) 顺序存储结构#define LIST_INIT_SIZ
4、E 20 /*线性表存储空间的初始分配量*/#define LISTINCREMENT 10 /*线性表存储空间的分配增量*/typedef struct ElemType *elem; /*存储空间基址*/ int length; /*当前长度*/ int listsize; /*当前分配的存储容量*/ SqList;(2) 无头结点单链表存储结构typedef struct LNode ElemType data; struct LNode *next; LNode, *LList; /* 不带头结点单链表类型*/(3) 带头结点单链表存储结构typedef struct LNode /*
5、 结点类型 */ ElemType data; struct LNode *next; LNode, *Link, *Position;typedef struct LinkList /* 链表类型 */ Link head,tail; /* 分别指向线性链表中的头结点和最后一个结点 */ int len; /* 指示线性链表中数据元素的个数 */ LinkList;3. 算法设计(1) 顺序存储结构Status SetEmpty(SqList &L) /*构造一个空的顺序线性表 */ L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemTyp
6、e); if(!L.elem) return OVERFLOW; /* 存储分配失败 */ L.length=0; /* 空表长度为0 */ L.listsize=LIST_INIT_SIZE; /* 初始存储容量 */ return OK; Status Destroy (SqList &L) /*销毁顺序线性表L */ free(L.elem); L.elem=NULL; L.length=0; L.listsize=0; return OK;int Length(SqList L) /* 求表长*/ return L.length;Status Get(SqList &L, int i,
7、 ElemType &e) /* 获取第i元素 */ if(iL.length) return ERROR; e=*(L.elem+i-1); return OK;int Locate(SqList L, ElemType x) /* 确定x在表中的位序 */ ElemType *p; int i=1; /* i的初值为第1个元素的位序 */ p=L.elem; /* p的初值为第1个元素的存储位置 */ while(i=L.length & *p+!=x) +i; if(i=L.length) return i; else return 0;Status Insert(SqList &L,
8、int i, ElemType e) /* 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1 */ ElemType *newbase,*q,*p; if(iL.length+1) /* i值不合法 */ return ERROR; if(L.length= L.listsize) /* 当前存储空间已满,增加分配 */ newbase=(ElemType *) realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType); if(!newbase) return OVERFLOW; /* 存储分配失败 */ L.elem
9、=newbase; /* 新基址 */ L.listsize+=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 */ return OK;Status Delete(SqList &L, int i, ElemType &e) /* 初始条件:顺序线性表L已存在,1iListLength(L) */ /* 操作结果:删除L的第i个数据元素
10、,并用e返回其值,L的长度减1 */ ElemType *p,*q; if(i L.length) /* i值不合法 */ return ERROR; 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 */ return OK;Status Display(SqList L) /* 依次显示表中元素 */ ElemType *p; i
11、nt i; p=L.elem; printf( ); for(i=1; inext; free(q); q=L; return OK;int Length(LList L) /* 求表长*/ int n=0; while(L!=NULL) n+; L=L-next; return n;Status Get(LList L, int i, ElemType &e) /* 获取第i元素 */ int j=1; while (jnext; j+; if(L!=NULL) e=L-data; return OK; else return ERROR; /* 位置参数i不正确 */int Locate(
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
10 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构设计性实验线性表 数据 结构设计 实验 线性