数据结构实验源代码

数据结构实验代码2第一点：数据结构实验代码2的背景与意义数据结构是计算机科学中至关重要的一个领域，它研究如何有效地存储、组织和管理数据，以及如何高效地执行相关操作。

在现代软件开发和计算机科学教育中，理解和掌握数据结构是不可或缺的。

数据结构实验代码2，作为一个具体的实践案例，旨在帮助学生深化对数据结构理论知识的理解，通过亲自动手编写和调试代码，增强对数据结构在实际应用中的认识。

实验代码2通常涉及到复杂的数据结构，比如图（Graph）、树（Tree）的高级算法实现，比如深度优先搜索（DFS）、广度优先搜索（BFS）、最短路径算法（如Dijkstra或Bellman-Ford算法）、最小生成树算法（如Prim或Kruskal算法）等。

通过对这些算法的实验实现，学生不仅能够掌握算法的工作原理，还能够理解其在解决实际问题时的效率和适用场景。

此外，数据结构实验代码2也是对学生编程能力和问题解决能力的一种锻炼。

在编写代码的过程中，学生需要考虑到算法的效率、空间复杂度，以及代码的可读性和可维护性。

这对于学生将来从事软件开发工作，具有重要的现实意义。

在当前的数字经济时代，数据结构的掌握程度直接关系到软件质量的高低和开发效率的快慢，因此，数据结构实验代码2在计算机科学与技术教育中占有举足轻重的地位。

第二点：数据结构实验代码2的关键技术与实现步骤数据结构实验代码2在技术实现上，涉及多个关键的步骤和考虑因素。

首先，学生需要选择合适的编程语言和开发环境，这对于代码的编写和调试都是非常重要的。

常见的编程语言如C/C++、Java、Python等，都具备实现复杂数据结构和算法的性能和灵活性。

接下来，是数据结构的具体实现。

这要求学生不仅要熟悉类和对象的概念，还需要能够设计出既符合数据结构特性，又能够有效实现算法逻辑的类和对象。

例如，在实现图的数据结构时，学生需要定义图的节点（Vertex）和边（Edge），并且提供添加节点、添加边、查找节点等基础操作。

