算法与数据结构 单链表

福建工程学院计算机与信息科学系

实验报告

2011 – 2012 学年第 一 学期 任课老师： 蒋建辉 课程名称 算法与数据结构 实验题目 班级 计算机1001 座号 3100301114 姓名 张扬文 实验开始日期：2011/9/27 报告提交日期：2011/10/7 单链表 实验时间 实验目的、要求 一、实验目的 1．熟悉单链表的存储结构； 2．熟悉单链表的操作； 3．熟悉单链表的应用。 二、实验内容 1．实现带头结点的单链表的创建。 2．已知带头结点的单链表L中的结点是按整数值递增排列，设计算法并实现将值为x的结点插入到表L中，使得L仍然有序。 3．实现输出单链表中各结点的值。 （二）（选做） 1．两个已排序（升序）的单链表，合并成一个链表而不改变其排序性； 实验设计内容 实验内容： 1． 设计数据结构 /*单链表*/ typedef int elemtype; typedef struct node { elemtype data; struct node *next; }LinkNode,*LinkList; 2．根据实验内容的描述设计算法 2.1 创建列表 LinkList CreatHead_LinkList() { LinkList L; LinkNode *s,*p; int x; L=(LinkNode *)malloc(sizeof(LinkNode)); //申请空间 L->next=NULL; p=L; printf(\请从小到大输入你要输入的数据（－1结束）：\\n\ scanf(\ while(x!=-1) {

1

s=(LinkNode*)malloc(sizeof(LinkNode)); s->data=x; s->next = NULL; p->next =s; p=s; //指针向后移 scanf(\ } return L; } 2.2 插入函数 LinkList Ins_LinkList(LinkList L, elemtype item) { LinkNode *q,*t,*p; t=(LinkNode*)malloc(sizeof(LinkNode)); t->data=item; if (L->next == NULL) //如果列表为空，则输出 {printf(\列表为空！！\\n\ else { q=L; p=L->next; while(p!=NULL) //若头指针不为空 if(p->data < item) //输入数据大于头指针 { q=p; p=p->next; //指针向下移 } else break; } if(p==NULL) { printf(\节点不存在！\\n\ return 0; } else { q->next=t; t->next=p; return L; } } 2.3 输出函数

2

void PrnList(LinkList L) { LinkList p; p=L->next; printf(\打印数据如下：\\n\ while(p) { printf(\ p=p->next; } printf(\} 2.4 菜单函数 void menu() { printf(\顺序表例程--------------\\n\ printf(\退出\\n\ printf(\从小到大输入数据\\n\ printf(\插入元素\\n\ printf(\打印数据\\n\} 2.5 主函数 void main() { printf(\学号：3100301114 张扬文 计算机1001\\n\ elemtype x; LinkList L; do{ menu(); //调用菜单函数 printf(\输入你的选择：\ scanf(\ switch(x) { case 0: break; case 1: L=CreatHead_LinkList(); break; case 2: { printf(\请你要插入的数：\\n\ scanf(\ Ins_LinkList(L,x); } break; case 3: PrnList(L); break; } }while(x!=0); //当输入数据不为0；

3

return 1; } 2.6 选做题 void MergeList(SeqList *A, SeqList *B, SeqList *C) { int i=0, j=0, k=0; while(i <= A->last && j <= B->last) //当两列表都不为空时，执行以下循环 { if(A->data[i] < B->data[j]) //比较两数的大小，将小的赋值给C { C->data[k++]=A->data[i++]; } else C->data[k++]=B->data[j++]; } while(i <= A->last) //当B为空时，将A全赋值给C C->data[k++]=A->data[i++]; while(j <= B->last) //当A为空时，将B全赋值给C C->data[k++]=B->data[j++]; C->last=A->last+B->last+1; //C的长度等于A+B for(i=0;i < C->last;i++) { if(C->data[i]==C->data[i+1]) //当两个数相等时 { j=i; for(j=i;jlast;j++) C->data[j]=C->data[j+1]; //将后面的数向前移一 C->last--; i--; } } } 将选做题调试后的结果为： 4