数据结构课程上机参考代码

SqList

#include <iostream>using namespace std;#include <malloc.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef  int Status; /* int是函数的类型,其值是函数结果状态代码，如OK等 */#define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量 */#define LISTINCREMENT 2 /* 线性表存储空间的分配增量 */typedef int ElemType;typedef struct{ElemType *elem;int length;int listsize;}SqList;Status InitList(SqList  &L) /* 算法2.3 */{L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;}Status ListInsert(SqList &L, int i ,ElemType e) /* 算法2.4 */{ int *newbase,*q,*p;if(i<1||i>L.length+1) /* i值不合法 */return ERROR; if(L.length>=L.listsize) /* 当前存储空间已满,增加分配 */{newbase=(int *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW); /* 存储分配失败 */L.elem=newbase; /* 新基址 */L.listsize+=LISTINCREMENT; /* 增加存储容量 */}q=L.elem+i-1; /* q为插入位置 */for(p=L.elem+L.length-1;p>=q;--p) /* 插入位置及之后的元素右移 */*(p+1)=*p;*q=e; /* 插入e */++L.length; /* 表长增1 */return OK;}Status ListDelete(SqList &L,int i,ElemType &e) /* 算法2.5 */{int *p,*q;if(i<1||i>L.length) /* i值不合法 */return ERROR;p=L.elem+i-1; /* p为被删除元素的位置 */e=*p; /* 被删除元素的值赋给e */q=L.elem+L.length-1; /* 表尾元素的位置 */for(++p;p<=q;++p) /* 被删除元素之后的元素左移 */*(p-1)=*p;L.length--; /* 表长减1 */return OK;}int LocateElem(SqList L, ElemType e)        /* 算法2.6*/{int *p;int i=1;p=L.elem; /* p的初值为第1个元素的存储位置 */while(i<=L.length&&(*p++!=e))++i;if(i<=L.length)return i;elsereturn 0;}void print(SqList L){int i;for(i=0;i<L.length;i++)printf("%d ", L.elem[i]);printf("\n");} int main(){SqList L;ElemType e;int i,n,t;InitList(L);cout<<"您要在表中插入几个元素：";cin>>n;for(i=1;i<=n;i++){cin>>e;ListInsert(L,i,e);}cout<<"目前表中元素为：";print(L);cout<<"请输入您要查询的值：";cin>>e;i=LocateElem(L,e);if(i==0)cout<<"查找失败"<<endl;else cout<<e<<"在表中的位置为:"<<i<<endl;cout<<"请输入您要删除元素的位置：";cin>>i;t=ListDelete(L,i,e); /* 删除第j个数据 */if(t==ERROR)cout<<"删除第"<<i<<"个数据失败"<<endl;elsecout<<"删除第"<<i<<"个的元素值为"<<e<<endl;cout<<"目前表中元素为：";print(L);system("PAUSE");return 1;}

LinkList

#include <iostream>using namespace std;#include <malloc.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef  int Status;typedef int ElemType;typedef  struct  LNode {ElemType  data ;struct  LNode *next ;
} LNode, *LinkList ;
Status GetElem_L ( LinkList L, int i, ElemType &e )
{LinkList p;int j;p=L->next;j=1;while(p && j<i){p=p->next;j++;}if ( !p || j>i )return ERROR;
}
Status ListInsert_L ( LinkList &L, int i , ElemType e ) {// 在带头结点的单链表L中第i个数据元素之前插入数据元素eLinkList p,s;int j=0;p=L;while(p && j<i-1){p=p->next;j++;}if ( !p || j>i-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 ) {// 在带头结点的单链表L中，删除第i个元素，并由e返回其值LinkList p=L,q;int j=0;while(p && j<i-1){p=p->next;j++;}if ( !p || j>i-1 )return ERROR;q=p->next;p->next=q->next;e=q->data;free(q);return OK;
}void  CreateList_L (LinkList &L, int n) {//逆位序输入n个元素的值，建立带头结点的单链表L。LinkList p;L=(LinkList) malloc(sizeof(LNode)) ;L->next=NULL;for( int i=n; i>0; --i){p= (LinkList) malloc(sizeof(LNode)) ;cin>>p->data;p->next=L->next;L->next=p;}
}void print(LinkList L)
{LinkList p;p=L->next;while(p){cout<<p->data;p=p->next;}
}
int main(){LinkList L;ElemType e;int i,n,t;cout<<"您要在表中插入几个元素：";cin>>n;CreateList_L(L,n);cout<<"目前表中元素为：";print(L);cout<<"请输入您要查询元素的位置：";cin>>i;GetElem_L(L,i,e);cout<<"元素值为:"<<e<<endl;cout<<"请输入您要删除元素的位置：";cin>>i;t=ListDelete_L(L,i,e);if(t==ERROR)cout<<"删除第"<<i<<"个数据失败"<<endl;elsecout<<"删除第"<<i<<"个的元素值为"<<e<<endl;cout<<"目前表中元素为：";print(L);system("PAUSE");return 1;}

