当前位置：文档之家 › 数据结构编程

数据结构编程

  • 格式：doc
  • 大小：176.00 KB
  • 文档页数：35

数据结构1.八皇后问题#include<stdio.h>#define NUM 8int a[NUM+1];void main(){int i,k,flag,not_finish=1,count=0;i=1;a[1]=1;printf("The possible configuration of 8 queens are:\n");while(not_finish){while(not_finish&&i<=NUM){for(flag=1,k=1;flag&&k<i;k++)if(a[k]==a[i])flag=0;for(k=1;flag&&k<i;k++)if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i))) flag=0;if(!flag){if(a[i]==a[i-1]){i--;if(i>1&&a[i]==NUM)a[i]=1;else if(i==1&&a[i]==NUM)not_finish=0;else a[i]++;}else if(a[i]==NUM) a[i]=1;else a[i]++;}else if(++i<=NUM)if(a[i-1]==NUM) a[i]=1;else a[i]=a[i-1]+1;}if(not_finish){++count;printf((count-1)%3?" [%2d]: ":" \n[%2d]: ",count);for(k=1;k<=NUM;k++)printf(" %d",a[k]);if(a[NUM-1]<NUM) a[NUM-1]++;else a[NUM-1]=1;i=NUM-1;}}}2.k阶斐波那契序列，要求满足fn ≤max而fn+1 >max 。

（循环队列的容量仅为k或k+1）#include <stdio.h>#define QL 10typedef struct queue{int data[QL];int f,r;}queue,Q;void feibo(Q &q,int max){int mul=0;q.f=q.r=0;q.data[q.r]=1;q.r++;q.data[q.r]=1;while(q.data[q.r]<max){q.r++;if(q.r%QL==q.f){if(q.r==QL){mul++;q.r=q.f;}if(q.f!=QL-1)q.f++;elseq.f=0;}if(q.r>=2){q.data[q.r]=q.data[q.r-1]+q.data[q.r-2];}else{if(q.r==0)q.data[q.r]=q.data[QL+q.r-1]+q.data[QL+q.r-2];elseq.data[q.r]=q.data[q.r-1]+q.data[QL+q.r-2];}}printf("%d\n",mul);printf("n=%d\n",QL*mul+q.r-1);if(q.r>=1)printf("f(n)=%d\n",q.data[q.r-1]);elseprintf("f(n)=%d\n",q.data[QL+q.r-1]);}void main(){Q qq;int n;printf("请输入max值：");scanf("%d",&n);feibo(qq,n);}运行结果：例如：请输入max值：50n=8f（n）= 343.约瑟夫环：编号为1,2,3,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止。

报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一人开始重新从1报数，如此下去，直到所有人全部出列为止。

编程打印出列顺序。

