数据结构课程实验报告

实验题目:单链表的基本算法

班级 通信143 姓名 刘峻霖 学号 2014101108 日期 20xx年6月18日星期四

一、 需求分析

1． 程序的功能：

本程序主要你完成单链表的生成，实现在任意位置的插入、删除，链表的查找和求表长等功能。

2． 输入输出的要求：

当选择删除功能时，从键盘读入欲删除的元素位置，按指定位置删除；当选择插入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号；当选择求表长功能时，返回该单链表表长的数值。每种操作结束后，都能在屏幕上打印出此时单链表元素的遍历结果

3． 测试数据：

A：插入操作中依次输入数据，如输入11,12,13,14,15,16，生成一个单链表。 B：查找操作中依次输入12,15,22，返回3个元素在单链表中的位置。

C：删除操作中依次输入2,5，删除位于2和5的元素。

二、 概要设计

1． 本程序所用的抽象数据类型的定义

typedef struct _NODE{

listType data;

struct _NODE *next;

} node;

2． 主程序的流程及各程序模块之间的层次关系。

主程序流程如下：

申请空间创建一个单链表

初始化单链表

为用户提供插入、删除、查找、结束四个选项

用户选择时执行各自模块的功能（各模块呈并列关系）

结束程序

三、 详细设计

1． 采用c语言定义相关的数据类型；

C语言中单链表的节点结构为：

typedef struct _NODE{

listType data;

struct _NODE *next;

} node;

2． 写出各模块的伪码算法；

插入：int insert_list (int pos, listType data)

删除：int delete_list(int pos)

查找：int find_list( listType data)

求表长：int length_list()

3． 画出函数的调用关系图。

提供选择：1-》插入，2-》删除，3-》查找，4-》求表长

执行1时调用函数init_list()，2时调用delete_list()，3时调用find_list ()，4时调用length_list()

四、 调试分析

1． 调试中遇到的问题及对问题的解决方法；

调用函数时没注意形参与实参的对应关系，导致主函数执行错误。要仔细注意程序中函

数名是否误用。

2． 算法的时间复杂度和空间复杂度。

插入运算的主要操作是比较，以寻找插入位置。比较的次数与插入位置i有关，在最好的情况下即i=1时比较的次数为0在最坏的情况即i=n+1时比较的次数为n次。平均次数为n/2。最坏的情况下插入运算的时间复杂度为O（n）。

删除运算的主要操作是比较，以寻找删除节点。比较的次数与删除位置i有关，在最好的情况下即i=1时比较的次数为0在最坏的情况即i=n时比较的次数为n-1次。平均次数为n/2。最坏的情况下删除运算的时间复杂度为O（n）

五、 使用说明及测试结果

程序执行后显示以下内容：

创建单链表；

选择以下功能：1插入，2删除，3查找，4求表长；

选择各自功能时执行各自的程序；

结束程序；

六、 源程序（带注释）

#include <stdio.h>

#include <stdlib.h>

#define listType int

#define placeholder d

// 此单链表的头结点不用来存储数据。

typedef struct _NODE{

listType data;

struct _NODE *next;

} node;

//-----global variable define------

node *head = NULL;

//--------function define-------

// 从有数据起，下标为1;

int length_list()

{

int i = 0;

node *p;

for (p=head; p->next; )

{

i++;

p=p->next;

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

}

return i;

}

void destroy_list( )

{

node *p = head;

while (p)

{

p=p->next;

free(head);

head = p;

}

}

void init_list( )

{

node *p;

char ch;

if (head == NULL)

head = (node *)malloc(sizeof(node)); else

{

destroy_list( );

head = NULL;

init_list( );

}

printf("Please input numbers :\n");

head->next = (node *)malloc(sizeof(node)); for (p=head->next; ; )

{

scanf("%d", &p->data);

if (ch=getchar() == '\n')

break;

p->next = (node *)malloc(sizeof(node)); p = p->next;

p->next = NULL;

}

printf("\nInput data is :");

for (p=head; p->next; )

{

p=p->next;

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

}

}

int insert_list (int pos, listType data)

{

int i;

node *p = head, *q;

for (i=0, p=head; i < pos-1 && p!=NULL; p=p->next, i++); if (p == NULL || i>pos-1)

{

printf("illegal position!");

return 0;

}

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

q->data = data;

q->next = p->next;

p->next = q;

return 1;

}

int delete_list(int pos)

{

int i;

node *p=head, *q;

for (i=0; p->next != NULL && i<pos-1; i++, p=p->next); if (i > pos-1 || p->next == NULL)

{

printf("illegal position!");

return 0;

}

q=p->next;

p->next = q->next;

free(q);

printf("Success////");

}

int find_list( listType data)

{

node *p = head;

int i = 0;

while (p)

{

if (p->data == data)

return i;

p=p->next;

i++;

}

return -1;

}

int main(void)

{

char choice;

int pos;

int length;

listType data;

node *p;

init_list( );

while (1)

{

printf("\n-----------------options------------------\n");

printf("------1, 插入数据-------------------------\n");

printf("------2, 删除数据-------------------------\n");

printf("------3, 数据查找-------------------------\n");

printf("------4, 求出长度-------------------------\n");

printf("------5, 结束程序-------------------------\n");

printf("------------------------------------------\n");

printf("------------------------------------------\n");

printf("请选择(1,2,3,4):");

scanf(" %c", &choice);

switch (choice)

{

case '1':

printf("\nPlease input the index that you want to insert :"); scanf("%d", &pos);

printf("\nPlease input the data that you want to insert :"); scanf("%d", &data);

insert_list(pos, data);

printf("\nChanged list is :");

for (p=head; p->next;)

{

p=p->next;

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

}

break;

case '2':

printf("\nPlease input the index of the data :"); scanf("%d", &pos);

delete_list(pos);

printf("\nChanged list is :");

for (p=head, p=p->next; p; p=p->next)

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

break;

case '3':

printf("\nPlease input the data which you want to find :"); scanf("%d", &data);

pos = find_list(data);

if (pos == -1)

{

printf("The data was not found!");

break;

}

printf("The data's index is %d", pos);

break;

case '4':

length = length_list();

printf("The linkedlist's length is %d.", length); break;

case '5':

goto endProgram;

}

}

endProgram :

return 0;

}

 

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

数据结构实验报告

题 目：单链表

院系名称：

专业名称：班 级：

学生姓名：

学号（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;