数据结构课程单链表实验报告

郑州轻工业学院

《数据结构》课程实验

实 验 报 告

题目： 单链表表的基本操作及c语言实现 专业： 信息管理与信息系统 班级： 11-01 姓名： *** 完成日期： 2013/5/23

郑州轻工业学院

数据结构实验报告

一、 试验内容

用c语言实现单链表的建立插入删除查找，合并等内容

二、试验目的

掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构，深入对链表链式结构的了解。

三．源程序代码

#include #include typedef int Elemtype; typedef int Status;

typedef struct node//定义存储节点 { int data;//数据域 struct node *next;//结构体指针

} *linklist,node;//结构体变量，结构体名称 linklist creat (int n)//创建单链表 { linklist head,r,p;//定义头指针r,p,指针 int x,i; head=(node *)malloc(sizeof(node));//生成头结点 r=head;//r指向头结点 printf(\"输入数字:\\n\"); for(i=n;i>0;i--)//for 循环用于生成第一个节点并读入数据 { scanf(\"%d\ p=(node *)malloc(sizeof(node)); p->data=x;//读入第一个节点的数据 r->next=p;//把第一个节点连在头结点的后面 r=p;//循环以便于生成第二个节点 }

r->next=0;//生成链表后的断开符 return head;//返回头指针 }

void output (linklist head)//输出链表 { linklist p; p=head->next;

郑州轻工业学院

数据结构实验报告

do { printf(\"%3d\ p=p->next; } while(p); printf(\"\\n\"); }

Status insert ( linklist &l,int i, Elemtype e)//插入操作 { int j=0; linklist p=l,s; while(jnext; ++j; } if(!p || j>i-1) return -1; else { s=(node *)malloc(sizeof(node)); s->data=e; s->next=p->next; p->next=s; return 1; } }

Status delect ( linklist &l,int i, Elemtype &e)//删除操作 { int j=0; linklist p=l,q;

while(jnext) { p=p->next; ++j; }

if(!p->next || j>i-1) return -1;

郑州轻工业学院

数据结构实验报告

else { q=p->next; p->next=q->next; e=q->data; free(q); return 1; } }

void combine(linklist la,linklist lb)//合并单链表 { node *pa,*pb,*pc; linklist lc; pa=la->next; pb=lb->next; lc=pc=la; while(pa && pb){ if(pa->data<=pb->data){ pc->next=pa; pc=pa; pa=pa->next; } else{pc->next=pb;pc=pb;pb=pb->next;} } pc->next=pa?pa:pb; free(lb); }

Status GetElem(linklist l,int i,Elemtype &e )//查找操作 { linklist p; int j; p=l->next; j=1; while(p && jnext; ++j; } if(!p || j>i) return -2; e=p->data;

郑州轻工业学院

数据结构实验报告

return e; }

void main() { linklist la,lb; int n; int i,j; Elemtype e; printf(\"请输入第一个链表:\\n\"); printf(\"输入链表元素的个数:\\n\"); scanf(\"%d\ la=creat(n); printf(\"输出链表:\\n\"); output(la); printf(\"请输入要查找元素的位置:\\n\"); scanf(\"%d\ j=GetElem(la,i,e); printf(\"所要查找的元素是%d\\n\ printf(\"请输入插入位置和元素:\\n\"); scanf(\"%d%d\ insert(la,i,e); printf(\"插入后的链表:\\n\"); output(la);

printf(\"请输入要删除的位置:\\n\"); scanf(\"%d\delect(la,i,e);

printf(\"删除的那个元素是:%d\\n\printf(\"输出删除后的顺序表:\\n\"); output(la); printf(\"请输入第一个非递减链表:\\n\"); printf(\"输入链表元素的个数:\\n\"); scanf(\"%d\ la=creat(n); printf(\"输出链表:\\n\"); output(la); printf(\"请输入第二个非递减链表:\\n\");

郑州轻工业学院

数据结构实验报告

printf(\"输入链表元素的个数:\\n\"); scanf(\"%d\ lb=creat(n); printf(\"输出链表:\\n\"); output(lb); combine(la,lb);

printf(\"输出合并后的链表:\\n\"); output(la); }

运行结果如下：

郑州轻工业学院

数据结构实验报告

六、结果分析与思考

关于单链表的建立要比顺序表难懂，单链表的建立有头插法和尾插法两种，我选用的是尾插法，尾插法较之头插法更为简单和使用，一定要熟练使用。

郑州轻工业学院