实验二线性表的链式存储实验目的：●掌握线性表的链式存储结构的定义及C语言实现●掌握单链表中的各种基本操作（单链表的建立、合并、删除等）实验内容：1、单链表的建立及输出(插入)参考代码：/*保存在头文件Linklist.h*/#include <stdio.h>#include<malloc.h>#define NULL 0typedef int Elemtype;typedef struct Lnode{Elemtype data;struct Lnode *next;}Lnode,*Linklist;//使用尾插法创建单链表void creatlist_L(Linklist L,int n){int i;Linklist p,q;q=L;for(i=1;i<=n;i++){p=(Linklist)malloc(sizeof(Lnode)); printf("输入线性表的第%d个元素：",i); scanf("%d",&p->data);p->next=q->next;q->next=p;q=q->next;}}//使用头插法创建单链表void creatlist_L(Linklist L,int n){int i;Linklist p;p=L;for(i=n;i>0;i--){p=(Linklist)malloc(sizeof(Lnode));printf("输入线性表的第%d个元素：",i);scanf("%d",&p->data);p->next=L->next;L->next=p;}}void traverlist_L(Linklist head){Linklist p;printf("以head 为头指针的单链表中的元素为："); p=head->next;while(p!=NULL){printf("%5d ",p->data);p=p->next;}printf("\n");}#include<stdio.h>#include<Linklist.h>void main(){Linklist head;int n;printf("********建立一个单链表中的操作******\n");printf("输入要建立链表的长度：");scanf("%d",&n);head=(Linklist)malloc(sizeof(Lnode));head->next=NULL;creatlist_L(head,n);printf("\n********输出单链表中元素*****\n");traverlist_L(head);}2、单链表的查找创建一个单链表，编写单链表的查找函数，实现单链表的查找。

int Getelem(Linklist L,int i,Elemtype &e){int j;Linklist p;p=L->next;j=1;while(p&&j<i){p=p->next;++j;}if (!p||j>i)return NULL;e=p->data;return e;}//按序查找void Getelem(Linklist L,Elemtype e){Linklist p;p=L->next;while(p && p->data!=e){p=p->next;printf("\n查找成功！\n");}if (!p)printf("\n查找失败！\n");}//按值查找3、单链表的删除创建一个单链表，编写函数实现单链表的删除操作。

void Listdelete(Linklist &L,int i){Linklist p,q;p=L;int j=0;while((p->next)&&(j<i-1)){p=p->next;++j;}if(!(p->next)||(j<i-1))printf("删除位置不合理，操作失败！");else{q=p->next;p->next=q->next;delete q;printf("删除成功！");}}//删除指定位置的元素4、有序单链表的合并建立两个带头结点的有序单链表La，Lb（单调递增），利用La，Lb的结点空间，将La和Lb合并成一个按元素值递增的有序单链表Lc。

参考代码：#include <Linklist.h>void mergelist_L(Linklist La,Linklist Lb,Linklist &Lc){InList(Lc);int i,j,k,La_len,Lb_len,e,ai,bj;i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while((i<=La_len)&&(j<=Lb_len)){ai=GetElem(La,i,ai);bj=GetElem(Lb,j,bj);if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}while(i<=La_len){ai=GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){bj=GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}void main(){Linklist La,Lb,Lc;int n1,n2;La=(Linklist)malloc(sizeof(Lnode));La->next=NULL;printf("******两个单链表的合并操作******\n");printf("\n请输入要建立的链表La的长度：");scanf("%d",&n1);creatlist_L(La,n1);printf("\n******输出链表La中元素******\n");traverlist_L(La);Lb=(Linklist)malloc(sizeof(Lnode));Lb->next=NULL;printf("******两个单链表的合并操作******\n");printf("\n请输入要建立的链表Lb的长度：");scanf("%d",&n2);creatlist_L(Lb,n2);printf("\n******输出链表Lb中元素******\n");traverlist_L(Lb);printf("\n******下面执行合并操作******\n");Lc=La;mergelist_L(La,Lb,Lc);printf("\n******输出由链表La和Lb归并所得新的链表Lc中的元素******\n");traverlist_L(Lc);}5、已知带头结点的单链表L中的结点是按整数值递增排列。

试写一个算法，将值为x的结点插入到表L中，使得L仍然有序。

分析算法的时间复杂度。

void Insert(Linklist L,int x){Linklist p,q;p=L->next;q=L;while(p&&p->data<x){q=p;p=p->next;}p=(Linklist)malloc(sizeof(Lnode));p->data=x;p->next=q->next;q->next=p;}6、线性表的合并有两个集合A 和B 分别用线性表LA 和LB 表示，即：线性表中的数据元素为集合中的成员。

现求一个新的集合A＝A∪B。

（线性表任选一种存储方式）void Union(Linklist &La,Linklist Lb){int i,La_len,Lb_len,e;La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){e=GetElem(Lb,i,e);Insert(La,e);}}实验总结：1.头插法创建单链表2.单链表的查找3.单链表的删除4.有序表中插入元素5.（4-5）有序链表的合并和两个集合的合并。