数据结构实验指导书学生版.doc

数据结构课程实验指导书LIAOCHENG UNIVERSITY数据结构实验指导书聊城大学计算机学院2015年9月22目录实验一线性表1基本信息1实验预习1实验过程1实验数据和实验结果记录10实验结果分析11实验二栈和队列11基本信息11实验预习11实验过程12实验数据和实验结果记录20实验结果分析22实验三二叉树22基本信息22实验预习23实验过程23实验数据和实验结果记录30实验结果分析30实验四查找31基本信息31实验预习31实验过程31实验数据和实验结果记录35实验结果分析36实验一线性表基本信息实验课程：数据结构设课形式：非独立课程学分：4实验项目：线性表项目类型：设计项目学时：4实验预习实验目的和要求：1、熟悉C语言集成开发环境；2、会定义线性表的顺序结构和链式结构；3、熟悉对线性表的基本操作，如插入、删除等。实验内容和原理或涉及的知识点：自己编写程序实现线性表的建立、插入、删除等功能。实验条件：具有C语言集成开发环境的计算机实验设计方案：设计的顺序表算法有：1、初始化顺序表；2、顺序表的插入操作；3、顺序表的删除操作。设计的链表算法有：1、建立链表；2、链表的插入操作；3、链表的删除操作；4、链表数据元素的访问。实验过程1、根据实验预习阶段的实验设计方案，顺序表算法伪C代码如下。typedef struct ElemType *elem; int length; int listsize;SqList; status InitList(SqList &L) L.elem=(ElemType *) malloc(LIST_INIT_SIZE*sizeof(ElemType); if (!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK;status ListInsert_Sq(SqList &L, int i, ElemType e) if (iL.length+1) return ERROR; if (L.length=L.listsize) newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType) ; if (!newbase) exit (OVERFLOW); L.elem = newbase; L.listsize=L.listsize+LISTINCREMENT; q=&(L.elemi-1); for (p=&(L.elemL.length-1);p=q; -p) *(p+1)=*p;*q=e; L.length+; return OK; status ListDelete_Sq(SqList &L, int i, ElemType &e) if (iL.length) return ERROR; p=&L.elemi-1; e=*p; q=L.elem+L.length-1; for (+p; p=q; +p) *(p-1)=*p; -L.length; return OK; /ListDelete_Sq2、将算法细化为程序代码如下。#include #include #define OK 1#define ERROR 0#define OVERFLOW -2#define LISTINCREMENT 10#define LIST_INIT_SIZE 20typedef int status;typedef int ElemType;typedef struct ElemType *elem;int length;int listsize; SqList;status InitList(SqList *L);/ 构造一个空的线性表status ListInsert_Sq(SqList *L, int i, ElemType e);/ 在 L 中第 i 个位置之前插入 e ，L 长度加 1status ListDelete_Sq(SqList *L, int i, ElemType *e);/ 删除 L 的第 i 个数据元素，并用 e 返回其值，L 长度减 1void visit(ElemType e);/ 打印 e 的值到显示器void ListTraverse(SqList L, void visit(ElemType);/ 依次对 L 的每个元素调用函数 visit(ElemType)int main() int i, j; SqList L; InitList(&L); puts(Please input 6 number to initilize linkedlist:); for (i=1; ielem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof (ElemType);if (!L-elem) exit(OVERFLOW); L-length=0; L-listsize=LIST_INIT_SIZE; return OK;status ListInsert_Sq(SqList *L, int i, ElemType e) if (iL-length+1) return ERROR; if (L-length = L-listsize) ElemType *newbase = (ElemType *)realloc(L-elem, (L-listsize+LISTINCREMENT)*sizeof(ElemType); if (!newbase) exit (OVERFLOW); L-elem = newbase; L-listsize += LISTINCREMENT; ElemType *p, *q = &(L-elemi-1); for (p=&(L-elemL-length-1);p=q; -p) *(p+1)=*p; *q=e; L-length+; return OK;status ListDelete_Sq(SqList *L, int i, ElemType *e) if (iL-length) return ERROR; ElemType *p=&L-elemi-1; *e = *p; ElemType *q = L-elem + L-length - 1; for (+p; plength-; return OK;void visit(ElemType e) printf(%dt, e);void ListTraverse(SqList L, void visit(ElemType) int i; for (i=0; inext=NULL; for (i=n;i0;-i) p=(Linklist) malloc(sizeof(Lnode); scanf(%d,&p-data); p-next= L-next; L-next =p; return OK; /createList_L/*或者用下面的尾插法status CreateList_L(Linklist &L,int n) Linklist r; L=(Linklist) malloc(sizeof(LNode); L-next=NULL; r=L; for ( i=1;idata); r-next=p;r=p; ; r-next=NULL; /createList_L*/status ListInsert_L(Linklist &L, int i, ElemType e) p = L; j =0; while (p & jnext; +j; if (!p | ji-1) return ERROR; s=(Linklist)malloc(sizeof(Lnode); s-data = e; s-next = p-next; p-next = s; return OK; /ListInsert_Lstatus Listdelete_L(Linklist &L, int i, ElemType &e) p = L; j =0; while (p-next & jnext; +j; if (!(p-next) | ji-1) return ERROR; q=p-next; p-next=q-next; e=q-data; free(q); return OK; /Listdelete_L5、将算法细化为程序代码如下：#include #include #define OK 1#define ERROR 0#define OVERFLOW -2typedef int status;typedef int ElemType;typedef struct Lnode ElemType data; struct Lnode *next; Lnode, *Linklist;status CreateList_L(Linklist *L, int n);/ 正序创建链表status ListInsert_L(Linklist *L, int i, ElemType e);/ 在 L 中第 i 个位置之前插入 estatus Listdelete_L(Linklist *L, int i, ElemType *e);/ 删除 L 的第 i 个数据元素，并用 e 返回其值void visit(ElemType e);/ 打印 e 的值到显示器void ListTraverse(Linklist L, void visit(ElemType);/ 依次对 L 的每个元素调用函数 visit(ElemType)int main() int i, j; Linklist L; puts(Please input 6 number to initilize linkedlist:); CreateList_L(&L, 6); puts(The linked list is:); ListTraverse(L, visit); puts(Please input a element to insert:); scanf(%d, &j); puts(Please input the position to insert:); scanf(%d, &i); ListInsert_L(&L, i, j); puts(After insert, the linked list is:); ListTraverse(L, visit); puts(Please input the position to delete:); scanf(%d, &i); Listdelete_L(&L, i, &j); puts(After delete, the linked list is:); ListTraverse(L, visit); printf(The deleted element is:%dn, j); return 0;status CreateList_L(Linklist *L, int n) *L = (Linklist)malloc(sizeof (Lnode); if (!*L) exit(OVERFLOW); int i; Linklist p, r = *L; (*L)-next = NULL; for (i=1; idata); r-next = p; r = p; r-next = NULL; return OK;status ListInsert_L(Linklist *L, int i, ElemType e) int j =0; Linklist s, p = *L; while (p & jnext; +j; if (!p | ji-1) return ERROR; s = (Linklist)malloc(sizeof (Lnode); s-data = e; s-next = p-next; p-next = s; return OK;status Listdelete_L(Linklist *L, int i, ElemType *e) int j =0; Linklist q, p = *L; while (p-next & jnext; +j; if (!(p-next) | ji-1) return ERROR; q = p-next; p-next = q-next; *e = q-data; free(q); return OK;void visit(ElemType e) printf(%dt, e);void ListTraverse(Linklist L, void visit(ElemType) Linklist p = L-next; while (p != NULL) visit(p-data); p = p-next; putchar(n);6、 编译、链接、运行程序。实验数据和实验结果记录1、顺序表程序的一个运行实例如下。2、链表程序的一个运行实例如下。实验结果分析1、此程序的顺序表直接使用插入函数得到初始表，也可自己设计函数输入不同数值以得到顺序表；2、注意一些经常在算法使用的常量可在一个专门的head.h文件中定义；3、程序中的输入输出可使用C知识，也可使用C+中知识；4、分析思考算法改为程序时需要注意的问题；5、分析顺序表和链表的区别。实验二栈和队列基本信息实验课程：数据结构 设课形式：非独立课程学分：4实验项目：栈和队列项目类型：基础项目学时：4实验预习实验目的和要求：1、熟练掌握栈和队列的结构，以及这种数据结构的特点；2、会定义顺序栈、循环队列，能实现栈、队列的基本操作；3、会利用栈解决典型问题，如数制转换等。实验内容和原理或涉及的知识点：用C语言设计实现栈的初始化、入栈、出栈、判空等功能，并利用栈完成数制转换功能；设计实现循环队列的定义、初始化、入队、出队、求队列长度等功能。实验条件：具有C+语言集成开发环境的计算机实验设计方案：栈设计的算法有：1、初始化栈；2、入栈；3、出栈；4、判断栈是否为空；5、十进制转换为八进制。队列设计的算法有：1、初始化；2、入队；3、出队；4、求队列长度。实验过程1、根据实验预习阶段的实验设计方案，编写顺序栈的伪C代码如下。typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;Status InitStack(SqStack &S) S.base = (SElemType *)malloc (STACK_INIT_SIZE*sizeof (SElemType);if (!S.base) exit (OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK; /InitStackStatus Push(SqStack &S, SElemType e) if (S.top-S.base=S.stacksize) /栈满 S.base=(SElemType *)realloc (S.base, (S.stacksize+STACKINCREMENT) * sizeof(SElemType); if (!S.base) exit (OVERFLOW); S.top = S.base + S.stacksize; S.stacksize+=STACKINCREMENT; / if *S.top+ = e; return OK; /PushStatus Pop(SqStack &S, SElemType &e) if(S.top = S.base)return ERROR; e = * - S.top; return OK; /Pop Status StackEmpty(SqStack S) if (S.base=S.top) return TRUE; return FALSE;void conversion () InitStack(S); scanf (%d,&N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion2、将算法细化为程序代码。3、编译、链接、运行程序。4、循环队列的伪C代码如下：#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; / 动态分配存储空间 int front; / 头指针，若队列不空， / 指向队列头元素 int rear; / 尾指针，若队列不空，指向 队列尾元素 的下一个位置 SqQueue;Status InitQueue (SqQueue &Q) / 构造一个空队列Q Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType); if (!Q.base) exit (OVERFLOW); / 存储分配失败 Q.front = Q.rear = 0; return OK; Status EnQueue (SqQueue &Q, ElemType e) / 插入元素e为Q的新的队尾元素 if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR; /队列满 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK;Status DeQueue (SqQueue &Q, ElemType &e) / 若队列不空，则删除Q的队头元素， / 用e返回其值，并返回OK; 否则返回ERROR if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK;int QueueLength(SqQueue Q) return (Q.rear - Q.front+MAXSIZE) % MAXSIZE;5、将算法细化成程序代码：6、编译、链接、运行程序。实验数据和实验结果记录栈程序的一个运行实例如下。队列的一个运行实例如下：实验结果分析1、分析数制转换时后进先出的特点；2、分析如果将数转换为二进制， conversion函数的修改；3、分析如果没有初始化栈的操作时程序的运行结果；3、写出自己的心得体会。实验三二叉树基本信息实验课程：数据结构设课形式：非独立课程学分：4实验项目：二叉树项目类型：综合项目学时：4实验预习实验目的和要求：1、熟练掌握二叉树的结构，以及这种数据结构的特点；2、会定义二叉树的链式存储结构；3、能实现二叉树的建立、遍历等功能，需要完成先序遍历、中序遍历和后序遍历递归算法以及中序非递归算法。实验内容和原理或涉及的知识点：自己编写程序实现二叉树的各种基本操作，如二叉树的建立，遍历等。实验条件：具有C语言集成开发环境的计算机实验设计方案：设计的算法有：1、递归建立二叉树；2、先序递归遍历二叉树；3、中序递归遍历二叉树；4、后序递归遍历二叉树。5、中序非递归遍历二叉树实验过程1、根据实验预习阶段的实验设计方案，编写伪C代码如下。typedef struct BiTNode TelemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;status CreateBiTree(BiTree &T)/按先序次序输入二叉树中结点的值,空格表示空树/生成二叉树的二叉链表存储结构，T为根结点指针 scanf(%c,&ch); if (ch= ) T=NULL; else if (!(T=(BiTNode *) malloc(sizeof(BiTNode) exit(OVERFLOW); T-data=ch; /建立根结点 CreateBiTree( T-lchild); /建立左子树 CreateBiTree(T-rchild); /建立右子树 return OK; /CreateBiTreestatus PrintElement(TelemType e) printf(%c,e); /输出元素值 return OK;status PreorderTraverse(BiTree T, status(*visit)(TelemType e) /先序遍历根结点指针为T的二叉树if (T) if (visit(T-data) if (PreorderTraverse(T-lchild,visit)if (PreorderTraverse(T-rchild,visit) return OK; return ERROR; else return OK; /if (T) /PreorderTraverseStatus InorderTraverse1(BiTree T, Status(*visit)(TElemType e) /先序遍历根结点指针为T的二叉树if (T) if (InorderTraverse1(T-lchild,visit)if (visit(T-data)if (InorderTraverse1(T-rchild,visit) return OK;return ERROR; else return OK; /if (T)/InorderTraversestatus PostorderTraverse(BiTree T, status(*visit)(TelemType e) /后序遍历根结点指针为T的二叉树if (T) if (PostorderTraverse(T-lchild,visit)if (PostorderTraverse(T-rchild,visit) if (visit(T-data) return OK; return ERROR; else return OK; /if (T) /PostorderTraverseStatus InorderTraverse2(BiTree T, Status (*visit)(TElemType e) SqStack S;InitStack(S); BiTree p=T;while( p | !StackEmpty(S) ) / 找到最左下的结点if (p) Push(S,p); p=p-lchild; / 根指针进栈，遍历左子树else /根指针退栈，访问根结点，遍历右子树Pop(S,p); if (!visit(p-data) ) return ERROR;p=p-rchild; /else / whilereturn OK;/ InOrderTraverse2、将算法细化为程序代码。3、编译、链接、运行程序。实验数据和实验结果记录程序的一个运行实例如下。实验结果分析1、分析递归建立二叉树算法输入数据的格式和意义；2、分析先序、中序、后