《数据结构课程设计》word版.doc

仲 恺 农 业 工 程 学 院课 程 设 计 报 告课程名称： 数 据 结 构 院（系）： 专 业： 班 级： 学 号： 姓 名： 指导老师： The general staff (1 employees in addition to vice president, director, manager, deputy manager and special positions outside the contract period) to resign, to give 10 days notice, the project manager or department manager, administrative personnel department or relevant responsible person for the relevant visa after departure procedures; in addition to general staff personnel outside the contract period of turnover must submit the resignation report, a month ahead of schedule, the administrative personnel department, general manager of visa before separation procedures; probation employees shall pay in advance 5 resignation report, the project manager or department manager and administrative personnel department visa before departure; positive after special reasons did not sign a contract with reference to general employees Through the staff35目 录1顺序表12链表63栈和队列124树和二叉树185图246查找和排序29课程设计总结33参 考 文 献331顺序表2题 设线性表存于A1.size的前num各分量中，且递增有序。请设计一个算法，将x插入到线性表的适当位置上，以保持线性表的有序性。一、数据结构说明1、线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。 假设线性表的每个元素需占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系： LOC(ai+1)=LOC(ai)+L 一般来说，线性表的第i个数据元素ai的存储位置为 LOC(ai) = LOC(a1)+(i-1) * L 式中LOC(a1)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。线性表的这种机内表示称做线性表的顺序存储结构或顺序映象(Sequential Mapping)，反之，称这种存储结构的线性表为顺序表。它的特点是，为表中相邻的元素ai和ai+1赋以相邻的存储位置LOC(ai)和LOC(ai+1)。换句话说，以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。 2、顺序表存储结构：用一段地址连续的存储单元依次存储线性表中的数据元素 空闲图1 顺序表存续结构示意图二、顺序表的存储结构设计typedef struct ElemType *data;/存储空间基址int length;/当前长度int size;/当前分配的存储容量(以sizeof(ElemType)为单位SqList;三、算法设计（程序流程图）开始有序顺序表L1元素e2输入数据赋给e2把e2插入有序顺序表L1的适当位置输出有序顺序表L1结束图2 顺序表课程设计流程图四、详细设计#include #include #include /* exit() */#include #define LIST_INIT_SIZE 100/*线性表存储空间的初始分配量*/#define LISTINCREMENT 2/*线性表存储空间的分配增量*/typedef int ElemType;typedef struct ElemType *data;/存储空间基址int length;/当前长度int size;/当前分配的存储容量(以sizeof(ElemType)为单位SqList;/*函数结果状态代码*/#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/*因为在math.h中已定义OVERFLOW的值为3,故去掉此行*/typedef int Status;/*Status是函数的类型,其值是函数结果状态代码，如OK等*/typedef int Boolean;/*Boolean是布尔类型,其值是TRUE或FALSE*/Status InitList(SqList &L) /*操作结果：构造一个空的顺序线性表*/L.data=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(! L.data) exit(OVERFLOW);/*存储分配失败*/L.length=0;/*空表长度为0*/L.size=LIST_INIT_SIZE;/*初始存储容量*/return OK;Status InsertOrderList(SqList &L,ElemType x) /顺序表L中的元素依值递增有序，本算法将x插入其中适当位置/以保持其有序性。入口断言：0=L.length=0&x=i+1;j-)L.dataj+1=L.dataj;L.datai+1=x;L.length+;return OK;Status ListTraverse(SqList L) /*初始条件：顺序线性表L已存在*/*操作结果：依次对L的每个数据元素访问并输出*/ElemType *p;int i;p=L.data;for(i=1;i=L.length;i+)printf(%d , *p+);printf(n);return OK;void main()SqList L1;ElemType e1,e2;int i,n;printf(顺序表 第2题n);InitList(L1);/初始化顺序表printf(给顺序表长度赋值 n=);scanf(%d,&n);/通过键盘输入为顺序表长度赋值printf(输入元素:n);for(i=1;i=n;i+)scanf(%d,&e1);/通过键盘输入为e赋值InsertOrderList(L1,e1);/调用InsertOrderList函数，在L中递增插入新的数据元素e1 printf(有序递增顺序表为:); ListTraverse(L1);/依次对L的每个数据元素访问并输出printf(输入一个元素并把它插入表中n);scanf(%d,&e2);InsertOrderList(L1,e2);/调用InsertOrderList函数，在有序递增顺序表L中有序插入新的数据元素e2printf(新有序递增顺序表为:);ListTraverse(L1);/依次对L的每个数据元素访问并输出五、调试分析1、调试结果图3 顺序表课程设计调试结果2、时间复杂度Status InsertOrderList(SqList &L,ElemType x)函数的时间复杂度为O(n)。3、程序存在问题和解决办法在调试程序的时候发现自己编程序的时候考虑不周，忽略了顺序表的最大容量的问题，程序运行的结果跟预想的结果不吻合。解决办法是在编写程序的时候要把顺序表的最大容量这个问题考虑进去。2链表5题 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。一、数据结构说明1、线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。因此，为了表示每个数据元素 ai 与其直接后继数据元素ai+1 ，之间的逻辑关系，对数据元素ai 来说，除了存储其本身的信息之外，还需存储个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素ai 的存储映象，称为结点(Node)。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称做指针或链。 n个结点( ai（1in)的存储映象)链结成一个链表，即为线性表 (a1 ， a2 ， ， an )的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。2、链表存储结构：用一组任意的存储单元存放线性表的元素data next P 结点 （*p）图4 链表存储结构示意图二、链表的存储结构设计struct LNode;typedef struct LNode *PtrToNode;typedef PtrToNode List;typedef PtrToNode Position;typedef struct LNode ElemType data;/ 数据域 struct LNode *next;/ 指针域 *LinkList; LinkList L;/L为单链表的头指针三、算法设计（程序流程图）开始链表L1对链表L1作有序递减排序删除最小值，并把它赋给MIN输出链表L1结束图5 链表课程设计流程图四、详细设计#include /*EOF(=Z或F6),NULL*/#include /*exit()*/#include typedef int ElemType;/*函数结果状态代码*/#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */typedef int Status; /*Status是函数的类型,其值是函数结果状态代码，如OK等*/typedef int Boolean;/*Boolean是布尔类型,其值是TRUE或FALSE*/struct LNode;typedef struct LNode *PtrToNode;typedef PtrToNode List;typedef PtrToNode Position;typedef struct LNode ElemType data;/ 数据域 struct LNode *next;/ 指针域 *LinkList; LinkList L;/L为单链表的头指针void Insert(ElemType X,Position P)Position TmpCell;/*1*/TmpCell=(Position)malloc( sizeof( struct LNode ) );/*2*/if(TmpCell=NULL)/*3*/printf(Out of space!);/*4*/TmpCell-data=X;/*5*/TmpCell-next=P-next;/*6*/P-next=TmpCell;int IsLast(Position P,List L)return P-next=NULL;Position FindPrevious(ElemType X,List L)Position P;/*1*/P=L;/*2*/while(P-next!=NULL&P-next-data!=X)/*3*/P=P-next;/*4*/return P;void Delete(ElemType X,List L)Position P,TmpCell;P=FindPrevious(X,L);if(!IsLast(P,L)/*Assumption of header use*/TmpCell=P-next;/*X is found; delete it*/TmpCell-data=X;/给指针TmpCell赋值P-next=P-next-next;/更改P-Next的值free(TmpCell);/释放TmpCell所指向的结点Status ListTraverse(List L)/*初始条件：线性表L已存在*/List P=L-next;while(P)printf(%d ,P-data);/*输出元素*/P=P-next;/*指针指向下一个元素*/printf(n);return OK;void main(void)List L1;Position P1;int Min;int j,x,n;printf(链表 第5题n);L1=(List)malloc(sizeof(struct LNode);/*产生头结点,并使L指向此头结点*/if(!L1)/*存储分配失败*/exit(0);L1-next=NULL;/*头结点的指针域的值为NULL*/printf(给链表长度赋值 n=);scanf(%d,&n);/通过键盘为n赋值printf(输入元素：n);for(j=1;jnext;Min=P1-data;P1=P1-next;for(;P1!=NULL;P1=P1-next)if(P1-datadata;printf(删除最小值为Min=%d n,Min);Delete(Min,L1);/删除链表中的最小值printf(删除最小值后，新的链表为:);ListTraverse(L1);五、调试分析1、调试结果图6 链表课程设计调试结果2、时间复杂度P1=L1-next;Min=P1-data;P1=P1-next;for(;P1!=NULL;P1=P1-next)if(P1-datadata;本段程序的时间复杂度为O(n)，而void Delete(ElemType X,List L)函数的时间复杂度为O(1)，所以在链表中删除最小值的时间复杂度为O(n)。3、程序存在问题和解决办法调用指针的时候出现数据混乱，解决办法是调用指针的时候要注意指针所指向的数据，避免发生数据混乱。3栈和队列11题 如果允许在循环队列的两端都可以进行插入和删除操作。要求：（1） 写出循环队列的类型定义；（2）写出“从队尾删除”和“从队头插入”的算法。一、数据结构说明1、栈(Stack) 是限定仅在表尾进行插入或删除操作的线性表。因此， 对栈来说，表尾端有其特殊含义，称为栈顶(top)，相应地，表头端称为栈底(bottom)。不含元素的空表称为空栈。队列(Queue)是一种先进先出(First in First Out，缩写为FIFO)的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。2、栈存储结构：出栈进栈栈顶栈底 . . .图7 栈的示意图3、队列存储结构：图8 队列的示意图二、队列的存储结构设计struct QueueRecordint Capacity;/队列最大容量int Front;/队头int Rear;/队尾int Size;/队列大小ElementType *Array;/数组;三、算法设计（程序流程图）开始初始化队列Q输入一串元素从队头插入元素从队尾删除元素结束图9 栈和队列课程设计流程图四、详细设计#include /* malloc()等 */#include /* EOF(=Z或F6),NULL */#include /* atoi() */#include /* exit() */struct QueueRecord;typedef struct QueueRecord *Queue;#define MinQueueSize 5typedef char ElementType;struct QueueRecordint Capacity;/队列最大容量int Front;/队头int Rear;/队尾int Size;/队列大小ElementType *Array;/数组;void MakeEmpty(Queue Q)Q-Size=0;Q-Front=1;Q-Rear=0;int IsEmpty(Queue Q)return Q-Size=0;int IsFull(Queue Q)return Q-Size=Q-Capacity;static int Succ(int Value, Queue Q)if(-Value =-1)Value=Q-Capacity-1;return Value;Queue CreateQueue(int MaxElements)Queue Q;/* 1 */if(MaxElementsArray=(ElementType *)malloc(sizeof(ElementType)*MaxElements);/* 7 */if(Q-Array=NULL)/* 8 */printf(Out of spaace!); exit(0);/* 9 */Q-Capacity=MaxElements;/* 10 */MakeEmpty(Q);/* 11 */return Q;void Enqueue(ElementType X, Queue Q)if(IsFull ( Q )printf(Full queue);else Q-Size+;/队列大小加1 Q-Front=Succ(Q-Front,Q); Q-ArrayQ-Front=X;/将元素X插入队列中ElementType Dequeue(Queue Q)ElementType c2;if(IsEmpty(Q)printf(Empty);exit(0);Q-Size-;/队列大小减1 Q-Front=Succ(Q-Front,Q);c2=Q-ArrayQ-Front;return c2;void main(void)char c1,c2;Queue Q;int i,MAX;printf(栈和队列 第11题n);printf(输入数据赋给MAX(MAX=5) n); scanf(%d,&MAX);getchar( ); Q=CreateQueue(MAX );/建立一个大小MAX的队列printf(依次输入元素a b c d e n); for(i=1;i=5;i+)scanf(%c,&c1);getchar( ); Enqueue(c1, Q);/将元素c1插入队列中/*以下程序语句（可以有一条或多条）的功能输出出队序列*/printf(输出出队序列为：);for(i=1;i=5;i+)c2=Dequeue(Q);printf(%c ,c2);printf(n);五、调试分析1、调试结果图10 栈和队列课程设计调试结果2、时间复杂度入队函数的时间复杂度为O(n)。出队函数的时间复杂度为O(n)。3、程序存在问题和解决办法程序刚开始运行的时候输出的结果跟自己预想的预想的结果不吻合，原因是输入数据的时候按Enter键，Enter键被当做元素了，解决办法是添加getchar（）语句，运行结果正确。4树和二叉树13题 二叉树排序方法如下：（1）将第一个数据放在树根。 （2）将随后读入的数据与树根中的数据相比较，若比树根大，则置于右子树，反之则置于左子树，建成一棵二叉树；（3）利用中序遍历打印排序结果。一、数据结构说明1、在现实的生活中，描述一个单位的组织结构以及一个家族的族谱都可用树形结构来形象地表示出，在计算机的领域中，数据库系统中信息的组织形式也可用它来描述，因此它是一种应用非常广泛的非线性结构，其中以二叉树最为常用。本次实验以二叉树的操作为主。2、二叉树是另一种树形结构。它的特点是每个结点最多有两棵子树（二叉树中不存在度大于2的结点），而且二叉树的子树有左右之分，其次序不能颠倒。树的一般形态如下：ABCDEFGIH图11 树3、树存储结构：双亲表示法，孩子链表表示法，孩子兄弟法。本次算法树主要采用孩子链表表示法进行存储，如下： 序号 data firstchild1021A543B26C43 D87E5F76G8HI图12 树的孩子链表表示法示意图二、二叉排序树的存储结构设计typedef struct SearchTNode TElemType Element;/数据域 struct SearchTNode *lchild,*rchild; /* 左右孩子指针 */SearchTNode,*SearchTree;三、算法设计（程序流程图）开始初始化二叉树Ti=1，n= T=NULL？输入元素Xroot=X输入元素YX（Y）root?lchild=X(Y)rchild=X(Y)i+in?中序遍历输出二叉树T结束图13 二叉树课程设计流程图四、详细设计#include /* EOF(=Z或F6),NULL */#include /* exit() */#include#include typedef int ElementType;/* 函数结果状态代码 */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */typedef int TElemType; /* 二叉树的二叉链表存储表示 */typedef struct SearchTNode TElemType Element;/数据域 struct SearchTNode *lchild,*rchild; /* 左右孩子指针 */SearchTNode,*SearchTree;/* 二叉树的二叉链表存储的基本操作 */Status InitBiTree(SearchTree *T) /* 操作结果: 构造空二叉树T */ *T=NULL; return OK; void CreatSearchTree(SearchTree *T ,TElemType X) if (*T=NULL)/*如果是空树*/ *T=(SearchTree)malloc(sizeof(struct SearchTNode); if (*T=NULL) exit(OVERFLOW); else (*T)-Element=X; (*T)-lchild=(*T)-rchild=NULL; /* 最后建立一个结点的树 */ else /* 如果是树 */ if (XElement) CreatSearchTree(&(*T)-lchild),X); else if (X(*T)-Element) CreatSearchTree(&(*T)-rchild),X); void InOrderTraverse(SearchTree T) /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */ /* 操作结果: 中序递归遍历T,对每个结点调用函数Visit一次且仅一次 */ if(T) InOrderTraverse(T-lchild); /* 先中序遍历左子树 */ printf(%d ,T-Element);/* 再访问根结点 */ InOrderTraverse(T-rchild); /* 最后中序遍历右子树 */ void main() SearchTree T; TElemType X; int i,n; printf(树和二叉树 第13题n); InitBiTree(&T);/构造空树 printf(输入结点的个数n= ); scanf(%d,&n); printf(请输入结点：n); for(i=1;i=n;i+) scanf(%d,&X);/通过键盘给X赋值 CreatSearchTree(&T,X);/建立二叉排序树 printf(中序递归遍历二叉排序树:); InOrderTraverse(T);/调用中序遍历函数 printf(n);五、调试分析1、调试结果图15 二叉树课程设计调试结果2、时间复杂度void CreatSearchTree(SearchTree *T ,TElemType X)函数的时间复杂度为O(n)。3、程序存在问题和解决办法程序刚开始运行的结果和自己预想的结果十分的不吻合，经检查发现void CreatSearchTree(SearchTree *T ,TElemType X)函数中出现的问题，经过把此函数修改调整后，运行结果正确。5图14题 编写函数实现用Prim算法构造最小生成树的算法。一、数据结构说明1、图（GRAPH）是一种复杂的数据结构，结点之间的关系可以是任意的，由此图的应用极为广泛，已经渗透到如物理、化学、电讯工程、计算机科学等领域。2、图存储结构：邻接矩阵表示法和邻接表表示法，本次实验图主要以邻接表进行存储。 用邻接矩阵表示法表示图如下图所示：V3V03 0 1 0 1 A = 1 0 1 1 V1V2 0 1 0 0 1 0 0 1 图16 一个无向图的邻接矩阵表示无向图对应的邻接表表示如下图所示： 序号 vertex firstedge0V0 1 3 V11 0 2 3 112V2 V3 3 0 1 图17 一个无向图的的邻接表表示二、图（prim算法辅助数组）的存储结构设计struct int adjvex; int lowcost; closedgeMAX_VERTEX_NUM;三、算法设计（程序流程图）开始辅助数据数组初始化一个节点初始化i=1选择第i个顶点的最小相连边；将另个顶点并入将另个顶点并入；i+ig.arcnum？j=0jg.arcnum？输出最小树结束j+新顶点并入后重新选择最小边图18 图课程设计流程图四、详细设计#include #define MAX_VERTEX_NUM 100 #define INFINITY 99999 int mapMAX_VERTEX_NUMMAX_VERTEX_NUM; int n,e; struct int adjvex; int lowcost; closedgeMAX_VERTEX_NUM; /构造连通图void LoadMap() int i,j,v,u,c; for( i=1;i=n;i+) for( j=1;j=n;j+) mapij=INFINITY; for( i=1;i=e;i+) scanf(%d%d%d,&u,&v,&c); mapuv=c; mapvu=c; /输出生成树的每条边void MiniSpanTree_PRIM() int i,j,k,min,u; u=1;for( j=1; j=n; +j) if( j!=u ) closedgej.adjvex = u; closedgej.lowcost = mapuj; closedgeu.lowcost = 0; for( i=1;in;+i) min = INFINITY; for ( j=1;j0 & closedgej.lowcostmin ) k = j; min = closedgej.lowcost; printf(%d-%dn,closedgek.adjvex,k); closedgek.lowcost = 0; for( j=1; j=n; j+) if( mapkj closedgej.lowcost ) closedgej.adjvex = k; closedgej.lowcost = mapkj; void main() printf(图 第14题n); printf(请输入连通图的顶点数目: );scanf(%d,&n);printf(请输入连通图的边的数目: );scanf(%d,&e);printf(请依次输入每条边的两个顶点名和权值(顶点_顶点_权值)(如：1 2 5):n);LoadMap(); printf(最小生成树所包括的边如