《数据结构课程设计》实验报告.docx

《《数据结构课程设计》实验报告.docx》由会员分享，可在线阅读，更多相关《《数据结构课程设计》实验报告.docx（43页珍藏版）》请在三一办公上搜索。

1、数据结构课程设计实验报告数据结构 学 院：专 业：班级学号：姓 名：学 期：教 师： 实 验 报 告 1 实 验 报 告 院： 课程名称：数据结构 日期： 班级 专业 计算机科学与技术 实验名称 所用软件 实 验 目 的 实 验 准 备 学号 姓名 实验室 计算机号 成绩评定 教师签名 C语言的熟悉 V C 1熟练掌握C语言中数组，指针和结构体的使用。 2理解数据结构的基本概念。 1复习C语言中数组，指针、结构体的相关知识点。 2复习课堂讲解的理论知识。 3阅读实验内容1。 4改正实验内容2的程序并编好实验内容3、4的源程序。 1、改正后的程序为： 实 验 内 容 #include typed

2、ef struct int xh;float gs; float wy; float jsj; float zf;student; void main student a7; int i,j; for(i=1;i=6;i+) ai.xh=i; printf(输入学生的三门课成绩：n); for(i=1;i=6;i+) scanf(%f,&ai.gs); scanf(%f,&ai.wy); scanf(%f,&ai.jsj); for(i=1;i=6;i+) ai.zf=ai.gs+ai.wy+ai.jsj; printf(输出学生的学号及总成绩：n); for(i=1;i=6;i+) prin

3、tf(%3d ,i); printf(%3fn,ai.zf); for(i=2; i=6; i+) if(ai.zfai-1.zf) a0=ai; for( j=i-1; a0.zfaj.zf;-j ) aj+1=aj; aj+1=a0; printf(n排名结果为：n); for(i=1;i=6;i+) printf(%3d ,i); printf( %3d,ai.xh); printf( %fn,ai.zf); 输出结果为： 2 能否将程序段中的斜体字部分进行改写？请写出至少一种改写后的算法。 for(i=1; i6; i+) for(j=1;jaj+1.zf) a0=aj; aj=aj+

4、1;aj+1=a0; 2、#include void main struct student int num; char name20; float score; stu10,*p; int i,temp=0; float max; for(i=0;i10;i+) scanf (%d %s%f, &stui.num,stui.name,&stui.score); max=stu0.score; for(i=1;i10;i+) if(maxnum,p-name,p-score); 3.计算任意输入的正整数的各位数字之和 1）源程序为： #include stdio.h int sum(int x

