求c++数据结构问题 1.判断有向树是以v0为根的生成树; 2.求无向图的边数0。
数据结构是一个抽象概念,是指数据在计算机中的组织方式和一系列相关的操作
常见的组织方式有线性表(数组,栈,队列,链表),树,哈希表,磁盘文件等
常见的操作方式有查找,插入,删除,排序
而对于这些操作,通常有一些成熟的算法来支持。
具体细节,请参考《数据结构》教程
你这段程序还没涉及到数据结构研究的范畴。
题目1:
测试示例:
代码:
#define _author "Reskip"#define _CRT_SECURE_NO_WARNINGS#include #include#include#include#include#include#include#include#include#include#includeusing namespace std;bool datas[100005];int pos[100005];int beg;char temp;int main(){int tar = 0;int posx = 0;while (cin >> temp){posx++;if (temp == '('){datas[beg] = 1;pos[beg] = posx;beg++;}if (temp == ')'){if (beg&&datas[beg - 1] == 1){cout << pos[beg-1] << " " << posx << "
";beg--;}else{tar = 1;}}if (temp == '['){datas[beg] = 0;pos[beg] = posx;beg++;}if (temp == ']'){if (beg&&datas[beg - 1] == 0){cout << pos[beg-1] << " " << posx << "
";beg--;}else{tar = 1;}}}if (beg || tar){cout << "Match false!
";}else{cout << "Match succeed!
";}return 0;}题目2:
输入输出格式:
输入:
第1个稀疏矩阵的行数、列数、非零元个数(三个数都大于0)、三元组
第2个稀疏矩阵的行数、列数、非零元个数(三个数都大于0)、三元组 、
以行为主序输入稀疏矩阵三元组表
输出:
乘积矩阵的行数、列数、非零元个数(三个数都大于0)、三元组
代码:
#define _author "Reskip"#define _CRT_SECURE_NO_WARNINGS#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;struct table{int x, y, val;}d1[105], d2[105], ans[10005];int cmp(table a, table b){if (a.x != b.x){return a.x > col >> drop;cin >> n;for (int i = 0; i > d1[i].x >> d1[i].y >> d1[i].val;}cin >> drop >> rol;cin >> m;for (int i = 0; i > d2[i].x >> d2[i].y >> d2[i].val;}int beg = 0;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (d1[i].y == d2[j].x){ans[beg].x = d1[i].x;ans[beg].y = d2[j].y;ans[beg].val = d1[i].val*d2[j].val;beg++;}}}sort(ans, ans + beg, cmp);for (int i = 1; i < beg; i++){if (ans[i].x == ans[i - 1].x&&ans[i].y == ans[i - 1].y){ans[i].val += ans[i - 1].val;ans[i - 1].val = 0;}}int cnt = 0;for (int i = 0; i < beg; i++){if (ans[i].val){cnt++;}}cout << col << "
" << rol << "
" << cnt << "
";for (int i = 0; i < beg; i++){if (ans[i].val){cout << ans[i].x << "," << ans[i].y << "," << ans[i].val << "
";}}//system("pause");}
2、四种逻辑结构的前驱和后继的关系
3、顺序存储结构要求存储空间是连续的、元素之间的关系用下标表示;链式存储要求存储空间是不连续的,元素之间的关系用指针表示。
4、T(n)和S(n)分别表示什么?
5、何谓上溢和下溢。溢是当一个超长的数据进入到缓冲区时,超出部分被写入上级缓冲区,上级缓冲区存放的可能是数据、上一条指令的指针,或者是其他程序的输出内容,这些内容都被覆盖或者破坏掉。可见一小部分数据或者一套指令的溢出就可能导致一个程序或者操作系统崩溃。
下溢是当一个超长的数据进入到缓冲区时,超出部分被写入下级缓冲区,下级缓冲区存放的是下一条指令的指针,或者是其他程序的输出内容。
5、广义表表长和深度求解
6、无向完全图中边的个数为多少
若一个完全无向图具有n条边,则该图的顶点个数为2n+1/4)+1/2
7、折半查找的前提是?索引查找的表结构的构成?
前提是必须有有序表。只能由于静态查找
8、什么排序的比较次数与元素的初始状态无关。 选择排序和归并排序
9、在一个长度为n的顺序表中第i个元素(1≤i≤n)后插入一个元素时,需向后移动多少元素 n-i-1
10、head和tail的综合使用
11、在有向图中每个顶点的度等于该顶点的( n(n-1)|2 )。
12、二叉树的深度求解
13、二叉树的深度求解
14、将一颗已知树转换成二叉树,写出后序遍历的结果。
#include "iostream.h"
#include "stdlib.h"
#define MaxSize 100
typedef char ElemType;
typedef struct Node
{
ElemType data;
struct Node *left,*right;
}BTree; //树的单元结构
void creatree(BTree **BT,ElemType *str)
{
//根据括弧表示法创建一棵二叉树
BTree *stack[MaxSize],*p;
int top=-1,k,j=0; //top为栈指针,k指定是左还是右孩子,j为str指针
char ch;
*BT=NULL;
ch=str[j];
while(ch!='\0')
{
switch(ch)
{
case '(':
top++;
stack[top]=p;
k=1; //标示为左孩子
break;//////////////////你这里少了break;
case ')':
top--;
break;
case ',':
k=2;//标示为右孩子
break;
default:
p=(BTree *)malloc(sizeof(BTree));
p->data=ch;
p->left=p->right=NULL;
if(*BT==NULL) //根结点
*BT=p;
else{
switch(k)
{
case 1:
stack[top]->left=(BTree *)malloc(sizeof(BTree));
stack[top]->left=p;break;
case 2:
stack[top]->right=(BTree *)malloc(sizeof(BTree));
stack[top]->right=p;
}
}
}
j++;
ch=str[j];
}
}
void postorder(BTree *BT)
{ //后序遍历
if(BT!=NULL)
{
postorder(BT->left);
postorder(BT->right);
cout<<BT->data;
}
}
int BTreeDepth(BTree *BT)
{ //求二叉树的深度
int leftdep,rightdep;
if(BT==NULL)
return 0;
else
{
leftdep=BTreeDepth(BT->left);
rightdep=BTreeDepth(BT->right);
if(leftdep>rightdep)
return leftdep+1;
else
return rightdep+1;
}
}
int nodecount(BTree *BT)
{ //求结点数
if(BT==NULL)
return 0;
else
{
return(nodecount(BT->left)+nodecount(BT->right)+1);
}
}
int leafcount(BTree *BT)
{ //叶子结点
if(BT==NULL)
return 0;
else if(BT->left==NULL && BT->right==NULL)
return 1;
else
return (leafcount(BT->left)+leafcount(BT->right)+1);
}
int noleafcount(BTree *BT){ //非叶子结点
if(BT==NULL)
return 0;
else if(BT->left==NULL && BT->right==NULL)
return 0;
else
return(noleafcount(BT->left)+noleafcount(BT->right)+1);
}
int main(){
char yumensi[100],tianla;
int i=0;
cout<<"请用括号表示法输入一棵二叉树并以一个.结束,例如"<<"'A(B(D,E(H,I)),C(G)).'"<<endl;
cout<<"请注意正确输入因为程序不能判断输入是否正确!!否则后果自负!!"<<endl;
cin>>tianla;
while(tianla!='.')
{
yumensi[i]=tianla;
i++;
cin>>tianla;
}
yumensi[i]='\0';
BTree *tree;
creatree(&tree,yumensi);
cout<<"先序遍历结果:";
preorder(tree); cout<<endl;
cout<<"中序遍历结果:";
inorder(tree); cout<<endl;
cout<<"后序遍历结果:";
postorder(tree); cout<<endl;
cout<<"深处为:"<<BTreeDepth(tree)<<endl;
cout<<"结点个数:"<<nodecount(tree)<<endl;
cout<<"叶子结点个数:"<<leafcount(tree)<<endl;
cout<<"非叶子结点个数:"<<noleafcount(tree)<<endl;
cout<<"BY: B.Lee 版权没有,盗版不究"<<endl;
return 1;
}
15、已知有向图,请给出该图的邻接表的表示和计算顶点的度
16、写出直接插入排序的排序过程。
for(i = 1; i < n; ++i)
{
int temp = a[i];
for (j = i; j > 0 && temp < a[j - 1]; --j)
{
a[j] = a[j - 1];
}
a[j] = temp;
17、给定四个结点A,B,C,D的权值来构造一棵哈夫曼树,写出哈夫曼编码,求出平均编码长度。
18、对给定的带权无向图用PRIM算法求出最小生成树,并写出计算过程。
PRIM(简单版) 最小生成树算法 (Minimum Spanning Tree)
* 输入:图g; // 有向图或者无向图
* 输出:(1)最小生成树长sum;
* (2)最小生成树prev。
* 结构: 图g用邻接矩阵表示,最短边长dist用数组表示。
* 算法:Prim算法
* 复杂度:O(|V|^2)
*/
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;
int n; // n : 顶点个数
vector<vector<int> > g; // g : 图(graph)(用邻接矩阵(adjacent matrix)表示)
vector<bool> known; // known : 各点是否已经选取
vector<int> dist; // dist : 已选取点集到未选取点的最小边长
vector<int> prev; // prev : 最小生成树中各点的前一顶点
int s; // s : 起点(start)
int sum; // sum : 最小生成树长
bool Prim() // 贪心算法(Greedy Algorithm)
{
known.assign(n, false);
dist.assign(n, INT_MAX);
prev.resize(n); // 初始化known、dist、prev。
dist[s] = 0; // 初始化起点到自身的路径长为0。
int i;
for (i = 0; i < n; ++i)
{
int min = INT_MAX, v;
for (int i = 0; i < n; ++i)
if (!known[i] && min > dist[i])
min = dist[i], v = i; // 寻找未知的最短路径长的顶点v,
if (min == INT_MAX) break; // 如果找不到,退出;
known[v] = true; // 如果找到,将顶点v设为已知,
sum += dist[v]; // 调整最小生成树长
for (int w = 0; w < n; ++w) // 遍历所有v指向的顶点w,
if (!known[w] && g[v][w] < INT_MAX && dist[w] > g[v][w])
dist[w] = g[v][w], prev[w] = v; /* 调整顶点w的最短路径长dist和最短路径的前一顶点 prev。 */
}
return i == n; // 如果选取顶点个数为n,成功。
}
int main()
{
n = 7;
g.assign(n, vector<int>(n, INT_MAX));
g[0][1] = g[1][0] = 2; g[0][2] = g[2][0] = 4; g[0][3] = g[3][0] = 1;
g[1][3] = g[3][1] = 3; g[1][4] = g[4][1] = 10;
g[2][3] = g[3][2] = 2; g[2][5] = g[5][2] = 5;
g[3][4] = g[4][3] = 7; g[3][5] = g[5][3] = 8; g[3][6] = g[6][3] = 4;
g[4][6] = g[6][4] = 6;
g[5][6] = g[6][5] = 1;
s = 0; // 起点任选
sum = 0;
if (Prim())
{
cout << sum << endl;
for (int i = 1; i < n; ++i)
if(i != s) cout << prev[i] << "->" << i << endl;
}
else
{
cout << "Some vertex cann't be reached." << endl;
}
system("pause");
return 0;
}
19、对于给定7个数据元素的有序表,采用顺序查找, 假设查找表中每个元素的概率相同,求查找成功时的平均查找长度。
20、写出不带头结点的单链表的合并算法,删除重复结点。
#include<stdio.h>
typedef struct node
{
int data;
struct node *next;
}LNode,*LinkList;
LinkList Create_LinkList()
{
LinkList L=NULL;
LNode *s,*h=NULL;
int x;
scanf("%d",&x);
while(x!=-1)
{
s=(LNode *)malloc(sizeof(LNode));
s->data=x;
if(L==NULL) L=s;
else h->next=s;
h=s;
scanf("%d",&x);
}
if(h!=NULL) h->next=NULL;
return L;
}
void pur_linklist(LinkList H)
{
LNode *q,*r;
q=H;
if(q==NULL) return;
while(q->next)
{
if(q->data==q->next->data)
{ r=q->next;
q->next=r->next;
free(r);
q=q->next;
}
else q=q->next;
}
}
main()
{
LinkList H;
LNode *p;
H=Create_LinkList();
pur_linklist(H);
p=H;
while(p)
{
printf("%d\n",p->data);
p=p->next;
}
}
#include<iostream>
#include<stdlib.h>
using namespace std;
#define MAXSIZE 100
typedef int DataType;
typedef struct
{
DataType * elem; //线性表的基地址
int length; //线性表当前的长度
int listsize; //线性表当前分配的最大存储内容容量
}SeqList;
void CreatList(SeqList *L)
{
cout<<"输入线性表当前长度:";
cin>>L->length;
//分配空间
L->elem = (int*) malloc(L->length*sizeof(int));
cout<<"请按从小到大升序输入线性表的各个元素";
for(int i = 0;i< L->length;i++)
{
cin>>L->elem[i];
}
L->listsize = L->length;
}
void MergeSeqList(SeqList *A, SeqList *B, SeqList *C)
{
DataType *pa, *pb, *pc, *palast, *pblast;
pa = A->elem; pb = B->elem;
C->length = A->length + B->length;
C->elem = (DataType*)malloc(C->length*sizeof(DataType));
if(!C->elem) exit(-1);
palast = A->elem + A->length - 1;
pblast = B->elem + B->length - 1;
pc = C->elem;
while(pa <= palast && pb <= pblast)
{
if(*pa <= *pb)
{
*pc = *pa;
pc++;
pa++;
}
else
{
*pc=*pb;
pc++;
pb++;
}
}
while(pa<=palast) {
*pc=*pa;
pc++;
pa++;
}
while(pb<=pblast)
{
*pc=*pb;
pc++;
pb++;
}
}
void DisList(SeqList *L)
{
for(int i=0;i<L->length;i++)
{
cout<<L->elem[i]<<" ";
}
cout<<endl;
}
void main()
{
SeqList A,B,C;
cout<<"顺序表A:"<<endl;
CreatList(&A);
cout<<"顺序表B:"<<endl;
CreatList(&B);
MergeSeqList(&A,&B, &C);
cout<<"顺序表C:"<<endl;
DisList(&C);
}
数据结构1000个问题与解答-C语言版目录
1.6 数据处理:如排序、查找、字符串处理、统计学应用等,实用性强。1.7 矩阵操作:如矩阵加减乘法、逆矩阵、转置、稀疏矩阵处理等,矩阵运算的深入解析。第2章:结构体 2.1 使用typedef简化类型定义,访问结构元素更为便捷。2.2 结构体实例化,如三维空间点的表示、几何形状模型构建等。2.3 线性...
c语言数据结构问题
存放数据信息 struct ff *next; }; \/\/ 每行的头结点,存放下一行的头结点的地址即指向下一行 struct ff *next_friend; \/\/ 指向下一个数据节点};void main(){ int circle_num,i,j,num; scanf("%d",&circle_num);
关于数据结构(C语言)的几个题
第二步s的后继指向q的后继节点;第三步q的后继指向s 4.查找72只需2步:第一步:设立low、high与mid指针,将72与mid指向的值即48比较;第二部:72比48大,low指向mid+1,重新算出mid,指向72,再与72比较,即查找成功。最多比较次数参考严蔚敏《数据结构》第九章 查找 220页。5.例如图中这...
C语言数据结构中串和数组的三个问题!!高手速来!急!!在线等!
数据结构 树的遍历 数据结构迷宫求解代码 数据结构线性复习表 二维数组 数组与数据结构 什么是数据结构数组 数据结构 数组自测题 数据结构数组bounds c语言数据结构 其他类似问题2009-03-07 数据结构 c语言的问题。在线等答案。~~~ 2011-05-08 C语言的问题。急急急!!!在线等答案!!! 2013-03-19 ...
跪求数据结构(c语言版)的几个问题解答
链表中的每一个节点的数据类型为结构体类型,节点有两个成员:整型成员(实际需要保存的数据)和指向下一个结构体类型节点的指针即下一个节点的地址(事实上,此单链表是用于存放整型数据的动态数组)。链表按此结构对各节点的访问需从链表的头找起,后续节点的地址由当前节点给出。无论在表中访问那一...
C语言数据结构的问题
这个函数应该是用来返回链表中第i个节点的指针的。节点编号从0开始。当i = 0时,for循环在执行时,j 首先被赋值为0,检查条件j < i-1条件不成立,直接跳出循环。此时p的值没有修改,就是第一个节点的值,并直接返回。满足程序要求。这种代码,可以自己在纸上模拟一下,也可以弄明白的。希望可以...
C语言版的数据结构问题:数据结构和数据类型的关系?
那么A属于一个数据结构,a,b,p都属于数据元素。A的初始大小是四个字节,既元素最大的一个的空间。。。里面的成员同时存在,各自有各自的地址,互不干扰。既pA->a,pA->b,pA->p是可以同时存在滴。数据类型 用enum 定义,共用存储单元 enum{int a=1 ,int b ,char c=‘c’}e,b。enum其实...
C语言数据结构问题
第一题:最终单链表的形式就是如上图所示,此题的意思是实现: 裴波那契数列 即 1 1 2 3 5 8 13 21 ……第二题:找到单链表 h中节点中data中最大的,用p 和q指向这个data最大的节点。
一道C语言里的数据结构问题
这个是计算n趋于无穷大时的阶次,因此阶次从低到高的次序为:31+1\/n , 100n + nlog2(n), 20log2(2^n) + n^2, 2^n + 89n^3
一个C语言版数据结构问题。求解释
尾指针指向表尾,当向尾部插入值时速度快(因为如果是头指针的话需要寻址到尾部),因为是单循环链表,P-->next就指向表头了。
管廖通脉: /* 判断相同环的基本思路: (1) 长度相同 (2) 对其中一个循环左移,次数为len-1, 如果循环左移后顺序相同,则为相同环 */ int iMovleft(char *instr) { int len; char tmp; if (instr==NULL) return -1; len = strlen(instr); tmp = instr[0]; memmove(instr, ...
大东区18344958171: C++实现数据结构 某带权有向图G - ?
管廖通脉: dev c++下运行成功#include#include#define MAXV 50 typedef struct//邻接矩阵存储结构 { int no; int info; }VertexType; typedef struct { int edges[MAXV][MAXV]; int n,e; VertexType vexs[MAXV]; }MGraph; typedef struct ANode //邻接表存储结构 { int ...
大东区18344958171: C++数据结构的问题 - ?
管廖通脉: 第一个问题,这个参数是需要压栈的元素,为了提高效率,这里用了引用作为参数 第二个问题,把元素放入数组的栈顶,然后把指向栈顶的计数器加1 第三个问题,那个圆括号是调用了类的构造函数传递的参数
大东区18344958171: c++数据结构 - ?
管廖通脉: 表头不存储元素(也就是所谓的“带头结点的线性表”):A[0]为表头,其数据域为空,指针域指向3,于是首元结点为A[3]即data为78的元素;由于A[3].next=2,于是下一个元素为A[2],其data为50……依此类推,直到某处next域为null时,得到整个线性表{78, 50, 40, 60, 34, 90}.你的题目可能有数据错误.
大东区18344958171: 数据结构编程题(C++编写) - ?
管廖通脉: #include int main(int argc, char *argv[]){int a[100],r,c, n;scanf("%d", &n);for(r=0; r {a[r]=1;for(c=r-1; c>=1; a[c--]+=a[c-1]);printf("%*d", (n-r)*3+1,a[0]);for(c=1; c printf("\n");}return 0;}
大东区18344958171: 求c++数据结构问题答案:已知一单链表(看补充) - ?
管廖通脉: int LinkLen(Linklist head) {int len = 0;while (head){len++;head = head->next;}return len; } void Insert(Linklist head, Lnode *newnode) {if (head == NULL) return;while (head->next)head = head->next; //循环找到最后一个节点head->next = newnode; //将最后一个节点指向新节点 }
大东区18344958171: c++数据结构问题 - ?
管廖通脉: int a[100], o[50], m[50]; for(inti=0; i < 100; i++){ if( i%2) { o[i/2]=i; } else m[i/2]=i;}
大东区18344958171: c++版的数据结构的问题?
管廖通脉: #include <iostream.h> template <class Telem> class SqList { private: Telem *elem; int curlen; int maxlen; public: SqList(int maxsz=100):maxlen(maxsz) { curlen=n; elem=new Telem[maxlen]; } SqList(Telem a[],int n,int maxsz=100):maxlen(maxsz) { ...
大东区18344958171: 2、已知一个带有表头结点的单链表,结点结构为(data , link),假设该链...?
管廖通脉: struct po{char data;po * nextp;}; bool IsWord(char c); bool IsNumber(char c); void sd(po* pointer,po* word, po* number,po* other){ //p是原链表指针,其他是新链表指针 po * p = pointer;//拷贝原链表指针 po * wordlast = word;//用来记录链表最后一...