数据结构课程实验设计1 下载本文

删除该结点后继续运行否则让q成为p的前驱指针。最后当p->next==p时停止运行,得到p所指向的结点即为猴子选出大王的编号。

四.程序源代码 #include

#include

/* 定义链表节点类型 */

typedef struct node {

int data;

struct node *next;

}linklist;

int main() {

int i, n, k, m, total;

linklist *head, *p, *s, *q;

/* 读入问题条件 */

printf(\

scanf(\

printf(\enter from the monkeys began to count off the first of several:\

scanf(\

printf(\

scanf(\

/* 创建循环链表,头节点也存信息 */

head = (linklist*) malloc(sizeof(linklist));

p = head;

p->data = 1;

p->next = p;

/* 初始化循环链表 */

for (i = 2; i <= n; i++)

{

s = (linklist*) malloc(sizeof(linklist));

s->data = i;

s->next = p->next;

p->next = s;

p = p->next;

}

/* 找到第 k 个节点 */

p = head;

for (i = 1; i < k; i++)

{

p = p->next;

}

/* 保存节点总数 */

total = n;

printf(\

q = head;

/* 只剩一个节点时停止循环 */

while (total != 1)

{

/* 报数过程,p指向要删除的节点 */

for (i = 1; i < m; i++)

{

p = p->next;

}

/* 打印要删除的节点序号 */

printf(\

/* q 指向 p 节点的前驱 */

while (q->next != p)

{

q = q->next;

}

/* 删除 p 节点 */

q->next = p->next;

/* 保存被删除节点指针 */

s = p;

/* p 指向被删除节点的后继 */

p = p->next;

/* 释放被删除的节点 */

free(s);

/* 节点个数减一 */

total--;

}

/* 打印最后剩下的节点序号 */

printf(\

free(p);

system(\

return 0; }

D 建立二叉树,后序、先序遍历( 用递归或非递归的方法都可以)

一.实验任务:要求能够输入树的各个结点,并能够输出用不同方法遍历的遍历序列;分别建立二叉树存储结构的输入函数、输出后序遍历序列的函数、输出先序遍历序列的函数; 二.需求分析

该程序用非递归的方法,利用先序和中序建立二叉树,然后用后序遍历的方法输出二叉树的元素。

1、输入的形式和输入值的范围;

程序运行时输入二叉树的先序和中序序列,为字符型元素。 2、输出的形式;

运行结果为输出二叉树的后序序列,亦为字符型元素。 3、程序所能达到的功能;

本程序可以建立一个二叉树存储结构,并且访问其结点元素。 4、测试数据: 输入:先序:abcde 中序:edcba

输出:后序:edcba

三. 概要设计

1. 本程序中首先需定义二叉树的节点类型,节点为一个含有数据与和指针域的结构体。 2. 其次,本程序中需要用两个栈,一个用来存放指针,一个用来存放数组元素的下标。 3. 主程序中,分别输入两个字符串,作为二叉树的先序和中序序列;两个子函数分别实现创建二叉树和后序遍历输出二叉树的功能。而在子函数中还调用了例如出栈入栈等子函数。

四. 详细设计

1. 定义二叉树节点类型 struct node {

char data;

struct node *lchild; struct node *rchild; }BTree;

2.定义两个栈的类型 struct snode {

int top; int a[MAX]; };

struct snode1 {

int top;

struct node *c[MAX]; };

3.主函数 void main() {

char a[MAX]={0}; char b[MAX]={0}; char c=0,d=0; int i=0,j=0; struct node *g; snode s;

snode1 s4,s1; Initstack(&s); Initstack1(&s4); Initstack1(&s1);

printf(\请输入先序序列:\\n\ while(c!='\\n') {

c=getchar(); a[i]=c;