2014数据结构实验报告

课程名称：实验项目：实验地点：专业班级：学生姓名：指导教师：

数据结构 实验一 线性表 博学楼B座 学号： 2012

杨崇艳

2014年11月02日

实验一 线性表

一．实验目的

二．实验例题

[问题描述]

用链表形式存储一个字符串，插入、删除某个字符，最后按正序、逆序两种方式输出字符串。 [输入]

初始字符串，插入位置，插入字符，删除字符。 [输出]

已建立链表（字符串），插入字符后链表，删除字符后链表，逆转后链表。 [存储结构]

采用链式存储结构 [算法的基本思想]

建立链表：当读入字符不是结束符时，给结点分配存储空间，写数据域，将新结点插到表尾；插入字符：根据读入的字符在链表中找插入位置，将新结点插入到该位置之前；删除字符：根据读入的删除字符在链表中找到被删结点后，将其从链表中删除；链表逆转：从链表的第一个结点开始对所有结点处理，将每个结点的前驱变为它的后继；打印链表：从链表的第一个结点开始，依次打印各个结点的数据域。

三．程序清单

#define NULL 0

typedef struct node{ char a;

struct node *link; }node,*nodelink;

void readlink(nodelink head){ nodelink p,q; char c; p=head;

printf(\ scanf(\ if (c=='\\n') printf(\。\ while(c!='\\n')

{ q=(nodelink)malloc(sizeof(node)); q->a=c; p->link=q; p=q; scanf(\ }

p->link=NULL; }

void writelink(nodelink head) { nodelink q;

if (head->link==NULL) printf(\。\\n\ for(q=head->link;q;q=q->link) printf(\ printf(\ }

int insert(nodelink head,char k1,char k2) { nodelink p,q; p=head->link;

while(p->a!=k1&&p) p=p->link;

if(p){ q=(nodelink)malloc(sizeof(node));

q->a=k2; q->link=p->link; p->link=q; return 1; }

else { printf(\} }

int delete(nodelink head,char k) { nodelink p,q;

q=head; p=head->link;

while(((p->a)!=k)&&p){ q=q->link; p=p->link; } if(p) { q->link=p->link; return 1; }

else{ printf(\}

void opside(nodelink head) { nodelink p,q; p=head->link;

while(p->link){ q=p->link; p->link=q->link; q->link=head->link; head->link=q; } } main()

{ char k1,k2,k3; nodelink head;

head=(nodelink)malloc(sizeof(node)); head->link=NULL; readlink(head);

if (head->link!=NULL)

{printf(\ if (head->link!=NULL)

{ printf(\ k1=getch(); printf(\

printf(\ k2=getch(); printf(\

if (insert(head,k1,k2))

{printf(\ printf(\ k3=getch(); printf(\ if (delete(head,k3))

{ printf(\writelink(head); } if (head->link!=NULL)

{printf(\ writelink(head); free(head); } } }

四．运行结果

Input a linktable(a string):dfkdspogjdj↙ Build link is :dfkdspogjdj

Please input a char you want to insert after:s↙ Please input a char you want to insert:n↙ After p insert y,link is:dfkdsnpogjdj

Please input a char you want to delete:k↙ after delete p,link is:dfdsnpogjdj Opsite result is :jdjgopnsdfd

五．实验结果与分析

通过本实验，我熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。丰富了编程经验，提高了对顺序存储结构的知识点的理解和掌握。

课程名称：实验项目：实验地点：专业班级：学生姓名：指导教师：

数据结构 实验二 树 博学楼B座 学号： 201200

杨崇艳

2014年11月02日

实验二 树

一．实验目的

二．实验例题

[问题描述]

任意给定一棵二叉树。试设计一个程序，在计算机中构造该二叉树，并对它 进行遍历。

[输入]

一棵二叉树的结点若无子树，则可将其子树看作 “.”，输入时，按照前序序列的顺序输入该结点的内容。对 下图，其输入序列为ABD..EH...CF.I..G..。

[输出]

若为空二叉树，则输出：THIS IS A EMPTY BINARY TREE。若二叉树不空，按后序序列输出，对上例，输出结果为：DHEBIFGCA。 [存储结构]

采用二叉链表存储。 [算法的基本思想]

采用递归方法建立和遍历二叉树。首先建立二叉树的根 结点，然后建立其左右子树，直到空子树为止。后序遍历二叉树时，先遍历左子树，后遍历右子树，最后访问根结点。

三．程序清单

#include #include struct node {char info;

struct node *llink,*rlink; };

typedef struct node NODE; NODE *creat() { char x; NODE *p;

scanf(\ printf(\ if(x!='.')

{ p=(NODE *)malloc(sizeof(NODE)); p->info=x;

p->llink=creat();

p->rlink=creat(); }

else p=NULL; return p; }

本文来源：https://www.bwwdw.com/article/f9v2.html