数据结构实验指导书(新2005.6)

1、 实验一 顺序表的基本操作一、实验目的1理解线性表顺序表示的基本概念及顺序表在计算机上的实现。2掌握顺序表的基本操作算法。3学会用c语言编写算法并上机调试通过。二、实验内容1建立顺序表。2对顺序表进行元素的插入和删除操作。三、验证实验1实验要求1）输入一个顺序表，并输出，验证输入的内容与输出的内容是否一致。2）实现顺序表的插入操作（在第i个元素之前插入一个元素，即将线性表中从第i个元素开始的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置）。3）实现顺序表的删除操作（删除第i个元素，即把第i个元素之后的所有元素前移一个位置）。2核心算法采用的数据描述为：顺序表在c语言中用一维

2、数组表示。#define maxlen 100/*线性表的最大长度*/typedef structelemtype elemmaxlen; /*顺序表中存放元素的数组，其中elemtype为抽象数据类型，在程序具体实现时可以用任意类型代替*/ int last; /*顺序表的长度，即元素个数*/sqlisttp;status insert(sqlisttp &v,int i,elemtype b) /*在顺序表v中第i个元素前插入新元素b*/if (iv.last+1) return error; /*插入位置不正确则出错*/ else if (v.last=maxlen) return ov

3、erflow; /*顺序表v中已放满元素，再做插入操作则溢出*/ else for(j=v.last-1;j=i-1;j-) v.elemj+1=v.elemj;/*将第i个元素及后续元素位置向后移一位*/ v.elemi-1=b;/*在第i个元素位置处插入新元素b*/ v.last+;/*顺序表v的长度加1*/ return ok; status delete(sqlisttp &v,int i) /*在顺序表v中删除第i个元素*/if (iv.last) return error; /*删除位置不正确则出错*/else for(j=i;j=v.last-1;j+) v.elemj-1=v.

4、elemj; /*将第i+1个元素及后继元素位置向前移一位*/ v.last-;/*顺序表v的长度减1*/ return ok； 3程序代码参考#define maxlen 50typedef structint elemmaxlen;int last;sqlisttp;sqlisttp insert(sqlisttp v,int i,int b) /*顺序表插入函数*/int j; if(iv.last+1) printf(error!); else if(v.last=maxlen) printf(overflow!); else for(j=v.last-1;j=i-1;j-) v.el

5、emj+1=v.elemj; v.elemi-1=b; v.last+;return v;sqlisttp delete(sqlisttp v,int i) /*顺序表删除函数*/int j; if(iv.last) printf(error!); else for(j=i;j=v.last-1;j+) v.elemj-1=v.elemj; v.last-;return v;void display(sqlisttp v) /*顺序表元素输出函数*/ int j; for(j=0;j=v.last-1;j+) printf(%d ,v.elemj); printf(n); main() /主函

