中国地质大学数据结构实习报告

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

线性表的实现

1. 用链表实现线性表

这些是程序中一些子程序的声明，用它们来创建链表，并完成插入、删除、查找元素等操作，并且可以按照元素位置或者元素大小来进行这些操作。

pNode CreateLinkLists();

void PrintLists(pNode L);

void InsertRear(pNode L);

void InsertHead(pNode L);

void InsertkTh(pNode L, int position, ElemType x);

int GetLength(pNode L);

pNode Find(ElemType x, pNode L);

pNode FindPrevoius(ElemType x, pNode L);

int IsEmpty(pNode L);

int IsLast(pNode P, pNode L);

void Delete(ElemType x, pNode L);

void DeletekTh(int position, pNode L);

void DeleteList(pNode L);

插入程序代码

void InsertkTh(pNode L, int position, ElemType x)

{

int i;

pNode TmpNode, Tmp = L;

TmpNode = (pNode) malloc(sizeof(struct Node));

TmpNode->data = x;

TmpNode->next = NULL;

for(i=0; i

{

if(Tmp->next==NULL)

{

printf("The insertion position is invalid!\n");

return;

}

else

Tmp=Tmp->next;

}

TmpNode->next=Tmp->next;

Tmp->next=TmpNode;

}

删除程序代码

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");

printf(" 3. 插入一个元素到链表中 \n");

printf(" 4. 查找链表中的元素 \n");

printf(" 5. 删除链表中的元素 \n");

printf(" 6. 清空链表 \n");

scanf("%d",&i);

switch (i)

{ case 1: {

printf("输入元素来建立链表，0为结束输入的标志"); LinkLists = CreateLinkLists();

printf("链表为:");

PrintLists(LinkLists);

}

case 2: {PrintLists(LinkLists); break;}

case 3: {

printf("依次输入插入的位置和元素");

scanf("%d",&position);

scanf("%d",&x);

InsertkTh(LinkLists, int position, ElemType x); break;}

case 4: {

printf("输入要查找的元素");

scanf("%d",&x);

m=Find(ElemType x, LinkLists);

printf("%d",m);

break;}

case 5: {

printf("输入要删除的元素的位置");

scanf("%d",&position);

DeletekTh(int position, LinkLists);

break;}

case 6: {DeleteList(LinkLists); break;}

}

}

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)

{

arrLst->length=0;

}

//判断是否为空

int is_empty(arrayList arrLst)

{

if(0==arrLst->length)

{

printf("the arrayList is empty!\n"); return 1;

}

else

{

printf("the arrayList is not empty!\n"); return 0;

}

}

//求有多少个元素

int arrayLength(arrayList arrLst)

{

return arrLst->length;

}

//取出某个元素

int getElem(arrayList arrLst,int index,ElemType e) {

if(indexarrayLength(arrLst)-1) return 0;

else

{

e=arrLst->Array[index];

return 1; }

}

//遍历顺序表，并打印

void printArray(arrayList arrLst)

{

int i;

printf("array elements are:");

for(i=0;i

{

printf("%d\t",arrLst->Array[i]);

}

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)

{

return(S->top==-1);

}

void Push(ElemType X,STACK S)

{

if(IsFull(S))

{ printf("堆栈已满，元素无法进栈\n");

}

else

{

S->top++;

S->data[S->top]=X;

}

}

void Pop(STACK S)

{

if(IsEmpty(S))

printf("堆栈为空，元素无法出栈\n"); else

S->top--;

}

ElemType Top(STACK S)

{

if(!IsEmpty(S))

return S->data[S->top];

else

printf("堆栈为空！\n");

}

int DisposeStack(STACK S)

{

if(S==NULL)

return 0;

else

{

free(S);

printf("堆栈已成功清空！\n"); return 1;

}

}

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);

}

设置断点可以看到栈中的元素

模式匹配

这是模式匹配原函数，采用了KMP 方式进行匹配 #include

#include "moshipipei.h"

int IndexKMP(STRING *S, STRING *T, int next[]) {

int i=0;

int j=0;

while( ilength && jlength) {

if( j==-1 || S->p_str[i] == T->p_str[j] ) {

++i; ++j;

}

else

j = next[j];

}

if( j==T -> length )

return i-T -> length+1;

else return 0;

}

