# 数据结构实习（欢迎大家一起在评论区交流学习）

题目一 线性结构的操作

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;
{
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;
}
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的头指针
}

//将链表打印
ListNode* p;
p = L->next;
while (p)
{
cout << p->data<<" ";
p = p->next;
}
cout << endl;
}
int main()
{
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;
}``````

1. 题目三 图的操作

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;
}
``````

1. 题目四 查找

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;
}``````

1. 题目五 选做题

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