中国地质大学数据结构实习报告_中国地质大学实习报告
中国地质大学数据结构实习报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“中国地质大学实习报告”。
Practice Report for Data Structures and Algorithm Analysis
Data Structures Course Report
Candidate: Student Number:
Major:
Communication Engineering Supervisor:
Wu rangzhong
China University of Geosciences(Wuhan)Wuhan, Hubei 430074, P.R.China
May 18, 2013
China University of Geosciences, Faculty of Mechanics and Electronic Information
删除程序代码
void DeletekTh(int position, pNode L){
pNode Tmp=L, TmpPre=NULL;
int i=0;
for(i=0;i
{
if(Tmp->next!=NULL)
{
TmpPre = Tmp;
Tmp=Tmp->next;
}
else if(Tmp->next==NULL && i
{
printf(“The Deletion position is invalid!n”);
return;
}
}
TmpPre->next=Tmp->next;
free(Tmp);}
这是程序主函数，以此来完成以上子函数的功能
#include #include #include “lianbiao.h”
int main(){
int i,x,position;pNode m;
pNode LinkLists;
{
printf(“输入元素来建立链表，0为结束输入的标志”);
LinkLists = CreateLinkLists();
printf(“链表为:”);
PrintLists(LinkLists);
}
printf(“选择你需要的操作，输入序号：n”);
printf(“
1.建立一个链表
n”);
printf(“
2.输出链表
n”);
}
2.数组实现线性表
用数组实现的功能和用链表表示的相同 部分子函数如下
//初始化顺序表：给出初始化长度
int initialArray(arrayList arrLst,int len)
{
arrLst->length=0;
arrLst->size=len;
arrLst->Array=(ElemType*)malloc(len*sizeof(ElemType));
if(arrlst->Array==NULL)
return 0;
else
return 1;
}
//删除顺序表
void deleteArray(arrayList arrLst)
{
arrLst->length=0;
arrLst->size=0;
free(arrLst->Array);
arrLst->Array=NULL;
}
//清空顺序表
void clearArray(arrayList arrLst)
{
}
printf(“n”);
}
//判断某个元素的位置
int locateElem(arrayList arrLst,ElemType e)
{
int i;
for(i=0;i
{
if(e==arrLst->Array[i])
return i;
}
return-1;
}
堆栈
主要是实现元素的进栈、出栈、判断栈中元素个数
堆栈的源函数 #include #include #include“duizhan.h”
STACK CreatStack(){
STACK S;
S=(STACK)malloc(sizeof(struct Stack));
if(S==NULL)
{
printf(“无法建立堆栈!”);
return 0;
}
S->top=-1;
return S;}
int IsFull(STACK S){
return(S->top==MAX-1);}
int IsEmpty(STACK S){
int StackLen(STACK S){
if(!IsEmpty(S))
return S->top;else
return 0;}
堆栈的主函数 #include #include #include“duizhan.h”
void main(){
STACK liliS;
liliS=CreatStack();
Push(1,liliS);
Push(2,liliS);
Push(3,liliS);
Pop(liliS);
Pop(liliS);
DisposeStack(liliS);} 设置断点可以看到栈中的元素
主函数 void main(){ STRING *Str, *Pat;int position=0;Str=(STRING *)malloc(sizeof(STRING));Pat=(STRING *)malloc(sizeof(STRING));char S_str[20]=“ababcabcacbab”;char P_str[20]=“abcac”;
Str->p_str = S_str;Str->length = strlen(S_str);Pat->p_str = P_str;Pat->length = strlen(P_str);
int *next=(int *)malloc(sizeof(int)*(Pat->length +1));
GetNext(Pat, next);position=IndexKMP(Str, Pat, next);
printf(“%dn”,position);}
显示两个字符串是在第6个元素开匹配的。
}
//插入新元素
M->data[p].i=row;
M->data[p].j=col;
M->data[p].e=e;
M->tu++;
return OK;
}
稀疏矩阵的的转置
Status TransposeSMatrix(const TSMatrix *M,TSMatrix *T){
int col,p,q;
T->mu=M->nu;
T->nu=M->mu;T->tu=M->tu;
if(T->tu){
q=1;
for(col=1;colmu;col++)
for(p=1;ptu;p++)
if(M->data[p].j==col){
T->data[q].i=M->data[p].j;
T->data[q].j=M->data[p].i;
T->data[q].e=M->data[p].e;
q++;
}
}
return OK;
}
稀疏矩阵的乘法
Status MultSMatrix(const TSMatrix *M,const TSMatrix *T,TSMatrix *Q){
int i,j,k,p;
ElemType m,t,s;
if(M->nu!=T->mu){
printf(“Sorry,these two matrice can't multiply.n”);
return ERROR;
}
Q->mu=M->mu;
Q->nu=T->nu;
Q->tu=0;
p=1;
for(i=1;imu;i++){
for(j=1;jnu;j++){
s=0;
for(k=1;knu;k++){
if(FALSE==FindElem(M,i,k,&m))
查找
采用的是快速查找法 源程序
#include #include “chazhao.h”
int SequenceSearch(int array[],int n,int x){
int i=0;
while(i
i++;
if(i==n)
return-1;
else
return i;} 建立一个数组后查找元素，输入元素后，返回元素所在数组的下标。
5用数组储存数据，在用冒泡法排序后将排序好的数组输出。
AVL树
程序主要是在向二叉树插入节点后，最终生成AVL树
AVL树中的单旋转
static Position SRL(Position K2)
{
Position K1 = NULL;
K1 = K2->left;
K2->left = K1->right;
K1->right = K2;
K2->height = MAX(Height(K2->left), Height(K2->right))+ 1;
K1->height = MAX(Height(K1->left), Height(K2))+ 1;
return K1;}
static Position SRR(Position K2)
{
Position K1 = NULL;
#else
Position K1 = NULL;
Position K2 = NULL;
K1 = K3->right;
K2 = K1->left;
K1->left = K2->right;
K2->right = K1;
K3->right = K2->left;
K2->left = K3;
return K2;
#endif
}
主程序
#include #include “avlTree.h”
void PrintTree(AvlTree T)
{
if(T!= NULL)
{
PrintTree(T->left);
printf(“h=%d, e=%dn”, T->height, T->ele);
PrintTree(T->right);
}
}
int main(void)
{
AvlTree T = NULL;
T = MakeEmpty(T);
T = Insert(3, T);
T = Insert(2, T);
T = Insert(1, T);
T = Insert(4, T);
T = Insert(5, T);
T = Insert(6, T);
T = Insert(7, T);
T = Insert(16, T);
T = Insert(15, T);
T = Insert(14, T);
T = Insert(13, T);
s->bottom=0;
s->top=0;
memset(s->printout,0,sizeof(int)*MAX_LEN);}
void push(mstack *s,int m){
s->printout[s->top++]=m;}
int pop(mstack *s){
return s->printout[--s->top];}
void InitGraph(Graph *g,int n){
int i,j;
for(i=1;i
for(j=1;j
{
if(i==j)g->matrix[i][j]=0;
else g->matrix[i][j]=INFINITE;
}
for(i=1;i
{
in[i]=0;
Len[i]=INFINITE;
path[i]=0;
} }
