数据结构课程设计报告.docx

数据结构课程设计报告1.题目：线性表抽象数据类型的实现1.1顺序存储结构抽象数据类型定义adt list 数据对象：d=ai:|aielemset,i=1n,n0数据关系：r1=|ai-1,aid,i=2,n0基本操作:initlist_sq(sqlist *l)操作结果：构造一个空的线性表l。getelem(l,i,&e)初始条件：线性表l已经存在,1=i=listlength(l)操作结果：用e返回l中第i个数据元素的值listinsert(&l,i,e)初始条件：线性表l已经存在,1=i=listlength(l)+1操作结果：在l中第i个位置前插入新的数据元素 e，l的长度加1listdelete(&l,i,&e)初始条件：线性表l已经存在且非空,1=i=listlength(l)操作结果：删除l中第i个数据元素，并用 e返回其值，l的长度减1listlength(l)初始条件：线性表l已经存在.操作结果：返回l中数据元素的个数 listsize(l) 操作结果：返回l的容量adt sqlist1.2链式存储结构抽象数据类型定义adt list 数据对象：d=ai:|aielemset,i=1n,n0数据关系：r1=|ai-1,aid,i=2,n0基本操作:linklist *creatl(linklist *l)初始条件：线性表l已经存在操作结果：存储输入的数据元素。 listinsert(&l,i,e)初始条件：线性表l已经存在,1=i=listlength(l)+1操作结果：在l中第i个位置前插入新的数据元素 e，l的长度加1listdelete(&l,i,&e)初始条件：线性表l已经存在且非空,1=ielem = (elemtype*)malloc(list_init_size*sizeof(elemtype); if(!l-elem) return false; l-length=0; l-listsize=list_init_size; return ture; /插入表int listinsert(sqlist *l,int i,elemtype e)elemtype *p,*q,*newbase;if (i l-length+1) return false;if(l-length)=(l-listsize) newbase=(elemtype*)malloc(list_init_size+list_increment)*sizeof(elemtype); if(!newbase) return false; l-elem=newbase;l-listsize+=list_increment; p=&(l-elemi-1); for(q=(&l-eleml-length-1);q=p;-q) *(q+1)=*(q); *p=e; +(l-length);/删除表int listdelete(sqlist *l,int i,elemtype *e)elemtype *p,*q;if (i l-length) return false;p=&(l-elemi-1);*e=*p;q=l-elem+l-length-1;for(+p;plength); /取线性表的元素getelem(sqlist l,int i,elemtype *e)if (i (l.length) return false;*e=l.elemi-1;printf(%dn,*e);/求长度int listlength(sqlist l)return l.length; /求容量int listsize(sqlist l)return l.listsize;3.2：链式存储结构算法设计/输入函数 struct list *creat() a *head,*p,*pt;int length,i;printf(你要输入的个数:);scanf(%d,&length); count=length;for(i=1;inext=p;pt=p; printf(第%d个数的位置,i);scanf(%ld,&p-num); while(p-num99999|p-numnum);printf(第%d个数的值,i);scanf(%s,&p-name);p-next=null;printf( 你输入的数据:n);return(head);/输出函数void print(a *head)a *p;p=head;printf( _n);printf( 有%d个数n,count);printf( 位置 数值n);if(head!=null) doprintf(%23ld%24sn,p-num,p-name);p=p-next;while(p!=null);else printf(sorry!空表);printf( _n);/位置插入函数 struct list *p_insert(a *head)a *p1,*p2,*inp;int place,i;printf(要插入的位置：);scanf(%d,&place);inp=(a *)malloc(len);printf(位置);scanf(%ld,&inp-num);while(inp-num99999|inp-numnum);printf(数值);scanf(%s,&inp-name);p1=head;for(i=1;inext;if(i=1)inp=p1-next;head=inp; else p2-next=inp;inp-next=p1;count+;printf( 按位置插入后结果:n);return(head);/排序函数 struct list *shen_sort(a *head)a *p,*min;int i=1;long m_num;int m_name8;p=head;min=head;for(i=1;inext; while(p!=null) if(p-numnum) m_num=p-num;p-num=min-num;min-num=m_num; strcpy(m_name,p-name);strcpy(p-name,min-name);strcpy(min-name,m_name); p=p-next; min=min-next; printf( 排序后结果:n);return(head);/按顺序插入函数struct list *s_insert(a *head)a *p1,*p2,*pi;head=shen_sort(head);pi=(a *)malloc(len);printf(插入的位置);scanf(%ld,&pi-num);while(pi-num99999|pi-numnum);printf(数值);scanf(%s,&pi-name);p1=head; while(pi-nump1-num&p1-next!=null) p2=p1;p1=p1-next; if(pi-numnum)if(p1=head) head=pi; else p2-next=pi; pi-next=p1; else p1-next=pi;pi-next=null; count+; printf( 按顺序插入后结果:n); return(head);/删除函数 struct list *del(a *head)a *p1,*p2;long del_num;printf(要删除的数的位置);scanf(%ld,&del_num);p1=head; while(p1-num!=del_num&p1-next!=null) p2=p1;p1=p1-next; if(p1-num=del_num) if(p1=head)head=p1-next;else p2-next=p1-next;count-;printf( 删除后结果:n); else printf(位置不存在，删除失败); return(head);/修改函数 struct list *amend(a *head)a *p;long num;printf(要修改的位置);scanf(%ld,&num);p=head; while(p-num!=num&p-next!=null) p=p-next; if(p-num=num) printf(修改后的数值);scanf(%s,&p-name);printf( 修改后结果:n); else printf(位置不存在，修改失败); return(head);/释放函数 void free_list(a *head)a *p=head;printf(释放链表);while(p!=null)head=head-next;free(p);p=head; /菜单函数 void menu()printf(*链表操作菜单*n);printf( 1、输入 2、输出 3、按位置插入n); printf( 4、排序 5、顺序插入 6、删除n);printf( 7、修改 0、释放链表 退出n);printf(*n);4.测试4.1顺序存储结构测试/主函数main()sqlist l;int e,i,k,t,m,n;initlist_sq(&l);printf(请输入8个数据元素);printf(n);for(i=1;i=8;i+)scanf(%d,&e); listinsert(&l,i,e);printf(n); printf(现在的数据元素是t);for(i=1;i=l.length;i+)printf(t%d,l.elemi-1);printf(n);printf(请输入删除数据元素的位置);scanf(%d,&k);printf(n);listdelete(&l,k,&e);printf(现在的线性表是：);for(i=1;i=l.length;i+)printf(t%d,l.elemi-1);printf(n);printf(请输入插入数据元素的位置);scanf(%d,&k);printf(n);printf(请输入你想插入的数据元素);scanf(%d,&e);printf(n);listinsert(&l,k,e);printf(现在的数据元素是：);for(i=1;i=l.length;i+)printf(t%d,l.elemi-1);printf(n);printf(请输入你想查找的位置：);scanf(%d,&k);getelem(l,k,&e);m=listlength(l);printf(长度=%dn,m);n=listsize(l);printf(大小=%dn,n);4.2链式存储结构测试/主函数 void main()a *head; int m;int flag=1;menu();while(flag)printf(输入代码:);scanf(%d,&m);switch(m)case 1:head=creat();print(head);printf(一共有%d个数n,count);break;case 2:print(head);printf(一共有%d个数n,count);break;case 3:system(cls);menu();print(head);head=p_insert(head);print(head);printf(一共有%d个数n,count);break;case 4:system(cls);menu();print(head);head=shen_sort(head);print(head);printf(一共有%d个数n,count);break;case 5:system(cls);menu();print(head);head=s_insert(head);print(head);printf(一共有%d个数n,count);break;case 6:system(cls);menu();print(head);head=del(head);print(head);printf(一共有%d个数n,count);break;case 7:system(cls);menu();print(head);head=amend(head);print(head);printf(一共有%d个数n,count);break;case 0:free_list(head);flag=0;system(cls);printf(nnnnnnnnnnnn 谢谢使用n);break;default:printf(代码错误，请重新输入n);创建测试插入测试删除测试5二种存储结构的比较 链式存储结构: (1)占用额外的空间以存储指针(浪费空间) (2)存取某个元素速度慢，要同时存储数据元素和下一个数据元素的地址 (3)插入元素和删除元素速度快，不需要移动大量的数据元素 (4)没有空间限制,存储元素的个数无上限,基本只与内存空间大小有关.顺序存储结构: (1)空间利用率高，因为没有存储下一个数据元素的地址 (2)存取某个元素速度快，因为是顺序存储，直接可以返回 (3)插入元素和删除元素存在元素移动,速度慢,耗时 (4)有空间限制,当需要存取的元素个数可能多于顺序表的元素个数时,会出现溢出问题.当元素个数远少于预先分配的空间时,空间浪费巨大.总结 当存储的数据元素不多时，用顺序存储，当存储的数据元素较多时