数据结构上机实验源文件

《数据结构》实验报告一题目：快速排序班级：学号：姓名：日期：程序名：一、上机实验的问题和要求：一趟快速排序示例，关键字序列：{52, 49, 80, 36, 14, 58, 61, 97, 23, 75}二、程序设计的基本思想，原理和算法描述：基本思想快速排序是通过比较关键字，以某个记录为界（称为支点记录），将待排序列分成两个部分。

其中一部分所有记录的关键字大于或等于支点记录的关键字，另一部分所有关键字小于支点记录的关键字。

将待排序列按关键字以支点记录分成两部分的过程，称为一次划分，或一趟快速排序三、源程序及注释：int partition(Record r[ ], int low, int high){int k;r[0]=r[low];k=r[low].key;while(low<high){while(low<high&&r[high].key>=k)high--;r[low]=r[high];while(low<high&&r[low].key<k)low++;r[high]=r[low];}r[low]=r[0];return low;}void main(){Record r[size];int i=1, j, k, low=1, high;printf("输入关键字序列：\n");scanf("%d", &k);while(k!=0){r[i++].key=k;scanf("%d", &k);}high=i-1;partition(r, low, high);printf("一趟快速排序之后的关键字序列为：\n");for(i=1;i<=high;i++)printf("%d ", r[i].key);printf("\n");}四、运行输出结果：五、调试和运行程序过程中产生的问题及采取的措施：六、对算法的程序的讨论、分析，改进设想，其它经验教训：七、对实验方式、组织、设备、题目的意见和建议：。

东华大学信息科学与技术学院实验报告实验名称：线性表的基本操作指导教师：学生姓名：学生学号：实验日期：2012/11一、实验目的１、熟悉Ｃ或VC++语言上机环境。

２、会定义线性表的顺序存储结构和链式存储结构。

３、熟悉顺序表和单链表的一些基本操作和应用。

４、加深对线性表的理解，逐步培养解决实际问题的编程能力。

二、实验环境运行Ｃ或VC++的微机。

三、实验内容：分别使用顺序表和单链表存储结构实现以下操作：1.建立线性表L＝｛12,13,21,24,28,31,42,77｝；2.在第5个元素之前插入26；3.删除第5个元素28；4.查找28。

四、实验设计思路及算法流程(一)使用顺序表实现操作:建立顺序表，完成顺序表的基本操作：初始化、插入、删除、输出、查找元素、判线性表是否为空；问题分析：利用顺序表,设计一组输入数据，能够对顺序表进行如下操作：创建一个新的顺序表，实现动态空间分配的初始化；已给定的值插入到指定位置和删除指定位置的值，形成有序顺序表；按值查找，根据给定数据元素的值，查找该元素的位置，对查找结果进行返回；实现顺序表的各个元素的输出；“初始化算法”的操作结果：构造一个空的顺序线性表，对顺序表的空间进行动态管理，实现动态分配、回收和增加存储空间；“位置插入算法”的初始条件：顺序线性表L已存在，给定的元素位置为i，且1≤i≤ListLength(L)+1 ；其操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1；“位置删除算法”的初始条件：顺序线性表L已存在，1≤i≤ListLength(L) ；其操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 ；“输出算法”的初始条件：顺序线性表L已存在；其操作结果：依次对L的每个数据元素进行输出；“按值查找算法”初始条件：顺序线性表L已存在，元素值为e；其操作结果：返回L 中数据元素值为e的元素位置；线性表的顺序存储结构的定义及其基本操作的参考程序（顺序表）文件一：pubuse. h 是公共使用的常量定义和系统函数调用声明。

实验一线性表抽象数据类型的实现【实验内容】1.利用程序设计语言实现单链表的抽象数据类型。

2.明白单链表头结点在程序语言的表示及用法。

3.掌握单链表的插入、删除、输出等运算。

【实验方法与步骤】个人程序如下：#include <stdio.h>#include <stdlib.h>typedef struct node{int nDate;struct node *pstnext;}Node;//链表输出董宝超void output(Node *head){Node *p = head->pstnext;while(NULL != p){printf("%d ", p->nDate);p = p->pstnext;}printf("\r\n");}//创建链表王宁宁Node* creat(){Node *head = NULL, *p = NULL, *s = NULL;int Date = 0, cycle = 1;head = (Node*)malloc(sizeof(Node));if(NULL == head){printf("分配内存失败\r\n");return NULL;}head->pstnext = NULL;p = head;while(cycle){printf("请输入数据且当输入数据为0时结束输入\r\n");scanf("%d", &Date);if(0 != Date){s = (Node*)malloc(sizeof(Node)); if(NULL == s){printf("分配内存失败\r\n");return NULL;}s->nDate = Date;p->pstnext = s;p = s;}else{cycle = 0;}}p->pstnext = NULL;return(head);}//在指定元素之后插入新结点张容void insert_2(Node *head, int i, int Newdate) {Node *pre = head, *New = NULL;int j = 0;while(NULL != pre->pstnext && j < i){pre = pre->pstnext;j++;}if(j == i){New = (Node*)malloc(sizeof(Node));if(NULL == New){printf("分配内存失败\r\n");return;}New->nDate = Newdate;New->pstnext = pre->pstnext;pre->pstnext = New;}else{printf("插入位置不存在\r\n");}}void main()//兰洋王克{int date, num; //待查找数据int i3; //指定删除元素的位置int i1, i2, Newdate_1, Newdate_2; //待插入的新数据 int Delete_date, k; //待删除的数据与其个数Node *Head = NULL; //定义头结点Node *Head_New = NULL;//链表建立Head = creat();printf("输出建立的单链表\r\n");output(Head);//在指定第i2个元素之后插入新元素Newdateprintf("在指定第i个元素之后插入新元素Newdate"); printf("请输入i与元素且以逗号间隔\r\n");scanf("%d,%d", &i2, &Newdate_2);insert_2(Head, i2, Newdate_2);printf("插入后新链表\r\n");output(Head);return;}总程序如下：#include <stdio.h>#include <stdlib.h>typedef struct node{int nDate;struct node *pstnext;}Node;//链表输出void output(Node *head){Node *p = head->pstnext;while(NULL != p){printf("%d ", p->nDate);p = p->pstnext;}printf("\r\n");}//链表建立Node* creat(){Node *head = NULL, *p = NULL, *s = NULL; int Date = 0, cycle = 1;head = (Node*)malloc(sizeof(Node));if(NULL == head){printf("分配内存失败\r\n");return NULL;}head->pstnext = NULL;p = head;while(cycle){printf("请输入数据且当输入数据为0时结束输入\r\n"); scanf("%d", &Date);if(0 != Date){s = (Node*)malloc(sizeof(Node));if(NULL == s){printf("分配内存失败\r\n");return NULL;}s->nDate = Date;p->pstnext = s;p = s;}else{cycle = 0;}}p->pstnext = NULL;return(head);}//单链表测长void length(Node *head){Node *p = head->pstnext;int j=0;while(NULL != p){p = p->pstnext;j++;}printf("%d\r\n", j);}//链表按值查找void research_Date(Node *head, int date) {Node *p;int n=1;p = head->pstnext;while(NULL != p && date != p->nDate){p = p->pstnext;++n;}if(NULL == p){printf("链表中没有找到该值");}else if(date == p->nDate){printf("要查找的值%d在链表中第%d个位置\r\n", date, n); }return;}//按序号查找void research_Number(Node *head, int Num){Node *p=head;int i = 0;while(NULL != p && i < Num){p = p->pstnext;i++;}if(p == NULL){printf("查找位置不合法\r\n");}else if(i == 0){printf("查找位置为头结点\r\n");}else if(i == Num){printf("第%d个位置数据为%d\r\n", i, p->nDate); }}//在指定元素之前插入新结点void insert_1(Node *head, int i, int Newdate) {Node *pre = head, *New = NULL;int j = 0;while(NULL != pre && j < i-1){pre = pre->pstnext;j++;}if(NULL == pre || j > i-1){printf("插入位置不存在\r\n");}else{New = (Node*)malloc(sizeof(Node));if(NULL == New){printf("分配内存失败\r\n");return;}New->nDate = Newdate;New->pstnext = pre->pstnext;pre->pstnext = New;}}//在指定元素之后插入新结点void insert_2(Node *head, int i, int Newdate) {Node *pre = head, *New = NULL;int j = 0;while(NULL != pre->pstnext && j < i){pre = pre->pstnext;j++;}if(j == i){New = (Node*)malloc(sizeof(Node)); if(NULL == New){printf("分配内存失败\r\n");return;}New->nDate = Newdate;New->pstnext = pre->pstnext;pre->pstnext = New;}else{printf("插入位置不存在\r\n");}}//删除指定结点void Delete_1(Node *head, int i3) {Node *p = head, *pre = NULL;int j = 0;while(NULL != p && j < i3){pre = p;p = p->pstnext;j++;}if(NULL == p){printf("删除位置不存在\r\n");}else{pre->pstnext = p->pstnext;free(p);}}//指定删除单链表中某个数据，并统计删除此数据的个数int Delete_2(Node *head, int Delete_date){int count = 0;Node *p = head, *q;while(NULL != p->pstnext){q = p->pstnext;if(q->nDate == Delete_date){p->pstnext = q->pstnext;free(q);++count;}else{p = q;}}return count;}//链表逆置void Reverse_list(Node *head){Node *q, *s;if(NULL == head->pstnext || NULL == head->pstnext->pstnext) {return;}q = head->pstnext->pstnext;head->pstnext->pstnext = NULL;while(NULL != q){s = q->pstnext;q->pstnext = head->pstnext;head->pstnext = q;q = s;}}//单链表的连接void connect_list(Node *head, Node *head_New) {Node *p = head;while(NULL != p->pstnext){p = p->pstnext;}p->pstnext = head_New->pstnext;}//单链表销毁void destroy_list(Node* head){while (NULL != head){Node* temp = head;head = head->pstnext;free(temp);}}void main(){int date, num; //待查找数据int i3; //指定删除元素的位置int i1, i2, Newdate_1, Newdate_2; //待插入的新数据 int Delete_date, k; //待删除的数据与其个数Node *Head = NULL; //定义头结点Node *Head_New = NULL;//链表建立Head = creat();printf("输出建立的单链表\r\n");output(Head);//单链表测长printf("单链表长度为\r\n");length(Head);//链表按值查找printf("请输入待查找的数据\r\n");scanf("%d", &date);research_Date(Head, date);//链表按序号查找printf("请输入待查找序号\r\n");scanf("%d", &num);research_Number(Head, num);//在指定第i1个元素之前插入新元素Newdateprintf("在指定第i个元素之前插入新元素Newdate"); printf("请输入i与元素且以逗号间隔(eg:2,23)\n"); scanf("%d,%d", &i1, &Newdate_1);insert_1(Head, i1, Newdate_1);printf("插入后新链表\r\n");output(Head);//在指定第i2个元素之后插入新元素Newdateprintf("在指定第i个元素之后插入新元素Newdate"); printf("请输入i与元素且以逗号间隔(eg:2,23)\n"); scanf("%d,%d", &i2, &Newdate_2);insert_2(Head, i2, Newdate_2);printf("插入后新链表\r\n");output(Head);//指定删除i3元素printf("删除元素的位置\r\n");scanf("%d", &i3);Delete_1(Head, i3);printf("删除后新链表\r\n");output(Head);//指定删除单链表中某个数据，并统计删除此数据的个数 printf("请输入待删除的元素\r\n");scanf("%d", &Delete_date);k = Delete_2(Head, Delete_date);printf("删除后新链表\r\n");output(Head);printf("删除指定元素在链表中的个数为：");printf("%d\r\n", k);//单链表逆置Reverse_list(Head);printf("逆置后输出\r\n");output(Head);//单链表的连接printf("建立一个新链表\r\n");Head_New = creat();printf("输出新链表");output(Head);printf("将新链表连接到原来链表的尾部并输出\r\n"); connect_list(Head, Head_New);output(Head);destroy_list(Head);return;}【实验结果】实验二表达式求值的实现【实验内容】1.用程序设计语言实现栈的抽象数据类型。

数据结构上机实验源代码栈的应用十进制数转换为八进制数，逆序输出所输入的数实验代码：//stack.h，头文件class stack{public:stack();bool empty()const;bool full()const;error_code gettop(elementtype &x)const;error_code push(const elementtype x);error_code pop();private:int count;elementtype data[maxlen];};stack::stack(){count=0;}bool stack::empty()const{return count==0;}bool stack::full()const{return count==maxlen;}error_code stack::gettop(elementtype &x)const{if(empty())return underflow;else{x=data[count-1];return success;}}error_code stack::push(const elementtype x){if(full())return overflow;data[count]=x;count++;return success;}error_code stack::pop(){if(empty())return underflow;count--;return success;}//主程序#include<iostream.h>enum error_code{overflow,underflow,success};typedef int elementtype;const int maxlen=20;#include"stack.h"void read_write() //逆序输出所输入的数{stack s;int i;int n,x;cout<<"please input num int n:";cin>>n;for(i=1;i<=n;i++){cout<<"please input a num:";cin>>x;s.push(x);}while(!s.empty()){s.gettop(x);cout<<x<<" ";s.pop();}cout<<endl;}void Dec_to_Ocx(int n) //十进制转换为八进制{stack s1;int mod,x;while(n!=0){mod=n%8;s1.push(mod);n=n/8;}cout<<"the ocx of the dec is:";while(!s1.empty()){s1.gettop(x);cout<<x;s1.pop();}cout<<endl;}void main(){int n;// read_write();cout<<"please input a dec:";cin>>n;Dec_to_Ocx(n);}队列的应用打印n行杨辉三角实验代码：//queue.hclass queue{public:queue(){count=0;front=rear=0;}bool empty(){return count==0;}bool full(){return count==maxlen-1;}error_code get_front(elementtype &x){if(empty())return underflow;x=data[(front+1)%maxlen];return success;}error_code append(const elementtype x){if(full())return overflow;rear=(rear+1)%maxlen;data[rear]=x;count++;return success;}error_code serve(){if(empty())return underflow;front=(front+1)%maxlen;count--;return success;}private:int count;int front;int rear;int data[maxlen];};//主程序#include<iostream.h>enum error_code{overflow,underflow,success};typedef int elementtype;const int maxlen=20;#include"queue.h"void out_number(int n) //打印前n行的杨辉三角{int s1,s2;int i;int j;int k;queue q;for(i=1;i<=(n-1)*2;i++)cout<<" ";cout<<"1 "<<endl;q.append(1);for(i=2;i<=n;i++){s1=0;for(k=1;k<=(n-i)*2;k++)cout<<" ";for(j=1;j<=i-1;j++){q.get_front(s2);q.serve();cout<<s1+s2<<" ";q.append(s1+s2);s1=s2;}cout<<"1 "<<endl;q.append(1);}}void main(){int n;cout<<"please input n:";cin>>n;out_number(n);}单链表实验实验目的:实验目的（1）理解线性表的链式存储结构。

