数据结构第一次上机实验内容

数据结构第一次上机实验内容

注意：请把实验答案传到电子邮箱：luanch302@163.com，请写上姓名和学号。

第一部分：程序分析题

1、认真阅读分析下面的程序，并上机运行本程序，简述其功能。

程序如下：

#include

#include

#define MaxLength 10

typedef struct LIST

{ char name[MaxLength];

int length;

struct LIST *next;

}LIST;

LIST a,l,b,c,*p,*head;

void print_list() /* Print all the node of the list. */

{do

{printf(\"%s\\n\

p=p->next;

}while(p!=NULL);

}

insert_element(LIST l,int i,char x)

{int k;

if(i<1||i>l.length+1)

return(0);

if(l.length>=MaxLength)

{printf(\"The sequenlist is overflow!\");

return(-1);

}

for(k=l.length;k>=i-1;k--)

l.name[k+1]=l.name[k];

l.name[i-1]=x;

l.length++;

return(1);

}

delete_element(LIST l,int i)

{int k;

if(i>l.length||i<1)

{printf(\"The element you want to delete is not exist!\");

return(0);

}

for(k=i;kl.name[k-1]=l.name[k];

return(1);

}

LIST *insert_node(LIST *head,char x[MaxLength],int k)

{LIST *p,*pre,*s;

int j=1;

p=head;

pre=NULL;

while((p!=NULL)&&(j{ pre=p;

p=p->next;

j++;

}

if(j!=k)

{printf(\"The number of the node in the linklist is not reached k!\");

return(0);

}

s=(LIST *)malloc(sizeof(LIST));

if(s==NULL)

printf(\"The memory is not enough!\");

strcmp(s->name,x);

if(pre==NULL) /* When k=1. */

{s->next=head;

head=s;

}else

{s->next=pre->next;

pre->next=s;

}

return(head);

}

delete_node(LIST *head,int i)

{LIST *p,*q;

q=NULL;

p=head;

while(i--!=0&&p!=NULL)

{q=p;

p=p->next;

}

if(p==NULL)

{printf(\"The node not exist!\");

return(0);

}else

{if(q==NULL)

head=head->next;

else q->next=p->next;

free(p);

}

}

main()

{int i,choice;

char x[MaxLength],element,listname;

LIST l;

clrscr();

strcpy(a.name,\"Zhou\"); a.length=4;

strcpy(b.name,\"Xing\"); b.length=4;

strcpy(c.name,\"Chi\"); c.length=3;

head=&a;

a.next=&b;

b.next=&c;

c.next=NULL;

p=head;

printf(\"Welcome to use this programe!\\nNow the exist list is:\\n\");

print_list();

printf(\"Please chose the function:\\n1.Insert a element in a

sequenlist.\\n2.Delete a element in a sequenlist.\\n3.Insert a node in the

linklist.\\n4.Delete a node in the link list.\\n5.Quit the programe.\\n\");

scanf(\"%d\

switch(choice)

{case 5:{printf(\"Thanks to use!Good bye!\");

break;}

case 1:{printf(\"Input the list name:\");

scanf(\"%c\

printf(\"Input where the element you Insert:\");

scanf(\"%i\

printf(\"Input the element you want to Insert:\");

scanf(\"%c\

if(listname=='a') l=a;

if(listname=='b') l=b;

if(listname=='c') l=c;

insert_element(l,i,element);

print_list();

}

case 2:{printf(\"Input the list name:\");

scanf(\"%c\

printf(\"Input where the element you Delete:\");

scanf(\"%i\

if(listname=='a') l=a;

if(listname=='b') l=b;

if(listname=='c') l=c;

delete_element(l,i);

print_list();

}

case 3:{printf(\"Input where the node you want to Insert:\");

scanf(\"%d\

printf(\"Input the node you want to Insert:\");

scanf(\"%c\

insert_node(head,x,i);

print_list();

}

case 4:{printf(\"Input where the node you want to Delete:\");

scanf(\"%d\

delete_node(head,i);

print_list();

}

}

}

2、认真阅读分析下面的程序，并上机运行本程序，简述其功能，并写出运行结果。

#include \"stdio.h\"

void main()

{int a[20],i,j,x,y;

for(i=0;i<20;i++)

a[i]=0;

printf(\"请输入10个非零整数：\\n\");

for(i=0;i<10;i++)

scanf(\"%d\

printf(\"请输入\\\"在x之前插入y\\\"中的x,y：\\n\");

scanf(\"%d%d\

printf(\"插入之前顺序表为：\");

for(i=0;i<10;i++)

printf(\"%d,\

printf(\"\\n\");

for(i=10;i>=x;i--)

a[i+1]=a[i];

a[i]=y;

printf(\"插入之后顺序表为：\");

for(i=0;i<11;i++)

printf(\"%d,\

printf(\"\\n\");

printf(\"请输入\\\"删除第y个数据\\\"中的y：\\n\");

scanf(\"%d\

printf(\"删除之前顺序表为：\");

for(i=0;i<11;i++)

printf(\"%d,\

printf(\"\\n\");

for(i=y;i<11;i++)

a[i]=a[i+1];

printf(\"删除之后顺序表为：\");

for(i=0;i<10;i++)

printf(\"%d,\

printf(\"\\n\");

}

键入：1 2 3 4 5 6 7 8 9 10

输出：

3、认真阅读分析下面的程序，并上机运行本程序，简述其功能，并写出运行结果。

#include \"stdio.h\"

#include \"stdlib.h\"

void main()

{int x,y;

struct node

{int data;

struct node * next;

}*p,*q,*head;

printf(\"请输入10个正整数:\\n\");

scanf(\"%d\

head=(struct node *)malloc(sizeof(struct node));

p=head;

p->data=x;p->next=null;

for(i=0;i<9;i++)

{q=(struct node *)malloc(sizeof(struct node));

scanf(\"%d\

q->data=x;

q->next=null;

p->next=q;

p=q;

}

printf(\"\\\"请输入在x之后插入y\\\"中的x,y：\\n\")；

scanf(\"%d%d\

printf(\"插入之前链表为：\");

p=head;

while(p!=null)

{printf(\"%d,\

p=p->next;

}

printf(\"\\n\");

p=head;

while(p->data!=x&&p!=null)

p=p->next;

q=(struct node *)malloc(sizeof(struct node));

q->data=y;

q->next=p->next;

p->next=q;

printf(\"插入之后链表为：\");

p=head;

while(p!=null)

{printf(\"%d,\

p=p->next;

}

printf(\"\\n\");

printf(\"请输入\\\"删除第y个数据\\\"中的y：\\n\")；

scanf(\"%d\

printf(\"删除之前链表为：\");

p=head;

while(p!=null)

{printf(\"%d,\

p=p->next;

}

printf(\"\\n\");

printf(\"删除之后链表为：\");

p=head;

while(p->data!=x&&p!=null)

{q=p;

p=p->next;

}

q->next=p->next;

p=head;

while(p!=null)

{printf(\"%d,\

p=p->next;

}

printf(\"\\n\");

}

键入：1 2 3 4 5 6 7 8 9 10

输出：

4、认真阅读分析下面的程序，并上机运行本程序，简述其功能，并写出运行结果。

#include \"stdio.h\"

#include \"stdlib.h\"

void main()

{int x,y;

struct node

{int data;

struct node * next;

struct node * pred;

}*p,*q,*head;

printf(\"请输入一批数遇到0就结束:\\n\");

head=(struct node *)malloc(sizeof(struct node));

p=head;

p->data=0;p->next=null;p->pred=null;

scanf(\"%d\

while(x!=0)

{q=(struct node *)malloc(sizeof(struct node));

q->data=x;

q->next=null;

p->next=q;

q->pred=p;

p=q;

scanf(\"%d\

}

printf(\"读入数据的顺序为：\\n\")；

p=head->next;

while(p!=null)

{printf(\"%d,\

p=p->next;

}

printf(\"\\n\");

printf(\"先进先出顺序为：\\n\")；

p=head->next;

while(p!=null)

{printf(\"%d,\

p=p->next;

}

printf(\"\\n\");

printf(\"先进后出顺序为：\\n\")；

p=head->next;

while(p!=null)

{q=p;

p=p->next;

}

while(q->pred!=null)

{printf(\"%d,\

q=q->pred;

}

printf(\"\\n\");

}

键入：1 2 3 4 5 6 7 8 9 0

输出：

5、认真阅读分析下面的程序，并上机运行本程序，简述其功能，并写出运行结果。

#include \"stdio.h\"

#include \"stdlib.h\"

#define null 0

void main()

{int x,y;

struct node

{int data;

struct node * next;

struct node * pred;

}*p,*q,*head;

printf(\"请输入一个正整数:\");

head=(struct node *)malloc(sizeof(struct node));

p=head;

p->data=0;p->next=null;p->pred=null;

scanf(\"%d\

while(x/2!=0||x%2!=0)

{q=(struct node *)malloc(sizeof(struct node));

q->data=x%2;

q->next=null;

p->next=q;

q->pred=p;

p=q;

x=x/2;

}

printf(\"读入的数据为：%d\\n\

printf(\"%d对应的二进制数据为：\\n\

p=head->next;

while(p!=null)

{q=p;

p=p->next;

}

while(q->pred!=null)

{printf(\"%d\

q=q->pred;

}

printf(\"\\n\");

}

键入：25

输出：

第二部分：编程题

1、编程：用数组实现一个线性表，向其中依次存入各字符元素后，输出该线性表；然后删除线性表中最前(左)边的字符元素，再输出该线性表；最后在线性表中最前(左)边元素的前(左)边插入一个新元素，再输出该线性表。提示：从键盘输入字符'A'、'B'、'C'、'D'和'E'，再依次存入线性表，最后插入的字符为'F'。

2、编程：用数组实现一个栈，向其中依次压入字符元素后，再弹出栈中所有元素并输出，要求实现FILO。提示：从键盘输入的字符依次为'A'、'B'、'C'、'D'和'E'。

3、编程：用数组实现一个队列，向其中依次输入字符元素后，再输出队列中所有元素，要求实现FIFO。提示：从键盘输入的字符依次为'A'、'B'、'C'、'D'和'E'。

4、编程：用数组实现一个栈，借助该栈来实现将一个十进制数转换为二进制数。提示：从键盘输入的十进制数为25，求其对应的二进制数。

5、编程：用数组来存储一个字符串，求该字符串的长度。提示：从键盘输入字符串为\"Goodbye!\"。