0%

数据结构的几个典例

发表于 更新于 分类于 ，

前言：

  • 过一年看都感觉很简单了，但是这些记录下来，看见自己成长的脚印，我觉得是很棒的一些事情，也可也给一些初入数据结构的伙伴们一些启发。

最基本的链表结构

程序功能

1．(菜单)主程序；

2．表的建立及初始化；

3．表的数据插入（插入的数据可是整数或字母）；

4．表的数据删除；

5．表的数据输出；

程序源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
#define maxsize 1024

typedef struct
{
    datatype data[maxsize];
    int last;
}sequenlist;

void CREAT(sequenlist *L)//创建一个初始顺序表

{
    int n,i,j=1;
    L->last=0;
    printf("请输入初始建立的数据个数:\n");
    scanf("%d",&n);
    for(i=0;i<n;i++,j++)
    {
        printf("Data[%d]:",j);
        scanf("%d",&L->data[i]);
        L->last++;
    }

}

int INSERT(sequenlist *L,char x,int i) //将新节点x插入顺序表L上的第i个位置
{
    int j;
    if(((*L).last)>=maxsize-1)
    {
        printf("overflow");
        return NULL;
    }
    else if((i<1)||(i>((*L).last)+1))
    {
        printf("error");
        return NULL;
    }
    else
    {
        for(j=(*L).last;j>=i-1;j--)
            (*L).data[j+1]=(*L).data[j];
        (*L).data[i-1]=x;
        (*L).last=(*L).last+1;
    }
    return(1);
}

int DELETE(sequenlist *L,int i) //从顺序表L上删除第i个位置上的结点
{
    int j;
    if((i<1)||(i>(*L).last+1))
    {
        printf("errer");
        return NULL;
    }
    else
    {
        for(j=i;j<=(*L).last;j++)
            (*L).data[j-1]=(*L).data[j];
        (*L).last--;
    }
    return (1);
}


void SHOW(sequenlist *L)//输出
{
    int i,j=1;
    for(i=0;i<L->last;i++)
        printf("%d	",L->data[i]);
    printf("\n");
}

void charu(sequenlist *L)//插入的导航项
{
    int x,i;
    printf("请输入需要插入的位置：");
    scanf("%d",&i);
    printf("请输入需要插入的数据：");
    scanf("%d",&x);
    INSERT(L,x,i);
}

void shanchu(sequenlist *L)//删除的导航项
{
    int i;
    printf("请输入需要删除的位置：");
    scanf("%d",&i);
    DELETE(L,i);
}

int main()
{
    sequenlist *L;
    sequenlist list;
    L=&list;
    int select;
    while(1)//循环菜单
    {
        printf("请选择要执行的操作：\n1.表的建立及初始化  2.表的数据插入  3.表的数据删除  4.表的数据输出  5.退出\n");
        scanf("%d",&select);
        switch(select)
        {
            case 1 : CREAT(L); break;
            case 2 : charu(L); break;
            case 3 : shanchu(L); break;
            case 4 : SHOW(L);break;
            case 5 : exit(1);break;
            default : printf("输入有误！");break;
        }
    }
    return 0;
}

Huffman树建立与中序遍历的实现

程序功能

  1. (菜单)主程序；

  2. Huffman树的建立；

  3. Huffman树的中序遍历；

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <stdio.h>
#define N 100

struct Node
{
	int data;
	char letter;
	struct Node *lchild;
	struct Node *rchild;
};

struct Node a[N];
int NUM;

struct Node *Huffman()
{
	int i,n;
	int x,y,z;
	int data;
	int s;
	char letter;
	struct Node *lchild;
	struct Node *rchild;
	n=i=NUM;//计算输入了多少个数据的记录值
	x=0;//记录节点运行到了哪里
	y=0;//每一次找出最小和次最小归零的两次循环计数
	z=1;//合并次数的计数


	s=n;//记录下原来有多少个值
	while(z<s)//运行哈夫曼合并 循环次数小于节点数—1 因为z=1开始当z=5时候无法进行循环 即进行了4次 so 这个循环进行s-1次 进行s-1次合并
	{
		while(y<2)//找出第一个最小的和第二个最小的
		{
			for(i=x+1;i<n;i++)//找出最小的数并赋值给a[x]
			{
				if(a[x].data>=a[i].data)
				{
				data=a[x].data;
				letter=a[x].letter;
				lchild=a[x].lchild;
				rchild=a[x].rchild;
				a[x].letter=a[i].letter;
				a[x].data=a[i].data;
				a[x].lchild=a[i].lchild;
				a[x].rchild=a[i].rchild;
				a[i].letter=letter;
				a[i].data=data;
				a[i].rchild=rchild;
				a[i].lchild=lchild;
				}
			}//此时最小的是a[x]
			x++;//此时最小的是a[x-1]，第二小的是a[x]
			y++;
		}
		n++;//添加一个节点存储树根
		a[n-1].lchild=&a[x-2];
  		a[n-1].rchild=&a[x-1];
		a[n-1].data=a[x-2].data+a[x-1].data;
		z++;
		y=0;
	}
	return &a[n-1];
}

