一、实验目的
（1）掌握线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现；
（2）掌握线性表的各种操作（建立、插入、删除等）的实现算法；
二、实验仪器及环境：
PC计算机 7操作系统 .05
三、实验内容及结果（按照具体实验题目，按照如下格式书写）
1．随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。
2．遍历单向链表。
3．把单向链表中元素逆置（不允许申请新的结点空间）。
4.在单向链表中删除所有的偶数元素结点。
5．编写在非递减有序链表中插入一个元素使链表元素仍有序的函数数据结构实验报告链表，并利用该函数建立一个非递减有序单向链表。
6．利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。
7．利用算法5建立两个非递减有序单向链表数据结构实验报告链表，然后合并成一个非递减链表。
8．利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。
10．在主函数中设计一个简单的菜单数据结构实验报告链表 数据结构实验报告 链表，分别调试上述算法。
#include
#include
#include
#include
#include
#define MAXASIZE 100
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LNode,*LinkList;
using namespace std;
//1．随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。
LinkList creat()//创建一个带头节点的链表
{
printf("Please Input a List of Numbers: ");
LinkList p1,p2,head;
head=(LNode *)malloc(sizeof(LNode));
head->next=NULL;
p1=head;
ElemType x;
while(scanf("%d",&x)!=-1)
{
p2=(LNode *)malloc(sizeof(LNode));
p2->data=x;
p1->next=p2;
p1=p2;
}
p1->next=NULL;
return head;
}
//2．遍历单向链表。
void display(LinkList head)//遍历
{
LinkList p;
p=head->next;
printf("HEAD -> ");
<p>![数据结构实验报告链表_c语言列表结构链表_递归逆序输出链表数据][1]
while(p!=NULL)
{
printf("%d -> ",p->data);
p=p->next;
}
printf("TAIL\n");
}
void InsertList(LinkList head,ElemType x)//插入x
{
//printf("Please Input the Location and the Number which You Want to Insert: ");
LinkList l=head,p1,p2;
l=head;
bool flag=0;
if (l->next->data>x)//队首
{
p2=(LNode *)malloc(sizeof(LNode));
p2->data=x;
p2->next=l->next;
l->next=p2;
return;
}
while(l->next)
{
l=l->next;
p1=l;
//flag=0;//flag=0表示尚未插入
if (p1->datanext->data>=x)//插入在p1与p1->next中间
{
p2=(LNode *)malloc(sizeof(LNode));
p2->data=x;
p2->next=p1->next;
p1->next=p2;
flag=1;//已插入
break;
}
}
if (!flag)
{
p2=(LNode *)malloc(sizeof(LNode));
p2->data=x;
p2->next=NULL;
l->next=p2;
}
}
LinkList CreateNew(LinkList head)//构建非递减有序单向链表；
{
LinkList l,p1,p2=head;
l=(LNode *)malloc(sizeof(LNode));
l->next=NULL;
ElemType x;
p2=head->next;
while(p2)
{
x=p2->data;
p1=(LNode *)malloc(sizeof(LNode));
p1->data=x;
p1->next=l->next;
l->next=p1;
p2=p2->next;
}
return l;
}
//3．把单向链表中元素逆置（不允许申请新的结点空间）。
LinkList ReverseList(LinkList head)//逆置链表
{
LinkList p1,p2;
if (head->next==NULL) return head;
p1=head->next;
head->next=NULL;
while(p1)
{
p2=p1;
p1=p1->next;
p2->next=head->next;
head->next=p2;
}
return head;
}
ElemType LengthList(LinkList head)
{
LinkList p;
p=head->next;
int num=0;
while(p!=NULL)
{
p=p->next;
num++;
}
return num;
}
//5．编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。
LinkList SortList(LinkList head)//排序为非减链表
{
LinkList p;
if (head->next == NULL) return head;
int n=LengthList(head);
for(int i=1; inext;
for(int j=0; jdata > p->next->data)
{
ElemType tmp=p->data;
p->data=p->next->data;
p->next->data=tmp;
}
p=p->next;
}
}
return head;
  ![递归逆序输出链表数据_c语言列表结构链表_数据结构实验报告链表][2]
}
//4.在单向链表中删除所有的偶数元素结点。
LinkList DeleteEven(LinkList head)//删除偶数元素节点
{
LinkList p1,p2;
p1=head;
p2=p1->next;
while(p1->next)
{
if ((p2->data & 1)==0)
{
p1->next=p2->next;
free(p2);
p2=p1->next;
}
else
{
p2=p2->next;
p1=p1->next;
}
}
return head;
}
//7．利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表。
void MergeList1(LinkList &head,LinkList &l)//合并两个链表，递增排列
{
LinkList p=head;
while(p->next!=NULL)
{
p=p->next;
InsertList(l,p->data);
}
CreateNew(l);
}
//6．利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。
void MergeList2(LinkList &head,LinkList &l)//合并两个链表，递减排列
{
LinkList p=head;
while(p->next!=NULL)
{
p=p->next;
InsertList(l,p->data);
}
CreateNew(l);
ReverseList(l);
}
//8．利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）
void divide(LinkList head)//分为左右两部分，左边的元素为奇数，右边所有元素为偶数
{
LinkList L=head,p,q,r,s;
r=L;
p=L->next;
int j=0;
while(p!=NULL)
  ![数据结构实验报告链表_递归逆序输出链表数据_c语言列表结构链表][3]
{
s=p;//s为最后一个节点；
p=p->next;
j++;
}
r=L;
p=L->next;
q=p->next;
for(int i=0; idata)%2==0)
{
r->next=q;
p->next=NULL;
s->next=p;
s=p;
p=q;
q=p->next;
}
else
{
r=p;
p=q;
q=p->next;
}
}
}
void depart(LinkList head,LinkList l)
{
LinkList q=head,p;
q=q->next;
while(q->data%2==1)
{
ElemType x;
x=q->data;
p=(LinkList)malloc(sizeof(LNode));
p->data=x;
p->next=l->next;
l->next=p;
head->next=q->next;
free(q);
q=head->next;
}
}
void freelist(LinkList head)//释放链表空间
{
LinkList l=head;
LinkList q;
while(l)
{
q=l;
l=l->next;
free(q);
}
}
void swap(LinkList head)//交换值的排序
{
LinkList l=head,p,q;
  ![c语言列表结构链表_递归逆序输出链表数据_数据结构实验报告链表][4]
p=l->next;
int j=0;
while(p)
{
p=p->next;
j++;
}
for(int i=0; inext;
for(int k=i; knext;
if(p->data > q->data)
{
int tmp;
tmp=p->data;
p->data=q->data;
q->data=tmp;
}
}
}
}
int main()
{
LinkList head=creat();
//显示
display(head);
//排序
LinkList head2=SortList(head);
display(head2);
//合并链表1
MergeList1(head,head2);
//合并链表2
MergeList2(head,head2);
display(head2);
//链表插入元素
int tt;
scanf("%d",&tt);
InsertList(head,tt);
display(head);
//逆置链表
ReverseList(head);
display(head);
//删除偶数元素
DeleteEven(head);
display(head);
//按奇偶分解链表
divide(head);
LinkList l;
l=(LinkList)malloc(sizeof(LNode));
l->next=NULL;
depart(head,l);
display(head);
display(l);
return 0;
}</p>
文章来源:https://blog.csdn.net/wuxuanyi27/article/details/51174330