void GetNext(STRING *P,int next[]) {

int i=0;

next[0]=-1;

int j=-1;

while( i

length )

{

if(j==-1 || P->p_str[i]==P->p_str[j]) {

++i; ++j;

next[i]=j;

}

else j=next[j];

}

}

#include

#include

#include

#include "moshipipei.h"

主函数

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("%d\n",position);

}

显示两个字符串是在第6个元素开匹配的。

稀疏矩阵

TSMatrix NewMatrix(int m,int n){

//新建一个三元组表示的稀疏矩阵

TSMatrix M;

M.mu=m;

M.nu=n;

M.tu=0;

return M;

}

向三元组表内插入矩阵元素

Status InsertElem(TSMatrix *M,int row,int col,ElemType e){

//在三元组表示的稀疏矩阵M ，第 row 行，第 col 列位置插入元素e //插入成功，返回OK ，否则返回ERROR

int i,t,p;

if(M->tu>=MAXSIZE){//当前三元组表已满

printf("\nError:There is no space in the matrix;\n");

return ERROR;

}

if(row>M->mu||col>M->nu||row

return ERROR;

}

p=1;//标志新元素应该插入的位置

if(M->tu==0){//插入前矩阵M 没有非零元素

M->data[p].i=row;

M->data[p].j=col;

M->data[p].e=e;

M->tu++;

return OK;

}

for(t=1;ttu;t++)//寻找合适的插入位置

if((row>=M->data[t].i)&&(col>=M->data[t].j))

p++;

if(row==M->data[t-1].i && col==M->data[t-1].j){//插入前，该元素已经存在 M->data[t-1].e=e;

return OK;

}

for(i=M->tu;i>=p;i--){//移动p 之后的元素

M->data[i+1].i=M->data[i].i;

M->data[i+1].j=M->data[i].j;

M->data[i+1].e=M->data[i].e;

}

//插入新元素

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))

continue;

if(FALSE==FindElem(T,k,j,&t))

continue;

s+=m*t;

}

if(s!=0){//Q[i][j]非零

Q->data[p].i=i;

Q->data[p].j=j;

Q->data[p].e=s;

p++;

Q->tu++;

}

}

}

return OK;

}

查找

采用的是快速查找法

源程序

#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;

}

建立一个数组后查找元素，输入元素后，返回元素所在数组的下标。

排序

采用的是冒泡法排序

源程序

#include

#include "paixu.h"

void BubbleSort(int array[],int n)

{

int i=0;

int j=0;

int temp=0;

int flag=0;

for(i=0;i

{

flag = 0;

for(j=n-1;j > i;j--)

{

if(array[j]

{

temp =array[j];

array[j] = array[j-1];

array[j-1] = temp;

flag = 1;

}

}

if (flag == 0)

break;

}

}

void PrintArray(int array[] , int n)

{

int i;

for(i=0;i

printf(" %d ",array[i]);

printf("\n");

}

用数组储存数据，在用冒泡法排序后将排序好的数组输出。

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;

K1 = K2->right;

K2->right = K1->left;

K1->left = K2;

K2->height = MAX(Height(K2->left), Height(K2->right)) + 1; K1->height = MAX(Height(K2), Height(K1->right)) + 1;

return K1;

}

AVL 树中的双旋转

static Position DRL(Position K3)

{

#if 0

K3->left = SRR(K3->left);

return SRL(K3);

#else

Position K1 = NULL;

Position K2 = NULL;

K1 = K3->left;

K2 = K1->right;

K1->right = K2->left;

K2->left = K1;

K3->left = K2->right;

K2->right = K3;

return K2;

#endif

}

static Position DRR(Position K3)

{

#if 0

K3->right = SRL(K3->right);

return SRR(K3);

#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=%d\n", 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);

T = Insert(12, T);

T = Insert(11, T);

T = Insert(10, T);

T = Insert(8, T);

T = Insert(9, T);

PrintTree(T);

return 0;

}

树的结果：h 表示节点的高度，e 表示节点的值

路由算法

路由算法采用的是Dijkstra 算法

源代码

#include

#include

#include "Dijkstra.h"

#define MAX_LEN 100

#define INFINITE 1000

void InitStack(mstack *s)

{

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;

}

}

- 21 -