6、数 sqlisttp v;int i,b,j,value;printf(please input the length:n);/*请求输入顺序表中元素个数*/scanf(%d,&v.last);printf(n please input the value:n);/*请求输入顺序表中各个元素*/for(j=0;jnext=null;/*头结点的指针域初始为空*/ while(node!=0) p=(linklist)malloc(sizeof(lnode);/*生成一个新结点*/ p-data=node;/*新结点数据域赋值*/ p-next=l-next;/*新结点指针域指向开始结点*/ l

7、-next=p; /*头结点指针域指向新结点，即新结点成为开始结点*/ void creat2(linklist &l) /*用尾插法建立单链表(带头结点)*/ l=(linklist)malloc(sizeof(lnode);/*生成头结点*/ l-next=null;/*头结点的指针域初始为空*/ r=l;/*尾指针初始指向头结点*/ while(node!=0) p=(linklist)malloc(sizeof(lnode);/*生成一个新结点*/ p-data=node; /*新结点数据域赋值*/ p-next=null; /*新结点指针域为空*/ r-next=p;/*尾结点指针域

8、指向新结点*/ r=p; /*尾指针指向新结点，即新结点成为尾结点*/ status list_insert(linklist &l,int i;elemtype x) /*在带头结点的单链表l中第i个位置之前插入新元素x*/ p=l; j=0; while(p!=null&jnext; +j;/*寻找插入位置，使p指向单链表l中第i-1个位置*/ if(p=null|ji-1) return error;/*若位置不正确则出错*/ s=(linklist)malloc(sizeof(lnode);/*生成一个新结点*/ s-data=x;/*新结点数据域赋值*/ s-next=p-next;

9、/*新结点指针域指向p的后继结点*/ p-next=s;/*新结点成为p的后继结点*/ return ok;status list_delete(linklist &l,int i)/*在带头结点的单链表l中，删除第i个结点*/ p=l;j=0; while(p-next!=null&jnext; +j; /*寻找插入位置，使p指向单链表l中第i-1个位置*/ if (p-next=null|ji-1) return error;/*若位置不正确则出错*/ q=p-next; /* q指向p的后继结点*/ p-next=q-next;/*q的后继结点成为p的后继结点*/ x=q-data;/*

10、返回第i个位置的元素*/free(q);/*释放q所指结点的空间*/return ok;3程序代码参考#include typedef struct lnode int data; struct lnode *next;londe,linklist;linklist creat(linklist l) /*单链表建立函数 */int node; linklist p; l=(linklist)malloc(sizeof(lnode); l-data=-1; l-next=null; printf(n please input the node(end with 0):n);/*请求输入顺序表中

11、各个元素*/ scanf(%d,&node); while(node!=0) p=(linklist)malloc(sizeof(lnode); p-data=node; p-next=l-next; l-next=p; printf(n please input the node(end with 0):n); scanf(%d,&node); return l;linklist insert(linklist l,int i,int x) /*单链表插入函数*/int j;linklist p,s; p=l; j=0; while (p!=null&jnext; +j; if (p=nul

12、l|ji-1) printf(n error position!n); else s=(linklist)malloc(sizeof(lnode); s-data=x; s-next=p-next;p-next=s;return l;linklist delete(linklist l,int i) /*单链表删除函数*/int j,x; linklist p,q;p=l; j=0;while(p-next!=null&jnext; +j;if(p-next=null|ji-1) printf(n erroe position!n); else q=p-next; p-next=q-next;

13、 x=q-data; printf(nthe delete data is:%dn,x); free(q);return l;void display(linklist l) /*单链表元素输出(遍历)函数*/linklist p; p=l-next; while(p!=null) printf(%d ,p-data); p=p-next;printf(n);main()/*主函数*/ linklist l; int i,x; l=creat(l);/*调用单链表建立函数*/ display(l); /*调用单链表元素输出(遍历)函数*/printf(n please input the po

14、sition you want to insert:);/*请求输入插入操作位置*/ scanf(%d,&i); printf(n please input the node you want to insert:);/*请求输入需要插入的元素*/ scanf(%d,&x); l=insert(l,i,x);/*调用单链表插入函数*/ display(l);/*调用单链表元素输出(遍历)函数*/ printf(n please input the node position you want to delete:); /*请求输入删除操作位置*/ scanf(%d,&i); l=delete(

15、l,i); /*调用单链表删除函数*/ display(l); /*调用单链表元素输出(遍历)函数*/ 4执行结果please input the node(end with 0):11please input the node(end with 0):33please input the node(end with 0):22please input the node(end with 0):55 please input the node(end with 0):44please input the node(end with 0):77 please input the node(end

16、 with 0):66please input the node(end with 0):99please input the node(end with 0):88please input the node(end with 0):111please input the node(end with 0):0111 88 99 66 77 44 55 22 33 11please input the position you want to insert:3please input the node you want to insert:456111 88 456 99 66 77 44 55

17、 22 33 11please input the node position you want to delete:7the delete data is:44111 88 456 99 66 77 55 22 33 11四、设计实验编写在双向链表存储结构中实现插入和删除操作的算法，并用程序加以实现。采用的数据描述为：typedef struct dulnode elemtype data;/*数据域*/ struct dulnode *prior;/*指向前驱结点的指针域*/ struct dulnode *next;/*指向后继结点的指针域*/ dulnode,*dulinklist;实

18、验三 队列的基本操作一、实验目的1掌握队列的基本概念、队列与线性表的区别、队列的形式定义以及在计算机上的实现。2掌握入队和出队操作及队列在实际问题中的简单应用。二、实验内容1建立循环队列。2对循环队列进行元素的插入和删除操作。三、验证实验1实验要求1）用数组作为存储空间建立一个循环队列，并输出，观察输入前后的内容变化。2）实现循环队列的入队和出队操作，观察“头指针”、“尾指针”（虚拟指针）的移动情况（入队操作指将新元素插入到队列尾部，成为队列新的队尾元素；出队操作指删除队首元素）。注意：利用模运算解决循环队列中遇到的下标越界问题。2核心算法采用的数据描述为：循环队列采用顺序结构#define

19、maxqsize 100/*循环队列的最大长度*/ typedef struct elemtype basemaxqsize; /*存放元素的数组空间*/int front; /*“头指针”*/int rear; /*“尾指针”*/ sqqueue;status enqueue(sqqueue &q,elemtype x) /*在循环队列q中，插入新元素使其成为队尾元素*/ if (q.rear+1)%maxqsize=q.front) return error;/*若队列满，插入操作出错*/ q.baseq.rear=x;/*新元素成为队尾元素*/ q.rear=(q.rear+1)%max

20、qsize;/*利用模运算，“尾指针”加1*/ return ok; status dequeue(sqqueue &q)/*在循环队列q中，删除q的队首元素*/ if (q.front=q.rear) return error;/*若队列空，删除操作出错*/ x=q.baseq.front;/*取队首元素*/ q.front=(q.front+1)%maxqsize;/*利用模运算，“头指针”加1*/ return ok;3程序代码参考#define maxqsize 100#define n 5typedef struct int *base;int front; int rear; sq

21、queue;sqqueue initqueue(sqqueue q)/*队列初始化函数*/ q.base=(int *)malloc(maxqsize*sizeof(int); if(!q.base) printf(overflown); else q.front=q.rear=0; return q;sqqueue enqueue(sqqueue q,int x)/*队列插入函数*/ if (q.rear+1)%maxqsize=q.front) printf(errorn); elseq.baseq.rear=x; q.rear=(q.rear+1)%maxqsize; return q;

22、sqqueue dequeue(sqqueue q)/*队列删除函数*/ int x; if (q.front=q.rear) printf(errorn ); else x=q.baseq.front; printf(nthe delete data is:%d,x); q.front=(q.front+1)%maxqsize; return q;void display(sqqueue q)/*队列元素输出函数*/int k,m; k=q.front;m=q.rear;while(k!=m) printf(%5d,q.basek); k=(k+1)%maxqsize; printf(n);

23、main()/*主函数*/sqqueue q;int i,x,y;q=initqueue(q);/*调用队列初始化函数*/printf(please input create data:n);/*请求输入队列中各个元素*/ for(i=1;idata=x;/*新结点数据域赋值*/ createbitree(t-lchild);/*递归建立左子树*/ createbitree(t-rchild); /*递归建立右子树*/ status preorder(bitree &t) /*先序遍历二叉树*/ if(t!=null)/*若二叉树非空*/ visit(t-data);/*访问根结点*/ pre

24、order(t-lchild);/*递归先序遍历左子树*/ preorder(t-rchild); /*递归先序遍历右子树*/ return ok;status inorder(bitree &t) /*中序遍历二叉树*/ if(t!=null) /*若二叉树非空*/ inorder(t-lchild); /*递归中序遍历左子树*/ visit(t-data); /*访问根结点*/ inorder(t-rchild); /*递归中序遍历右子树*/ return ok; status postorder(bitree &t) /*后序遍历二叉树*/ if(t!=null) /*若二叉树非空*/

25、postorder(t-lchild); /*递归后序遍历左子树*/ postorder(t-rchild); /*递归后序遍历右子树*/ visit(t-data); /*访问根结点*/ return ok; 3程序代码参考#include typedef struct bitnodechar data; struct bitnode *lchild,*rchild;bitnode,*bitree;bitree creat(bitree t)/*建立二叉树函数*/char x; scanf(%c,&x); if (x=#) t=null; else t=(bitree)malloc(size

26、of(bitnode); t-data=x; t-lchild=creat(t-lchild); t-rchild=creat(t-rchild); return t; bitree preorder(bitree t)/*先序遍历二叉树函数*/ if (t!=null) printf(%c,t-data); t-lchild=preorder(t-lchild); t-rchild=preorder(t-rchild);return t; bitree midorder(bitree t) /*中序遍历二叉树函数*/ if (t!=null) t-lchild=midorder(t-lchi

27、ld); printf(%c,t-data); t-rchild=midorder(t-rchild);return t; bitree backorder(bitree t) /*后序遍历二叉树函数*/ if (t!=null) t-lchild=backorder(t-lchild); t-rchild=backorder(t-rchild); printf(%c,t-data);return t; main()/*主函数*/ bitree t;char x;int y;t=null； printf(creat tree!n);/*请求输入二叉树中各个元素*/ t=creat(t);/*调

28、用建立二叉树函数*/ printf(please input the choose!:n);/*请求选择遍历方式*/ printf(1-preorder 2-midorder 3-backorder); scanf(%d,&y); switch(y) case 1:t=preorder(t);break;/*调用先序遍历二叉树函数*/ case 2:t=midorder(t);break; /*调用中序遍历二叉树函数*/ case 3:t=backorder(t);break; /*调用后序遍历二叉树函数*/ default:printf(error!n); 4执行结果creat tree!a

29、b#cd#please input the choose!1-preorder 2-midorder 3-backorder:3bdca对应的二叉树如下图所示: abbcd 四、设计实验编写两棵二叉树判断相等的算法，要求用先序、中序、后序三种方法解决问题，并用相应程序加以实现。实验五 用任意方法对给定的数组排序一、实验目的1熟悉并掌握各种排序方法的设计思路。2掌握在计算机上实现的各种具体排序操作。二、实验内容1实现插入排序操作（插入排序基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的序列中的适当位置，直到全部记录插入完成为止）。2实现交换排序操作（交换排序基本思想：在待排

30、序的序列中，找到不满足有序性的两个关键字，交换位置，以满足有序性，重复整个过程直到该序列中的所有关键字都有序为止）。3实现选择排序操作（选择排序基本思想：每一趟从待排序的记录中选出关键字最小的记录，并顺序放在已排好序的序列的最后，直到全部记录排序好为止。三、验证实验采用的数据描述为：#define maxsize 100/*数组的最大长度*/typedef int keytypetypedef struct keytype key;/*关键字项*/ infotype otherinfo;/*其它数据项*/redtype;typedef struct redtype rmaxsize+1;/*存

31、放记录中各个数据项的数组*/ int length;/*数组长度*/ sqlist;1对给定的数组，用任意一种插入排序方法对它进行排序，观察数组在排序前后的变化情况。直接插入排序（插入排序的一种）1）基本思想假设待排序的记录存放在数组rn中，排序过程的某一中间时刻，数组r被划分成两个子区间r1，ri-1和ri，rn，其中前一个子区间是已排好序的有序区，后一个区间是当前未排好序的无序区。直接插入排序的基本操作是将当前无序区的第一个记录ri插入到有序区中适当位置，使r1到ri变成新的有序区。2）基本步骤初始时，令i=1，由于一个记录自然有序，故r1自成一个有序区，无序区是r2到rn，然后依次将r2

32、，r3，插入到当前的有序区中，直到i=n时，将rn插入到有序区为止。3）核心算法void insertsort(sqlist &l)/*直接插入排序*/ for (i=2;i=l.length;+i) if (l.ri.keyl.ri-1.key) l.r0=l.ri;/*l.r0具有监视哨的作用*/ for(j=i-1;l.r0.keyl.rj.key;-j) l.rj+1=l.rj;/*记录后移*/ l.rj+1=l.r0; 4）程序代码参考#define maxsize 100#define n 10typedef int keytype;typedef structkeytype ke

33、y;redtype;typedef structredtype rmaxsize+1;int length;sqlist;sqlist insertsort(sqlist l)/*直接插入排序函数*/ int i,j; l.length=n; for (i=2;i=l.length;+i) if (l.ri.keyl.ri-1.key) l.r0=l.ri; for(j=i-1;l.r0.keyl.rj.key;-j) l.rj+1=l.rj; l.rj+1=l.r0; return l;main()/*主函数*/sqlist l;int i; printf(please input 10 d

34、ata:n);/*请求输入10个数据*/ for(i=1;i=n;i+) scanf(%d,&l.ri.key); l=insertsort(l);/*调用直接插入排序函数*/ printf(after insert sort data is:n);/*输出排序后的序列*/ for(i=1;i=n;i+) printf(%5d,l.ri.key); 5）执行结果please input 10 data:14 4 2 56 3 76 5 89 123 34after insert sort data is:2 3 4 5 14 34 56 76 89 1232对给定的数组，用任意一种交换排序方法

35、对它进行排序，观察数组在排序前后的变化情况。起泡排序（交换排序的一种）1）基本思想将待排序的记录看成从上到下的存放，把关键字较小的记录看成“较轻的”，关键字较大的记录看成“较重的”，小关键字的记录好像水中的气泡一样，向上浮；大关键字的记录如水中的石块向下沉，当所有的气泡都浮到了相应的位置，且所有的石块都沉到了水中，排序就结束了。2）基本步骤首先比较第一个和第二个记录的关键字，将其中较小的关键字放到前一个位置，较大的放到第二个位置，然后比较第二个和第三个关键字，仍将较小的关键字放到前一个位置，较大的放到后一个位置，依此类推，直到比较第n-1个和第n个关键字，这样，就将排序序列中最大的一个关键字放

36、到了第n个位置，此为一趟起泡排序，下面再对n-1个记录重复这个过程。3）核心算法void bubblesort(sqlist &l)/*起泡排序*/ for (i=1;i=l.length-1;+i) for(j=1;j=l.length-i;+j) if (l.rj+1.keyl.rj.key) temp=l.rj; l.rj=l.rj+1; l.rj+1=temp; /*数据交换*/ 4）程序代码参考#define maxsize 100#define n 10typedef int keytype;typedef structkeytype key;redtype;typedef str

37、uctredtype rmaxsize+1;int length;sqlist;sqlist bubblesort(sqlist l)/*起泡排序函数*/int i,j,d; redtype temp; l.length=n; for (i=1;i=l.length-1;+i) for(j=1;j=l.length-i;+j) if (l.rj+1.keyl.rj.key) temp=l.rj; l.rj=l.rj+1; l.rj+1=temp; return l;main()/*主函数*/sqlist l;int i;printf(please input 10 data:n);/*请求输入

38、10个数据*/for(i=1;i=n;i+) scanf(%d,&l.ri.key);l=bubsort(l);/*调用起泡排序函数*/printf(after bubblesort data is:n);/*输出排序后的序列*/for(i=1;i=n;i+) printf(%5d,l.ri.key);5）执行结果please input 10 data:14 4 2 56 3 76 5 89 123 34after bubblesort data is:2 3 4 5 14 34 56 76 89 123 3对给定的数组，用任意一种选择排序方法对它进行排序，观察数组在排序前后的变化情况。直接选择排序（选择排序的一种）1）基本思想首先在所有记录中选出关键字最小的记录，把它与第一个记录进行位置交换，然后在其余的记录中再选出关键字次小的记录与第二个记录进行位置交换，依此类推，直到所有记录排好序。2）基本步骤*置i为1*当in，重复下列步骤：在（ri,rn）中选出一个关键字最小的记录rk，若rk不是ri，（即k!=i），交换ri,rk的位置，否则不进行交换；i值加1。3）核心算法void selectsort(sqlist &l)/*直接选择排序*/ for(i=1;i=l.length-1;+i) k=i; for(j=i+1;j=l.length;+j) i