#include<iostream.h>typedef struct strt{int num,pwd;//num为号码，pwd为密码struct strt *next;}*psp,sp;int main(){int m,n,i,j;psp head,rear,pt,pt2,p;head=new sp;rear=head;cout<<"n:";//输入人数cin>>n;cout<<"m:";//输入初始密码cin>>m;pt=head;for(i=1;i<n;i++){pt2=new sp;pt->next=pt2;pt=pt2;rear=pt2;}rear->next=head;pt=head;for(i=1;i<=n;i++){cin>>j;pt->pwd=j;pt->num=i;pt=pt->next;}pt2=pt=rear;for(j=1;j<=n;j++){for(i=1;i<=m;i++){pt2=pt;pt=pt->next;}p=pt2->next;cout<<"num:"<<p->num<<"pwd:"<<p->pwd<<endl; m=p->pwd;pt2->next=p->next;delete(p);pt=pt2;}return 0;//程序结束}程序结果n：4m：21231num：2 pwd：2num：4 pwd：1num：1 pwd：1num：3 pwd：34.按先序扩展序列建立二叉树5. 先序、中序、后序遍历的递归算法#include <stdlib.h>#include <stdio.h>#define STACK_INIT_SIZE 50#define STACKINCREMENT 10#define OK 1#define ERROR 0#define OVERFLOW 0typedef int Status;typedef char TElemType;typedef struct s_BiTNode{TElemType data;struct s_BiTNode *lchild,*rchild;} BiTNode, *BiTree;Status CreateBiTree(BiTree *T);Status InOrderTraverse(BiTree T,Status (*Fun) (TElemType e));Status PostOrderTraverse(BiTree T,Status (*Fun) (TElemType e));Status Visit(TElemType e);void main(){BiTree Tr=NULL;printf("下面以'根左右'的先序扩展顺序构造二叉树:\n");printf("\n请输入二叉树元素,(/表示空) ");if(CreateBiTree(&Tr))printf("构造二叉树成功!\n");elseprintf("构造二叉树失败!\n");printf("\n中序遍历序列为: ");InOrderTraverse(Tr,Visit);printf("\n后序遍历序列为: ");PostOrderTraverse(Tr,Visit);printf("\n");getch();}Status CreateBiTree(BiTree *Tree){TElemType ch;scanf("%c",&ch);if(ch == '/')(*Tree) = NULL;else{if(!((*Tree) = (BiTree)malloc(sizeof(BiTNode))))exit(OVERFLOW);(*Tree)->data = ch;CreateBiTree(&((*Tree)->lchild));CreateBiTree(&((*Tree)->rchild));}return (OK);}Status InOrderTraverse(BiTree T,Status (*Fun) (TElemType e)) {if(T){if(InOrderTraverse(T->lchild,Fun))if(Visit(T->data))if(InOrderTraverse(T->rchild,Fun))return OK;return ERROR;}elsereturn OK;}/*InOrderTraverse*/Status PostOrderTraverse(BiTree T,Status (*Fun) (TElemType e)) {{if(PostOrderTraverse(T->lchild,Fun))if(PostOrderTraverse(T->rchild,Fun)){Visit(T->data);return OK;}return ERROR;}elsereturn OK;}Status Visit(TElemType e){printf("%c",e);return OK;}程序结果：下面以'根左右'的先序扩展顺序构造二叉树:请输入二叉树元素,(/表示空)ABDG///EH//IK///C/F/J/构造二叉树成功!中序遍历序列为：GDBHEKIACFJ后序遍历序列为：GDHKIEBJFCA6.中序遍历的非递归算法7.先序遍历的非递归算法#include <stdio.h>#include <stdlib.h>#define STACKINITSIZE 100#define STACKINCREMENT 10#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedef struct BiTNode{char data;BiTNode *lchild,*rchild;}* BiTree;typedef struct {BiTree *base;BiTree *top;int stacksize,k;int CreateBiTree(BiTree &T){char ch=' ';scanf("%c",&ch);if(ch==' ')T=NULL;else{if(!(T=(BiTree)malloc(sizeof(BiTree))))return 0;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}return 1;}void InitStack(SqStack &S){S.base=(BiTree *)malloc(STACKINITSIZE*sizeof(BiTree));//if(!S.base)return 0;S.top=S.base;S.stacksize=STACKINITSIZE;//return 1;}int StackEmpty(SqStack S){if(S.top==S.base)return 0;return 1;}void Push(SqStack &S,BiTree e){if(S.top-S.base>=S.stacksize){S.base=(BiTree *)realloc(S.base,(STACKINITSIZE+STACKINCREMENT)*sizeof (BiTree));//if(!S.base)return 0;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*(S.top)=e;S.top++;}int Pop(SqStack &S,BiTree *e){if(S.top==S.base)return 0;S.top--;*e=*S.top;return 1;}int GetTop(SqStack s,BiTree e){if(s.top==s.base)return 0;e=*(s.top--);return 1;}//*******************void PreOrderTraverser(BiTree T){//非递归先序遍历二叉树SqStack s;InitStack(s);BiTree p;p=T;while(p||StackEmpty(s)){if(p){printf("%c",p->data);Push(s,p);p=p->lchild;}else{Pop(s,&p);p=p->rchild;}}}void InOrderTraverse(BiTree T){//非递归中序遍历二叉树SqStack s;InitStack(s);BiTree p;p=T;while(p||StackEmpty(s)){if(p){Push(s,p);p=p->lchild;}else{Pop(s,&p);printf("%c",(*p).data);p=p->rchild;}}}void main(){BiTree T;printf("输入二叉树的先序扩展序列");CreateBiTree(T);printf("\n非递归中序遍历二叉树：");InOrderTraverse(T);printf("\n非递归先序遍列二叉树：");PreOrderTraverser(T);printf("\n");}运行结果：输入二叉树的先序扩展序列：ABDGEHIKCFJ非递归中序遍历二叉树：GDBHEKIACFJ非递归先序遍列二叉树：ABDGEHIKCFJ8.后序遍历的非递归算法#define STACKINITSIZE 100#define STACKINCREMENT 10#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedef struct BiTNode{char data;BiTNode *lchild,*rchild;}* BiTree;typedef struct {BiTree *base;BiTree *top;int *ibase;int mark;int stacksize;}SqStack;int CreateBiTree(BiTree &T){char ch=' ';scanf("%c",&ch);if(ch==' ')T=NULL;else{if(!(T=(BiTree)malloc(sizeof(BiTree))))return 0;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}return 1;}void InitStack(SqStack &S){S.base=(BiTree *)malloc(STACKINITSIZE*sizeof(BiTree));S.ibase=(int *)malloc(STACKINITSIZE*sizeof(int));//if(!S.base)return 0;S.top=S.base;S.mark=0;S.stacksize=STACKINITSIZE;//return 1;}int StackEmpty(SqStack S){if(S.top==S.base)return 1;return 0;}void Push(SqStack &S,BiTree e,int i){if(S.top-S.base>=S.stacksize){S.base=(BiTree *)realloc(S.base,(STACKINITSIZE+STACKINCREMENT)*sizeof(BiTree));//if(!S.base)return 0;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*(S.top)=e;S.ibase[S.mark]=i;S.mark++;S.top++;}int Pop(SqStack &S,BiTree *e,int &i){if(S.top==S.base)return 0;S.top--;*e=*S.top;S.mark--;i=S.ibase[S.mark];return 1;}void PostOrderTraverser(BiTree T){SqStack s;int i=0;InitStack(s);BiTree p;p=T;Push(s,p,0);while(!StackEmpty(s)){Pop(s,&p,i);switch(i){case 0:Push(s,p,1);if(p->lchild)Push(s,p->lchild,0);break;case 1:Push(s,p,2);if(p->rchild)Push(s,p->rchild,0);break;case 2:printf("%c",p->data);}}}void main(){BiTree T;printf("输入结点的先序扩展序列:");CreateBiTree(T);printf("\n非递归后序遍历为：");PostOrderTraverser(T);printf("\n");}运行结果：输入结点的先序扩展序列: ABDGEHIKCFJ非递归后序遍历为：GDHKIEBJFCA9.层次的非递归算法#include<stdio.h>#include<stdlib.h>typedef struct BiTNode{char data;BiTNode *lchild,*rchild;}* BiTree;void CreateBiTree(BiTree &T){//printf("按先序次序输入结点的值,并以$作为结束符号");char ch=' ';scanf("%c",&ch);if(ch==' ')T=NULL;else{if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))printf("cuo");T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}}void visit(BiTree T){//按先序序列访问二叉树，并打印出它的扩展序列；if(T)printf("%c",T->data);else printf("树是空树");if(T->lchild)visit(T->lchild);else printf(" ");if(T->rchild)visit(T->rchild);else printf(" ");}typedef struct QNode{BiTree data;QNode *next;}QNode,*QueuePtr;//**********typedef struct{QueuePtr front;QueuePtr rear;}LinkQueue;void InitQueue(LinkQueue &Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));Q.front->next=NULL;}void DestroyQueue(LinkQueue &Q){while(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}}void EnQueue(LinkQueue &Q,BiTree e){QNode *p;p=(QueuePtr)malloc(sizeof(QNode));p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;}int DeQueue(LinkQueue &Q){if(Q.front==Q.rear)return 0;QNode *p;p=Q.front->next;//e=*p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;return 1;}void CengTraverser(BiTree T){LinkQueue Lq;InitQueue(Lq);BiTree p=NULL;p=T;EnQueue(Lq,p);p=Lq.rear->data;while(p){printf("%c",p->data);if(p->lchild){EnQueue(Lq,p->lchild);}if(p->rchild){EnQueue(Lq,p->rchild);}DeQueue(Lq);if(Lq.front!=Lq.rear)p=Lq.front->next->data;else p=NULL;}}void main(){BiTree T;printf("输入二叉树的先序扩展序列");CreateBiTree(T);printf("二叉树的层次遍历为:");CengTraverser(T);printf("\n");}10.求二叉树的深度(后序遍历)#include<stdio.h>#include<stdlib.h>typedef struct BiTNode{char data;BiTNode *lchild,*rchild;//左右孩子指针}* BiTree;int CreateBiTree(BiTree &T){scanf("%c",&ch);if(ch==' ')T=NULL;else{if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))return 0;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}return 1;}//后序遍历的递归算法int deep(BiTree T){//按后序遍历，并打印出它的后序序列；if(T){return (deep(T->lchild)>deep(T->rchild)?deep(T->lchild):deep(T->rchild))+1;}else return 0;}void main(){BiTree T;printf("\n输入二叉树的先序扩展序列:");CreateBiTree(T);printf("\n二叉树的深度为：");printf("%d",deep(T));printf("\n");}11.求树的深度#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedef struct CSNode{char data;CSNode *firstchild,*nextsibling;}CSNode,*CSTree;int CreateCSTree(CSTree &T){char ch=' ';scanf("%c",&ch);if(ch==' ')T=NULL;else{if(!(T=(CSNode *)malloc(sizeof(CSNode))))return 0;T->data=ch;CreateCSTree(T->firstchild);CreateCSTree(T->nextsibling);}return 1;}int deep(CSTree T){//按后序遍历求树的深度；if(T){return (deep(T->firstchild)+1)>deep(T->nextsibling)?(deep(T->firstchild)+1):deep(T->nextsibling);}else return 0;}void main(){CSTree T;printf("\n按照先序遍历扩展序列输入树终结点的值:");CreateCSTree(T);printf("\n树的深度为：");printf("%d",deep(T));printf("\n");}12.编写DFS算法的非递归函数。

