編寫報告能讓我們對自己未來的工作有更透徹的理解，隨著人們自身素質(zhì)提升。我們通常會使用到報告，撰寫報告需要注意哪些內(nèi)容呢？出國留學網(wǎng)的編輯認真整理了大量信息推出了這篇數(shù)據(jù)結(jié)構(gòu)報告，本文供你參考，希望能幫到你！
數(shù)據(jù)結(jié)構(gòu)報告【篇1】
一、實驗目的及要求
1)掌握棧和隊列這兩種特殊的線性表，熟悉它們的特性，在實際問題背景下靈活運用它們。
本實驗訓練的要點是“棧”和“隊列”的觀點;
二、實驗內(nèi)容
1) 利用棧，實現(xiàn)數(shù)制轉(zhuǎn)換。
2) 利用棧，實現(xiàn)任一個表達式中的語法檢查(選做)。
3) 編程實現(xiàn)隊列在兩種存儲結(jié)構(gòu)中的基本操作(隊列的初始化、判隊列空、入隊列、出隊列);
三、實驗流程、操作步驟或核心代碼、算法片段
順序棧：
Status InitStack(SqStack &S)
{
S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S.base)
return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status DestoryStack(SqStack &S)
{
free(S.base);
return OK;
}
Status ClearStack(SqStack &S)
{
S.top=S.base;
return OK;
}
Status StackEmpty(SqStack S)
{
if(S.base==S.top)
return OK;
return ERROR;
}
int StackLength(SqStack S)
{
return S.top-S.base;
}
Status GetTop(SqStack S,ElemType &e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base) return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Push(SqStack &S,ElemType e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base)
return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,ElemType &e)
{
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
Status StackTraverse(SqStack S)
{
ElemType *p;
p=(ElemType *)malloc(sizeof(ElemType));
if(!p) return ERROR;
p=S.top;
while(p!=S.base)//S.top上面一個...
{
p--;
printf("%d ",*p);
}
return OK;
}
Status Compare(SqStack &S)
{
int flag,TURE=OK,FALSE=ERROR;
ElemType e,x;
InitStack(S);
flag=OK;
printf("請輸入要進棧或出棧的元素：");
while((x= getchar())!='#'&&flag)
{
switch (x)
{
case '(':
case '[':
case '{':
if(Push(S,x)==OK)
printf("括號匹配成功!\n\n");
break;
case ')':
if(Pop(S,e)==ERROR || e!='(')
{
printf("沒有滿足條件\n");
flag=FALSE;
}
break;
case ']':
if ( Pop(S,e)==ERROR || e!='[')
flag=FALSE;
break;
case '}':
if ( Pop(S,e)==ERROR || e!='{')
flag=FALSE;
break;
}
}
if (flag && x=='#' && StackEmpty(S))
return OK;
else
return ERROR;
}
鏈隊列：
Status InitQueue(LinkQueue &Q)
{
Q.front =Q.rear=
(QueuePtr)malloc(sizeof(QNode));
if (!Q.front) return ERROR;
Q.front->next = NULL;
return OK;
}
Status DestoryQueue(LinkQueue &Q)
{
while(Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}
Status QueueEmpty(LinkQueue &Q)
{
if(Q.front->next==NULL)
return OK;
return ERROR;
}
Status QueueLength(LinkQueue Q)
{
int i=0;
QueuePtr p,q;
p=Q.front;
while(p->next)
{
i++;
p=Q.front;
q=p->next;
p=q;
}
return i;
}
Status GetHead(LinkQueue Q,ElemType &e)
{
QueuePtr p;
p=Q.front->next;
if(!p)
return ERROR;
e=p->data;
return e;
}
Status ClearQueue(LinkQueue &Q)
{
QueuePtr p;
while(Q.front->next )
{
p=Q.front->next;
free(Q.front);
Q.front=p;
}
Q.front->next=NULL;
Q.rear->next=NULL;
return OK;
}
Status EnQueue(LinkQueue &Q,ElemType e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof (QNode));
if(!p)
return ERROR;
p->data=e;
p->next=NULL;
Q.rear->next = p;
Q.rear=p; //p->next 為空
return OK;
}
Status DeQueue(LinkQueue &Q,ElemType &e)
數(shù)據(jù)結(jié)構(gòu)報告【篇2】
一、實驗目的：
了解哈夫曼樹的思想和相關(guān)概念;
1.初始化：能夠?qū)斎氲娜我忾L度的字符串s進行統(tǒng)計，統(tǒng)計每個字符的頻度，并建立哈夫曼樹。
2.建立編碼表：利用已經(jīng)建好的哈夫曼樹進行編碼，并將每個字符的編碼輸出。
3.編碼：根據(jù)編碼表對輸入的字符串進行編碼，并將編碼后的字符串輸出。
4.譯碼：利用已經(jīng)建好的哈夫曼樹對編碼后的字符串進行譯碼，并輸出譯碼結(jié)果。
6.計算輸入的字符串編碼前和編碼后的長度，并進行分析，討論哈夫曼編碼的壓縮效果。
7.用戶界面可以設計成“菜單”方式，能進行交互，根據(jù)輸入的字符串中每個字符出現(xiàn)的次數(shù)統(tǒng)計頻度，對沒有出現(xiàn)的字符一律不用編碼。
Data：
哈夫曼樹類的數(shù)據(jù)域，繼承節(jié)點類型為int的二叉樹 class HuffmanTree:public BiTree
data:
struct BiNode //二叉樹的結(jié)點結(jié)構(gòu) {
};
待編碼字符串由鍵盤輸入，輸入時用鏈表存儲，鏈表節(jié)點為 struct Node
1.初始化函數(shù)(void HuffmanTree::Init(string Input))
2.獲得輸入字符串的第一個字符，并將其插入到鏈表尾部,n=1(n記錄的是鏈表
3.1 將當前取出的字符與鏈表中已經(jīng)存在的字符逐個比較，如果當前取出
的字符與鏈表中已經(jīng)存在的某個字符相同，則鏈表中該字符的權(quán)值加1。
3.2 如果當前取出的字符與鏈表中已經(jīng)存在的字符都不相同，則將其加入
到鏈表尾部，同時n++
4.tSize=n(tSize記錄鏈表中字符總數(shù)，即哈夫曼樹中葉子節(jié)點總數(shù))
源代碼：
{
Node *front=new Node; //初始化鏈表的頭結(jié)點
throw exception(“堆空間用盡”);
front->next=NULL;
front->character=NULL;
front->count=0;
Node *pfront=front;
Node* New1=new Node;
throw exception(“堆空間用盡”);
New1->character=ch; //將第一個字符插入鏈表
New1->count=1;
New1->next=pfront->next;
pfront->next=New1;
bool replace=0; //判斷在已經(jīng)寫入鏈表的字符中是否有與當前讀出的字符相同的字符 int n=1; //統(tǒng)計鏈表中字符個數(shù)
{
pfront=pfront->next;
if((int)pfront->character == (int)ch) //如果在鏈表中有與當前字符相同的字符，
{
pfront->count++;
replace=1;
break;
}
}while(pfront->next);
if(!replace) //如果在鏈表中沒找到與當前字符相同的字符，則將該字符作為新成 員插入鏈表
{
Node* New=new Node;
throw exception(“堆空間用盡”);
New->character=ch;
New->count=1;
New->next=pfront->next;
pfront->next=New;
n++;
}
pfront=front; //重置pfront和replace變量為默認值 replace=0;
}
pfront=front;
{
front=pfront;
pfront=pfront->next;
front;
}
時間復雜度：
2.創(chuàng)建哈夫曼樹(void HuffmanTree::CreateCodeTable(Node *p))
算法偽代碼：
2. 將存儲字符及其權(quán)值的鏈表中的字符逐個寫入三叉鏈表的前tSize個結(jié)點
3.1 從存儲字符及其權(quán)值的鏈表中取出兩個權(quán)值最小的結(jié)點x,y，記錄其
下標x,y。
3.3 將下標為x的結(jié)點設置為i結(jié)點的左孩子，將下標為y的結(jié)點設置為
源代碼：
void HuffmanTree::CreateHTree(Node *p,int n)
{
root= new BiNode[2*n-1]; //初始化哈夫曼樹
Node *front=p->next;
throw exception(“沒有輸入字符”);
root[i].data=front->count;
root[i].lchild=-1;
root[i].rchild=-1;
root[i].parent=-1;
front=front->next;
}
front=p;
int New1,New2;
{
SelectMin(New1,New2,0,i); //從0~i中選出兩個權(quán)值最小的結(jié)點
root[New1].parent=root[New2].parent=i; //用兩個權(quán)值最小的結(jié)點生成新結(jié)點，
root[i].data=root[New1].data+root[New2].data;//新結(jié)點的權(quán)值為其孩子的權(quán)值的和 root[i].lchild=New1;
root[i].rchild=New2;
root[i].parent=-1;
}
}
時間復雜度：
在選取兩個權(quán)值最小的結(jié)點的函數(shù)中要遍歷鏈表，時間復雜度為O(n),故該函數(shù)
3.創(chuàng)建編碼表(void HuffmanTree::CreateCodeTable(Node *p))
2.4.1 如果當前葉子結(jié)點是其雙親的左孩子，則其對應的編碼為0，否
2.4.2 child指針指向葉子結(jié)點的雙親，parent指針指向child指針的雙親，
源代碼：
void HuffmanTree::CreateCodeTable(Node *p)
{
HCodeTable=new HCode[tSize]; //初始化編碼表
Node *front=p->next;
{
HCodeTable[i].data=front->character; //將第i個字符寫入編碼表
int parent=root[i].parent; //得到第i個字符對應的葉子節(jié)點的雙親
int k=0;
if(tSize==1) //如果文本中只有一種字符，它的編碼為0
{
HCodeTable[i].code[k]='0';
k++;
}
while(parent!=-1) //從第i個字符對應的葉子節(jié)點開始，尋找它到根結(jié)點的路徑
{
if(child==root[parent].lchild) //如果當前結(jié)點為雙親的左孩子，則編碼為0，
HCodeTable[i].code[k]='0';
HCodeTable[i].code[k]='1';
k++;
child=parent;
parent=root[child].parent;
}
HCodeTable[i].code[k]='';
Reverse(HCodeTable[i].code); //將編碼逆置
}
{
cout
parent=root[parent].lchild;
parent=root[parent].rchild;
i++;
}
if(tSize==1) //如果編碼表只有一個字符，則根結(jié)點即為葉子結(jié)點 i++;
d.append(1,HCodeTable[parent].data);//將葉子節(jié)點對應的字符追加到解碼串中 }
cout
}
時間復雜度：
8. 計算哈夫曼編碼的壓縮比(void HuffmanTree::Calculate(string s1,string s2)) 算法偽代碼：
2. 獲得編碼后的字符串的長度，將其除以8然后向上取整，得到其占用的字
源代碼：
void HuffmanTree::Calculate(string s1,string s2)
{
int cal1=s1.length();
int cal2=s2.length();
cal2=ceill((float)cal2/8); //將編碼串的比特數(shù)轉(zhuǎn)化為字節(jié)數(shù) cout
cout
cout
9. 打印哈夫曼樹(void HuffmanTree::PrintTree(int TreeNode,int layer) ) 算法偽代碼：
3. 根據(jù)當前結(jié)點所在的層次確定其前面要輸出多少空格，先輸出空格，在打
源代碼：
void HuffmanTree::PrintTree(int TreeNode,int layer)
{
if(TreeNode==-1) //如果待打印結(jié)點為空，則返回 return;
{
PrintTree(root[TreeNode].rchild,layer+1); //先打印該結(jié)點的右子樹，layer記錄
cout
cout
PrintTree(root[TreeNode].lchild,layer+1); //打印該結(jié)點的左子樹
}
}
10. 菜單函數(shù)(void HuffmanTree::Menu())
算法偽代碼：
1. 逐一讀取鍵盤緩存區(qū)中的字符，并將它們逐一追加到記錄輸入字符串的
3.利用string變量創(chuàng)建哈夫曼樹，初始化編碼表。
cout
string Input;
char letter;
{
letter=cin.get();
Input.append(1,letter);
}while(letter!=' ');
Input.erase(Input.length()-1,1); //去掉Input末尾的回車符
Init(Input); //根據(jù)輸入的字符串創(chuàng)建哈夫曼樹及其編碼表 cout
PrintTree(2*tSize-1-1,1); //打印哈夫曼樹
cout
string d1,d2;
cout
cout
cout
Calculate(Input,d1); //計算編碼前后的壓縮比
1.由于題目要求能輸入任意長的字符串，所以本程序采用了string變量來記錄輸入
2.打印哈夫曼樹時采用了遞歸函數(shù)，且采用了凹凸表的形式打印哈夫曼樹。
主函數(shù)流程圖：
經(jīng)過這次實驗，我了解了哈夫曼樹的創(chuàng)建過程，了解了一種不等長編碼的方法，用設斷點調(diào)試的方法更加熟練，同時熟悉了STL中string類型的用法，對C++更加熟悉
數(shù)據(jù)結(jié)構(gòu)報告【篇3】
二.實驗目的：
1、使學生熟練掌握哈夫曼樹的生成算法。
2、熟練掌握哈夫曼編碼的方法。
三.問題描述：
已知n個字符在原文中出現(xiàn)的頻率，求它們的哈夫曼編碼。
1、讀入n個字符，以及字符的權(quán)值，試建立一棵Huffman樹。
2、根據(jù)生成的Huffman樹，求每個字符的Huffman編碼。并對給定的待編碼字符序列進行編碼，并輸出。
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //動態(tài)分配數(shù)組存儲郝夫曼樹
typedef char* *HuffmanCode;//動態(tài)分配數(shù)組存儲郝夫曼編碼
(2)主要的實現(xiàn)思路：
1.基本上沒有什么太大的問題，在調(diào)用select這個函數(shù)時，想把權(quán)值最小的兩個結(jié)點的序號帶回HuffmanCoding，所以把那2個序號設置成了引用。
2.在編程過程中，在什么時候分配內(nèi)存，什么時候初始化花的時間比較長
3.最后基本上實現(xiàn)后，發(fā)現(xiàn)結(jié)果仍然存在問題，經(jīng)過分步調(diào)試，發(fā)現(xiàn)了特別低級的輸入錯誤。把HT[i].weight=HT[s1].weight+HT[s2].weight;中的s2寫成了i
typedef struct{
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char* *HuffmanCode;
void Select(HuffmanTree &HT,int k,int &s1,int &s2)
{ int i;
i=1;
while(i
s1=i;
{
if(HT[i].parent==0&&HT[i].weight
{
if(HT[i].parent==0&&i!=s1)break;
}
s2=i;
{
if(HT[i].parent==0&&i!=s1&&HT[i].weight
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
int m,c,f,s1,s2,i,start;
char *cd;
if(n
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0號單元未用，預分配m+1個單元
HuffmanTree p=HT+1;
{
p->weight=*w;
p->parent=p->rchild=p->lchild=0;
{
p->weight=p->parent=p->rchild=p->lchild=0;
{
Select(HT,i-1,s1,s2); //選出當前權(quán)值最小的
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;
HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); //分配n個字符編碼的頭指針變量
cd=(char*)malloc(n*sizeof(char)); //分配求編碼的工作空間
for(i=1;i
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //從葉子到根逆向求編碼
{
if(HT[f].lchild==c)cd[--start]='0';
cd[--start]='1';
}
HC[i]=(char*)malloc((n-start)*sizeof(char)); //為第i個字符編碼分配空間
strcpy(HC[i],&cd[start]);//從cd復制編碼到HC
HuffmanTree HT;
HuffmanCode HC;
cout
cin>>n;
w=(int*)malloc((n+1)*sizeof(int)); //記錄權(quán)值，號單元未用
ch=(char*)malloc((n+1)*sizeof(char));//記錄字符，號單元未用
cout
{
cout
}
數(shù)據(jù)結(jié)構(gòu)報告【篇4】
首先你要知道什么是數(shù)據(jù)結(jié)構(gòu)，學習數(shù)據(jù)結(jié)構(gòu)的意義。這將是你學習的動力所在。計算機軟件都用到了數(shù)據(jù)結(jié)構(gòu)。所以，學好數(shù)據(jù)結(jié)構(gòu)對于你將來從事計算機編程類的工作有十分重要的作用。
數(shù)據(jù)結(jié)構(gòu)中的基本概念，你要一定清楚。平時要多看書，要在計算機上去調(diào)試程序，在調(diào)試的過程中，你才能發(fā)現(xiàn)自己的問題，然后及時解決。在上機調(diào)試的過程中，更要大膽嘗試，注重運用。拿到一個題時，更要深入分析，嘗試用不同的算法去設計。當然編程的時候，要注意格式。比如：變量一定要先定義后使用。變量的定義不要定義在中間。
算法與數(shù)據(jù)結(jié)構(gòu)是緊密聯(lián)系，所以你算法一定要會。如果你是學生，只需把課本上出現(xiàn)的搞懂就好了，比如線性表的插入，刪除，查找算法，它都是固定的。你就要理解，當然你要學會畫圖。對于書中的內(nèi)容要熟悉。
數(shù)據(jù)結(jié)構(gòu)的大綱如下：線性表、棧和隊列，串、數(shù)組和廣義表、樹與森林、圖、還有就是查找和排序。簡單的總結(jié)一下也就是它的邏輯結(jié)構(gòu)：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。這些基本的內(nèi)容你如果搞懂了，你的數(shù)據(jù)結(jié)構(gòu)也就學好了。
要嚴格要求自己。在學習算法的過程中，你要想它為什么要這樣設計?它的優(yōu)點在哪里?想著去改進算法，慢慢的的你的邏輯思維能力也就提高了。你會發(fā)現(xiàn)其實數(shù)據(jù)結(jié)構(gòu)也就那么回事，不是很難。
有不懂得地方要及時請教老師，不要不懂裝懂。不要放過任何一個細節(jié)，因為我的專業(yè)就是計算機，所以有很多都是深有體會。
首先你要清楚一周內(nèi)所要做的事情，然后制定一張作息時間表。在表上填上那些非花不可的時間，如吃飯、睡覺、上課、娛樂等。安排這些時間之后，選定合適的、固定的時間用于學習，必須留出足夠的時間來完成正常的閱讀和課后作業(yè)。當然，學習不應該占據(jù)作息時間表上全部的空閑時間，總得給休息、業(yè)余愛好、娛樂留出一些時間，這一點對學習很重要。一張作息時間表也許不能解決你所有的問題，但是它能讓你了解如何支配你這一周的時間，從而使你有充足的時間學習和娛樂。
這就意味著在你認真投入學習之前，先把要學習的內(nèi)容快速瀏覽一遍，了解學習的大致內(nèi)容及結(jié)構(gòu)，以便能及時理解和消化學習內(nèi)容。當然，你要注意輕重詳略，在不太重要的地方你可以花少點時間，在重要的地方，你可以稍微放慢學習進程。
學習成績好的學生很大程度上得益于在課堂上充分利用時間，這也意味著在課后少花些功夫。課堂上要及時配合老師，做好筆記來幫助自己記住老師講授的內(nèi)容，尤其重要的是要積極地獨立思考，跟得上老師的思維。
課堂上做的筆記你要在課后及時復習，不僅要復習老師在課堂上講授的重要內(nèi)容，還要復習那些你仍感模糊的認識。如果你堅持定期復習筆記和課本，并做一些相關(guān)的習題，你定能更深刻地理解這些內(nèi)容，你的記憶也會保持更久。定期復習能有效地提高你的考試成績。
選擇某個地方作你的學習之處，這一點很重要。它可以是你的單間書房或教室或圖書館，但是它必須是舒適的，安靜而沒有干擾。當你開始學習時，你應該全神貫注于你的功課，切忌“身在曹營心在漢”。
平時測驗的目的主要看你掌握功課程度如何，所以你不要弄虛作假，而應心平氣和地對待它?；蛟S，你有一兩次考試成績不盡如人意，但是這不要緊，只要學習扎實，認真對待，下一次一定會考出好成績來。通過測驗，可讓你了解下一步學習更需要用功夫的地方，更有助于你把新學的知識記得牢固。
數(shù)據(jù)結(jié)構(gòu)報告【篇5】
一、需求分析1、程序所實現(xiàn)的功能；2、程序的輸入，包含輸入的數(shù)據(jù)格式和說明；3、程序的輸出，程序輸出的形式；4、測試數(shù)據(jù)，如果程序輸入的數(shù)據(jù)量比較大，需要給出測試數(shù)據(jù)；5、合作人及其分工二、設計說明1、主要的數(shù)據(jù)結(jié)構(gòu)設計說明；2、程序的主要流程圖；3、程序的主要模塊，要求對主要流程圖中出現(xiàn)的模塊進行說明4、程序的主要函數(shù)及其偽代碼說明(不需要完整的代碼)；5、合作人設計分工三、上機結(jié)果及體會1、合作人編碼分工2、實際完成的情況說明（完成的功能，支持的數(shù)據(jù)類型等）；3、程序的性能分析，包括時空分析；4、上機過程中出現(xiàn)的問題及其解決方案；5、程序中可以改進的地方說明；6、程序中可以擴充的功能及設計實現(xiàn)假想；說明：1、如果程序比較大，可以將設計說明分為概要設計和詳細設計兩部分。概要設計主要負責程序的流程、模塊、抽象數(shù)據(jù)類型設計；詳細設計負責程序的數(shù)據(jù)類型定義和主要函數(shù)的說明。2、設計說明中，不需要寫出代碼或者模塊的詳細代碼，只需要寫出主要函數(shù)的偽代碼說明。
數(shù)據(jù)結(jié)構(gòu)報告【篇6】
1)掌握棧和隊列這兩種特殊的線性表，熟悉它們的特性，在實際問題背景下靈活運用它們。
本實驗訓練的要點是“?！焙汀瓣犃小钡挠^點;
1) 利用棧，實現(xiàn)數(shù)制轉(zhuǎn)換。
2) 利用棧，實現(xiàn)任一個表達式中的語法檢查(選做)。
3) 編程實現(xiàn)隊列在兩種存儲結(jié)構(gòu)中的基本操作(隊列的初始化、判隊列空、入隊列、出隊列);
順序棧：
Status InitStack(SqStack &S)
{
S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
return ERROR;
=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status DestoryStack(SqStack &S)
{
free(S.base);
return OK;
}
Status ClearStack(SqStack &S)
{
=S.base;
return OK;
}
return OK;
return ERROR;
}
{
return -S.base;
}
Status GetTop(SqStack S,ElemType &e)
{
if(-S.base>=S.stacksize)
{
S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base) return ERROR;
=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*++=e;
return OK;
}
Status Push(SqStack &S,ElemType e)
{
if(-S.base>=S.stacksize)
{
S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
return ERROR;
=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*++=e;
return OK;
}
Status Pop(SqStack &S,ElemType &e)
return ERROR;
e=*--;
return OK;
}
{
ElemType *p;
p=(ElemType *)malloc(sizeof(ElemType));
if(!p) return ERROR;
p=;
while(p!=S.base)//上面一個...
{
p--;
printf(“%d ”,*p);
}
return OK;
}
{
int flag,TURE=OK,FALSE=ERROR;
ElemType e,x;
InitStack(S);
flag=OK;
while((x= getchar)!='#'&&flag)
case '{':
printf(“括號匹配成功!nn”);
break;
printf(“沒有滿足條件n”);
flag=FALSE;
}
break;
break;
break;
}
}
if (flag && x=='#' && StackEmpty(S))
return ERROR;
}
鏈隊列：
Status InitQueue(LinkQueue &Q)
{
Q.front =Q.rear=
(QueuePtr)malloc(sizeof(QNode));
if (!Q.front) return ERROR;
Q.front->next = NULL;
return OK;
}
Status DestoryQueue(LinkQueue &Q)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}
Status QueueEmpty(LinkQueue &Q)
{
return OK;
return ERROR;
}
{
int i=0;
QueuePtr p,q;
p=Q.front;
{
i++;
p=Q.front;
q=p->next;
p=q;
}
return i;
}
Status GetHead(LinkQueue Q,ElemType &e)
{
QueuePtr p;
p=Q.front->next;
return ERROR;
e=p->data;
return e;
}
Status ClearQueue(LinkQueue &Q)
{
QueuePtr p;
{
p=Q.front->next;
free(Q.front);
Q.front=p;
}
Q.front->next=NULL;
Q.rear->next=NULL;
return OK;
}
Status EnQueue(LinkQueue &Q,ElemType e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof (QNode));
return ERROR;
p->data=e;
p->next=NULL;
Q.rear->next = p;
return OK;
}
Status DeQueue(LinkQueue &Q,ElemType &e)
{
QueuePtr p;
return ERROR;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
Q.rear = Q.front; //只有一個元素時(不存在指向尾指針)
free (p);
return OK;
}
Status QueueTraverse(LinkQueue Q)
{
QueuePtr p,q;
{
printf(“這是一個空隊列!n”);
return ERROR;
}
p=Q.front->next;
{
q=p;
printf(“%ddata);
q=p->next;
p=q;
}
return OK;
}
循環(huán)隊列：
Status InitQueue(SqQueue &Q)
{
Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
exit(OWERFLOW);
Q.front=Q.rear=0;
return OK;
}
Status EnQueue(SqQueue &Q,QElemType e)
{
if((Q.rear+1)%MAXQSIZE==Q.front)
return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQSIZE;
return OK;
}
Status DeQueue(SqQueue &Q,QElemType &e)
return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return OK;
}
{
return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
Status DestoryQueue(SqQueue &Q)
{
free(Q.base);
return OK;
}
Status QueueEmpty(SqQueue Q) //判空
return OK;
return ERROR;
}
printf(“這是一個空隊列!”);
Q.front++;
}
return OK;
}
數(shù)據(jù)結(jié)構(gòu)報告【篇7】
1、進一步掌握指針變量的含義及應用。
2、掌握二叉樹的結(jié)構(gòu)特征，以及各種存儲結(jié)構(gòu)的`特點及使用范圍。
3、掌握用指針類型描述、訪問和處理二叉樹的運算。
題目1:編寫一個程序，采用一棵二叉樹表示一個家譜關(guān)系。要求程序具有如下功能：
（1）用括號表示法輸出家譜二叉樹，
（2）查找某人的所有兒子，
為了能夠用二叉樹表示配偶、子女、兄弟三種關(guān)系，特采用以下存儲關(guān)系，則能在二叉樹上實現(xiàn)家譜的各項運算。
二叉樹型存儲結(jié)構(gòu)定義為：
struct SNODE *right; //指向兄弟或子女結(jié)點
實驗由主函數(shù)、家譜建立函數(shù)、家譜輸出函數(shù)、兒子查找函數(shù)、祖先查找函數(shù)、結(jié)點定位函數(shù)、選擇界面函數(shù)七個函數(shù)共同組成。其功能描述如下：
void InitialFamily(FNODE *&head) //家譜建立函數(shù)
輸出形式為：父和母（子1和子妻1（孫1），子2和子妻2（孫2））
void PrintFamily(FNODE *head) //家譜輸出函數(shù)
（4）兒子查找函數(shù)：在家譜中查找到某人所有的子女并輸出，同時也能辨別出其是否為家族成員與是否有子女
void FindSon(FNODE *b,char p[]) //兒子查找函數(shù)
（5）祖先查找函數(shù)：在家譜中查找到某人所有的祖先并輸出，同時也能辨別出其是否為家族中成員。
int FindAncestor(FNODE *head,char son[ ]) //祖先查找函數(shù)
FNODE *findnode(FNODE *b,char p[]) //結(jié)點定位函數(shù)
（7）選擇界面函數(shù)：為便于編寫程序，將用戶選擇部分獨立為此函數(shù)。
（三）各函數(shù)的詳細設計：
void InitialFamily(FNODE *&head) //家譜建立函數(shù)
1：首先建立當前人的信息，將其左右結(jié)點置為空，
2：然后讓用戶確定其是否有配偶，如果沒有配偶，則當前程序結(jié)束，
3：如果有則建立其配偶信息，并將配偶結(jié)點賦給當前人的左結(jié)點；
4：再讓用戶確定其是否有子女，如果有則遞歸調(diào)用家譜建立函數(shù)建立子女結(jié)點，并將其賦給配偶結(jié)點的下一個右結(jié)點。
void PrintFamily(FNODE *head) //家譜輸出函數(shù)
1：首先判斷當前結(jié)點是否為空，如果為空則結(jié)束程序；
3：然后判斷其左結(jié)點（配偶結(jié)點）是否為空，如不為空則輸出“和配偶信息。
4：再判斷配偶結(jié)點的右結(jié)點是否為空，如不為空則遞歸調(diào)用輸出其子女信息，最后輸出“）”；
FNODE *findnode(FNODE *b,char p[]) //結(jié)點定位函數(shù)
void FindSon(FNODE *b,char p[]) //兒子查找函數(shù)
1：在家譜中定位到要查找的結(jié)點，如無則輸出“查找不到此人”
2：判斷其配偶結(jié)點與子女結(jié)點是否為空，為空則輸出“無子女”
3：不為空則輸出其配偶結(jié)點的所有右結(jié)點（子女結(jié)點）。
int FindAncestor(FNODE *head,char son[ ]) //祖先查找函數(shù)
1：先在家譜中定位到要查找的結(jié)點，如為空輸出“不存在此人”，程序結(jié)束
4：訪問過，再判斷是否為查找結(jié)點，如是則輸出棧中保存的其祖先結(jié)點，并濾過其兄弟結(jié)點不輸出；不是查找結(jié)點，則退棧一個元素
5：未訪問過，則取當前棧頂元素，置訪問標志——1，同時取其右結(jié)點
數(shù)據(jù)結(jié)構(gòu)報告【篇8】
1.下列程序段的時間復雜度為( )。
(A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n)
2.設順序線性表中有n個數(shù)據(jù)元素，則刪除表中第i個元素需要移動( )個元素。
(A) n-i (B) n+l -i (C) n-1-i (D) i
3.設F是由T1、T2和T3三棵樹組成的森林，與F對應的二叉樹為B，T1、T2和T3的結(jié)點數(shù)分別為N1、N2和N3，則二叉樹B的根結(jié)點的左子樹的結(jié)點數(shù)為( )。
(A) N1-1 (B) N2-1 (C) N2+N3 (D) N1+N3
4.利用直接插入排序法的思想建立一個有序線性表的時間復雜度為( )。
(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n)
5.設指針變量p指向雙向鏈表中結(jié)點A，指針變量s指向插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X的操作序列為( )。
(A) p->right=s; s->left=p; p->right->left=s; s->right=p->right;
(B) s->left=p;s->right=p->right;p->right=s; p->right->left=s;
(C) p->right=s; p->right->left=s; s->left=p; s->right=p->right;
(D) s->left=p;s->right=p->right;p->right->left=s; p->right=s;
6.下列各種排序算法中平均時間復雜度為O(n2)是( )。
(A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 冒泡排序
7.設輸入序列1、2、3、…、n經(jīng)過棧作用后，輸出序列中的第一個元素是n，則輸出序列中的第i個輸出元素是( )。
(A) n-i (B) n-1-i (C) n+l -i (D) 不能確定
8.設散列表中有m個存儲單元，散列函數(shù)H(key)= key % p，則p最好選擇( )。
9.設在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點數(shù)有2個，度數(shù)為2的結(jié)點數(shù)有1個，度數(shù)為1的結(jié)點數(shù)有2個，那么度數(shù)為0的結(jié)點數(shù)有( )個。
10.設完全無向圖中有n個頂點，則該完全無向圖中有( )條邊。
(A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2
11.設順序表的長度為n，則順序查找的平均比較次數(shù)為( )。
(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2
12.設有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過( )次比較。
13.設順序線性表的長度為30，分成5塊，每塊6個元素，如果采用分塊查找，則其平均查找長度為( )。
14.設有向無環(huán)圖G中的有向邊集合E={，，，}，則下列屬于該有向圖G的一種拓撲排序序列的是( )。
(A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3
15.設有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹的深度為( )。
1.設指針p指向單鏈表中結(jié)點A，指針s指向插入的結(jié)點X，則在結(jié)點A的前面插入結(jié)點X時的操作序列為：
1) s->next=___________;2) p->next=s;3) t=p->data;
4) p->data=___________;5) s->data=t;
2.設某棵完全二叉樹中有100個結(jié)點，則該二叉樹中有______________個葉子結(jié)點。
3.設某順序循環(huán)隊列中有m個元素，且規(guī)定隊頭指針F指向隊頭元素的前一個位置，隊尾指針R指向隊尾元素的當前位置，則該循環(huán)隊列中最多存儲_______隊列元素。
4.對一組初始關(guān)鍵字序列(40，50，95，20，15，70，60，45，10)進行冒泡排序，則第一趟需要進行相鄰記錄的比較的次數(shù)為__________，在整個排序過程中最多需要進行__________趟排序才可以完成。
5.在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應最好選擇_________排序，如果從節(jié)省存儲空間的.角度來考慮則最好選擇________排序。
6.設一組初始記錄關(guān)鍵字序列為(20，12，42，31，18，14，28)，則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長度是_______________________________。
7.設一棵二叉樹的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹的前序序列為____________________。
8.設用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、6、32、3、21、10，根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹，則這棵哈夫曼樹的高度為________________。
9.設一組記錄關(guān)鍵字序列為(80，70，33，65，24，56，48)，則用篩選法建成的初始堆為_______________________。
10. 10. 設無向圖G(如右圖所示)，則其最小生成樹上所有邊的權(quán)值之和為_________________。
3.子串“ABC”在主串“AABCABCD”中的位置為2。( )
4.若一個葉子結(jié)點是某二叉樹的中序遍歷序列的最后一個結(jié)點，則它必是該二叉樹的先序遍歷序列中的最后一個結(jié)點。( )
6.用鄰接矩陣作為圖的存儲結(jié)構(gòu)時，則其所占用的存儲空間與圖中頂點數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。( )
8.入棧操作和入隊列操作在鏈式存儲結(jié)構(gòu)上實現(xiàn)時不需要考慮棧溢出的情況。( )
1.設計計算二叉樹中所有結(jié)點值之和的算法。
2.設計將所有奇數(shù)移到所有偶數(shù)之前的算法。
3.設計判斷單鏈表中元素是否是遞增的算法。
數(shù)據(jù)結(jié)構(gòu)報告【篇9】
1.判斷鏈表是否存在環(huán)型鏈表問題：判斷一個鏈表是否存在環(huán)，例如下面這個鏈表就存在一個環(huán)：
例如N1->N2->N3->N4->N5->N2就是一個有環(huán)的鏈表，環(huán)的開始結(jié)點是N5這里有一個比較簡單的解法，設置兩個指針p1，p2。每次循環(huán)p1向前走一步，p2向前走兩步。直到p2碰到NULL指針或者兩個指針相等結(jié)束循環(huán)。如果兩個指針相等則說明存在環(huán)。
{
int data;
link* next;
};
{
link* p1=head, *p2 = head;
if (head ==NULL || head->next ==NULL)
{
return false;
}
do{
p1= p1->next;
p2 = p2->next->next;
} while(p2 && p2->next && p1!=p2);
return false;
}
2,鏈表反轉(zhuǎn) 單向鏈表的反轉(zhuǎn)是一個經(jīng)常被問到的一個面試題，也是一個非?；A的問題。比如一個鏈表是這樣的： 1->2->3->4->5 通過反轉(zhuǎn)后成為5->4->3->2->1。最容易想到的方法遍歷一遍鏈表，利用一個輔助指針，存儲遍歷過程中當前指針指向的下一個元素，然后將當前節(jié)點元素的指針反轉(zhuǎn)后，利用已經(jīng)存儲的指針往后面繼續(xù)遍歷。源代碼如下：
struct linka {
int data;
linka* next;
};
return;
linka*pre, *cur, *ne;
pre=head;
cur=head->next;
{
ne = cur->next;
cur->next = pre;
pre = cur;
cur = ne;
}
head->next = NULL;
head = pre;
}
還有一種利用遞歸的方法。這種方法的基本思想是在反轉(zhuǎn)當前節(jié)點之前先調(diào)用遞歸函數(shù)反轉(zhuǎn)后續(xù)節(jié)點。源代碼如下。不過這個方法有一個缺點，就是在反轉(zhuǎn)后的最后一個結(jié)點會形成一個環(huán)，所以必須將函數(shù)的返回的節(jié)點的next域置為NULL。因為要改變head指針，所以我用了引用。算法的源代碼如下：
linka* reverse(linka* p,linka*& head)
{
if(p == NULL || p->next == NULL)
{
head=p;
{
linka* tmp = reverse(p->next,head);
tmp->next = p;
return p;
}
}
3,判斷兩個數(shù)組中是否存在相同的數(shù)字 給定兩個排好序的數(shù)組，怎樣高效得判斷這兩個數(shù)組中存在相同的數(shù)字？
這個問題首先想到的是一個O(nlogn)的算法。就是任意挑選一個數(shù)組，遍歷這個數(shù)組的所有元素，遍歷過程中，在另一個數(shù)組中對第一個數(shù)組中的每個元素進行binary search。用C++實現(xiàn)代碼如下：
bool findcommon(int a[],int size1,int b[],int size2)
{
int i;
for(i=0;i
{
int start=0,end=size2-1,mid;
{
mid=(start+end)/2;
return true;
else if (a[i]
start=mid+1;
}
}
return false;
}
后來發(fā)現(xiàn)有一個 O(n)算法，
因為兩個數(shù)組都是排好序的。所以只要一次遍歷就行了。首先設兩個下標，分別初始化為兩個數(shù)組的起始地址，依次向前推進。推進的規(guī)則是比較兩個數(shù)組中的數(shù)字，小的那個數(shù)組的下標向前推進一步，直到任何一個數(shù)組的下標到達數(shù)組末尾時，如果這時還沒碰到相同的數(shù)字，說明數(shù)組中沒有相同的數(shù)字。
bool findcommon2(int a[], int size1, int b[], int size2)
{
int i=0,j=0;
while(ireturn true;j++;if(a[i]i++;}return false;}4,最大子序列 問題：給定一整數(shù)序列A1， A2，... An （可能有負數(shù)），求A1~An的一個子序列Ai~Aj，使得Ai到Aj的和最大例如：整數(shù)序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和為21。對于這個問題，最簡單也是最容易想到的那就是窮舉所有子序列的方法。利用三重循環(huán)，依次求出所有子序列的和然后取最大的那個。當然算法復雜度會達到O(n^3)。顯然這種方法不是最優(yōu)的，下面給出一個算法復雜度為O(n)的線性算法實現(xiàn)，算法的來源于Programming Pearls一書。 在給出線性算法之前，先來看一個對窮舉算法進行優(yōu)化的算法，它的算法復雜度為O(n^2)。其實這個算法只是對對窮舉算法稍微做了一些修改：其實子序列的和我們并不需要每次都重新計算一遍。假設Sum(i, j)是A[i] ... A[j]的和，那么Sum(i, j+1) = Sum(i, j) + A[j+1]。利用這一個遞推，我們就可以得到下面這個算法：{int i,j,v,max=a[0];for(i=0;i{v=0;for(j=i;j{v=v+a[j];//Sum(i, j+1) = Sum(i, j) + A[j+1]max=v;}}return max;}那怎樣才能達到線性復雜度呢？這里運用動態(tài)規(guī)劃的思想。先看一下源代碼實現(xiàn)：{int i,max=0,temp_sum=0;for(i=0;i{temp_sum+=a[i];max=temp_sum;temp_sum=0;}return max;}在這一遍掃描數(shù)組當中，從左到右記錄當前子序列的和temp_sum，若這個和不斷增加，那么最大子序列的和max也不斷增加(不斷更新max)。如果往前掃描中遇到負數(shù)，那么當前子序列的和將會減小。此時temp_sum 將會小于max，當然max也就不更新。如果temp_sum降到0時，說明前面已經(jīng)掃描的那一段就可以拋棄了，這時將temp_sum置為0。然后，temp_sum將從后面開始將這個子段進行分析，若有比當前max大的子段，繼續(xù)更新max。這樣一趟掃描結(jié)果也就出來了。5, 找出單向鏈表的中間結(jié)點 這道題和解判斷鏈表是否存在環(huán)，我用的是非常類似的方法，只不過結(jié)束循環(huán)的條件和函數(shù)返回值不一樣罷了。設置兩個指針p1，p2。每次循環(huán)p1向前走一步，p2向前走兩步。當p2到達鏈表的末尾時，p1指向的時鏈表的中間。{link* p1,*p2;p1=p2=head;if(head==NULL || head->next==NULL)return head;do {p1=p1->next;p2=p2->next->next;} while(p2 && p2->next);return p1;}來自：akalius.blog/163319
數(shù)據(jù)結(jié)構(gòu)報告【篇10】
實驗報告;課程名稱：數(shù)據(jù)結(jié)構(gòu)班級：軟件工程實驗成績：;1206;實驗名稱：打印機隊列模擬學號：4848批;程序的設計;實驗編號：實驗一姓名：實驗日期：5月2;一、實驗目的;對隊列的理解;對STL中的queue的使用;實驗仿真一個網(wǎng)絡打印過程;二、實驗內(nèi)容與實驗步驟流程圖;這個任務隊列的測試使用STL隊列適配器;具體地說,每一行中包含的信息是
這個任務隊列的測試使用STL隊列適配器。程序要求完成模擬的實現(xiàn)共享打印機。這個打印機使用先進先出隊列。仿真是通過讀取和處理事件數(shù)據(jù)文件的列表。一個有效的數(shù)據(jù)文件中的每一行包含信息打印作業(yè)和提交這份工作的時間。
具體地說,每一行中包含的信息是提交工作的時間(以秒為單位),和在頁面的工作長及工作的計算機的名稱。在模擬的開始,每個這些事件的每一個應該被程序所讀，存儲在繼承工作負載隊列。程序應該通過循環(huán)遞增計數(shù)器或while-loop模擬時間的流逝。程序應該將計數(shù)器初始化為零,然后依次增加1秒。當模擬等于當前時間的打印作業(yè)的提交時間在工作隊列的前面，一個打印作業(yè)完成。當這一切發(fā)生的時候,從工作隊列取出這個事件,然后把它放在另一個隊列對象。這個隊列對象存儲已完成的打印作業(yè)。當程序仿真其他的打印工作的時候，這些工作在隊列等待。
#include “simulator.h”
protected:
queue waiting;
priority_queue priority_waiting;
public:
fifo(int seconds_per_page);
void simulate(string file);
};
bool operator
using namespace std;
fifo::fifo(int seconds_per_page):simulator(seconds_per_page){ }
void fifo::simulate(string file){
int finish_time = 0;
float agg_latency = 0;
int totaljob =0;
event evt;
if(file.find(“arbitrary”)!= string::npos){
string outfile =“arbitrary.out”;
ofstream osf(outfile.c_str());
loadworkload(file);
osf
for(int time =1;!waiting.empty()||!workload.empty();time++){ while(!workload.empty() && time ==
workload.front().arrival_time()){
evt= workload.front();
osf
workload.pop();
}
if(!waiting.empty() && time >= finish_time){
totaljob ++;
evt = waiting.front();
agg_latency += time - evt.arrival_time();
osf
finish_time = time + evt.getjob().getnumpages() * seconds_per_page;
}
}
osf
osf
osf
return;
}
if(file.find(“bigfirst”) != string::npos){
string outfile = “bigfirst.out”;
ofstream osf(outfile.c_str());
loadworkload(file);
=1;!priority_waiting.empty()||!workload.empty();time++){
while(!workload.empty() && time ==
workload.front().arrival_time()){
evt= workload.front();
osf
workload.pop();
}
if(!priority_waiting.empty() && time >= finish_time){
totaljob ++;
evt = priority_();
agg_latency += time - evt.arrival_time();
osf
finish_time = time + evt.getjob().getnumpages() * seconds_per_page; }
}
osf
osf
osf
return;
}
cerr
cerr
bool operator
return evtleft.getjob().getnumpages()
evtright.getjob().getnumpages();
經(jīng)測試，功能較為完整。代碼流程簡圖如下：
通過這次實驗，我了解了有關(guān)隊列方面的知識。掌握了隊列的邏輯結(jié)構(gòu)，抽象數(shù)據(jù)類型，隊列的存儲方式等。運用先進先出表，仿真了網(wǎng)絡打印隊列。這都使我對數(shù)據(jù)結(jié)構(gòu)的學習有了新的認識與幫助。在實驗過程中，我也遇到了許多困難，從開始時對隊列運算的不熟悉，到逐漸查找資料，從而完成了實驗;六、附錄;-《數(shù)據(jù)結(jié)構(gòu)與算法分析》以及網(wǎng)上資料;
逐漸查找資料，從而完成了實驗。在今后的學習中，我將繼續(xù)努力，加強對堆棧，隊列等知識的學習，以達到精益求精。