数据结构实验报告

题 目：单链表

院系名称：

专业名称：班 级：

学生姓名：

学号（8位）：

指导教师： 陈 燕 设计起止时间：20xx年10月29日~20xx年11月04日

一. 题目要求

编写一个单链表实现单链表的各种运算功能

二．概要设计

1．功能模块的调用关系图

2．各个模块详细的功能描述。

主函数main()

初始化单链表函数InitList_L

显示单链表内容函数DispList_L

插入元素函数ListInsert_L

删除元素函数ListDelete_L

查找元素函数LocateList_L

创建链表函数CreateList_L

链表元素长度函数ListLength_L

三．详细设计（主要函数的程序流程图）

四．测试数据及运行结果

1．正常测试数据和运行结果

2．异常测试数据及运行结果

五．调试情况，设计技巧及体会

1．改进方案

刚开始调试的时候老出现错误，经过不断看书，和同学讨论，不断改进自己的代码，虽然成功了，但是功能并不是很全面，进过改进，才改成功。

2．体会

熟能生巧，只有将单链表相关知识弄懂才能熟练的运用，对于代码出错，绝对不能急躁，要有耐心才能有清醒的头脑，将代码改好。

六．代码

#include <stdio.h>

#include <stdlib.h>

#define n 10

#define null 0

typedef struct node{

int data;

struct node *next;

}node;

node* CreatLink(int a[]){

node *q,*p,*h;

int i;

for(i=0;i<n;i++){

p=(node*)malloc(sizeof(node)); p->data=a[i];

if(!i)

h=p;

else

q->next=p;

q=p;

}

q->next=null;

return h;

}

void DispLink(node *h){

node *p;

int sum=0;

p=h;

while(p){

printf("%d\t",p->data);

p=p->next;

sum+=1;

if(!(sum%5))

printf("\n");

}

printf("\n");

}

node* DeleteLink(node *h,int x){

node *q,*p;

int sum=1;

p=h;

if(!(h->data-x)){

h=p->next;

printf("待删除结点位置为头结点！\n"); free(p);

return h;

}

while(1){

q=p;

p=p->next;

sum+=1;

if(!(p->data-x)){

q->next=p->next;

printf("待删除结点位置为第%d个结点\n",sum); free(p);

break;

}

if(!(sum-n)){

printf("未找到可删除结点\n");

break;

}

}

return h;

}

node* InsertLink(node *h,int ins,int x){

node *q,*p;

int k=0;

q=h;

p=(node *)malloc(sizeof(node));

p->data=x;

if(!(k-ins)){

p->next=h;

h=p;

printf("待插结点位置位于头节点之前\n");

return h;

}

while(1){

q=q->next;

k=k+1;

if(!(k+1-ins)){

p->next=q->next;

q->next=p;

printf("待插入结点位置位于第%d个结点之后\n",ins); break;

}

if(ins<0||ins>k+1){

printf("输入的待插入结点位置不正确\n"); break;

}

}

return h;

}

int main(){

int i,x,ins;

int a[n]={1,2,3,4,5,6,7,8,9,10};

node *head;

head=CreatLink(a);

} DispLink(head); printf("请输入需要删除的结点值x="); scanf("%d",&x); head=DeleteLink(head,x); DispLink(head); printf("请输入待插入结点x="); scanf("%d",&x); printf("请输入插入结点位置ins="); scanf("%d",&ins); head=InsertLink(head,ins,x); DispLink(head); return 0;

 

第二篇：数据结构课程单链表实验报告

郑州轻工业学院

《数据结构》课程实验

实验报告

题目：       单链表表的基本操作及c语言实现    

专业：         信息管理与信息系统     

班级：               11-01                  

姓名：            高博文                         

完成日期：         2013/5/23             

一、  试验内容

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

二、试验目的

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

三．源程序代码

#include<stdio.h>

#include<stdlib.h>

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",&x);

              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->data);

              p=p->next;

       }

       while(p);

       printf("\n");

}

Status insert ( linklist &l,int i, Elemtype e)//插入操作

{

       int j=0;

linklist p=l,s;

       while(j<i-1 && p)

       {

              p=p->next;

              ++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(j<i-1 && p->next)

{

       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 && j<i)

        {

               p=p->next;

               ++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",&n);

       la=creat(n);

       printf("输出链表:\n");

       output(la);

       printf("请输入要查找元素的位置:\n");

       scanf("%d",&i);

       j=GetElem(la,i,e);

       printf("所要查找的元素是%d\n",j);

       printf("请输入插入位置和元素:\n");

       scanf("%d%d",&i,&e);

       insert(la,i,e);

       printf("插入后的链表:\n");

       output(la);

printf("请输入要删除的位置:\n");

scanf("%d",&i);

delect(la,i,e);

printf("删除的那个元素是:%d\n",e);

printf("输出删除后的顺序表:\n");

output(la);

       printf("请输入第一个非递减链表:\n");

       printf("输入链表元素的个数:\n");

       scanf("%d",&n);

       la=creat(n);

       printf("输出链表:\n");

       output(la);

       printf("请输入第二个非递减链表:\n");

       printf("输入链表元素的个数:\n");

       scanf("%d",&n);

       lb=creat(n);

       printf("输出链表:\n");

       output(lb);

combine(la,lb);

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

       output(la);

}

运行结果如下：

六、结果分析与思考

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