合集下载

北京理工大学数据结构编程练习答案

北京理工大学数据结构编程练习答案

1.一元多项式相加(10分)成绩: 10 / 折扣: 0.8题目说明：编写一元多项式加法运算程序。

要求用线性链表存储一元多项式（参照课本）。

该程序有以下几个功能：1. 多项式求和输入：输入三个多项式，建立三个多项式链表Pa、Pb、Pc（提示：调用CreatePolyn(polynomial &P,int m)。

输出：显示三个输入多项式Pa、Pb、Pc、和多项式Pa+Pb、多项式Pa+Pb+Pc （提示：调用AddPolyn(polynomial &Pa, polynomial Pb), 调用PrintPolyn(polynomial P))。

0. 退出输入：根据所选功能的不同，输入格式要求如下所示（第一个数据是功能选择编号，参见测试用例）：∙ 1多项式A包含的项数，以指数递增的顺序输入多项式A各项的系数（整数）、指数（整数）多项式B包含的项数，以指数递增的顺序输入多项式B各项的系数（整数）、指数（整数）多项式C包含的项数，以指数递增的顺序输入多项式C各项的系数（整数）、指数（整数）∙0 －－－操作终止，退出。

输出：对应一组输入，输出一次操作的结果（参见测试用例）。

∙ 1 多项式输出格式：以指数递增的顺序输出: <系数,指数>,<系数,指数>,<系数,指数>,参见测试用例。

