严蔚敏数据结构c语言代码
❶ 求严蔚敏教授编写的（《数据结构》c语言版）中赫夫曼算法的完整代码
//*************预定义****************
#
include
<stdio.h>
#
include
<malloc.h>
#
include
<iostream.h>
#
include
<conio.h>
#
include
<string.h>
#
define
MAX_LENGTH
100
typedef
char
**HuffmanCode;
//**********数据结构*************
typedef
struct
{
int
weight;
//权值
int
parent,lchild,rchild;
//双亲，左右孩子
}HTNode,*HuffmanTree;
//结点和指针
//**********select函数**************
void
Select(HuffmanTree
HT,int
i,int
&s1,int
&s2)
{
//在建立哈夫曼树的所有结点中选择权值最小的两个结点存放在s1,s2中
int
j,k=1;
while(HT[k].parent!=0)
k++;
s1=k;
for(j=1;j<=i;++j)
if(HT[j].parent==0&&HT[j].weight<HT[s1].weight)
s1=j;
k=1;
while((HT[k].parent!=0||k==s1))
k++;
s2=k;
for(j=1;j<=i;++j)
if(HT[j].parent==0&&HT[j].weight<HT[s2].weight&&j!=s1)
s2=j;
}
//**********构建哈夫曼树***********************
void
HuffmanCoding（huffmanTree
&HT,hu）
void
HuffmanCoding(HuffmanTree
&HT,HuffmanCode&HC,int
*w,int
n)
{
int
m,i,s1,s2,start,c,f;
HuffmanTree
p;
if(n<=1)
return;
m=2*n-1;//由得到的叶子数而计算结点总数
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//分配存储空间
for(p=HT+1,i=1;i<=n;++i,++p,++w)
{
p->weight=*w;//为结点初始化权值
cout<<endl<<"HT["<<i<<"].weight="<<p->weight<<"
";
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;++i,++p)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}//初始化双亲和左右孩子，使他们成为孤立的
cout<<endl<<endl<<"哈弗曼树创建的顺序如下：";
for(i=n+1;i<=m;++i)
{
Select(HT,i-1,s1,s2);
//调用select函数
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;//新结点的权值是s1和s2权值的和
cout<<endl<<"HT["<<s1<<"]
and
HT["<<s2<<"]
create";
cout<<"
HT["<<i<<"],
weight="<<HT[i].weight;
}//每次选择最小的两个结点做左右孩子，权值和为新的结点的权值和，删去连个小的结点
//*********哈夫曼编码*****************
HC=(HuffmanCode)malloc((n+1)*sizeof(char
*));
char
*cd;
cd=(char
*)malloc(n*sizeof(char));
cd[n-1]='\0';
cout<<endl<<endl<<"HuffmanTree编码是："<<endl;
for(i=1;i<=n;++i)//从底下往上寻回编码
{
start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
if(HT[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
HC[i]=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
printf("\nHT[%d]
node's
Huffman
code
is:
%s",i,HC[i]);
}
free(cd);
}
//****************主函数部分********************
void
main()
{
HuffmanTree
HT;
HuffmanCode
HC;
int
n,i;
int
*w,W[MAX_LENGTH];
cout<<"***********本实验实现的是哈夫曼树的建立以及编码*********";//交互信息
cout<<endl<<"请输入哈弗曼树元素的个数：
";
cin>>n;
for(i=0;i<n;++i)
{
cout<<"请输入第
"<<i+1<<"个元素的权值（0~255的整数）：
";
cin>>W[i];
}
w=W;
HuffmanCoding(HT,HC,w,n);
getch();
}
个人觉得这个有点长。。不知道对不对。看看吧~
❷ 严蔚敏的数据结构（C语言版）最短路径算法 代码段：p[w]=p[v];p[w][w]=true;//p[w]=p[v]+[w]是什么意思
二维数组P中保存的是v0到各个点的最短路径。在v行中，值为true的列连起来，就是v0到v的最短路径。因为v0到w点的最短路径是v0到v的最短路径在加上<v,w>，所以w列先复制所有的v列的值，然后在将p[w][w]=true。此时w行中所有值为true列，就是v0到w的最短路径
❸ 求严蔚敏的 c语言版的 数据结构 创建一个链表的 代码、
这是我写的，可以运行成功
#include<stdio.h>
struct link
{
char ch;
struct link *next;
};
typedef struct link LINK;
/*
//创建(非递归) 头结点不存储数据
LINK* Create()
{
LINK *p,*q,*head;
char c;
head=(LINK *)malloc(sizeof(LINK));
head->next=NULL;
p=head;
scanf("%c",&c);
while(c!='@')
{
q=(LINK *)malloc(sizeof(LINK));
q->ch=c;
q->next=NULL;
p->next=q;
p=q;
scanf("%c",&c);
}
return(head);
}
*/
//创建(递归) 头结点存储数据
LINK *Create()
{
LINK *head,*p,*q;
char c;
scanf("%c",&c);
if(c=='@')
return(NULL);
else
{
head=(LINK *)malloc(sizeof(LINK));
head->ch=c;
head->next=Create();
return(head);
}
}
//遍历
void vTraverse(LINK *head)
{
LINK *p;
p=head;
//p=p->next;
while(p!=NULL)
{
printf("%2c",p->ch);
p=p->next;
}
}
/*******************************
* 功能：删除链表中指定位置pos的节点
* 参数：head 链表头结点
pos 位置（1开头）
* 返回值：1删除成功 0失败
********************************/
int iDelete(LINK *head,int pos)
{
int i=1;
LINK *p,*q;
p=head;
q=p;
p=p->next;
while(p!=NULL)
{
if(i==pos)
{
q->next=p->next;
break;
}
else
{
q=p;
p=p->next;
i++;
}
}
if(p==NULL) return(0);
else
return(1);
}
/********************************************
* 功能：在指定位置插入指定的字符
* 参数：head 链表头结点
pos位置
chInsert 插入的字符
* 返回值：0 插入失败 1插入成功
*********************************************/
int iInsert(LINK *head,int pos,char chInsert)
{
int i=1;
LINK *p,*q;
p=head;
//p=p->next;
while(p!=NULL)
{
if(i==pos)
{
q=(LINK *)malloc(sizeof(LINK));
q->ch=chInsert;
q->next=p->next;
p->next=q;
break;
}
else
{
p=p->next;
i++;
}
}
if(NULL==p)
return(0);
else
return(1);
}
int main(void)
{
//头节点不储存数据
LINK *head=NULL;
head=Create();
vTraverse(head);
if(iInsert(head,2,'Q')==1)
vTraverse(head);
return(0);
}
❹ 跪求，数据结构堆排序的完整代码严蔚敏版本的。要求用书上的算法实现，c语言版本的。
哥们，这是严蔚敏的数据结构书上的堆排序算法，代码如下，试一下吧
堆排序heapsort（第26行至37行）首先调用建堆函数buildheap，将n个待排序记录建立一个初始堆，然后重复执行n-1次元素交换（第32行至34行）和siftdown进行堆排序。init和print函数与图8.1相同。为节约篇幅，只给出其函数原型，略去其实现。
1 #include <stdlib.h>
2 #define N 8
3 int a[N];
4 void init()
5 void print()
6 int siftdown(int i,int n)
7 {
8 int t;
9 int j = 2*i + 1;
10 while (j < n) {
11 if ((j < (n-1)) && (a[j] < a[j+1])) j++;
12 if (a[i] >= a[j]) return 0;
13 t = a[i];
14 a[i] = a[j];
15 a[j] = t;
16 i = j;
17 j = 2*i + 1;
18 }
19 }
20 void buildheap(int n)
21 {
22 int i;
23 for (i = n/2-1;i >= 0;i--)
24 siftdown(i,n);
25 }
26 void heapsort(int n)
27 {
28 int i,t,j;
29 buildheap(n);
30 for (i = 0;i < n;i++) {
31 print(N);
32 t = a[0];
33 a[0] = a[n-i-1];
34 a[n-i-1] = t;
35 siftdown(0,n-i-1);
36 }
37 }
38 void main()
39 {
40 init(N);
41 print(N);
42 heapsort(N);
43 print(N);
44 }
❺ 关于严蔚敏C语言版数据结构算法2-4的疑问
1、newBase
=
(ElemType
*)
realloc
(L.elem,
(L.listsize
+
LISTINCREMENT)
*
sizeof(ElemType));
//为初始
顺序表
以LISTINCREMENT
大小
重新增加存储空间，如果去掉L.elem，则新增
空间
的对象不明。
2、增加分配的
代码
意思是，在当前分配空间不足时加ListIncrement大小的空间，不够再加，一直加到空间够用为止，于是就保证了分配的空间足够用了。3、顺序表是从0号位置开始计数的，所以
长度
为Length顺序表最后一位为Length-1，同样，第i个
元素
的位置也就为[i-1]了。4、
源代码
段寻找位置的
原理
是先让一个
指针
q指向要插入数的位置，指针p指向表尾[Length-1]，然后比较p,q的值，如果p>=q，就把p指向的元素向后挪一位[Length](也就是表长加1了)，P就指向倒数第二个[Length-2]位置；再用p,q做个比较，如果p仍然大于或等于q,那么继续吧p指向的数向后挪一位[Length-1]，p又指向下一个数[Length-3]，以此内推，
直到最后
p指向第[i-2]那位，此时第[i-1]就为空的，正好把要插入的数插进去。你所给的
算法
，首先把位置和长度都搞错了，你的意思可能是这样的吧：for(p=&L.elem[i-1];p<=&L.elem[L.length-1];++p)
{
*(p+1)=*p;
Length++;}如果是这样的话，那不仅你要插的元素插不进去，反而把从[i-1]位置开始后面所有的元素都被复制成了L.elem[i-1]相同的元素了。
❻ 关于严蔚敏C语言版数据结构的栈PUSH实现代码
ElemType是笔误S.base=(ElemType *)malloc (S.base, (S.stacksize+STACKINCREMENT)*sizeof(Elemtype));这个是分配一段内存，长度是(S.stacksize+STACKINCREMENT)*sizeof(Elemtype)这么多字节，因为这个函数是重新分配的，所以也要分配表s.base的存储空间