数据结构设计性实验－线性表 .doc

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(

12、LList L, ElemType x) /* 确定x在表中的位序 */ int n=1; while (L!=NULL & L-data!=x) L=L-next; n+; if (L=NULL) return 0; else return n;Status Insert(LList &L, int i, ElemType e) /* 插入第i元素*/ int j=1; LList s,q; s=(LList)malloc(sizeof(LNode); s-data=e; q=L; if (i=1) s-next=q; L=s; return OK; else while(jnext!=NU

13、LL) q=q-next; j+; if (j=i-1) s-next=q-next; q-next=s; return OK; else return ERROR; /* 位置参数i不正确 */ Status Delete(LList &L, int i, ElemType &e) /* 删除第i元素*/ int j=1; LList q=L,t; if (i=1) e=q-data; L=q-next; free(q); return OK; else while (jnext!=NULL) q=q-next; j+; if (q-next!=NULL & j=i-1) t=q-next;

14、 q-next=t-next; e=t-data; free(t); return OK; else return ERROR; /* 位置参数i不正确*/ void Display(LList L) /* 依次显示表中元素 */ printf(单链表显示: ); if (L=NULL) printf(链表为空!); else if (L-next=NULL) printf(%cn, L-data); else while(L-next!=NULL) printf(%c-, L-data); L=L-next; printf(%c, L-data); printf(n);（3） 带头结点单链表

15、Status SetEmpty(LinkList &L) /* 置带头结点的空单链表*/ Link p; p=(Link)malloc(sizeof(LNode); /* 生成头结点 */ if(p) p-next=NULL; L.head=L.tail=p; L.len=0; return OK; else return ERROR;Status Destroy(LinkList &L) /* 销毁线性链表L，L不再存在 */ Link p,q; if(L.head!=L.tail) /* 不是空表 */ p=q= L.head-next; L.head-next=NULL; while(p

16、!=L.tail) p=q-next; free(q); q=p; free(q); free(L.head); L.head=L.tail=NULL; L.len=0; return OK;int Length(LinkList L) /* 返回线性链表L中元素个数 */ return L.len;Status Get(LinkList L, int i, ElemType &e) /* 获取第i元素 */ /* i=0为头结点 */ Link p; int j; if(iL.len) return ERROR; else p=L.head; for(j=1;jnext; e=p-data;

17、 return OK; int Locate(LinkList L, ElemType x) /* 确定x在表中的位序 */ int i=0; Link p=L.head; do p=p-next; i+; while(p & p-data!=x); /* 没到表尾且没找到满足关系的元素 */ if (!p) return 0; else return i;Status Insert(LinkList &L, int i, ElemType e) /* 插入第i元素*/ int j=0; Link s,q; s=(Link)malloc(sizeof(LNode); s-data=e; q=L

18、.head; while(jnext!=NULL) q=q-next; j+; if (j=i-1) s-next=q-next; q-next=s; if (L.tail=q) L.tail=s; L.len+; return OK; else return ERROR; /* 位置参数i不正确 */Status Delete(LinkList &L, int i, ElemType &e) /* 删除第i元素*/ int j=0; Link q=L.head,t; while (jnext!=NULL) q=q-next; j+; if (q-next!=NULL & j=i-1) t=q

19、-next; q-next=t-next; e=t-data; if(L.tail=t) L.tail=q; free(t); L.len-; return OK; else return ERROR; /* 位置参数i不正确*/void Display(LinkList L) /* 依次显示表中元素 */ Link p; printf(单链表显示: ); if (L.head=L.tail) printf(链表为空!); else p=L.head-next; while(p-next!=NULL) printf(%c-, p-data); p=p-next; printf(%c, p-da

20、ta); printf(n);4测试（1） 顺序存储结构SqList head; void main() /* 主函数*/ char e,c; int i,n,select,x1,x2,x3,x4,m,g; SetEmpty(head); n=random(8); /* 随机产生表长 */ for (i=1; i0 & select 5);（2） 无头结点单链表LList head;void main() /* 主函数*/ char e,c; int i,n,select,x1,x2,x3,x4,m,g; SetEmpty(head); n=random(8); /* 随机产生表长 */ fo

21、r (i=1; i0 & select 5);（3） 带头结点单链表LinkList head;void main() /* 主函数*/ char e,c; int i,n,select,x1,x2,x3,x4,m,g; SetEmpty(head); n=random(8); /* 随机产生表长 */ for (i=1; i0 & select5);5三种存储结构的比较存储结构顺序映象无头结点单链表带头结点单链表基本操作时间复杂度SetEmpty(&L)O(1)O(1)O(1)Destroy(&L)O(1)O(n)O(n)Length(L)O(1)O(n)O(1)Get(L, i, &e)O

22、(1)O(n)O(n)Locate(L,e,compare()O(n)O(n)O(n)Insert(&L, i, e)O(n)O(n)O(n)Delete(&L, i, &e)O(n)O(n)O(n)Display(L)O(n)O(n)O(n)优缺点分析优 点可以随机存取插入删除时不需要移动元素1对空表不需要额外进行判断处理；2求表长度方便缺 点插入删除时需要移动元素1对空表需要额外进行判断处理；2求表长度不方便不能随机存取6思考与小结（1）无头结点单链表的插入和删除操作的实现，要区分该表是否为空，并编写相应的代码。（2）在算法设计时，要注意判断有关参数值的合法性。（3）三种存储结构的主函数相同。设计主函数及测试运行时，要考虑测试的完备性。