嚴蔚敏數據結構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的存儲空間