数据结构实验报告new.docVIP

本科实验报告 课程名称： 数据结构 实验项目：线性结构、树形结构、图结构、查找、排序 实验地点： 逸夫楼302 专业班级： 软件1225班 学号： 2012005700 学生姓名： 宋立伟 指导教师： 杨永强 2013年 1 月 2日 实验名称：线性表 一．目的与要求 本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列例题，上机通过，并观察其结果，然后独立完成后面的实习题。 二．例题 [问题描述] 用链表形式存储一个字符串，插入、删除某个字符，最后按正序、逆序两种方式输出字符串。 [输入] 初始字符串，插入位置，插入字符，删除字符。 [输出] 已建立链表（字符串），插入字符后链表，删除字符后链表，逆转后链表。 [存储结构] 采用链式存储结构 [算法的基本思想] 建立链表：当读入字符不是结束符时，给结点分配存储空间，写数据域，将新结点插到表尾；插入字符：根据读入的字符在链表中找插入位置，将新结点插入到该位置之前；删除字符：根据读入的删除字符在链表中找到被删结点后，将其从链表中删除；链表逆转：从链表的第一个结点开始对所有结点处理，将每个结点的前驱变为它的后继；打印链表：从链表的第一个结点开始，依次打印各个结点的数据域。 [参考源程序] #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!=k1p) ?????? p=p-link; ??? if(p){ ?????? q=(nodelink)malloc(sizeof(node)); ?????? q-a=k2; ?????? q-link=p-link; ?????? p-link=q; ?????? return 1; ??? ? } ??? 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; ??? whi