数据结构上机实验报告8—AAXXX课程名称：数据结构年级：09实验日期：姓名：学号：04班级：实验名称：图实验序号：实验八成员人数：1一、实验目的及要求1.了解C语言程序的特点2．掌握简单的C语言程序结构3．熟练掌握运行Ｃ程序的步骤和方法4. 掌握图的存储表示方法、图的遍历二、实验环境三、实验内容1）使用邻接表表示图，并对图进行深度优先遍历和广度优先遍历。

四、算法描述及实验步骤用算法表示方法，流程图等形式表达算法设计思想与算法实现步骤五、调试过程及实验结果六、总结熟悉图结构，了解图的存储和遍历七、附录（源程序清单）#include<stdlib.h>#include<stdio.h>int visited[10];typedef struct ArcNode{int adjvex;struct ArcNode *next;}Edge;typedef struct VNode{char vertex;Edge *first;}Vertex;typedef Vertex AdjList[10];typedef struct{AdjList adj;int n,e;}Algraph;void creatALG(Algraph *g){int i,j,k;Edge *s=NULL;printf("please input vertex:");scanf("%d",&(g->n));printf("please input edges:");scanf("%d",&(g->e));getchar();for(i=0;i<g->n;i++){g->adj[i].vertex=i+48;g->adj[i].first=NULL;}for(k=0;k<g->e;k++){printf("please the %d edge:",k+1); scanf("%d %d",&i,&j);getchar();s=(Edge *)malloc(sizeof(Edge));s->adjvex=j;s->next=g->adj[i].first;g->adj[i].first=s;}}void DFSG(Algraph *g,int i){Edge *p;printf("%c ",g->adj[i].vertex);visited[i]=1;p=g->adj[i].first;while(p){if(!visited[p->adjvex])DFSG(g,p->adjvex);p=p->next;}}void Depth_First(Algraph *g){int i;for(i=0;i<g->n;i++)visited[i]=0;for(i=0;i<g->n;i++)if(!visited[i])DFSG(g,i);}void Breadth_First(Algraph *g,int i){Edge *p;int q[10],f=0,r=0;int j,v;for(j=0;j<g->n;j++)visited[j]=0;visited[i]=1;printf("%c ",g->adj[i].vertex);q[r++]=i;while(r!=f){v=q[f++];p=g->adj[v].first;while(p){if(!visited[p->adjvex]){visited[p->adjvex]=1;printf("%c ",g->adj[p->adjvex].vertex);q[r++]=p->adjvex;}p=p->next;}}}void main(){Algraph G;creatALG(&G);printf("\nDepth_First Search:");Depth_First(&G);printf("\nBreadth_First Search:");Breadth_First(&G,0);}。

链栈#include<iostream.h>#include<stdlib.h>typedef int ElemType;struct SNode{ElemType data;SNode* next;};void InitStack(SNode*& HS){HS=NULL;//将栈置空}void Push(SNode*& HS,const ElemType& item) {//为插入元素获取动态结点SNode* newptr=new SNode;//给新分配的结点赋值newptr->data=item;//向栈顶插入新结点newptr->next=HS;HS=newptr;}ElemType Pop(SNode*& HS){if(HS==NULL){cerr<<"Linked stack is empty!"<<endl;exit(1);}SNode*p=HS;HS=HS->next;ElemType temp=p->data;delete p;return temp;}ElemType Peek(SNode* HS){if(HS==NULL){cerr<<"Linked stack is empty!"<<endl;exit(1);}return HS->data;//返回栈顶结点的值}bool EmptyStack(SNode* HS){return HS==NULL;}void ClearStack(SNode*& HS){SNode *cp,*np;cp=HS;//给cp指针赋初值，使之指向栈顶结点while(cp!=NULL){//从栈顶到栈底依次删除每个结点np=cp->next;delete cp;cp=np;}HS=NULL;}void main(){SNode* a;InitStack(a);int x;cin>>x;while(x!=-1){Push(a,x);cin>>x;}while(!EmptyStack(a))//栈不为空时依次退栈打印出来cout<<Pop(a)<<" ";cout<<endl;ClearStack(a);}顺序栈#include<iostream.h>#include<stdlib.h>typedef int ElemType;struct Stack{ElemType *stack;int top;int MaxSize;};void InitStack(Stack& S){//初始设置栈空间大小为10个元素位置S.MaxSize=10;//动态空间分配，若分配失败侧退出运行S.stack=new ElemType[S.MaxSize];if(!S.stack){cerr<<"动态存储分配失败!"<<endl;exit(1);}S.top=-1;}void Push(Stack& S,ElemType item){if(S.top==S.MaxSize-1){int k=sizeof(ElemType);S.stack=(ElemType*)realloc(S.stack,2*S.MaxSize*k);S.MaxSize=2*S.MaxSize;}//栈顶指针后移一个位置S.top++;//新元素插入栈顶S.stack[S.top]=item;}ElemType Pop(Stack& S){//若栈空则退出运行if(S.top==-1){cerr<<"Stack is empty!"<<endl;exit(1);}//栈顶指针减1表示退栈S.top--;//返回原栈顶元素的值return S.stack[S.top+1];}ElemType Peek(Stack& S){if(S.top==-1){cerr<<"Stack is empty!"<<endl;exit(1);}return S.stack[S.top];}bool EmptyStack(Stack& S){return S.top==-1;}void ClearStack(Stack& S){if(S.stack){delete []S.stack;S.stack=0;}S.top=-1;S.MaxSize=0;}void main(){Stack s;InitStack(s);int a[8]={4,5,6,20,42,30,58,65};int i;for(i=0;i<8;i++) Push(s,a[i]);cout<<Pop(s);cout<<' '<<Pop(s)<<endl;Push(s,60);cout<<Peek(s);cout<<' '<<Pop(s)<<endl;while(!EmptyStack(s)) cout<<Pop(s)<<' ';cout<<endl;ClearStack(s);}栈的应用----运算#include<iostream.h>#include<stdlib.h>typedef char ElemType;struct Stack{ElemType *stack;int top;int MaxSize;};void InitStack(Stack& S){//初始设置栈空间大小为10个元素位置S.MaxSize=10;//动态存储空间分配，若分配失败则退出运行S.stack=new ElemType[S.MaxSize];if(!S.stack){cerr<<"动态存储分配失败!"<<endl;exit(1);}S.top=-1;}void Push(Stack& S,ElemType item){//若栈空间用完则自动扩大2倍空间，原有栈内容不变if(S.top==S.MaxSize-1){int k=sizeof(ElemType);S.stack=(ElemType*)realloc(S.stack,2*S.MaxSize*k);S.MaxSize=2*S.MaxSize;}S.top++;S.stack[S.top]=item;}ElemType Pop(Stack& S){if(S.top==-1){cerr<<"Stack is empty!"<<endl;exit(1);}S.top--;return S.stack[S.top+1];}ElemType Peek(Stack& S){if(S.top==-1)cerr<<"Stack is empty!"<<endl;exit(1);}return S.stack[S.top];}bool EmptyStack(Stack& S){return S.top==-1;}void ClearStack(Stack& S){if(S.stack){delete[]S.stack;S.stack=0;}S.top=-1;S.MaxSize=0;}int Precedence(char op){switch(op){case '+':case '-':return 1;case '*':case '/':return 2;case '(':case '@':default:return 0;}}void Change(char*S1,char*S2){Stack R;InitStack(R);Push(R,'@');int i=0,j=0;char ch=S1[i];while(ch!='\0')if(ch==' ') ch=S1[++i];else if(ch=='('){Push(R,ch); ch=S1[++i];}else if(ch==')'){while(Peek(R)!='(') S2[j++]=Pop(R);Pop(R);ch=S1[++i];}else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'){char w=Peek(R);while(Precedence(w)>=Precedence(ch)){S2[j++]=w;Pop(R);w=Peek(R);}Push(R,ch);ch=S1[++i];}else{if((ch<'0'||ch>'9')&& ch!='.'){cout<<"中缀表达式错误!"<<endl;exit(1);}while((ch>='0'&&ch<='9')||ch=='.'){S2[j++]=ch;ch=S1[++i];}S2[j++]=' ';}}ch=Pop(R);while(ch!='@'){if(ch=='('){cerr<<"expression error!"<<endl;exit(1);}else{S2[j++]=ch;ch=Pop(R);}}S2[j++]='\0';}void main(){char a[30];char b[30];cout<<"请输入一个中缀算术表达式:"<<endl;cin.getline(a,sizeof(a));Change(a,b);cout<<"对应的后缀算术表达式: "<<endl;cout<<b<<endl;}。

数据结构与算法B上机实验报告第1次2011-10-02 顺序表的实现和基本操作第2次2011-10-29 二叉树的实现和递归遍历第3次2011-11-23 内部排序第4次2011-12-dd 实现图从邻接矩阵到邻接表存储转化第一次线性表数据结构一、上机实习题目线性链表操作——插入、删除、合并、排序、查找二数据结构设计（算法设计）源程序（#include <iostream>#define MaxSize 100using namespace std;typedef int ElemType;class SeqList{ElemType list[MaxSize];int length;public:SeqList() {length=0;}void SeqListSort(int i,ElemType x);void SeqListCreat(int n);void SeqListInset(int i,ElemType x);void SeqListDelete(int i);void SeqListMerge();int GetLength(){return length;}int SeqListFind(ElemType x);int SeqListIsEmpty();void SeqListPrint();}Mylist1,Mylist2;//创建顺序表void SeqList::SeqListCreat(int n){ElemType x;cout<<"请输入数据元素:";for (int i=0;i<n;i++){cin>>x;list[i]=x;length++;}}//对顺序表进行排序void SeqList::SeqListSort(int i,ElemType x) {for(int k=0;k<length;k++){for(i=k+1;i<=length;i++){if(list[k]>list[i]){x=list[k];list[k]=list[i];list[i]=x;}}}}//在顺序表L中的第i个位置插入新元素x void SeqList::SeqListInset(int i,ElemType x) {int k;if(length>=MaxSize)cout<<"表已满，无法插入！"<<endl;else if(i<0||i>length)cout<<"参数i不合理！"<<endl;else{for (k=length;k>=i;k--){list[k]=list[k-1];}list[i-1]=x;length++;}}//删除第i个位置的数据元素void SeqList::SeqListDelete(int i){int k;if(!SeqListIsEmpty())cout<<"表已空，无法删除！"<<endl;else if(i<0||i>length)cout<<"参数i不合理！"<<endl;elsefor(k=i-1;k<length;k++)list[k]=list[k+1];length--;}//查找元素x在表中的位置int SeqList::SeqListFind(ElemType x) {int i=0;while(i<length&&list[i]!=x)i++;if(i>length)return -1;elsereturn i+1;}//判断顺序表是否为空int SeqList::SeqListIsEmpty(){if(length<=0)return 0;else return 1;}//将顺序表显示在屏幕上void SeqList::SeqListPrint(){if(!SeqListIsEmpty())cout<<"空表！"<<endl;elsefor(int i=0;i<length;i++)cout<<list[i]<<" ";cout<<endl;}int main(){SeqList Mylist1,Mylist2;int i,n,flag=1,select;ElemType x;cout<<"1. 建立顺序表\n";cout<<"2. 对顺序表进行排序\n";cout<<"3. 求x数值的位置\n";cout<<"4. 在第i个位置插入新元素x\n"; cout<<"5. 删除第i个位置上的数值\n"; cout<<"6. 将两个顺序表合并\n";cout<<"7. 退出\n";cout<<endl;while (flag){cout<<"请选择操作：";cin>>select;switch(select){case 1:cout<<"请输入顺序表1的长度：";cin>>n;Mylist1.SeqListCreat(n);cout<<"你所输入的顺序表1为：";Mylist1.SeqListPrint();cout<<"请输入顺序表2的长度：";cin>>n;Mylist2.SeqListCreat(n);cout<<"你所输入的顺序表2为：";break;case 2:cout<<"请选择所要排序的顺序表1或2："; cin>>n;if(n==1){Mylist1.SeqListSort(i,x);cout<<"排序后的顺序表1为:";Mylist1.SeqListPrint();}else{Mylist2.SeqListSort(i,x);cout<<"排序后的顺序表2为:";Mylist2.SeqListPrint();}break;case 3:cout<<"请输入x的值：";cin>>x;i=Mylist1.SeqListFind(x);if(i!=-1) cout<<"x的位置为："<<i<<endl;else cout<<"没有找到！";break;case 4:cout<<"请输入要插入的元素的位置和数值x："; cin>>i>>x;cout<<"插入后的顺序表为:";Mylist1.SeqListPrint();break;case 5:cout<<"请输入要删除的元素的位置：";cin>>i;Mylist1.SeqListDelete(i);cout<<"删除后的顺序表为：";Mylist1.SeqListPrint();break;case 6:cout<<"合并后的顺序表为：\n";Mylist1.SeqListPrint();Mylist2.SeqListPrint();break;case 7:flag=0;break;}}}三运行结果为：四、上机环境和使用语言（计算机程序实现）Visual C++。

