数据结构实验报告（华夏）

L= sequenlist; creatlist ( L ) ; clrscr();

printf(“ i , I -----------插入\\n”) ; printf(“ d , D -----------删除\\n”) ; printf(“ q , Q -----------退出\\n”) ; do { do

{ cmd=getchar() ; }

while (( cmd!=?d? )&& (cmd!=?D? )&& (cmd!=?I? )&& (cmd!=?i? )&&(cmd!=?q?) &&(cmd!=?Q?)) ;

switch (cmd) { case ?i? :

case ?I? : {

scanf(“%c”,&x) ; scanf(“%d”,&i) ; insert(L,x,i); printout (L) ; break ; }

case ?d? : case ?D? : {

scanf(“%d”,&i) ; delete(L , i); printout (L) ; break ; }

}

} while ( (cmd!=?q?) || (cmd!=?Q?)) }

三、运行结果分析与讨论

[测试数据] 输入n 为 10 （形成10个结点的表）

输入10个字符，如：A，B，C，D，E，F，G，H，I，J 选择I，输入G，10 程序运行的结果是什么？ 选择I，输入G，14 程序运行的结果是什么？

选择I，输入M，4 程序运行的结果是什么？ 选择D，输入6 程序运行的结果是什么？ 选择D，输入20 程序运行的结果是什么？

请将测试后的结果写出来，分析结果正确与否，提出改进意见。 四、巩固题 将参考程序按自己的想法转换为电子通信录程序。

注意：编程时可以考虑功能扩充、人机界面设计等问题，使之达到自己满意的效果。

实验二 链表的应用

一、预习报告

实验目的

1、掌握用Turbo C上机调试线性表的基本方法； 2、掌握指针变量和动态变量的使用及单链表的建立等运算算法在C语言上的程序实现；

基本原理与方法 链表的操作算法用C语言编程实现 实验设备 PC机一台、配置Turbo C软件

二、实验内容

链表基本操作的实现-----一元多项式简单计算器设计

[问题描述] 设计一元多项式简单计算器，用链式存储结构进行存储，完成常规操作。 [基本要求] 一元多项式简单计算器的基本功能有： 1、 输入并建立多项式的存储结构； 2、 输出多项式；

3、 两个多项式的加、减、乘运算；

[实现提示] 可选择带头结点的单链表或单向循环链表实现，假设要求用户按幂从大到

小的次序输入各个结点，结点的数据域有两项：幂与系数；

[参考程序]

#include #include

typedef struct polynode { int coef ;

int expn ;

struct polynode *next ; } *pnode ;

pnode createpoly () /*根据用户输入，建立多项式*/ { int a, n, i=1 ; pnode head , s, p ;

prinft (“输入一元多项式（以0，0标志结束）：\\n”) ; prinft (“要求：按幂从大到小的次序输入各个结点\\n”) ; head=(pnode) malloc (sizeof (struct polynode ) ) ; head->next = NULL; p = head ; do {

printf( “ 第%d次-> 系数，幂：” , i++ ) ; scanf (“ %d,%d”, &a, &n ) ; if ( a!=0 || n!=0)

{ s= (pnode) malloc (sizeof (struct polynode ) ) ; s -> cofe = a ; s -> expn = n ; s-> next = NULL ; p -> next = s ; p = s ; } } while (a!=0 || n!=0 ) ; printf ( “ \\n ”) ; return (head ) ; }

void printpoly (pnode head ) /*显示以head为头结点的多项式*/ { pnode s, p ;

int first = 1 ;

p = head -> next ; /*移去附加的表头结点*/ while (p != NULL) { if (first)

{ if ( p -> expn = = 1) /*显示头结点，系数大于0时，不显示+号*/ printf ( “%dx” , p ->coef ) ; else if (p -> expn = = 0) printf ( “%d” , p ->coef ) ; else

printf ( “%dx^%d” , p ->coef , p ->expn) ; first = 0 ; }

else /*显示其它结点，系数大于0时，显示+号*/ { if ( p -> expn = = 1)

printf ( “%+dx” , p ->coef ) ; else if (p -> expn = = 0) printf ( “%+d” , p ->coef ) ; else

printf ( “%+dx^%d” , p ->coef , p ->expn) ; }

p = p -> next ; }

printf ( “\\n ”) ; }

pnode addpoly (pnode pa,pnode pb ) /*两个多项式的加法运算*/ { int n;

pnode pc,s,p ; /*pc是新产生的链表头结点指针*/ pa = pa -> next ; pb = pb -> next ;

pc = (pnode) malloc (sizeof (struct polynode ) ) ; /*产生附加的表头结点*/ pc ->next = NULL ; p = pc ; /* P 指向PC链表的最后结点*/ while (pa != NULL && pb != NULL ) { if ( pa -> expn > pb -> expn )

{ s= (pnode) malloc (sizeof (struct polynode ) ) ; /* 建新结点*/ s -> coef = pa -> coef ; s -> expn = pa -> expn ; s ->next=NULL ; p -> next = s ; p = s ; pa = pa -> next ; }

else if (pa -> expn < pb -> expn )

{ s= (pnode) malloc (sizeof (struct polynode ) ) ;

s -> coef = pb -> coef ; s -> expn = pb -> expn ; s ->next=NULL ; p -> next = s ; p = s ; pb = pb -> next ; }

else /* 两项幂相等*/ { n= pa -> coef + pb -> coef ; if ( n!= 0 )

{ s= (pnode) malloc (sizeof (struct polynode ) ) ;

s -> coef =n; s -> expn = pa -> expn ; s ->next=NULL ; p -> next = s ; p = s ; }

pa = pa -> next ; pb = pb -> next ; }

}

while ( pa != NULL )

{ s= (pnode) malloc (sizeof (struct polynode ) ) ;

s -> coef = pa -> coef ; s -> expn = pa -> expn ; s ->next=NULL ; p -> next = s ; p = s ; pa = pa -> next ; }

while ( pb != NULL )

{ s= (pnode) malloc (sizeof (struct polynode ) ) ;

s -> coef = pb -> coef ; s -> expn = pb -> expn ; s ->next=NULL ; p -> next = s ; p = s ; pb = pb -> next ; }

return ( pc ) ;

}

main ()

{ pnode poly1 ,poly2 , poly3 ;

printf(“建立第1个一元多项式=>\\n”) ; poly1 = createpoly () ;

printf(“建立第2个一元多项式=>\\n”) ; poly2= createpoly () ;

poly3 = addpoly (poly1 , poly2 ) ; printf(“第1个一元多项式为\\n”) ; printpoly ( poly1) ;

printf(“第2个一元多项式为\\n”) ; printpoly ( poly2) ;

printf(“相加后的一元多项式为\\n”) ; printpoly ( poly3) ; }

三、运行结果分析与讨论

1．[测试数据] 给出两个多项式 3x3+2x2-5x+6 和 -2x3-2x2+5x+4 写出程序运行的结果 ，分析结果正确与否，提出改进意见。

2．按照参考程序的思路，补充两个函数，实现两个多项式的减、乘运算。

注意：主函数也要做相应改造，使之成为可供选择操作的控制模块。

四、巩固题 用单链表结构解决约瑟夫环问题

[问题描述] 设有N个人坐成一圈，现从某个人开始报数，数到M的人出列，再从下一个人开始重

新报数，数到M的人又出列，-----直到所有人都出列为止，试设计他们出列次序的程序。

设计算法及C程序，并调试运行之