数据结构实习(欢迎大家一起在评论区交流学习)

                                                         题目一 线性结构的操作

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

相关知识点详细视频https://www.bilibili.com/video/BV1nJ411V7bd?p=43https://www.bilibili.com/video/BV1nJ411V7bd?p=43


                                          题目二 树的操作

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

相关知识点视频讲解https://www.bilibili.com/video/BV1nJ411V7bd?p=101https://www.bilibili.com/video/BV1nJ411V7bd?p=101

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

相关知识点视频讲解https://www.bilibili.com/video/BV1nJ411V7bd?p=133https://www.bilibili.com/video/BV1nJ411V7bd?p=133

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>