//文件名：exp1-1.cpp#include <stdio.h>#include <math.h>bool prime(int n) //判断正整数n是否为素数{int i;for (i=2;i<=(int)sqrt(n);i++)if (n%i==0)return false; //若n不是素数,则退出并返回false return true;}void main(){int n,i,j=0; //j用于累计素数个数printf("n:");scanf("%d",&n);printf("小于等于%d的素数:\n",n);if (n>2){ printf("%4d",2);j++;}for (i=3;i<=n;i+=2)if (prime(i)){ printf("%4d",i);if (j!=0 && ++j%10==0) //每行最多显示10个素数printf("\n");}printf("\n");}//文件名：exp1-2.cpp#include <stdio.h>int func(int num){int s=0;do{s+=num%10;num/=10;} while(num);return(s);}{int n;printf("输入一个整数:");scanf("%d",&n);printf("各位数字之和:%d\n",func(n));printf("\n");}//文件名：exp1-3.cpp#include <stdio.h>#include <string.h>#define MAX 100 //字符串的最大长度bool func(char s[]){bool flag=true;int i,j,slen=strlen(s); //slen为字符串s的长度for (i=0,j=slen-1;i<j;i++,j--)if (s[i]!=s[j]){flag=false;break;}return(flag);}void main(){char s[MAX];printf("输入一字符串:");scanf("%s",s);if (func(s))printf("%s字符串是回文\n",s);elseprintf("%s字符串不是回文\n",s);}}实验题3//文件名:algo3-1.cpp#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct{ElemType data[MaxSize];int top; //栈顶指针} SqStack;void InitStack(SqStack *&s) //初始化栈S{ s=(SqStack *)malloc(sizeof(SqStack));s->top=-1; //栈顶指针置为-1 }void DestroyStack(SqStack *&s) //销毁栈s{free(s);}bool StackEmpty(SqStack *s) //判断栈空{return(s->top==-1);}bool Push(SqStack *&s,ElemType e) //进栈{ if (s->top==MaxSize-1) //栈满的情况，即栈上溢出return false;s->top++; //栈顶指针增1s->data[s->top]=e; //元素e放在栈顶指针处return true;}bool Pop(SqStack *&s,ElemType &e) //出栈{ if (s->top==-1) //栈为空的情况，即栈下溢出return false;e=s->data[s->top]; //取栈顶指针元素的元素s->top--; //栈顶指针减1return true;}bool GetTop(SqStack *s,ElemType &e) //取栈顶元素{ if (s->top==-1) //栈为空的情况，即栈下溢出return false;e=s->data[s->top]; //取栈顶指针元素的元素return true;}//文件名:algo3-2.cpp#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct linknode{ElemType data; //数据域struct linknode *next; //指针域} LiStack;void InitStack(LiStack *&s) //初始化栈s{ s=(LiStack *)malloc(sizeof(LiStack));s->next=NULL;}void DestroyStack(LiStack *&s) //销毁栈{ LiStack *p=s,*q=s->next;while (q!=NULL){ free(p);p=q;q=p->next;}free(p); //此时p指向尾节点,释放其空间}bool StackEmpty(LiStack *s) //判断栈是否为空{return(s->next==NULL);}void Push(LiStack *&s,ElemType e) //进栈{ LiStack *p;p=(LiStack *)malloc(sizeof(LiStack));p->data=e; //新建元素e对应的节点*p p->next=s->next; //插入*p节点作为开始节点s->next=p;}bool Pop(LiStack *&s,ElemType &e) //出栈{ LiStack *p;if (s->next==NULL) //栈空的情况return false;p=s->next; //p指向开始节点e=p->data;s->next=p->next; //删除*p节点free(p); //释放*p节点return true;}bool GetTop(LiStack *s,ElemType &e) //取栈顶元素{ if (s->next==NULL) //栈空的情况return false;e=s->next->data;return true;}//文件名:algo3-3.cpp#include <stdio.h>#include <malloc.h>#define MaxSize 5typedef char ElemType;typedef struct{ElemType data[MaxSize];int front,rear; //队首和队尾指针} SqQueue;void InitQueue(SqQueue *&q) //初始化队列{ q=(SqQueue *)malloc (sizeof(SqQueue));q->front=q->rear=0;}void DestroyQueue(SqQueue *&q) //销毁队列{free(q);}bool QueueEmpty(SqQueue *q) //判断队列空{return(q->front==q->rear);}bool enQueue(SqQueue *&q,ElemType e) //进队{if ((q->rear+1)%MaxSize==q->front) //队满上溢出return false;q->rear=(q->rear+1)%MaxSize;q->data[q->rear]=e;return true;}bool deQueue(SqQueue *&q,ElemType &e) //出队{if (q->front==q->rear) //队空下溢出return false;q->front=(q->front+1)%MaxSize;e=q->data[q->front];return true;}//文件名:algo3-4.cpp#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct qnode{ElemType data;struct qnode *next;} QNode;typedef struct{QNode *front;QNode *rear;} LiQueue;void InitQueue(LiQueue *&q) //初始化队列{ q=(LiQueue *)malloc(sizeof(LiQueue));q->front=q->rear=NULL;}void DestroyQueue(LiQueue *&q) //销毁队列{ QNode *p=q->front,*r; //p指向队头数据节点if (p!=NULL) //释放数据节点占用空间{ r=p->next;while (r!=NULL){ free(p);p=r;r=p->next;}}free(p);free(q); //释放链队节点占用空间}bool QueueEmpty(LiQueue *q) //判断队列是否为空{return(q->rear==NULL);}void enQueue(LiQueue *&q,ElemType e) //进队{ QNode *p;p=(QNode *)malloc(sizeof(QNode));p->data=e;p->next=NULL;if (q->rear==NULL) //若链队为空,则新节点是队首节点又是队尾节点q->front=q->rear=p;else{ q->rear->next=p; //将*p节点链到队尾,并将rear指向它q->rear=p;}}bool deQueue(LiQueue *&q,ElemType &e) //出队{ QNode *t;if (q->rear==NULL) //队列为空return false;t=q->front; //t指向第一个数据节点if (q->front==q->rear) //队列中只有一个节点时q->front=q->rear=NULL;else //队列中有多个节点时q->front=q->front->next;e=t->data;free(t);return true;}//文件名:exp3-1.cpp#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct{ElemType data[MaxSize];int top; //栈顶指针} SqStack;extern void InitStack(SqStack *&s);extern void DestroyStack(SqStack *&s);extern bool StackEmpty(SqStack *s);extern bool Push(SqStack *&s,ElemType e);extern bool Pop(SqStack *&s,ElemType &e);extern bool GetTop(SqStack *s,ElemType &e);void main(){ElemType e;SqStack *s;printf("栈s的基本运算如下:\n");printf(" (1)初始化栈s\n");InitStack(s);printf(" (2)栈为%s\n",(StackEmpty(s)?"空":"非空"));printf(" (3)依次进栈元素a,b,c,d,e\n");Push(s,'a');Push(s,'b');Push(s,'c');Push(s,'d');Push(s,'e');printf(" (4)栈为%s\n",(StackEmpty(s)?"空":"非空"));printf(" (5)出栈序列:");while (!StackEmpty(s)){Pop(s,e);printf("%c ",e);}printf("\n");printf(" (6)栈为%s\n",(StackEmpty(s)?"空":"非空"));printf(" (7)释放栈\n");DestroyStack(s);}//文件名:exp3-2.cpp#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct linknode{ElemType data; //数据域struct linknode *next; //指针域} LiStack;extern void InitStack(LiStack *&s);extern void DestroyStack(LiStack *&s);extern bool StackEmpty(LiStack *s);extern void Push(LiStack *&s,ElemType e);extern bool Pop(LiStack *&s,ElemType &e);extern bool GetTop(LiStack *s,ElemType &e);void main(){ElemType e;LiStack *s;printf("栈s的基本运算如下:\n");printf(" (1)初始化栈s\n");InitStack(s);printf(" (2)栈为%s\n",(StackEmpty(s)?"空":"非空"));printf(" (3)依次进栈元素a,b,c,d,e\n");Push(s,'a');Push(s,'b');Push(s,'c');Push(s,'d');Push(s,'e');printf(" (4)栈为%s\n",(StackEmpty(s)?"空":"非空"));printf(" (5)出栈序列:");while (!StackEmpty(s)){Pop(s,e);printf("%c ",e);}printf("\n");printf(" (6)栈为%s\n",(StackEmpty(s)?"空":"非空"));printf(" (7)释放栈\n");DestroyStack(s);}//文件名:exp3-4.cpp#include <stdio.h>#include <malloc.h>#define MaxSize 5typedef char ElemType;typedef struct qnode{ElemType data;struct qnode *next;} QNode;typedef struct{QNode *front;QNode *rear;} LiQueue;extern void InitQueue(LiQueue *&q);extern void DestroyQueue(LiQueue *&q);extern bool QueueEmpty(LiQueue *q);extern void enQueue(LiQueue *&q,ElemType e);extern bool deQueue(LiQueue *&q,ElemType &e);void main(){ElemType e;LiQueue *q;printf("链队的基本运算如下:\n");printf(" (1)初始化链队q\n");InitQueue(q);printf(" (2)依次进链队元素a,b,c\n");enQueue(q,'a');enQueue(q,'b');enQueue(q,'c');printf(" (3)链队为%s\n",(QueueEmpty(q)?"空":"非空"));if (deQueue(q,e)==0)printf("\t提示:队空,不能出队\n");elseprintf(" (4)出队一个元素%c\n",e);printf(" (5)依次进链队元素d,e,f\n");enQueue(q,'d');enQueue(q,'e');enQueue(q,'f');printf(" (6)出链队序列:");while (!QueueEmpty(q)){ deQueue(q,e);printf("%c ",e);}printf("\n");printf(" (7)释放链队\n");DestroyQueue(q);}//文件名:exp3-5.cpp#include <stdio.h>#define M 4 //行数#define N 4 //列数#define MaxSize 100 //栈最多元素个数int mg[M+2][N+2]={ //一个迷宫,其四周要加上均为1的外框{1,1,1,1,1,1},{1,0,0,0,1,1},{1,0,1,0,0,1},{1,0,0,0,1,1},{1,1,0,0,0,1},{1,1,1,1,1,1}};struct{int i,j;int di;} Stack[MaxSize],Path[MaxSize]; //定义栈和存放最短路径的数组int top=-1; //栈顶指针int count=1; //路径数计数int minlen=MaxSize; //最短路径长度void mgpath(int xi,int yi,int xe,int ye) //求迷宫路径{int i,j,di,find,k;top++; //进栈Stack[top].i=xi;Stack[top].j=yi;Stack[top].di=-1;mg[xi][yi]=-1; //初始方块进栈while (top>-1) //栈不空时循环{i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;if (i==xe && j==ye) //找到了出口,输出路径{printf("%4d: ",count++);for (k=0;k<=top;k++){printf("(%d,%d) ",Stack[k].i,Stack[k].j);if ((k+1)%5==0) printf("\n\t"); //输出时每5个方块换一行}printf("\n");if (top+1<minlen) //比较找最短路径{for (k=0;k<=top;k++)Path[k]=Stack[k];minlen=top+1;}mg[Stack[top].i][Stack[top].j]=0; //让该位置变为其他路径可走方块top--;i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;}find=0;while (di<4 && find==0) //找下一个可走方块{ di++;switch(di){case 0:i=Stack[top].i-1;j=Stack[top].j;break;case 1:i=Stack[top].i;j=Stack[top].j+1;break;case 2:i=Stack[top].i+1;j=Stack[top].j;break;case 3:i=Stack[top].i,j=Stack[top].j-1;break;}if (mg[i][j]==0) find=1;}if (find==1) //找到了下一个可走方块{ Stack[top].di=di; //修改原栈顶元素的di值top++;Stack[top].i=i;Stack[top].j=j;Stack[top].di=-1;//下一个可走方块进栈mg[i][j]=-1; //避免重复走到该方块}else //没有路径可走,则退栈{mg[Stack[top].i][Stack[top].j]=0; //让该位置变为其他路径可走方块top--;}}printf("最短路径如下:\n");printf("长度: %d\n",minlen);printf("路径: ");for (k=0;k<minlen;k++){printf("(%d,%d) ",Path[k].i,Path[k].j);if ((k+1)%5==0) printf("\n\t"); //输出时每5个方块换一行}printf("\n");}void main(){printf("迷宫所有路径如下:\n");mgpath(1,1,M,N);}//文件名:exap3-6.cpp#include <stdio.h>#include <stdlib.h>#define MaxSize 100int cont=0; //记录解个数typedef struct{int col[MaxSize]; //col[i]存放第i个皇后的列号int top; //栈顶指针} StType; //定义顺序栈类型int count=0;bool place(StType st,int i,int j) //测试(i,j)是否与1～i-1皇后有冲突{int k=1;if (i==1) return true; //放第一个皇后时没有冲突while (k<=i-1) //j=1到k-1是已放置了皇后的列{if ((st.col[k]==j)|| (abs(j-st.col[k])==abs(k-i)))return false;k++;}return true;}void queen(int n) //求解n皇后问题{int i,j,k;bool find;StType st; //定义栈stst.top=0; //初始化栈顶指针st.top++; //将(1,1)进栈st.col[st.top]=1;while (st.top>0) //栈不空时循环{i=st.top; //当前皇后为第i个皇后if (st.top==n) //所有皇后均放好,输出一个解{printf(" 第%d个解：",++count);for (k=1;k<=st.top;k++)printf("(%d,%d) ",k,st.col[k]);printf("\n");}find=false;for (j=1;j<=n;j++)if (place(st,i+1,j)) //在i+1行找到一个放皇后的位置(i+1,j){st.top++;st.col[st.top]=j;find=true;break;}if (find==false) //在i+1行找不到放皇后的位置,回溯{while (st.top>0){if (st.col[st.top]==n) //本行没有可放位置,退栈st.top--;for (j=st.col[st.top]+1;j<=n;j++) //在本行找下一个位置if (place(st,st.top,j)){st.col[st.top]=j;break;}if (j>n) //当前皇后在本行没有可放的位置st.top--; //退栈else //本行找到一个位置后退出回溯break;}}}}void main()int n; //n存放实际皇后个数printf(" 皇后问题(n<20) n=");scanf("%d",&n);if (n>20)printf("n值太大,不能求解\n");else{ printf(" %d皇后问题求解如下：\n",n);queen(n);printf("\n");}}//文件名:exp3-7.cpp#include <stdio.h>#include <malloc.h>typedef struct qnode{int data;struct qnode *next;} QNode; //链队节点类型typedef struct{QNode *front,*rear;} QuType; //链队类型void Destroyqueue(QuType *&qu) //释放链队{QNode *p,*q;p=qu->front;if (p!=NULL) //若链队不空{q=p->next;while (q!=NULL) //释放队中所有的节点{free(p);p=q;q=q->next;}free(p);}free(qu); //释放链队节点}void SeeDoctor()int sel,flag=1,find,no;QuType *qu;QNode *p;qu=(QuType *)malloc(sizeof(QuType)); //创建空队qu->front=qu->rear=NULL;while (flag==1) //循环执行{printf("1:排队2:就诊3:查看排队4.不再排队,余下依次就诊5:下班请选择:");scanf("%d",&sel);switch(sel){case 1: printf(" >>输入病历号:");do{scanf("%d",&no);find=0;p=qu->front;while (p!=NULL && !find){if (p->data==no)find=1;elsep=p->next;}if (find)printf(" >>输入的病历号重复,重新输入:");} while (find==1);p=(QNode *)malloc(sizeof(QNode)); //创建节点p->data=no;p->next=NULL;if (qu->rear==NULL) //第一个病人排队qu->front=qu->rear=p;else{qu->rear->next=p;qu->rear=p; //将*p节点入队}break;case 2: if (qu->front==NULL) //队空printf(" >>没有排队的病人!\n");else //队不空{p=qu->front;printf(" >>病人%d就诊\n",p->data);if (qu->rear==p) //只有一个病人排队的情况qu->front=qu->rear=NULL;elsequ->front=p->next;free(p);}break;case 3:if (qu->front==NULL) //队空printf(" >>没有排列的病人!\n");else //队不空{p=qu->front;printf(" >>排队病人:");while (p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");}break;case 4:if (qu->front==NULL) //队空printf(" >>没有排列的病人!\n");else //队不空{p=qu->front;printf(" >>病人按以下顺序就诊:");while (p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");}Destroyqueue(qu); //释放链队flag=0; //退出break;case 5:if (qu->front!=NULL) //队不空printf(" >>请排队的病人明天就医!\n");flag=0; //退出Destroyqueue(qu); //释放链队break;}}}void main(){SeeDoctor();}//文件名:exp3-8.cpp#include <stdio.h>#include <malloc.h>#define N 3 //停车场内最多的停车数#define M 4 //候车场内最多的停车数#define Price 2 //每单位停车费用typedef struct{int CarNo[N]; //车牌号int CarTime[N]; //进场时间int top; //栈指针} SqStack; //定义顺序栈类型typedef struct{int CarNo[M]; //车牌号int front,rear; //队首和队尾指针} SqQueue; //定义循环队类型//以下为顺序栈的基本运算算法void InitStack(SqStack *&s){s=(SqStack *)malloc(sizeof(SqStack));s->top=-1;}bool StackEmpty(SqStack *s){return(s->top==-1);}bool StackFull(SqStack *s){return(s->top==N-1);}bool Push(SqStack *&s,int e1,int e2){if (s->top==N-1)return false;s->top++;s->CarNo[s->top]=e1;s->CarTime[s->top]=e2;return true;}bool Pop(SqStack *&s,int &e1,int &e2){if (s->top==-1)return false;e1=s->CarNo[s->top];e2=s->CarTime[s->top];s->top--;return true;}void DispStack(SqStack *s){int i;for (i=s->top;i>=0;i--)printf("%d ",s->CarNo[i]);printf("\n");}//以下为循环队列的基本运算算法void InitQueue(SqQueue *&q){q=(SqQueue *)malloc (sizeof(SqQueue));q->front=q->rear=0;}bool QueueEmpty(SqQueue *q){return(q->front==q->rear);}bool QueueFull(SqQueue *q) //判断队满{return ((q->rear+1)%M==q->front);}bool enQueue(SqQueue *&q,int e) //进队{if ((q->rear+1)%M==q->front) //队满return false;q->rear=(q->rear+1)%M;q->CarNo[q->rear]=e;return true;}bool deQueue(SqQueue *&q,int &e) //出队{if (q->front==q->rear) //队空的情况return false;q->front=(q->front+1)%M;e=q->CarNo[q->front];return true;}void DispQueue(SqQueue *q) //输出队中元素{int i;i=(q->front+1)%M;printf("%d ",q->CarNo[i]);while ((q->rear-i+M)%M>0){i=(i+1)%M;printf("%d ",q->CarNo[i]);}printf("\n");}void main(){int comm;int no,e1,time,e2;int i,j;SqStack *St,*St1;SqQueue *Qu;InitStack(St);InitStack(St1);InitQueue(Qu);do{printf("输入指令(1:到达2:离开3:停车场4:候车场0:退出):");scanf("%d",&comm);switch(comm){case 1: //汽车到达printf(" 车号到达时间:");scanf("%d%d",&no,&time);if (!StackFull(St)) //停车场不满{Push(St,no,time);printf(" >>停车场位置:%d\n",St->top+1);}else //停车场满{if (!QueueFull(Qu)) //候车场不满{enQueue(Qu,no);printf(" >>候车场位置:%d\n",Qu->rear);}elseprintf(" >>候车场已满,不能停车\n");}break;case 2: //汽车离开printf(" 车号离开时间:");scanf("%d%d",&no,&time);for (i=0;i<=St->top && St->CarNo[i]!=no;i++);if (i>St->top)printf(" >>未找到该编号的汽车\n");else{for (j=i;j<=St->top;j++){Pop(St,e1,e2);Push(St1,e1,e2); //倒车到临时栈St1中}Pop(St,e1,e2); //该汽车离开printf(" >>%d汽车停车费用:%d\n",no,(time-e2)*Price);while (!StackEmpty(St1))//将临时栈St1重新回到St中{Pop(St1,e1,e2);Push(St,e1,e2);}if (!QueueEmpty(Qu)) //队不空时,将队头进栈St{deQueue(Qu,e1);Push(St,e1,time); //以当前时间开始计费}}break;case 3: //显示停车场情况if (!StackEmpty(St)){printf(" >>停车场中的车辆:"); //输出停车场中的车辆DispStack(St);}elseprintf(" >>停车场中无车辆\n");break;case 4: //显示候车场情况if (!QueueEmpty(Qu)){printf(" >>候车场中的车辆:"); //输出候车场中的车辆DispQueue(Qu);}elseprintf(" >>候车场中无车辆\n");break;case 0: //结束if (!StackEmpty(St)){printf(" >>停车场中的车辆:"); //输出停车场中的车辆DispStack(St);}if (!QueueEmpty(Qu)){printf(" >>候车场中的车辆:"); //输出候车场中的车辆DispQueue(Qu);}break;default: //其他情况printf(" >>输入的命令错误\n");break;}} while(comm!=0);}//文件名:algo7-1.cpp#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct node{ElemType data; //数据元素struct node *lchild; //指向左孩子struct node *rchild; //指向右孩子} BTNode;void CreateBTNode(BTNode *&b,char *str) //由str串创建二叉链{BTNode *St[MaxSize],*p=NULL;int top=-1,k,j=0;char ch;b=NULL; //建立的二叉树初始时为空ch=str[j];while (ch!='\0') //str未扫描完时循环{switch(ch){case '(':top++;St[top]=p;k=1; break; //为左节点case ')':top--;break;case ',':k=2; break; //为右节点default:p=(BTNode *)malloc(sizeof(BTNode));p->data=ch;p->lchild=p->rchild=NULL;if (b==NULL) //p指向二叉树的根节点b=p;else //已建立二叉树根节点{switch(k){case 1:St[top]->lchild=p;break;case 2:St[top]->rchild=p;break;}}}j++;ch=str[j];}}BTNode *FindNode(BTNode *b,ElemType x) //返回data域为x的节点指针{BTNode *p;if (b==NULL)return NULL;else if (b->data==x)return b;else{p=FindNode(b->lchild,x);if (p!=NULL)return p;elsereturn FindNode(b->rchild,x);}}BTNode *LchildNode(BTNode *p) //返回*p节点的左孩子节点指针{return p->lchild;}BTNode *RchildNode(BTNode *p) //返回*p节点的右孩子节点指针{return p->rchild;}int BTNodeDepth(BTNode *b) //求二叉树b的深度{int lchilddep,rchilddep;if (b==NULL)return(0); //空树的高度为0 else{lchilddep=BTNodeDepth(b->lchild); //求左子树的高度为lchilddeprchilddep=BTNodeDepth(b->rchild); //求右子树的高度为rchilddepreturn (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1);}}void DispBTNode(BTNode *b) //以括号表示法输出二叉树{if (b!=NULL){printf("%c",b->data);if (b->lchild!=NULL || b->rchild!=NULL){printf("(");DispBTNode(b->lchild);if (b->rchild!=NULL) printf(",");DispBTNode(b->rchild);printf(")");}}}int BTWidth(BTNode *b) //求二叉树b的宽度{struct{int lno; //节点的层次编号BTNode *p; //节点指针} Qu[MaxSize]; //定义顺序非循环队列int front,rear; //定义队首和队尾指针int lnum,max,i,n;front=rear=0; //置队列为空队if (b!=NULL){rear++;Qu[rear].p=b; //根节点指针入队Qu[rear].lno=1; //根节点的层次编号为1while (rear!=front) //队列不为空{front++;b=Qu[front].p; //队头出队lnum=Qu[front].lno;if (b->lchild!=NULL) //左孩子入队{rear++;Qu[rear].p=b->lchild;Qu[rear].lno=lnum+1;}if (b->rchild!=NULL) //右孩子入队{rear++;Qu[rear].p=b->rchild;Qu[rear].lno=lnum+1;}}max=0;lnum=1;i=1;while (i<=rear){n=0;while (i<=rear && Qu[i].lno==lnum){n++;i++;}lnum=Qu[i].lno;if (n>max) max=n;}return max;}elsereturn 0;}int Nodes(BTNode *b) //求二叉树b的节点个数{int num1,num2;if (b==NULL)return 0;else if (b->lchild==NULL && b->rchild==NULL)return 1;else{num1=Nodes(b->lchild);num2=Nodes(b->rchild);return (num1+num2+1);}}int LeafNodes(BTNode *b) //求二叉树b的叶子节点个数{int num1,num2;if (b==NULL)return 0;else if (b->lchild==NULL && b->rchild==NULL)return 1;else{num1=LeafNodes(b->lchild);num2=LeafNodes(b->rchild);return (num1+num2);}}void DestroyBTNode(BTNode *&b){if (b!=NULL){DestroyBTNode(b->lchild);DestroyBTNode(b->rchild);free(b);}}//文件名:exp7-1.cpp#include <stdio.h>typedef char ElemType;typedef struct node{ElemType data; //数据元素struct node *lchild; //指向左孩子struct node *rchild; //指向右孩子} BTNode;extern void CreateBTNode(BTNode *&b,char *str);extern BTNode *FindNode(BTNode *b,ElemType x);extern BTNode *LchildNode(BTNode *p);extern BTNode *RchildNode(BTNode *p);extern int BTNodeDepth(BTNode *b);extern void DispBTNode(BTNode *b);extern int BTWidth(BTNode *b);extern int Nodes(BTNode *b);extern int LeafNodes(BTNode *b);extern void DestroyBTNode(BTNode *&b);void main(){ BTNode *b,*p,*lp,*rp;;CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");printf("二叉树的基本运算如下:\n");printf(" (1)输出二叉树:");DispBTNode(b);printf("\n");printf(" (2)H节点:");p=FindNode(b,'H');if (p!=NULL){ lp=LchildNode(p);if (lp!=NULL)printf("左孩子为%c ",lp->data);elseprintf("无左孩子");rp=RchildNode(p);if (rp!=NULL)printf("右孩子为%c",rp->data);elseprintf("无右孩子");}printf("\n");printf(" (3)二叉树b的深度:%d\n",BTNodeDepth(b));printf(" (4)二叉树b的宽度:%d\n",BTWidth(b));printf(" (5)二叉树b的节点个数:%d\n",Nodes(b));printf(" (6)二叉树b的叶子节点个数:%d\n",LeafNodes(b));printf(" (7)释放二叉树b\n");DestroyBTNode(b);}//文件名:exp7-2.cpp#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct node{ElemType data; //数据元素struct node *lchild; //指向左孩子struct node *rchild; //指向右孩子} BTNode;extern void CreateBTNode(BTNode *&b,char *str);extern void DispBTNode(BTNode *b);extern void DestroyBTNode(BTNode *&b);void PreOrder(BTNode *b) //先序遍历的递归算法{if (b!=NULL){printf("%c ",b->data); //访问根节点PreOrder(b->lchild); //递归访问左子树PreOrder(b->rchild); //递归访问右子树}}void PreOrder1(BTNode *b){BTNode *St[MaxSize],*p;int top=-1;if (b!=NULL){top++; //根节点入栈St[top]=b;while (top>-1) //栈不为空时循环{p=St[top]; //退栈并访问该节点top--;printf("%c ",p->data);if (p->rchild!=NULL) //右孩子入栈{top++;St[top]=p->rchild;}if (p->lchild!=NULL) //左孩子入栈{top++;St[top]=p->lchild;}}printf("\n");}}void InOrder(BTNode *b) //中序遍历的递归算法{if (b!=NULL){InOrder(b->lchild); //递归访问左子树printf("%c ",b->data); //访问根节点InOrder(b->rchild); //递归访问右子树}}void InOrder1(BTNode *b){BTNode *St[MaxSize],*p;int top=-1;if (b!=NULL){p=b;while (top>-1 || p!=NULL){while (p!=NULL){top++;St[top]=p;p=p->lchild;}if (top>-1){p=St[top];top--;printf("%c ",p->data);p=p->rchild;}}printf("\n");}}void PostOrder(BTNode *b) //后序遍历的递归算法{if (b!=NULL){PostOrder(b->lchild); //递归访问左子树PostOrder(b->rchild); //递归访问右子树printf("%c ",b->data); //访问根节点}}void PostOrder1(BTNode *b){BTNode *St[MaxSize];BTNode *p;int flag,top=-1; //栈指针置初值if (b!=NULL){do{while (b!=NULL) //将t的所有左节点入栈{top++;St[top]=b;b=b->lchild;}p=NULL; //p指向当前节点的前一个已访问的节点flag=1;while (top!=-1 && flag){b=St[top]; //取出当前的栈顶元素if (b->rchild==p) //右子树不存在或已被访问,访问之{printf("%c ",b->data); //访问*b节点top--;p=b; //p指向则被访问的节点}else{b=b->rchild; //t指向右子树flag=0;}}} while (top!=-1);printf("\n");}}void TravLevel(BTNode *b){BTNode *Qu[MaxSize]; //定义循环队列int front,rear; //定义队首和队尾指针front=rear=0; //置队列为空队列if (b!=NULL)printf("%c ",b->data);rear++; //节点指针进入队列Qu[rear]=b;while (rear!=front) //队列不为空{front=(front+1)%MaxSize;b=Qu[front]; //队头出队列if (b->lchild!=NULL) //输出左孩子,并入队列{printf("%c ",b->lchild->data);rear=(rear+1)%MaxSize;Qu[rear]=b->lchild;}if (b->rchild!=NULL) //输出右孩子,并入队列{printf("%c ",b->rchild->data);rear=(rear+1)%MaxSize;Qu[rear]=b->rchild;}}printf("\n");}void main(){BTNode *b;CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");printf("二叉树b:");DispBTNode(b);printf("\n");printf("层次遍历序列:");TravLevel(b);printf("先序遍历序列:\n");printf(" 递归算法:");PreOrder(b);printf("\n");printf(" 非递归算法:");PreOrder1(b);printf("中序遍历序列:\n");printf(" 递归算法:");InOrder(b);printf("\n");printf(" 非递归算法:");InOrder1(b);printf("后序遍历序列:\n");printf(" 递归算法:");PostOrder(b);printf("\n");printf(" 非递归算法:");PostOrder1(b);DestroyBTNode(b);}//文件名:exp7-3.cpp#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct node{。