零多项式的输出格式为<0,0>∙0 无输出1.#include<iostream>#include<stdlib.h>using std::cin;using std::cout;using std::endl;struct date{int a;int b;struct date* pnext;};typedef struct date DATE;typedef struct date* PDATE;void output(PDATE p){int f=0;p=p->pnext;while(p!=NULL){if(p->a!=0){f=1;cout<<"<"<<p->a<<","<<p->b<<">";if(p->pnext==NULL)cout<<endl;elsecout<<",";}p=p->pnext;}if(f==0)cout<<"<0,0>"<<endl;}void add(PDATE a,PDATE b,PDATE c){PDATE p1,p2,p3;p1=a;p2=b;p3=c;if(p1!=NULL) p1=p1->pnext; //skip head if(p2!=NULL) p2=p2->pnext;while((p1!=NULL)&&(p2!=NULL)){if(p1->b>p2->b){p3->pnext=(PDATE)malloc(sizeof(DATE));p3=p3->pnext;p3->a=p2->a;p3->b=p2->b;p3->pnext=NULL;p2=p2->pnext;}else if(p1->b<p2->b){p3->pnext=(PDATE)malloc(sizeof(DATE));p3=p3->pnext;p3->a=p1->a;p3->b=p1->b;p3->pnext=NULL;p1=p1->pnext;}else{p3->pnext=(PDATE)malloc(sizeof(DATE));p3=p3->pnext;p3->a=p1->a+p2->a;p3->b=p1->b;p3->pnext=NULL;p1=p1->pnext;p2=p2->pnext;}}//end whileif(p1==NULL)p3->pnext=p2;if(p2==NULL)p3->pnext=p1;}int main(){int flag;int n;PDATE P[6]={NULL};PDATE p=NULL;for(int i=0;i<6;i++){P[i]=(PDATE)malloc(sizeof(DATE));P[i]->a=0;P[i]->b=0;P[i]->pnext=NULL;}cin>>flag;if(flag==1){for(int i=1;i<4;i++){p=P[i];cin>>n;while(n--!=0){p->pnext=(PDATE)malloc(sizeof(DATE));p=p->pnext;cin>>p->a>>p->b;p->pnext=NULL;}output(P[i]);}}add(P[1],P[2],P[4]);output(P[4]);add(P[4],P[3],P[5]);output(P[5]);}0 约瑟夫问题(10分)成绩: 10 / 折扣: 0.80 约瑟夫问题成绩10分折扣0.8(本题要求用循环链表实现)0 ,1, 2, 3题,只能选做三题.约瑟夫问题是一个经典的问题。

