上机实验报告(二)

“数据结构和算法 II”课程实验报告 实验名称：线性表的综合应用 班级_ 14 知识产权 1 班 _ 姓名 学号 _ 实验日 期： 2015/04/08 实验机时：2 学时 实验成绩： - 实验目的：掌握顺序表和链表的概念，学会对问题进行分析，选 择恰当的逻辑结构和物理结构 加深对顺序表和链表的理解，培养解决实际问题的编程能力 实验内容: 实现一元稀疏多项式的表示及基本操作（建立、销毁、输出、加 法、减法、乘法等操作） ； 一.实验内容：实现一元稀疏多项式的表示及基本操作（建立， 销毁，输出，加法，减法，求项数等操作）一元多项式一定 要包含系数项和指数项的描述，对一元多项式的基本运算， 可应用两个有序链表合并的思想进行 二程序及注释：#include“stdio.h“ #include“string.h“ #include“stdlib.h“ #include“ctype.h“ typedef struct node /定义结点 char data10; /结点的数据域为字符串 struct node *next; /结点的指针域 ListNode; typedef ListNode * LinkList; / 自定义 LinkList 单链表类型 LinkList CreatListR1(); /函数，用尾插入法建立带头结点的单链表 LinkList CreatList(void); /函数，用头插入法建立带头结点的单链表 ListNode *LocateNode(); /函数，按值查找结点 void DeleteList(); /函数，删除指定值的结点 void printlist(); /函数，打印链表中的所有值 void DeleteAll(); /函数，删除所有结点，释放内存 ListNode * AddNode(); /修改程序：增加节点。用头插法，返回头指针 /=主函数= void main() char ch10,num5; LinkList head; head=CreatList(); /用头插入法建立单链表，返回头指针 printlist(head); /遍历链表输出其值 printf(“ Delete node (y/n):“); /输入“y“或“n“去选择是否删除结点 scanf(“%s“,num); if(strcmp(num,“y“)=0 | strcmp(num,“Y“)=0) printf(“Please input Delete_data:“); scanf(“%s“,ch); /输入要删除的字符串 DeleteList(head,ch); printlist(head); printf(“ Add node ? (y/n):“); /输入“y“或“n“去选择是否增加结点 scanf(“%s“,num); if(strcmp(num,“y“)=0 | strcmp(num,“Y“)=0) head=AddNode(head); printlist(head); DeleteAll(head); /删除所有结点，释放内存 /=用尾插入法建立带头结点的单链表= LinkList CreatListR1(void) char ch10; LinkList head=(LinkList)malloc(sizeof(ListNode); /生成头结点 ListNode *s,*r,*pp; r=head; r-next=NULL; printf(“Input # to end “); /输入“#“代表输入结束 printf(“nPlease input Node_data:“); scanf(“%s“,ch); /输入各结点的字符串 while(strcmp(ch,“#“)!=0) pp=LocateNode(head,ch); /按值查找结点，返回结点指针 if(pp=NULL) /没有重复的字符串，插入到链表中 s=(ListNode *)malloc(sizeof(ListNode); strcpy(s-data,ch); r-next=s; r=s; r-next=NULL; printf(“Input # to end “); printf(“Please input Node_data:“); scanf(“%s“,ch); return head; /返回头指针 /=用头插入法建立带头结点的单链表= LinkList CreatList(void) char ch100; LinkList head,p; head=(LinkList)malloc(sizeof(ListNode); head-next=NULL; while(1) printf(“Input # to end “); printf(“Please input Node_data:“); scanf(“%s“,ch); if(strcmp(ch,“#“) if(LocateNode(head,ch)=NULL) strcpy(head-data,ch); p=(LinkList)malloc(sizeof(ListNode); p-next=head; head=p; else break; return head; /=按值查找结点，找到则返回该结点的位置，否则返回 NULL= ListNode *LocateNode(LinkList head, char *key) ListNode *p=head-next; /从开始结点比较 while(p!=NULL /扫描下一个结点 return p; /若 p=NULL 则查找失败，否则 p 指向找到的值为 key 的结点 /=修改程序：增加节点= ListNode * AddNode(LinkList head) char ch10; ListNode *s,*pp; printf(“nPlease input a New Node_data:“); scanf(“%s“,ch); /输入各结点的字符串 pp=LocateNode(head,ch); /按值查找结点，返回结点指针 printf(“ok2n“); if(pp=NULL) /没有重复的字符串，插入到链表中 s=(ListNode *)malloc(sizeof(ListNode); strcpy(s-data,ch); printf(“ok3n“); s-next=head-next; head-next=s; return head; /=删除带头结点的单链表中的指定结点= void DeleteList(LinkList head,char *key) ListNode *p,*r,*q=head; p=LocateNode(head,key); /按 key 值查找结点的 if(p=NULL ) /若没有找到结点，退出 printf(“position error“); exit(0); while(q-next!=p) /p 为要删除的结点，q 为 p 的前结点 q=q-next; r=q-next; q-next=r-next; free(r); /释放结点 /=打印链表= void printlist(LinkList head) ListNode *p=head-next; /从开始结点打印 while(p) printf(“%s, “,p-data); p=p-next; printf(“n“); /=删除所有结点，释放空间= void DeleteAll(LinkList head) ListNode *p=head,*r; while(p-next) r=p-next; free(p); p=r; free(p); 三实验结果： Input # to end Please input Node_data:bat Input # to end Please input Node_data:cat Input # to end Please input Node_data:eat Input # to end Please input Node_data:fat Input # to end Please input Node_data:hat Input # to end Please input Node_data:jat Input # to end Please input Node_data:lat Input # to end Please input Node_data:mat Input # to end Please input Node_data:# mat, lat, jat, hat, fat, eat, cat, bat, Delete node (y/n):y Please input Delete_data:hat mat, lat, jat, fat, eat, cat, bat, Insert node (y/n