数据结构1.创建一个链表并将他输出#include <stdio.h>#include <stdlib.h>typedef struct node{ int data;struct *link;}*linklist,Lnode;linklist Creat(int n){linklist p,list=NULL,r; int i,d;for(i=1;i<=n;i++){p=(linklist)malloc(sizeof(Lnode));printf("Enter a int data:"); scanf("%d",&d);p->data=d; p->link=NULL;if(list==NULL)list=p;elser->link=p;r=p; }return list;}void print(linklist list){linklist p; p=list;while(p!=NULL){printf("%d\n",p->data); p=p->link ; }}void main(){int n;linklist L;printf("Enter the number of data"); scanf("%d",&n); L=Creat(n); print(L);}创建线性链表在表头插一行#include <stdio.h>#include <stdlib.h>typedef struct node{ int data;struct node * link ;}*linklist,lnode;linklist creat(int n){ linklist p,list=NULL,r;int i ,d;for (i=1;i<=n; i++){ p=(linklist)malloc(sizeof(lnode));printf("enter a int data");scanf ("%d",&d);p->data=d;p->link=NULL;if(list==NULL)list=p;elser->link=p;r=p;}return list;}void print(linklist list){ linklist p;p=list;while (p!=NULL){ printf("%d\n",p->data);p=p->link;}}linklist insertf(linklist list,int item) { linklist p;p=(linklist)malloc(sizeof(lnode));p->data=item;p->link=list;list=p;return list;}void main(){int n,newdata;linklist l;printf("Enter the number of element:"); scanf("%d",&n);l=creat(n);print(l);printf("Enter a newdata:");scanf("%d",&newdata);l=insertf(l,newdata);print(l);}2.检查字符串是否匹配#include<stdio.h>int main(){char stack[20],s[256],w; int top=-1,i=0;printf("Enter a string:"); scanf("%s",s);while(s[i]!='\0'){ if(s[i]=='('||s[i]=='{'||s[i]=='['){stack[++top]=s[i];printf( "push %c %d\n",s[i],i);}elseif(s[i]==')'||s[i]=='}'||s[i]==']'){ w=stack[top--];if((s[i]==')'&&w!='(')||(s[i]==']'&&w!='[')||(s[i]=='}'&&w!='{')) {printf("Error\n");return 0;}}i++;}if(top==-1)printf("OK\n");elseprintf("ERROR\n");return 1;}3、顺序存储方式判断两字符串是否相等#include<stdio.h>int comstr(char A[],char B[]){int i=0;while(A[i]!='\0'&&B[i]!='\0'){if(A[i]!=B[i])return 0;i++; }if(A[i]==B[i])return 1;return 0;}void main(){char s1[256],s2[256];printf("Enter the first string:");gets(s1);printf("Enter the second string:");gets(s2);if(comstr(s1,s2))printf("YES\n");elseprintf("NO\n");}4、创建排序二叉树，采用中序遍历输出#include<stdio.h> #include<stdlib.h>typedef struct node{int data;struct node *L,*R;} *Tlink,Tnode;Tlink insert(Tlink T,int a) {Tlink q=T,p;p=(Tlink)malloc(sizeof(Tnode));p->data=a;p->L=p->R=NULL;if(T==NULL)T=p;elsewhile(1)if(a<q->data)if(q->L==NULL){q->L=p;break;}elseq=q->L;elseif(q->R==NULL){q->R=p;break;}elseq=q->R;return T;}void print(Tlink T){if(T!=NULL){ print(T->L);printf("%d,",T->data);print(T->R);}}void main(){ int a;Tlink T=NULL;while(1){ printf("Enter a int data:");scanf("%d",&a);if(a==-999)break;T=insert(T,a);}print(T);}5. 建立该图的邻接表存储做深度优先遍历。

