《《数据结构》实验报告（单链表实验、二叉树实验、排序实验）》由会员分享，可在线阅读，更多相关《《数据结构》实验报告（单链表实验、二叉树实验、排序实验）（26页珍藏版）》请在金锄头文库上搜索。
1、实验一 单链表实验(一) 实验目的1. 理解线性表的链式存储结构。2. 熟练掌握动态链表结构及有关算法的设计。3. 根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法。(二) 实验任务编写算法实现下列问题的求解1. 求链表中第i个结点的指针（函数），若不存在，则返回NULL。2. 在第i个结点前插入值为x的结点。3. 删除链表中第i个元素结点。4. 在一个递增有序的链表L中插入一个值为x的元素，并保持其递增有序特性。5. 将单链表L中的奇数项和偶数项结点分解开，并分别连成一个带头结点的单链表，然后再将这两个新链表同时输出在屏幕上，并保留原链表的显示结果，以便对照求解结果。6.
2、求两个递增有序链表L1和L2中的公共元素，并以同样方式连接成链表L3。(三) 主要仪器设备PC机，Windows操作平台，Visual C+(四) 实验分析顺序表操作：定义一个顺序表类，该类包括顺序表的存储空间、存储容量和长度，以及构造、插入、删除、遍历等操作的方法(五) 源程序头文件 文件名：linklist.h#includeusing namespace std;struct node int data; node *next;class listpublic: list(); int length()const return count; /求链表长度 list(); void cre
3、ate();/链表构建，以0为结束标志 void output();/链表输出 int get_element(const int i)const;/按序号取元素 node *locate(const int x) const;/搜索对应元素 int insert(const int i,const int x);/插入对应元素 int delete_element(const int i);/删除对应元素 node *get_head() return head; /读取头指针 void insert2(const int x); friend void SplitList(list L1,
4、 list&L2, list &L3); friend void get_public(list L1, list L2, list &L3);private: int count; node *head;list:list() head=new node; head-next=NULL; count=0;void list:create() /链表构建，以0为结束标志 int x; coutx; node *rear=head; while(x!=0) count+; node *s=new node; s-data=x; rear-next=s; rear=s; rear-next=NUL
5、L; cinx; void list:output() node *p=head-next; cout*Top of this list*endl; while(p!=NULL) coutdatanext; coutendl*End of this list*next; j=1; while(p!=NULL & j!=i) p=p-next; j+; if(p=NULL) return 0; else return x=p-data; return 1; node *list:locate(const int x)const node *p=head-next; while(p!=NULL)
6、if(p-data=x)return p; else p=p-next; return NULL;int list:insert(const int i,const int x) /实验2 node *p=head; int j=0; while(j!=i-1&p!=NULL) p=p-next; j+; if(icount+1) return 0; node *s=new node; s-data=x; s-next=p-next; p-next=s; count+; return 1;int list:delete_element(const int i) /实验3 node *p=hea
7、d; int j=0; while(j!=i-1&p!=NULL) p=p-next; j+; if(icount) return 0; node *u=p-next; p-next=u-next; delete u; count-; return 1;void list:insert2(const int x) /实验4 node* p,*q; p=head; while(p-next!=NULL & p-next-datanext; if (p-next=NULL | p-next-datax) q=new node; q-data=x; q-next=p-next; p-next=q;
8、count+; list:list() while(head-next!=NULL) delete_element(1);主程序#include #includelinklist.husing namespace std;void SplitList(list L1, list&L2, list &L3) node *p1= L1.head-next; for(int i = 1; p1 != NULL; i+) if(i % 2) L2.insert(L2.count+1,p1-data); else L3.insert(L3.count+1,p1-data); p1=p1-next; L1
9、.output(); L2.output(); L3.output();void get_public(list L1,list L2,list &L3) node *p1=L1.head-next, *p2=L2.head-next; while (p1!=NULL & p2!=NULL) if (p1-datadata) p1=p1-next; else if (p1-datap2-data) p2=p2-next; else L3.insert(L3.count+1,p1-data); p1=p1-next; p2=p2-next; int main() list L1; int i,x
10、; cout当前为实验1、2、3; L1.create(); couti; coutL1.get_element(i)endl; coutxi; L1.insert(i,x); L1.output(); couti; L1.delete_element(i); L1.output(); list L1; int x; cout实验4，输入递增有序的L; L1.create(); coutx; L1.insert2(x); L1.output(); list L1,L2,L3; cout当前为实验5，单链表L奇数、偶数项分开; L1.create(); SplitList(L1,L2,L3); list L1,L2,L3; cout当前为实验6，求L1与L2公共元素; L1.create(); L2.create(); get_public(L1,L2,L3); L3.output(); return 0;(六)
