㈠ 试分别用线性表的向量存储结构和链表存储结构来实现约瑟夫(Josephu)问题。请一并详细注解，谢谢
给分吧。。呵呵
#include<stdio.h>
struct Josephu_node{
int node_nu;
struct Josephu_node * pre;
struct Josephu_node * next;
};
struct Josephu_node * Josephu_node_add(struct Josephu_node * head,int nu)
{
struct Josephu_node * newnode;
if(head == NULL)
{
head= (struct Josephu_node *)malloc(sizeof(struct Josephu_node));
head->node_nu = 1;
head->pre = head;
head->next = head;
printf("Creat Head:%d",head->node_nu);
}else{
newnode = (struct Josephu_node *)malloc(sizeof(struct Josephu_node));
newnode->node_nu = nu;
newnode->pre = head->pre;
newnode->next = head;
head->pre->next = newnode;
head->pre = newnode;
printf(" ,%d",head->pre->node_nu);
}
return head;
}
struct Josephu_node *Joseph_node_del(struct Josephu_node * del_node)
{
struct Joseph_node * del_node_next=del_node->next;
if(del_node != NULL)
{
if(del_node->next != del_node){
del_node->pre->next = del_node->next;
del_node->next->pre = del_node->pre;
}else{
del_node_next = NULL;
}
printf(" %d,",del_node->node_nu);
free(del_node);
del_node = NULL;
return del_node_next;
}
return NULL;
}
int main(int argc ,char ** argv)
{
struct Josephu_node * head=NULL;
struct Josephu_node * node_tmp;
int nu_people=0;
int out_nu =0;
int i;
printf("Please input the nu of the People : ");
scanf("%d",&nu_people);
printf("Please input the rule out nu: ");
scanf("%d",&out_nu);
for(i=0;i<nu_people;i++)
{
head = Josephu_node_add(head,i+1);
}
printf("\n");
i = 0;
node_tmp = head;
printf("Out of the table: ");
while(node_tmp != node_tmp->pre)
{
if(i == out_nu-1)
{
node_tmp = Joseph_node_del(node_tmp);
i=0;
continue;
}
i++;
node_tmp = node_tmp->next;
}
node_tmp = Joseph_node_del(node_tmp);
printf("\n");
return 0;
}
㈡ 以邻接矩阵为存储结构，分别写出基于DFS和BFS遍历
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
template <class VertexType>
class Graph
{
public:
vector<VertexType> vertex; //存放节点数据
int ** edge;//邻边矩阵
int vcount; //顶点个数
int ecount; //边个数
Graph():edge(NULL),vcount(0),ecount(0){}//构造函数
void CreateGraph()//创建矩阵
{
VertexType item; //顶点信息
int v ,u,w; //边信息
cout << "请输入顶点的个数： ";
cin >> vcount;
cout << "请输入顶点" << endl;
for(int i = 0; i < vcount; ++i)
{
cin >> item;
vertex.push_back(item); //将顶点信息存放到向量中
}
edge = new int*[vcount]; //创建二维矩阵
for( i = 0; i < vcount; ++i )
{
edge[i] = new int[vcount];
for( int j = 0 ; j < vcount ; j++ )
edge[i][j] = 0;
}
cout << "请输入边的个数： ";
cin >> ecount;
cout << "请输入边的信息（始点，终点,权重)" << endl;
for( i = 0; i < ecount; ++i)
{
cin >> v >> u >> w;
edge[v][u] = w;
edge[u][v] = w;
cout<<"继续输入"<<endl;
}
}
void ShowGraph()
{
cout << "顶点的个数：" << vcount << endl;
cout << "边的个数：" << ecount << endl;
for(int i = 0; i < vcount; ++i)
{
for(int j = 0; j < vcount; ++j)
cout << edge[i][j] << " ";
cout << endl;
}
}
void DFS(const int v)//深度优先搜索
{
cout << "深度优先搜索" << endl;
int * visited = new int[vcount]; //标志数组
for( int i = 0 ; i < vcount ; i++ )
visited[i] = 0;
DepthFS( v, visited );
cout << endl;
delete[] visited;
}
void DepthFS( const int v , int * visited )//深度优先搜索
{
cout << vertex[v] << " ";
visited[v] = 1;
for(int i = 0; i < vcount; i++ )
{
if( visited[i] == 0 && edge[v][i] != 0 )
{
DepthFS( i, visited );
}
}
}
void BFS(const int v)//广度优先搜索
{
cout << "广度优先搜索" << endl;
int * visited = new int[vcount];
for( int i = 0 ; i < vcount ; i++ )
visited[i] = 0;
queue<int> Q;
Q.push(v); //入队列
while(!Q.empty())
{
int u = Q.front();
Q.pop(); //出队列
cout << vertex[u] << " ";
visited[u] = 1;
for(int j = 0; j < vcount; ++j)
{
if( visited[j] == 0 && edge[u][j] != 0 )
{
visited[j] = 1;
Q.push(j);
}
}
}
cout << endl;
delete[] visited;
}
};
int main()
{
Graph<char> graph;
graph.CreateGraph();
graph.ShowGraph();
cout << "请输入搜索的起始节点：-1表示终止";
int n;
cin>>n;
while(n!=-1)
{
cout << "请输入搜索的起始节点：";
cin >> n;
graph.DFS(n);
graph.BFS(n);
}
return 0;
}
代码还应该多自己写呦，不要走捷径
㈢ 向量的存储方法的是什么
向量通常的存储方法是顺序存储，每个元素在存储中占用的空间大小相同，若第一个元素存放的位置是LOC(k1), 每个元素占用的元素大小为s，则元素ki的存放位置为：
LOC(ki)= LOC(k1)+s * (i-1)
㈣ 已知一颗具有n个结点的完全二叉树以向量作为存储结构，设计一个非递归算法，实现对该树的先序遍历。
public class haha {
public haha(int tree[]) {
int p = 0;
int k = 0;
while(k != tree.length){
if(p < tree.length){
System.out.print(tree[p]+" ");
p = 2*p+1;
k++;
}
else {
p = p/2;
if(p%2==0){
p=p/4-1;
p = 2*p+2;
}
else { p =p+1;
if(p >= tree.length)
p = 2*p+1;
}
}
}
}
public static void main (String[] args) {
int tree[] = {1,2,3,4,5,6,7,8};
new haha(tree);
}
}
㈤ 3、 一棵n个结点的完全二叉树以向量（数组）作为存储结构，试设计非递归算法对该完全二叉树进行前序遍历。
#include<stdio.h>
#defineARRAY_MAX12
intmain()
{
inttree[ARRAY_MAX];
for(inti=0;i<ARRAY_MAX;i++)
tree[i]=i+1;
intflag=0;//记录当前叶子的遍历位置,0刚遍历到这个叶子,1已经遍历完成该叶子的左儿子,2已经遍历完成该叶子的右儿子
intcount=1;//假设tree不为空
while(!(count==1&&flag==2))
{
if(flag==0)
{
printf("%d",tree[count-1]);
if(count*2>ARRAY_MAX)
flag=1;
else
count=count*2;
}
elseif(flag==1)
{
if(count*2+1>ARRAY_MAX)
flag=2;
else
{
count=count*2+1;
flag=0;
}
}
elseif(flag==2)
{
if(count%2==0)
flag=1;
else
flag=2;
count=count/2;
}
}
getchar();
return0;
}
以上代码MicrosoftVisualC++6.0中编译通过，输出的数列为以下下二叉树的前序遍历
连5分都不给，真小气......
㈥ c数据结构判断题
1.错 2.对 3.对 4.错 5.错 6.对（不是向量，是线性） 7.错
㈦ C语言：向量存储结构结构来实现约瑟夫(Josephu)问题。
http://..com/question/408568942.html?oldq=1
㈧ 数据结构里面的向量是什么结构
向量数据亦称“矢量数据”。电子计算机中表示地理空间数据的一种数据结构。它用一系列定义起始点和终止点的线段和它们之间的连接关系来反映地理对象的空间分布。
通过记录线段端点的坐标,向量数据结构能更精确地反映地理事物的位置、长度和面积。空间点实体在向量数据中表示为一对坐标;线实体表示为一串坐标;面实体也表示为一串坐标,并且首尾点重合。
线性表、栈、队、串都属于线性结构，而线性表根据不同的存储结构又可分为顺序表和链表。
(8)以向量作为存储结构扩展阅读
向量一般以数组实现，可能用定长数组实现，存放元素个数有限制，也可能用动态长度数组实现，一旦元素装满后会再次申请更大的空间并将原有数据拷贝过去，C++STL中的vector就是后一种。
向量的记法：印刷体记作黑体（粗体）的字母（如a、b、u、v），书写时在字母顶上加一小箭头“→”。如果给定向量的起点（A）和终点（B），可将向量记作AB（并于顶上加→）。在空间直角坐标系中，也能把向量以数对形式表示，例如xOy平面中(2,3)是一向量。
㈨ 栈以向量存储是什么意思
C 啊,现在空栈是指针在最大下标以上,自然是进栈就需要往下减,并且合法下标只是1..n