数据结构上机实验本课程实验中已知的预定义常量和类型如下：#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status；实验一顺序表(一)一、 实验目的掌握顺序表的定义、存储结构及其基本操作。

二、 实验内容已知：线性表的动态分配顺序存储结构为#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct{int *elem；int length；int listsize；}SqList；在主程序中调用如下函数实现构造线性表，在线性表中插入数值，最后输出线性表。

1. 编写函数，Status InitList(SqList *L) 实现构造一个空的线性表，若构造成功则返回OK，否则返回ERROR。

2. 编写函数，Status ListInsert(SqList *L , int i , int e) 实现在线性表L中第i个位置之前插入新的数据元素e，L的长度加1。

若插入成功返回OK，否则返回ERROR。

（提示：i的合法值为：i>=1&&i<=L—>length+1）3. 编写函数，void ListPrint（SqList *L）实现将线性表中的元素依次输出到屏幕上。

4．编写函数，int Menu（），输出菜单项请选择你要进行的操作（请输入1-4中的任一个数字）：输入1：InitList2：ListInsert3：ListPrint4：Exit实验二顺序表（二）一、 实验目的掌握顺序表的定义、存储结构及其基本操作。

二、 实验内容在实验一的基础上，继续完成如下实验内容。

1.编写函数，Status ListDelete(Splist *L ，int i ，int *e)，实现删除L的第i个数据元素，并用e返回其值，L的长度减1。