数据结构全部代码

数据结构全部代码

引言：数据结构是计算机科学中非常重要的一门基础课程，它涉及到用于组织、管理和存储数据的各种方法和技术。

数据结构的学习对于编程和算法的理解至关重要。

本文将深入讨论数据结构的各种代码实现，包括数组、链表、树、堆以及图等。

概述：数据结构的代码实现是指将数据结构的抽象概念转化为实际的编程实现。

这些代码实现提供了一种将数据组织在计算机存储中的方法，并且支持各种对数据的操作。

下面将分别介绍数组、链表、树、堆以及图的代码实现。

正文内容：1.数组1.1创建数组1.2访问数组元素1.3修改数组元素1.4插入元素到数组中1.5从数组中删除元素2.链表2.1单链表的实现2.1.2在链表头部插入节点2.1.3在链表尾部插入节点2.1.4在指定位置插入节点2.1.5从链表中删除节点2.2双链表的实现2.2.1创建双链表节点2.2.2在链表头部插入节点2.2.3在链表尾部插入节点2.2.4在指定位置插入节点2.2.5从链表中删除节点3.树3.1二叉树的实现3.1.1创建二叉树节点3.1.2在二叉树中插入节点3.1.3从二叉树中删除节点3.1.4遍历二叉树3.1.5搜索二叉树中的某个元素3.2AVL树的实现3.2.2在AVL树中插入节点3.2.3从AVL树中删除节点3.2.4平衡AVL树3.2.5遍历AVL树4.堆4.1最大堆的实现4.1.1创建最大堆4.1.2插入元素到最大堆4.1.3从最大堆中删除元素4.1.4获取最大堆的最大值4.1.5堆排序4.2最小堆的实现4.2.1创建最小堆4.2.2插入元素到最小堆4.2.3从最小堆中删除元素4.2.4获取最小堆的最小值4.2.5堆排序5.图5.1邻接矩阵的实现5.1.1创建邻接矩阵5.1.2在邻接矩阵中插入边5.1.3从邻接矩阵中删除边5.1.4遍历邻接矩阵5.1.5判断两个节点是否相邻5.2邻接表的实现5.2.1创建邻接表5.2.2在邻接表中插入边5.2.3从邻接表中删除边5.2.4遍历邻接表5.2.5判断两个节点是否相邻总结：。

