数据结构实验报告.doc

0 本科实验报告课程名称: 数据结构 B 实验项目: 数据结构实验实验地点: 教室专业班级: 软件 1331 学号: 2013005976 学生姓名: 孙涛指导教师: 杨崇艳 2014 年 12月 16日 1 , 提高分析和解决问题的能力。要求仔细阅读并理解下列例题, 上机通过, 并观察其结果, 然后独立完成后面的实****题。[ 问题描述] 用链表形式存储一个字符串,插入、删除某个字符,最后按正序、逆序两种方式输出字符串。[ 输入] 初始字符串,插入位置,插入字符,删除字符。[ 输出] 已建立链表(字符串),插入字符后链表,删除字符后链表,逆转后链表。[ 存储结构] 采用链式存储结构[ 算法的基本思想] 建立链表:当读入字符不是结束符时,给结点分配存储空间,写数据域,将新结点插到表尾;插入字符: 根据读入的字符在链表中找插入位置, 将新结点插入到该位置之前; 删除字符: 根据读入的删除字符在链表中找到被删结点后,将其从链表中删除;链表逆转:从链表的第一个结点开始对所有结点处理,将每个结点的前驱变为它的后继;打印链表:从链表的第一个结点开始,依次打印各个结点的数据域。[ 参考源程序] #define NULL 0 typedef struct node{ char a; struct node *link; }node,*nodelink; void readlink(nodelink head){ nodelink p,q; char c; p=head; printf("Input a linktable(a string):"); scanf("%c",&c); if (c=='\n') printf("This string is empty 。"); while(c!='\n') { q=(nodelink)malloc(sizeof(node)); q->a=c; p->link=q; p=q; scanf("%c",&c); } p->link=NULL; } void writelink(nodelink head) { nodelink q; if (head->link==NULL) printf(" This link is empty 。\n"); for(q=head->link;q;q=q->link) printf("%c",q->a); printf("\n"); } int insert(nodelink head,char k1,char k2) { nodelink p,q; p=head->link; while(p->a!=k1&&p) p=p->link; if(p){ q=(nodelink)malloc(sizeof(node)); q->a=k2; q->link=p->link; p->link=q; return 1; 2 } else { printf("There is no %c\n",k1); return 0;} } int delete(nodelink head,char k) { nodelink p,q; q=head; p=head->link; while(((p->a)!=k)&&p){ q=q->link; p=p->link; } if(p) { q->link=p->link; return 1;} else{ printf("There is no %c\n",k); return 0;} } void opside(nodelink head) { nodelink p,q; p=head->link; while(p->link){ q=p->link; p->link=q->link; q->link=head->link; head->link=q; } } main() { char k1,k2,k3; nodelink head; head=(nodelink)malloc(sizeof(node)); head->link=NULL; readlink(head); if (head->link!=NULL) {printf("Build link is :"); writelink(head); } if (head->link!=NULL) { printf("Please input a char you want to insert after:"); k1=getch(); printf("%c\n",k1); printf("Please input a char you want to insert