数据结构实习(欢迎大家一起在评论区交流学习)
题目一 线性结构的操作
1、创建两个单链表LA=(1,2,5),LB=(2,4,6,7),编写算法,将它们合并成一个单链表LC,要求LC也是非递减有序排列。
源码:
#include<iostream>
using namespace std;
#define NULL 0
typedef struct ListNode { //构建带头结点的单链表结点结构体
int data;
ListNode* next;
}ListNode,*LinkList;
void InitList(LinkList& L) //初始化单链表,头结点指针指向NULL
{
L = new ListNode;
L->next = NULL;
}
void CreateList(LinkList& L,int data) { //用头插法构建单链表,从尾到头输入数据
ListNode* p;
p = new ListNode;
p->data = data;
p->next = L->next;
L->next = p;
}
void connect(LinkList a,LinkList b,LinkList&c){ //a表和b表合并成c表
ListNode* pa, * pb, * pc;
pa = a->next; //pa指向a表的首元结点
pb = b->next; //pb指向b表的首元结点
pc = c = a; //c表不用重新申请空间,直接用a表或b表的地址
while (pa && pb) { //当a表和b表中还有元素的的时候,也就是两表都为真的时候,执行下列语句
if (pa->data <= pb->data) { //如果a表中的值小于b表中的值
pc->next = pa; //pc的next结点就指向a
pc = pa;
pa = pa->next;
}
else {
pc->next = pb; //如果b表中的值小于a表中的值
pc = pb; //pc的next结点就指向b
pb = pb->next;
}
}
pc->next = pa ? pa : pb; //a表或b表其中一个比完了,看谁还有剩余就直接接在pc->next的后头
delete(b); //释放b的头指针
}
//将链表打印
void PrintfList(LinkList L) {
ListNode* p;
p = L->next;
while (p)
{
cout << p->data<<" ";
p = p->next;
}
cout << endl;
}
int main()
{
LinkList LA, LB, LC;
InitList(LA);
InitList(LB);
InitList(LC);
CreateList(LA,5);
CreateList(LA,2);
CreateList(LA,1);
CreateList(LB, 7);
CreateList(LB, 6);
CreateList(LB, 4);
CreateList(LB, 2);
cout << "LA:";
PrintfList(LA);
cout << "LB:";
PrintfList(LB);
connect(LA, LB, LC);
cout << "LC:";
PrintfList(LC);
return 0;
}
题目二 树的操作
2、假设用于通讯的电文仅有7个字母组成,字母在电文中出现的频率为0.19,0.02,0.06,0.32,0.03,0.28,0.10,编写算法,构造对应的哈夫曼树。
源码:
#include<iostream>
using namespace std;
typedef struct { //采用顺序存储结构,定义哈夫曼结点结构体
float weight;
float parent, lch, rch;
}HTnode,*HuffmanTree;
void Show(HuffmanTree HT, int m) //打印哈夫曼树
{
cout << "=========================" << endl;
for (int i = 1; i <= m; ++i)
{
cout << i << ". " << HT[i].weight << " "
<< HT[i].parent << " " << HT[i].lch << " " << HT[i].rch << endl;
cout << "-------------------------" << endl;
}
}
void Select(HuffmanTree& HT, int n, int& s1, int& s2) { //选出两个最小的
int min = 0;
for (int s = 1; s <= n; s++) {
if (HT[s].parent == 0) { //在没有双亲的结点中找
min =s;
break;
}
}
for (int j = 1; j<= n; j++) {
if (HT[j].parent == 0&&HT[j].weight< HT[min].weight) {
min = j;
}
}
s1 = min;
for (int s = 1; s <= n; s++) {
if (HT[s].parent == 0&&s!=s1) {
min = s;
break;
}
}
for (int j = 1; j <= n; j++) {
if (HT[j].parent == 0 && HT[j].weight < HT[min].weight&&j!=s1) {
min = j;
}
}
s2 = min;
}
void CreatHuffmanTree(HuffmanTree& HT, int number) { //构建哈夫曼树,number为结点数
if (number <= 1) {
return;
}
int m = 2 * number - 1; //结点数为number个,结合number-1次,每结合一次就出一个新结点,
// 创建完哈夫曼树后就是number+(number-1)个,也就是2*number-1
HT = new HTnode[m+1]; //因为不用0下标,所以在(2*number-1)的基础上再多申请一个空间
for (int i = 1; i <= m; i++) { //将哈夫曼树的结点初始化
HT[i].lch = 0;
HT[i].rch = 0;
HT[i].parent = 0;
HT[i].weight = 0;
}
cout << "请输入这" << number << "个元素的weight值" << endl;
for (int i = 1; i <= number; i++) { //各结点的输入权重
cin >> HT[i].weight;
}
int s1, s2;
for (int i = number + 1; i <= m; i++) { //在number+1的位置存入两个最小权重相加的新结点权重
int n = i - 1;
Select(HT,n,s1,s2); //调用方法,选出最小的两个,将下标赋值给s1和s2
HT[s1].parent = i; //则这两个最小权值的双亲结点为i;
HT[s2].parent = i;
HT[i].lch = s1;
HT[i].rch = s2;
HT[i].weight =HT[s1].weight + HT[s2].weight;
}
}
int main() {
HuffmanTree HT;
int number;
cout << "请输入结点数:" << endl;
cin >> number;
CreatHuffmanTree(HT, number);
Show(HT, 2*number-1);
return 0;
}
-
- 题目三 图的操作
3、用邻接矩阵法创建有向图,编写算法,实现图的深度优先遍历,输出遍历序列。
源码:
#include<iostream>
#include<iomanip>
using namespace std;
#define NULL 0
#define MAXSIZE 100
int flag[MAXSIZE]; //深度遍历监视器
//邻接矩阵
typedef struct Matrix {
int V_Data; //点数
int E_Data; //边数
char Node[MAXSIZE]; //顶点集
int Weight[MAXSIZE][MAXSIZE]; //权值的二维数组
}MaTrix, * MATRIX;
//邻接矩阵数据结构体
typedef struct Edge {
int v1; //第几行
int v2; //第几列
int weight; //权值
}*EDGE;
void Init_Matrix(MATRIX S, int Vertex) //初始化邻接矩阵
{
S->E_Data = 0;
S->V_Data = Vertex;
int i, j;
for (i = 0; i < Vertex; i++)
{
for (j = 0; j < Vertex; j++)
{
S->Weight[i][j] = 0; //二维数组中的权值全初始化为零
}
}
}
void InSerData(MATRIX S, EDGE E)
{
S->Weight[E->v1][E->v2] = E->weight; //将数据结构体的权值放入到邻接矩阵中
}
void DFS_Begin(MATRIX P, int k, int V) //进行深度遍历
{
int i;
flag[k] = 1; //已经遍历过的,将监视器flag赋值为1
cout <<setw(5)<< P->Node[k] ; //输出结点权值
for (i = 0; i < V; i++)
{
if (!flag[i] && P->Weight[k][i] != 0) //邻接点未被遍历且不为NULL
{
DFS_Begin(P, i, V); //进行套娃,递归调用DFS_Begin
}
}
}
void Init_DFSMatrix(MATRIX P, int V)
{
int i;
for (i = 0; i < V; i++)
{
flag[i] = 0; //将监视器flag初始化为0;
}
for (i = 0; i < V; i++)
{
if (!flag[i]) //如果没有遍历,则进行遍历
DFS_Begin(P, i, V);
}
cout << endl;
}
void InSerEdge_Data(MATRIX S, int edge, int V) //输入矩阵中的数据
{
int i, j;
if (edge > 0)
{
cout<<"请输入边<vi,vj>中的下标i和j和权值(空格分隔!)"<<endl;
for (i = 0; i < edge; i++)
{
EDGE E;
E = new Edge;
cin>>E->v1>>E->v2>>E->weight;
if (E->v1 == E->v2)
{
cout<<"图邻接矩阵对角线为0,输入错误,结束运行"<<endl;
return;
}
InSerData(S, E);
}
printf("请输入要定义的顶点,填入顶点表中: n");
for (j = 0; j < V; j++)
{
cin>>S->Node[j];
}
}
else {
cout<<"输入的边数错误"<<endl;
}
}
void Show_Matrix(MATRIX p, int Vertex) //打印邻接矩阵
{
int i, j;
for (i = 0; i < Vertex; i++)
{
for (j = 0; j < Vertex; j++)
{
cout << " "<<p->Weight[i][j];
}
cout << endl;
}
}
int main()
{
int Vertex;
int edge;
MATRIX p;
cout << "请输入顶点个数: " << endl;
cin >> Vertex;
cout << "请输入边的数量: " << endl;
cin >> edge;
p = new Matrix;
p->V_Data = Vertex;
p->E_Data = edge;
Init_Matrix(p, Vertex);
InSerEdge_Data(p, edge, Vertex);
cout << "无向图邻接矩阵如下:" << endl;
cout << "n----------------------------------" << endl;
Show_Matrix(p, Vertex);
cout<<"n----------------------------------"<<endl;
cout<<"深度遍历—邻接矩阵结果为:"<<endl;
Init_DFSMatrix(p, Vertex);
return 0;
}
-
- 题目四 查找
4、列表中有11个元素(6,12,15,18,22,25,28,35,46,58,60),编写算法,使用折半查找法查找12 和50。
源码:
#include<iostream>
using namespace std;
#define OK 1
#define OVERFLOW -1
#define MAXSIZE 100 //静态分配内存
typedef struct {
int* elem;
int length;
}SqList; //使用线性表的顺序存储结构
int InitList(SqList& L) {
L.elem = new int[MAXSIZE];
if (!L.elem) {
printf("分配内存失败");
return OVERFLOW;
}
L.length = 0;
return OK;
}
void creatList(SqList& L,int data,int &i) { //创建顺序表
L.length++;
L.elem[i] =data;
i++;
}
void BinSrch(SqList L, int k) { //二分查找法
int low = 1;
int high = L.length;
int mid;
while (low<=high)
{
mid = (low + high) / 2;
if (k == L.elem[mid-1]) {
cout << k << "在顺序表中的第" << mid << "个位置" << endl;
return;
}
else if (k < L.elem[mid - 1]) {
high = mid - 1;
}
else
{
low = mid + 1;
}
}
cout << "表中查无此数!!!" << endl;
}
int main() {
int i=0;
SqList L;
InitList(L);
creatList(L, 6, i);
creatList(L, 12, i);
creatList(L, 15, i);
creatList(L, 18, i);
creatList(L, 22, i);
creatList(L, 25, i);
creatList(L, 28, i);
creatList(L, 35, i);
creatList(L, 46, i);
creatList(L, 58, i);
creatList(L, 60, i);
BinSrch(L, 12);
BinSrch(L, 50);
return 0;
}
-
- 题目五 选做题
5、编写算法,求下图任意两个顶点间的最短路径。
源码:
#include<iostream>
using namespace std;
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535
typedef struct
{
char vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
} MGraph;
typedef int Patharc[MAXVEX][MAXVEX]; //建立D[][]二维数组用来存储两顶点之间的最短路径权值
typedef int ShortPathTable[MAXVEX][MAXVEX]; //建立P[][]二维数组来存贮对应顶点的最小路径的前驱矩阵
/* 构建图 */
void CreateMGraph(MGraph* G)
{
int i, j,v,e,x,y,value,weight;
cout << "请输入顶点数和边数,空格分开" << endl;
cin >> v >> e;
G->numEdges = e;
G->numVertexes = v;
cout << "请输入各顶点的值:" << endl;
for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
{
cin >> value;
G->vexs[i] = value;
}
for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
{
for (j = 0; j < G->numVertexes; j++)
{
if (i == j)
G->arc[i][j] = 0;
else
G->arc[i][j] = G->arc[j][i] = INFINITY;
}
}
cout << "请输入边<vi,vj>中的下标i和j和权值(空格分隔!)" << endl;
for (int i = 0; i < G->numEdges; i++) {
cin >> x >> y >> weight;
G->arc[x][y] = weight;
}
}
//弗洛伊德算法
void ShortestPath_Floyd(MGraph MG, Patharc P, ShortPathTable D)
{
int v, w, k;
for (v = 0; v < MG.numVertexes; v++)
{
for (w = 0; w < MG.numVertexes; w++)
{
D[v][w] = MG.arc[v][w]; //将D和P初始化
P[v][w] = w;
}
}
for (k = 0; k < MG.numVertexes; k++)
{
for (v = 0; v < MG.numVertexes; v++)
{
for (w = 0; w < MG.numVertexes; w++)
{
if (D[v][w] > D[v][k] + D[k][w]) //如果v->k->w的权值比v->w的权值小
{
D[v][w] = D[v][k] + D[k][w]; //在表中原位置赋予较小的权值
P[v][w] = P[v][k]; //路径设置经过下标为k的顶点
}
}
}
}
}
int main(void)
{
int v, w, k;
MGraph MG;
Patharc P;
ShortPathTable D;
CreateMGraph(&MG);
ShortestPath_Floyd(MG, P, D);
cout << "各顶点间最短路径如下: " << endl;
for (v = 0; v < MG.numVertexes; v++)
{
for (w = v + 1; w < MG.numVertexes; w++)
{
cout << "v" << v << "--" << "v" << w << " weight: " << D[v][w]
<< " Path: " << v << ' ';
k = P[v][w];
while (k != w)
{
cout << "-> " << k << " ";
k = P[k][w];
}
cout << "-> " << w << endl;
}
cout << endl;
}
return 0;
}
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
二维码