.
上海电力学院
计算机软件技术实验
Word 文档实验报告
实验题目： 单链表的实现及测试 院 系： 自动化工程学院 专业年级： 自动化2013级 学生姓名： 晁文涛 学号20131529
.
实验二 单链表的基本算法
一． 实验目的：
通过上机编程掌握
1．生成单链表的基本算法；
2． 在单链表上的插入、删除运算。
二． 实验要求：
1. 给出程序设计的基本思想、原理和算法描述。
2. 画出程序流程图；根据数据结构有关知识编出算法程序； 3. 源程序给出注释；
4. 保存和打印出程序的运行结果，并结合程序进行分析。
三． 实验内容：
1.
编写函数实现单链表的基本运算： (1) 单链表的生成
反向建立链表（头插法）
思想：首先生成头结点，形成一个空链表，然后在表中逐一读入新的结点，反复执行下列步骤： 使用malloc函数开辟新结点的存储单元； 将读入数据存放到新结点的数据域中； 将新结点插入到当前链表的表头上，直到读入结束标志为止。 流程图为：
开始
具体算法如下： NODE *creatlink1() //头插法 Head=(NODE*)malloc(sizeof(NODE));Head->=null;{NODE *head,*s;
int x;
head=(NODE*)malloc(sizeof(NODE)); //生成头结点
请输入x的值head->next=NULL; scanf(\"%d\ //读入第一个结点值
判断x！=0while(x!=0)
Y {s=(NODE*)malloc(sizeof(NODE));
s->data=x; s=(NODE*)malloc(sizeof(NODE)); s->next=head->next; head->next=s; //将新节点插入
S->data=x;到表头上 S->next=head->next;Head->next=s; scanf(\"%d\ }
结束return head;
}
Word 文档
.
正向建立单链表（尾插法）
思想：首先生成头结点，依次读入线性表的元素，从前往后依次将元素插入到当前链表的最后一个结点之后。 流程图为：
具体算法为：
开始NODE *creatlink2() //尾插法 {
Head=(NODE*)malloc(sizeof(NODE)); NODE *head,*p,*s; Head->=null; int num; head=(NODE*)malloc(sizeof(NODE));//
输入num的值生成头结点 scanf(\"%d\读入第一个结点值
P=head; p=head; //头指针等于尾指针 while (num!=0) //输入0作为结束符 {
判断num！=0 s=(NODE*)malloc(sizeof(NODE));//生
Y成新节点 s=(NODE*)malloc(si s->data=num; //新结点上填入输zeof(NODE));入值 p->next=s; //新结点*s插入到尾结S->data=num;p->next=s;点*p之后 Np=s; p=s; //尾指针指向新的表尾
输入sum的 scanf(\"%d\ //读入下一个值结点值 } p->next=NULL; //将尾结点的指针置空 P->next=null; return head; //返回单链表表头指针 }
结束
（2）单链表的插入
思想：首先要搜索单链表以找到指定插入结点的前趋结点p；然后改变链接，即只要是将待插入结点的指针域内容赋予p结点的指针域即可。
Word 文档
.
流程图为：
开始请输入要插入元素的结点i和要插入的数值xJ=i-1;P=get(head,j);判断p是否为NULL？NInsertafter(p,x)S=（NODE*）malloc(sizeof(NODE));输出“error”S->data=x;S->next=p->next;P->next=s;结束具体算法为：
NODE *get(NODE *head,int i) //查找第i个元素的位置 { NODE *p; int counter=1; p=head->next; while((p!=NULL)&&(counternext; counter++; } if((p!=NULL)&&(counter==i)) //找到，1<=i<=n return p; else return NULL; //找不到，i>n或i<=n }void insertafter(NODE *p,int x) { NODE *s; s=(NODE*)malloc(sizeof(NODE)); //修改i-1结点的尾指针
s->data=x;
s->next=p->next; p->next=s; }
void insert(NODE *head,int i,int x) //在i个位置插入x {
NODE *p; int j=i-1;
p=get(head,j); //调用查找函数找到i-1的结点位置 if(p==NULL) printf(\"error\"); else insertafter(p,x); //调用insertafter函数 }
(2) 单链表的删除
思想：首先要搜索单链表以找到指定删除结点的前趋结点p；然后改变链接，即只要是将待删除结点的指针域内容赋予p结点的指针域即可。
Word 文档
.
流程图为：
开始
具体算法为：
void delete(NODE *head,int i) //删除第i个位置的元素 请输入要删除元素的结{ 点i NODE *p,*s;
J=0； int j=0; P=head; p=head; while((p->next!=NULL)&&(j判断p->next是否不素的结点 为NULL且j小于i-1？ { Y p=p->next; P=p->next;J++; j++; N } if((p->next==NULL)||(j>i-1))判断p->next是否为 printf(\"i值不合法 \\n\"); YNULL或者j大于i-1？ else {
S=p->next;输出“i值不 s=p->next; //修改p->next，使指向s->next P->next=s->next;合法\\n”；Free(s); p->next=s->next; //删除s结点 free(s);
结束 }
}
2. 编写主函数测试单链表的各种基本运算：
(1) 生成一个至少包含有5个元素的单链表,元素值由计算机输入 (2) 在表中的第5个位置上插入元素”7” (3) 删除表中的第6个元素
(4) 显示(1)—(3)每一步的操作结果
源程序为：
#include #include typedef int datatype; typedef struct node { datatype data; struct node *next; }NODE;NODE *creatlink1() //头插法 {NODE *head,*s; int x;
head=(NODE*)malloc(sizeof(NODE)); //生成头结点 head->next=NULL; scanf(\"%d\ //读入第一个结点值 while(x!=0)
Word 文档
.
{s=(NODE*)malloc(sizeof(NODE)); s->data=x; s->next=head->next; head->next=s; //将新节点插入到表头上 scanf(\"%d\ }
return head; }
NODE *creatlink2() //尾插法 { NODE *head,*p,*s; int num; head=(NODE*)malloc(sizeof(NODE));//生成头结点 scanf(\"%d\ //读入第一个结点值 p=head; //头指针等于尾指针 while (num!=0) //输入0作为结束符 { s=(NODE*)malloc(sizeof(NODE));//生成新节点 s->data=num; //新结点上填入输入值 p->next=s; //新结点*s插入到尾结点*p之后 p=s; //尾指针指向新的表尾 scanf(\"%d\ //读入下一个结点值 } p->next=NULL; //将尾结点的指针置空 return head; //返回单链表表头指针 }
NODE *get(NODE *head,int i) //查找第i个元素的位置 { NODE *p; int counter=1; p=head->next; while((p!=NULL)&&(counternext; counter++; } if((p!=NULL)&&(counter==i)) //找到，1<=i<=n return p; else return NULL; //找不到，i>n或i<=n }void delete(NODE *head,int i) //删除第i个位置的元素 { NODE *p,*s;
Word 文档
.
int j=0; p=head; while((p->next!=NULL)&&(jnext; j++; } if((p->next==NULL)||(j>i-1)) printf(\"i值不合法 \\n\"); else { s=p->next; //修改p->next，使指向s->next p->next=s->next; //删除s结点 free(s); } }void insertafter(NODE *p,int x) { NODE *s; s=(NODE*)malloc(sizeof(NODE)); //修改i-1结点的尾指针 s->data=x; s->next=p->next; p->next=s; }
void insert(NODE *head,int i,int x) //在i个位置插入x { NODE *p; int j=i-1; p=get(head,j); //调用查找函数找到i-1的结点位置 if(p==NULL) printf(\"error\"); else insertafter(p,x); //调用insertafter函数 }
void print(NODE *head) //输出函数 {int x;
NODE *p; p=head; printf(\"\\n\"); p=p->next; while(p) {
x=p->data; printf(\"%4d\
Word 文档
.
p=p->next; } }
main() {
NODE *head;
printf(\"Please enter the link of elements:\\n\"); //head=creatlink1(); //头插法 head=creatlink2(); //尾插法 printf(\"The first step of is :\\n\"); print(head); printf(\"\\n\");
insert(head,5,7); //调用插入函数 printf(\"The second step of is :\\n\"); print(head); printf(\"\\n\");
delete(head,6); //调用删除函数 printf(\"The third step of is :\\n\"); print(head); printf(\"\\n\"); }
运算结果为：
四、实验心得
在这次实验中，我学到很多东西，加强了我的编程能力，加强了我对链表的了解，并且培养了我的思考能力。虽然在编写的过程的中遇到一些困难，但在老师和自己的努力下，得到了解决，也使自己加深了印象，以后要多加练习。
Word 文档
