算法与数据结构实验

实验目的：

1.掌握链表的概念，学会对链表进行操作．

2.加深对链式存储数据结构的理解，逐步培养解决实际问题的能力．

实验内容：

1.初始化链表 2.建立一个链表．

3.向链表中插入指定的元素． 4.从链表中删除一个元素．

实验程序：

#include #include typedef struct list{

int data;

struct list *next; }LIST;

void initlist(LIST **p) {*p=NULL;}

void insertlist1(LIST **p , int ele, int pos) {

int i;

LIST *u,*q,*r;

u=( LIST *)malloc(sizeof(LIST)); u->data=ele;

for(i=0,r=*p; inext;} if (r= =*p) *p=u; else q->next=u; u->next = r; }

int deletelist (LIST **p , int ele) {

LIST *q , *r; q = *p;

if(q = =NULL) return 1;

1

if(q->data = = ele)

{ p=q->link; free(r); return 0; } for(;q->data!=ele && q->next!=NULL) if(q->data == ele)

{ q->next=r->next; free(q); return 0;} return 1; }

实验二

实验目的：

1.熟悉栈的定义和栈的基本操作．

2.掌握顺序存储栈和链式存储栈的基本运算． 3.加深对栈的理解，逐步培养解决问题的能力．

实验内容：

1.编写进栈和出栈函数及输出栈顶元素函数． 2.调用以上函数完成下列操作： （1）调用进栈函数建立栈 （2）读取栈顶元素． （3）删除栈顶元素．

（4）输出栈中所有元素．

实验程序：

#include #define MAXN 10

int push(int *stack,int maxn,int topp,int x) {

if(*topp>=maxn) return 1; stack[+topp]=x; ++(*topp); return 0 }

int pop(int *stack,int *topp,int *cp) {

if(*topp==0) return 1; --(*topp);

*cp=stack[*topp]; return 0

2

}

void outputstack(int *stack,int topp) {

int i;

for(i=topp-1;i>=0;i--)

printf(“%d”,stack[i]); printf(“\\n”); }

void main() {

int s[MAXN]; int op; while(1) {

printf(“请选择操作，1：进栈 2：出栈 0：退出”); fflush(stdin); scanf(“%d”,&op); switch(op){

case 0: return; case 1:

printf(“请输入一个进栈元素：”); scanf(“%d”,&i);

if(push(s,MAXN,&top,i)==0)

{printf(“进栈成功，栈内元素为：\\n”); Output(s,top);}

else printf(“栈满\\n”); break;

“出栈元素为：［％d］,栈内元素为：\\n”,i); “栈空\\n”);

3

case 2:

if(pop(s,&top,&i)==0) {printf( Output(s,top);}

else printf( break; } } }

实验三

实验目的：

1.掌握链接队列的进队和出队等基本操作．

2.加深对队列的理解，逐步培养解决问题的能力．

实验内容：

1.编写进队和出队及输出队列中元素函数． 2.调用以上函数完成下列操作： （1）调用进进队函数建立队列 （2）读取队列中第一个元素． （3）删除队列中元素．

（4）输出队列中所有元素．

实验程序：

#include #include typedef struct queue{

int data;

struct queue *link; }QUEUE;

void enqueue(QUEUE **head, QUEUE **tail,int x) {

QUEUE *p;

P=(QUEUE *) malloc(sizeof(QUEUE)); p->data=x; p->link=NULL;

if(*head==NULL) *head=*tail=p; else {

(*tail)->link=p; *tail=p;} }

int dequeue(QUEUE **head, QUEUE **tail,int *cp) {

QUEUE *p; P=*head;

if(*head==NULL) return 1; *cp=(*head)->data;

4

*head=(*head)->link;

if(*head==NULL) *tail=NULL; free(p); return 0; }

void outputqueue(QUEUE *head) {

while(head!=NULL)

{printf(“%d”,head->data); head=head->link; }

printf(“\\n”); }

void main() {

QUEUE *head,*tail; int op,I; while(1) {

printf(“请选择操作，1：进队 2：出队 0：退出”); fflush(stdin); scanf(“%d”,&op); switch(op){

case 0: return;

case 1: printf(“请输入进队元素：”); scanf(“%d”,&i);

enqueue(*head,*tail,&i); printf(“对内元素为：”); outputqueue(head); break;

case 2: if(dequeue(*head,*tail,&i)==0)

{printf(“出队元素为［%d］,对内元素为：\\n”); Outputqueue(head);}

else printf(“队列空\\n”); break; } }

}

5

实验四

实验目的：

1.掌握数组的定义、 赋值和输入输出方法等基本操作． 2.加深对数组的理解，逐步培养解决问题的能力．

实验内容：

1.编写程序求Fibonacci数列的前20项．

2.按行顺序为5×5的二维数组赋20以内的自然数，然后输出该数组的下三角．实验程序：

1.

#include #define MAX 20 void main() {

int i,fib[MAX]; fib[0]=0; fib[1]=1;

for(i=2;ifib[i]=fib[i-1]+fib[i-2]; for(i=0;iprintf(“%d%c”,fib[i],(i%5)==4? ’\\n’:’\’); } 2.

#include #define MAX 5 void main() {

int i,j,n=1; int a[MAX][MAX] for(i=0;iprintf(“%d\”,a[i][j]); printf(“\\n”);}}

6

实验五

实验目的：

1.掌握在数组上进行各种查找的方法与算法． 2.深刻理解各种方法的特点，并加以灵活运用．

3.加深对查找的理解，逐步培养解决问题的编程能力．

实验内容：

1.编写对无序线性表，有序线性表的顺序查找和折半查找的程序．

2.调用上述函数实现对数组a[]={13,48,25,31,14,19,67,89,10,54}各种查找．实验程序：

#include #include #define N 10

int a[N]= {13,48,25,31,14,19,67,89,10,54}; void ss_sort(int a[],int n) {

int i,j,k,t;

for(i=0;i<=n-1;i++)

{for(k=i,j=i+1;ja[j]) k=j; if(k!=i)

{t=a[i]; a[i]=a[k]; a[k]=t;} }

}

int search1(int *k,int n,int key) {

int i;

for(i=0;i}

int search2(int *k,int n,int key) {

int i;

for(i=0;ik[i];i++); if(i7

}

int bin_search(int *k,int n,int key) {

int low=0,high=n-1,mid; while(lowmid=(low+high)/2;

if(key==k[mid]) return mid; if(key>k[mid]) low=mid+1; else high=mid-1; }

return -1; }

void main() {

int i,j;

printf(“原始数据序列为：\\n”); for(i=0;iprintf(“%d\”,a[i]);

printf(“\\n请输入要查找的关键码：”); scanf(“%d”,&i);

if(j=search1(a,N,i)>=0) printf(“找到关键码，位置为%d\\n”,j+1); else printf(“找不到\\n”); getch();

ss_sort(a,N);

printf(“排序后数据序列为：\\n”); for(i=0;iprintf(“%d\”,a[i]);

printf(“\\n请输入要查找的关键码：”); scanf(“%d”,&i);

if(j=search2(a,N,i)>=0) printf(“找到关键码，位置为%d\\n”,j+1); else printf(“找不到\\n”); getch();

printf(“\\n请输入要查找的关键码：”); scanf(“%d”,&i);

if(j=bin_search(a,N,i)>=0) printf(“找到关键码，位置为%d\\n”,j+1); else printf(“找不到\\n”); getch(); }

8