实验一 用指针处理链表指导书.doc

实验一用指针处理链表一实验目的了解链表是一种重要的数据结构和动态进行存储分配的一种结构。学会使用链表进行数据操作。二. 实验内容能够编写简单的建立链表、输出链表、链表插入和删除的程序，并进行数据输入、输出、插入和删除操作。三实验环境需要仪器、设备1 PC机一台，预装Win2K/Win98操作系统及Microsoft Visual C+ 6.0程序。 四实验线路及原理根据所给流程图写出建立一个有5名学生数据的单向链表的函数；将链表中各结点的数据集资输出的函数；删除和插入某个结点的函数；最后写出主程序建立链表及执行上述各项操作。开辟一个新结点，并使p1,p2指向它读入一个学生数据给p1所指的结点Head=NULL,n=0当读入的p1-num不是零N=n+1n真=1假Head=p1(把p1所指的结点作为第一个结点)P2-next=p1(把p1所批的结点连接到表尾)P2=p1(p2移到表尾)再开辟一个新结点，使p1再指向它读入一个学生数据给p1所指结点表尾结点的指针变量置NULL五实验方法与步骤自己设计后，经由指导教师审查后进行编译链接调试。六. 实验报告内容与要求1 画出程序流程图。2 写出具体程序。七. 思考1查找表的工作方式是否与链表操作一致？为什么？ 实验二用二叉树实现类属查找表一实验目的了解查找表是一种重要的数据抽象，是数据库应用和字处理的中心环节，是编译结构、操作系统设计、图形和数值方法以及其他应用的中心。二. 实验内容用二叉树实现类属查找表，建立面向对象系统的体系结构和基于对象消息传递的框架。插入一个实体到表中；从表中删去一个实体；确定表中具体实体是否存在；显示有中所有实体。三实验环境需要仪器、设备仪器：PC机一台。 四实验线路及原理用二叉树实现类属查找表，建立面向对象系统的体系结构和基于对象消息传递的框架。插入一个实体到表中；从表中删去一个实体；确定表中具体实体是否存在；显示有中所有实体。五实验方法与步骤1. 提供函数lessthan, equal和visittype的全局类型定义。指定lessthan是指向函数类型的指针，该函数返回一个整数并带有两个参数，每个均为一个字符地址。2. 定义一个类node，说明类search_table是它的一个友元。它的私有部分包含一个指向左或右子节点的指针，以及指向字符类型的指针。3. 指定类search_table中含有：数据root是一个指向类node的对象；数据size保存每个节点对象中数据存储的字节数；数据lt是一个指向类型lessthan函数的指针；eq是一个指向类型equal的函数指针；visit是一个指向类型visittype函数的指针。4. 类search_table的实现参见附录。5. 编写使用search_table抽象的测试程序。建立三张表，每张表使用一组不同的函数进行相等和不等的测试。第一张表使用last_name作为建表时的关键字；第二张表使用first_name作为建表时的关键字；第三张表使用age作为建表时的关键字。1 测试程序参见附录。六. 实验报告内容与要求1 出程序流程图。2 写出具体程序。七. 思考1能否用其它方式实现查找表？为什么？9附录1：/*Cchain.cpp*/#include Stdlib.h#include stdio.h#include iostream.h#define NULL 0#define LEN sizeof(struct student)struct studentlong num;int score;struct student *next;int n;struct student *creat()struct student *head;struct student *p1,*p2;n=0;p1=p2=(struct student *)malloc(LEN);scanf(%d,%f,&p1-num,&p1-score);head=NULL;while(p1-num!=0)n=n+1;if(n=1)head=p1;else p2-next=p1;p2=p1;p1=(struct student *)malloc(LEN);cinp1-num;cinp1-score;p2-next=NULL;return(head);struct student *del(struct student *head,long num)struct student *p1,*p2;if (head=NULL)printf(nlist null!n);goto end;p1=head;while(num!=p1-num&p1-next!=NULL)p2=p1;p1=p1-next;if(num=p1-num)if(p1=head)head=p1-next;else p2-next=p1-next;printf(delete:%ldn,num);n=n-1;else printf(%ld not been found!n,num);end:return(head);void print(struct student *head)struct student *p;printf(nNow,These %d records are:n,n);p=head;if(head!=NULL)do printf(%ld ,p-num);p=p-next;while (p!=NULL);struct student *insert(struct student *head,struct student *stud)struct student *p0,*p1,*p2;p1=head;p0=stud;if(head=NULL)head=p0;p0-next=NULL;elsewhile(p0-nump1-num)&(p1-next!=NULL)p2=p1;p1=p1-next;if(p0-numnum)if(head=p1) head=p0;else p2-next=p0;p0-next=p1;elsep1-next=p0;p0-next=NULL;n=n+1;return(head);void main()struct student * head,*stu;long del_num;printf(input records:n);head=creat();print(head);printf(ninput the deleted number:);cindel_num;head=del(head,del_num);print(head);printf(ninput the inserted record:);stu=(struct student *)malloc(LEN);cinstu-num;cinstu-score;head=insert(head,stu);print(head);附录2：/*search.h*/typedef int(* lessthan)(char*,char*);typedef int(* equal)(char*,char*);typedef void(* visittype)(char*);class nodefriend class search_table;private:node *left,*right;char *contents;class search_tableprivate:node *root;int size;lessthan it;equal eq;visittype visit;public:search_table (int s,lessthan l,equal e,visittype v)root=0;size=s;it=l;eq=e;visit=v;void insert(char *a);void remove(char *a);int is_present(char *a);void process_nodes (node *n=0,int first=1);void clear (node *n=0,int first=1);search_table()clear();/*search.cpp*/#include search.hvoid search_table:process_nodes(node *n,int first)node *current;if(first)current=root;first=0;elsecurrent=n;if(current!=0)process_nodes(current-left,first);(*visit)(current-contents);process_nodes(current-right,first);void search_table:insert(char *a)node *parent,*current;int found=0;parent=0;current=root;while (current&!found)if(*eq)(current-contents,a)found=1;elseparent=current;if(*it)(a,current-contents)current=current-left;elsecurrent=current-right;if(!found)if(!parent)root=new node;root-left=root-right=0;root-contents=new charsize;for(int i=0;icontentsi=ai;elseif(*it)(a,parent-contents)node *new_node=new node;new_node-contents=new charsize;for(int i=0;icontentsi=ai;new_node-left=new_node-right=0;parent-left=new_node;else node * new_node=new node;new_node-contents=new charsize;for(int i=0;icontentsi=ai;new_node-left=new_node-right=0;parent-right=new_node;int search_table:is_present(char *a)node *parent,*current;int found=0;parent=0;current=root;while(current&!found)if(*eq)(current-contents,a)found=1;elseparent=current;if(*it)(a,current-contents)current=current-left;elsecurrent=current-right;return found;void search_table:clear(node*n,int first)node *current;if(first)current=root;first=0;root=0;elsecurrent=n;if (current!=0)clear(current-left,first);clear(current-right,first);delete current-contents;delete current;void search_table:remove(char *a)node *previous,*present,*replace,*s,*parent;int found=0;previous=0;present=root;while (present&!found)if(*eq)(a,present-contents)found=1;elseprevious=present;if(*it)(a,present-contents)present=present-left;elsepresent=present-right;if(found)if(present-left=0)replace=present-right;elseif(present-right=0)replace=present-left;elseparent=present;replace=present-right;s=replace-left;while(s!=0)parent=replace;replace=s;s=replace-left;if(parent!=present)parent-left=replace-right;replace-right=present-right;replace-left=present-left;if(previous=0)root=replace;elseif(present=previous-left)previous-left=replace;elseprevious-right=replace;delete present-contents;delete present;/*treetst.cpp*/#include string.h#include stdio.h#include search.hstruct infochar lastname20;char firstname20;int age;int equal_lastname(char *n1,char*n2)info *info1,*info2;info1=(info*)n1;info2=(info*)n2;return(strcmp(info1-lastname,info2-lastname)=0);int equal_firstname(char *n1,char*n2)info *info1,*info2;info1=(info*)n1;info2=(info*)n2;return(strcmp(info1-firstname,info2-firstname)=0);int equal_age(char *n1,char*n2)info *info1,*info2;info1=(info*)n1;info2=(info*)n2;return(info1-age=info2-age);int less_than_lastname(char *n1,char*n2)info *info1,*info2;info1=(info*)n1;info2=(info*)n2;return(strcmp(info1-lastname,info2-lastname)firstname,info2-firstname)ageage);void display(char *n)info *info1;info1=(info*)n;printf(n%s,%s%d,info1-lastname,info1-firstname,info1-age);void main()search_table table1(sizeof(info),less_than_lastname,equal_lastname,display);info my_info;strcpy(my_info.lastname,Jones);strcpy(my_info.firstname,Mary);my_info.age=26;table1.insert(char *)&my_info);strcpy(my_info.lastname,Zachary);strcpy(my_info.firstname,Richard);my_info.age=46;table1.insert(char *)&my_info);strcpy(my_info.lastname,Smith);strcpy(my_info.firstname,Avery);my_info.age=16;table1.insert(char *)&my_info);strcpy(my_info.lastname,Berlin);strcpy(my_info.firstname,Irving);my_info.age=96;table1.insert(char *)&my_info);strcpy(my_info.lastname,Kansas);strcpy(my_info.firstname,Wichita);my_info.age=123;table1.insert(char *)&my_info);cess_nodes();search_table table2(sizeof(info),less_than_firstname,equal_firstname,display);strcpy(my_info.lastname,Jones);strcpy(my_info.firstname,Mary);my_info.age=26;table2.insert(char *)&my_info);strcpy(my_info.lastname,Zachary);strcpy(my_info.firstname,Richard);my_info.age=46;table2.insert(char *)&my_info);strcpy(my_info.lastname,Smith);strcpy(my_info.firstname,Avery);my_info.age=16;table2.insert(char *)&my_info);strcpy(my_info.lastname,Berlin);strcpy(my_info.firstname,Irving);my_info.age=96;table2.insert(char *)&my_info);strcpy(my_info.lastname,Kansas);strcpy(my_info.firstname,Wichita);my_info.age=123;table2.insert(char *)&my_info);cess_nodes();search_table table3(sizeof(info),less_than_age,equal_age,display);strcpy(my_info.lastname,Jones);strcpy(my_info.firstname,Mary);my_info.age=26;table3.insert(char *)&my_info);strcpy(my_info.lastname,Zachary);strcpy(my_info.firstname,Richard);my_info.age=46;table3.insert(char *)&my_info);strcpy(my_info.lastname,Smith);strcpy(my_info.firstname,Avery);my_info.age=16;table3.insert(char *)&my_info);strcpy(my_info.lastname,Berlin);strcpy(my_info.firstname,Irving);my_info.age=96;table3.insert(char *)&my_i