c数据结构算法题
#include<stdio.h>
intmain()
{
doubles=0.00,w=1.00,p=1.00,f=0.00;
inti=0;
doubler0=0.00,r1=0.02,r2=0.05,r3=0.08,r4=0.10,r5=0.15;
printf("pleaseinputs: ");
scanf("%d",&s);
if(s>=3000)
i=5;
else
i=(int)s/250;
switch(i)
case0:f=p*w*s*(1.0-r0);break;
case1:f=p*w*s*(1.0-r1);break;
case2:f=p*w*s*(1.0-r2);break;
case3:f=p*w*s*(1.0-r3);break;
case4:f=p*w*s*(1.0-r4);break;
case5:f=p*w*s*(1.0-r5);break;
default:printf("inputerror");
printf("allfaref=%f",f);
return0;
}
‘贰’ 数据结构（C语言版） 中一题目的算法
算法我觉得只用一个一个的查，比较是否合题意，其时间复杂度为O(N),如果觉得这个复杂也可以用二分法，时间复杂度就只有O(log2n)
‘叁’ 数据结构c语言版 ：算法设计题 求大神解答。。在线等。。。
/*判断一段字符串是不是回文,所谓回文，也就
是正读反读都一样，如asdffdsa*/
#include<iostream>
#include<stdio.h>
using namespace std;
const int size=100;
class HuiWen
{
private:
char ch[100];
int top;
public:
HuiWen(){top = -1;};
void input(char c);
bool isHuiWen();
bool empty();
};
void HuiWen::input(char c)
{
//if(top==size-1) throw"上溢";
top++;
//cin>>ch[top];
ch[top]= c;
}
bool HuiWen::isHuiWen()
{
for(int i=0;i<top;i++)
if(ch[top--]!=ch[i])
return 0;
return 1;
}
bool HuiWen::empty()
{
if(top==-1)
return 1;
return 0;
}
int main()
{
HuiWen hw;
cout<<"请输入字符串，以回车键结束"<<endl;
int c;
while((c=getchar())!='\n')
hw.input(c); //主要就是这里做了修改。
if(hw.empty())
cout<<"对不起，无字符"<<endl;
else
{
if(hw.isHuiWen())
cout<<"该字符串是回文"<<endl;
else
cout<<"该字符串不是回文"<<endl;
}
return 0;
}
‘肆’ 19年3月二级C--数据结构与算法
1.假设线性表的长度为n，则最坏情况下:
冒泡排序: 需要经过n/2遍的从前往后扫描和n/2遍从后往前扫描，需要比较的次数为n(n-1)/2。总的时间复杂度为O(n的平方)。
快速排序: 比较次数也是n(n-1)/2。总的时间复杂度为O(n的平方)。
直接插入排序: 所需要比较的次数为n(n-1)/2。总的时间复杂度为O(n的平方)。
希尔排序所需要比较的次数为O(n的1.5次方)。(时间复杂度小于以上三种)
堆排序: 最坏情况下，其时间复杂度为O(nlogn)。(小于O(n的平方))。
2.根据数据结构中各元素之间前后关系的复杂程度，一般数据结构分为两大类: 线性结构和非线性结构。
如果一个非空的数据结构满足下列两个条件，①有且只有一个根结点 ②每个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，又称线性表。
3.算法时间复杂度与空间复杂度没有关系。
4.所谓算法的时间复杂度，是指执行算法所需要的计算工作量。
为了能够比较客观的反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所用的计算机程序设计语言，以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。
5.同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。
算法分析的目的在于选择合适算法和改进算法。
6.堆排序在平均情况下的时间复杂度与最坏情况下的时间复杂度都是O(nlogn)。
7.二叉链表: 以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和第一个孩子下的一个兄弟结点。
循环链表是链式存储结构，循环队列是线性存储结构。( 【×】循环链表是循环队列的链式存储结构)
双向链表也叫双链表，是链表的一种，它的每个数据结点都有两个指针，分别指向直接后继和直接前驱，所以从双链表中的任意一个结点开始都可以很方便地访问它的前驱结点和后继结点。
8.数据的逻辑结构由两个要素: 一是数据元素的集合，通常记为D。二是D上的关系，它反映了D中各元素之间的前后件关系，通常记为R。
即一个数据结构可以表示成B=(D,R)，其中B表示数据结构，为了反映D中各元素之间的前后件关系，一般用二元组来表示。例如，假如a与b是D中的两个数据，则二元组表示a是b的前件，b是a的后件。
线性结构用图形表示更加直观。例如: R=｛(5,1)，(7,9)，(1,7)，(9,3)｝，结构为: 5→1→7→9→3
9.快速排序法是一种互换类的排序方法，但由于比冒泡排序的速度快，因此称为快速排序。
其基本思想是从线性表中选择一个元素设为t，将线性表后面小于t的元素移到前面，而前面大于t的元素移到后面，结果就将线性表分成了两部分，t插入到分界线的位置处，这个过程称为线性表的分割。
简单插入排序法，是指将无序序列中的各元素依次插入到已经有序的线性表中。
冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换，逐步将线性表变为有序。
后两种元素的移动过程中不会产生新的逆序。
10.程序可作为算法的一种描述。
11.为了降低算法的空间复杂度，要求算法尽量采用原地工作，所谓的原地工作是指执行算法时所使用的额外空间固定。
一个算法的空间复杂度一般是指执行这个算法所需要的内存空间，一个算法所占用的存储空间包括程序所占的空间，输入的初始数据所占的空间以及算法执行过程中所需要的额外空间。
12.能从任意一个结点开始没有重复的扫描到所有结点的数据结构是循环链表。
13.循环队列是队列的一种存储结构
14.算法的设计要求包括效率与低存储量，即要考虑算法的时间复杂度与空间复杂度。
算法的复杂度包括时间复杂度和空间复杂度。
时间复杂度: 是指执行算法所需要的计算工作量。
空间复杂度: 一般是指执行这个算法所需要的内存空间。
15.栈是一种特殊的线性表。链式结构把每一个存储结点分为数据域与指针域，带链的栈可以通过指针域的变化改变原有的栈的组织数据原则; 而顺序栈的栈底指针不变，栈顶指针改变。
16.堆排序在最坏的情况下需要比较nlogn次。
快速排序，在最坏情况下需要比较n(n-1)/2次。
顺序查找，在最坏情况下需要比较n次。
最坏情况下，二分查找需要log2n(小于n-1)
在长度为n的顺序表中寻找最大项/最小项时，比较次数最少为1，最多为n-1。
17.如果一个非空的数据结构满足下列两个条件，①有且只有一个根节点 ②每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称为非线性结构。
18.带链栈空的条件是 top=bottom=NULL
19.满二叉树也是完全二叉树，完全二叉树不一定是满二叉树。对于满二叉树和完全二叉树来说，可以按照程序进行顺序存储，不仅节省了空间，又能方便地确定每一个结点的父结点等于左右子结点的位置，但顺序存储结构对于一般的二叉树不适用。
20.带链栈队头指针与队尾指针相同，且不为空时，队列元素个数为1; 若为空时，队列元素个数为0。
带链栈的栈底指针是随栈的操作而动态变化的。
21.二叉树的链式存储结构，也称为二叉链表。在二叉树中，由于每一个元素可以有两个后件，因此用于存储二叉树的存储结点的指针域有两个，所以二叉链表属于非线性结构。
22.线性表由一组元素数据元素构成，各元素的数据类型必须相同，矩阵是一个比较复杂的线性表，线性表除了插入和删除运算之外，还可以查找，排序，分解，合并等。数组是长度固定的线性表。
23.冒泡排序中，在互换两个相邻元素时，只能消除一个逆序; 快速排序及希尔排序中，一次交换可以消除多个逆序。
24.二分法检索的效率比较高，设线性表有n个元素，则最多的比较次数为log2n，最少检索次数为1。
25.循环链表的结构具有以下两个特点。一，在循环链表中，增加了一个表头结点，其数据域为任意或者根据需要来设置指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。二、循环链表中最后一个节点的指针域不是空，而是指向表头结点，即在循环链表中所有的结点指针构成一个环状链。
26.二叉树的存储结构是非线性结构，而完全二叉树是特殊形态的二叉树。采用顺序存储的完全二叉树属于非线性结构。
27.时间复杂度和计算机运行速度以及存储空间无关。
算法的空间复杂度和存储结构无关。
数据处理效率与数据的存储结构有关。
28.线性表，向量，栈，队列都属于线性结构的顺序存储。
29.循环队列是队列的存储结构。
循环链表是另一种形式的念式存储结构。
(✘循环链表是循环队列的链式存储结构。✘)
30.完全二叉树的总结点为奇数时，叶子结点是总结点加一再除以二。
31.在实际处理中，可以用一位数组来存储堆序列中的元素，也可以用完全二叉树来直观的表示堆的结构。在用完全二叉树表示堆时，树中所有非叶子结点值均不小于其左，右子树的根结点值，因为堆顶元素必须为序列的n个元素的最大项，因此其中序并不是有序序列。
多重链表指表中每个结点由两个或两个以上的指针域的链表。如果一个非空的数据结构满足下列两个条件，①有且只有一个根结点，②每个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构，所以多重链表不一定是非线性结构。
在计算机中二叉树通常采用链式存储结构，对于满二叉树和完全二叉树来说，可以按层次进行顺序存储。
排序二叉树的中序遍历序列是有序序列。
32.对于一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。
33.在线性表中寻找最大项时，平均情况下和最坏情况下比较次数都是n-1。
34.在长度为n的顺序表中查找一 个元素， 假没需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相
同的。则在平均情况下需要比较的次数大约为_
A.3n/4 B.n C.n/2 D.n/4
本题的考查知识点是顺序表的存储结构。
因为需要查找的元素有一半机会在表中，所以二分之一的情况下平均比较次数为n/2，另二分之一的情况下平均比较次数为n。总的平均比较次数为(n/2+n) /2-3n/4。
故本题答案为A。
35.设数据结构B=(D, R)，其中
D={a,b,c,d，e，f}
R={(a，b)，(b，c)，(c，d)，(d，e)，(e，f)，(f,a)}该数据结构为
A.线性结构 B.循环队列
C.循环链表 D.非线性结构
本题的考查知识点是数据结构。
如果一个非控的数据结构满足下列两个条件: 1) 有且只有一个根节点; 2) 每一一个结点最多有一一个前件，也最多有一一个后件。则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。
数据结构B=(D, R)中， 每一个结点均有一个前件，不符合“有且只有一个根节点”的条件，所以为非线性结构。故本题答案选D。
36.某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。 该队列中的元素个数为_
A.1 B.0 C.1或0 D.不确定
本题的考查知识点是带链队列。
在初始状态为front=rear=NULL的带链队列入队时，如果插入的结点既是队首结点又是队尾结点，则rear和front同时指向这个结点;否则在循环队列的队尾加入一一个新元素，rear指向新增结点的数据域，rear+1, front不变。 退队时，在循环队列的排头位置退出一个元素并赋给指定的变量，front指向第二个结点的数据域，front+1, rear不变。当front=rear=10时， front和rear同时指向这个唯一 元素，所以该队列中的元素个数为1。
故本题答案为A。
37.若二叉树没有叶子结点，则为空二叉树。
38.某带链栈的初始状态为top=bottom=NULL, 经过一系列正 常的入栈与退栈操作后，top=10, bottom=20。 该栈中的元素个数为_____。
A.不确定 B. 10 C.1 D.0
本题考查的知识点是栈。
带链的栈是具有栈属性的链表，线性链表的存储单元是不连续的，为把存储空间中一-些离散的空闲存 储结点利用起来，把所有空闲的结点组织成一个带链的栈，称为可利用栈。
线性链表执行删除操作运算时， 被删除的结点可以”回收到可利用栈，对应于可利用栈的入栈运算;线性链表执行插入运算时，需要一个新的结点，可以在可利用栈中取栈顶结点，对应于可利用栈的退栈运算。
可利用栈的入栈运算和退栈运算只需要改动top指针即可。因为是不连续的存储空间，所以top指针将不会有规律地连续变化，因此无法据此判断栈中的元素个数。
所以本题答案为A。
‘伍’ 求助数据结构题用C语言做
1: 因为要删除那些即在B表又在C表中的元素，所以A,B，C三个表中都会有这个元素。那么用指针遍历A表，用另外两个指针遍历B,C。查找B,C中同A的元素，因为3个表都是有序的，可以采用些简单的比较。找到后删除。
2：void AE(stack &s)
{
int stack (s); //得到传递过来的栈
push(s,3); // 3进栈
push(s,4); // 4进栈
int x=pop(s)+2*pop(s); // x = 3 + 2 * 4
push(s,x); // x 进栈
int a[5]={2,5,8,22,15};
for(j=0;j<5;j++)
push(s,a[i]) // A数组进栈
while(!stackempty(s)) // 直到栈空
printf("%d",2*pop(s)); //输出 2*栈中每个元素
结果自己想了。
‘陆’ 数据结构（C语言版） 中一题目的算法
/***
*
*题目：已知
线性表
中的元素以值递增有序排列，并以
单链表
做存储结构。试写一高效的算法，
*
删除表中所有值大于
mink
且小于
maxk
的元素（若表中存在这样的元素）,同时释放
*
被删除节点空间，并分析你的算法的
时间复杂度
（注意：mink
和
maxk
是给定的两个
*
参变量，它们的值可以和表中的元素相同，也可以不同）
*
****/
#include
#include
#include
"DynaLinkList.h"
void
DelMminMax(LinkList
*L,
int
min,
int
max)
{
LinkList
p
=
(*L)->next,
q
=
(*L),
r;
while
(p
&&
p->data
<=
min)
{
q
=
p;
p
=
p->next;
}
while
(
p
&&
p->data
<
max)
{
r
=
p;
p
=
p->next;
q->next
=
p;
free(r);
}
}
//算法的时间复杂度为O(n)
int
main()
{
LinkList
L;
ElemType
e,
min,
max;
InitList(&L);
printf("输入8个元素建立线性表L(元素递增有序):\n");
for
(int
i=1;
i<=8;
i++)
{
scanf("%d",
&e);
ListInsert(&L,
i,
e);
}
printf("表L是：\n");
ListTraverse(L,
visit);
printf("请输入待删除的元素的区间是(min,max):\n");
scanf("%d%d",
&min,
&max);
DelMminMax(&L,min,max);
printf("删除(%d,%d)之间的元素后表L是：\n",min,max);
ListTraverse(L,
visit);
return
0;
}
‘柒’ 数据结构(C语言版）课后题－关于串的算法
算法如下：
int strReplace(SString S,SString T, SString V)
{/*用串V替换S中的所有子串T */
int pos,i;
pos=strIndex(S,1,T); /*求S中子串T第一次出现的位置*/
if(pos = = 0) return(0);
while(pos!=0) /*用串V替换S中的所有子串T */
{
switch(T.len-V.len)
{
case 0: /*串T的长度等于串V的长度*/
for(i=0;i<=V.len;i++) /*用V替换T*/
S->ch[pos+i]=V.ch[i];
case >0: /*串T的长度大于串V的长度*/
for(i=pos+t.ien;i<S->len;i--) /*将S中子串T后的所有字符
S->ch[i-t.len+v.len]=S->ch[i]; 前移T.len-V.len个位置*/
for(i=0;i<=V.len;i++) /*用V替换T*/
S->ch[pos+i]=V.ch[i];
S->len=S->len-T.len+V.len;
case <0: /*串T的长度小于串V的长度*/
if(S->len-T.len+V.len)<= MAXLEN /*插入后串长小于MAXLEN*/
{ /*将S中子串T后的所有字符后移V.len-T.len个位置*/
for(i=S->len-T.len+V.len;i>=pos+T.len;i--)
S->ch[i]=S->ch[i-T.len+V.len];
for(i=0;i<=V.len;i++) /*用V替换T*/
S->ch[pos+i]=V.ch[i];
S->len=S->len-T.len+V.len; }
else
{ /*替换后串长>MAXLEN,但串V可以全部替换*/
if(pos+V.len<=MAXLEN)
{ for(i=MAXLEN-1;i>=pos+T.len; i--)
S->ch[i]=s->ch[i-T.len+V.len]
for(i=0;i<=V.len;i++) /*用V替换T*/
S->ch[pos+i]=V.ch[i];
S->len=MAXLEN;}
else /*串V的部分字符要舍弃*/
{ for(i=0;i<MAXLEN-pos;i++)
S->ch[i+pos]=V.ch[i];
S->len=MAXLEN;}
}/*switch()*/
pos=StrIndex(S,pos+V.len,T); /*求S中下一个子串T的位置*/
}/*while()*/
return(1);
}/*StrReplace()*/
‘捌’ 请C语言版数据结构高手帮帮忙！
第一题：
#include<iostream.h>
struct list
{
int num;
struct list *next;
}head={0,0};
void push(struct list *head,int num)
{
struct list *p=head;
while(p->next&&p->next->num<num)
{
p=p->next;
};
struct list *p1=new list;
p1->num=num;
p1->next=p->next;
p->next=p1;
}
void pop(struct list *head,int num1,int num2)//num1<num2
{
struct list *p=head,*q,*q1;
while(p->next&&p->next->num<=num1)
{
p=p->next;
//cout<<endl<<p->num;
};
q=p;
p=p->next;
while (p&&p->num<num2)
{
q1=p;
p=p->next;
delete q1;
}
q->next=p;
}
void print(struct list *head)
{
struct list *p=head->next;
while (p)
{
cout<<p->num<<ends;
p=p->next;
}
}
void main()
{
push(&head,1);
push(&head,4);
push(&head,6);
push(&head,2);
push(&head,3);
push(&head,7);
push(&head,-1);
print(&head);
cout<<endl;
pop(&head,1,6);
print(&head);
}
第二题：
#include<iostream.h>
void change(unsigned int num,char str[])
{
unsigned int temp;
int i=0;
char te[100];
do
{
//temp=num/8;
te[i++]=num%8+48;
num=num/8;
} while(num);
for (int j=0;j<i;j++)
{
str[j]=te[i-j-1];
}
str[j]=0;
}
void main()
{
unsigned int num;
char str[100];
cin>>num;
change(num,str);
cout<<str;
}
第三题：
#include<iostream.h>
struct list
{
int num;
struct list *next;
}head1={0,0},head2={0,0},head3={0,0};
void push(struct list *head,int num)
{
struct list *p=head;
while(p->next&&p->next->num<num)
{
p=p->next;
};
struct list *p1=new list;
p1->num=num;
p1->next=p->next;
p->next=p1;
}
void print(struct list *head)
{
struct list *p=head->next;
while (p)
{
cout<<p->num<<ends;
p=p->next;
}
}
void hebing(struct list *head1,struct list *head2,struct list *head3)
{
struct list *p1=head1->next,*p2=head2->next,*p3=head3,*p4;
while (p1||p2)
{
if (p1&&p2&&p1->num==p2->num)
{
p4=p1;
p1=p1->next;
p2=p2->next;
}
else if (p1&&!p2||((p1&&p2)&&p1->num<p2->num))
{
p4=p1;
p1=p1->next;
}
else
{
p4=p2;
p2=p2->next;
}
struct list *p=new struct list;
p->num=p4->num;
p->next=p3->next;
p3->next=p;
p3=p3->next;
}
}
void main()
{
push(&head1,1);
push(&head1,4);
push(&head1,6);
push(&head1,2);
push(&head1,3);
push(&head1,7);
push(&head1,-1);
push(&head2,3);
push(&head2,1);
push(&head2,9);
push(&head2,-2);
push(&head2,-3);
push(&head2,7);
push(&head2,-1);
print(&head1);
cout<<endl;
print(&head2);
cout<<endl;
hebing(&head1,&head2,&head3);
print(&head3);
}
//最近要考试，有空把后面几个写给你。
//妄我专门腾出那么多时间帮你写。竟不加分。
‘玖’ C数据结构题目
一维数组类型Array1D的定义：
typedef ElemType Array1D[MAXLEN];
void Rotate(Array1D &a, int n, int k)
/* a[n] contains the elements, */
/* rotate them right circlely by k sits */
{
int round,pos1,pos2,i,temp;
for(i=1;i<=k;i++)
if(k%i==0&&n%i==0) round=i;
for(i=0;i<round;i++)
{
pos1=pos2=(n+(i-k)%n)%n;
temp=a[pos1];
for(;;)
{
if(pos1!=i)
{
pos1=(n+(pos1-k)%n)%n;
a[pos2]=a[pos1]; //a[pos1]存放即将替换a[pos2]的数值
pos2=pos1;
}
else break;
}
a[pos1]=temp;
}
}
n=15,k=6,则p=3.
第一条链:A[0]->A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0].
第二条链:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1].
第三条链:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2].
pos1=(n+(pos1-k)%n)%n;逆推上去 9->3->12->6->0 pos1=(n+pos1-k&n)%n
顺推 pos1=(pos1+k)%n
只用一个元素大小的附加存储，元素移动或交换次数为O(n) 所以只能逆推
循环次数为n和k的最大公约数
‘拾’ 数据结构c语言题目 求大神解一下。
#include<iostream>
usingnamespacestd;
constintMaxSize=200;
classSeqList
{public:
SeqList(inta[],intn);
intLength();
voidInsert(intb[],intlength2);
voidPrintList();
private:
intdata[MaxSize];
intlength;
};
SeqList::SeqList(inta[],intn)
{inti;
if(n>MaxSize)throw"
参数非法
";
for(i=0;i<n;i++)
data[i]=a[i];
length=n;
}
intSeqList::Length()
{
returnlength;
}
voidSeqList::Insert(intb[],intlength2)
{intj,h,i=0;
for(j=0;j<length&&i<length2;++j)
{if(b[i]<data[j])
{for(h=length;h!=j;--h)
data[h]=data[h-1];
data[j]=b[i];
++length;
++i;
}
elseif(j==length-1&&b[i]>data[length-1])
{
data[length]=b[i];
length++;
++i;
}
}
}
voidSeqList::PrintList()
{for(inti=0;i<length;i++)
cout<<data[i]<<"";
cout<<endl;
}
voidmain()
{
inta[6]={1,5,8,10,15,21};
intb[3]={6,13,18};
SeqLists(a,6);
SeqListc(b,3);
cout<<"
合并前的顺序表
A"<<endl;
s.PrintList();
cout<<"
合并前的顺序表
B"<<endl;
c.PrintList();
cout<<"
合并后的顺序表
C"<<endl;
intx=c.Length();
s.Insert(b,x);
s.PrintList();
}