數據結構的課程設計
『壹』 數據結構c語言版的 課程設計
一、問題描述：
利用哈夫曼編碼進行信息通信可以大大提高信道利用率，縮簡訊息傳輸時間，降低傳輸成本。但是，這要求在發送端通過一個編碼系統對待傳數據預先編碼，在接收端將傳來的數據進行解碼（復原）。對於雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編／解碼系統。試為這樣的信息收發站寫一個哈夫曼碼的編／解碼系統。
二、基本要求：
1、I：初始化（Initialization），從終端讀入字元集大小n，以及n個字元和n個權值，建立哈夫曼樹，並將它存於文件hfmTree中。
2、E：編碼（Encoding），利用已建好的哈夫曼樹（如不在內存，則從文件hfmTree中讀人），對文件ToBeTran中的正文進行編碼，然後將結果存入文件CodeFile中。
3、D：解碼（Decoding），利用已建好的哈夫曼樹將文件CodeFile中的代碼進行解碼，結果存入文件TextFile中。
4、P：輸出代碼文件（Print），將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字元形式的編碼文件寫入文件CodePrin中。
5、T：輸出哈夫曼樹（TreePrinting），將已在內存中的哈夫曼樹以直觀的方式（樹或凹人表形式）顯示在終端上，同時將此字元形式的哈夫曼樹寫入文件TreePrint中。
三、測試數據：]
用下表給出的字元集和頻度的實際統計數據建立哈夫曼樹，並實現以下報文的編碼和解碼：「THIS PROGRAM IS MY FAVORITE」。
字元 A B C D E F G H I J K L M
頻度 186 64 13 22 32 103 21 15 47 1 5 32 20 20
字元 N O P Q R S T U V W X Y Z
頻度 57 63 15 1 48 51 80 23 8 18 1 16 1
四、實現提示：
1、哈夫曼編碼採用一個字元串數組存儲。
2、用戶界面可以設計為「菜單」方式：顯示上述功能符號，再加上「Q」，表示退出運行Quit。請用戶鍵入一個選擇功能符。此功能執行完畢後再顯示此菜單，直至某次用戶選擇了「Q」為止。
3、在程序的一次執行過程中，第一次執行I、D或C命令之後，哈夫曼樹已經在內存了，不必再讀入。每次執行中不一定執行I命令，因為文件hfmTree可能早已建好。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
int n;
struct node{
int w;
int flag;
char c;
struct node *plink,*llink,*rlink;
char code[50];
}*num[100],*root;
FILE *fp;
char tmpcode[50];
int t=0;
void main(void)
{
int i;
void settree(void); //建立樹
void code(void); //對文件編碼
void decode(void); // 解碼
void disp(void);
root=(struct node*)malloc(sizeof(struct node));
puts("*******************哈夫曼編/解碼器演示******************************");
while(1){
start:
puts("1. 初始化 2. 編碼 3. 解碼 4.顯示編碼表 5. 退出");
while(scanf("%d",&i)!=1)
{
while(getchar()!='\n')
continue;
puts("輸入錯誤!");
puts("請重新輸入！");
puts("1. 初始化 2. 編碼 3. 解碼 4.顯示編碼表 5. 退出");
}
switch (i)
{
case 1:
settree();
break;
case 2:
code();
break;
case 3:
decode();
break;
case 4:
disp();
break;
case 5:
exit(0);
default:
puts("輸入錯誤！");
puts("請重新輸入！");
goto start;
}
}
}
void settree(void)
{
int i,j,k;
struct node *p1,*p2,*tmp,*p;
void go(struct node *);
void setcode(struct node *);//建立每一個字元的編碼
void printtree(struct node *);
puts("輸入字元集的大小：");
scanf("%d",&n);
while(getchar()!='\n')
continue;
for(i=0;i<n;i++)
{
p=(struct node *)malloc(sizeof(struct node));
puts("請輸入一個字元");
scanf("%c",&p->c);
while(getchar()!='\n')
continue;
puts("請輸入該字元的權值:");
scanf("%d",&p->w);
while(getchar()!='\n')
continue;
p->plink=NULL;
p->rlink=NULL;
p->llink=NULL;
num[i]=p;
}
for(i=0;i<n-1;i++) //（遞增）排序
{
for(j=i+1;j<n;j++)
{
if(num[i]->w>num[j]->w)
{
tmp=num[i];
num[i]=num[j];
num[j]=tmp;
}
}
}
/*******************************開始建立樹***********************/
num[n]=NULL; //結束標志
k=n;
while(num[1]!=NULL)
{
p=(struct node *)malloc(sizeof(struct node));
p1=num[0];
p2=num[1];
p->llink=p1;
p->rlink=p2;
p->plink=NULL;
p1->plink=p;
p2->plink=p;
p->w=p1->w+p2->w;
for(i=1;i<k;i++)
{
num[i]=num[i+1];
}
k--;
num[0]=p;
for(i=0;i<k-1;i++) //排序
{
for(j=i+1;j<k;j++)
{
if(num[i]->w>num[j]->w)
{
tmp=num[i];
num[i]=num[j];
num[j]=tmp;
}
}
}
}
root=num[0];
/*建立完畢*/
/*寫入文件，前序*/
if((fp=fopen("c:\\hfmtree.wxl","wb"))==NULL)
{
puts("文件打開錯誤！");
getchar();
exit(0);
}
setcode(root);
go(root);
fclose(fp);
}
void setcode(struct node *p)
{
if(p->llink==NULL&&p->rlink==NULL)
{
tmpcode[t]='\0';
strcpy(p->code,tmpcode);
}
else
{
tmpcode[t++]='0';
setcode(p->llink);
t--;
tmpcode[t++]='1';
setcode(p->rlink);
t--;
}
}
void go(struct node *p)
{
if(p->llink==NULL&&p->rlink==NULL)
{
fputc('(',fp);
fputc(p->c,fp);
fputs(p->code,fp);
fputc(')',fp);
}
else
{
go(p->llink);
go(p->rlink);
}
}
void code(void)
{
FILE *fp1,*fp2,*fp3;
char ch1,ch2,c;
if((fp1=fopen("c:\\hfmtree.wxl","rb"))==NULL)
{
puts("文件打開錯誤！");
getchar();
exit(0);
}
if((fp2=fopen("c:\\tobetrans.txt","wb"))==NULL)
{
puts("文件打開錯誤！");
getchar();
exit(0);
}
if((fp3=fopen("c:\\codefile.wxl","wb"))==NULL)
{
puts("文件打開錯誤！");
getchar();
exit(0);
}
while((ch1=fgetc(fp2))!=EOF)
{
t=0;
while((ch2=fgetc(fp1))!=EOF)
{
if(ch1==ch2)
{
while((c=fgetc(fp1))!=')')
{
tmpcode[t++]=c;
}
tmpcode[t]='\0';
fputs(tmpcode,fp3);
fputc('@',fp3);
rewind(fp1);
break;
}
}
}
fclose(fp1);
fclose(fp2);
fclose(fp3);
}
void decode(void)
{
FILE *fp1,*fp2,*fp3;
char ch1,ch2,ch3;
char temp_3[20];
char temp_1[20];
int t1,t3;
if((fp1=fopen("c:\\hfmtree.wxl","rb"))==NULL)
{
puts("文件打開錯誤！");
getchar();
exit(0);
}
if((fp2=fopen("c:\\textfile.txt","wb"))==NULL)
{
puts("文件打開錯誤！");
getchar();
exit(0);
}
if((fp3=fopen("c:\\codefile.wxl","rb"))==NULL)
{
puts("文件打開錯誤！");
getchar();
exit(0);
}
while((ch3=fgetc(fp3))!=EOF)
{
t3=0;
while(ch3!='@')
{
temp_3[t3++]=ch3;
ch3=fgetc(fp3);
}
temp_3[t3]='\0';
while((ch1=fgetc(fp1))!=EOF)
{
if(isalpha(ch1))
{
ch2=ch1;
t1=0;
while((ch1=fgetc(fp1))!=')')
{
temp_1[t1++]=ch1;
}
temp_1[t1]='\0';
if(strcmp(temp_1,temp_3)==0)
{
fputc(ch2,fp2);
rewind(fp1);
break;
}
}
}
}
fclose(fp1);
fclose(fp2);
fclose(fp3);
}
void disp(void)
{
FILE *fp1,*fp2;
char ch1,ch2;
char tmp[20];
int t;
if((fp1=fopen("c:\\hfmtree.wxl","rb"))==NULL)
{
puts("文件打開錯誤！");
getchar();
exit(0);
}
if((fp2=fopen("c:\\hfmcode.txt","wb"))==NULL)
{
puts("文件打開錯誤！");
getchar();
exit(0);
}
while((ch1=fgetc(fp1))!=EOF)
{
if(ch1=='(')
{
t=0;
ch1=fgetc(fp1);
ch2=ch1;
while((ch1=fgetc(fp1))!=')')
{
tmp[t++]=ch1;
}
tmp[t]='\0';
printf("%c-----%s\n",ch2,tmp);
fputc(ch2,fp2);
fputc('-',fp2);
fputc('-',fp2);
fputc('-',fp2);
fputs(tmp,fp2);
fputc('\n',fp2);
}
}
fclose(fp1);
fclose(fp2);
}
『貳』 數據結構課程設計是什麼
.需求分析
1.運行環境
硬體：計算機486/64M以上
操作系統： WIN9x 以上/WIN2000/WIN XP/WIN ME
相關軟體：vistualC++
2．程序所實現的功能：
（1）建立並顯示圖的鄰接表。
（2）深度優先遍歷，顯示遍歷結果。
（3）對該圖進行拓撲排序，顯示排序結果。
（4）給出某一確定頂點到所有其它頂點的最短路徑。
3.程序的輸入，包含輸入的數據格式和說明
(1)輸入頂點數,及各頂點信息(數據格式為整形)
(2)輸入邊數,及權值(數據格式為整形)
4.程序的輸出，程序輸出的形式
(1)輸出圖的鄰接表、深度優先遍歷結果、拓撲排序結果。
(2)輸入某一確定頂點到其它所有頂點的最短路徑。
5.測試數據
二、設計說明
1、 演算法設計的思想
建立圖類，建立相關成員函數。最後在主函數中實現。具體成員函數的實現請參看源程序。
2、 主要的數據結構設計說明
圖鄰接矩陣、鄰接表的建立。圖的深度優先遍歷、拓撲排序、頂點之間的最短路徑。
3、 程序的主要模板template <class Type> class Graph
4、 程序的主要函數
Graph、link()、DFTraverse()、TopologicalOrder()、
TopologicalOrder()、GetVertexPos()、ShortestPath
三、上機結果及體會
1、 實際完成的情況說明
主要程序參考教材《數據結構——C++版》。
2、 程序的性能分析
可連續建圖
3、 上機過程中出現的問題及其解決方案。
編譯沒有錯誤，但結果有問題。解決方案：雖然程序的編譯通過，只能說明語法上沒有問題，結果只所以不正確是因為演算法上原因。
4、 程序中可以改進的地方說明
程序中的深度優先遍歷，浪費空間較大，可以考慮用循環來做。但這樣將付出代碼長度度加長的代價。
5、 程序中可以擴充的功能及設計實現假想
實現假想：隨用戶的輸入可以隨時動態的顯示圖的生成。
6、 收獲及體會
編寫程序即是一件艱苦的工作，又是一件愉快的事情。最大的收獲：編程時如果遇到看似簡單但又無法解決的問題，很容易灰心喪氣。此時切不可煩躁，一定要冷靜的思考，認真的分析。要勇敢的面對問題，勇敢的接受問題，勇敢的處理問題，最後最勇敢的解決問題。
四、參考文獻
數據結構（C++版） 葉核亞 主編 機械工業出版社
數據結構經典演算法實現與習題解答 汪傑 編著 人民郵電出版社
數據結構課程設計 蘇仕華 編著 機械工業出版社
數據結構程序設計題典 李春葆 編著 清華大學出版社
數據結構課程與題解（用C/C++描述） 胡聖榮 編著 北京大學出版社
[程序運行流程圖]
char op //程序控制變數
『叄』 數據結構線性表課程設計
#include "stdio.h"
#include "stdlib.h"
#define NULL 0
typedef struct node{
char data;
struct node *next;
}linklist;
main(){
void create(linklist *L);
void list(linklist *L);
int find(linklist *L,char ch);
int delete1(linklist *L,char x);
void del(linklist *L);
linklist *L;
char ch,x;
int s,n;
L=(linklist *)malloc(sizeof(linklist));
L->next=NULL;
printf("Create a linklist:\n");
create(L);
getchar();
printf("List the linklist:");
list(L);
printf("\n Input ch=");
scanf("%c",&ch);
getchar();
n=find(L,ch);
printf("\n n= %d",n);
printf("\n Input x= ");
scanf("%c",&x);
getchar();
s=delete1(L,x);
printf("\n S=%d",s);
printf("\n List the new linklist:");
list(L);
printf("\n Delete list:");
del(L);
getch();
}
void create(linklist *L){
char ch;
linklist *r,*s;
r=L;
printf("Typr '@' to end\n");
printf("Input the value of node:");
ch=getchar();
while(ch!='@'){
=(linklist *)malloc(sizeof(linklist));
s->data=ch;
r->next=s;
r=s;
ch=getchar();
}
r->next=NULL;
}
void list(linklist *L){
int i=1;
linklist *p;
p=L->next;
if(!p){
printf("\n Empty list !");
return;
}
do{
printf("\n Node number %d,value %c",i++,p->data);
p=p->next;
}while(p);
}
int find(linklist *L,char ch){
linklist *p=L->next;
int s=0;
while(p){
if(p->data==ch)s=s+1;
p=p->next;
}
return(s);
}
int delete1(linklist *L,char x){
int s=0;
linklist *p,*q;
p=L;q=L->next;
while(q){
if(q->data==x){
p->next=q->next;
free(q);
q=p->next;
s++;
}
else{
p=q;
q=q->next;
}
}
return(s);
}
void del(linklist *L){
linklist *p=L,*q;
while(p){
q=p->next;
free(p);
p=q;
}
}
『肆』 跪求數據結構課程設計（C語言版）代碼，感激不盡
在C語言中，結構體(struct)指的是一種數據結構，是C語言中聚合數據類型(aggregate data type)的一類。結構體可以被聲明為變數、指針或數組等，用以實現較復雜的數據結構。結構體同時也是一些元素的集合，這些元素稱為結構體的成員(member)，且這些成員可以為不同的類型，成員一般用名字訪問。[1]
定義與聲明
結構體的定義如下所示，struct為結構體關鍵字，tag為結構體的標志，member-list為結構體成員列表，其必須列出其所有成員；variable-list為此結構體聲明的變數。[1]
struct tag {
member-list
} variable-list ;
在一般情況下，tag、member-list、variable-list這3部分至少要出現2個。以下為示例：[1]
//此聲明聲明了擁有3個成員的結構體，分別為整型的a，字元型的b和雙精度的c
//同時又聲明了結構體變數s1
//這個結構體並沒有標明其標簽
struct {
int a;
char b;
double c;
} s1;
//同上聲明了擁有3個成員的結構體，分別為整型的a，字元型的b和雙精度的c
//結構體的標簽被命名為SIMPLE,沒有聲明變數
struct SIMPLE{
int a;
char b;
double c;
};
//用SIMPLE標簽的結構體，另外聲明了變數t1、t2、t3
struct SIMPLE t1, t2[20], *t3;
//也可以用typedef創建新類型
typedef struct{
int a;
char b;
double c;
} Simple2;
//現在可以用Simple2作為類型聲明新的結構體變數
Simple2 u1, u2[20], *u3;
在上面的聲明中，第一個和第二聲明被編譯器當作兩個完全不同的類型，即使他們的成員列表是一樣的，如果令t3=&s1，則是非法的。[1]
結構體的成員可以包含其他結構體，也可以包含指向自己結構體類型的指針，而通常這種指針的應用是為了實現一些更高級的數據結構如鏈表和樹等。[1]
//此結構體的聲明包含了其他的結構體
struct COMPLEX{
char string[100];
struct SIMPLE a;
};
//此結構體的聲明包含了指向自己類型的指針
struct NODE{
char string[100];
struct NODE *next_node;
};
如果兩個結構體互相包含，則需要對其中一個結構體進行不完整聲明，如下所示：[1]
struct B;
//對結構體B進行不完整聲明
//結構體A中包含指向結構體B的指針
struct A{
struct B *partner;
//other members;
};
//結構體B中包含指向結構體A的指針，在A聲明完後，B也隨之進行聲明
struct B{
struct A *partner;
//other members;};
結構體作用
結構體和其他類型基礎數據類型一樣，例如int類型，char類型 只不過結構體可以做成你想要的數據類型。以方便日後的使用。[1]
在實際項目中，結構體是大量存在的。研發人員常使用結構體來封裝一些屬性來組成新的類型。由於C語言內部程序比較簡單，研發人員通常使用結構體創造新的「屬性」，其目的是簡化運算。[1]
結構體在函數中的作用不是簡便，其最主要的作用就是封裝。封裝的好處就是可以再次利用。讓使用者不必關心這個是什麼，只要根據定義使用就可以了。[1]
結構體的大小與內存對齊
結構體的大小不是結構體元素單純相加就行的，因為我們主流的計算機使用的都是32bit字長的CPU，對這類型的CPU取4個位元組的數要比取一個位元組要高效，也更方便。所以在結構體中每個成員的首地址都是4的整數倍的話，取數據元素時就會相對更高效，這就是內存對齊的由來。每個特定平台上的編譯器都有自己的默認「對齊系數」(也叫對齊模數)。程序員可以通過預編譯命令#pragma pack(n)，n=1,2,4,8,16來改變這一系數，其中的n就是你要指定的「對齊系數」。[1]
規則：
1、數據成員對齊規則：結構(struct)(或聯合(union))的數據成員，第一個數據成員放在offset為0的地方，以後每個數據成員的對齊按照#pragma pack指定的數值和這個數據成員自身長度中，比較小的那個進行。[1]
2、結構(或聯合)的整體對齊規則：在數據成員完成各自對齊之後，結構(或聯合)本身也要進行對齊，對齊將按照#pragma pack指定的數值和結構(或聯合)最大數據成員長度中，比較小的那個進行。[1]
3、結合1、2可推斷：當#pragma pack的n值等於或超過所有數據成員長度的時候，這個n值的大小將不產生任何效果。
『伍』 數據結構課程設計
這個是程序：
#include "string.h"
#define NULL 0
unsigned int key;
unsigned int key2;
int *p;
struct node
{
char name[20],address[20];
char num[11];
struct node *next;
}
**phone;
**nam;
**address;
typedef struct node *pnode;
typedef struct node *mingzi;
void hash(char num[11])
{
int i = 3;
key=(int)num[2];
while(num[i]!=NULL)
{
key+=(int)num[i];
i++;
key=key%17;
}
void hash2(char name[8])
{
int i = 1;
key2=(int)name[0];
while(name[i]!=NULL)
{
key2+=(int)name[i];
i++;
}
Key2=key2%17;
}
struct node* input()
{
struct node *temp=(struct node*)malloc(sizeof(struct node));
temp = new node;
temp->next=NULL;
printf("qing shu ru xing ming(no more then 8 chars) :\n");
scanf("%s",&temp->name);
printf"qing shu ru dian hua hao ma(no more then 11 numbers):\n");
scanf("%s",&temp->num);
printf("qing shu ru di (no more then 20 chars):\n");
scanf("%s",&temp->address);
return temp;
}
int add()
{
struct node *newphone;
struct node *newname;
newphone=input();
printf("ni de ji lu shi");
if(find(newphone->num))
{
printf("hao ma yi jing cun zai bu nene zai tian jia.\n");
return 0;
}
if(find2(newphone->name))
{
printf("xing ming yi jing cun zai bu neng zai tian jia.\n");
return 0;
}
printf("%s_%s_%s\n",newphone->name,newphone->address,newphone->num);
newname=newphone;
newphone->next=NULL;
newname->next=NULL;
hash(newphone->num);
hash2(newname->name);
newphone->next = phone[key]->next;
phone[key]->next=newphone;
newname->next = nam[key2]->next;
nam[key2]->next=newname;
return 0;
}
int find(char num[11])
{
int isfind=0;
struct node *q;
hash(num);
node *q=phone[key]->next;
while(q!= NULL)
{
if(strcmp(num,q->num) ==0)
{
isfind=1;
break;
}
q=q->next;
}
if(isfind)
printf("%s_%s_%s\n",q->name,q->address,q->num);
return isfind;
}
int find2(char name[8])
{
int isfind=0;
hash2(name);
struct node *q=nam[key2]->next;
while(q!= NULL)
{
if(strcmp(name,q->name)==0)
{
isfind=1;
break;
}
q=q->next;
}
if(isfind)
printf("%s_%s_%s\n",q->name,q->address,q->num);
return isfind;
}
void create()
{
int i;
phone = (pnode*)malloc(13*sizeof(pnode));
for(i=0;i<13;i++)
{
phone[i]=(struct node*)malloc(sizeof(struct node));
phone[i]->next=NULL;
}
}
void create2()
{
int i;
nam = (mingzi*)malloc(13*sizeof(mingzi));
for(i=0;i<13;i++)
{
nam[i]=(struct node*)malloc(sizeof(struct node));
nam[i]->next=NULL;
}
}
void list()
{
int i;
struct node *p;
for(i=0;i<13;i++)
{
p=phone[i]->next;
while(p)
{
printf("%s_%s_%s\n",p->name,p->address,p->num);
p=p->next;
}
}
}
void list2()
{
int i;
struct node *p;
for(i=0;i<13;i++)
{
p=nam[i]->next;
while(p!=NULL)
{
printf("%s_%s_%s\n",p->name,p->address,p->num);
p=p->next;
}
}
}
void menu()
{
printf("0.tian jia ji lv.\n");
printf("2.cha zhao ji lu.\n");
printf("3.xing ming lie biao.\n");
printf("4.hao ma lie biao.\n");
printf("5.qing chu suo you ji lu.\n");
printf("6.tui chu xi tong.\n");
}
int main()
{
char num[11];
char name[8];
int sel;
create();
create2();
while(1)
{
menu();
scanf("%d",&sel);
if(sel==3)
{
char b;
printf("Input 9 to search with number,8 to name.\n");
b=getch();
if(b=='9')
{
printf("Please input the number:\n");
scanf("%s",&num);
if(!find(num))
printf("Record not exist.\n");
}
else if(b=='8')
{
printf("Please input the name:\n");
scanf("%s",&name);
if(!find(name))
printf("Record not exist.\n");
}
else
{
printf("Wrong input!Please input again!\n");
continue;
}
}
else if(sel==2)
{
printf("All record with name:\n");
list2();
}
else if(sel==0)
{
printf("Please input the information:\n");
add();
}
else if(sel==4)
{
printf("All record with number:\n");
list();
}
else if(sel==5)
{
create();
create2();
printf("All records have been removed.\n");
}
else if(sel==6)
{printf("7");
break;
}
}
return 0;
}
『陸』 數據結構課程設計的需求分析怎麼寫
一 需求分析：
在該部分中根據設計題目的要求，充分地分析和理解問題，敘述系統的功能要求，明確問題要求做什麼？以及限制條件是什麼？
1．1問題描述
1．2基本要求
(1) 輸入的形式和輸入值的范圍；
(2) 輸出的形式；
(3) 程序所能達到的功能；
二 概要設計
說明本程序中用到的所有抽象數據類型的定義。主程序的流程以及各程序模塊之間的層次(調用)關系。
1、 數據結構
2、 程序模塊
3、各模塊之間的調用關系以及演算法設計
三 詳細設計
實現概要設計中定義的所有數據類型,對每個操作寫出偽碼演算法;對主程序和其他模塊也都需要寫出偽碼演算法(偽碼演算法達到的詳細程度建議為:按照偽碼演算法可以在計算機鍵盤直接輸入高級程序設計語言程序);寫出出函數和過程的調用關系.
四 測試與分析
測試數據，輸出測試的結果，這里的測試數據應該完整和嚴格。並對結果進行分析。
五 總結
總結可以包括 : 課程設計過程的收獲、遇到問題、遇到問題解決問題過程的思考、程序調試能力的思考、對數據結構這門課程的思考、在課程設計過程中對《數據結構》課程的認識等內容。
『柒』 數據結構課程設計：順序表
#include <iostream>
using namespace std;
#define TURE 1
#define FALSE 0
#define _INIT_SIZE 100
#define INCREMENT 10
class sqlist
{
private:
char * base; //指向順序表的基址
int length; //當前線性表使用掉的長度
int size; //線性表的最大長度
char * top; //指向未使用的第一個位置
bool add(); //在順序表滿時，自動追加
public:
sqlist();
sqlist(const sqlist&);
~sqlist(); //虛構函數
bool insert(int,char);//給定位置和元素，插入操作
bool insert_end(char);//在末尾插入
bool empty(); //非空返回TURE ，空返回FALSE
bool del(int); // 刪除給定的位置元素
int e_search(char); //輸入給定元素，找出對應位置
char a_search(int); //輸入對應位置，找出對應元素
int get_length();
friend ostream& operator<<(ostream& out, sqlist &); //重載輸出操作符
};
sqlist::sqlist() //構造函數，初始化數據部分
{
base=new char[_INIT_SIZE];
top=base;
length=0;
size=_INIT_SIZE;
}
sqlist::sqlist(const sqlist &t_sq) //拷貝函數
{
char *temp;
size=t_sq.size;
base=new char[size];
top=base;
length=t_sq.length;
temp= t_sq.base;
for(int i=t_sq.length;i>0;i++,top++,temp++)
*top=*temp;
}
sqlist::~sqlist()
{
delete []base;
}
bool sqlist::add()
{
char *t_sq1;
char *t_sq2;
size=size+INCREMENT;
t_sq1=new char[size];
if(t_sq1==NULL)
return FALSE;
t_sq2=base;
top=t_sq1;
for(int i=length;i>0;i--,top++,t_sq2++)
*top=*t_sq2;
delete []base;
base=t_sq1;
return TURE;
}
bool sqlist::insert(int t_a, char t_e) //判斷方式有問題
{
char *t_p1;
char *t_p2;
if(t_a>=length+1||t_a<1)
return FALSE;
if(length>=size)
if(!add()) return FALSE;
t_p1=base+t_a-1;
t_p2=top;
for(; t_p2>t_p1-1 ;t_p2-- )
*t_p2=*(t_p2-1);
*t_p1=t_e;
length++;
top++;
return TURE;
}
bool sqlist::insert_end(char t_e)
{
if(length>=size)
if(!add()) return FALSE;
*top=t_e;
length++;
top++;
return TURE;
}
bool sqlist::empty()
{
if(length==0)
return FALSE;
else
return TURE;
}
bool sqlist::del(int t_a)
{
if(t_a>size||t_a<1)
return FALSE;
char *t_p1;
char *t_p2;
t_p1=base+t_a-1;
t_p2=t_p1;
for(; t_p2<top;t_p2++)
*t_p2=*(t_p2+1);
top--;
length--;
return TURE;
}
int sqlist::get_length()
{
return length;
}
char sqlist::a_search(int t_a)
{
char *t_p;
t_p=base+t_a-1;
return *t_p;
}
int sqlist::e_search(char t_e)
{
char *t_p;
int i=1;
for(t_p=base;t_p<top;t_p++,i++)
if(*t_p==t_e)
return i;
return EOF;
}
ostream& operator<<(ostream& out, sqlist &t_sq)
{
char *t_p;
for(t_p=t_sq.base;t_p<t_sq.top;t_p++)
out<<*t_p<<" ";
return out;
}
void main()
{
sqlist sq;
for(int i='a';i<5+'a';i++)
sq.insert_end(i);
cout<<"線性表: "<<sq<<endl; //輸出線性表
cout<<"線性表長度: "<<sq.get_length()<<endl;
if(!sq.empty())
cout<<"線性表為空"<<endl;
else
cout<<"線性表非空"<endl;
cout<<"線性表第3個元素是"<<sq.a_search(3)<<endl;
cout<<"元素a的位置是："<<sq.e_search('a')<<endl;
sq.insert(4,'f');
cout<<"線性表: "<<sq<<endl;
sq.del(3);
cout<<"線性表: "<<sq<<endl;
system("pause");
}
『捌』 數據結構的課程設計怎麼弄啊
# include <stdio.h>
# include <malloc.h>
struct BTNode
{
int data;
struct BTNode * pLchild;//p是指針，L是左，child是孩子
struct BTNode * pRchild;
};
//函數聲明
struct BTNode * CreateBTree(void);//創建樹
void PreTraverseBTree(struct BTNode * pT);//先序遍歷
void InTraverseBTree(struct BTNode * pT);//中序遍歷
void PostTraverseBTree(struct BTNode * pT);//後續遍歷
int main(void)
{
struct BTNode * pT = CreateBTree();
PreTraverseBTree(pT);
printf("\n");
InTraverseBTree(pT);
printf("\n");
PostTraverseBTree(pT);
return 0;
}
//創建樹
struct BTNode * CreateBTree(void)
{
struct BTNode * pA = (struct BTNode * )malloc(sizeof(BTNode));
struct BTNode * pB = (struct BTNode * )malloc(sizeof(BTNode));
struct BTNode * pC = (struct BTNode * )malloc(sizeof(BTNode));
struct BTNode * pD = (struct BTNode * )malloc(sizeof(BTNode));
struct BTNode * pE = (struct BTNode * )malloc(sizeof(BTNode));
pA->data = 'A';
pB->data = 'B';
pC->data = 'C';
pD->data = 'D';
pE->data = 'E';
pA->pLchild = pB;
pA->pRchild = pC;
pB->pLchild = NULL;
pB->pRchild = NULL;
pC->pLchild = pD;
pC->pRchild = NULL;
pD->pLchild = NULL;
pD->pRchild = pE;
pE->pLchild = NULL;
pE->pRchild = NULL;
return pA;
}
//先序遍歷
void PreTraverseBTree(struct BTNode * pT)
{ //先訪問根節點，再先序訪問左子樹，最後先序訪問右子樹
if ( pT != NULL)
{
printf("%c\n",pT->data);//訪問根節點
//pT->pLchild可以代表整個左子樹
PreTraverseBTree(pT->pLchild);
PreTraverseBTree(pT->pRchild);
}
return;
}
//中序遍歷
void InTraverseBTree(struct BTNode * pT)
{
if(pT != NULL )
{
if (NULL != pT->pLchild)
{
InTraverseBTree(pT->pLchild);
}
printf("%c\n",pT->data);
if (NULL != pT->pRchild)
{
InTraverseBTree(pT->pRchild);
}
}
return;
}
//後續遍歷
void PostTraverseBTree(struct BTNode * pT)
{
if(pT != NULL )
{
if (NULL != pT->pLchild)
{
PostTraverseBTree(pT->pLchild);
}
if (NULL != pT->pRchild)
{
PostTraverseBTree(pT->pRchild);
}
printf("%c\n",pT->data);
}
return;
}
『玖』 關於數據結構的課程設計
#include"stdio.h"
#defineMAX30000
/*函數聲明區*/
intSequenceSearch(inte[],intlen,intkey);
intBinarySearch(inte[],intlen,intkey);
voidStraightInsertSort(inte[],intlen);
voidQuickSort(inte[],intfirst,intend);
voidMergeSort(inte[],inta[],intfirst,intend);
voidHeapSort(inte[],intlen);
voidPrint(inte[],intlen,intcols);
/*全局變數區*/
longcompare; /*比較次數*/
longmove; /*移動次數*/
voidmain()
{
inti;
intn;
inttable[MAX],table1[MAX];
intkey;
intpos;
intchoice;
intcols=10;
system("cls");
printf("*********************************************************** ");
printf("INITIALIZETABLE ");
printf("n=");
scanf("%d",&n);
srand(time(NULL));
for(i=0;i<n;i++)
{
table[i]=rand();
table1[i]=table[i];
}
while(1)
{
system("cls");
printf("*********************************************************** ");
printf("ORIGINTABLE(%d): ",n);
Print(table,n,cols);
printf("*********************************************************** ");
printf("ORDERTABLE(%d): ",n);
StraightInsertSort(table1,n);
Print(table1,n,cols);
printf("*********************************************************** ");
printf("ALGORITHANALYSISSYSTEM ");
printf("1.SEQUENCESEARCHING ");
printf("2.BINARYSEARCHING ");
printf("3.STRAIGHTINSERTSORTING ");
printf("4.MERGESORTING ");
printf("5.HEAPSORTING ");
printf("6.QUICKSORTING ");
printf("0.EXITSYSTEM ");
printf("*********************************************************** ");
printf("YOURCHOICE:");
scanf("%d",&choice);
switch(choice)
{
case0:
return;
case1:
{
/***********************************************************************/
/*執行順序查找*/
printf(" key=");
scanf("%d",&key);
compare=0;
pos=SequenceSearch(table,n,key);
printf(" SequenceSearching ");
printf("---------------------------------------- ");
printf("Analysisdetails: ");
if(pos==-1)
{
printf(" search%dfail. ",key);
printf(" compare:%ldtimes.",compare);
}
else
{
printf(" search%dsuccess. ",key);
printf(" compare:%ldtimes.",compare);
}
printf(" ");
/***********************************************************************/
break;
}
case2:
{
/***********************************************************************/
/*執行二分查找*/
printf(" key=");
scanf("%d",&key);
compare=0;
pos=BinarySearch(table1,n,key);
printf(" BinarySearching ");
printf("---------------------------------------- ");
printf("Analysisdetails: ");
if(pos==-1)
{
printf(" search%dfail. ",key);
printf(" compare:%ldtimes.",compare);
}
else
{
printf(" search%dsuccess. ",key);
printf(" compare:%ldtimes.",compare);
}
printf(" ");
/***********************************************************************/
break;
}
case3:
{
/***********************************************************************/
/*執行直接插入排序*/
for(i=0;i<n;i++)
table1[i]=table[i];
compare=move=0;
StraightInsertSort(table1,n);
printf(" StraightInsertSorting ");
printf("---------------------------------------- ");
printf("Analysisdetails: ");
printf(" compare:%ldtimes. ",compare);
printf(" move:%ldtimes. ",move);
/***********************************************************************/
break;
}
case4:
{
/***********************************************************************/
/*執行歸並排序*/
for(i=0;i<n;i++)
table1[i]=table[i];
compare=move=0;
MergeSort(table1,table,0,n-1);
printf(" MergeSorting ");
printf("---------------------------------------- ");
printf("Analysisdetails: ");
printf(" compare:%ldtimes. ",compare);
printf(" move:%ldtimes. ",move);
/***********************************************************************/
break;
}
case5:
{
/***********************************************************************/
/*執行堆排序*/
for(i=0;i<n;i++)
table1[i]=table[i];
compare=move=0;
HeapSort(table1,n);
printf(" HeapSorting ");
printf("---------------------------------------- ");
printf("Analysisdetails: ");
printf(" compare:%ldtimes. ",compare);
printf(" move:%ldtimes. ",move);
/***********************************************************************/
break;
}
case6:
{
/***********************************************************************/
/*執行快速排序*/
for(i=0;i<n;i++)
table1[i]=table[i];
compare=move=0;
QuickSort(table1,0,n-1);
printf(" QuickSorting ");
printf("---------------------------------------- ");
printf("Analysisdetails: ");
printf(" compare:%ldtimes. ",compare);
printf(" move:%ldtimes. ",move);
/***********************************************************************/
break;
}
default:
break;
}/*endofswitch*/
system("pause");
getch();
}
}
/*順序查找*/
intSequenceSearch(inte[],intlen,intkey)
{
inti;
for(i=0;i<len;i++)
if(++compare&&e[i]==key)
returni;
++compare;
return-1;
}
/*二分查找*/
intBinarySearch(inte[],intlen,intkey)
{
inthigh,low,mid;
high=len-1;
low=0;
while(low<=high)
{
mid=(low+high)/2;
++compare;
if(key==e[mid])
return mid;
elseif(key>e[mid])
low=mid+1;
else
high=mid-1;
}
++compare;
return-1;
}
/*直接插入排序*/
voidStraightInsertSort(inte[],intlen)
{
inti,j,temp;
for(i=1;i<len;i++)
{
temp=e[i];
++move;
for(j=i-1;j>=0;j--)
{
if(++compare&&e[j]>temp)
{
e[j+1]=e[j];
++move;
}
else
break;
}
e[j+1]=temp;
++move;
}
}
/*快速排序*/
voidQuickSort(inte[],intfirst,intend)
{
inti=first,j=end,temp=e[first];
while(i<j)
{
while(++compare&&i<j&&e[j]>=temp)
j--;
e[i]=e[j];
++move;
while(++compare&&i<j&&e[i]<=temp)
i++;
e[j]=e[i];
++move;
}
e[i]=temp;
if(first<i-1)
QuickSort(e,first,i-1);
if(end>i+1)
QuickSort(e,i+1,end);
}
/*歸並排序*/
voidMergeSort(inte[],inta[],intfirst,intend)
{
voidMerge(inte[],inta[],intfirst,intm,intend);
intm;
intbak[MAX];
if(first==end)
a[first]=e[first];
else
{
m=(first+end)/2;
MergeSort(e,bak,first,m);
MergeSort(e,bak,m+1,end);
Merge(bak,a,first,m,end);
}
for(m=0;m<=end;m++)
e[m]=a[m];
}
voidMerge(inte[],inta[],intfirst,intm,intend)
{
inti=first,j=m+1,k=first;
while(i<=m&&j<=end)
{
++compare;
++move;
if(e[i]<=e[j])
a[k++]=e[i++];
else
a[k++]=e[j++];
}
while(i<=m&&++move)
a[k++]=e[i++];
while(j<=end&&++move)
a[k++]=e[j++];
}
/*堆排序*/
voidHeapSort(inte[],intlen)
{
voidsift(inte[],intl,intm);
inti,temp;
for(i=len/2-1;i>=0;i--)
sift(e,i,len);
for(i=len-1;i>=1;i--)
{
move+=2;
temp=e[i];
e[i]=e[0];
e[0]=temp;
sift(e,0,i-1);
}
}
voidsift(inte[],intl,intm)
{
inti,j,x;
i=l;
j=2*i+1;
x=e[i];
while(j<=m)
{
if(j<m&&++compare&&e[j]<e[j+1])
j++;
if(++compare&&x<e[j])
{
++move;
e[i]=e[j];
i=j;
j=2*i+1;
}
else j=m+1;
}
e[i]=x;
++move;
}
voidPrint(inte[],intlen,intcols)
{
inti;
for(i=1;i<=len;i++)
{
printf("%6d",e[i-1]);
if(i%cols==0)
printf(" ");
}
printf(" ");
}
運行測試：
『拾』 數據結構課程設計
#include <stdio.h>
#include <malloc.h>
#include <windows.h>
#include <time.h>
#define MAXSIZE 100
typedef struct Ttime{
int t_hour;
int t_min;
int t_sec;
}Ttime;
typedef struct Mcar{
int number;
Ttime t[2];
}Mcar;
typedef struct{
Mcar elements[MAXSIZE];
int top;
}CarStop;
typedef struct node{
Mcar date;
struct node *next;
}LinkQueue;
typedef struct{
LinkQueue *front;
LinkQueue *rear;
}Queue;
void InitQueue(Queue *Q){
Q -> front = (LinkQueue *) malloc(sizeof(LinkQueue));
Q -> front -> next = NULL;
Q -> rear = Q -> front;
}
int IsEmptyH(Queue Q){
if(Q.front == Q.rear)
return 1;
else
return 0;
}
void EeQueue(Queue *Q, Mcar x){
Q -> rear -> next = (LinkQueue *)malloc(sizeof(LinkQueue));
Q -> rear = Q -> rear -> next;
Q -> rear -> date = x;
Q -> rear -> next = NULL;
}
Mcar DeQueue(Queue *Q){
LinkQueue *p;
Mcar y;
if(!(*Q)){
p = Q -> front -> next;
Q -> front -> next = p -> next;
if(p -> next == NULL)
Q -> rear = Q -> front;
y = p -> date;
free(p);
return y;
}
}
int IsEmpty(CarStop S){
if(S.top == 0)
return 1;
else
return 0;
}
int IsFull(CarStop S){
if(S.top == MAXSIZE)
return 1;
else
return 0;
}
int Init(CarStop *S){
S -> top = 0;
}
void PutIn(CarStop *S, Mcar D){
if(!IsFull(*S)){
S -> elements[S -> top] = D;
S -> top++;
}
else
printf("IS FULL");
}
Mcar Pop(CarStop *S){
if(!IsEmpty(*S)){
S -> top--;
return S -> elements[S -> top];
}
else
printf("IS NULL");
}
Mcar TopNum(CarStop S){
if(!IsEmpty(S)){
return S.elements[S.top - 1];
}
}
int serachOneCar(CarStop S, Mcar num){
int i = 0;
if(!IsEmpty(S)){
while(i <= S.top){
if(num.number == S.elements[i].number)
return 1;
i++;
}
}
else
return 0;
}
void getInOneCar(CarStop *CarStack, Queue *Q, Mcar car){
time_t secnow;
struct tm * tmptr;
time(&secnow);
tmptr = localtime(&secnow);
car.t[0].t_hour= tmptr -> tm_hour;
car.t[0].t_min = tmptr -> tm_min;
car.t[0].t_sec = tmptr -> tm_sec;
printf("please put in you car number:\n");
scanf("%d", &car.number);
if(!IsFull(*CarStack))
PutIn(CarStack, car);
else{
printf("car stop is full, please stay in bian\n");
EeQueue(Q, car);
}
printf("you car's intime is :[%d]:[%d]:[%d]\n\n\n", car.t[0].t_hour, car.t[0].t_min, car.t[0].t_sec);
}
void getOutOneCar(CarStop *CarStack, CarStop *CarStackL, Queue *Q, Mcar car){
Mcar lin;
time_t secnow;
struct tm * tmptr;
time(&secnow);
tmptr = localtime(&secnow);
car.t[1].t_hour= tmptr -> tm_hour;
car.t[1].t_min = tmptr -> tm_min;
car.t[1].t_sec = tmptr -> tm_sec;
printf("please put in you car number:\n");
scanf("%d", &car.number);
if(IsEmpty(*CarStack) || !serachOneCar(*CarStack, car))
printf("soory, there is no the car\n");
else{
while(1){
lin = Pop(CarStack);
if(lin.number == car.number)
break;
else
PutIn(CarStackL, lin);
}
while(!IsEmpty(*CarStackL)){
PutIn(CarStack, Pop(CarStackL));
}
if(!IsEmptyH(*Q))
PutIn(CarStack, DeQueue(Q));
printf("\n\nyou car's intime is :[%d]:[%d]:[%d]\n", lin.t[0].t_hour, lin.t[0].t_min, lin.t[0].t_sec);
printf("you car's out time is :[%d]:[%d]:[%d]\n", car.t[1].t_hour, car.t[1].t_min, car.t[1].t_sec);
int alltime = (car.t[1].t_hour - lin.t[0].t_hour) * 3600 + (car.t[1].t_min - lin.t[0].t_min) * 60 + (car.t[1].t_sec - lin.t[0].t_sec);
printf("you car's all time is second:[%d]\n", alltime);
}
}
int main(){
CarStop CarStack, CarStackL;
Queue Q;
LinkQueue *pp;
InitQueue(&Q);
Init(&CarStack);
Init(&CarStackL);
Mcar car;
//String caozuo;
int caozuo, i, j;
while(1){
printf("\t**************the car stop menu*************\n");
printf("\t\t***** 1. get in a car\n\n");
printf("\t\t***** 2. get out a car\n\n");
printf("\t\t***** 0. out the car stop\n\n");
printf("\t\t*****put in the else you can see all the car in the carstop\n\n");
printf("\t*****************************************\n");
printf("please put in you caozuo: \n");
scanf("%d", &caozuo);
switch(caozuo){
case 1: getInOneCar(&CarStack, &Q, car);
break;
case 2: getOutOneCar(&CarStack, &CarStackL, &Q, car);
break;
case 0: return 0; break;
default : break;
}
if(!IsEmpty(CarStack)){
i = 0;
printf("the all car is:\n");
while(i < CarStack.top){
printf("the [%d] is %d\n",i + 1, CarStack.elements[i].number);
i++;
}
}
else
printf("the car stop IS NULL\n");
printf("****************************\n");
if(!IsEmptyH(Q)){
j = 1;
pp=Q.front;
printf("the bian's car is:\n");
while(pp!=Q.rear){
printf("the [%d] wait car is %d\n", j, pp -> next -> date.number);
pp = pp -> next;
j++;
}
}
else
printf("the bian is NULL\n");
printf("****************************\n");
system("pause");
system("cls");
}
}
C語言編譯通過