void input()
{
	printf("请输入您需要输入的树的数量！\n");
	int x=1;
	scanf("%d",&NUM);
	int i; 
	for(i=0;i<NUM;i++)
	{
		a[i].lchild=NULL;
		a[i].rchild=NULL;
		getchar();
		printf("请输入第%d棵树的字母！\n",x);
		scanf("%c",&a[i].letter);
		printf("请输入第%d棵树的数值！\n",x);
		scanf("%d",&a[i].data);
		x++;
	}
 	 
}

void LDR(struct Node *r)
{
	if(r!=NULL)
	{
		LDR(r->lchild);
		printf("%d       %c\n",r->data,r->letter);
		LDR(r->rchild);
	}
}

int main ()
{
	struct Node *root;
	input();
	root=Huffman();
	printf("中序遍历输出:\n");
	printf("节点值: 字母:\n");
	LDR(root);
	return 0;
}

Prim算法构造最小生成树的实现

程序功能

  1. Prim算法对课本139页图7.16构造最小生成树；

  2. 输出最小生成树的边；

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<stdio.h>
#define n 6 //其他的图需要自行改变

typedef struct
{
	int fromvex,endvex;
	int length;
} edge;

int dist[n][n];
edge T[n-1];

void input()
{
	int i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			printf("请输入点%d到点%d的权值（若无则输入比最大的边的权值还要大的值（例如图最大权值为20则不存在边的输入21））：",i,j);
			scanf("%d",&dist[i-1][j-1]);
		}
}


void PRIM() //从第一个点出发构造联通网络dist的最小生成树，结果放在结构体数组T中
{
	int j,k,m,v,min,max=10000;
	int d;
	edge e;
	for(j=1;j<n;j++)
	{
		T[j-1].fromvex=1;//序号为1的节点，第一个加入树中的节点
		T[j-1].endvex=j+1;
		T[j-1].length=dist[0][j];//循环把所有与1节点相关的边存入T中候选
	}
	for(k=0;k<n-1;k++)//在T中找到最短的边
	{
		min=max;
		for(j=k;j<n-1;j++)
		{
			if(T[j].length<min)//如果所读取的length小于min则把此length赋值给min
			{
				min=T[j].length;
				m=j;
			}//此时T[m]为最短的那一条边
		}
			e=T[m];T[m]=T[k];T[k]=e;//交换后T[k]为加入树的第一边，而T[m]为默认的一个边，则T[k]以前的边都是比T[k]大的边
			v=T[k].endvex;//记录加入树中的第二个节点
			printf("第%d条边 权值为%d 连接了%d和%d两个点\n",k+1,T[k].length,T[k].fromvex,T[k].endvex);
			for(j=k+1;j<n-1;j++)//更新T中的每一条边，过滤掉大的边
			{
				d=dist[v-1][T[j].endvex-1];
				if(d<T[j].length)
				{
					T[j].length=d;
					T[j].fromvex=v;
				}
			}
	}
}

void main()
{
	input();
	PRIM();
}

待处理图

1

变成待处理表格

变成a[6][6]的表格为（这里因为最大的权重为7，则连不到的输入8）

1 2 3 4 5 6
1 8 6 1 5 8 8
2 6 8 5 8 3 8
3 1 5 8 7 5 4
4 5 8 7 8 8 2
5 8 3 5 8 8 6
6 8 8 4 2 6 8

运行结果

2

快速排序算法的实现

程序功能

  1. (菜单)主程序；

  2. 排序数据的建立；

  3. 输出采用快速排序算法实现的每一趟排序结果；

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
#define N 100

int a[N];
int n;
int s1,t1;
int l,h;
void input()
{
	int k=0;
	printf("请输入您需要输入几个数字:");
	scanf("%d",&n);
	t1=n-1;
	while(k<n)
	{
		printf("请输入第%d个数:",k+1);
		scanf("%d",&a[k]);
		k++;
	}
}

void output()
{
	int k=0;
	while(k<n)
	{
		printf("%d ",a[k]);
		k++;
	}
	printf("\n");
}

int partition(int a[N],int l,int h)
{
	int i,j;
	int temp;
	i=l;
	j=h;
	temp=a[i];
	do
	{
		while((a[j]>=temp)&&(i<j))
			j--;
		if(i<j)
			a[i++]=a[j];
		while((a[i]<=temp)&&(i<j))
			i++;
		if(i<j)
			a[j--]=a[i];
	}while(i!=j);
	a[i]=temp;
	return i;
}

void quicksort(int a[N],int s1,int t1)
{
	int i;
	if(s1<t1)
	{
		i=partition(a,s1,t1);
		quicksort(a,s1,i-1);
		quicksort(a,i+1,t1);
	}
}

void main()
{
	input();
	quicksort(a,0,n-1);
	output();
}

运行结果

3

结论

这些都是大二上学期写的实验中 比较经典的，现在回头看，非常的简单，但是当时对自己还是有一些许挑战的，留来记录自己成长吧，不积跬步无以至千里。