数据结构的课程设计
『壹』 数据结构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语言编译通过