数据结构c语言实现

数据结构c语言实现

数据结构c语言实现数据结构是计算机科学中重要的一个领域，它研究不同的数据组织方式，以及在这些数据上进行各种操作的算法。

常见的数据结构包括数组、栈、队列、链表、树、图等。

在C语言中，数据结构是通过使用结构体来实现的。

结构体是由一组数据成员组合而成的自定义数据类型，可以包含不同数据类型的数据成员。

以下是如何在C语言中实现不同的数据结构。

数组数组是数据结构中最基本的数据结构之一。

C语言中的数组定义方式如下：```int array[5];```这个代码定义了一个名为array的数组，其中有5个元素，每个元素的类型是整数。

要访问数组中的元素，可以通过下标访问：这个代码设置了数组中第一个元素的值为1。

栈栈是一种后进先出（LIFO）的数据结构。

使用C语言中的数组可以实现栈。

以下是一个简单的栈实现：```#define MAXSIZE 100int stack[MAXSIZE];int top = -1;void push(int data){if(top<MAXSIZE-1){ //判断栈是否满了stack[++top] = data; //插入数据}}int isEmpty(){return top==-1; //栈是否为空}队列链表链表是一个由节点组成的数据结构，每个节点包含一个数据成员和一个指向下一个节点的指针。

在C语言中，链表可以使用结构体和指针来实现。

以下是一个单向链表的实现：```struct node{int data;struct node *next;};struct node *head = NULL;void insert(int data){struct node *new_node = (struct node*) malloc(sizeof(struct node)); //分配内存new_node->data = data; //初始化数据new_node->next = head; //新节点指向当前头节点head = new_node; //更新头节点}void delete(int data){struct node *current_node = head; //从头节点开始查找struct node *previous_node = NULL;while(current_node!=NULL&&current_node->data!=data){ //查找节点previous_node = current_node;current_node = current_node->next;}if(current_node!=NULL){ //找到了节点if(previous_node!=NULL){ //非头节点previous_node->next = current_node->next; }else{ //头节点head = current_node->next;}free(current_node); //释放内存}}树。

数据结构课程设计代码

数据结构课程设计代码

数据结构课程设计代码根据提供的输入输出需求，下面是一个示例的数据结构课程设计代码。

```pythonclass Node:def __init__(self, data):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = Nonedef add(self, data):new_node = Node(data)if self.head is None:self.head = new_nodeelse:current = self.headwhile current.next is not None:current = current.nextcurrent.next = new_nodedef remove(self, data):current = self.headprev = Nonewhile current is not None:if current.data == data:if prev is None:self.head = current.next else:prev.next = current.next returnprev = currentcurrent = current.nextdef display(self):current = self.headwhile current is not None:print(current.data, end=" ")current = current.nextprint()if __name__ == "__main__":linked_list = LinkedList()while True:print("1. Add element")print("2. Remove element")print("3. Display elements")print("4. Quit")choice = input("Enter your choice: ")if choice == "1":data = input("Enter element to add: ")linked_list.add(data)elif choice == "2":data = input("Enter element to remove: ")linked_list.remove(data)elif choice == "3":linked_list.display()elif choice == "4":breakelse:print("Invalid choice")```这个代码示例实现了一个简单的链表数据结构，在命令行中提供了添加元素、删除元素和显示元素的选项。