1、实验一 单链表实验(一 ) 实 验 目 的1. 理解线性表的链式存储结构。2. 熟练掌握动态链表结构及有关算法的设计。3. 根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法。(二 ) 实 验 任 务编写算法实现下列问题的求解1. 求链表中第 i 个结点的指针（函数） ，若不存在，则返回 NULL。2. 在第 i 个结点前插入值为 x 的结点。3. 删除链表中第 i 个元素结点。4. 在一个递增有序的链表 L 中插入一个值为 x 的元素，并保持其递增有序特性。5. 将单链表 L 中的奇数项和偶数项结点分解开，并分别连成一个带头结点的单链表，然后再将这两个新链表同时输出在屏幕上，
2、并保留原链表的显示结果，以便对照求解结果。6. 求两个递增有序链表 L1 和 L2 中的公共元素，并以同样方式连接成链表 L3。(三 ) 主 要 仪 器 设 备PC 机，Windows 操作平台，Visual C+(四 ) 实 验 分 析顺序表操作：定义一个顺序表类，该类包括顺序表的存储空间、存储容量和长度，以及构造、插入、删除、遍历等操作的方法(五 ) 源 程 序头文件 文件名：linklist.h#includeusing namespace std;struct nodeint data;node *next;class listpublic:list();int length()con
3、streturn count; /求链表长度list();void create(); /链表构建，以 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 i
4、nt x);friend void SplitList(list L1, listfriend void get_public(list L1, list L2, list 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=N
5、ULL;cinx;void list:output()node *p=head-next;coutdatanext;coutnext;j=1;while(p!=NULL j+;if(p=NULL) return 0;elsereturn x=p-data;return 1;node *list:locate(const int x)constnode *p=head-next;while(p!=NULL)if(p-data=x)return p;else p=p-next;return NULL;int list:insert(const int i,const int x) /实验 2nod
6、e *p=head;int j=0;while(j!=i-1j+;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) /实验 3node *p=head;int j=0;while(j!=i-1j+;if(icount)return 0;node *u=p-next;p-next=u-next;delete u;count-;return 1;void list:insert2(const int x)
7、 /实验 4node* p,*q;p=head;while(p-next!=NULL if (p-next=NULL | p-next-datax)q=new node;q-data=x;q-next=p-next;p-next=q;count+;list:list()while(head-next!=NULL) delete_element(1);主程序#include #include“linklist.h“using namespace std;void SplitList(list L1, listfor(int i = 1; p1 != NULL; i+)if(i % 2) L2.i
8、nsert(L2.count+1,p1-data);else L3.insert(L3.count+1,p1-data);p1=p1-next;L1.output();L2.output();L3.output();void get_public(list L1,list L2,list while (p1!=NULL else if (p1-datap2-data)p2=p2-next;elseL3.insert(L3.count+1,p1-data);p1=p1-next;p2=p2-next;int main()list L1;int i,x;couti;coutxi;L1.insert(i,x);L1.output();couti;