Stack

#include <iostream>using namespace std;#include <stdio.h>#include <malloc.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef  int Status;#define  STACK_INIT_SIZE   100#define  STACKINCREMENT  10typedef int SElemType;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;}Status 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 ;}*s.top++=e ;return OK;
}Status Pop (SqStack &s, SElemType &e){if (s.top==s.base) return ERROR ;e=*--s.top ;return OK ;}Status StackEmpty(SqStack s ){if (s.top==s.base)  return  1;else  return  0;}void conversion(int N,int d){SqStack  s;int  x;InitStack(s);while( N )  {Push (s,N % d );N=N / d ;}cout<<"转换后的数值为：";while(!StackEmpty (s)){Pop (s,x ) ;if(d==16){if(x>=10)printf("%c",x-10+'A');elsecout<<x;}else cout<<x ;}
}int main(){int n,d;cout<<"您要把哪个整数转化为几进制：";cin>>n>>d;conversion(n,d);system("PAUSE");return 1;}

Queue

#include <iostream>using namespace std;#include <malloc.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef  int Status;typedef int QElemType;typedef  struct  QNode {QElemType  data ;struct  QNode *next ;
} QNode, *Queueptr ;
typedef struct  {Queueptr   front;Queueptr   rear ;} Lqueue ;Status InitQueue(Lqueue &Q ){Q.front=Q.rear=(Queueptr)malloc(sizeof(QNode));if (!Q.front) exit (OVERFLOW) ;Q.front->next=NULL ;return OK;}Status Enqueue(Lqueue &Q,QElemType e ){Queueptr p;p=(Queueptr)malloc(sizeof(QNode));if (!p) exit (OVERFLOW) ;p->data=e ; p->next=NULL ;Q.rear->next=p; Q.rear=p;return OK;}Status Dequeue(Lqueue &Q,QElemType &e ){Queueptr p;if (Q.front==Q.rear) return ERROR;p=Q .front->next ;   e=p->data;Q.front->next=p->next;if (Q.rear==p)  Q.rear=Q.front;free(p);return OK;}int Locate (Lqueue Q, QElemType e )
{Queueptr p;int i;p=Q.front->next;i=1;while(p && p->data!=e){p=p->next;i++;}if ( p )return i;elsereturn 0;
}void print(Lqueue Q)
{Queueptr p;p=Q.front->next;while(p){cout<<p->data<<"  ";p=p->next;}cout<<endl;
}
int main(){Lqueue Q;QElemType e;int i,n,t;InitQueue(Q);cout<<"您要在队列中插入几个元素：";cin>>n;for(i=1;i<=n;i++){cin>>e;Enqueue(Q,e);}cout<<"目前队列中元素为：";print(Q);cout<<"请输入您要查询的元素";cin>>e;t=Locate(Q,e);if(t==0)cout<<e<<"不在队列中"<<endl;elsecout<<e<<"是队列中的第"<<t<<"个元素"<<endl;Dequeue(Q,e);cout<<e<<"出队"<<endl;cout<<"目前队列中元素为：";print(Q);system("PAUSE");return 1;}

Tree

