数据结构实验报告.doc

实验一 线性表及其应用请写出实验内容的操作步骤：1.建立含n个数据元素的顺序表,并输出该表中各元素的值及顺序表的长度。2.建立一个顺序表L=21，23，14，5，56，17，31，然后在第i个位置插入元素68。#include#define size 100typedef int datatype;typedef struct datatype datasize;int length;list;void listinit(list &l)l.length=0;void create(list &l)int n,i;printf(请输入个数N.n);scanf(%d,&n);printf(请逐一输入这%d个数字。n,n);for(i=1;i=n;i+) scanf(%3d,&l.datai);l.length+;void print(list &l)int i;if(l.length=0)printf(该线性表为空。n);else printf(该线性表为：);for(i=1;i=l.length;i+)printf(%3d,l.datai);printf( length=%d,l.length);printf(n);void listinsert(list &l,int i,datatype e)int j;if(il.length+1)printf(Error.n);else for(j=l.length+1;ji;j-)l.dataj=l.dataj-1; l.datai=e; l.length+; void listdelete(list &l,int i,datatype e)int j;if(il.length)printf(Error.n);else e=l.datai;if(i!=l.length)for(j=i;jl.length;j+)l.dataj=l.dataj+1; l.length-;void main()int i,j;int a7=21,23,14,5,56,17,31;list l;printf(建立顺序线性表L.n);listinit(l);printf(初始化成功.n);print(l);create(l);print(l);printf(n);list la;listinit(la);printf(建立一个线性表La=21，23，14，5，56，17，31.n);for(j=0;j7;j+)la.dataj+1=aj;la.length+;printf(请输入i值。 -在第i个位置插入68.n);scanf(%d,&i);listinsert(la,i,68);print(la);3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。#include#include#includetypedef int datatype;struct nodedatatype data;node * next;node * INPUTNode(node *head)node *r,*p;int i,j,len;r=head; printf(输入数据的个数N:n); scanf(%d,&len);printf(逐一输入%d个数:n,len); for(i=0;idata=j; p-next=NULL; r-next=p; r=p; return (head);void PrintList(node *head)node *p;p=head;while(p!=NULL)printf(%d ,p-data);p=p-next;printf(n);int main()node *head;int i;head=(node *)malloc(sizeof(node);head-next=NULL;head-data=NULL;INPUTNode(head);printf(建立链表: ); PrintList(head); scanf(%d,&i);return 0;实验二 栈和队列请写出实验内容的操作步骤：一、 初始化顺序栈；插入元素；删除栈顶元素；取栈顶元素；遍历顺序栈；置空顺序栈。#include#define size 100typedef int ElemType;typedef struct ElemType stacksize; int top;SqStack; void initstack(SqStack *p)p-top=-1;printf(已初始化顺序栈.n);void Push(SqStack *p,ElemType x) if(p-toptop=p-top+1; p-stackp-top=x; printf(已插入新栈顶元素: %d.n,x);void Pop(SqStack *p)ElemType x;if(p-topstackp-top;p-top=p-top-1;printf(已删除栈顶元素: %d.n,x); void GetTop(SqStack *p) ElemType x;if(p-topstackp-top;printf(栈顶元素为: %d.n,x);void OutStack(SqStack *p) int i;if(p-toptop;i=0;i-)printf( %d,p-stacki);printf(n);void setEmpty(SqStack *p)p-top=-1;printf(已将顺序栈置空.n);void main()int i,n;ElemType e;SqStack p;initstack(&p);printf(请输入要存储的数据个数N：);scanf(%d,&n);for(i=1;i=n;i+)scanf(%d,&e);Push(&p,e);OutStack(&p);printf(n);Pop (&p);GetTop(&p); OutStack(&p);printf(n);setEmpty(&p);二、初始化并建立链队列；入链队列；出链队列；遍历链队列。#include#includetypedef int datatype;typedef struct qnode datatype data;struct qnode *next;qnode,*que;typedef struct que front;que rear;linkque;void initque(linkque &Q)Q.front=Q.rear=(que)malloc(sizeof(qnode);if(!Q.front)printf(Overflow.n);else Q.front-next=NULL;printf(已创建空队列.n);void enque(linkque &Q,datatype e)qnode *p;p=(que)malloc(sizeof(qnode);if(!p)printf(Overflow.n);else p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;printf(已在队尾插入: %d.n,e);void deque(linkque &Q)qnode *p;datatype e;p=(que)malloc(sizeof(qnode);if(Q.front=Q.rear)printf(该队列为空.);else p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;printf(已删除队头元素: %d.n,e);void display(linkque &Q)qnode *p;p=Q.front-next;printf(遍历链队列: );while(p!=NULL) printf(%d-,p-data); p=p-next; printf(NULL.n);void main()int i,n;datatype e;linkque Q;initque(Q);printf(请输入要存储的数据个数N：);scanf(%d,&n);for(i=1;i=n;i+)scanf(%d,&e);enque(Q,e);display(Q);printf(n);deque(Q);display(Q);实验三 链队列一、初始化并建立链队列；入链队列；出链队列；遍历链队列。#include#includetypedef int datatype;typedef struct qnode datatype data;struct qnode *next;qnode,*que;typedef struct que front;que rear;linkque;void initque(linkque &Q)Q.front=Q.rear=(que)malloc(sizeof(qnode);if(!Q.front)printf(Overflow.n);else Q.front-next=NULL;printf(已创建空队列.n);void enque(linkque &Q,datatype e)qnode *p;p=(que)malloc(sizeof(qnode);if(!p)printf(Overflow.n);else p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;printf(已在队尾插入: %d.n,e);void deque(linkque &Q)qnode *p;datatype e;p=(que)malloc(sizeof(qnode);if(Q.front=Q.rear)printf(该队列为空.);else p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;printf(已删除队头元素: %d.n,e);void display(linkque &Q)qnode *p;p=Q.front-next;printf(遍历链队列: );while(p!=NULL) printf(%d-,p-data); p=p-next; printf(NULL.n);void main()int i,n;datatype e;linkque Q;initque(Q);printf(请输入要存储的数据个数N：);scanf(%d,&n);for(i=1;i=n;i+)scanf(%d,&e);enque(Q,e);display(Q);printf(n);deque(Q);display(Q);实验四 树和二叉树1. 建立自己的头文件BT.H，内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法。#include#includetypedef struct BiTNode char data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;void CreateBiTree(BiTree &t) char c; c=getchar();if(c=#) t=NULL;else t=(BiTNode *)malloc(sizeof(BiTNode);t-data=c; CreateBiTree(t-lchild); CreateBiTree (t-rchild); void finorder(BiTree root) if (root!=NULL) finorder(root-lchild); finorder(root-rchild);printf(%c,root-data); void minorder(BiTree root) if (root!=NULL) minorder(root-lchild);printf(%c,root-data); minorder(root-rchild); void binorder(BiTree root) if (root!=NULL) binorder(root-lchild); binorder(root-rchild);printf(%c,root-data); 2. 建立二叉树,并通过调用函数, 输出先序遍历、中序遍历与后序遍历的结果。#include#includevoid main() char c; BiTree t;printf(请建立二叉树：n); CreateBiTree(t);printf(n先序遍历该二叉树：); finorder(t);printf(n中序遍历该二叉树：); minorder(t);printf(n后序遍历该二叉树：);binorder(t);printf(n);实验五 图的遍历#include#include#define MAXVEX 30 struct edgenode int adjvex ; /*邻接点域*/ struct edgenode *next ; /*链域*/ ; struct vexnode char data; /*顶点信息*/ struct edgenode *link; ;typedef struct vexnode adjlistMAXVEX; void creategraph (adjlist g,int n,int e) int i,s,d; struct edgenode *p; for(i=1;i=n;i+) printf(n请输入第%d个顶点信息：,i); scanf(%d,&gi.data); gi.link=NULL; for(i=1;iadjvex=d; /*邻接点序号为d*/ p-next=gs.link; gs.link=p; /*将新结点插入顶点Vs边表的头部*/ p=(struct edgenode *)malloc(sizeof(edgenode); p-adjvex=s; /*邻接点序号为s*/ p-next=gd.link; gd.link=p; /*将新结点插入顶点Vd边表的头部*/ int vi