数据结构上机题目
- 格式:doc
- 大小:43.50 KB
- 文档页数:8
数据结构上机题正文:一、题目描述根据给定的需求,设计并实现一个数据结构,用于解决特定的问题。
二、问题分析1、输入:a) 数据规模:给定的数据规模(例如.10^5)b) 输入格式:输入的数据格式(例如:一行一个整数)c) 输入限制:输入数据的限制条件(例如:输入整数范围在0到100之间)2、需求:a) 需求描述:具体要求及其功能(例如:实现一个栈数据结构,并完成push、pop、top等操作)b) 需求分析:对需求进行分析、理解,确定实现思路3、思路:a) 思路描述:实现的思路(例如:使用数组实现一个栈,利用栈的特点进行push、pop等操作)b) 算法分析:分析算法的时间复杂度、空间复杂度(例如:push操作的时间复杂度是O(1))三、数据结构设计1、数据结构描述:对设计的数据结构进行详细的描述、定义(例如:栈是一种先进后出的数据结构,提供push、pop等操作)2、数据结构实现:具体实现细节(例如:使用数组实现栈,使用指针实现链表等)四、主要函数设计1、函数1:函数描述、输入参数、返回值(例如:push函数用于将元素压入栈中,输入参数是要入栈的元素,返回值是操作是否成功)2、函数2:函数描述、输入参数、返回值(例如:pop函数用于将栈顶元素弹出,输入参数为空,返回值是弹出的元素)五、实验步骤1、步骤1:描述具体实验步骤、流程(例如:首先创建一个空栈)2、步骤2:描述具体实验步骤、流程(例如:依次进行push、pop等操作)3、:::六、实验结果与分析1、结果描述:实验结果(例如:对于给定的数据规模,push、pop等操作的效率)2、结果分析:对实验结果进行分析和讨论(例如:通过比较不同数据规模下的性能表现,得出结论:在较大数据规模下,该数据结构的性能较优)七、总结与展望1、总结:总结本次实验的目的、内容、方法和结果(例如:本次实验主要实现了一个栈数据结构,并验证了其性能优势)2、展望:对进一步的研究和改进提供展望(例如:可以进一步探索不同数据结构的实现方式,比较其性能差异)附件:1、附件1:示例代码实现2、附件2:示例数据集法律名词及注释:1、法律名词1:注释说明(例如:该法律名词的定义和含义)2、法律名词2:注释说明(例如:该法律名词的定义和含义)。
数据结构》上机练习题1、设有两个有序序列, 利用归并排序将它们排成有序表,并输出。
2、设有一有序序列, 从键盘输入一个数, 判别是否在序列中,如果在输出“YSE”;否则, 将它插入到序列中使它仍然有序, 并输出排序后的序列。
3、设有一有序序列,从键盘输入一个数,判别是否在序列中,如果不在,则输出“NO”,否则,将它从序列中删除它, 并输出删除后的序列。
4、从键盘输入一组任意数据,建立一个有序链表, 并从链头开始输出该链,使输出结果是有序的。
5、从键盘输入一组任意数据,建立一个包含所有输入数据的单向循环链表, 并从链表的任意开始, 依次输出该链表中的所有结点。
10、设有一个链表,(自己建立, 数据从键盘输入), 再从键盘输入一个数,判别是否在链表中, 如果不在, 则输出“ NO“,否则, 将它从链表中删除, 并输出删除后的链表。
11、设有一个链表,(自己建立, 数据从键盘输入), 再从键盘输入一个数,判别是否在链表中,如果在输出“ YSE”,否则,将它从插入到链头,并输出插入后的链表。
12、设有一个链表,(自己建立, 数据从键盘输入), 再从键盘输入一个数,判别是否在链表中,如果在输出“ YSE”,否则,将它从插入到链尾,并输出插入后的链表。
13、编写栈的压栈push、弹栈pop函数, 从键盘输入一组数据,逐个元素压入堆栈, 然后再逐个从栈中弹出它们并输出14、编写栈的压栈 push 、弹栈 pop 函数,用它判别() 的匹配问题 树中序遍历的结果。
树先序遍历的结果。
树后序遍历的结果。
树的总结点数。
树叶子结点数。
叉树的高度。
21、给出一个无向图的邻接矩阵 , 输出各个顶点的度。
22、给出一个有向图的邻接矩阵 , 输出各个顶点的入度与出度。
23、输入一个有序序列 , 利用折半查找来查找一个数是否在序列中 出其位置 ,否则输出“ NO ”。
24、用插入排序方法对一组数据进行排序 , 并输出每趟排序的结果。
数据结构上机实验考试标准一、评分标准:1.根据考试完成情况,参考平时上机情况评定优、良、中、及格、不及格5个档。
2.成绩分布比例近似为:优15%、良30%、中30%、及格20%、不及格<10%二、评分原则:1.充分参考平时实验完成情况,结合如下原则给出成绩;2.只完成第一题,成绩为良以下成绩(中、及格),若平时上机情况很好,可以考虑良好;3.两道题都完成,成绩为良及以上(优、良),根据完成质量和完成时间给成绩;4.如未完成任何程序,则不及格(根据平时成绩将不及格率控制在10%以下);三、监考要求:1.考试前,要求学生检查电脑是否工作正常,如果不正常及时解决,待所有考生均可正常考试后再发布试题。
2.平时上机完成的程序可以在考试过程直接调用,在考试开始前复制到硬盘当中,考试过程中可以看教材。
3.考试开始后向学生分发考题的电子文档,同时宣读试题,学生可以通过网络或磁盘拷贝试题。
4.考试开始十五分钟之后把网络断开,学生不得再使用任何形式的磁盘。
5.程序检查时,记录其完成时间和完成情况。
除检查执行情况外,还要求学生对代码进行简要讲解,核实其对代码的理解情况和设计思想,两项均合格方视为试题完成。
6.完成考试的学生须关闭电脑立刻离开考场,考试成绩由教务办统一公布,负责教师不在考试现场公布成绩。
数据结构上机实验考试题目(2011年12月23日)题目1.设C={a1,b1,a2,b2,…,a n,b n}为一线性表,采用带头结点的单链表hc(hc为C链表的头指针)存放,设计一个算法,将其拆分为两个线性表(它们都用带头结点的单链表存放),使得:A={a1,a2,…,a n},B={b n,b n-1,…,b1}。
[例] C链表为:C={1,2,3,4,5,6,7,8,9,10}拆分后的A、B链表如下:A={1,3,5,7,9},B={10,8,6,4,2}。
要求:算法的空间复杂度为O(1)。
即利用C链表原来的空间。
数据结构上机实验题:1.分裂线性表,将线性表L1中奇数存到线性表L2中,偶数存到线性表L3中2.编写递归函数,计算二叉树中叶子结点的数目。
3.编写直接插入排序测试程序4.编程实现顺序检索算法参考答案:1. 分裂线性表,将L1中奇数存到L2中,偶数存到L3中#include <stdio.h>#define N 100 /*预定义最大的数据域空间*/typedef int datatype; /*假设数据类型为整型*/typedef struct {datatype data[N]; /*此处假设数据元素只包含一个整型的关键字域*/int length; /*线性表长度*/} seqlist; /*预定义的顺序表类型*/void initseqlist(seqlist *L) //初始化表{L->length=0;}void input(seqlist *L) //输入多个数据创建表{datatype x;initseqlist(L);printf("Please input numbers,0 as end:\n");scanf("%d",&x);while (x){L->data[L->length++]=x;scanf("%d",&x);}}void print(seqlist *L){int i;for (i=0;i<L->length;i++){ printf("%5d",L->data[i]);if ((i+1)%10==0) printf("\n");}printf("\n");}/*分裂线性表,将L1中奇数存到L2中,偶数存到L3中*/void sprit(seqlist *L1,seqlist *L2,seqlist *L3){int i,j,k,len;j=0,k=0;len=L1->length-1;for (i=0;i<=len;i++){ if(L1->data[i]%2==0)L3->data[j++]=L1->data[i];else L2->data[k++]=L1->data[i];}L2->length=k;L3->length=j;}int main(){seqlist L1,L2,L3;initseqlist(&L2);initseqlist(&L3);input(&L1);sprit(&L1,&L2,&L3);print(&L1);print(&L2);print(&L3);}2.编写递归函数算法,计算二叉树中叶子结点的数目。
数据结构上机答案(c语言版)实习一:1、编写一个读入一个字符串,把它存入一个链表,并按相反的次序打印的程序。
2、设有一个单位的人员工资有如下信息:name、department、base pay、allowance、total。
现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中;再从paydata取出工资数据并给每个人的base pay增加100元,增加后将工资数据显示于屏幕(每行1人)。
请编写能够完成上述工作的程序。
代码如下:1.#include#include#includevoid main(){char x;struct node //定义个结构node{char c;struct node *next;};struct node *head,*pb,*pf,*p,*s,*t; //定义指针printf("请输入字符串,按Enter结束!\n");for(int i=0;x!='\n';i++){pb=(struct node *)malloc(sizeof(struct node));//动态分配n字节的内存空间scanf("%c",&pb->c); //输入字符x=pb->c;if(i==0){ //输入的首个字符作为头结点pfhead=pb;pf=head;}else if(pb->c!='\n'){ //如果输入的是Enter,输入终止,否则把字符依次存入链表pf->next=pb; //把输入的字符pb存在pf后,pb后为空pb->next=NULL;pf=pb;//pb赋给pf,重复上述操作p=head;}}for(;p!=NULL;p=p->next)s=p; //把指向链表的最后一个字符的指针赋给sprintf("输出结果为:\n");printf("%c",s->c);//输出链表的最后一个字符for(p=head;s!=head;)//若s==head,该链表只有一个字符。
05信管《数据结构》上机考题(A卷)
学号:姓名:成绩:
试题:建立一个数据为整型的单链表L,然后将该链表中数据域值最小的那个结点移到链表的最前端。
要求与评分标准:
第一步:建立单链表(30分)
第二步:显示该单链表(10分)
第三步:查找链表中数据域值最小的结点,并将它移到链表的最前端(50分)第四步:显示该单链表,检查上述操作是否成功(10分)
05信管《数据结构》上机考题(B卷)
学号:姓名:成绩:
试题:在一个递增有序的顺序表中插入一个元素,使插入之后仍有序。
要求与评分标准:
第一步:建立一个递增有序的顺序表,注:可以在输入数据时按递增的顺序输入(30分)
第二步:显示该顺序表(10分)
第三步:在顺序表中找到合适的位置插入指定的元素,使插入之后仍有序(50分)第四步:显示该顺序表,检查上述操作是否成功(10分)
05信管《数据结构》上机考题(C卷)
学号:姓名:成绩:
试题:已知单链表L中的元素递增有序,请用高效的办法删除L中元素值大于mink且小于maxk的所有结点(注:mink和maxk由形参给出,它们与链表的数据域同类型且mink且小于maxk)
要求与评分标准:
第一步:建立递增有序的单链表L(30分)
第二步:显示该单链表(10分)
第三步:用高效的办法删除L中元素值大于mink且小于maxk的所有结点(50分)
第四步:显示该单链表,检查上述操作是否成功(10分)。
数据结构机考题库汇总1、在下列对顺序表进行的操作中,算法时间复杂度为O(1)的是(A)。
选项A)访问第i个元素的前驱(1i=n)选项B)在第i个元素之后插入一个新元素(1=i=n)选项C)删除第i个元素(1=i=n)选项D)对顺序表中元素进行排序顺序表是随机存取结构,选项A中实质是查找第i个结点和第i一1个结点,因此时间复杂度为O(1);选项B和C插入和删除都需要移动元素,时间复杂度为O(n);选项D是排序问题,时间复杂度是O(n)~O(n2)。
2、不带头结点的单链表head为空的判定条件是(A)。
选项A)head==NULL选项B)head-next==NULL选项C)head-next==head选项D)head!=NULL在不带头结点的单链表head中,head指向第一个元素结点,head=NULL表示该链表为空。
3、在一个长度为n的顺序表中,在第i个元素之前插入一个新元素时,需向后移动(B)个元素。
选项A)n-i选项B)n-i+1选项C)n-i-1选项D)ii之前共有(i-1)个元素,所以,需移动(n-(i-1))个元素。
4、某程序的时间复杂度为(3n+nlog2n+n2+8),其数量级表示为(C)。
选项A)O(n)选项B)O(nlog2n)选项C)O(n2)选项D)O(log2n)5、在以下的叙述中,正确的是(C)。
选项A)线性表的顺序存储结构优于链表存储结构选项B)线性表的顺序存储结构适用于频繁插入删除数据元素的情况选项C)线性表的链表存储结构适用于频繁插入删除数据元素的情况选项D)线性表的链表存储结构优于顺序存储结构6、对一个具有n个元素的线性表,建立其单链表的时间复杂性为(A)。
选项A)O(n)选项B)O(1)选项C)O(n2)选项D)O(log2n)7、线性表链式存储结构的特点,哪个是错误的(C)。
选项A)逻辑上相邻的元素,其物理位置不一定相邻,元素之间的邻接关系由指针域指示选项B)链表是非随机存取存储结构,对链表的存取必须从头指针开始选项C)链表是一种动态存储结构,链表的结点可用free()申请和用malloc()释放。
目录第1章绪论——上机实验题1解析实验题1.1求素数实验题1.2求一个正整数的各位数字之和实验题1.3求一个字符串是否为回文第2章线性表——上机实验题2解析实验题2.1实现顺序表各种基本运算的算法/*文件名: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;}实验题2.2实现单链表各种基本运算的算法*文件名: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->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;}}第3章栈和队列——上机实验题3解析实验题3.1实现顺序栈各种基本运算的算法*文件名: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");}实验题3.2实现链栈各种基本运算的算法/*文件名: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");}实验题3.3实现顺序队列各种基本运算的算法/*文件名:algo3-3.cpp*/#include <stdio.h>#include <malloc.h>#define MaxSize 5typedef char ElemType;typedef struct{ElemType elem[MaxSize];int front,rear; /*队首和队尾指针*/} SqQueue;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;}实验题3.4实现链队各种基本运算的算法/*文件名: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 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;}第4章串——上机实验题4解析实验题4.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");}}实验题4.2实现链串各种基本运算的算法*文件名: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");}第5章数组和稀疏矩阵——上机实验题5解析实验题5.1求5×5阶螺旋方阵/*文件名:exp5-1.cpp*/#include <stdio.h>#define MaxLen 10void fun(int a[MaxLen][MaxLen],int n){int i,j,k=0,m;if (n%2==0) //m=én/2ùm=n/2;elsem=n/2+1;for (i=0;i<m;i++){for (j=i;j<n-i;j++){k++;a[i][j]=k;}for (j=i+1;j<n-i;j++){k++;a[j][n-i-1]=k;}for (j=n-i-2;j>=i;j--){k++;a[n-i-1][j]=k;}for (j=n-i-2;j>=i+1;j--){k++;a[j][i]=k;}}}void main(){int n,i,j;int a[MaxLen][MaxLen];printf("\n");printf("输入n(n<10):");scanf("%d",&n);fun(a,n);printf("%d阶数字方阵如下:\n",n);for (i=0;i<n;i++){for (j=0;j<n;j++)printf("%4d",a[i][j]);printf("\n");}printf("\n");}实验题5.2求一个矩阵的马鞍点/*文件名:exp5-2.cpp*/#include <stdio.h>#define M 4#define N 4void MinMax(int A[M][N]){int i,j,have=0;int min[M],max[N];for (i=0;i<M;i++) /*计算出每行的最小值元素,放入min[0..M-1]之中*/{min[i]=A[i][0];for (j=1;j<N;j++)if (A[i][j]<min[i])min[i]=A[i][j];}for (j=0;j<N;j++) /*计算出每列的最大值元素,放入max[0..N-1]之中*/{max[j]=A[0][j];for (i=1;i<M;i++)if (A[i][j]>max[j])max[j]=A[i][j];}for (i=0;i<M;i++)for (j=0;j<N;j++)if (min[i]==max[j]){printf(" A[%d,%d]=%d\n",i,j,A[i][j]); /*显示马鞍点*/have=1;}if (!have)printf("没有鞍点\n");}void main(){int i,j;int A[M][N]={{9, 7, 6, 8},{20,26,22,25},{28,36,25,30},{12,4, 2, 6}};printf("A矩阵:\n");for (i=0;i<M;i++){for (j=0;j<N;j++)printf("%4d",A[i][j]);printf("\n");}printf("A矩阵中的马鞍点:\n");MinMax(A); /*调用MinMax()找马鞍点*/}实验题5.3求两个对称矩阵之和与乘积/*文件名:exp5-3.cpp*/#include <stdio.h>#define n 4#define m 10int value(int a[],int i,int j){if (i>=j)return a[(i*(i-1))/2+j];elsereturn a[(j*(j-1))/2+i];}void madd(int a[],int b[],int c[n][n]){int i,j;for (i=0;i<n;i++)for (j=0;j<n;j++)c[i][j]=value(a,i,j)+value(b,i,j);}void mult(int a[],int b[],int c[n][n]){int i,j,k,s;for (i=0;i<n;i++)for (j=0;j<n;j++){s=0;for (k=0;k<n;k++)s=s+value(a,i,k)*value(b,k,j); c[i][j]=s;}}void disp1(int a[]){int i,j;for (i=0;i<n;i++){for (j=0;j<n;j++)printf("%4d",value(a,i,j));printf("\n");}}void disp2(int c[n][n]){int i,j;for (i=0;i<n;i++){for (j=0;j<n;j++)printf("%4d",c[i][j]);printf("\n");}}void main(){int a[m]={1,2,3,4,5,6,7,8,9,10};int b[m]={1,1,1,1,1,1,1,1,1,1};int c1[n][n],c2[n][n];madd(a,b,c1);mult(a,b,c2);printf("\n");printf("a矩阵:\n");disp1(a);printf("b矩阵:\n");disp1(b);printf("a+b:\n");disp2(c1);printf("a*b:\n");disp2(c2);printf("\n");}实验题5.4实现稀疏矩阵(采用三元组表示)的基本运算/*文件名:exp5-4.cpp*/#include <stdio.h>#define N 4typedef int ElemType;#define MaxSize 100 /*矩阵中非零元素最多个数*/ typedef struct{ int r; /*行号*/int c; /*列号*/ElemType d; /*元素值*/} TupNode; /*三元组定义*/typedef struct{ int rows; /*行数值*/int cols; /*列数值*/int nums; /*非零元素个数*/TupNode data[MaxSize];} TSMatrix; /*三元组顺序表定义*/void CreatMat(TSMatrix &t,ElemType A[N][N]){int i,j;t.rows=N;t.cols=N;t.nums=0;for (i=0;i<N;i++){for (j=0;j<N;j++)if (A[i][j]!=0){t.data[t.nums].r=i;t.data[t.nums].c=j;t.data[t.nums].d=A[i][j];t.nums++;}}}void DispMat(TSMatrix t){int i;if (t.nums<=0)return;printf("\t%d\t%d\t%d\n",t.rows,t.cols,t.nums);printf("\t------------------\n");for (i=0;i<t.nums;i++)printf("\t%d\t%d\t%d\n",t.data[i].r,t.data[i].c,t.data[i].d); }void TranMat(TSMatrix t,TSMatrix &tb){int p,q=0,v; /*q为tb.data的下标*/tb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums;if (t.nums!=0){for (v=0;v<t.cols;v++) /*tb.data[q]中的记录以c 域的次序排列*/for (p=0;p<t.nums;p++) /*p为t.data的下标*/if (t.data[p].c==v){tb.data[q].r=t.data[p].c;tb.data[q].c=t.data[p].r;tb.data[q].d=t.data[p].d;q++;}}}int MatAdd(TSMatrix a,TSMatrix b,TSMatrix &c){int i=0,j=0,k=0;ElemType v;if (a.rows!=b.rows || a.cols!=b.cols)return 0; /*行数或列数不等时不能进行相加运算*/c.rows=a.rows;c.cols=a.cols; /*c的行列数与a的相同*/while (i<a.nums && j<b.nums) /*处理a和b中的每个元素*/{if (a.data[i].r==b.data[j].r) /*行号相等时*/{if(a.data[i].c<b.data[j].c) /*a元素的列号小于b 元素的列号*/{c.data[k].r=a.data[i].r;/*将a元素添加到c中*/c.data[k].c=a.data[i].c;c.data[k].d=a.data[i].d;k++;i++;}else if (a.data[i].c>b.data[j].c)/*a元素的列号大于b元素的列号*/{c.data[k].r=b.data[j].r; /*将b元素添加到c中*/c.data[k].c=b.data[j].c;c.data[k].d=b.data[j].d;k++;j++;}else /*a元素的列号等于b元素的列号*/{v=a.data[i].d+b.data[j].d;if (v!=0) /*只将不为0的结果添加到c中*/{c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=v;k++;}i++;j++;}}else if (a.data[i].r<b.data[j].r) /*a元素的行号小于b元素的行号*/{c.data[k].r=a.data[i].r; /*将a元素添加到c中*/c.data[k].c=a.data[i].c;c.data[k].d=a.data[i].d;k++;i++;}else /*a元素的行号大于b元素的行号*/{c.data[k].r=b.data[j].r; /*将b元素添加到c中*/c.data[k].c=b.data[j].c;c.data[k].d=b.data[j].d;k++;j++;}c.nums=k;}return 1;}int value(TSMatrix c,int i,int j){int k=0;while (k<c.nums && (c.data[k].r!=i || c.data[k].c!=j))k++;if (k<c.nums)return(c.data[k].d);elsereturn(0);}int MatMul(TSMatrix a,TSMatrix b,TSMatrix &c){int i,j,k,p=0;ElemType s;if (a.cols!=b.rows) /*a的列数不等于b的行数时不能进行相乘运算*/return 0;for (i=0;i<a.rows;i++)for (j=0;j<b.cols;j++){s=0;for (k=0;k<a.cols;k++)s=s+value(a,i,k)*value(b,k,j);if (s!=0) /*产生一个三元组元素*/{c.data[p].r=i;c.data[p].c=j;c.data[p].d=s;p++;}}c.rows=a.rows;c.cols=b.cols;c.nums=p;return 1;}void main(){ElemType a1[N][N]={{1,0,3,0},{0,1,0,0},{0,0,1,0},{0,0,1,1}};ElemType b1[N][N]={{3,0,0,0},{0,4,0,0},{0,0,1,0},{0,0,0,2}};TSMatrix a,b,c;CreatMat(a,a1);CreatMat(b,b1);printf("a的三元组:\n");DispMat(a);printf("b的三元组:\n");DispMat(b);printf("a转置为c\n");TranMat(a,c);printf("c的三元组:\n");DispMat(c);printf("c=a+b\n");MatAdd(a,b,c);printf("c的三元组:\n");DispMat(c);printf("c=a*b\n");MatMul(a,b,c);printf("c的三元组:\n");DispMat(c);}实验题5.5实现广义表的基本运算#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct lnode{ int tag; /*结点类型标识*/ union{ElemType data;struct lnode *sublist;}val;struct lnode *link; /*指向下一个元素*/} GLNode;extern GLNode *CreatGL(char *&s);extern void DispGL(GLNode *g);void Change(GLNode *&g,ElemType s,ElemType t) /*将广义表g中所有原子s 替换成t*/{if (g!=NULL){if (g->tag==1) /*子表的情况*/Change(g->val.sublist,s,t);else if (g->val.data==s) /*原子且data域值为s的情况*/g->val.data=t;Change(g->link,s,t);}}void Reverse(GLNode *&g) /*将广义表g所有元素逆置*/{GLNode *p,*q,*t;t=NULL;if (g!=NULL){p=g;while (p!=NULL) /*将同级的兄弟逆置*/{q=p->link;if (t==NULL){t=p;p->link=NULL;}else{p->link=t;t=p;}p=q;}g=t;p=g;while (p!=NULL){if (p->tag==1)Reverse(p->val.sublist);p=p->link;}}}int Same(GLNode *g1,GLNode *g2) /*判断两个广义表是否相同*/ {int s;if (g1==NULL && g2==NULL) /*均为NULL的情况*/return 1;else if ((g1==NULL && g2!=NULL) || (g1!=NULL && g2==NULL)) /*一个为NULL,另一不为NULL的情况*/return 0;else{s=1;while (g1!=NULL && g2!=NULL && s==1){if (g1->tag==1 && g2->tag==1)/*均为子表的情况*/s=Same(g1->val.sublist,g2->val.sublist);else if (g1->tag==0 && g2->tag==0)/*均为原子的情况*/{if (g1->val.data!=g2->val.data)s=0;}else /*一个为原子,另一为子表的情况*/s=0;g1=g1->link;g2=g2->link;}if (g1!=NULL || g2!=NULL) /*有一个子表尚未比较完时*/s=0;return s;}}ElemType MaxAtom(GLNode *g) /*求广义表g中最大的原子*/{ElemType m=0,m1; /*m赋初值0*/while (g!=NULL){if (g->tag==1) /*子表的情况*/{m1=MaxAtom(g->val.sublist); /*对子表递归调用*/if (m1>m) m=m1;}else{if (g->val.data>m) /*为原子时,进行原子比较*/m=g->val.data;}g=g->link;}return m;}void DelAtom(GLNode *&g,ElemType x) /*删除广义表g中的第一个为x原子*/{GLNode *p=g,*q,*pre;while (p!=NULL){q=p->link;if (p->tag==1) /*子表的情况*/DelAtom(p->val.sublist,x); /*对子表递归调用*/else{if (p->val.data==x) /*为原子时,进行原子比较*/{if (p==g)/*被删结点是本层的第1个结点*/{g=q;free(p); /*释放结pre=g;}else /*被删结{pre->link=q;free(p);}return;}}pre=p;p=q;}}void DelAtomAll(GLNode *&g,ElemType x) /*删除广义表g中的所有为x原子*/{GLNode *p=g,*q,*pre;while (p!=NULL){q=p->link;if (p->tag==1) /*子表的情况*/DelAtomAll(p->val.sublist,x); /*对子表递归调用*/else{if (p->val.data==x) /*为原子时,进行原子比较*/if (p==g)/*被删结点是本层的第1个结点*/{g=q;free(p); /*释放结pre=g;}else /*被删结{pre->link=q;free(p);}}pre=p;p=q;}}void PreOrder(GLNode *g) /*采用先根遍历g*/{if (g!=NULL){if (g->tag==0) /*为原子结点时*/printf("%c ",g->val.data);elsePreOrder(g->val.sublist); /*为子表时*/ PreOrder(g->link);}}void main(){GLNode *g1,*g2,*g3,*g4;char *str1="(a,(a),((a,b)),((a)),a)";char *str2="(a,(b),((c,d)),((e)),f)";char *str3="(a,(a,b),(a,b,c)))";char *str4="(a,(b),((c,d)),((e)),f)";g1=CreatGL(str1);printf("\n");printf(" 广义表g1:");DispGL(g1);printf("\n");printf(" 将广义表g1中所有'a'改为'b'\n");Change(g1,'a','b');printf(" 广义表g1:");DispGL(g1);printf("\n\n");g2=CreatGL(str2);printf(" 广义表g2:");DispGL(g2);printf("\n");printf(" 广义表g2中最大原子:%c\n",MaxAtom(g2));printf(" 将g2的元素逆置\n");Reverse(g2);printf(" 广义表g2:");DispGL(g2);printf("\n\n");printf(" 广义表g1和g2%s\n\n",(Same(g1,g2)?"相同":"不相同"));g3=CreatGL(str3);printf(" 广义表g3:");DispGL(g3);printf("\n");printf(" 删除广义表g3的第一个为'a'的原子\n");DelAtom(g3,'a');printf(" 广义表g3:");DispGL(g3);printf("\n\n");printf(" 删除广义表g3中的所有'a'原子\n");DelAtomAll(g3,'a');printf(" 广义表g3:");DispGL(g3);printf("\n\n");g4=CreatGL(str4);printf(" 广义表g4:");DispGL(g4);printf("\n");printf(" 采用先根遍历g4的结果:");PreOrder(g4);printf("\n\n");}。
数据结构上机题目第二次:sqlist-顺序表2.11 设顺序表va中的数据元素递增有序。
试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性。
2.21 试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表(a1,a2,…,an)逆置为(an,an-1,…,a1)。
第三次:LinkList-单链表2.15已知指针ha和hb分别指向两个单链表的头结点,并且已知两个链表的长度分别为m和n。
试写一算法将这两个链表连接在一起(即令其中一个表的首元结点连在另一个表的最后一个结点之后),假设指针hc 指向连接后的链表的头结点,并要求算法以尽可能短的时间完成连接运算。
请分析你的算法的时间复杂度。
2.19已知线性表中的元素以值递增有序排列,并以单链表作存储结构。
试写一高效的算法,删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素),同时释放被删结点空间,并分析你的算法的时间复杂度(注意,mink和maxk是给定的两个参变量,它们的值可以和表中的元素相同,也可以不同)。
第四次:cdLinkList-循环链表2.33已知由一个线性链表表示的线性表中含有三类字符的数据元素(如:字母字符、数字字符和其他字符),试编写算法将该线性表分割为三个循环链表,其中每个循环链表表示的线性表中均只含一类字符。
2.38设有一个双向循环链表,每个结点中除有prior,data和next 三个域外,还增设了一个访问频度域freq。
在链表被起用之前,频度域freq的值均初始化为零,而每当对链表进行一次LOCATE(L,x)的操作后,被访问的结点(即元素值等于x的结点)中的频度域freq的值便增1,同时调整链表中结点之间的次序,使其按访问频度非递增的次序顺序排列,以便始终保持被频繁访问的结点总是靠近表头结点。
试编写符合上述要求的LOCATE操作的算法。
第五次:outqueue-实验1线性表实验目的熟悉线性表的基本运算在顺序存储结构和链式存储结构上的实现,其中重点熟悉链表的各种操作。
当涉及数据结构的上机实验题时,通常会涉及编程和算法的实践。
以下是一些可能的
上机实验题目:
1. 实现一个栈(Stack)数据结构,并编写基本的操作(入栈、出栈、获取栈顶元素等)。
2. 实现一个队列(Queue)数据结构,并编写基本的操作(入队、出队等)。
3. 实现一个链表(Linked List)数据结构,并编写插入、删除、查找等操作。
4. 实现一个二叉树(Binary Tree)数据结构,并编写遍历算法(前序、中序、后序遍历)。
5. 实现一个图(Graph)数据结构,并编写基本的图算法(深度优先搜索、广度优先搜索)。
6. 实现一个哈希表(Hash Table)数据结构,并编写插入、删除、查找等操作。
这些实验题目可以帮助学生加深对数据结构的理解,并通过编程实践来掌握数据结构
的基本操作和算法。
同时,这些实验也有助于提高学生的编程能力和解决问题的能力。
数据结构上机试题一、顺序表的操作(1)插入元素操作:将新元素x插入到顺序表a中第i个位置。
(2)删除元素操作:删除顺序表a中第i个元素。
#include<iostream.h>#include<stdlib.h>#define MAX 100;typedef struct{int data[100];int length;}sqlist;void init(sqlist &a)//线性表初始化{a.length=0;}void insert(sqlist &a ,int i,int x)// 插入元素操作{int j;if(i<0||i>a.length+1||a.length==100);else{for(j=a.length+1;j>i;j--)a.data[j]=a.data[j-1];a.data[j]=x;a.length++;}}void deleted(sqlist &a ,int i)// 删除元素操作{int j;if(i<0&&i>a.length);else{for(j=i;j<a.length;j++)a.data[j]=a.data[j+1];a.length--;}}void main(){sqlist a;//线性表为aint i,e,x,n,j,s;//i插入位置,e动态建线性表要用,X插入元素,n表长init(a);//构造一个空表cout<<"输入表长n: ";cin>>n;cout<<"输入表长为"<<n<<" 个数: ";for(j=0;j<n;++j){cin>>e;insert(a,j,e);}cout<<"插入前: ";for(j=0;j<a.length ;j++)cout<<a.data[j]<<" ";cout<<"输入要插入位置i: ";cin>>i;cout<<"输入要插入的元素x: ";cin>>x;cout<<"打算在第"<<i<<"个位置插入元素"<<x ; insert(a,i-1,x);//由于从0开始,要构造显示从一开始,所以减1cout<<"插入后结果: ";for(j=0;j<a.length;j++)cout<<a.data[j]<<" ";cout<<"输入要删除的位置s: ";cin>>s;deleted(a,s-1);//由于从0开始,要构造显示从一开始,所以减1cout<<"删除后结果: ";for(j=0;j<a.length;j++)cout<<a.data[j]<<" ";}二、单链表的操作(1)创建一个带头结点的单链表;(2)插入元素操作:将新元素x插入到单链表中第i 个元素之后;(3)删除元素操作:删除单链表中值为x的元素;#include<iostream.h>#include<stdlib.h>typedef struct LNode{int data;struct LNode *next;}LNode;//创建一个带头结点的长度长度长度为n的链表L;void createlist(LNode *&L ,int n){int i;LNode *p;L=(LNode *)malloc(sizeof(LNode));L->next=NULL;for(i=1;i<=n;i++){p=(LNode *)malloc(sizeof(LNode));cout<<"请输入链表第"<<i<<"个元素";cin>>p->data;p->next=L->next;L->next=p;}}//插入元素操作:将新元素x插入到单链表L中第i个元素之后void insert(LNode *&L ,int i,int x){int j=0;LNode *p,*q;p=L;while(p->next!=NULL){j++;if(j==i){q=(LNode *)malloc(sizeof(LNode));//找到位置q->data=x;//放入数据q->next=p->next;p->next=q;break;}p=p->next;}if(p->next==NULL){q=(LNode *)malloc(sizeof(LNode));//找到位置q->data=x;//放入数据q->next=p->next;p->next=q;}}//删除元素操作:删除单链表中值为x的元素;void deleted(LNode *&L ,int x){LNode *p,*q;p=L;while(p->next!=NULL){if(p->next->data==x){q=p->next;p->next=p->next->next;free(q);}p=p->next;}}void print(LNode *&L){LNode *p;p=L->next;while(p!=NULL){cout<<p->data<<" ";p=p->next;}}void main(){LNode * L,*p;//节点为Lint i,x,y,s,n;//i插入位置,X插入元素,y为删除元素,n表长cout<<"输入表长n: ";cin>>n;createlist(L,n);cout<<"输出插入之前:";print(L);cout<<"请输入插入的位置i: ";cin>>i;cout<<"请输入插入的元素x: ";cin>>x;insert(L,i,x);cout<<"输出插入后:";print(L);cout<<"请输入删除的元素y: ";cin>>y;deleted(L,y);//删除元素操作:删除单链表中值为y的元素;cout<<"输出删除后:";print(L);}三、在顺序栈上实现将非负十进制数转换成二进制数#include<iostream.h>#include<stdlib.h>#define MAX 100//在顺序栈上实现将非负十进制数x转换成二进制数void conversion(int &x){int stack[MAX];int top=-1;int t;while(x){stack[++top]=x%2;x=x/2;}while(top!=-1){t=stack[top--];cout<<t;}}void main(){int x,t;cout<<"请输入你要转换的非负十进制数x:"<<endl;cin>>x;cout<<"输出转换后的二进制数:"; conversion(x);cout<<endl;}四、在顺序表中采用顺序查找算法和折半查找算法寻找关键字X在顺序表中的位置。
模拟题一、有一只猫抓了n (n>1)个老鼠后向老鼠宣布:老鼠按自然数进行编号(1~n),并按自然数顺序排队,以后先后次序不准变;于是猫每天吃掉编号为奇数的老鼠,剩下的老鼠再按原次序进行自然数编号,直至某一天只剩下一只小老鼠;而该小老鼠是猫从第一天起就想吃掉的那只,请问这只小老鼠的最初编号是几?(1)用链结构实现,链的每个节点所包含的“数据域”信息是老鼠的最初编号(从1开始编号),另一个信息是链的下一节点地址。
(2)建立一条有n个节点的链:先创建一个空链,然后向链尾插入n 个节点。
(3)开始删除奇数节点:从链首开始删除“奇”节点,直至链尾;判断链是否只剩下一个节点?不是则循环执行上一步,是则结束循环。
(4)输出结果。
(5)程序编写完成后,请以f1.c或f1.cpp作为文件名存放到F盘上。
答案:#include <iostream.h>#include <assert.h>struct mouse //链“节点”类声明{int n;mouse *nextptr;};int cat_mouse(int num) //函数定义{mouse *headptr=0,*tailptr=0,*frontptr,*p;int i;//先把1个老鼠加入链作为链首节点headptr=tailptr=new mouse;assert(headptr!=NULL); //动态内存分配异常处理headptr->n=1; //老鼠的编号headptr->nextptr=NULL;//在链尾再添加n-1个老鼠for(i=2;i<=num;++i){p=new mouse;assert(p!=NULL);p->n=i;cout<<p->n<<" ";tailptr->nextptr=p;tailptr=p;tailptr->nextptr=NULL; //设置链尾节点的“下一节点地址”为空//开始删除老鼠while(headptr!=tailptr) //每循环一次,删除链上的奇节点,直至只剩下1个节点 { p=headptr->nextptr; //链的首节点总是先被删除delete headptr; //析构首节点headptr=frontptr=p; //本次循环的第2个节点成为链的首节点 i=2; //从第2个节点开始循环:删除链的奇节点 while(p!=NULL) //从2开始循环至链尾节点{if((i%2)==1) //是奇节点{if (p->nextptr==NULL) //如果该奇节点是最后一个节点 {frontptr->nextptr=NULL; //前一节点成为链的尾节点tailptr=frontptr;delete p;p=NULL; //因本循环的判断条件是p!=NULL,到链尾,所以置为0 }else //是奇节点但不是尾节点,删除{frontptr->nextptr=p->nextptr; //从链上删除该奇节点 delete p;p=frontptr->nextptr; //下一节点的地址已保存在frontPtr的 nextPtr中 ++i;} //frontPtr成为被删节点的下一节点的上一节点,故值不变 }else //不是奇节点,不删除{frontptr=p;p=p->nextptr;++i;}}}return headptr->n; //返回最后一个节点的编号}void main() //主函数{int i, num;do{cout<<"\n请输入老鼠的只数(大于1,输入0退出):";cin>>num;if(num>1){i=cat_mouse(num);cout<<"最后剩下的一只老鼠是:"<<i<<endl;}}while(num!=0);以下为软件运行环境实效(在C++6.0中书写好的答案截图)注意点:1、考试考号和座位号(上机号)有一定的对应关系,跟老师确认后输入,以免做了成绩给了别人;2、就一大题,6.00开考,7.00结束;3、后面的截图是软件的实际操作界面,作为参考;。
《数据结构》课程实习题目实习一1、编写一个读入一个字符串,把它存入一个链表,并按相反的次序打印的程序。
2、设有一个单位的人员工资,有如下信息:name、department、base pay、allowance、total。
现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中;再从paydata取出工资数据并给每个人的base pay增加100元,增加后将工资数据显示于屏幕(每行1人)。
请编写能够完成上述工作的程序。
实习二1、试用分别用线性表的向量存储结构和链表存储结构来实现约瑟夫(Josephu)问题。
约瑟夫问题如下:设有n个人围坐圆桌周围。
从某个位置上的人开始从1报数,数到m的人便出列,下一个人(第m+1个)又从1报数开始,数到m的人便是第2个出列的人,依次类推,直到最后一个人出列为止,这样就可以得到一个人员排列的新次序。
例如,n=8,m=4,从第1个人数起,得到的新次序为48521376.实习三编写建立一个由单链表组织存储的整数序列的程序,链表中每个结点存储一个整型数值,以此为基础完成将整数b插入到该链表中第一个数值为a的结点之前的程序。
实习四采用llink-rlink方式存储二叉排序树,编写能够通过键盘输入建立二叉排序树,并在建立完立即在屏幕显示中序遍历结果的程序。
实习五对于给定的一个工程施工图,该图以边为单位从键盘输入,编写能够找出该图的关键路径的程序。
实习六假设有一个数据类型为整型的一维数组A,A 中的数据元素呈无序状态,编写一个采用堆排序法将A中的数据元素按由小到大进行排序的程序。
《数据结构》答案(答案仅供参考)实验一1、编写一个读入一个字符串,把它存入一个链表,并按相反的次序打印的程序。
#include<stdio.h>#include<malloc.h>{char ch;struct str *next;};void main(){char tem;struct str *p,*h,*s;h=malloc(sizeof(struct str));h->next=NULL;if(h!=NULL){printf("请输入一个字符:");//scanf("%c",&tem);tem=getchar();h->ch=tem;while(tem!='$'){printf("请继续输入:");s=malloc(sizeof(struct str));if(s!=NULL){tem=getchar();//scanf("%c",&tem);s->ch=tem;}if(tem=='$')free(s);else{if(h->next==NULL)h->next=s;elsep->next=s;p=s;}}p->next=NULL;}printf("字符串逆序输出为:\n");while(h->next!='\0'){p=h;while(p->next!='\0'){p=p->next;}printf("%c",p->ch);s->next='\0';}printf("%c",h->ch);printf("\n");}2、设有一个单位的人员工资,有如下信息:name、department、 base pay、allowance、total。
习题二⒉1描述以下四个概念的区别:头指针变量,头指针,头结点,首结点(第一个结点)。
解:头指针变量和头指针是指向链表中第一个结点(头结点或首结点)的指针;在首结点之前附设一个结点称为头结点;首结点是指链表中存储线性表中第一个数据元素的结点。
若单链表中附设头结点,则不管线性表是否为空,头指针均不为空,否则表示空表的链表的头指针为空。
2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。
解:顺序存储是按索引直接存储数据元素,方便灵活,效率高,但插入、删除操作将引起元素移动,降低了效率;而链式存储的元素存储采用动态分配,利用率高,但须增设表示结点之间有序关系的指针域,存取数据元素不如顺序存储方便,但结点的插入和删除十分简单。
顺序存储适用于线性表中元素数量基本稳定,且很少进行插入和删除,但要求以最快的速度存取线性表中的元素的情况;而链式存储适用于频繁进行元素动态插入或删除操作的场合。
2.3 在头结点为h的单链表中,把值为b的结点s插入到值为a的结点之前,若不存在a,就把结点s插入到表尾。
Void insert(Lnode *h,int a,int b){Lnode *p,*q,*s;s=(Lnode*)malloc(sizeof(Lnode));s->data=b;p=h->next;while(p->data!=a&&p->next!=NULL){q=p;p=p->next;}if (p->data==a){q->next=s;s->next=p;}else{p->next=s;s->next=NULL;}}2.4 设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B,使A中含有原链表中序号为奇数的元素,而B中含有原链表中序号为偶数的元素,并且保持元素原有的相对顺序。
Lnode *cf(Lnode *ha){Lnode *p,*q,*s,*hb;int t;p=ha->next;q=ha;t=0;hb=(Lnode*)malloc(sizeof(Lnode));s=hb;while(p->next!=NULL){if (t==0){q=p;p=p->next;t=1;}else{q->next=p->next;p->next=s->next; s->next=p; s=p;p=p->next; t=0;}}s->next=NULL;return (hb);}2.5设线性表中的数据元素是按值非递减有序排列的,试以不同的存储结构,编写一算法,将x插入到线性表的适当位置上,以保持线性表的有序性。
1、顺序表的插入与删除#define ListSize 10#define n 8#define Error printftypedef int DataType;typedef struct{DataType data[ListSize];int length;}seqlist;void deletelist(seqlist *L);void insertlist(seqlist *L);main(){seqlist *L=0;int i;char c;printf("请按递减顺序输入%d个整数:\n",n);for(i=0;i<n;i++)scanf("%d",&L->data[i]);L->length=n;printf("\n请选择:\n");printf("A----------------------插入------------------\n");printf("B----------------------删除------------------\n");printf("C----------------------退出------------------\n");scanf("\n%c",&c);while(c!='c'&&c!='C'){if(c=='A'||c=='a')insertlist(L);else deletelist(L);printf("当前顺序表中的数据是:\n");for(i=0;i<L->length;i++)printf("%3d",L->data[i]);printf("\n请再选择:\n");printf("A----------------------插入------------------\n");printf("B----------------------删除------------------\n");printf("C----------------------退出------------------\n");scanf("\n%c",&c);}}void insertlist(seqlist *L){int x,i,j;printf("\n请输入要插入的整数:");scanf("\n%d",&x);printf("\n在下面序列中插入%d\n",x);for(i=0;i<L->length;i++)printf("%3d",L->data[i]);i=0;while(i<L->length&&x<L->data[i])i++;if(i<0||i>L->length+1)Error("\n插入位置错误!\n");else if(L->length>=ListSize)Error("\n表溢出,无法插入!"); else if(x==L->data[i])printf("\n重复插入,不允许!\n");/*=========空白处1===========*/L->data[j+1]=l->data[j];L->data[i]=x;L->length++;/*======================*/}}void deletelist(seqlist *L){int x,i,j,num;printf("\n请输入要删除的整数:");scanf("\n%d",&x);printf("\n在下面序列中删除%d\n",x);for(i=0;i<L->length;i++)printf("%3d",L->data[i]);i=0;num=0;while(i<L->length&&x<L->data[i])i++;if(x!=L->data[i])Error("\n没找到要删除的整数!\n");else{num++;while(L->data[i+1]==x&&i<L->length-1){i++;num++;}printf("\n删除原表中从第%d个位置以后的%d个数据%d\n",i-num+1,num,x); for(j=i+1;j<=L->length-1;j++)/*=====请在下面填入相应的语句======*/L->data[j-num]=L->data[j];L->length=L->length-num;/*=====================*/}}2\ 单链表的插入与删除*/#include <stdio.h>#include <stdlib.h>#include <string.h>#define Error printf#define n 5typedef struct node{int data;struct node *next;}ListNode;typedef ListNode * LinkList;LinkList Createlinklist(void);void Insertlinklist(LinkList head);void Deletelinklist(LinkList head);void Outputlinklist(LinkList head);main(){LinkList head;char c;head=Createlinklist();printf("请选择:\n");printf("A--------------插入-----------------\n");printf("B--------------删除-----------------\n");while(c!='c'&&c!='C'){if(c=='A'||c=='a')Insertlinklist(head);else Deletelinklist(head);Outputlinklist(head);printf("\n请再选择:\n");printf("A--------------插入-----------------\n"); printf("B--------------删除-----------------\n"); printf("C--------------退出-----------------\n"); scanf("\n%c",&c);}}/*****************************/LinkList Createlinklist(){int x;LinkList head,s,r;head=(ListNode*)malloc(sizeof(ListNode));r=head;r->next=NULL;printf("请按递减顺序输入整数(输0 结束):\n"); scanf("%d",&x);while (x!=0){s=(ListNode*)malloc(sizeof(ListNode));s->data=x;s->next=r->next;r->next=s;r=s;scanf("\n%d",&x);}return head;}void Insertlinklist(LinkList head){int x;ListNode *p,*s;int i,j;printf("请输入要插入的整数:");scanf("%d",&x);p=head;j=0;while(p->next&&x<p->next->data){j++;p=p->next;}if(x==p->next->data)Error("重复插入,不允许!\n");else{s=(ListNode *)malloc(sizeof(ListNode));/*=====请在下面填入相应的语句===*/S->data=x;P->next=S;/*====================*/ }}void Deletelinklist(LinkList head){int x;ListNode *p,*r;int i,j;printf("请输入要删除的整数:");scanf("%d",&x);p=head;r=head->next;while(r&&x<r->data){ p=r;r=r->next;}if(r==NULL||x!=r->data)Error("没找到要删除的整数.\n");else{/*==========空白处2=========*/p->next=r->next;free(r);/*====================*/}}void Outputlinklist(LinkList head){ListNode *p;p=head->next;printf("当前链表中数据为:\n");while(p){printf("%6d",p->data);p=p->next;}}/*====数据结构上机考核试题3======*//* 栈的操作#define StackSize 10 #define Error printftypedef int DataType;typedef struct{DataType data[StackSize];int top;}SeqStack;void InitStack(SeqStack *s){s->top=0; }int StackEmpty(SeqStack *S){if (S->top==0)return 1;else return 0;}int StackFull(SeqStack *S){return S->top==StackSize;}void Push(SeqStack *S,DataType x){if(StackFull(S))Error("栈溢出!");/*==========空白处1============*/Else S->data[++(S->top)]=x;/*=====================*/}DataType Pop(SeqStack *S){If(StackEmpty(S))Error(“Stack underflow”);Else return S->data[--(S->top)];/*=========*/}void conversion(int N,int B);main(){int N,B;char ch;printf("进行数值转换请输入Y,退出请输入N:"); scanf("\n%c",&ch);while (ch=='Y'||ch=='y'){printf("请输入需要转换的十进制数:");scanf("%d",&N);printf("\n请输入想要转换的进制数(2,8or16):"); scanf("%d",&B);conversion(N,B);printf("继续转换请输入Y,退出请输入N:");scanf("\n%c",&ch); }}void conversion(int N,int B){ DataType i;SeqStack *S;InitStack(S);while(N){Push(S,N%B); N=N/B; }printf("转换的结果为:");while(!StackEmpty(S)){i=Pop(S);switch(i){case 10:printf("%c",'a');break;case 11:printf("%c",'b');break;case 12:printf("%c",'c');break;case 13:printf("%c",'d');break;case 14:printf("%c",'e');break;case 15:printf("%c",'f');break;default:printf("%d",i); }}printf("\n"); }/*==========数据结构上机考核试题4======*/ /* 队列的操作*/#include <stdio.h>#define QueueSize 100#define Error printftypedef char DataType;typedef struct{int front;int rear;int count;DataType data[QueueSize];}CirQueue;void InitQueue(CirQueue *Q){ Q->front=Q->rear=0;int QueueEmpty(CirQueue *Q){ return Q->count==0; }int QueueFull(CirQueue *Q){ return Q->count==QueueSize; }void EnQueue(CirQueue *Q,DataType x){ if(QueueFull(Q))Error("队列溢出!");e lse{ /*==========空白处1===========*/ Q->count++;Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%QueueSize;/*=================*/ }} DataType DeQueue(CirQueue *Q) {DataType temp;if(QueueEmpty(Q))Error("队列下溢!");else{temp=Q->data[Q->front];/*============空白处2===========*/ Q->count--;Q->front=(q->front+1)%QueueSize;/*==============*/return temp;}}void Inputch(CirQueue *Q);void Outputch(CirQueue *Q);main(){ CirQueue *Q=0;char ch;printf("\n 继续进行请按Y,退出请按N:"); scanf("\n%c",&ch);while(ch=='Y'||ch=='y'){ InitQueue(Q);Inputch(Q);Outputch(Q);printf("\n 继续进行请按Y,退出请按N:"); scanf("\n%c",&ch); }}void Inputch(CirQueue *Q){ char ch;printf("\n 请输入字符串并以$为结束符:"); scanf("%c",&ch);while(ch!='$'){ EnQueue(Q,ch);scanf("%c",&ch); }}void Outputch(CirQueue *Q){ char ch;printf("你输入的字符串是:");while(!QueueEmpty(Q)){ch=DeQueue(Q);printf("%c",ch); }printf("\n"); }/*========数据结构上机考核试题5=====*/ /* 二叉树的遍历*/DataType data;struct node *lchild,*rchild;}BinTNode;typedef BinTNode *BinTree;int count;void CreateBinTree(BinTree *T);void Levelorder(BinTree T);main(){BinTree T;char ch1,ch2;printf("\n请选择:\n");ch1='y';while(ch1=='y'||ch1=='Y'){printf("\nA------------------二叉树建立-------------");printf("\nB------------------层次遍历---------------");printf("\nC------------------退出-------------------\n");scanf("\n%c",&ch2);switch(ch2){case 'a':case 'A':printf("请按先序输入建立二叉树存储的结点序列:\n"); CreateBinTree(&T);break;case 'b':case 'B':printf("该二叉树的层次遍历序列为:\n");Levelorder(T);break;case 'c':case 'C':ch1='n';break;default:ch1='n'; }}}void CreateBinTree(BinTree *T){char ch;scanf("\n%c",&ch);if(ch=='0') *T=NULL;else {*T=(BinTNode*)malloc(sizeof(BinTNode));(*T)->data=ch;CreateBinTree(&(*T)->lchild);CreateBinTree(&(*T)->rchild); }}void Levelorder(BinTree T){int i,j;BinTNode *q[20],*p;p=T;if(p!=NULL){i=1;q[i]=p;j=2;}while(i!=j){p=q[i];printf("%3c",p->data);/*==========空白处1==============*/if(p->lchild!=NULL){q[j]=p->lchild; j++;}if(p->rchild!=NULL){q[j]=p->rchild; j++;}i++;/*===========*/}}/*======数据结构上机考核试题6========*//* 求二叉树叶子结点个数*/DataType data;struct node *lchild,*rchild;}BinTNode;typedef BinTNode *BinTree;int count;void CreateBinTree(BinTree *T);void Leafnum(BinTree T);main(){BinTree T;char ch1,ch2;printf("\n请选择:\n");ch1='y';while(ch1=='y'||ch1=='Y'){printf("\nA------------------二叉树建立-------------");printf("\nB------------------求叶子结点个数---------");printf("\nC------------------退出-------------------\n");scanf("\n%c",&ch2);switch(ch2){case 'a':case 'A':printf("请按先序输入二叉树存储的结点序列:\n"); CreateBinTree(&T);break;case 'b':case 'B':count=0;Leafnum(T);printf("该二叉树有%d个叶子.\n",count);break;case 'c':case 'C':ch1='n';break;default:ch1='n';}}}void CreateBinTree(BinTree *T){ char ch;scanf("\n%c",&ch);if(ch=='0') *T=NULL;else {*T=(BinTNode*)malloc(sizeof(BinTNode));(*T)->data=ch;CreateBinTree(&(*T)->lchild);CreateBinTree(&(*T)->rchild); }}void Leafnum(BinTree T){ if(T){if(T->lchild==NULL&&T->rchild==NULL)/*=============空白处1==============*/ count++;Leafnum(T->lchild);Leafnum(T->rchild);/*==================*/}}/*========数据结构上机考核试题7======*//* 二分查找*/#include <stdio.h>#define n 10main(){int R[n],i,k,low,mid,high,m;char ch;printf("请按递增顺序输入10个整数:\n",n);for(i=0;i<n;i++)scanf("%d",&R[i]);printf("需要查找请输入Y,否则输入N:");scanf("\n%c",&ch);while(ch=='y'||ch=='Y'){printf("请输入要查找的整数:\n");scanf("\n%d",&k);low=0;high=n-1;m=0;while(low<=high){ /*========空白处1===========*//*=======请在下面填入相应的语句========*/mid=(low+high)/2;m++;if(R[mid]>k) high=mid-1;else if(R[mid]<k) low=mid+1;else break;/*=============*/ }if(low>high){printf("\n没找到!\n");printf("共进行了%d次比较.\n",m);if(R[mid]<k)mid++;printf("可将此数插入到第%d的位置上.\n",mid+1);}else {printf("\n要找的数据%d在第%d的位置上.\n",k,mid+1); printf("共进行了%d此比较.\n",m); }printf("\n继续查找请输入Y,否则输入N:\n");scanf("\n%c",&ch); }}/*=====数据结构上机考核试题8========*//* 直接插入排序*/#define NULL 0#define n 10#define Error printf#define FLASE 0#define TRUE 1#include <math.h>typedef int KeyType;typedef char InfoType;typedef struct{KeyType key;InfoType otherinfo;}RecType;typedef RecType Seqlist[n+1];int m,num;void main(){Seqlist S;int i;char ch1,ch2;printf("请输入10个待排序整数:\n");for(i=1;i<=n;i++)scanf("%d",&S[i].key);ch1='y';while(ch1=='y'||ch1=='Y'){printf("******************\n");printf("请选择:(0-2)\n");printf("1-----更新待排数据-------------------\n");printf("2--------直接插入排序----------------\n");printf("0-----退出------------------------\n");scanf("\n%c",&ch2);switch(ch2){case '1':printf("请输入10个更新数据(整数):\n");for(i=1;i<=n;i++)scanf("%d",&S[i].key);break;case '2':printf("请输入要输出第几趟结果:");scanf("\n%d",&m);for(i=1;i<=n;i++)R[i].key=S[i].key;Insertsort();break;case '0':ch1='n';break;default:ch1='n';}}}void Insertsort(){ int i,j,k;for(i=2;i<=n;i++){ if(R[i].key<R[i-1].key){ /*=========空白处1===========*/R[0]=R[i]; j=j-1;Do{R[j+1]=R[j]; j--; }/*==================*/while(R[0].key<R[j].key);R[j+1]=R[0]; }if(i-1==m){ printf("第%d趟结果是:",m);for(k=1;k<=n;k++)printf("%5d",R[k].key);printf("\n");printf("请输入还要输出第几趟结果,不想输出时请输入0):");scanf("\n%d",&m); } }printf("最终排序结果是:");printf("\n");}/*=====数据结构上机考核试题9========*//* 快速排序*/#define NULL 0#define n 10#define Error printf#define FLASE 0#define TRUE 1#include <math.h>typedef int KeyType;typedef char InfoType;typedef struct{KeyType key;InfoType otherinfo;}RecType;typedef RecType Seqlist[n+1];int m,num;Seqlist R;void Quicksort(int low,int high);int Partition(int i,int j);void main(){Seqlist S;int i;char ch1,ch2;printf("请输入10个待排序整数:\n");for(i=1;i<=n;i++)scanf("%d",&S[i].key);ch1='y';while(ch1=='y'||ch1=='Y'){printf("***********************\n");printf("请选择:(0-2)\n");printf("1---------更新待排序数据-----------------\n"); printf("2---------快速排序-----------------------\n"); printf("0-------------退出---------------------------\n"); scanf("\n%c",&ch2);switch(ch2){case '1':printf("请输入10个更新数据:\n");for(i=1;i<=n;i++)scanf("%d",&S[i].key);break;case '2':printf("请输入要输出第几趟结果:"); scanf("\n%d",&m);for(i=1;i<=n;i++)R[i].key=S[i].key;num=0;Quicksort(1,n);break;case '0':ch1='n';break;default:ch1='n'; }}}int Partition(int i,int j){ RecType pivot=R[i];while(i<j){/*==========空白处1===========*/{while(i<j&&r[j].key>=pivot.key) j--;if(i<j) R[i++]=R[j];while(i<j&&R[i].key<=pivot.key) i++;if(i<j) R[j--]=R[i]; }/*=================*/}R[i]=pivot;return i;}/*****************************/void Quicksort(int low,int high){int pivotpos ,k;if(low<high){pivotpos=Partition(low,high);num++;if(m==num){printf("第%d趟结果是: ",m);for(k=1;k<=n;k++)printf("%5d",R[k].key);printf("\n");printf("请输入还要输出第几趟结果,不想输出时请输入0):"); scanf("\n%d",&m);}Quicksort(low,pivotpos-1);Quicksort(pivotpos+1,high);}if(low==1&&high==n){printf("最终排序结果是:");for(k=1;k<=n;k++)printf("%5d",R[k].key);printf("\n");}}/*=======数据结构上机考核试题10========*//* 堆排序*//*下面有2处空白,空白处都标有醒目标记, */#define NULL 0#define n 10#define Error printf#define FLASE 0#define TRUE 1#include <math.h>typedef int KeyType;typedef char InfoType;typedef struct{KeyType key;InfoType otherinfo;}RecType;typedef RecType Seqlist[n+1];int m,num;Seqlist R;void Heapsort();void main(){Seqlist S;int i;char ch1,ch2;printf("请输入10个待排序整数:\n");for(i=1;i<=n;i++)scanf("%d",&S[i].key);ch1='y';while(ch1=='y'||ch1=='Y'){printf("********************************\n"); printf("请选择:(0-2)\n");printf("1----------更新待排序数据-----------\n"); printf("2---------堆排序-----------------------\n"); printf("0----------退出----------------------\n"); scanf("\n%c",&ch2);switch(ch2){case '1':printf("请输入10个更新数据:\n");for(i=1;i<=n;i++)scanf("%d",&S[i].key);break;case '2':printf("请输入要输出第几趟结果:"); scanf("\n%d",&m);for(i=1;i<=n;i++)R[i].key=S[i].key;Heapsort();break;case '0':ch1='n';break;default:ch1='n';}}}/********************************/void Heapify(int low,int high){int large;RecType temp=R[low];for(large=2*low;large<=high;large*=2){/*==========空白处1=========*//*=====请在下面填入相应的语句=====*/If(large<high&&R[large].key<R[large+1].key) large++;/*=================*/if(temp.key>=R[large].key)break;R[low]=R[large];low=large;}R[low]=temp;}/***********************/void BuildHeap(){int i;/*==========空白处2===========*//*===请在下面填入相应的建堆操作语句==*/for(i=n/2; i>0; i--)Heapify(i,n) ;/*================*/}/****************************/void Heapsort(){int i,k;BuildHeap();for(i=n;i>1;i--){R[0]=R[1];R[1]=R[i];R[i]=R[0];if(i==(n-m+1)){printf("第%d趟结果是:\n",m);for(k=1;k<=n;k++)printf("%5d",R[k].key);printf("\n");printf("请输入还想输出第几趟结果,不想输出时请输入0):"); scanf("\n%d",&m);}Heapify(1,i-1);}printf("最终排序结果是:\n");for(k=1;k<=n;k++)printf("%5d",R[k].key);printf("\n"); }1. 顺序表的插入与删除/*========空白处1========*/L->data[j+1]=l->data[j];L->data[i]=x;L->length++;/*======空白处2=======*/L->data[j-num]=L->data[j];L->length=L->length-num;2.单链表的插入与删除/*=====空白处1====*/S->data=x;S->next=P->next;P->next=S;/*====空白处2=====*/p->next=r->next;free(r);3. 栈的操作/*=======空白处1========*/Else S->data[++(S->top)]=x;/*=======空白处2========*/If(StackEmpty(S))Error(“Stack underflow”);Else return S->data[--(S->top)];4.队列的操作/*========空白处1========*/Q->count++;Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%QueueSize;/*========空白处2========*/Q->count--;Q->front=(q->front+1)%QueueSize;5. 二叉树的遍历/*========空白处1========*/if(p->lchild!=NULL){q[j]=p->lchild; j++;} if(p->rchild!=NULL){q[j]=p->rchild; j++;} i++;6. 求二叉树叶子结点个数/*=======空白处1=======*/count++;Leafnum(T->lchild);Leafnum(T->rchild);7. 二分查找/*=======空白处1=======*/mid=(low+high)/2;m++;if(R[mid]>k) high=mid-1;else if(R[mid]<k) low=mid+1;else break;8. 直接插入排序/*=========空白处1=========*/R[0]=R[i]; j=j-1;Do{R[j+1]=R[j]; j--; }9. 快速排序/*=========空白处1========*/{while(i<j&&r[j].key>=pivot.key) j--;if(i<j) R[i++]=R[j];while(i<j&&R[i].key<=pivot.key) i++;if(i<j) R[j--]=R[i]; }10. 堆排序=========空白处1=========*/If(large<high&&R[large].key<R[large+1].key) large++; ========空白处2=========*/for(i=n/2; i>0; i--)Heapify(i,n) ;。
数据结构上机实验题目实验一线性表的顺序存储结构实验学时 2学时背景知识:顺序表的插入、删除及应用.目的要求:1.掌握顺序存储结构的特点。
2.掌握顺序存储结构的常见算法。
实验内容1.输入一组整型元素序列,建立顺序表。
2.实现该顺序表的遍历。
3.在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。
4.判断该顺序表中元素是否对称,对称返回1,否则返回0。
5.实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数.6.输入整型元素序列利用有序表插入算法建立一个有序表.7.利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表.8。
利用该顺序结构实现循环队列的入队、出队操作。
8.编写一个主函数,调试上述算法。
#include 〈stdio.h〉#include <stdlib。
h>#define OVERFLOW 0#define MAXSIZE 100typedef int ElemType;typedef struct list{ElemType elem[MAXSIZE];int length;}Sqlist;void Creatlist(Sqlist &L){int i;printf(”请输入顺序表的长度:"); //输入一组整型元素序列,建立一个顺序表.scanf("%d”,&L。
length);for(i=0;i<L。
length;i++)scanf(”%d",&L。
elem[i]);}void printlist(Sqlist &L)//以输出的形式实现对该顺序表的遍历{int i;for(i=0;i<L.length;i++)printf("%d ”,L。
elem[i]);printf(”\n”);}void Searchlist(Sqlist &L,int x) //在顺序表中进行顺序查找某一元素x,查找成功则返回其存储位置i,否则返回错误信息{int i,k=—1;for(i=0;i<L.length;i++)if(L。
数据结构上机题目
第二次:sqlist-顺序表
2.11 设顺序表va中的数据元素递增有序。
试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性。
2.21 试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表(a1,a2,…,an)逆置为(an,an-1,…,a1)。
第三次:LinkList-单链表
2.15已知指针ha和hb分别指向两个单链表的头结点,并且已知两个链表的长度分别为m和n。
试写一算法将这两个链表连接在一起(即令其中一个表的首元结点连在另一个表的最后一个结点之后),假设指针hc 指向连接后的链表的头结点,并要求算法以尽可能短的时间完成连接运算。
请分析你的算法的时间复杂度。
2.19已知线性表中的元素以值递增有序排列,并以单链表作存储结构。
试写一高效的算法,删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素),同时释放被删结点空间,并分析你的算法的时间复杂度(注意,mink和maxk是给定的两个参变量,它们的值可以和表中的元素相同,也可以不同)。
第四次:cdLinkList-循环链表
2.33已知由一个线性链表表示的线性表中含有三类字符的数据元素(如:字母字符、数字字符和其他字符),试编写算法将该线性表分割为
三个循环链表,其中每个循环链表表示的线性表中均只含一类字符。
2.38设有一个双向循环链表,每个结点中除有prior,data和next 三个域外,还增设了一个访问频度域freq。
在链表被起用之前,频度域freq的值均初始化为零,而每当对链表进行一次LOCATE(L,x)的操作后,被访问的结点(即元素值等于x的结点)中的频度域freq的值便增1,同时调整链表中结点之间的次序,使其按访问频度非递增的次序顺序排列,以便始终保持被频繁访问的结点总是靠近表头结点。
试编写符合上述要求的LOCATE操作的算法。
第五次:outqueue-实验1线性表
实验目的
熟悉线性表的基本运算在顺序存储结构和链式存储结构上的实现,其中重点熟悉链表的各种操作。
时间要求:4学时
问题描述:
约瑟夫(Joseph)问题的一种描述是:编号为1,2,3,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码〈正整数〉,一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数,报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。
试设计一个程序求出出列顺序。
基本要求:
利用单向循环链表存储结构模拟此过程,按照出列的顺序打印出各人的编号。
实现提示:
程序运行后首先要求用户指定初始报数上限值,然后读取各人的密码(小于
30)。
选作内容:
在顺序存储结构上实现上述问题的操作。
Input
输入包括两行,第一行包括报数上限值m和人数n,第二行为n个人的密码,所有数据之间由空格分隔。
Output
输出一行,共n个整数,表示各编号人的出列顺序。
各数之间由空格分隔。
Sample Input
20 7
3 1 7 2
4 8 4
Sample Output
6 1 4
7 2 3 5
第六次:StackQueue-实验2栈和队列
实验目的
熟悉栈和队列的基本特性,掌握栈和队列基本运算的实现过程。
时间要求:4+4学时
问题描述:
设停车场内只有一个可停放 n 辆汽车的狭长通道,且只有一个大门可供汽车进出,汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列(大门在最南端,最先到达的第一辆车停放在车场的最北端),若车场内已停满 n 辆汽车,则后来的汽车只能在门外的便道上等候, 一旦有车开走,则排在便道上的第一辆车即可开入,当停车场内某辆车要离开时,在它之后开入的车辆必须先退出车场为它让路,待该辆车开出大门外,其它车辆再按原次序进入车场,每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用,当便道上汽车要离开时,排在它前面的汽车要先开走让路,然后再依次排到队尾,并且在便道上停车不收费。
试
为停车场编制按上述要求进行管理的模拟程序。
基本要求:
以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列管理,每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时间,对每一组输入数据进行操作后的输出数据为:若是车辆到达,则输出汽车在停车场内或便道上的停车位置;若是车辆离去,则输出汽车在停车场内停留的时间和应交纳的费用(在便递上停留的时间不收费),栈以顺序结构实现,队列以链表结构实现。
实现提示:
需另设一栈,临时停放为给要离去的汽车让路而从停车场退出来的汽车,也用顺序存储结构实现。
输入数据按到达或离去的时刻有序。
栈中每个元素表示一辆汽车,包含有两个数据项:汽车牌照号码和进入停车场的时间。
选作内容:
(1)两个栈共享空间,思考应开辟数组的空间是多少 ?
(2)汽车可有不同种类,则它们的占地面积不同,收费标准也不同,如 1 辆客车和 1.5 辆小汽车的占地面积相同,1辆十轮卡车占地面积相当于3辆小汽车的占地面积。
(3)停放在便道上的汽车也收费,收费标准比停放在停车场的车低,请思考如何修改结构以满足这神要求。
Input
输入第一行,包括两个数据,第一个整数为停车场最多可停放车辆数,第二个浮点数表示单位时间的停车费用。
接下来有多行数据,每行有三个整数,第一个为0或1,0表示进入车场,1表示离开车场;第二个整数为车号;第三个整数为进入或离开的时间。
当一行中三个数均为0时表示输入结束,所有数据之间由空格分隔。
Output
输出为三部分,第一部分为按离开停车场顺序打印出的各车费用,每车一行,包括车号和费用(保留小数点后两位)。
第二部分占一行为当前停车场中的所有车辆,从北到南顺序输出各车车号。
第三部分占一行为当前便道上的所有车辆,从前向后顺序输出各车车号。
各车号之间由一个空格分隔。
Sample Input
2 1.5
0 1 5
0 2 10
1 1 15
0 3 20
0 4 25
0 5 30
0 6 35
1 2 40
0 7 45
1 6 50
0 0 0
Sample Output
1 15.00
2 45.00
3 4
7 5
第七次: btree-二叉树
6.41编写递归算法,在二叉树中求位于先序序列中第k个位置的结点的值。
6.42编写递归算法,计算二叉树中叶子结点的数目。
6.43编写递归算法,将二叉树中所有节点的左、右子树相互交换。
第八次: BST-二叉排序树
9-1一棵以二叉链表存储的二叉排序树,并且可能存在值相同的结点。
设计一个算法,按升序打印出树中所有结点,但相同值的结点只打印一次。
9-2一棵以二叉链表存储的二叉排序树,并且可能存在值相同的结
点。
设计一个算法,统计树中不同结点的个数。