#include <iostream>using namespace std;#include <malloc.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef  int Status; typedef char TElemType;typedef struct BiTNode {TElemType  data;struct BiTNode   *lchild, *rchild; 
} BiTNode,  *BiTree;void Preorder(BiTree T){ // 先序遍历二叉树 if (T) {cout<<T->data; // 访问结点Preorder(T->lchild); // 遍历左子树Preorder(T->rchild); // 遍历右子树}}
void Inorder(BiTree T){ // 中序遍历二叉树 if (T) {Inorder(T->lchild); // 遍历左子树cout<<T->data; // 访问结点Inorder(T->rchild); // 遍历右子树}}
void CountLeaf (BiTree T, int   &count){  if ( T ) {if ((!T->lchild)&& (!T->rchild))     count++;CountLeaf( T->lchild, count); // 统计左子树中叶子结点个数CountLeaf( T->rchild, count); // 统计右子树中叶子结点个数}}int Depth (BiTree T ){  int depthval,depthLeft,depthRight;if ( !T )       depthval = 0;else{ depthLeft = Depth( T->lchild );depthRight= Depth( T->rchild );depthval = 1 +(depthLeft>depthRight?depthLeft:depthRight);}return depthval;}void CreateBiTree(BiTree &T) {// 按先序次序输入二叉树中结点的值（一个字符），//空格字符表示空树，构造二叉链表表示的二叉树T。char ch;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); // 构造右子树}} // CreateBiTree int main()
{BiTree T;int leafnum=0,depth;cout<<"Please input the preorder of the tree:";CreateBiTree(T);cout<<"The preorder of the tree is:";Preorder(T);cout<<endl;cout<<"The inorder of the tree is:";Inorder(T);cout<<endl;depth= Depth(T);cout<<"The depth of the tree is:"<<depth<<endl;CountLeaf(T,leafnum);cout<<"The leaf num of the tree is:"<<leafnum<<endl; system("PAUSE");return 1;
}

邻接矩阵Graph

#include<iostream>
using namespace std;#define MAXSIZE 9 // 存储空间初始分配量
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0typedef int Status;
typedef char VertexType;typedef struct
{VertexType vexs[MAXSIZE];int  arcs[MAXSIZE][MAXSIZE];int vexnum,arcnum;
}Graph;int LocateVex(Graph G,char v)
{for(int i=0;i<G.vexnum;i++)if(G.vexs[i]==v)return i;return -1;
}
// 建立图的邻接矩阵
void  CreateUDG(Graph &G)
{int i,j,k;printf("输入顶点数和边数:\n");cin>>G.vexnum>>G.arcnum;for(i = 0;i < G.vexnum;i++)cin>>G.vexs[i];for(i = 0; i < G.vexnum;i++)for(j = 0; i < G.vexnum;i++)G.arcs[i][j]=0;for(k = 0;k < G.arcnum;k++){char v1,v2;cout<<"输入边上的两个顶点:\n";cin>>v1>>v2;i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=G.arcs[j][i]=1;}
}int FirstAdjVex(Graph G, int v)
{int j;for(j=0;j<G.vexnum;j++)if(G.arcs[v][j]==1)return j;return -1;
}int NextAdjVex(Graph G, int v, int w)
{int j;for(j=w+1;j<G.vexnum;j++)if(G.arcs[v][j]==1)return j;return -1;
}int  visited[MAXSIZE];// 邻接矩阵的深度优先递归算法
void DFS(Graph G, int v)
{visited[v] = TRUE;cout<<G.vexs[v];for(int w = FirstAdjVex(G, v); w>=0; w = NextAdjVex(G, v, w))if ( !visited[w] )	DFS(G, w);
}//邻接矩阵的深度遍历操作
void DFSTraverse(Graph G)
{int i;for(i = 0; i < G.vexnum; i++)visited[i] = 0;for(i = 0; i < G.vexnum; i++)if(!visited[i])DFS(G, i);
}int main()
{Graph G;CreateUDG(G);cout<<"深度遍历:";DFSTraverse(G);system("PAUSE");return 0;
}