return OK;
}
int InsertSort(Form &F)
{//对顺序表F作直接插入排序
int i,j;
int comp=0;//比较次数
int move=0;//移动次数
for(i=2;i<=F.length;i++)
{
comp++;
if(F.r[i].key<F.r[i-1].key)
{
high--;
move++;
}
F.r[low]=F.r[high];
if(low<high&&F.r[low].key<=p)
{
low++;
move++;
}
F.r[high]=F.r[low];
}
F.r[low]=F.r[0];
return low;
}
void main()
{
Form F;
Init_Form(F);
{
F.r[0]=F.r[i]; //F.r[0]是监视哨
F.r[i]=F.r[i-1];
j=i-2;
comp++;
if(F.r[0].key<F.r[j].key)
{//进行元素移动，以腾出位置插入F.r[i]
F.r[j+1]=F.r[j];// 记录后移
j--;
move++;
}
F.r[j+1]=F.r[0]; //在j+1处插入F.r[i]
2.实现快速排序算法。
3.实现折半插入排序。
4.采用几组不同数据测试各个排序算法的性能（比较次数和移动次数）。

《数据结构》上机作业——实验报告（五）[推荐]第一篇：《数据结构》上机作业——实验报告(五)[推荐]“计算机软件技术基础”课程实验报告（五）实验名称：排序算法班级_______ 姓名__________ 学号______实验日期：实验机时：3 学时实验成绩：-----------------一.实验目的：1、掌握主要排序算法的思想和实现技术。

二.实验内容：1、设计一程序，要求：输入学生“软件技术基础”课的成绩（学号、姓名、平均成绩、总学分）；按总学分对学生数据进行排序。

（要求：实现任选3种排序算法）三.程序：1、程序规范（输入数据、功能、输出数据）2、设计分析（数据表示、算法）3、C源代码（电子版）四.程序调试：第二篇：《数据结构》上机作业——实验报告(六)“计算机软件技术基础”课程实验报告（六）实验名称：数据库及SQL语言班级_______ 姓名__________ 学号______实验日期：实验机时：3 学时实验成绩：-----------------一.实验目的：1、学习数据库设计的一般过程及相关技术；2、学习access数据库管理系统；3、掌握数据库的输入、查询、更新操作。

二.实验内容：1、需求陈述：某校图书馆要建立一个图书数据管理系统。

该图书馆的图书（书名、分类号、作者、出版社）存放在不同的借阅室（室名），读者（姓名、系名、类别）在书架上找到所需图书后，可以到服务台办理借阅（借阅时间）。

设计要求：λ分析需求，建立数据库的概念模型；λ将概念模型转换为关系模型（注意：是否需要作规范化处理）；λ写出创建基本表的SQL语句；λ写出以下查询要求的SQL语句：（1）所有“高等数学习题集”书的信息；（2）读者“李林”借了什么书？（3）“社会学原理”在哪个借阅室？2、在access数据库管理系统中建立所设计的关系表；3、向各表中输入一组实验数据（元组）（注意：关系完整性）；4、对数据库进行查询。

三.实验结果：1、实体-关系图；2、数据库表；3、创建基本表的语句；4、查询语句。

实验名称：数据结构实验实验时间：2021年X月X日实验地点：计算机实验室实验目的：1. 理解并掌握基本数据结构（线性表、栈、队列、链表、树、图）的概念和操作。

2. 能够运用C语言实现基本数据结构的各种操作。

3. 培养编程能力和问题解决能力。

实验内容：1. 线性表2. 栈3. 队列4. 链表5. 树6. 图实验环境：1. 操作系统：Windows 102. 编程语言：C语言3. 开发环境：Visual Studio 2019实验步骤：一、线性表1. 实现线性表的创建、插入、删除、查找和遍历等基本操作。

2. 编写代码，实现以下功能：- 创建一个线性表，包含10个元素。

- 在第3个位置插入一个新元素。

- 删除第5个位置的元素。

- 查找线性表中的第7个元素。

- 遍历线性表，并打印所有元素。

二、栈1. 实现栈的创建、入栈、出栈、判空和求栈顶元素等基本操作。

2. 编写代码，实现以下功能：- 创建一个栈。

- 向栈中依次入栈元素1、2、3、4、5。

- 判断栈是否为空。

- 求栈顶元素。

- 出栈元素，并打印出栈的元素。

三、队列1. 实现队列的创建、入队、出队、判空和求队头元素等基本操作。

2. 编写代码，实现以下功能：- 创建一个队列。

- 向队列中依次入队元素1、2、3、4、5。

- 判断队列是否为空。

- 求队头元素。

- 出队元素，并打印出队的元素。

四、链表1. 实现单链表、双向链表和循环链表的创建、插入、删除、查找和遍历等基本操作。

2. 编写代码，实现以下功能：- 创建一个单链表，包含元素1、2、3、4、5。

- 在第2个位置插入一个新元素。

- 删除第3个位置的元素。

- 查找链表中的第4个元素。

- 遍历链表，并打印所有元素。

五、树1. 实现二叉树的创建、插入、删除、查找和遍历等基本操作。

2. 编写代码，实现以下功能：- 创建一个二叉树，包含元素1、2、3、4、5。

- 在第2个位置插入一个新元素。

- 删除第3个位置的元素。

图用0和1表示是否相邻，对于有向图有向网用权值类型表示InfoType* info; //该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct {//点的值char name;char* data;}VertexType[MAX_VERTEX_NUM];typedef struct{VertexType vexs; //顶点向量AdjMatrix arcs; //邻接矩阵int vexnum; //图的当前顶点数int arcnum; //图的当前弧数GraphKind kind; //图的种类标志}MGraph;//***********************以下操作默认是无向网，即Kind = AG**************************//***********************顶点是名称字母。

书上的是数字，例如v************************Status LocateVex(MGraph G,char u){if(G.vexnum == 0) return -1; //图不存在int i;for(i = 0;i < G.vexnum;i++)if(G.vexs[i].name == u)return i;return -2; //图中不存在与u相等的点}Status CreateGraph(MGraph& G){int i,j,k;VRType w;char v1,v2;char data[50];cout << "你想要创建几个顶点？ " << endl;cin >> G.vexnum;cout << "你想要创建几条弧？ " << endl;cin >> G.arcnum;cout << "依次输入顶点名称:" << endl;for(i = 0;i < G.vexnum;i++)cin >> G.vexs[i].name; //构造顶点向量for(i = 0;i < G.vexnum;i++)for(j = 0;j < G.vexnum;j++){G.arcs[i][j].adj = INFINITY; //初始化邻接矩阵G.arcs[i][j].info = NULL;}for(k = 0;k < G.arcnum;k++){ //构造邻接矩阵cout << "输入一条边依附的两个顶点: ";cin >> v1 >> v2;cout << "输入这条边的权值: " << endl;cin >> w;cout << "输入这条边的信息: " << endl;cin >> data;i = LocateVex(G,v1);j = LocateVex(G,v2);G.arcs[i][j].adj = w;G.arcs[i][j].info = data;G.arcs[j][i] = G.arcs[i][j];}return 1;}Status DestroyGraph(MGraph& G){G.vexnum = NULL;G.arcnum = NULL;return 1;}char* GetVex(MGraph G,char v){if(G.vexnum == 0) return NULL;int i;i = LocateVex(G,v);if(i >= 0) //判断是否是图上的顶点，后面的函数省略了这一步return G.vexs[i].data;elsereturn NULL;}Status PutVex(MGraph& G,char v,char* value){if(G.vexnum == 0) return 0;int i;i = LocateVex(G,v);G.vexs[i].data = value;return 1;}//VertexType FirstAdjVex(MGraph G,char v) {}//返回第一个邻接顶点，邻接表操作//VertexType NextAdjVex(MGraph G,char v,char w) {} //邻接表操作Status InsertVex(MGraph& G,char v){if(G.vexnum == 0) return 0;int i;G.vexs[G.vexnum].name = v;G.vexnum++;for(i = 0;i < G.vexnum;i++){G.arcs[i][G.vexnum - 1].adj = INFINITY;G.arcs[G.vexnum - 1][i].adj = INFINITY;}return 1;}Status DeleteVex(MGraph& G,char v){if(G.vexnum == 0) return 0;int i,j,k;k = LocateVex(G,v);for(i = 0,j = 0;i < G.vexnum;i++)if(G.arcs[i][k].adj != INFINITY)j++;for(i = k;i < G.vexnum - 1;i++)G.vexs[i] = G.vexs[i+1];G.vexs[i].name = NULL;G.vexs -> data = NULL;G.vexnum--;G.arcnum = G.arcnum - j;return 1;}Status InsertArc(MGraph& G,char v,char w){ if(G.vexnum == 0) return 0;int i,j;VRType q;char data[50];i = LocateVex(G,v);j = LocateVex(G,w);cout << "输入这条边的权值: " << endl;cin >> q;cout << "输入这条边的信息: " << endl;cin >> data;G.arcs[i][j].adj = q;G.arcs[i][j].info = data;G.arcs[j][i] = G.arcs[i][j];G.arcnum = G.arcnum + 2;return 1;}Status DeleteArc(MGraph& G,char v,char w){if(G.vexnum == 0) return 0;int i,j;i = LocateVex(G,v);j = LocateVex(G,w);G.arcs[i][j].adj = INFINITY;G.arcs[i][j].info = NULL;G.arcs[j][i] = G.arcs[i][j];G.arcnum = G.arcnum - 2;return 1;}Status Print(MGraph G){int i,j;for(i = 0;i < G.vexnum ;i++){for(j = 0;j < G.vexnum ;j++)cout << G.arcs [i][j].adj << " ";cout << endl;}return 1;}int main(){int j;char i,c,d;MGraph G;CreateGraph(G);cout << "此时矩阵为: " << endl;Print(G);cout << "输入i：:";cin >> i;j = LocateVex(G,i);cout << "i为第"<< j+1 << "个顶点" << endl;cout << "为两个点添加边，输入添加边的两个顶点: " << endl;cin >> c >> d;InsertArc(G,c,d);cout << "此时矩阵为: " << endl;Print(G);DeleteArc(G,c,d);cout << "添加顶点V；" << endl;cout << "此时矩阵为: " << endl;Print(G);c = 'V';InsertVex(G,c);cout << "此时矩阵为: " << endl;Print(G);cout << "删除顶点B；" << endl;d = 'B';DeleteVex(G,d);cout << "此时矩阵为: " << endl;Print(G);DestroyGraph(G);return 0;}运行结果：2、题目：2. 哈夫曼树的建立。

数据结构实验报告一、实验题目树和二叉树的应用二、实验内容哈夫曼编码设计三、实验目的掌握树和二叉树的概念及工作原理，运用其原理及概念完成上述实验题中的内容。

四、实验要求为了使学生更好的掌握与理解课堂上老师所讲的概念与原理，实验前每个学生要认真预习所做的实验内容及编写源程序伪码（写在纸上及盘中均可）以便在实验课中完成老师所布置的实验内容。

五、实验代码#include<stdio.h>#include<stdlib.h>#include<string.h>#define NAMEMAX 20#define CODEMAX 30typedef unsigned int UINT;typedef char NAME[NAMEMAX];typedef char CODE[CODEMAX];typedef struct{NAME name;CODE code;UINT weight;UINT parent,lchild,rchild;}HTNode,*HuffmanTree;void menu();void input();void HuffmanCoding(HuffmanTree *HT,NAME *str,int *w,int n);void menu(){int select;system("cls");printf("\t哈夫曼树的应用\n");printf("[1]输入哈弗曼树的基本情况并查找\n");printf("[2]退出\n");printf("请输入你的选项(1--2)：");scanf("%d",&select);switch(select){case 1:input();break;case 2:exit(0);break;}}void input(){HuffmanTree HT;int *w,n,i;NAME *str;char temp[50];system("cls");printf("请输入权值的个数(>1): ");scanf("%d",&n);w=(int*)malloc(n*sizeof(int));str=(NAME*)malloc(n*sizeof(NAME));printf("请依次输入%d个符号(回车分隔):\n",n);for(i=0;i<n;i++)scanf("%s",str[i]);printf("请依次输入%d个权值(整型):\n",n);for(i=0;i<n;i++)scanf("%d",w+i);HuffmanCoding(&HT,str,w,n);for(i=1;i<=n;i++)printf("%s---%s\n",HT[i].name,HT[i].code); printf("请输入你要查的字符\n");scanf("%s",temp);for(i=1;i<=n;i++)if(!strcmp(HT[i].name,temp))printf("%s\n",HT[i].code); printf("请输入你要查的编码\n");scanf("%s",temp);for(i=1;i<=n;i++)if(!strcmp(HT[i].code,temp))printf("%s\n",HT[i].name); printf("\n按回车键返回主菜单……\n");getchar();menu();}int minnode(HuffmanTree t,int i){int j,flag;unsigned int k=0xffffffff;for(j=1;j<=i;j++)if(t[j].weight<k&&t[j].parent==0)k=t[j].weight,flag=j;t[flag].parent=1;return flag;}void select(HuffmanTree t,int i,int *s1,int *s2){int j;*s1=minnode(t,i);*s2=minnode(t,i);if(*s1>*s2){j=*s1;*s1=*s2;*s2=j;}}void HuffmanCoding(HuffmanTree *HT,NAME *str,int *w,int n) {int i,s1,s2,start;unsigned c,f;HuffmanTree p;char *cd;if(n<=1||n>CODEMAX)return;*HT=(HuffmanTree)malloc(2*n*sizeof(HTNode));for(p=*HT+1,i=1;i<=n;++i,++p,++w){strcpy((*p).name,str[i-1]);(*p).weight=*w;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;}for(;i<=2*n-1;++i,++p)(*p).parent=0;for(i=n+1;i<2*n;++i){select(*HT,i-1,&s1,&s2);(*HT)[s1].parent=(*HT)[s2].parent=i;(*HT)[i].lchild=s1;(*HT)[i].rchild=s2;(*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;}cd=(char*)malloc(n*sizeof(char));cd[n-1]=0;for(i=1;i<=n;i++){start=n-1;for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent) {if((*HT)[f].lchild==c)cd[--start]='0';else cd[--start]='1';}strcpy((*HT)[i].code,&cd[start]);}free(cd);}int main(){menu();return 0;}六、实验结果。

/*文件名:algo2-1.cpp*/#include <stdio.h>#include <malloc.h>#define MaxSize 50typedef char ElemType;typedef struct{ElemType elem[MaxSize];int length;} SqList;void InitList(SqList *&L){L=(SqList *)malloc(sizeof(SqList));L->length=0;}void DestroyList(SqList *L){free(L);}int ListEmpty(SqList *L){return(L->length==0);}int ListLength(SqList *L){return(L->length);}void DispList(SqList *L){int i;if (ListEmpty(L)) return;for (i=0;i<L->length;i++)printf("%c",L->elem[i]);printf("\n");}int GetElem(SqList *L,int i,ElemType &e) {if (i<1 || i>L->length)return 0;e=L->elem[i-1];return 1;}int LocateElem(SqList *L, ElemType e) { int i=0;while (i<L->length && L->elem[i]!=e) i++;if (i>=L->length)return 0;elsereturn i+1;}int ListInsert(SqList *&L,int i,ElemType e){int j;if (i<1 || i>L->length+1)return 0;i--; /*将顺序表位序转化为elem下标*/for (j=L->length;j>i;j--) /*将elem[i]及后面元素后移一个位置*/ L->elem[j]=L->elem[j-1];L->elem[i]=e;L->length++; /*顺序表长度增1*/return 1;}int ListDelete(SqList *&L,int i,ElemType &e){int j;if (i<1 || i>L->length)return 0;i--; /*将顺序表位序转化为elem下标*/e=L->elem[i];for (j=i;j<L->length-1;j++)L->elem[j]=L->elem[j+1];L->length--;return 1;}/*文件名:algo2-2.cpp*/#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct LNode /*定义单链表结点类型*/{ElemType data;struct LNode *next;} LinkList;void InitList(LinkList *&L){L=(LinkList *)malloc(sizeof(LinkList)); /*创建头结点*/L->next=NULL;} void DestroyList(LinkList *&L){LinkList *p=L,*q=p->next;while (q!=NULL){free(p);p=q;q=p->next;}free(p);}int ListEmpty(LinkList *L){return(L->next==NULL);}int ListLength(LinkList *L){LinkList *p=L;int i=0;while (p->next!=NULL){i++;p=p->next;}return(i);}void DispList(LinkList *L){LinkList *p=L->next;while (p!=NULL){printf("%c",p->data);p=p->next;}printf("\n");}int GetElem(LinkList *L,int i,ElemType &e) {int j=0;LinkList *p=L;while (j<i && p!=NULL){j++;p=p->next;} if (p==NULL)return 0;else{e=p->data;return 1;}}int LocateElem(LinkList *L,ElemType e){LinkList *p=L->next;int n=1;while (p!=NULL && p->data!=e){p=p->next;n++;}if (p==NULL)return(0);elsereturn(n);}int ListInsert(LinkList *&L,int i,ElemType e){int j=0;LinkList *p=L,*s;while (j<i-1 && p!=NULL){j++;p=p->next;}if (p==NULL) /*未找到第i-1 个结点*/return 0;else /*找到第i-1个结点*p*/{s=(LinkList *)malloc(sizeof(LinkList)); /*创建新结点*s*/ s->data=e;s->next=p->next; /*将*s 插入到*p 之后*/p->next=s;return 1;}}int ListDelete(LinkList *&L,int i,ElemType &e){ int j=0;LinkList *p=L,*q;while (j<i-1 && p!=NULL){j++;p=p->next;}if (p==NULL) /*未找到第i-1 个结点*/return 0;else /*找到第i-1个结点*p*/{q=p->next; /*q 指向要删除的结点*/p->next=q->next; /*从单链表中删除*q 结点*/free(q); /*释放*q 结点*/return 1;}}/*文件名:algo2-3.cpp*/#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct DNode /*定义双链表结点类型*/{ElemType data;struct DNode *prior; /*指向前驱结点*/struct DNode *next; /*指向后继结点*/} DLinkList;void InitList(DLinkList *&L){L=(DLinkList *)malloc(sizeof(DLinkList)); /*创建头结点*/ L->prior=L->next=NULL;}void DestroyList(DLinkList *&L){DLinkList *p=L,*q=p->next;while (q!=NULL){free(p);p=q;q=p->next;}free(p);}int ListEmpty(DLinkList *L){ return(L->next==NULL);}int ListLength(DLinkList *L){DLinkList *p=L;int i=0;while (p->next!=NULL){i++;p=p->next;}return(i);}void DispList(DLinkList *L){DLinkList *p=L->next;while (p!=NULL){printf("%c",p->data);p=p->next;}printf("\n");}int GetElem(DLinkList *L,int i,ElemType &e) {int j=0;DLinkList *p=L;while (j<i && p!=NULL){j++;p=p->next;}if (p==NULL)return 0;else{e=p->data;return 1;}}int LocateElem(DLinkList *L,ElemType e) {int n=1;DLinkList *p=L->next;while (p!=NULL && p->data!=e) {n++;p=p->next;}if (p==NULL)return(0);elsereturn(n);}int ListInsert(DLinkList *&L,int i,ElemType e){int j=0;DLinkList *p=L,*s;while (j<i-1 && p!=NULL){j++;p=p->next;}if (p==NULL) /*未找到第i-1 个结点*/return 0;else /*找到第i-1个结点*p*/{s=(DLinkList *)malloc(sizeof(DLinkList)); /*创建新结点*s*/ s->data=e;s->next=p->next; /*将*s 插入到*p 之后*/if (p->next!=NULL) p->next->prior=s;s->prior=p;p->next=s;return 1;}}int ListDelete(DLinkList *&L,int i,ElemType &e){int j=0;DLinkList *p=L,*q;while (j<i-1 && p!=NULL){j++;p=p->next;}if (p==NULL) /*未找到第i-1 个结点*/return 0;else /*找到第i-1个结点*p*/{ q=p->next; /*q 指向要删除的结点*/if (q==NULL) return 0; /*不存在第i个结点*/p->next=q->next; /*从单链表中删除*q 结点*/if (p->next!=NULL) p->next->prior=p;free(q); /*释放*q 结点*/return 1;}void Sort(DLinkList *&head) /*双链表元素排序*/{DLinkList *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->data<p->data) /*在有序表中找插入*p 的前驱结点*q*/q=q->next;p->next=q->next; /*将*p 插入到*q 之后*/if (q->next!=NULL) q->next->prior=p;q->next=p;p->prior=q;p=r;}}}/*文件名:algo2-4.cpp*/#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct LNode /*定义单链表结点类型*/{ElemType data;struct LNode *next;} LinkList;void InitList(LinkList *&L){L=(LinkList *)malloc(sizeof(LinkList)); /*创建头结点*/L->next=L;} void DestroyList(LinkList *&L){LinkList *p=L,*q=p->next;while (q!=L){free(p);p=q;q=p->next;free(p);}int ListEmpty(LinkList *L){return(L->next==L);}int ListLength(LinkList *L){LinkList *p=L;int i=0;while (p->next!=L){i++;p=p->next;}return(i);}void DispList(LinkList *L){LinkList *p=L->next;while (p!=L){printf("%c",p->data);p=p->next;}printf("\n");}int GetElem(LinkList *L,int i,ElemType &e) {int j=0;LinkList *p;if (L->next!=L) /*单链表不为空表时*/ {if (i==1){e=L->next->data; return 1;}else /*i 不为1 时*/{p=L->next;while (j<i-1 && p!=L){j++;p=p->next;if (p==L)return 0;else{e=p->data;return 1;}}}else /*单链表为空表时*/return 0;}int LocateElem(LinkList *L,ElemType e){LinkList *p=L->next;int n=1;while (p!=L && p->data!=e){p=p->next;n++;}if (p==L)return(0);elsereturn(n);}int ListInsert(LinkList *&L,int i,ElemType e){int j=0;LinkList *p=L,*s;if (p->next==L || i==1) /*原单链表为空表或i==1时*/{s=(LinkList *)malloc(sizeof(LinkList)); /*创建新结点*s*/s->data=e; s->next=p->next; /*将*s 插入到*p 之后*/ p->next=s;return 1;}else{p=L->next;while (j<i-2 && p!=L){j++;p=p->next;}if (p==L) /*未找到第i-1 个结点*/return 0;else /*找到第i-1个结点*p*/{s=(LinkList *)malloc(sizeof(LinkList)); /*创建新结点*s*/ s->data=e;s->next=p->next; /*将*s 插入到*p 之后*/p->next=s;return 1;}}}int ListDelete(LinkList *&L,int i,ElemType &e){int j=0;LinkList *p=L,*q;if (p->next!=L) /*原单链表不为空表时*/{if (i==1) /*i==1 时*/{q=L->next; /*删除第1 个结点*/L->next=q->next;free(q);return 1;}else /*i 不为1 时*/{p=L->next;while (j<i-2 && p!=L){j++;p=p->next; }if (p==L) /*未找到第i-1 个结点*/return 0;else /*找到第i-1个结点*p*/{q=p->next; /*q 指向要删除的结点*/p->next=q->next; /*从单链表中删除*q 结点*/free(q); /*释放*q 结点*/return 1;}}}else return 0;}/*文件名:algo2-5.cpp*/#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct DNode /*定义双链表结点类型*/{ElemType data;struct DNode *prior; /*指向前驱结点*/struct DNode *next; /*指向后继结点*/} DLinkList;void InitList(DLinkList *&L){L=(DLinkList *)malloc(sizeof(DLinkList)); /*创建头结点*/ L->prior=L->next=L;}void DestroyList(DLinkList *&L){DLinkList *p=L,*q=p->next;while (q!=L){free(p);p=q;q=p->next;}free(p);}int ListEmpty(DLinkList *L){return(L->next==L);}int ListLength(DLinkList *L) {DLinkList *p=L;int i=0;while (p->next!=L){i++;p=p->next;}return(i);}void DispList(DLinkList *L){DLinkList *p=L->next;while (p!=L){printf("%c",p->data);p=p->next;}printf("\n");}int GetElem(DLinkList *L,int i,ElemType &e) {int j=0;DLinkList *p;if (L->next!=L) /*双链表不为空表时*/ {if (i==1){e=L->next->data;return 1;}else /*i 不为1 时*/{p=L->next;while (j<i-1 && p!=L){j++;p=p->next;}if (p==L)return 0;else{e=p->data;return 1; }}}else /*双链表为空表时*/return 0;}int LocateElem(DLinkList *L,ElemType e) {int n=1;DLinkList *p=L->next;while (p!=NULL && p->data!=e){n++;p=p->next;}if (p==NULL)return(0);elsereturn(n);}int ListInsert(DLinkList *&L,int i,ElemType e){int j=0;DLinkList *p=L,*s;if (p->next==L) /*原双链表为空表时*/{s=(DLinkList *)malloc(sizeof(DLinkList)); /*创建新结点*s*/ s->data=e;p->next=s;s->next=p;p->prior=s;s->prior=p;return 1;}else if (i==1) /*原双链表不为空表但i=1时*/{s=(DLinkList *)malloc(sizeof(DLinkList)); /*创建新结点*s*/ s->data=e;s->next=p->next;p->next=s; /*将*s 插入到*p 之后*/s->next->prior=s;s->prior=p;return 1;}else{p=L->next;while (j<i-2 && p!=L) { j++;p=p->next;}if (p==L) /*未找到第i-1 个结点*/return 0;else /*找到第i-1个结点*p*/{s=(DLinkList *)malloc(sizeof(DLinkList)); /*创建新结点*s*/ s->data=e;s->next=p->next; /*将*s 插入到*p 之后*/if (p->next!=NULL) p->next->prior=s;s->prior=p;p->next=s;return 1;}}}int ListDelete(DLinkList *&L,int i,ElemType &e){int j=0;DLinkList *p=L,*q;if (p->next!=L) /*原双链表不为空表时*/{if (i==1) /*i==1 时*/{q=L->next; /*删除第1 个结点*/L->next=q->next;q->next->prior=L;free(q);return 1;}else /*i 不为1 时*/{p=L->next;while (j<i-2 && p!=NULL){j++;p=p->next;}if (p==NULL) /*未找到第i-1 个结点*/return 0;else /*找到第i-1个结点*p*/{q=p->next; /*q 指向要删除的结点*/ if (q==NULL) return 0; /*不存在第i个结点*/p->next=q->next; /*从单链表中删除*q 结点*/if (p->next!=NULL) p->next->prior=p;free(q); /*释放*q 结点*/return 1;}}}else return 0; /*原双链表为空表时*/}/*文件名:algo3-1.cpp*/#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct{ElemType elem[MaxSize];int top; /*栈指针*/} SqStack;void InitStack(SqStack *&s){s=(SqStack *)malloc(sizeof(SqStack)); s->top=-1;}void ClearStack(SqStack *&s){free(s);}int StackLength(SqStack *s){return(s->top+1);}int StackEmpty(SqStack *s){return(s->top==-1);}int Push(SqStack *&s,ElemType e) {if (s->top==MaxSize-1)return 0;s->top++;s->elem[s->top]=e;return 1;} int Pop(SqStack *&s,ElemType &e) {if (s->top==-1)return 0;e=s->elem[s->top];s->top--;return 1;}int GetTop(SqStack *s,ElemType &e) {if (s->top==-1)return 0;e=s->elem[s->top];return 1;}void DispStack(SqStack *s){int i;for (i=s->top;i>=0;i--)printf("%c ",s->elem[i]);printf("\n");}/*文件名:algo3-2.cpp*/#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct linknode{ElemType data; /*数据域*/ struct linknode *next; /*指针域*/ } LiStack;void InitStack(LiStack *&s){s=(LiStack *)malloc(sizeof(LiStack)); s->next=NULL;}void ClearStack(LiStack *&s){LiStack *p=s->next;while (p!=NULL){free(s);s=p;p=p->next;} }int StackLength(LiStack *s){int i=0;LiStack *p;p=s->next;while (p!=NULL){i++;p=p->next;}return(i);}int StackEmpty(LiStack *s){return(s->next==NULL);}void Push(LiStack *&s,ElemType e){LiStack *p;p=(LiStack *)malloc(sizeof(LiStack));p->data=e;p->next=s->next; /*插入*p 结点作为第一个数据结点*/ s->next=p;}int Pop(LiStack *&s,ElemType &e){LiStack *p;if (s->next==NULL) /*栈空的情况*/return 0;p=s->next; /*p 指向第一个数据结点*/e=p->data;s->next=p->next;free(p);return 1;}int GetTop(LiStack *s,ElemType &e){if (s->next==NULL) /*栈空的情况*/return 0;e=s->next->data;return 1;}void DispStack(LiStack *s) {LiStack *p=s->next;while (p!=NULL){printf("%c ",p->data);p=p->next;}printf("\n");}/*文件名:algo3-3.cpp*/#include <stdio.h>#include <malloc.h>#define MaxSize 5typedef char ElemType;typedef struct{ElemType elem[MaxSize];int front,rear; /*队首和队尾指针*/void InitQueue(SqQueue *&q){q=(SqQueue *)malloc (sizeof(SqQueue));q->front=q->rear=0;}void ClearQueue(SqQueue *&q){free(q);}int QueueEmpty(SqQueue *q){return(q->front==q->rear);}int QueueLength(SqQueue *q){return (q->rear-q->front+MaxSize)%MaxSize; }int enQueue(SqQueue *&q,ElemType e){if ((q->rear+1)%MaxSize==q->front) /*队满*/ return 0;q->rear=(q->rear+1)%MaxSize;q->elem[q->rear]=e;return 1;}int deQueue(SqQueue *&q,ElemType &e) {if (q->front==q->rear) /*队空*/return 0;q->front=(q->front+1)%MaxSize;e=q->elem[q->front];return 1;}/*文件名:algo3-4.cpp*/#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct qnode{ElemType data;struct qnode *next;} QNode;typedef struct{QNode *front;} LiQueue;void InitQueue(LiQueue *&q){q=(LiQueue *)malloc(sizeof(LiQueue));q->front=q->rear=NULL;}void ClearQueue(LiQueue *&q){QNode *p=q->front,*r;if (p!=NULL) /*释放数据结点占用空间*/ {r=p->next;while (r!=NULL){free(p);p=r;r=p->next;}}free(q); /*释放头结点占用空间*/}int QueueLength(LiQueue *q){int n=0;QNode *p=q->front;while (p!=NULL) {n++;p=p->next;}return(n);}int QueueEmpty(LiQueue *q){if (q->rear==NULL)return 1;elsereturn 0;}void enQueue(LiQueue *&q,ElemType e) {QNode *s;s=(QNode *)malloc(sizeof(QNode));s->data=e;s->next=NULL;if (q->rear==NULL) /*若链队为空,则新结点是队首结点又是队尾结点*/ q->front=q->rear=s;else{q->rear->next=s; /*将*s结点链到队尾,rear指向它*/q->rear=s;}}int deQueue(LiQueue *&q,ElemType &e){QNode *t;if (q->rear==NULL) /*队列为空*/return 0;if (q->front==q->rear) /*队列中只有一个结点时*/{t=q->front;q->front=q->rear=NULL;}else /*队列中有多个结点时*/{t=q->front;q->front=q->front->next;}e=t->data;free(t); return 1;}/*文件名:algo4-1.cpp*/#include <stdio.h>#define MaxSize 100 /*最多的字符个数*/typedef struct{ char ch[MaxSize]; /*定义可容纳MaxSize个字符的空间*/ int len; /*标记当前实际串长*/} SqString;void StrAssign(SqString &str,char cstr[]) /*str为引用型参数*/{int i;for (i=0;cstr[i]!='\0';i++)str.ch[i]=cstr[i];str.len=i;}void StrCopy(SqString &s,SqString t) /*s为引用型参数*/{int i;for (i=0;i<t.len;i++)s.ch[i]=t.ch[i];s.len=t.len;}int StrEqual(SqString s,SqString t){int same=1,i;if (s.len!=t.len) /*长度不相等时返回0*/same=0;else{for (i=0;i<s.len;i++)if (s.ch[i]!=t.ch[i]) /*有一个对应字符不相同时返回0*/same=0;}return same;}int StrLength(SqString s){return s.len;}SqString Concat(SqString s,SqString t){SqString str;int i;str.len=s.len+t.len; for (i=0;i<s.len;i++) /*将s.ch[0]～s.ch[s.len-1]复制到str*/ str.ch[i]=s.ch[i];for (i=0;i<t.len;i++) /*将t.ch[0]～t.ch[t.len-1]复制到str*/str.ch[s.len+i]=t.ch[i];return str;}SqString SubStr(SqString s,int i,int j){SqString str;int k;str.len=0;if (i<=0 || i>s.len || j<0 || i+j-1>s.len){printf("参数不正确\n");return str; /*参数不正确时返回空串*/}for (k=i-1;k<i+j-1;k++) /*将s.ch[i]～s.ch[i+j]复制到str*/str.ch[k-i+1]=s.ch[k];str.len=j;return str;}SqString InsStr(SqString s1,int i,SqString s2){int j;SqString str;str.len=0;if (i<=0 || i>s1.len+1) /*参数不正确时返回空串*/{printf("参数不正确\n");return s1;}for (j=0;j<i-1;j++) /*将s1.ch[0]～s1.ch[i-2]复制到str*/ str.ch[j]=s1.ch[j];for (j=0;j<s2.len;j++) /*将s2.ch[0]～s2.ch[s2.len-1]复制到str*/ str.ch[i+j-1]=s2.ch[j];for (j=i-1;j<s1.len;j++) /*将s1.ch[i-1]～s.ch[s1.len-1]复制到str*/ str.ch[s2.len+j]=s1.ch[j];str.len=s1.len+s2.len;return str;}SqString DelStr(SqString s,int i,int j){int k;SqString str; str.len=0;if (i<=0 || i>s.len || i+j>s.len+1) /*参数不正确时返回空串*/{printf("参数不正确\n");return str;}for (k=0;k<i-1;k++) /*将s.ch[0]～s.ch[i-2]复制到str*/str.ch[k]=s.ch[k];for (k=i+j-1;k<s.len;k++)/*将s.ch[i+j-1]～ch[s.len-1]复制到str*/ str.ch[k-j]=s.ch[k];str.len=s.len-j;return str;}SqString RepStr(SqString s,int i,int j,SqString t){int k;SqString str;str.len=0;if (i<=0 || i>s.len || i+j-1>s.len) /*参数不正确时返回空串*/{printf("参数不正确\n");return str;}for (k=0;k<i-1;k++) /*将s.ch[0]～s.ch[i-2]复制到str*/str.ch[k]=s.ch[k];for (k=0;k<t.len;k++) /*将t.ch[0]～t.ch[t.len-1]复制到str*/ str.ch[i+k-1]=t.ch[k];for (k=i+j-1;k<s.len;k++) /*将s.ch[i+j-1]～ch[s.len-1]复制到str*/ str.ch[t.len+k-j]=s.ch[k];str.len=s.len-j+t.len;return str;}void DispStr(SqString str){int i;if (str.len>0){for (i=0;i<str.len;i++)printf("%c",str.ch[i]);printf("\n");}}/*文件名:algo4-2.cpp*/#include <stdio.h>#include <malloc.h> typedef struct snode{char data;struct snode *next;} LiString;void StrAssign(LiString *&s,char t[]){int i;LiString *r,*p;s=(LiString *)malloc(sizeof(LiString));s->next=NULL;r=s;for (i=0;t[i]!='\0';i++){p=(LiString *)malloc(sizeof(LiString));p->data=t[i];p->next=NULL;r->next=p;r=p;}}void StrCopy(LiString *&s,LiString *t){LiString *p=t->next,*q,*r;s=(LiString *)malloc(sizeof(LiString));s->next=NULL;s->next=NULL;r=s;while (p!=NULL) /*将t 的所有结点复制到s*/ {q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}}int StrEqual(LiString *s,LiString *t){LiString *p=s->next,*q=t->next;while (p!=NULL && q!=NULL && p->data==q->data) {p=p->next;q=q->next;}if (p==NULL && q==NULL)return 1;elsereturn 0;} int StrLength(LiString *s){int i=0;LiString *p=s->next;while (p!=NULL){i++;p=p->next;}return i;}LiString *Concat(LiString *s,LiString *t){LiString *str,*p=s->next,*q,*r;str=(LiString *)malloc(sizeof(LiString));str->next=NULL;r=str;while (p!=NULL) /*将s 的所有结点复制到str*/ {q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}p=t->next;while (p!=NULL) /*将t 的所有结点复制到str*/{q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}return str;}LiString *SubStr(LiString *s,int i,int j){int k;LiString *str,*p=s->next,*q,*r;str=(LiString *)malloc(sizeof(LiString));str->next=NULL;r=str;if (i<=0 || i>StrLength(s) || j<0 || i+j-1>StrLength(s)){printf("参数不正确\n");return str; /*参数不正确时返回空串*/}for (k=0;k<i-1;k++) p=p->next;for (k=1;k<=j;k++) /*将s 的第i个结点开始的j 个结点复制到str*/ {q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}return str;}LiString *InsStr(LiString *s,int i,LiString *t){int k;LiString *str,*p=s->next,*p1=t->next,*q,*r;str=(LiString *)malloc(sizeof(LiString));str->next=NULL;r=str;if (i<=0 || i>StrLength(s)+1) /*参数不正确时返回空串*/{printf("参数不正确\n");return str;}for (k=1;k<i;k++) /*将s 的前i个结点复制到str*/{q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}while (p1!=NULL) /*将t 的所有结点复制到str*/{q=(LiString *)malloc(sizeof(LiString));q->data=p1->data;q->next=NULL;r->next=q;r=q;p1=p1->next;}while (p!=NULL) /*将*p 及其后的结点复制到str*/{q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}return str;} LiString *DelStr(LiString *s,int i,int j){int k;LiString *str,*p=s->next,*q,*r;str=(LiString *)malloc(sizeof(LiString));str->next=NULL;r=str;if (i<=0 || i>StrLength(s) || j<0 || i+j-1>StrLength(s)){printf("参数不正确\n");return str; /*参数不正确时返回空串*/}for (k=0;k<i-1;k++) /*将s 的前i-1 个结点复制到str*/{q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}for (k=0;k<j;k++) /*让p 沿next 跳j 个结点*/p=p->next;while (p!=NULL) /*将*p 及其后的结点复制到str*/ {q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}return str;}LiString *RepStr(LiString *s,int i,int j,LiString *t){int k;LiString *str,*p=s->next,*p1=t->next,*q,*r;str=(LiString *)malloc(sizeof(LiString));str->next=NULL;r=str;if (i<=0 || i>StrLength(s) || j<0 || i+j-1>StrLength(s)){printf("参数不正确\n");return str; /*参数不正确时返回空串*/}for (k=0;k<i-1;k++) /*将s 的前i-1 个结点复制到str*/ {q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL; r->next=q;r=q;p=p->next;}for (k=0;k<j;k++) /*让p 沿next 跳j 个结点*/p=p->next;while (p1!=NULL) /*将t 的所有结点复制到str*/ {q=(LiString *)malloc(sizeof(LiString));q->data=p1->data;q->next=NULL;r->next=q;r=q;p1=p1->next;}while (p!=NULL) /*将*p 及其后的结点复制到str*/ {q=(LiString *)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}return str;}void DispStr(LiString *s){LiString *p=s->next;while (p!=NULL){printf("%c",p->data);p=p->next;}printf("\n");}/*文件名:algo7-1.cpp*/#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct node{ElemType data; /*数据元素*/struct node *lchild; /*指向左孩子*/struct node *rchild; /*指向右孩子*/} BTNode;void CreateBTNode(BTNode *&b,char *str) /*由str串创建二叉链*/{BTNode *St[MaxSize],*p=NULL; int top=-1,k,j=0;char ch;b=NULL; /*建立的二叉树初始时为空*/ch=str[j];while (ch!='\0') /*str未扫描完时循环*/{switch(ch){case '(':top++;St[top]=p;k=1; break; /*为左结点*/case ')':top--;break;case ',':k=2; break; /*为右结点*/default:p=(BTNode *)malloc(sizeof(BTNode));p->data=ch;p->lchild=p->rchild=NULL;if (b==NULL) /*p 指向二叉树的根结点*/ b=p;else /*已建立二叉树根结点*/{switch(k){case 1:St[top]->lchild=p;break;case 2:St[top]->rchild=p;break;}}}j++;ch=str[j];}}BTNode *FindNode(BTNode *b,ElemType x) /*返回data域为x 的结点指针*/ {BTNode *p;if (b==NULL)return NULL;else if (b->data==x)return b;else{p=FindNode(b->lchild,x);if (p!=NULL)return p;elsereturn FindNode(b->rchild,x);}} BTNode *LchildNode(BTNode *p) /*返回*p 结点的左孩子结点指针*/{return p->lchild;}BTNode *RchildNode(BTNode *p) /*返回*p 结点的右孩子结点指针*/{return p->rchild;}int BTNodeDepth(BTNode *b) /*求二叉树b的深度*/{int lchilddep,rchilddep;if (b==NULL)return(0); /*空树的高度为0*/else{lchilddep=BTNodeDepth(b->lchild); /*求左子树的高度为lchilddep*/rchilddep=BTNodeDepth(b->rchild); /*求右子树的高度为rchilddep*/ return (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1);}}void DispBTNode(BTNode *b) /*以括号表示法输出二叉树*/{if (b!=NULL){printf("%c",b->data);if (b->lchild!=NULL || b->rchild!=NULL){printf("(");DispBTNode(b->lchild);if (b->rchild!=NULL) printf(",");DispBTNode(b->rchild);printf(")");}}}int BTWidth(BTNode *b) /*求二叉树b 的宽度*/{struct{int lno; /*结点的层次编号*/BTNode *p; /*结点指针*/} Qu[MaxSize]; /*定义顺序非循环队列*/int front,rear; /*定义队首和队尾指针*/int lnum,max,i,n; front=rear=0; /*置队列为空队*/ if (b!=NULL){rear++;Qu[rear].p=b; /*根结点指针入队*/Qu[rear].lno=1; /*根结点的层次编号为1*/while (rear!=front) /*队列不为空*/{front++;b=Qu[front].p; /*队头出队*/lnum=Qu[front].lno;if (b->lchild!=NULL) /*左孩子入队*/{rear++;Qu[rear].p=b->lchild;Qu[rear].lno=lnum+1;}if (b->rchild!=NULL) /*右孩子入队*/{rear++;Qu[rear].p=b->rchild;Qu[rear].lno=lnum+1;}}max=0;lnum=1;i=1;while (i<=rear){n=0;while (i<=rear && Qu[i].lno==lnum){n++;i++;}lnum=Qu[i].lno;if (n>max) max=n;}return max;}elsereturn 0;}int Nodes(BTNode *b) /*求二叉树b的结点个数*/{int num1,num2;if (b==NULL) return 0;else if (b->lchild==NULL && b->rchild==NULL) return 1;else{num1=Nodes(b->lchild);num2=Nodes(b->rchild);return (num1+num2+1);}}int LeafNodes(BTNode *b) /*求二叉树b的叶子结点个数*/ {int num1,num2;if (b==NULL)return 0;else if (b->lchild==NULL && b->rchild==NULL) return 1;else{num1=LeafNodes(b->lchild);num2=LeafNodes(b->rchild);return (num1+num2);}}/*文件名:algo8-1.cpp*/#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct lnode{ int tag; /*结点类型标识*/union{。

G->adjlist[i].firstarc=NULL;
for(i=0;i<n;i++) //检查邻接矩阵的每个元素
for(j=0;j<n;j++)
if(g.edges[i][j]!=0)
{
p=(ArcNode *)malloc(sizeof(ArcNode)); //新申请一个节点空间，就是后面的一段段小的节点
visited[p->adjvex]=1;
rear=(rear+1)%max; //又要入队了，马上要重复之前的操作了
queue[rear]=p->adjvex;
}
p=p->nextarc;
}
}
printf("\n");
}
void main()
{
int i,j;
MGraph g;
ALGraph *G; //没有定义过的邻接表类型加上*
visited[v]=1; //第一个点设为已被访问并输出，接着以他为主进行遍历
printf(" %d",v);
p=G->adjlist[v].firstarc;
while(p!=NULL)
{
if(visited[p->adjvex]==0)
DFS(G,p->adjvex);
p=p->nextarc;
typedef struct //图的定义
{
int edges[max][max]; //邻接矩阵
int n,e; //顶点数和弧数
VertexType vexs[max]; //存放定点信息
}MGraph; //图的邻接矩阵类型