数据结构实验 链表

实验名称：链表

班级： 学号___________姓名： 报告日期：

一、实验目的及要求

1. 掌握单链表的存储结构形式及其描述。

2. 掌握单链表的建立、查找、插入和删除操作。

二、实验内容

1. 编写函数，实现随机产生或键盘输入一组元素，建立一个带头结点的单链表（无序）。

2. 编写函数，实现遍历单链表。

3. 编写函数，实现把单向链表中元素逆置（不允许申请新的结点空间）。

4. 编写函数，建立一个非递减有序单链表。

5. 编写函数，利用以上算法，建立两个非递减有序单链表，然后合并成一个非递减链表。

6. 编写函数，在非递减有序单链表中插入一个元素使链表仍然有序。

7. 编写函数，实现在非递减有序链表中删除值为x的结点。

8. 编写一个主函数，在主函数中设计一个简单的菜单，分别调试上述算法。

三、实验结果

四、实验总结：

这次实验使我在已经掌握单链表的存储结构，单链表的建立、查找、插入和删除操作的思想的基础上，可以对其利用C语言进行编程的实现，不仅对单链表的有关内容有了更深的理解，同时也对C语言编程的学习有了很大的进步。期间也遇到不少麻烦，；例如在编好程序后，编译运行时出现很多错误，但是在同学和网络的帮助下，将其成功解决。此外，需要注意的就是在用C语言进行编程时，一定要细心，注意基础知识的积累。同时算法思想也很重要。

源代码：

#include

#include

typedef int ElemType;

typedef struct LNode

{

ElemType data;

struct LNode *next;

}LNode,*Linklist;

void Createlist(Linklist &L)

{

Linklist p,s;

ElemType x;

L=(Linklist)malloc(sizeof(LNode));

L->next=NULL;

p=L;

scanf(\"%d\

while(x)

{

s=(Linklist)malloc(sizeof(LNode));

s->data=x;

s->next=NULL;

p->next=s;

p=s;

scanf(\"%d\

}

void printlist(Linklist &L)

{

Linklist p;

p=L;

while(p->next!=NULL){

p=p->next;

printf(\"%d \

printf(\"\\n\");

}

void nizhi(Linklist &L)

{

Linklist p,s;

p=L->next;

L->next=NULL;

while(p)

{

s=p;

p=p->next;

s->next=L->next;

L->next=s;}

}

void charu(Linklist &L,ElemType x)

{

Linklist p,s;

s=(Linklist)malloc(sizeof(LNode));

s->data=x;

p=L;

while(p->next&&p->next->data<=x)

p=p->next;

s->next=p->next;

p->next=s;

}

void CreatSort(Linklist &L)

{

ElemType x;

L=(Linklist)malloc(sizeof(LNode));

L->next=NULL;

printf(\"建立非递减有序单链表，随机输入一组数据并以0结束：\\n\");

scanf(\"%d\

while(x)

{

charu(L,x);

scanf(\"%d\

}

void merger(Linklist La,Linklist Lb,Linklist &Lc)

{

Linklist p,q,s,rear;

p=La->next;

q=Lb->next;

Lc=rear=La;

free(Lb);

while(p&&q){

if(p->datadata) {s=p;p=p->next;}

else {s=q;q=q->next;}

rear->next=s;

rear=rear->next;}

if(p) rear->next=p;else rear->next=q;

}

void shanchu(Linklist &L,ElemType x)

{Linklist p,q;

p=L;

q=L->next;

while(q&&q->data!=x){

p=q;

q=q->next;}

if(!q) printf(\"\\nnot deleted\");

else {p->next=q->next;free(q);}

}

void main()

{

Linklist La,Lb,Lc;

ElemType x;

int n;

printf(\"1.随机盘输入一组元素，建立无序的单链表，以0结束\\n\");

printf(\"2.以输出的形式遍历单链表\\n\");

printf(\"3.把单向链表中元素逆置\\n\");

printf(\"4.建立一个非递减有序单链表\\n\");

printf(\"5.建立两个非递减有序单链表，然后合并成一个非递减链表\\n\");

printf(\"6.在非递减有序单链表中插入一个元素\\n\");

printf(\"7.删除指定的元素\\n\");

while(1){

printf(\"请选择:\");

scanf(\"%d\

switch(n)

{case 1:printf(\"请随机输入一组元素以建立单链表，以0结束:\");

Createlist(La);break;

case 2:printf(\"单链表以输出形式遍历为:\");

printlist(La);break;

case 3:nizhi(La);

printf(\"已建立单链表中的元素逆置为：\");

printlist(La);break;

case 4:

CreatSort(La);

printf(\"所建非递减有序单链表为:\");

printlist(La);break;

case 5:

CreatSort(La);

CreatSort(Lb);

merger(La,Lb,Lc);

printf(\"合并后的单链表为:\");

printlist(Lc);break;

case 6:

CreatSort(La);

printf(\"新建非递减有序单链表为:\");

printlist(La);

printf(\"请输入要插入单链表的元素x:\");

scanf(\"%d\

charu(La,x);

printlist(La);break;

case 7:

CreatSort(La);

printf(\"新建非递减有序单链表为:\");

printlist(La);

printf(\"请输入要删除的元素x:\");

scanf(\"%d\

shanchu(La,x);

printlist(La);break;

default :printf(\"输入有误，请重新选择！\\n\");

}

}

}