数据结构实验报告

实验一、单链表

实验目的：

• 理解线性表的链式存储结构。

• 熟练掌握动态链表结构及有关算法的设计。

（一）、阅读程序：指出算法功能、写出运行结果，并通过运行算法来验证。 （test02_1）此算法的功能是复制单链表。

slist

（二）算法填空：在算法的空白处填入适当的内容来完成算法，以实现指定功能，并通过运行验证。

Tesst02_4 //函数linkLength返回链表L的长度

#include \"linklist.h\"

int linklength(link l) {

link p; int i;

p=l->next; while (p!=NULL){ i++;

_p=p->next; } return i; }

void main() { link l; get_hsllist(l); printf(\"\\nLength=%d\

1 2 15 3 4 5 6 7 8 99 ∧ copy1 1 2 15 3 4 5 6 7 8 99 ∧ copy2 1 2 15 3 4 5 6 7 8 99 ∧ Wait(); }

(三)算法设计：

<1>求链表中第i个节点的指针，若不存在则返回NULL。 node *get_element(node *L,int i) { node *p=L->next; int j=1; while(j!=i&&p!=NULL){ p=p->next; j++; } return p; return NULL; }

<2>在一个递增有序的链表L中插入一个值为x的元素，并保持其递增有序的特性。 void set_insert(node *L,elementtype x) { node *u,*p=L; while(p->next!=NULL&&p->next->datenext; if(p->next==NULL||p->next->date>x) { u=new node; u->date=x; u->next=p->next; p->next=u; } }

实验二、二叉树

实验目的：

• 掌握二叉树的动态链表存储结构及表示。 • 掌握二叉树的三种遍历算法 。

• 运用三种遍历的方法求解有关问题。

（一） 阅读程序：指出算法的功能，写出运行结果，并通过运行算法来验证（test 06_1）

此算法的功能：先序遍历二叉树，依次按先后顺序输出每一个子树和序号。

(1,a)(2,b)(3,c)(4,d)(5,e)(6,f)(7,g)(8,h)(9,i)(10,j)(11,k)(12,l)(13,m)(14,n)(15,o)(16,p)(17,q)(18,r)(19,s)(20,t)(21,u)(22,v)(23,w)(24,x)(25,y)(26,z)

(1,a)(2,b)(3,c)(4,d)(5,e)(6,f)(7,g)(6,h)(7,i)(7,j)(4,k)(5,l)(5,m)(3,n)(4,o)(4,p)(2,q)(3,r)(4,s)(5,t)(5,u)(3,v)(4,w)(5,x)(4,y)(5,z)

（二）算法填空：在算法的空白处填上适当的内容来完成算法，以实现指定功能并验证

test06_3//仅访问其中的叶子节点 void visite_leaf(brite t) {

if(T!=Null) {

if (t->lchild==Null&&t->rchild==Null) visite_bnode(t,1); visite_leaf(t->lchild); visite_leaf(t->rchild); } }

(三)算法调试

test06_4//先遍历二叉树，试修改其中的错误（下面为修改后的程序） void bitrepreorder(brrite t) {if (t!=Null) {

visite_bnode(t,1);

britre preorder(t->lchild); britre preorder(t->rchild); } }

（四）编写算法实现下列问题的求解 <1>求二叉树的高度 int high (Bnode *T) {

if(T==NULL)return 0;

Else return max(high(T->lchild),high(T->rchild))+1; }

<2>按中序次序输出二叉树中各结点的值及其层次书

void inorder(Bnode *T) {

if(T!=NULL) { n++; cout<data<lchild); inorder(T->rchild); } }

实验三 图

实验目的：

• 掌握图的基本概念。

• 熟练掌握图的两种遍历算法、遍历生成树及遍历算法的应用。

（一）算法设计

<1>判断无向图是否连通

bool c(graph G) { int i,k=0; for(i=1;i<=n;i++) visited[i]=false; for(i=1;i<=n；i++) if(visited[i]==false) { K++; dfs(G,i); } if(k==1)return true; else return false;

}

<2>求图中边或弧的数目

void dfs(graph G,int v) {

int w;

visited[v]=true; w=firstadj(G,v); while(w!=0) { E++; if(visited[w]==false) dfs(G,w); w=nextadj(G,v,w); } }

int Enum(graph G) {

int i;E=0;

for(i=1;i<=n;i++) visited[i]=false; for(i=1;i<=n;i++) if(visited[i]==false) dfs(G,i); return E/2; }

实验四 查找

实验目的：

• 掌握顺序表的查找方法，尤其是二分查找方法。 • 掌握二叉排序树的建立及查找。

（一）算法设计

<1>设计算法建立二叉排序树 void create_bst(Bnode *&T) {

Bnode *u; elementtype x; T=Null; cin>>x;

while (x!=End_Of_Num) {

u=new Bnode; u->date=x; u->lchild=Null; u->rchild=Null; insert(T,u); cin>>x; } }

<2>设计算法在二叉树中查找指定值的结点 Bnode *bst_search(Bnode *T,keytype x) {

Bnode *p=T; while (p!=Null) if (x==p->key) return p; else if (xkey) p=p->lchild; else p=p->rchild; return p; }

实验五 排序

实验目的：

• 掌握内部排序的各种算法及相应的性能。

（一）算法设计

<1>设计算法麻将一个整型数组调整为这样的数组，所有3的倍数在最左边，所有除以3

余1的数在中间，而所有除3余2的数在最右边，要求算法所用的时间尽可能的少 int *sort (int A[],int n) {

int i=0; int j=0; int B[]; while(i<=n) { if(A[i]%3==0) {

int B[j]=A[i]; j++; } i++; } i=0;

}

while (i{if (A[i]%3==1) {int B[i]=A[i]; j++; } i++; } i=0;

while(ireturn B;

《数据结构实验报告》

学院：计算机与信息学院

专业班级:通信08-2班

学号：20082487

学生姓名：唐超

任课教师：周红娟