5、) int x1,s; s=x%10; x1=x/10; while(x1!=0) s=s+x1%10; x1=x1/10; return s; 3 void main int a; scanf(%d,&a); printf(sum= %d,sum(a); 2）分析该算法的时间复杂度为： O(n) n为数字的位数 4.编写一个程序，判断一个字符串是否为“回文” 1）源程序为： #include stdio.h int huiwen(char *a) int len,i; for(len=0;alen!=0;len+); for(i=0;ai=alen-i-1 & ilen/2) return

6、1; else return 0; void main char a20; gets(a); puts(a); if(huiwen(a)printf(是回文); else printf(不是回文); 2）分析该算法的时间复杂度为： O(n) n为字符串的长度 4 实 验 报 告 院： 课程名称：数据结构 日期： 班级 专业 计算机科学与技术 实验顺序表的运算 名称 所用软件 实 验 目 的 实 验 准 备 学号 姓名 实验室 计算机号 成绩评定 教师签名 V C或TC 1 掌握线性表的基本概念 2 掌握线性表的建立、插入和删除等方法。 3 掌握线性表的基本算法。 1、 复习书上有关内容。 2、

7、 阅读实验步骤中的函数，写出函数功能。 3、 写出实验步骤2、3的源程序。 实 验 总 结 1、各子函数功能： *init_sqlist( ) 线性表的初始化 creatsqlist(sqlist *L) 线性表的建立 Location_sqlist(sqlist *L, int x) 在线性表中查找指定元素 InsList(sqlist *L,int i,int x) 将x插入到线性表的第i个位置 2.下列函数的功能是在顺序表中删除第i个元素，请编制主函数进行函数调用，上机调试运行。 #define MAXSIZE 100 #include stdio.h #include stdlib.h

8、 typedef int elemtype; typedef struct elemtype elemMAXSIZE; int last; sqlist; sqlist *init_sqlist( ) sqlist *L; L=(sqlist *)malloc(sizeof(sqlist); L-last=-1; return L; void creatsqlist(sqlist *L) int i; printf(请输入线性表的长度); scanf(%d,&i); L-last=i-1; for(i=0;ilast;i+) 5 scanf(%d,&(*L).elemi); int DelLi

9、st(sqlist *L,int i,elemtype *e) /*在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1iL.last+1 */ int k; if(iL-last+1) printf(删除位置不合法!); return(0); *e = L-elemi-1; /* 将删除的元素存放到e所指向的变量中*/ for(k=i; klast; k+) L-elemk-1 = L-elemk; /*将后面的元素依次前移*/ L-last-; return(1); void main sqlist *l;elemtype e; int i; l=init_sqlist

10、; creatsqlist(l); printf(建立的线性表为：n); for(i=0;ilast;i+) printf(%4d,l-elemi); if (DelList(l,2,&e) printf(n删除成功n); printf(删除一个元素的线性表为：n); for(i=0;ilast;i+) printf(%4d,l-elemi); 3.源代码如下： #define MAXSIZE 100 #include stdio.h #include stdlib.h typedef int elemtype; typedef struct elemtype elemMAXSIZE; int

11、 last; sqlist; sqlist *init_sqlist( ) 6 sqlist *L; L=(sqlist *)malloc(sizeof(sqlist); L-last=-1; return L; void creatsqlist(sqlist *L) int i; printf(请输入线性表的长度); scanf(%d,&i); L-last=i-1; printf(请输入线性表中的各元素值，注意：必须有序); for(i=0;ilast;i+) scanf(%d,&(*L).elemi); void merge(sqlist *LA, sqlist *LB, sqlist

12、*LC) int i,j,k; i=0;j=0;k=0; while(ilast&jlast) if(LA-elemielemj) LC-elemk= LA-elemi; i+; k+; else LC-elemk=LB-elemj; j+; k+; while(ilast) /*当表LA有剩余元素时，则将表LA余下的元素赋给表LC*/ LC-elemk= LA-elemi; i+; k+; while(jlast) /*当表LB有剩余元素时，则将表LB余下的元素赋给表LC*/ LC-elemk= LB-elemj; j+; k+; LC-last=LA-last+LB-last+1; 7 v

13、oid main sqlist *la,*lb,*lc; int i; printf(先建立线性表lan); la=init_sqlist; creatsqlist(la); printf(n所建立的线性表la为：); for(i=0;ilast;i+) printf(%4d,la-elemi); printf(n再建立线性表lbn); lb=init_sqlist; creatsqlist(lb); printf(n所建立的线性表lb为：); for(i=0;ilast;i+) printf(%4d,lb-elemi); lc=init_sqlist; merge(la,lb,lc); pr

14、intf(合并后的线性表lc为：n); for(i=0;ilast;i+) printf(%4d,lc-elemi); 4.源程序为： #define MAXSIZE 100 #include stdio.h #include stdlib.h typedef int elemtype; typedef struct elemtype elemMAXSIZE; int last; sqlist; int InsList(sqlist *l,elemtype x) int i; if(l-last=MAXSIZE-1) return 0; for(i=l-last;l-elemix & i=0;

15、i-) l-elemi+1=l-elemi; l-last+; l-elemi+1=x; return 1; void main /* 顺序表插入的主函数 */ 8 int i; sqlist *L; L=(sqlist *)malloc(sizeof(sqlist); L-last=-1; for(i=0;ielemi=i*3;L-last=L-last+1; for(i=0;ilast;i+) printf( %d,L-elemi); printf(n); printf(n); InsList(L,4); /*执行函数调用*/ for(i=0;ilast;i+) printf( %d,L-

16、elemi); 9 实 验 报 告 院： 课程名称：数据结构 日期： 班 级 专 业 实线性链表的运算 验名称 所用软件 实 验 目 的 实 验 准 备 学号 姓名 实验室 计算机号 成绩评定 V C 教师签名 4 掌握线性链表的基本概念 5 掌握线性链表的建立、插入和删除等方法。 6 掌握线性链表的基本算法。 1、 复习书上有关内容。 2、 阅读实验内容1，进行程序填空，并编制相应的主函数。 3、 编出实验内容2 的源程序。 一、线性链表基本操作 阅读下列各函数，进行程序填空并写出主函数，上机调试，写出运行结果。 #include stdio.h #include stdlib.h type

17、def char elemtype; typedef struct node elemtype data; struct node *next; NODE,*LINKLIST; /*链表的建立*/ LINKLIST createlistf char ch; LINKLIST head; NODE *p; head=(LINKLIST )malloc(sizeof(NODE); head-next=0; ch=getchar; while(ch!=$) p=(NODE *)malloc(sizeof(NODE); 10 实 验 内 容 p-data=ch; 1 2 ch=getchar; ret

18、urn (head); /*在链表的P指定结点之后插入值为x的结点*/ int InsLinkList(NODE *p, char x) NODE *s; /* 定义指向结点类型的指针 */ s=(NODE *)malloc(sizeof(NODE); /* 生成新结点 */ 3 4 5 return 1; /*删除P所指向的结点的后继结点*/ void DelLinkList(NODE *p) NODE *q; if(p-next!=0) q=p-next; /* q指向p的后继结点 */ 6 /* 修改p结点的指针域 */ free(q); /* 删除并释放结点 */ /*在链表中查找指定

19、结点*/ NODE *lbcz(NODE *h,int x) NODE *p; p=h; while (p!=0 & p-data!=x) 7 return(p); /*链表的输出*/ void printlink(NODE *h) NODE *p; p=h-next; printf(n); while (p!=0) printf(%c,p-data); p=p-next; 11 printf(n); main 二、已知一个有序的单链表，现有一个数据e，请将e插入到该单链表中并要求插入后单链表依然有序。 提示： 单链表中原有数据个数为10个，比如依次是1,3,5,7,12,45,67,89,9

20、2,99。 需要插入的数据e值为25。 有序表的插入，需要分两步完成：第一步确定插入位置，第二步在插入位置上插入指定的数据。 一、程序： #include stdio.h #include stdlib.h typedef char elemtype; typedef struct node elemtype data; struct node *next; NODE,*NODEPTR; NODEPTR createlistf char ch; NODEPTR head; NODE *p; head=(NODEPTR )malloc(sizeof(NODE); head-next=0; ch=

21、getchar; while(ch!=n) p=(NODE *)malloc(sizeof(NODE); p-data=ch; p-next=head-next; head-next=p; ch=getchar; return (head); int InsLinkList(NODE *p, char x) 12 实 验 总 结 NODE *s; /* 定义指向结点类型的指针 */ s=(NODE *)malloc(sizeof(NODE); /* 生成新结点 */ s-data=x; s-next=p-next; p-next=s; return 1; void DelLinkList(NO

22、DE *p) NODE *q; if(p-next!=0) q=p-next; /* q指向p的后继结点 */ p-next=q-next; /* 修改p结点的指针域 */ free(q); /* 删除并释放结点 */ NODE *lbcz(NODE *h,int x) NODE *p; p=h; while (p!=0 & p-data!=x) p=p-next; return(p); void printlink(NODE *h) NODE *p; p=h-next; printf(n); while (p!=0) printf(%c,p-data); p=p-next; printf(n

23、); void main NODE *h,*p; h=createlistf; printlink(h); p=lbcz(h,a); InsLinkList(p,k); printlink(h); p=lbcz(h,a); DelLinkList(p); printlink(h); 二、源代码以及输入数据输出结果为： #include stdio.h 13 #include stdlib.h typedef int elemtype; typedef struct node elemtype data; struct node *next; NODE,*NODEPTR; NODEPTR cre

24、atelistf int ch; NODEPTR head; NODE *p; head=(NODEPTR )malloc(sizeof(NODE); head-next=0; scanf(%d,&ch); while(ch!=0) p=(NODE *)malloc(sizeof(NODE); p-data=ch; p-next=head-next; head-next=p; scanf(%d,&ch); return (head); int InsLinkList(NODE *h, int x) NODE *s,*q,*p; /* 定义指向结点类型的指针 */ p=h;q=p; while(

25、p-next!=NULL & p-datanext; s=(NODE *)malloc(sizeof(NODE); /* 生成新结点 */ s-data=x; s-next=q-next; q-next=s; return 1; void printlink(NODE *h) NODE *p; p=h-next; printf(n); while (p!=0) printf( %d,p-data); p=p-next; 14 printf(n); void main NODE *h; printf(用头插法建有序链表，注意输入数字的顺序与得到顺序相反，以0作为结束n); h=createlis

26、tf; printf(建立的链表为); printlink(h); InsLinkList(h,55); printf(插入后的链表为); printlink(h); 运行情况为： 15 实 验 报 告 院： 课程名称：数据结构 日期： 班 级 专 业 学号 姓名 实验室 计算机号 成绩评定 实栈与队列的基本使用 验名称 所用软件 实 验 目 的 实 验 准 备 V C或TC 教师签名 7 掌握栈与队列的基本概念 8 掌握顺序栈的建立、入栈和出栈等方法。 9 掌握循环队列的概念和建立、入队出队方法。 10 了解链栈、链队的概念及有关操作。 1、 复习书上有关内容。 2、 阅读实验内容1，写出子

27、函数功能并进行程序填空。 3、 阅读实验内容2，写出各子函数功能 4、 编出实验内容3 的源程序。 一、栈的基本操作 实 验 内 容 利用栈将一个十进制数字转换成一个二进制数。请写出子函数功能并进行程序填空再上机运行。 程序如下： #include stdio.h #include stdlib.h #define Stack_size 30 typedef struct int elemStack_size; int top; SeqStack; void InitStack(SeqStack *s) s-top=-1; int Push(SeqStack *s,int x) if(s-to

28、p=Stack_size-1) return(0); s-top+; s-elems-top=x; return(1); 16 int Pop(SeqStack *s,int *x) if (s-top=-1)return 0; else *x=s-elems-top; s-top-; return(1); int IsEmpty(SeqStack s) if(s.top=-1) return 1; else return(0); void Conversion(int N) SeqStack S; int x; InitStack(&S); while(N0) x=N%2; Push(&S,

29、x); N=N/2; while(!IsEmpty(S) Pop(&S,&x); printf(%d,x); void main int x; printf(Enter a number:); scanf(%d,&x); Conversion(x); 二、队列的基本操作： #define qsize 50 #include stdio.h typedef struct int dataqsize; int front,rear; sqqueue; int inqueue(sqqueue *q,int x) /入队运算 if(q-rear+1=q-front) printf(queue over

30、flow);return 0; q-dataq-rear=x; q-rear=(q-rear+1)%qsize; return(1); 17 int dequeue(sqqueue *q) /出队运算 int temp; if (q-rear=q-front) printf(queue underflow);return(0); temp=q-dataq-front; q-front=(q-front+1)%qsize; return(temp); void prin(sqqueue *q) /输出 int i; printf(n); for(i=q-front;i!=q-rear;i=(i+

31、1)%qsize) printf( %d,q-datai); printf(n); void main /主函数 sqqueue sq; int I; sq.front=0; /队列初始化 sq.rear=0; for (I=0;Itop=Stack_Size-1) return(0); S-top+; S-elemS-top=x; return(1); int pop(SeqStack *S, int *x) if(S-top=-1) printf(stack empty); return(0); else *x=S-elemS-top; S-top-; return(1); NODEPTR

32、 createlistf int ch; NODEPTR head; NODE *p; head=(NODEPTR )malloc(sizeof(NODE); head-next=0; scanf(%d,&ch); while(ch!=0) p=(NODE *)malloc(sizeof(NODE); p-data=ch; p-next=head-next; head-next=p; scanf(%d,&ch); return (head); void nizhi(NODE *h) 19 NODE *p; /* 定义指向结点类型的指针 */ SeqStack s; s.top=-1; p=h-

33、next; while(p!=NULL) push(&s,p-data);p=p-next; p=h-next; while(p!=NULL) pop(&s,&(p-data);p=p-next; void printlink(NODE *h) NODE *p; p=h-next; printf(n); while (p!=0) printf( %d,p-data); p=p-next; printf(n); void main NODE *h; printf(用头插法建有序链表，注意输入数字的顺序与得到顺序相反，以0作为结束n); h=createlistf; printf(建立的链表为);

34、 printlink(h); nizhi(h); printf(逆置后的链表为); printlink(h); 20 实 验 报 告 院： 课程名称：数据结构 日期： 班级 专业 实验串与数组、特殊矩阵 名称 所用软件 实 验 目 的 实 验 准 备 学号 姓名 实验室 计算机号 成绩评定 教师签名 V C或TC 11 12 13 掌握串的基本概念与操作 掌握数组的概念及基本操作。 掌握特殊矩阵的压缩存储方法。 1、 复习书上有关内容。 2、 阅读实验内容1，进行程序填空，并写出各子函数功能。 3、 阅读实验内容2，编出子函数。 4、 编出实验内容3 、4的源程序。 一、下面是有关串的程序，请

35、进行阅读并进行填空，再上机调试。 #define maxsize 50 #include stdio.h int StrLength(char s) int i; for(i=0;si!=0;i+); return(i); int StrConcat1(char *s1,char *s2,char *s) int i=0,j,len1,len2; len1=StrLength(s1); len2=StrLength(s2); if( ) return(0); j=0; while(s1j!=0) ; i+; j+; while(s2j!=0) si=s2j; i+; j+; si=0; return 1; 21 实 验 内 容 int StrSub (char *t, char *s, int i, int len) /* 用t返回串s中第个i字符开始的长度为len 的子串1i串长*/ int slen;int j; slen=StrLength(s); if ( ) printf(参数不对); return 0; for (j=0; jlen; j+) ; tj=0; return