5、 使用说明及测试结果
程序执行后显示以下内容： 创建单链表； 选择以下功能：1插入，2删除，3查找，4求表长； 选择各自功能时执行各自的程序； 结束程序；
六、 源程序（带注释）
#include <stdio.h> #include <stdlib.h> #define listType int #define placeholder d // 此单链表的头结点不用来存储数据。 typedef struct _NODE{
数据结构课程实验报告
实验题ቤተ መጻሕፍቲ ባይዱ:单链表的基本算法
班级 通信143 姓名 刘峻霖 星期四 学号 2014101108 日期 2015年6月18日
1、 需求分析
1． 程序的功能： 本程序主要你完成单链表的生成，实现在任意位置的插入、删除， 链表的查找和求表长等功能。 2． 输入输出的要求： 当选择删除功能时，从键盘读入欲删除的元素位置，按指定位置删 除；当选择插入功能时，从键盘读入新元素值和被插入位置，在指 定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返 回其位置序号；当选择求表长功能时，返回该单链表表长的数值。 每种操作结束后，都能在屏幕上打印出此时单链表元素的遍历结果 3． 测试数据： A：插入操作中依次输入数据，如输入11,12,13,14,15,16，生成一个 单链表。 B：查找操作中依次输入12,15,22，返回3个元素在单链表中的位置。 C：删除操作中依次输入2,5，删除位于2和5的元素。
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;
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 {
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;
3、 详细设计
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()
2、 概要设计
1． 本程序所用的抽象数据类型的定义 typedef struct _NODE{ listType data; struct _NODE *next; } node; 2． 主程序的流程及各程序模块之间的层次关系。 主程序流程如下： 申请空间创建一个单链表 初始化单链表 为用户提供插入、删除、查找、结束四个选项 用户选择时执行各自模块的功能（各模块呈并列关系） 结束程序
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;
4、 调试分析
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）