数据结构实验完整代码目录一、顺序存储的线性表 (2)二、单链存储的线性表 (4)三、栈 (7)四、队列 (8)五、二叉树的建立和遍历 (10)六、霍夫曼树 (11)七、图的建立和遍历 (17)图的邻接矩阵表示 (17)图的邻接表表示 (20)八、图的最小生成树 (23)九、图的最短路径 (28)十、顺序查找表 (31)十一、二叉排序树的查找 (34)十二、哈希表 (36)十三、插入排序 (41)十四、交换排序-冒泡排序 (44)十五、交换排序-快速排序 (45)十六、简单选择排序 (45)十七、堆排序 (46)一、顺序存储的线性表typedef struct{char name[10];char no[10];double grade;}Student;typedef struct{Student *elem;int length;int listsize;}SqList;void Display(SqList *L){int i;for (i=0;i<L->length ;i++){cout<<i+1<<"：姓名"<<L->elem[i].name<<"，学号："<<L->elem[i].no<<"，成绩："<<L->elem[i].grade <<endl;}cout<<"请选择菜单项：";}SqList *CreateList(){SqList *L;L=(SqList*)malloc(sizeof(SqList));if(!L) cout<<"建立线性表失败！";else cout<<"建立线性表成功！";return(L);}int InitList(SqList *L){int i;char name[10],no[10];double grade;L->elem=(Student *)malloc(ListInitSize * sizeof(Student));if (!(L->elem)) cout<<"初始化表失败！";L->length = 0;L->listsize = ListInitSize;cout<<"请输入要录入信息的学生个数："<<endl;cin>>i;if (i>(L->listsize)){L->elem =(Student *)realloc(L->elem ,i*sizeof(Student));}for (int j=0;j<i;j++){cout<<"请输入第"<<j+1<<"个学生的信息："<<endl;cin>>name>>no>>grade;strcpy((L->elem+L->length)->name,name);strcpy((L->elem+L->length)->no,no);(L->elem+L->length)->grade =grade;L->length ++;}cout<<"信息录入完成！";return 0;}int Insert(SqList *l){Student e;int i,j;Student *newbase;cout<<"请输入要插入的位置：";cin>>j;j--;cout<<"请输入学生信息：";cin>>>>e.no>>e.grade;if(l->length==l->listsize){newbase=(Student*)realloc(l->elem,(l->listsize+ListIncreasement)*sizeof(Studen t));if(!newbase){cout<<"出错!";return 0;}l->elem=newbase;l->listsize+=ListIncreasement;}for(i=l->length;i>=j;i--){l->elem[i+1] = l->elem[i];}l->elem[j]=e;l->length++;cout<<"插入成功！";return 0;}int Delect(SqList *L){int i,j;cout<<"输入删除信息的位置:";cin>>j;j--;cout<<"删除的信息为:姓名："<<L->elem[j].name<<"，学号："<<L->elem[j].no<<"成绩："<<L->elem[j].grade<<endl;for(i=j+1;i<=L->length;i++){L->elem[i-1]=L->elem[i];}L->length--;cout<<"请按回车继续"<<endl;getchar();getchar();cout<<"删除成功！";return 0;}二、单链存储的线性表typedef struct Student{char name[10];char no[10];double grade;}Student;typedef struct LNode{Student data;LNode *next;}LNode,*LinkList;void CreateList(LinkList &l){l=(LinkList)malloc(sizeof(LNode));if (!l) cout<<"建立失败。

/* 树子系统*/#include <stdio.h>#include <malloc.h> #define MAX 100int count=0; /* 定义计算结点个数的变量*/ typedef struct tnode{char data;struct tnode *lchild,*rchild;}BT;BT *CreateBTree(){BT *t;char ch;scanf("%c",&ch);getchar();if(ch=='0')t=NULL;else{t=(BT *)malloc(sizeof(BT));t->data=ch;printf("请输入％c结点的左孩子结点:t->lchild=CreateBTree();printf("请输入％c结点的右孩子结点:t->rchild=CreateBTree();}return t;}void ShowBTree(BT *T){ if (T!=NULL){ printf("%c",T->data);if(T->lchild!=NULL){ printf("(");ShowBTree(T->lchild);if(T->rchild!=NULL){ printf(",");ShowBTree(T->rchild);}printf(")");}else",t->data);",t->data/* 用广义表表示法显示二叉树*//*当二叉树非空时*//*输入该结点数据域*//* 若其左子树非空*//* 输入左括号*//* 递归调用该函数输出其左子树各结点*/ /* 若其右子树非空*//* 输出逗号*//* 递归调用该函数输出其右子树各结点*//* 二叉树左子树为空，右子树不为空时*/ if(T->rchild!=NULL){printf("(");ShowBTree(T->lchild);if(T->rchild!=NULL){ printf(",");ShowBTree(T->rchild);} printf(")");}}}void PreOrder(BT *T){ if(T==NULL) return;else{ printf("%c",T->data);PreOrder(T->lchild);PreOrder(T->rchild);}}void InOrder(BT *T){ if(T==NULL) return;else{ InOrder(T->lchild);printf("%c",T->data);InOrder(T->rchild);}}void PostOrder(BT *T){ if (T==NULL) return;else{ PostOrder(T->lchild);PostOrder(T->rchild);printf("%c",T->data);}}void LevelOrder(BT *T){ int f,r;BT *p,*q[MAX];p=T;/* 输入左括号*//* 递归调用该函数输出其左子树各结点*/ /* 若其右子树非空*//* 输出逗号*//*递归调用该函数输出其右子树各结点*//* 先序遍历二叉树T*//*递归调用的结束条件*//* 输出结点的数据域*//*先序递归遍历左子树*//*先序递归遍历右子树*//* 中序遍历二叉树T*//* 递归调用的结束条件*//* 中序递归遍历左子树*//* 输出结点的数据域*//* 中序递归遍历右子树*//* 后序遍历二叉树T*//* 递归调用的结束条件*//* 后序递归遍历左子树*//* 后序递归遍历右子树*//* 输出结点的数据域*//* 按层次遍历二叉树T*//* 定义队头队尾指针*//* 定义循环队列，存放结点指针*if(p!=NULL){ f=1; q[f]=p; r=2; } while(f!=r) { p=q[f];printf("%c",p->data); if(p->lchild!=NULL) { q[r]=p->lchild; r=(r+1)%MAX; }if(p->rchild!=NULL) { q[r]=p->rchild; r=(r+1)%MAX; }f=(f+1)%MAX; }}/* 若二叉树非空，则根结点地址入队*//* 队列不空时 *//* 访问队首结点的数据域 */ /* 将队首结点的左孩子入队 *//* 将队首结点的右孩子入队 */void Leafnum(BT *T) /* 求二叉树叶子结点数 */ { if(T)/* 若树不为空 */{ if(T->lchild==NULL && T->rchild==NULL)count++; Leafnum(T->lchild); Leafnum(T->rchild);} }/* 全局变量 count 为计数值， 其初值为 0*/ /* 递归统计 T 的左子树叶子结点数 */ /* 递归统计 T 的右子树叶子结点数 */return rdep+1;void Nodenum(BT *T) { if(T) { count++;Nodenum(T->lchild); Nodenum(T->rchild);}} int TreeDepth(BT *T) { int ldep=0,rdep=0; 的深度 */ if(T==NULL) return 0; else { ldep=TreeDepth(T->lchild); rdep=TreeDepth(T->rchild); if(ldep>rdep)return ldep+1; else /* 若树不为空 *//* 全局变量 c ount 为计数值， 其初值为0*/ /* 递归统计 T 的左子树结点数 */ /* 递归统计 T 的右子树结点数 *//* 求二叉树深度 *//* 定义两个整型变量， 用以存放左、右子树/* 递归统计 T 的左子树深度 */ /* 递归统计 T 的右子树深度 */二叉树子系统");printf （"\n ================================================="）; printf （"\n| 1——建立一个新二叉树 |"）; printf （"\n| 2 --- 广义表表示法显示 |"）; printf （"\n| 3 --- 先序遍历 |"）; printf （"\n| 4 --- 中序遍历 |"）; printf （"\n| 5 --- 后序遍历 |"）; printf （"\n| 6 --- 层次遍历 |"）; printf （"\n| 7 --- 求叶子结点数目 |"）; printf （"\n| 8 --- 求二叉树总结点数目 |"）; printf （"\n| 9——求树深度 |"）; printf （"\n|0 --- 返回|"）;printf （"\n ================================================"）; printf （"\n 请输入菜单号（0-9 ）:"）;btree （） （BT *T=NULL; char ch1,ch2,a; ch1='y';while （ch1=='y'||ch1=='Y'） { MenuTree （）;scanf （"%c",&ch2）; getchar （）; switch （ch2） {case '1':printf （"请按先序序列输入二叉树的结点： \n"）;printf （"说明：输入结点后按回车（’0'表示后继结点为空）：\n"）; printf （"请输入根结点："）； T=CreateBTree （）;printf （"二叉树成功建立！ "）;break; case '2':printf （"二叉树广义表表示法如下： "）; ShowBTree （T ）;break; case '3':printf （"二叉树的先序遍历序列为： "）; PreOrder （T ）;break; case '4':printf(" 二叉树的中序遍历序列为： ");void （MenuTree （）/*显示菜单子函数*/printf （"\nInOrder(T);break;case '5':printf(" 二叉树的后序遍历序列为：");PostOrder(T);break;case '6':printf(" 二叉树的层次遍历序列为：");LevelOrder(T);break;case '7':count=0;Leafnum(T);printf("该二叉树有％~个叶子。

数据结构与算法实验源代码数据结构与算法实验源代码1.实验目的本实验旨在通过实践，加深对数据结构与算法的理解与应用能力，掌握数据结构和算法的基本概念与原理，并能够运用所学知识解决实际问题。

2.实验材料●一台已安装好编译器的计算机●数据结构与算法实验源代码文件3.实验环境配置在实验开始之前，必须确保计算机上已安装好以下环境：●编译器（可以是C++、Java等）●数据结构与算法实验源代码文件4.实验内容及步骤4.1 实验一：线性表4.1.1 实验目的通过实现线性表的相关操作，加深对线性表及其操作的理解，并能够灵活应用。

4.1.2 实验步骤1.实现线性表的初始化函数2.实现线性表的插入操作3.实现线性表的删除操作4.实现线性表的查找操作5.实现线性表的排序操作6.实现线性表的输出操作7.编写测试代码，对线性表进行测试4.1.3 实验结果与分析进行若干测试用例，验证线性表的正确性，并分析算法的时间复杂度与空间复杂度。

4.2 实验二：栈与队列4.2.1 实验目的通过实现栈与队列的相关操作，加深对栈与队列的理解，并掌握栈与队列的应用场景。

4.2.2 实验步骤1.实现栈的初始化函数2.实现栈的入栈操作3.实现栈的出栈操作4.实现栈的查看栈顶元素操作5.实现队列的初始化函数6.实现队列的入队操作7.实现队列的出队操作8.实现队列的查看队首元素操作4.2.3 实验结果与分析进行若干测试用例，验证栈与队列的正确性，并分析算法的时间复杂度与空间复杂度。

（继续添加实验内容及步骤，具体根据实验项目和教学要求进行详细分析）5.实验附件本文档所涉及的实验源代码文件作为附件随文档提供。

6.法律名词及注释6.1 版权：著作权法所规定的权利，保护作品的完整性和原创性。

6.2 开源：指软件可以被任何人免费使用、分发和修改的一种软件授权模式。

（继续添加法律名词及注释）。

数据结构实验源代码第二章线性表标题：约瑟夫环描述：约瑟夫环编号为1，2，3，……，n的n个人按顺时针方向围坐一圈。

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

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

设计程序输出出列顺序。

输入：人数n 报数上限m人员记录1 (格式为：姓名学号性别年龄班级健康状况)人员记录2?…人员记录n输出：第1次报数出列的人员记录第2次报数出列的人员记录…第n次报数出列的人员记录输入样例：5 3安弥邵女 28 计43 一般宰觅男 23 计79 健康；顾健男 27 计29 一般宓顽芳女 20 计17 健康能纸垄男 18 计11 健康输出样例：顾健男27 计29 一般安弥邵女28 计43 一般能纸垄男18 计11 健康宰觅男23 计79 健康宓顽芳女20 计17 健康提示：循环表#include<>#include<>#include<>um);scanf("%s", x[i].name); scanf("%f",&x[i].score_1);scanf("%f",&x[i].score_2);scanf("%f",&x[i].score_3);ListInsert(L,i,x[i]); }Ranking(L);while(p->next!=NULL){p=p->next;printf("%ld " ,p->; printf("%s " ,p->; printf("%.2f " ,p->; printf("%.2f " ,p->; printf("%.2f " ,p->; printf("%.2f " ,p->; printf("%ld\n" ,p->;}Destroy(&L);return 0;}标题：链表上的基本操作实现描述：在单链表存储结构上实现基本操作：初始化、创建、插入、删除、查找、遍历、逆置、合并运算。

数据结构完整代码数据结构完整代码1. 简介数据结构是计算机科学中的一个重要概念，用于组织和管理数据的方式。

在许多实际应用中，我们需要根据不同的需求选择合适的数据结构来存储和操作数据。

本文将介绍常见的数据结构，包括数组、链表、栈、队列和树，并提供完整的代码实现示例。

2. 数组（Array）数组是一种线性数据结构，用于存储固定大小的相同类型元素的集合。

数组的元素通过索引进行访问，索引是从0开始的整数。

以下是一个简单的数组实现示例代码：```pythonclass Array:def __init__(self, size):self.size = sizeself.data = [None] sizedef get(self, index):if index < 0 or index >= self.size:return Nonereturn self.data[index]def set(self, index, value):if index < 0 or index >= self.size:return Noneself.data[index] = value```3. 链表（Linked List）链表是一种常见的动态数据结构，它由多个节点组成，每个节点包含数据和指向下一个节点的指针。

链表的特点是在内存中不连续存储，而是通过指针将各个节点连接起来。

以下是一个简单的链表实现示例代码：```pythonclass Node:def __init__(self, value):self.value = valueself.next = Noneclass LinkedList:def __init__(self):self.head = Nonedef append(self, value):new_node = Node(value)if not self.head:self.head = new_nodeelse:curr_node = self.headwhile curr_node.next:curr_node = curr_node.next curr_node.next = new_nodedef remove(self, value):curr_node = self.headif curr_node.value == value:self.head = curr_node.nextreturnwhile curr_node.next:if curr_node.next.value == value:curr_node.next = curr_node.next.nextreturncurr_node = curr_node.next```4. 栈（Stack）栈是一种基于后进先出（LIFO）原则的数据结构，只能在一端进行插入和删除操作。

数据结构源代码归纳(一)2008年08月01日星期五23:46第一章绪论P8例：计算f=1！+2！+3！+…+n！，用C语言描述。

void factorsum（n）int n；{int i，j；int f，w；f=0；for （i=1；i〈=n；i++）{w=1；for （j=1；j〈=i；j++）w=w*j；f=f+w；}return；}第二章线性表P16【算法2.1 顺序表的插入】int Insert(Elemtype List[],int *num,int i,Elemtype x){/*在顺序表List[]中，*num为表尾元素下标位置，在第i个元素前插入数据元素x，若成功，返回TRUE，否则返回FALSE。

*/int j;if (i<0||i>*num+1){printf("Error!"); /*插入位置出错*/return FALSE;}if (*num>=MAXNUM-1){printf("overflow!");return FALSE;} /*表已满*/for (j=*num;j>=i;j--)List[j+1]=List[j]; /*数据元素后移*/List[i]=x; /*插入x*/(*num)++; /*长度加1*/return TRUE;}P18【算法2.2 顺序表的删除】int Delete(Elemtype List[],int *num,int i){/*在线性表List[]中，*num为表尾元素下标位置，删除第i个长度，线性表的长度减1，若成功，则返回TRUE；否则返回FALSE。

*/int j;if(i<0||i>*num){printf("Error!"); return FALSE; } /*删除位置出错！*/for(j=i+1;j<=*num;j++)List[j-1]=List[j]; /*数据元素前移*/(*num)--; /*长度减1*/return TRUE; }P19 例：将有序线性表La={2,4,6,7,9}，Lb={1,5,7,8}，合并为Lc={1,2,4,5,6,7,7,8,9}。

数据结构与算法实验源代码数据结构与算法实验源代码一、实验目的本实验旨在通过编写数据结构与算法的实验源代码，加深对数据结构与算法的理解，并提高编程能力。

二、实验环境本实验使用以下环境进行开发和测试：- 操作系统：Windows 10- 开发工具：IDEA（集成开发环境）- 编程语言：Java三、实验内容本实验包括以下章节：3.1 链表在本章节中，我们将实现链表数据结构，并实现基本的链表操作，包括插入节点、删除节点、查找节点等。

3.2 栈和队列在本章节中，我们将实现栈和队列数据结构，并实现栈和队列的基本操作，包括入栈、出栈、入队、出队等。

3.3 树在本章节中，我们将实现二叉树数据结构，并实现二叉树的基本操作，包括遍历树、搜索节点等。

3.4 图在本章节中，我们将实现图数据结构，并实现图的基本操作，包括广度优先搜索、深度优先搜索等。

3.5 排序算法在本章节中，我们将实现各种排序算法，包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。

3.6 搜索算法在本章节中，我们将实现各种搜索算法，包括线性搜索、二分搜索、广度优先搜索、深度优先搜索等。

四、附件本文档附带实验源代码，包括实现数据结构和算法的Java源文件。

五、法律名词及注释5.1 数据结构（Data Structure）：是指数据对象中数据元素之间的关系。

包括线性结构、树形结构、图形结构等。

5.2 算法（Algorithm）：是指解决问题的一系列步骤或操作。

算法应满足正确性、可读性、健壮性、高效性等特点。

5.3 链表（Linked List）：是一种常见的数据结构，由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

5.4 栈（Stack）：是一种遵循后进先出（LIFO）原则的有序集合，用于存储和获取数据。

5.5 队列（Queue）：是一种遵循先进先出（FIFO）原则的有序集合，用于存储和获取数据。

5.6 树（Tree）：是由节点组成的层级结构，其中一种节点作为根节点，其他节点按照父子关系连接。

/*顺序表的操作#include<iostream>#include<stdlib.h>using namespace std;Release 13.12 rev 9501 (2013/12/25 19:25:45) gcc 4.7.1 Windows/unicode - 32 bit #define MAX_SIZE 100typedef struct{int *emel;int lenth;}Sq;void init(Sq &l);void create(Sq &l);void trval(Sq &l);void find_value(Sq &l);void find_position(Sq &l);void insert(Sq &l);void dele(Sq &l);int main(){Sq l;init(l);create(l);trval(l);find_value(l);find_position(l);insert(l);trval(l);dele(l);trval(l);return 0;}void init(Sq &l){l.emel =new int[MAX_SIZE];if(l.emel ==NULL){cout<<"\t申请空间失败！"<<endl;exit(1);}l.lenth=0;cout<<"\t成功申请空间！该顺序表的长度目前为:"<<l.lenth<<endl; }void create(Sq &l){cout<<"\t请输入你想输入元素的个数：";int x;cin>>x;if((x<1)&&(x>MAX_SIZE)){cout<<"\t你说输入的数不在范围里"<<endl;return;}int i;for(i=0;i<x;i++){cin>>l.emel[i];}l.lenth=x;cout<<"\t成功赋值！"<<endl;}void trval(Sq &l){int i;cout<<"l(";for(i=0;i<l.lenth;i++){cout<<l.emel[i]<<" ";}cout<<")"<<" 该顺序表现在的长度为："<<l.lenth<<endl;}void find_value(Sq &l){int x,t=0;cout<<"\t请输入你要查找的值：";cin>>x;int i;for(i=0;i<l.lenth;i++){if(l.emel[i]==x){t=1;cout<<"\t成功找到该元素，它是顺序表的第"<<i+1<<"个元素！"<<endl;}}if(t==0){cout<<"\t无该元素！"<<endl;}}void find_position(Sq &l){int x;cout<<"\t请输入你要查找的位置：";cin>>x;int i;if((x<1)||(x>l.lenth)){cout<<"\t输入的值不在范围内！"<<endl;return;}for(i=1;i<=l.lenth;i++){if(i==x){cout<<"\t成功找到该元素，该值是"<<l.emel[i-1]<<endl;}}}void insert(Sq &l){int i,x,y;cout<<"\t请输入你要插入的位置";cin>>x;cout<<"\t请输入你要插入的值";cin>>y;if((x<1)||(x>l.lenth)){cout<<"\t输入的值不在范围内！"<<endl;return;}if(x==l.lenth){l.emel[l.lenth]=y;l.lenth=l.lenth+1;return;}for(i=l.lenth;i>=x;i--){l.emel[i]=l.emel[i-1];}l.emel[x-1]=y;l.lenth=l.lenth+1;}void dele(Sq &l){int i,x;cout<<"\t请输入你要删除位置：";cin>>x;if((x<1)||(x>l.lenth)){cout<<"\t输入的值不在范围内！"<<endl;return;}for(i=x-1;i<=l.lenth;i++){l.emel[i]=l.emel[i+1];}l.lenth=l.lenth-1;}成功申请空间！该顺序表的长度目前为:0请输入你想输入元素的个数：3852成功赋值！l(8 5 2 ) 该顺序表现在的长度为：3请输入你要查找的值：5成功找到该元素，它是顺序表的第2个元素！请输入你要查找的位置：3成功找到该元素，该值是2请输入你要插入的位置3请输入你要插入的值10l(8 5 2 10 ) 该顺序表现在的长度为：4请输入你要删除位置：3l(8 5 10 ) 该顺序表现在的长度为：3--------------------------------Process exited with return value 0 Press any key to continue . . .*//*#include<stdio.h>#include<stdlib.h>typedef struct Link{int num;struct Link *next;}L;L* creat(L* head){head=(L *)malloc(sizeof(L));if(head==NULL){printf("头节点申请失败！\n");exit(-1);}head->next=NULL;}void insert(L* head){int x,i;printf("请输入你想输入数据的个数：");scanf("%d",&x);L *p,*q;p=head;for(i=0;i<x;i++){q=(L *)malloc(sizeof(L));if(q==NULL){printf("新点申请失败！\n");exit(-1);}printf("请输入值：");scanf("%d",&q->num);q->next=NULL;p->next=q;p=q;}}{L *p;p=head->next;while(p!=NULL){printf("值为：%d\n",p->num);p=p->next;}}int main(){L *head;head=creat(head);printf("成功创建头节点！！！\n");insert(head);printf("成功输入数据！！！\n");print(head);return 0;}*//*线性表的操作#include<stdio.h>#include<stdlib.h>typedef struct Link{int num;struct Link *next;}L;L* creat(L* head){head=(L *)malloc(sizeof(L));if(head==NULL){printf("头节点申请失败！\n");exit(-1);}head->next=NULL;return head;}void init(L* head)int x,i;printf("请输入你想输入数据的个数：");scanf("%d",&x);L *p,*q;p=head;for(i=0;i<x;i++){q=(L *)malloc(sizeof(L));if(q==NULL){printf("新点申请失败！\n");exit(-1);}printf("请输入值：");scanf("%d",&q->num);q->next=p->next;p->next=q;}}int print(L* head){L *p;int lenth=0;p=head->next;printf("\t\tL(");while(p!=NULL){lenth++;printf("%d ",p->num);p=p->next;}printf(")\n");return lenth;}int insert(L *head,int lenth){printf("\t\t请输入你要插入的元素的位置:");int in;scanf("%d",&in);if(in<1 || in>lenth){printf("\t\t输入值不在范围内！");return -1;}L *p,*q;p=head->next;q=(L *)malloc(sizeof(L));if(q==NULL){printf("新点申请失败！\n");return -1;}printf("\t\t请为新节点输入值：");scanf("%d",&q->num);int i=0;while(p!=NULL){i++;if(i==in-1){q->next=p->next;p->next=q;}p=p->next;}lenth++;return lenth;}int dele(L *head,int lenth){printf("\t\t请输入你要删除的元素的位置:");int out;scanf("%d",&out);if(out<1 || out>lenth){printf("\t\t输入值不在范围内！");return -1;}L *p,*q;p=head->next;q=head;int i=0;while(p!=NULL){i++;if(i==out){q->next=p->next;}q=p;p=p->next;}lenth--;return lenth;}void find(L *head,int lenth){printf("\t\t请输入你要查找的元素的位置:");scanf("%d",&finder);if(finder<1 || finder>lenth){printf("\t\t输入值不在范围内！");return ;}L *p;p=head->next;int i=0;while(p!=NULL){i++;if(i==finder){printf("\t\t你要找的该位置所对应的值为：%d\n",p->num);}p=p->next;}}int main(){L *head;head=creat(head);printf("成功创建头节点！！！\n");printf("成功输入数据！！！\n");int len;len=print(head);printf("\t\t该线性表的长度为:%d\n",len);len=insert(head,len);len=print(head);printf("\t\t插入后线性表的长度为:%d\n",len);len=dele(head,len);len=print(head);printf("\t\t删除后该线性表的长度为:%d\n",len);find(head,len);return 0;}*//*顺序表的合并#include<iostream>using namespace std;{int *pa;int lenth;};struct LB{int *pb;int lenth;};struct LC{int *pc;int lenth;};void mergelist(LA la,LB lb,LC &lc);int main(){int x,y;LA la;LB lb;cout<<"\t\t请给线性表LA和LB指定长度：";cin>>x>>y;la.pa =new int(sizeof(int)*x);lb.pb =new int(sizeof(int)*y);for(i=0;i<x;i++){cout<<"请输入表LA的值:";cin>>la.pa[i];}cout<<endl;la.lenth=x;for(i=0;i<y;i++){cout<<"请输入表LB的值:";cin>>lb.pb[i];}lb.lenth=y;cout<<"LA(";for(i=0;i<x;i++){cout<<la.pa[i]<<" ";}cout<<")"<<endl;cout<<"LB(";for(i=0;i<y;i++){cout<<lb.pb[i]<<" ";}cout<<")"<<endl;LC lc;mergelist(la,lb,lc);return 0;}void mergelist(LA la,LB lb,LC &lc){lc.lenth=la.lenth+lb.lenth;lc.pc=new int(sizeof(int)*lc.lenth);int *pa=la.pa,*pb=lb.pb,*pc=lc.pc;int *pa_last=la.pa+la.lenth-1;int *pb_last=lb.pb+lb.lenth-1;while(pa<=pa_last && pb<=pb_last){if(*pa <= *pb){*pc++=*pa++;}else{*pc++=*pb++;}}while(pa<=pa_last){*pc++=*pa++;}while(pb<=pb_last){*pc++=*pb++;}cout<<"LC(";int i=0;for(i=0;i<lc.lenth;i++){cout<<lc.pc[i]<<" ";}cout<<")"<<endl;}*/// 栈/*#include<iostream>using namespace std;#include<stdlib.h>#define MAXSIZE 100typedef struct{int *base;int *top;int stacksize;}Sqstack;int Initstack(Sqstack &s);void Push(Sqstack &s,int e);void StackTraverse(Sqstack &s);void Gettop(Sqstack &s);void Pop(Sqstack &s);int main(){Sqstack s;Initstack(s);cout<<"\t\t初始化栈成功！"<<endl;Push(s,2);cout<<"\t\t2入栈成功！"<<endl;Push(s,4);cout<<"\t\t4入栈成功！"<<endl;Push(s,6);cout<<"\t\t6入栈成功！"<<endl;Push(s,8);cout<<"\t\t8入栈成功！"<<endl;cout<<"\n由栈底至栈顶的元素为：";StackTraverse(s);Gettop(s);Pop(s);Gettop(s);return 0;}int Initstack(Sqstack &s){s.base=new int[MAXSIZE];if(s.base==NULL){exit(1);}s.top=s.base;s.stacksize=MAXSIZE;}void Push(Sqstack &s,int e){if(s.top-s.base==s.stacksize){exit(1);}*s.top++=e;}void StackTraverse(Sqstack &s){int *p=s.base,i=0;while(p<s.top){i++;cout<<*p++<<" ";}cout<<"\t\t栈的长度是"<<i<<endl;}void Gettop(Sqstack &s){if(s.base==s.top){exit(1);}cout<<"栈顶元素是："<<*(s.top-1)<<endl; }void Pop(Sqstack &s){if(s.top==s.base){exit(1);}cout<<"出栈的第一个元素是:";cout<<*--s.top<<" "<<endl;}*///队列例题：/*#include<iostream>#include<stdlib.h>using namespace std;#define MAXQSIZE 100typedef struct{int *base;int front;int rear;}SqQueue;int InitQueue(SqQueue &q);int EnQueue(SqQueue &q,int x);int DeQueue(SqQueue &q);int main(){SqQueue q;InitQueue(q);EnQueue(q,1);EnQueue(q,3);EnQueue(q,5);EnQueue(q,7);DeQueue(q);DeQueue(q);DeQueue(q);DeQueue(q);return 0;}int InitQueue(SqQueue &q) {q.base=new int[MAXQSIZE];if(q.base==NULL){exit(1);}q.front=0;q.rear=0;return 0;}int EnQueue(SqQueue &q,int x){if((q.rear+1)%MAXQSIZE==q.front){exit(0);}q.base[q.rear]=x;q.rear=(q.rear+1)%MAXQSIZE;return 0;}int DeQueue(SqQueue &q){if(q.front==q.rear){exit(0);}int x=q.base[q.front];q.front=(q.front+1)%MAXQSIZE;cout<<x<<endl;}*//*#include<iostream>#include<stdlib.h>using namespace std;typedef struct Qnode{int date;struct Qnode *next;}Qnode,*Queueptr;typedef struct{Queueptr front; //队头指针Queueptr rear; //队尾指针}LinkQueue;int InitQueue(LinkQueue &Q);void EnQueue(LinkQueue &Q,int e);void TrvalQueue(LinkQueue Q);void DeQueue(LinkQueue &Q);int main(){LinkQueue Q;InitQueue(Q);EnQueue(Q,1);cout<<"\t元素1入队成功！"<<endl;EnQueue(Q,3);cout<<"\t元素3入队成功！"<<endl;EnQueue(Q,5);cout<<"\t元素5入队成功！"<<endl;EnQueue(Q,7);cout<<"\t元素7入队成功！"<<endl;cout<<"\t队列的元素分别是："<<endl;TrvalQueue(Q);cout<<"\t第一个出队的元素是："<<endl;DeQueue(Q);cout<<"\n\t第一个元素出队完成之后队列中从队头至队尾的元素为：";TrvalQueue(Q);return 0;}int InitQueue(LinkQueue &Q){Q.rear=new Qnode;Q.front=Q.rear;if(Q.front==NULL){exit(0);}Q.front->next=NULL;return 0;}void EnQueue(LinkQueue &Q,int e){Qnode *p=new Qnode;if(!p){exit(1);}p->date=e;p->next=NULL;Q.rear->next=p; //连接Q.rear=p; //修改队尾指针}void TrvalQueue(LinkQueue Q){Qnode *p=Q.front->next;//队头元素while(Q.front!=Q.rear){cout <<p->date<<" ";Q.front=p;p=p->next;}cout<<endl;}void DeQueue(LinkQueue &Q){if(Q.front==Q.rear){return;}Qnode *p=Q.front->next;cout<<"\t"<<p->date<<endl;Q.front->next=p->next;if(Q.rear==p){Q.rear=Q.front;delete p;}}*//*//表达式求值#include<iostream>#include<stdlib.h>#include<stdio.h>using namespace std;#define MAXSIZE 100typedef struct{char *base;char *top;char num;}OPND; //数据栈typedef struct{char *base;char *top;char c;}OPTR; //符号栈int Initstack(OPND &op_n,OPTR &op_t); void Pushstack(OPND &op_n,char ch); void Pushstack(OPTR &op_t,char ch); char Popstack(OPND &op_n,char ch); char Popstack(OPTR &op_t,char ch);char Gettop(OPTR op_t);char Gettop(OPND op_n);int In(char ch);char Precede(char x,char y);char operate(char z,char x,char y);int main(){OPND op_n;OPTR op_t;Initstack(op_n,op_t);Pushstack(op_t,'#');char ch;char p;cin>>ch;while(ch!='#' || Gettop(op_t)!='#'){if(!In(ch)){Pushstack(op_n,ch);cin>>ch;}else{switch( Precede(Gettop(op_t),ch) ){case '<':Pushstack(op_t,ch);cin>>ch;break;case '>':char x,y,z;x=Popstack(op_t,x);y=Popstack(op_n,y);z=Popstack(op_n,z);Pushstack(op_n,operate(z,x,y));break;case '=':p=Popstack(op_t,p);cin>>ch;break;}}}cout<<"\t表达式结果是："<<Gettop(op_n)<<endl;return 0;}int Initstack(OPND &op_n,OPTR &op_t){op_n.base=new char[MAXSIZE];op_t.base=new char[MAXSIZE];if((op_n.base==NULL) || (op_t.base==NULL)) {exit(1);}op_n.top=op_n.base;op_t.top=op_t.base;op_n.num=MAXSIZE;op_t.c=MAXSIZE;return 0;}void Pushstack(OPND &op_n,char ch){if(op_n.top-op_n.base==op_n.num){return;}*op_n.top++=ch;cout<<ch<<" 入数字栈"<<endl;}void Pushstack(OPTR &op_t,char ch){if(op_t.top-op_t.base==op_t.c){return;}*op_t.top++=ch;cout<<ch<<" 入操作符"<<endl; }char Popstack(OPND &op_n,char ch) {if(op_n.top==op_n.base){exit(1);}ch=*--op_n.top;cout<<ch<<" 出数字栈"<<endl;return ch;}char Popstack(OPTR &op_t,char ch) {if(op_t.top==op_t.base){exit(1);}ch=*--op_t.top;cout<<ch<<" 出字符栈"<<endl;return ch;}char Gettop(OPTR op_t){char x;if(op_t.top==op_t.base){exit(1);}x=*(op_t.top-1);cout<<"得到操作符栈顶"<<x<<endl;return x;}char Gettop(OPND op_n){char x;if(op_n.top==op_n.base){exit(1);}x=*(op_n.top-1);cout<<"得到操作数栈顶"<<x<<endl;return x;}int In(char ch){if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#') {return 1;}else{return 0;}}char Precede(char x,char y){if(x=='+' || x=='-'){if(y=='+' || y=='-' || y==')' || y=='#'){return '>';}else{return '<';}}if(x=='*'||x=='/'){if(y=='('){return '<';}else{return '>';}}if(x=='('){if(y==')'){return '=';}else if(y=='+'||y=='-'||y=='*'||y=='/'||y=='(') {return '<';}}if(x==')'){if(y!='('){return '>';}}if(x=='#'){if(y=='#'){return '=';}else if(y!=')'){return '<';}}}char operate(char z,char x,char y) {if(x=='+'){return (z-'0') + (y-'0')+48;}if(x=='-'){return (z-'0') - (y-'0')+48;}if(x=='*'){return (z-'0')* (y-'0')+48;}if(x=='/'){return (z-'0')/ (y-'0')+48;}}*//*#include<iostream>using namespace std;int main(){char a[10];char *b[10];char **c[10];return 0;}*//*#include<iostream>using namespace std;char f(char x,char y){return (x-'0') * (y-'0')+48; }int main(){char a='3',b='5';char p=f(a,b);cout<<p<<endl;return 0;}*///数列出队/*#include<iostream>#include<stdlib.h>using namespace std; typedef struct Qnode{int num;struct Qnode *next;}Qnode,*Queueptr;typedef struct{Queueptr front;Queueptr rear;}LinkQueue;int InitQueue(LinkQueue &Q);void EnQueue(LinkQueue &Q,int x); int DeQueue(LinkQueue &Q,int p); int main(){LinkQueue Q;InitQueue(Q);int x,i,y,num=0,e;cout<<"请输入总人数:";cin>>x;for(i=1;i<=x;i++){EnQueue(Q,i);}cout<<"请输入第几个数淘汰:";cin>>y;while(1){for(i=0;i<y;i++){if(i!=y-1){e=DeQueue(Q,e);EnQueue(Q,e);}else{DeQueue(Q,e);num++;}}if(num==x-1){break;}}e=DeQueue(Q,e);cout<<"最后剩下的是："<<e<<endl;return 0;}int InitQueue(LinkQueue &Q){Q.front=new Qnode;Q.rear=Q.front;if(Q.front==NULL){exit(1);}Q.front->next=NULL;}void EnQueue(LinkQueue &Q,int x) {Qnode *p=new Qnode;if(!p){exit(1);}p->num=x;p->next=NULL;Q.rear->next=p;Q.rear=p;}int DeQueue(LinkQueue &Q,int e) {Qnode *p;if(Q.rear==Q.front){exit(0);}p=Q.front->next;e=p->num;Q.front->next=p->next;if(Q.rear==p){Q.front=Q.rear;}delete p;return e;}*//*二叉树#include<iostream>#include<stdlib.h>using namespace std;typedef struct BiTNode{char date;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;void CreateBiTree(BiTree &T);int Depth(BiTree T);int NodeCount(BiTree T);int LeavesNodeCount(BiTree T);int PreOrderTraverse(BiTree T);int InOrderTraverse(BiTree T);int PostOrderTraverse(BiTree T);int main(){BiTree T;CreateBiTree(T);cout<<"二叉树的深度为："<<Depth(T)<<endl;cout<<"二叉树中结点个数为："<<NodeCount(T)<<endl;cout<<"二叉树中叶子结点个数为："<<LeavesNodeCount(T)<<endl;cout<<"先序遍历：";PreOrderTraverse(T);cout<<"\n中序遍历：";InOrderTraverse(T);cout<<"\n后序遍历：";PostOrderTraverse(T);cout<<endl;return 0;}void CreateBiTree(BiTree &T) {cout<<"请为该节点赋值:";char ch;cin>>ch;if(ch=='#'){T=NULL;}else{T =new BiTNode;T->date=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}}int Depth(BiTree T){int m,n;if(T==NULL){return 0;}else{m=Depth(T->lchild);n=Depth(T->rchild);if(m>n){return m+1;}else{return n+1;}}}int NodeCount(BiTree T){if(T==NULL){return 0;}else{return NodeCount(T->lchild)+NodeCount(T->rchild)+1;。

《数据结构》实验代码实验一：针对链式或顺序存储的线性表实现指定的操作题1 问题描述：有两个指数递减的一元多项式，写一程序先求这两个多项式的和，再求它们的积。

基本要求：用带表头结点的单链表作为多项式的存储表示；要建立两个单链表；多项式相加就是要把一个单链表中的结点插入到另一个单链表中去，要注意插入、删除操作中指针的正确修改。

题2 问题描述：编号为1，2，···，n的n个人围坐在一圆桌旁，每人持有一个正整数的密码。

从第一个人开始报数，报到一个预先约定的正整数m时，停止报数，报m的人退席，下一个人又重新从1开始报数，依此重复，直至所有的人都退席。

编一程序输出他们退席的编号序列。

例如，设m=20，n=7，7个人的密码依次是3，1，7，2，4，8，4，则退席的人的编号依次为6，1，4，7，2，3，5。

基本要求：用不带表头结点的循环单链表表示围成圆圈的n个人；要求建立此循环单链表；某人离席相当于删除一个结点，要正确设置程序中循环终止的条件和删除结点时指针的修改变化。

//实验1.1代码#include<iostream>using namespace std;struct poNode{float coef;int expn;poNode *next;};class Polynomail{public:Polynomail(int m=0);~Polynomail();int Print();int PolynLength();Polynomail &AddPolyn(Polynomail &P2,Polynomail &P3);Polynomail &MultiplyPolyn(Polynomail &P2,Polynomail &P4);private:int InsertpoNode();poNode *first;};int main(){int m;cout<<"输入多项式P1项数"<<endl;cin>>m;Polynomail P1(m);if(P1.PolynLength()!=m){cout<<"error!"<<endl;return -1;}cout<<"输入多项式P2项数"<<endl;cin>>m;Polynomail P2(m);if(P2.PolynLength()!=m){cout<<"error!"<<endl;return -1;}cout<<"多项式P1:";P1.Print();cout<<"多项式P2:";P2.Print();Polynomail P3;P3=P1.AddPolyn(P2,P3);cout<<"P1+P2:";P3.Print();Polynomail P4;P4=P1.MultiplyPolyn(P2,P4);cout<<"P1*P2:";P4.Print();return 0;}int Polynomail::InsertpoNode() { if(first==NULL){first=new poNode;cout<<"输入系数和指数："<<endl;cin>>first->coef;cin>>first->expn;first->next=NULL;}else{poNode *p=new poNode;poNode *q=first;cout<<"输入系数和指数："<<endl; cin>>p->coef;cin>>p->expn;poNode *r;while(q->next!=NULL&&q->expn<p->expn) {r=q;q=q->next;}if(q==first&&q->next!=NULL){if(q->expn==p->expn){return -1;}p->next=q;first=p;}else if(q==first&&q->next==NULL){if(p->expn<q->expn){p->next=q;first=p;}else if(p->expn>q->expn){q->next=p;p->next=NULL;}else{return -1;}}else if(q->next==NULL&&q!=first&&p->expn>q->expn) {q->next=p;p->next=NULL;}else{if(q->expn==p->expn){return -1;}r->next=p;p->next=q;}}return 0;}Polynomail::Polynomail(int m){first=NULL;int i;for(i=0;i<m;i++){int r=InsertpoNode();if(r==-1) break;}}int Polynomail::Print(){poNode *p=first;cout<<"f(x)=";if(first==NULL) cout<<"NULL"<<endl;while(p!=NULL){cout<<p->coef<<"*x^"<<p->expn;if(p->next==NULL) cout<<endl;else cout<<"+";p=p->next;}return 0;}Polynomail::~Polynomail(){poNode *p=first;while(p!=NULL){p=p->next;delete first;first=p;}}int Polynomail::PolynLength(){int i=0;poNode *p=first;while(p!=NULL){p=p->next;i++;}return i;}Polynomail &Polynomail::AddPolyn(Polynomail &P2,Polynomail &P3) {poNode *p=first;poNode *q=P2.first;P3.first=new poNode;poNode *r=P3.first;while(p!=NULL&&q!=NULL){if(p->expn==q->expn){r->coef=p->coef+q->coef;r->expn=p->expn;p=p->next;q=q->next;}else if(p->expn<q->expn){r->coef=p->coef;r->expn=p->expn;p=p->next;}else{r->coef=q->coef;r->expn=q->expn;q=q->next;}if(p!=NULL||q!=NULL){r->next=new poNode;r=r->next;}else r->next=NULL;}while(p!=NULL||q!=NULL) {if(p!=NULL){r->coef=p->coef;r->expn=p->expn;p=p->next;}else{r->coef=q->coef;r->expn=q->expn;q=q->next;}if(p!=NULL||q!=NULL){r->next=new poNode;r=r->next;}else r->next=NULL;}return P3;}Polynomail &Polynomail::MultiplyPolyn(Polynomail &P2,Polynomail &P4){poNode *p=first;while(p!=NULL){Polynomail P3;poNode *q=P2.first;P3.first=new poNode;poNode *r=P3.first;r->coef=p->coef*q->coef;r->expn=p->expn+q->expn;q=q->next;while(q!=NULL){r->next=new poNode;r=r->next;r->coef=p->coef*q->coef;r->expn=p->expn+q->expn;q=q->next;}r->next=NULL;P4=P4.AddPolyn(P3,P4);p=p->next;}return P4;}//实验1.2代码#include<iostream>using namespace std;struct numNode{int key;int num;numNode *next;};int CreatCircleList(numNode *now,int length); int Loop(numNode *now,int m);int main(){int m;int n;numNode *now=new numNode;cout<<"请输入人数："<<endl;cin>>n;cout<<"请输入初始数m:"<<endl;cin>>m;CreatCircleList(now,n);Loop(now,m);return 0;}int CreatCircleList(numNode *now,int length){if(length<=0){cout<<"error!"<<endl;return -1;}now->num=1;cout<<"请输入编号为1的人拥有的密码。

1、队列#include<stdlib.h>#include<stdio.h>#define OVERFLOW -1#define OK 1#define ERROR 0#define MAXSIZE 100typedef struct{int *elem;//队列存储空间int front;int rear;}SqQueue;//判断选择是否正确int menu_select(){int sn;for(;;){scanf("%d",&sn);if(sn<1||sn>6)printf("\n\t输入错误，请重新输入\n");elsebreak;}return sn;}//参数(传出)SqQueue &Q,循环队列(空)int InitQueue(SqQueue &Q){Q.elem=(int *)malloc(MAXSIZE*sizeof(int));if(!Q.elem)exit(OVERFLOW);Q.front=Q.rear=-1;for(int i=0;i<MAXSIZE;i++)Q.elem[i]=-1;return OK;}//返回Q的元素个数int QueueLength(SqQueue Q){return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; }//显示队列的元素void Display(SqQueue Q){for(int i=0;i<=QueueLength(Q);i++)if(Q.elem[i]!=-1)printf("%d ",Q.elem[i]);printf("\n");}//入队int EnQueue(SqQueue &Q,int e){Q.rear=(Q.rear+1)%MAXSIZE;if(Q.rear==Q.front)return ERROR;Q.elem[Q.rear]=e;return OK;}//出队int DeQueue(SqQueue &Q,int &e){if(Q.front==Q.rear)return ERROR;e=Q.elem[Q.front+1];Q.elem[Q.front+1]=-1;Q.front=(Q.front+1)%MAXSIZE;return OK;}void main(){SqQueue Q;InitQueue(Q);int elem,e;printf("请输入队列元素(以0结束):\n");scanf("%d",&elem);while(elem!=0){EnQueue(Q,elem);scanf("%d",&elem);}printf("队列为：\n");Display(Q);printf("1.初始化一个队列;\n2.入队;\n3.出队;\n4.显示队列的所有元素;\n5.队列长度:\n6.结束;\n");while(1){switch(menu_select()){case 1:printf("请输入队列元素(以0结束):\n");scanf("%d",&elem);while(elem!=0){EnQueue(Q,elem);scanf("%d",&elem);}printf("队列为：\n");Display(Q);fflush(stdin);break;case 2:scanf("%d",&elem);EnQueue(Q,elem);printf("队列为：\n");Display(Q);fflush(stdin);break;case 3:DeQueue(Q,elem);printf("队列为：\n");Display(Q);break;case 4:printf("\n队列的所有元素:\n");Display(Q);break;case 5:printf("%d",QueueLength(Q));break;case 6:return;}}}2矩阵（加，乘，转置）#include <stdio.h>#define M 3void MatrixAdd(int m1[M][M],int m2[M][M],int result[M][M])//两个矩阵m1和m2相加,结果放到result{int i,j;for (i=0;i<M;i++){for(j=0;j<M;j++)result[i][j]=m1[i][j]+m2[i][j];}}void MatrixTrams(int m1[M][M],int result[M][M])//矩阵转置{int i,j;for (i=0;i<M;i++){for (j=0;j<M;j++)result[i][j]=m1[j][i];}}void MatrixMultiply(int m1[M][M],int m2[M][M],int result[M][M]){int i,j;for (i=0;i<M;i++){for (j=0;j<M;j++){result[i][j]=0;for (int k=0;k<M;k++)result[i][j]+=m1[i][k]*m2[k][j];}}}void Display(int result[M][M])//显示矩阵{int i,j;for (i=0;i<M;i++){for(j=0;j<M;j++)printf("%-5d",result[i][j]);printf("\n");}}void main(){int A[M][M],B[M][M];int i,j;printf("请输入第一个矩阵：\n");for(i=0;i<M;i++)for(j=0;j<M;j++)scanf("%d",&A[i][j]);printf("请输入第二个矩阵：\n");for(i=0;i<M;i++)for(j=0;j<M;j++)scanf("%d",&B[i][j]);int result[M][M];printf("\n 矩阵A:\n");Display(A);printf("\n 矩阵B:\n");Display(B);printf("\n请选择：\n1.矩阵相加：\n2.矩阵A转置：\n3.矩阵B转置：\n4.矩阵相乘：\n5.退出。

/*顺序表的操作#include<iostream>#include<stdlib.h>using namespace std;Release 13.12 rev 9501 (2013/12/25 19:25:45) gcc 4.7.1 Windows/unicode - 32 bit #define MAX_SIZE 100typedef struct{int *emel;int lenth;}Sq;void init(Sq &l);void create(Sq &l);void trval(Sq &l);void find_value(Sq &l);void find_position(Sq &l);void insert(Sq &l);void dele(Sq &l);int main(){Sq l;init(l);create(l);trval(l);find_value(l);find_position(l);insert(l);trval(l);dele(l);trval(l);return 0;}void init(Sq &l){l.emel =new int[MAX_SIZE];if(l.emel ==NULL){cout<<"\t申请空间失败！"<<endl;exit(1);}l.lenth=0;cout<<"\t成功申请空间！该顺序表的长度目前为:"<<l.lenth<<endl; }void create(Sq &l){cout<<"\t请输入你想输入元素的个数：";int x;cin>>x;if((x<1)&&(x>MAX_SIZE)){cout<<"\t你说输入的数不在范围里"<<endl;return;}int i;for(i=0;i<x;i++){cin>>l.emel[i];}l.lenth=x;cout<<"\t成功赋值！"<<endl;}void trval(Sq &l){int i;cout<<"l(";for(i=0;i<l.lenth;i++){cout<<l.emel[i]<<" ";}cout<<")"<<" 该顺序表现在的长度为："<<l.lenth<<endl;}void find_value(Sq &l){int x,t=0;cout<<"\t请输入你要查找的值：";cin>>x;int i;for(i=0;i<l.lenth;i++){if(l.emel[i]==x){t=1;cout<<"\t成功找到该元素，它是顺序表的第"<<i+1<<"个元素！"<<endl;}}if(t==0){cout<<"\t无该元素！"<<endl;}}void find_position(Sq &l){int x;cout<<"\t请输入你要查找的位置：";cin>>x;int i;if((x<1)||(x>l.lenth)){cout<<"\t输入的值不在范围内！"<<endl;return;}for(i=1;i<=l.lenth;i++){if(i==x){cout<<"\t成功找到该元素，该值是"<<l.emel[i-1]<<endl;}}}void insert(Sq &l){int i,x,y;cout<<"\t请输入你要插入的位置";cin>>x;cout<<"\t请输入你要插入的值";cin>>y;if((x<1)||(x>l.lenth)){cout<<"\t输入的值不在范围内！"<<endl;return;}if(x==l.lenth){l.emel[l.lenth]=y;l.lenth=l.lenth+1;return;}for(i=l.lenth;i>=x;i--){l.emel[i]=l.emel[i-1];}l.emel[x-1]=y;l.lenth=l.lenth+1;}void dele(Sq &l){int i,x;cout<<"\t请输入你要删除位置：";cin>>x;if((x<1)||(x>l.lenth)){cout<<"\t输入的值不在范围内！"<<endl;return;}for(i=x-1;i<=l.lenth;i++){l.emel[i]=l.emel[i+1];}l.lenth=l.lenth-1;}成功申请空间！该顺序表的长度目前为:0请输入你想输入元素的个数：3852成功赋值！l(8 5 2 ) 该顺序表现在的长度为：3请输入你要查找的值：5成功找到该元素，它是顺序表的第2个元素！请输入你要查找的位置：3成功找到该元素，该值是2请输入你要插入的位置3请输入你要插入的值10l(8 5 2 10 ) 该顺序表现在的长度为：4请输入你要删除位置：3l(8 5 10 ) 该顺序表现在的长度为：3--------------------------------Process exited with return value 0Press any key to continue . . .*//*#include<stdio.h>#include<stdlib.h>typedef struct Link{int num;struct Link *next;}L;L* creat(L* head){head=(L *)malloc(sizeof(L));if(head==NULL){printf("头节点申请失败！\n");exit(-1);}head->next=NULL;return head;}void insert(L* head){int x,i;printf("请输入你想输入数据的个数：");scanf("%d",&x);L *p,*q;p=head;for(i=0;i<x;i++){q=(L *)malloc(sizeof(L));if(q==NULL){printf("新点申请失败！\n");exit(-1);}printf("请输入值：");scanf("%d",&q->num);q->next=NULL;p->next=q;p=q;}}void print(L* head){L *p;p=head->next;while(p!=NULL){printf("值为：%d\n",p->num);p=p->next;}}int main(){L *head;head=creat(head);printf("成功创建头节点！！！\n");insert(head);printf("成功输入数据！！！\n");print(head);return 0;}*//*线性表的操作#include<stdio.h>#include<stdlib.h>typedef struct Link{int num;struct Link *next;}L;L* creat(L* head){head=(L *)malloc(sizeof(L));if(head==NULL){printf("头节点申请失败！\n");exit(-1);}head->next=NULL;return head;}void init(L* head){int x,i;printf("请输入你想输入数据的个数：");scanf("%d",&x);L *p,*q;p=head;for(i=0;i<x;i++){q=(L *)malloc(sizeof(L));if(q==NULL){printf("新点申请失败！\n");exit(-1);}printf("请输入值：");scanf("%d",&q->num);q->next=p->next;p->next=q;}}int print(L* head){L *p;int lenth=0;p=head->next;printf("\t\tL(");while(p!=NULL){lenth++;printf("%d ",p->num);p=p->next;}printf(")\n");return lenth;}int insert(L *head,int lenth){printf("\t\t请输入你要插入的元素的位置:");int in;scanf("%d",&in);if(in<1 || in>lenth){printf("\t\t输入值不在范围内！");return -1;}L *p,*q;p=head->next;q=(L *)malloc(sizeof(L));if(q==NULL){printf("新点申请失败！\n");return -1;}printf("\t\t请为新节点输入值：");scanf("%d",&q->num);int i=0;while(p!=NULL){i++;if(i==in-1){q->next=p->next;p->next=q;}p=p->next;}lenth++;return lenth;}int dele(L *head,int lenth){printf("\t\t请输入你要删除的元素的位置:");int out;scanf("%d",&out);if(out<1 || out>lenth){printf("\t\t输入值不在范围内！");return -1;}L *p,*q;p=head->next;q=head;int i=0;while(p!=NULL){i++;if(i==out){q->next=p->next;}q=p;p=p->next;}lenth--;return lenth;}void find(L *head,int lenth){printf("\t\t请输入你要查找的元素的位置:");int finder;scanf("%d",&finder);if(finder<1 || finder>lenth){printf("\t\t输入值不在范围内！");return ;}L *p;p=head->next;int i=0;while(p!=NULL){i++;if(i==finder){printf("\t\t你要找的该位置所对应的值为：%d\n",p->num);}p=p->next;}}int main(){L *head;head=creat(head);printf("成功创建头节点！！！\n");init(head);printf("成功输入数据！！！\n");int len;len=print(head);printf("\t\t该线性表的长度为:%d\n",len);len=insert(head,len);len=print(head);printf("\t\t插入后线性表的长度为:%d\n",len);len=dele(head,len);len=print(head);printf("\t\t删除后该线性表的长度为:%d\n",len);find(head,len);return 0;}*//*顺序表的合并#include<iostream>using namespace std;struct LA{int *pa;int lenth;};struct LB{int *pb;int lenth;};struct LC{int *pc;int lenth;};void mergelist(LA la,LB lb,LC &lc);int main(){int x,y;LA la;LB lb;cout<<"\t\t请给线性表LA和LB指定长度：";cin>>x>>y;la.pa =new int(sizeof(int)*x);lb.pb =new int(sizeof(int)*y);int i;for(i=0;i<x;i++){cout<<"请输入表LA的值:";cin>>la.pa[i];}cout<<endl;la.lenth=x;for(i=0;i<y;i++){cout<<"请输入表LB的值:";cin>>lb.pb[i];}lb.lenth=y;cout<<"LA(";for(i=0;i<x;i++){cout<<la.pa[i]<<" ";}cout<<")"<<endl;cout<<"LB(";for(i=0;i<y;i++){cout<<lb.pb[i]<<" ";}cout<<")"<<endl;LC lc;mergelist(la,lb,lc);return 0;}void mergelist(LA la,LB lb,LC &lc){lc.lenth=la.lenth+lb.lenth;lc.pc=new int(sizeof(int)*lc.lenth);int *pa=la.pa,*pb=lb.pb,*pc=lc.pc;int *pa_last=la.pa+la.lenth-1;int *pb_last=lb.pb+lb.lenth-1;while(pa<=pa_last && pb<=pb_last){if(*pa <= *pb){*pc++=*pa++;}else{*pc++=*pb++;}}while(pa<=pa_last){*pc++=*pa++;}while(pb<=pb_last){*pc++=*pb++;}cout<<"LC(";int i=0;for(i=0;i<lc.lenth;i++){cout<<lc.pc[i]<<" ";}cout<<")"<<endl;}*///栈/*#include<iostream>using namespace std;#include<stdlib.h>#define MAXSIZE 100typedef struct{int *base;int *top;int stacksize;}Sqstack;int Initstack(Sqstack &s);void Push(Sqstack &s,int e);void StackTraverse(Sqstack &s);void Gettop(Sqstack &s);void Pop(Sqstack &s);int main(){Sqstack s;Initstack(s);cout<<"\t\t初始化栈成功！"<<endl;Push(s,2);cout<<"\t\t2入栈成功！"<<endl;Push(s,4);cout<<"\t\t4入栈成功！"<<endl;Push(s,6);cout<<"\t\t6入栈成功！"<<endl;Push(s,8);cout<<"\t\t8入栈成功！"<<endl;cout<<"\n由栈底至栈顶的元素为：";StackTraverse(s);Gettop(s);Pop(s);Gettop(s);return 0;}int Initstack(Sqstack &s){s.base=new int[MAXSIZE];if(s.base==NULL){exit(1);}s.top=s.base;s.stacksize=MAXSIZE;}void Push(Sqstack &s,int e){if(s.top-s.base==s.stacksize){exit(1);}*s.top++=e;}void StackTraverse(Sqstack &s){int *p=s.base,i=0;while(p<s.top){i++;cout<<*p++<<" ";}cout<<"\t\t栈的长度是"<<i<<endl;}void Gettop(Sqstack &s){if(s.base==s.top){exit(1);}cout<<"栈顶元素是："<<*(s.top-1)<<endl; }void Pop(Sqstack &s){if(s.top==s.base){exit(1);}cout<<"出栈的第一个元素是:";cout<<*--s.top<<" "<<endl;}*///队列例题：/*#include<iostream>#include<stdlib.h>using namespace std;#define MAXQSIZE 100typedef struct{int *base;int front;int rear;}SqQueue;int InitQueue(SqQueue &q);int EnQueue(SqQueue &q,int x);int DeQueue(SqQueue &q);int main(){SqQueue q;InitQueue(q);EnQueue(q,1);EnQueue(q,3);EnQueue(q,5);EnQueue(q,7);DeQueue(q);DeQueue(q);DeQueue(q);DeQueue(q);return 0;}int InitQueue(SqQueue &q){q.base=new int[MAXQSIZE];if(q.base==NULL){exit(1);}q.front=0;q.rear=0;return 0;}int EnQueue(SqQueue &q,int x){if((q.rear+1)%MAXQSIZE==q.front){exit(0);}q.base[q.rear]=x;q.rear=(q.rear+1)%MAXQSIZE;return 0;}int DeQueue(SqQueue &q){if(q.front==q.rear){exit(0);}int x=q.base[q.front];q.front=(q.front+1)%MAXQSIZE;cout<<x<<endl;}*//*#include<iostream>#include<stdlib.h>using namespace std;typedef struct Qnode{int date;struct Qnode *next;}Qnode,*Queueptr;typedef struct{Queueptr front; //队头指针Queueptr rear; //队尾指针}LinkQueue;int InitQueue(LinkQueue &Q);void EnQueue(LinkQueue &Q,int e);void TrvalQueue(LinkQueue Q);void DeQueue(LinkQueue &Q);int main(){LinkQueue Q;InitQueue(Q);EnQueue(Q,1);cout<<"\t元素1入队成功！"<<endl;EnQueue(Q,3);cout<<"\t元素3入队成功！"<<endl;EnQueue(Q,5);cout<<"\t元素5入队成功！"<<endl;EnQueue(Q,7);cout<<"\t元素7入队成功！"<<endl;cout<<"\t队列的元素分别是："<<endl;TrvalQueue(Q);cout<<"\t第一个出队的元素是："<<endl;DeQueue(Q);cout<<"\n\t第一个元素出队完成之后队列中从队头至队尾的元素为：";TrvalQueue(Q);return 0;}int InitQueue(LinkQueue &Q){Q.rear=new Qnode;Q.front=Q.rear;if(Q.front==NULL){exit(0);}Q.front->next=NULL;return 0;}void EnQueue(LinkQueue &Q,int e){Qnode *p=new Qnode;if(!p){exit(1);}p->date=e;p->next=NULL;Q.rear->next=p; //连接Q.rear=p; //修改队尾指针}void TrvalQueue(LinkQueue Q){Qnode *p=Q.front->next;//队头元素while(Q.front!=Q.rear){cout <<p->date<<" ";Q.front=p;p=p->next;}cout<<endl;}void DeQueue(LinkQueue &Q){if(Q.front==Q.rear){return;}Qnode *p=Q.front->next;cout<<"\t"<<p->date<<endl;Q.front->next=p->next;if(Q.rear==p){Q.rear=Q.front;delete p;}}*//*//表达式求值#include<iostream>#include<stdlib.h>#include<stdio.h>using namespace std;#define MAXSIZE 100typedef struct{char *base;char *top;char num;}OPND; //数据栈typedef struct{char *base;char *top;char c;}OPTR; //符号栈int Initstack(OPND &op_n,OPTR &op_t);void Pushstack(OPND &op_n,char ch);void Pushstack(OPTR &op_t,char ch);char Popstack(OPND &op_n,char ch);char Popstack(OPTR &op_t,char ch);char Gettop(OPTR op_t);char Gettop(OPND op_n);int In(char ch);char Precede(char x,char y);char operate(char z,char x,char y);int main(){OPND op_n;OPTR op_t;Initstack(op_n,op_t);Pushstack(op_t,'#');char ch;char p;cin>>ch;while(ch!='#' || Gettop(op_t)!='#'){if(!In(ch)){Pushstack(op_n,ch);cin>>ch;}else{switch( Precede(Gettop(op_t),ch) ){case '<':Pushstack(op_t,ch);cin>>ch;break;case '>':char x,y,z;x=Popstack(op_t,x);y=Popstack(op_n,y);z=Popstack(op_n,z);Pushstack(op_n,operate(z,x,y));break;case '=':p=Popstack(op_t,p);cin>>ch;break;}}}cout<<"\t表达式结果是："<<Gettop(op_n)<<endl;return 0;}int Initstack(OPND &op_n,OPTR &op_t){op_n.base=new char[MAXSIZE];op_t.base=new char[MAXSIZE];if((op_n.base==NULL) || (op_t.base==NULL)){exit(1);}op_n.top=op_n.base;op_t.top=op_t.base;op_n.num=MAXSIZE;op_t.c=MAXSIZE;return 0;}void Pushstack(OPND &op_n,char ch){if(op_n.top-op_n.base==op_n.num){return;}*op_n.top++=ch;cout<<ch<<" 入数字栈"<<endl;}void Pushstack(OPTR &op_t,char ch){if(op_t.top-op_t.base==op_t.c){return;}*op_t.top++=ch;cout<<ch<<" 入操作符"<<endl;}char Popstack(OPND &op_n,char ch)if(op_n.top==op_n.base){exit(1);}ch=*--op_n.top;cout<<ch<<" 出数字栈"<<endl;return ch;}char Popstack(OPTR &op_t,char ch){if(op_t.top==op_t.base){exit(1);}ch=*--op_t.top;cout<<ch<<" 出字符栈"<<endl;return ch;}char Gettop(OPTR op_t){char x;if(op_t.top==op_t.base){exit(1);}x=*(op_t.top-1);cout<<"得到操作符栈顶"<<x<<endl;return x;}char Gettop(OPND op_n){char x;if(op_n.top==op_n.base){exit(1);}x=*(op_n.top-1);cout<<"得到操作数栈顶"<<x<<endl;return x;}int In(char ch)if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#') {return 1;}else{return 0;}}char Precede(char x,char y){if(x=='+' || x=='-'){if(y=='+' || y=='-' || y==')' || y=='#'){return '>';}else{return '<';}}if(x=='*'||x=='/'){if(y=='('){return '<';}else{return '>';}}if(x=='('){if(y==')'){return '=';}else if(y=='+'||y=='-'||y=='*'||y=='/'||y=='('){return '<';}}if(x==')'){if(y!='('){return '>';}}if(x=='#'){if(y=='#'){return '=';}else if(y!=')'){return '<';}}}char operate(char z,char x,char y) {if(x=='+'){return (z-'0') + (y-'0')+48;}if(x=='-'){return (z-'0') - (y-'0')+48;}if(x=='*'){return (z-'0')* (y-'0')+48;}if(x=='/'){return (z-'0')/ (y-'0')+48;}}*//*#include<iostream>using namespace std;int main(){char a[10];char *b[10];char **c[10];return 0;}*//*#include<iostream>using namespace std;char f(char x,char y){return (x-'0') * (y-'0')+48;}int main(){char a='3',b='5';char p=f(a,b);cout<<p<<endl;return 0;}*///数列出队/*#include<iostream>#include<stdlib.h>using namespace std;typedef struct Qnode{int num;struct Qnode *next;}Qnode,*Queueptr;typedef struct{Queueptr front;Queueptr rear;}LinkQueue;int InitQueue(LinkQueue &Q);void EnQueue(LinkQueue &Q,int x); int DeQueue(LinkQueue &Q,int p); int main(){LinkQueue Q;InitQueue(Q);int x,i,y,num=0,e;cout<<"请输入总人数:";cin>>x;for(i=1;i<=x;i++){EnQueue(Q,i);}cout<<"请输入第几个数淘汰:";cin>>y;{for(i=0;i<y;i++){if(i!=y-1){e=DeQueue(Q,e);EnQueue(Q,e);}else{DeQueue(Q,e);num++;}}if(num==x-1){break;}}e=DeQueue(Q,e);cout<<"最后剩下的是："<<e<<endl;return 0;}int InitQueue(LinkQueue &Q){Q.front=new Qnode;Q.rear=Q.front;if(Q.front==NULL){exit(1);}Q.front->next=NULL;}void EnQueue(LinkQueue &Q,int x){Qnode *p=new Qnode;if(!p){exit(1);}p->num=x;p->next=NULL;Q.rear->next=p;}int DeQueue(LinkQueue &Q,int e) {Qnode *p;if(Q.rear==Q.front){exit(0);}p=Q.front->next;e=p->num;Q.front->next=p->next;if(Q.rear==p){Q.front=Q.rear;}delete p;return e;}*//*二叉树#include<iostream>#include<stdlib.h>using namespace std;typedef struct BiTNode{char date;struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;void CreateBiTree(BiTree &T);int Depth(BiTree T);int NodeCount(BiTree T);int LeavesNodeCount(BiTree T);int PreOrderTraverse(BiTree T);int InOrderTraverse(BiTree T);int PostOrderTraverse(BiTree T); int main(){BiTree T;CreateBiTree(T);cout<<"二叉树的深度为："<<Depth(T)<<endl;cout<<"二叉树中结点个数为："<<NodeCount(T)<<endl;cout<<"二叉树中叶子结点个数为："<<LeavesNodeCount(T)<<endl;cout<<"先序遍历：";PreOrderTraverse(T);cout<<"\n中序遍历：";InOrderTraverse(T);cout<<"\n后序遍历：";PostOrderTraverse(T);cout<<endl;return 0;}void CreateBiTree(BiTree &T){cout<<"请为该节点赋值:";char ch;cin>>ch;if(ch=='#'){T=NULL;}else{T =new BiTNode;T->date=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}}int Depth(BiTree T){int m,n;if(T==NULL){return 0;}else{m=Depth(T->lchild);n=Depth(T->rchild);if(m>n){return m+1;}else{return n+1;}}}int NodeCount(BiTree T){if(T==NULL){return 0;}else{return NodeCount(T->lchild)+NodeCount(T->rchild)+1;}}int LeavesNodeCount(BiTree T){if(T==NULL){return 0;}else if(T->lchild==NULL && T->rchild==NULL){return 1;}else{return LeavesNodeCount(T->lchild)+LeavesNodeCount(T->rchild);}}int PreOrderTraverse(BiTree T){if(T!=NULL){cout<<T->date;PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}int InOrderTraverse(BiTree T){if(T!=NULL){InOrderTraverse(T->lchild);cout<<T->date;InOrderTraverse(T->rchild);}}int PostOrderTraverse(BiTree T){if(T!=NULL){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);cout<<T->date;}}请为该节点赋值:-请为该节点赋值:+请为该节点赋值:a请为该节点赋值:#请为该节点赋值:#请为该节点赋值:*请为该节点赋值:b请为该节点赋值:#请为该节点赋值:#请为该节点赋值:-请为该节点赋值:c请为该节点赋值:#请为该节点赋值:#请为该节点赋值:d请为该节点赋值:#请为该节点赋值:#请为该节点赋值:/请为该节点赋值:e请为该节点赋值:#请为该节点赋值:#请为该节点赋值:f请为该节点赋值:#请为该节点赋值:#二叉树的深度为：5二叉树中结点个数为：11二叉树中叶子结点个数为：6先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d-e/f后序遍历：abcd-*+ef/-Process returned 0 (0x0) execution time : 76.214 s Press any key to continue.*//*#include<iostream>#include<stdlib.h>#include<string.h>using namespace std;typedef struct{int weiget;int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef char** HuffmanCode;void creat(HuffmanTree &HT,int n);void Select(HuffmanTree HT,int k,int &min1,int &min2); void creatcode(HuffmanTree HT,HuffmanCode &HC,int n); int min(HuffmanTree HT,int k);int main(){int n;cout<<"请输入叶子节点的个数:";cin>>n;HuffmanTree HT;creat(HT,n);HuffmanCode HC;creatcode(HT,HC,n);return 0;}void creat(HuffmanTree &HT,int n){if(n<1){exit(1);}int m=2*n-1,i;HT=new HTNode[m+1];for( i=1;i<=m;i++){HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(i=1;i<=n;i++){cout<<"请输入权值:";cin>>HT[i].weiget;}int s1,s2;for(i=n+1;i<=m;i++) //通过n-1次选择来合并创建{Select(HT,i-1,s1,s2);HT[s1].parent=i; //赋值，作为删除的标记HT[s2].parent=i;cout<<"s1:"<<s1<<" s2:"<<s2<<endl;HT[i].lchild=s1; //生成新节点HT[i].rchild=s2;HT[i].weiget=HT[s1].weiget+HT[s2].weiget;}}void Select(HuffmanTree HT,int k,int &min1,int &min2){min1=min(HT,k);min2=min(HT,k);}int min(HuffmanTree HT,int k){int i=0;int min;//存放weight最小且parent为-1的元素的序号int min_wei;//存放权值while(HT[i].parent!=0){i++;}min_wei=HT[i].weiget;min=i;for(;i<=k;i++){if(HT[i].weiget<min_wei && HT[i].parent==0){min_wei=HT[i].weiget;min=i;}}HT[min].parent=1;return min;}void creatcode(HuffmanTree HT,HuffmanCode &HC,int n){HC =new char *[n+1];char *cd=new char[n];cd[n-1]='\0';int i,start;//start指向最后，即编码结束符的位置int current,father;for(i=1;i<=n;i++){start=n-1;current=i;father=HT[i].parent;while(father!=0){--start;if(HT[father].lchild==current){cd[start]='0';}else{cd[start]='1';}current=father;father=HT[father].parent;}HC[i]=new char[n-start];strcpy(HC[i],&cd[start]);cout<<HT[i].weiget<<"对应的编码是："<<HC[i]<<endl;}delete cd;}请输入叶子节点的个数:5请输入权值:1请输入权值:2请输入权值:3请输入权值:4请输入权值:5s1:1 s2:2s1:3 s2:6s1:4 s2:5s1:7 s2:81对应的编码是：0102对应的编码是：0113对应的编码是：004对应的编码是：105对应的编码是：11Process returned 0 (0x0) execution time : 4.003 s Press any key to continue.*///折半查找#include<iostream>#include<stdio.h>using namespace std;#define ENDFLAG 10000typedef int KeyType;typedef char* InfoType;typedef struct{KeyType key;InfoType otherinfo;}ElemType;typedef struct{ElemType *R;int length;}SSTable;void CreateSTable(SSTable &ST,int n){int i;ST.R=new ElemType[n+1];for(i=1;i<=n;i++){cout<<"请输入"<<i<<"个测试数据：";cin>>ST.R[i].key;}ST.length=n;}int Search_Bin1(SSTable ST,KeyType key){int low,high,mid;low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(key==ST.R[mid].key){return mid;}else if(key<ST.R[mid].key){high=mid-1;}else{low=mid+1;}}return 0;}int Search_Bin2(SSTable ST,int low,int high,KeyType key) {int mid;if(low>high){return 0;}mid=(low+high)/2;printf("%d+++++",key==ST.R[mid].key);if(key==ST.R[mid].key){return mid;}else if(key<ST.R[mid].key){return Search_Bin2(ST,low,mid-1,key);}else{return Search_Bin2(ST,mid+1,high,key);}}int main(){int n;KeyType key;SSTable ST;cout<<"请输入静态查找表长：";cin>>n;CreateSTable(ST,n);cout<<"请输入待查记录的关键字：";cin>>key;cout<<"Search_Bin1算法计算的位置为："<<Search_Bin1(ST,key)<<endl;cout<<"Search_Bin2算法计算的位置为："<<Search_Bin2(ST,1,ST.length,key)<<endl;return 0;}/*请输入静态查找表长：5请输入1个测试数据：1请输入2个测试数据：2请输入3个测试数据：3请输入4个测试数据：4请输入5个测试数据：5请输入待查记录的关键字：3Search_Bin1算法计算的位置为：3Search_Bin2算法计算的位置为：3Process returned 0 (0x0) execution time : 8.620 sPress any key to continue.*//*#include<iostream>using namespace std;typedef struct{int key;}ElemType;typedef struct BSTNode{ElemType date;struct BSTNode *lchild,*rchild;}BSTNode,*BSTree;void Create(BSTree &T);void Insert(BSTree &T,ElemType e);int InOrderTraverse(BSTree T);int main(){BSTree T;Create(T);InOrderTraverse(T);cout<<"\n中序遍历：";return 0;}void Create(BSTree &T){T=NULL;ElemType e;cout<<"请为节点赋值:(0为结束条件)";cin>>e.key;while(e.key!=0){Insert(T,e);cout<<"请为节点赋值:(0为结束条件)";cin>>e.key;}}void Insert(BSTree &T,ElemType e){if(!T){BSTree S;S=new BSTNode;S->date=e;S->lchild=NULL;S->rchild=NULL;T=S;}else if(e.key<T->date.key){Insert(T->lchild,e);}else{Insert(T->rchild,e);}}int InOrderTraverse(BSTree T){if(T!=NULL){InOrderTraverse(T->lchild);cout<<T->date.key<<" ";InOrderTraverse(T->rchild);}return 0;}请为节点赋值:(0为结束条件)12请为节点赋值:(0为结束条件)7请为节点赋值:(0为结束条件)17请为节点赋值:(0为结束条件)11请为节点赋值:(0为结束条件)16请为节点赋值:(0为结束条件)2请为节点赋值:(0为结束条件)13请为节点赋值:(0为结束条件)9请为节点赋值:(0为结束条件)21请为节点赋值:(0为结束条件)4请为节点赋值:(0为结束条件)02 4 7 9 11 12 13 16 17 21中序遍历：Process returned 0 (0x0) execution time : 23.808 s Press any key to continue.*/。

实验1 求两个多项式的相加运算（线性表）编写一个程序用单链表存储多项式，并实现两个多项式相加的函数。

/*文件名:实验1.cpp*/#include <stdio.h>#include <malloc.h>#define MAX 20 /*多项式最多项数*/typedef struct /*定义存放多项式的数组类型*/{float coef; /*系数*/int exp; /*指数*/} PolyArray[MAX];typedef struct pnode /*定义单链表结点类型*/{float coef; /*系数*/int exp; /*指数*/struct pnode *next;} PolyNode;void DispPoly(PolyNode *L) /*输出多项式*/{PolyNode *p=L->next;while (p!=NULL){printf("%gX^%d ",p->coef,p->exp);p=p->next;}printf("\n");}void CreateListR(PolyNode *&L,PolyArray a,int n) /*尾插法建表*/{PolyNode *s,*r;int i;L=(PolyNode *)malloc(sizeof(PolyNode)); /*创建头结点*/L->next=NULL;r=L; /*r始终指向终端结点,开始时指向头结点*/ for (i=0;i<n;i++){s=(PolyNode *)malloc(sizeof(PolyNode));/*创建新结点*/s->coef=a[i].coef;s->exp=a[i].exp;r->next=s; /*将*s插入*r之后*/r=s;}r->next=NULL; /*终端结点next域置为NULL*/}void Sort(PolyNode *&head) /*按exp域递减排序*/{PolyNode *p=head->next,*q,*r;if (p!=NULL) /*若原单链表中有一个或以上的数据结点*/ {r=p->next; /*r保存*p结点后继结点的指针*/p->next=NULL; /*构造只含一个数据结点的有序表*/p=r;while (p!=NULL){r=p->next; /*r保存*p结点后继结点的指针*/q=head;while (q->next!=NULL && q->next->exp>p->exp)q=q->next; /*在有序表中找插入*p的前驱结点*q*/ p->next=q->next; /*将*p插入到*q之后*/q->next=p;p=r;}}}void Add(PolyNode *ha,PolyNode *hb,PolyNode *&hc) /*求两有序集合的并*/ {PolyNode *pa=ha->next,*pb=hb->next,*s,*tc;float c;hc=(PolyNode *)malloc(sizeof(PolyNode)); /*创建头结点*/tc=hc;while (pa!=NULL && pb!=NULL){if (pa->exp>pb->exp){s=(PolyNode *)malloc(sizeof(PolyNode)); /*复制结点*/s->exp=pa->exp;s->coef=pa->coef;tc->next=s;tc=s;pa=pa->next;}else if (pa->exp<pb->exp){s=(PolyNode *)malloc(sizeof(PolyNode)); /*复制结点*/s->exp=pb->exp;s->coef=pb->coef;tc->next=s;tc=s;pb=pb->next;}else /*pa->exp=pb->exp*/{c=pa->coef+pb->coef;if (c!=0) /*系数之和不为0时创建新结点*/{s=(PolyNode *)malloc(sizeof(PolyNode)); /*复制结点*/s->exp=pa->exp;s->coef=c;tc->next=s;tc=s;}pa=pa->next;pb=pb->next;}}if (pb!=NULL) pa=pb; /*复制余下的结点*/while (pa!=NULL){s=(PolyNode *)malloc(sizeof(PolyNode)); /*复制结点*/s->exp=pa->exp;s->coef=pa->coef;tc->next=s;tc=s;pa=pa->next;}tc->next=NULL;}void main(){PolyNode *ha,*hb,*hc;PolyArray a={{1.2,0},{2.5,1},{3.2,3},{-2.5,5}};PolyArray b={{-1.2,0},{2.5,1},{3.2,3},{2.5,5},{5.4,10}};CreateListR(ha,a,4);CreateListR(hb,b,5);printf("原多项式A: ");DispPoly(ha);printf("原多项式B: ");DispPoly(hb);Sort(ha);Sort(hb);printf("有序多项式A: ");DispPoly(ha);printf("有序多项式B: ");DispPoly(hb);Add(ha,hb,hc);printf("多项式相加: ");DispPoly(hc);}实验2 求解迷宫问题的所有路径 及最短路径程序（堆栈） 改进教材中3.2.4节中的求解迷宫问题程序，要求输出如图所示的迷宫的所有路径，并求出最短路径成都及最短路径。

单链表的操作#include "myhead.h"#include <iostream.h>typedef struct LNode {ElemType data; // 数据域struct LNode *next; // 后继指针} LNode, *LinkList;Status GetElem_L(LinkList &L, int i, ElemType &e) {// L为带头结点的单链表的头指针，e为返回值、int j;struct LNode *p;p = L->next; j=1; // p指向第一个结点while (p && j<i+1) {p = p->next; j++;} // 顺链后移,j计数if (!p || j>i+1) return ERROR; // 第i元素不存在e = p->data; // 取第i元素值return OK;} // GetElem_LStatus ListInsert_L(LinkList &L, int i, ElemType e) {// 在带头结点的单链表L中第i个位置之前插入元素e, 1≤i≤n+1struct LNode *p , *s; int j = 0;p = L;while (p && j<i-1) {p = p->next; j++;} // 寻找i-1结点if (!p || j>i-1) return ERROR;s = (LinkList) malloc(sizeof(LNode)); // 生成新结点s->data = e;s->next = p->next;p->next = s; // 插入L中return OK;} // ListInsert_Lvoid Listshow(LinkList &L){struct LNode *p; p=L->next;while(p){cout<<p->data<<" ";p=p->next;}cout<<endl;}void create(LinkList &L,int n,int a[])// 逆序输入n 个数据元素，建立带头结点的单链表{cout<<"请输入单链表的"<< n <<"个元素："<<endl;int i;struct LNode *p;L = (LinkList) malloc (sizeof (LNode));L->next = NULL; // 先建立一个带头结点的单链表for (i = n; i > 0; --i) {p = (LinkList) malloc (sizeof (LNode));cin>>p->data; // 输入元素值p->next = L->next; L->next = p; // 插入}cout<< endl;}Status ListDelete_L(LinkList &L, int i, ElemType &e) {// 在带头结点的单链表L中，删除第i个位置的元素, 1≤i≤n struct LNode *p,*q; int j;p = L; j = 0;while (p->next && j<i-1) {p = p->next; j++;} // 寻找i-1结点if (!p->next || j>i-1) return ERROR;q = p->next; p->next = q->next; // 删除i结点e = q->data; free(q); // 取值并释放结点return OK;} // ListDelete_Lvoid Listdestroy(LinkList &L) //销毁L，保留头结点{// 将单链表重新置为一个空表struct LNode *p;while (L->next) {p=L->next; L->next=p->next;free(p);}}void mergelist(LinkList &la,LinkList &lb,LinkList &lc)//将有序链表la和lb合并为lc，lc的头结点借用原来la的头结点，lb的头结点销毁{struct LNode *pa,*pb,*pc;pa=la->next; pb=lb->next; lc=pc=la;while (pa&&pb) {if(pa->data<=pb->data) {pc=pa;pa=pa->next; }else {pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;free(lb);}void main(){LinkList mylist,listb,listc;ElemType e;int a[]={1,12,23,34,45,56,67,78,89,90};int b[]={-6,6,16,26,36,46,96};create(mylist,10,a);create(listb,7,b);GetElem_L(mylist,5,e);cout<<"单链表的第5个元素是："<<e<<endl;cout<<"单链表的所有元素是：";Listshow(mylist);ListInsert_L(mylist,7,60);cout<<"插入第7个元素后单链表中的所有元素是：";Listshow(mylist);ListDelete_L(mylist,5,e);cout<<"删除了第五个元素后的单链表中的所有元素是：";Listshow(mylist);cout<<"删除的第五个元素是：";cout<<e<<endl;cout<<"listb中的元素有：";Listshow(listb);mergelist(mylist,listb,listc);cout<<"合并之后listc中的元素有：";Listshow(listc);Listdestroy(mylist);cout<<"销毁后单链表的元素是：";Listshow(mylist)；}串实验1.采用定长顺序显示表示串长的结构来存储串(结构定义见课件第15张幻灯片)2.实现BF算法(即朴素算法),BF函数头如下:(参见课件第21张幻灯片)int Index_BF(SString S, SString T) {}// 返回子串T在主串S中第0个字符之后的位置。

数据结构实验源代码【附】数据结构实验源代码范本一、实验背景与目的1.1 实验背景在计算机科学中，数据结构是指数据元素之间的关系，以及为操作这些数据元素所提供的方法。

数据结构对于程序的设计和性能优化具有重要影响。

1.2 实验目的本实验旨在通过编写和实现不同的数据结构，加深学生对数据结构的理解，掌握基本的数据结构操作方法。

二、实验内容2.1 线性表2.1.1 顺序表2.1.1.1 初始化顺序表2.1.1.2 插入元素到顺序表2.1.1.3 删除顺序表中的元素2.1.1.4 遍历顺序表2.1.1.5 查找指定元素在顺序表中的位置2.1.2 链表2.1.2.1 初始化链表2.1.2.2 插入元素到链表2.1.2.3 删除链表中的元素2.1.2.4 遍历链表2.1.2.5 查找指定元素在链表中的位置2.2 栈2.2.1 初始化栈2.2.2 进栈操作2.2.3 出栈操作2.2.4 获取栈顶元素2.2.5 判断栈是否为空2.3 队列2.3.1 初始化队列2.3.2 入队操作2.3.3 出队操作2.3.4 获取队首元素2.3.5 判断队列是否为空三、实验步骤3.1 线性表实现在实现顺序表和链表时，首先需要定义数据结构和所需的操作函数。

然后进行初始化、添加元素、删除元素等操作。

最后进行遍历和查找操作，并检验实验结果是否符合预期。

3.2 栈实现栈的实现过程与线性表类似，需要定义栈的数据结构和所需的函数，然后进行初始化、进栈、出栈等操作。

3.3 队列实现队列的实现也与线性表类似，需要定义队列的数据结构和函数，进行初始化、入队、出队等操作。

四、数据结构实验源代码以下是实验代码的源代码范本，包括线性表、栈和队列的实现。

（代码略，如需获取，请查看附件）五、附件本文档附带的附件为数据结构实验源代码。

六、法律名词及注释6.1 数据结构：计算机科学中，数据结构是指数据元素之间的关系，以及为操作这些数据元素所提供的方法。

6.2 顺序表：一种物理上相邻的存储结构，元素按照顺序依次存放。

1.邻接矩阵作为存储结构：#include <stdio.h>#include <stdlib.h>#define MaxVertexNum 100typedef struct{char verxs[MaxVertexNum];int edges[MaxV ertexNum][MaxVertexNum];int n,e;}MGraph;void creatMGraph(MGraph *G){int i,j,k;char a;printf("Input VertexNum(n)andEdgesNum(e):");scanf("%d,%d",&G->n,&G->e);scanf("%c",&a);printf("Input Vertex string");for(i=0;i<G->n;i++){scanf("%c",&a);G->verxs[i]=a;}for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->edges[i][j]=0;printf("Input edges,Creat Adjacency Matrix\n");for(k=0;k<G->e;k++){scanf("%d%d",&i,&j);G->edges[i][j]=1;G->edges[j][i]=1;}}typedef enum{FALSE,TRUE}Boolean;Boolean visited[MaxVertexNum];void DFSM(MGraph*G,int i){int j;printf("%c",G->verxs[i]);visited[i]=TRUE;for(j=0;j<G->n;j++)if(G->edges[i][j]==1&&!visited[j])DFSM(G,j);}void DFS(MGraph*G){int i;for(i=0;i<G->n;i++)visited[i]=FALSE;for(i=0;i<G->n;i++)if(!visited[i])DFSM(G,i);}void BFS(MGraph*G,int k){int i,j,f=0,r=0;int cq[MaxVertexNum];for(i=0;i<G->n;i++)visited[i]=FALSE;for(i=0;i<G->n;i++)cq[i]=-1;printf("%c",G->verxs[k]);visited[k]=TRUE;cq[r]=k;while(cq[f]!=-1){ i=cq[f];f=f+1;for(j=0;j<G->n;j++)if(G->edges[i][j]==1&&!visited[j]){printf("%c",G->verxs[j]);visited[j]=TRUE;r=r+1;cq[r]=j;}}}void main(){int i;MGraph*G;G=(MGraph*)malloc(sizeof(MGraph));creatMGraph(G);printf("Print Graph DFS:");DFS(G);printf("\n");printf("Print Graph BFS:");BFS(G,3);printf("\n");}2.邻接链表作为存储结构：#include"stdio.h"#include"stdlib.h"#define MaxVertexNum 50 /*定义最大顶点数*/typedef struct node{ /*边表结点*/int adjvex; /*邻接点域*/struct node *next; /*链域*/}EdgeNode;typedef struct vnode{ /*顶点表结点*/char vertex; /*顶点域*/EdgeNode *firstedge; /*边表头指针*/}VertexNode;typedef VertexNode AdjList[MaxVertexNum]; /*AdjList是邻接表类型*/ typedef struct {AdjList adjlist; /*邻接表*/int n,e; /*图中当前顶点数和边数*/} ALGraph; /*图类型*//* 建立图的邻接表*/void CreatALGraph(ALGraph *G){int i,j,k;char a;EdgeNode *s; /*定义边表结点*/printf("Input VertexNum(n)andEdgesNum(e): ");scanf("%d,%d",&G->n,&G->e); /*读入顶点数和边数*/scanf("%c",&a);printf("Input Vertex string:");for(i=0;i<G->n;i++) /*建立边表*/{scanf("%c",&a);G->adjlist[i].vertex=a; /*读入顶点信息*/G->adjlist[i].firstedge=NULL; /*边表置为空表*/}printf("Input edges,Creat Adjacency Matrix\n");for(k=0;k<G->e;k++) { /*建立边表*/scanf("%d%d",&i,&j); /*读入边（Vi，Vj）的顶点对序号*/s=(EdgeNode *)malloc(sizeof(EdgeNode)); /*/生成边表结点*/s->adjvex=j; /*邻接点序号为j*/s->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s; /*将新结点*S插入顶点Vi的边表头部*/s=(EdgeNode *)malloc(sizeof(EdgeNode));s->adjvex=i; /*邻接点序号为i*/s->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=s; /*将新结点*S插入顶点Vj的边表头部*/}}/* 定义标志向量，为全局变量*/typedef enum{FALSE,TRUE} Boolean;Boolean visited[MaxVertexNum];/* DFS：深度优先遍历的递归算法*/void DFSM(ALGraph *G,int i){ /*以Vi为出发点对邻接链表表示的图G进行DFS搜索*/ EdgeNode *p;printf("%c ",G->adjlist[i].vertex); /*访问顶点Vi*/visited[i]=TRUE; /*标记Vi已访问*/p=G->adjlist[i].firstedge; /*取Vi边表的头指针*/while(p) { /*依次搜索Vi的邻接点Vj，这里j=p->adjvex*/if(! visited[p->adjvex]) /*若Vj尚未被访问*/DFSM(G,p->adjvex); /*则以Vj为出发点向纵深搜索*/ p=p->next; /*找Vi的下一个邻接点*/}}void DFS(ALGraph *G){int i;for(i=0;i<G->n;i++)visited[i]=FALSE; /*标志向量初始化*/for(i=0;i<G->n;i++)if(!visited[i]) /*Vi未访问过*/DFSM(G,i); /*以Vi为源点开始DFS搜索*/}/* BFS：广度优先遍历*/void BFS(ALGraph *G,int k){ /*以Vk为源点对用邻接链表表示的图G进行广度优先搜索*/int i,f=0,r=0;EdgeNode *p;int cq[MaxVertexNum]; /*定义FIFO队列*/for(i=0;i<G->n;i++)visited[i]=FALSE; /*标志向量初始化*/for(i=0;i<=G->n;i++)cq[i]=-1; /*初始化标志向量*/printf("%c ",G->adjlist[k].vertex); /*访问源点Vk*/visited[k]=TRUE;cq[r]=k; /*Vk已访问，将其入队。