实验3

《数据结构与算法》实验报告

实验题目：单链表基本操作

班级：软工103班 姓名：吴昊骅 学号：2010081088 完成日期：2011年12月1日 一、实验目的：

1. 学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。

2. 掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。 二、实验内容：

1．编写程序完成单链表的下列基本操作： (1)初始化单链表La。

(2)在La中插入一个新结点。 (3)删除La中的某一个结点。

(4)在La中查找某结点并返回其位置。 (5)打印输出La中的结点元素值。

2 .构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、Lb合并成一个有序单链表Lc。

合并思想是：程序需要3个指针：pa、pb、pc，其中pa，pb分别指向La表与Lb表中当前待比较插入的结点，pc 指向Lc表中当前最后一个结点。依次扫描La和Lb中的元素，比较当前元素的值，将较小者链接到*pc之后，如此重复直到La或Lb结束为止，再将另一个链表余下的内容链接到pc所指的结点之后。

3.构造一个单链表L，其头结点指针 为head，编写程序实现将L逆置。（即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。） 三、设计分析：

（说明：依据实验内容分别说明实验程序中用到的数据类型的定义、主程序的流程以及每个操作（成员函数）的伪码算法）

四、实验步骤：

（只要求详细写出实验内容3的运行调试步骤） 五、本次实验的体会和收获

（说明：主要对运行情况作出分析，说明调试过程中遇到的主要问题及如何解决的，对每个具体算法写出时间复杂度分析和讨论，还可以提出对流程设计和算法编码的改进设想。如果程序未能通过，应当分析原因。）

六、附件：带注释的源程序 1、代码：

#include #include #include

typedef int ElemType;

typedef struct Node {

ElemType data; struct Node *next;

}LNode,*LinkList; //Lnode是结点类型名，LinkList是结点指针类型名

void InitList_L (LinkList &L,int n) //构造一个单链表 { int i; LinkList p, q; if (L != NULL) { printf(\"单链表已创建，请不要重复创建\\n\"); return; } L = (LinkList)malloc(sizeof(LNode)); //建立一个带头结点的单链表 if (L == NULL) //判断是否成功 { printf(\"头结点存储空间申请失败!\\n\"); exit(0); } L->data = 0; //初始化数据域 L->next = NULL; //初始化指针域 p = (LinkList)malloc(sizeof(LNode)); //生成新的结点 if (p == NULL) { printf(\"结点空间申请失败\\n\"); exit(0); } L->next = p; printf(\"请输入第1个结点的数据:\"); scanf(\"%d\ p->next = NULL; for (i = 1; i < n; i++) { q = (LinkList)malloc(sizeof(LNode)); //生成新的结点 if (q == NULL) { printf(\"结点空间申请失败\\n\"); exit(0); } p->next = q; //将新生成的结点连接在链表中 printf(\"请输入第%d个结点的数据:\

scanf(\"%d\从键盘读入数据 p = q; //滑动指针 } p->next = NULL; return ; }

int ListLength(LinkList L) //计算单链表的长度并返回其值 { int i; LinkList p; p = L; //p指向L的头结点 for (i = 0; p->next != NULL; i++) //将指针移动到链表尾部 { p = p->next; } return i; //返回长度 }

void ListInsert(LinkList &L, int i, ElemType e) //在第i个位置上插入元素e { int j; LinkList p, q; p = L; q = NULL; if (i < 1 || i > ListLength(L)) //判断要插入的位置是否越界 { printf(\"您输入的位置已经超出范围\\n\"); return; } for (j = 0; j < i - 1; j++) //让指针指向第i-1个元素 { p = p->next; } q = (LinkList)malloc(sizeof(LNode)); //申请一个新的空间 q->data = e; //为新申请的空间赋值 q->next = p->next; //记录线性表中原来的第i个位置的地址 p->next = q; //插入第i-1个结点的指针指向q return; }

void ListDelete(LinkList &L, int i, ElemType &e) //删除第i个结点并返回其数据e

{ LinkList p, q, r; int j; p = L; q = NULL; r = NULL; if (i < 1 || i > ListLength(L)) //判断要删除的位置是否越界 { printf(\"您输入的位置已经超出范围\\n\"); return; } for (j = 0; j < i - 1; j++) //将指针指向第i-1个结点 { p = p->next; } r = p->next; //r指向第i个结点（要删除的结点） e = r->data; //将要删除结点的数据返回 q = r->next; //q指向要删除结点的下一个结点 free(r); //释放要删除结点的空间（即删除该结点） p->next = q; //将原来的第i-1个结点的指针域指向删除结点后面的一个结点 return; }

void GetLocation(LinkList L, int &i, ElemType e) //在L中查找某结点并返回其位置 { LinkList p; int j; p = L; for (j = 0; p->next != NULL; j++) //若链表未结束，则继续查询 { p = p->next; //指针滑动 if (p->data == e) //检测结点数据是否和所要查的数据相同 { i = j; //将位置返回 return; //返回调用函数 } } }

void ListDisplay(LinkList L) //打印链表中所有的数据 { LinkList p;

int i = 1; p = L; //p指向头结点 while (p->next != NULL) //若p的下一个结点不为空则将p向后移并打印其数据 { p = p->next; printf(\"结点%d：%d \ if (i % 3 == 0) //每输出三个数据换行一次 { printf(\"\\n\"); } i++; } printf(\"\\n\"); }

void Menu() { printf(\"\\\单链表的下列基本操作\\n\"); printf(\"\\\1、创建单链表\\n\"); printf(\"\\\2、插入新结点\\n\"); printf(\"\\\3、删除结点\\n\"); printf(\"\\\4、查找数据\\n\"); printf(\"\\\5、打印单链表\\n\"); printf(\"\\\6、清屏\\n\"); printf(\"\\\7、退出程序\\n\"); }

int main(void) { LinkList L; int l, i, n; ElemType e; L = NULL; Menu(); while(1) { printf(\"\\n\\n请输入你要进行的项目:\"); scanf(\"%d\ switch (i) { case 1: printf(\"请输入你要创建链表的结点数：\");

scanf(\"%d\ InitList_L(L, n); printf(\"当前链表的长度为：%d\\n\ break; case 2: if (L == NULL) //判断单链表是否存在 { printf(\"链表不存在，请创建链表后再进行操作\\n\"); break; } printf(\"请输入你要插入的位置和数据:\"); scanf(\"%d %d\ ListInsert(L, i, e); break; case 3: if (L == NULL) //判断单链表是否存在 { printf(\"链表不存在，请创建链表后再进行操作\\n\"); break; } printf(\"请输入你要删除的结点的位置:\"); scanf(\"%d\ ListDelete(L, i, e); printf(\"您删除的数据为：%d\\n\ break; case 4: if (L == NULL) //判断单链表是否存在 { printf(\"链表不存在，请创建链表后再进行操作\\n\"); break; } printf(\"请输入你要查找的数据：\"); scanf(\"%d\ GetLocation(L, l, e); printf(\"您所查找的数据为链表中第%d个结点\\n\ break; case 5: if (L == NULL) //判断单链表是否存在 { printf(\"链表不存在，请创建链表后再进行操作\\n\"); break; } ListDisplay(L); break;

case 6: system(\"cls\"); Menu(); break; case 7: printf(\"感谢使用！\\n\"); exit(0); break; default: printf(\"您输入的信息有误，请重新输入\\n\"); } } return 0; }

2、代码：

#include #include #include

typedef int ElemType;

typedef struct Node {

ElemType data; struct Node *next;

}LNode,*LinkList; //Lnode是结点类型名，LinkList是结点指针类型名

int ListLength(LinkList L) //计算单链表的长度并返回其值 { int i; LinkList p; p = L; //p指向L的头结点 for (i = 0; p->next != NULL; i++) //将指针移动到链表尾部 { p = p->next; } return i; //返回长度 }

void Listsort(LinkList &L) //对已有链表排序 { LinkList T, p, q, r, t; //T为新链表的头结点，p为新链表的增加结

点，q为被排序链表的滑动指针，r为新链表的滑动指针，temp为比较的结点 int i, j, n, flag, temp; T = (LinkList)malloc(sizeof(LNode)); //新的链表头结点 T->data = 0; //对新链表初始化 T->next = NULL; //初始化地址 r = T; //新生成链表的滑动指针赋初值 q = L->next; for (j = 1; q; j++) //进行ListLength(L)趟排序 { temp = q->data; //取被排序链表的第一个结点的值 flag = 0; //初始化最大结点的坐标 for (i = 1; q; i++) //找到当前被排序链表中的最大值 { if (temp < q->data) //判断现在记录的数是否小于指针指向的数，如果小，则更新现在记录的数，并记录下标 { temp = q->data; flag = i; } q = q->next; //被排序链表的滑动指针向后移一位 } p = (LinkList)malloc(sizeof(LNode)); //用来链接新链表的结点 r->next = p; //将新生成的结点连在新链表里 r = r->next; //将新链表的滑动指针后移一位 r->next = NULL; //p->next = NULL; p->data = temp; //将刚才找到的最大值付给新的结点 q = L; //将被排序链表的滑动指针复位 for (n = 0; n < flag - 1; n++) //找到已经被排序的结点的前一个结点 { q = q->next; } t = q->next; //找到要删除的结点 q->next = t->next; //将要删的节点的后一个结点连在要删除结点的前一个结点上 free(t); //删除结点 q = L->next; //初始化被排序链表的滑动指针 } L = T; }

void InitList_L (LinkList &L,int n) //构造一个单链表 {

}

int i;

LinkList p, q;

if (L != NULL) { printf(\"单链表已创建，请不要重复创建\\n\"); return; }

L = (LinkList)malloc(sizeof(LNode)); //建立一个带头结点的单链表 if (L == NULL) //判断是否成功 { printf(\"头结点存储空间申请失败!\\n\"); exit(0); }

L->data = 0; //初始化数据域 L->next = NULL; //初始化指针域 p = (LinkList)malloc(sizeof(LNode)); //生成新的结点 if (p == NULL) { printf(\"结点空间申请失败\\n\"); exit(0); }

L->next = p;

printf(\"请输入第1个结点的数据:\"); scanf(\"%d\p->next = NULL; for (i = 1; i < n; i++) { q = (LinkList)malloc(sizeof(LNode)); //生成新的结点 if (q == NULL) { printf(\"结点空间申请失败\\n\"); exit(0); } p->next = q; //将新生成的结点连接在链表中 printf(\"请输入第%d个结点的数据:\ scanf(\"%d\从键盘读入数据 p = q; //滑动指针 }

p->next = NULL; Listsort(L); //调用排序函数 return ;

void MergerList(LinkList La, LinkList Lb, LinkList &Lc) //合并La、Lb { LinkList pa, pb, pc, pct; pa = La->next; pb = Lb->next; Lc = (LinkList)malloc(sizeof(LNode)); //建立一个带头结点的单链表 if (Lc == NULL) //判断是否成功 { printf(\"头结点存储空间申请失败!\\n\"); exit(0); } Lc->data = 0; //初始化数据域 Lc->next = NULL; //初始化指针域 pc = Lc; while (pa != NULL && pb != NULL) { if (pa->data > pb->data) //如果pa>pb,先插入pb再插入pa { pct = (LinkList)malloc(sizeof(LNode)); pct->data = pb->data; pc->next = pct; pc = pc->next; pct = (LinkList)malloc(sizeof(LNode)); pct->data = pa->data; pc->next = pct; pc = pc->next; } else //否则，先插入pa再插入pb { pct = (LinkList)malloc(sizeof(LNode)); pct->data = pa->data; pc->next = pct; pc = pc->next; pct = (LinkList)malloc(sizeof(LNode)); pct->data = pb->data; pc->next = pct; pc = pc->next; } pa = pa->next; //pa后移 pb = pb->next; //pb后移 } if (pa == NULL) //如果pa已经结束，则将pb的值逐个放入pc中 {

while (pb != NULL) { pct = (LinkList)malloc(sizeof(LNode)); pct->data = pb->data; pc->next = pct; pc = pc->next; pb = pb->next; } } else //否则将pa的值逐个放入pc中 { while (pa != NULL) { pct = (LinkList)malloc(sizeof(LNode)); pct->data = pa->data; pc->next = pct; pc = pc->next; pa = pa->next; } } pc->next = NULL; Listsort(Lc); printf(\"La、Lb已经并入Lc\\n\"); }

void ListDisplay(LinkList L) //打印链表中所有的数据 { LinkList p; int i = 1; p = L; //p指向头结点 while (p->next != NULL) //若p的下一个结点不为空则将p向后移并打印其数据 { p = p->next; printf(\"结点%d：%d \ if (i % 3 == 0) //每输出三个数据换行一次 { printf(\"\\n\"); } i++; } printf(\"\\n\"); }

void Menu() { printf(\"\\\单链表的下列基本操作\\n\"); printf(\"\\\1、创建单链表La\\n\"); printf(\"\\\2、创建单链表Lb\\n\"); printf(\"\\\3、合并La、Lb\\n\"); printf(\"\\\4、打印单链表La\\n\"); printf(\"\\\5、打印单链表Lb\\n\"); printf(\"\\\6、打印单链表Lc\\n\"); printf(\"\\\7、清屏\\n\"); printf(\"\\\8、退出程序\\n\"); }

int main(void) { LinkList La, Lb, Lc; int i, n; La = NULL; Lb = NULL; Lc = NULL; Menu(); while(1) { printf(\"\\n\\n请输入你要进行的项目:\"); scanf(\"%d\ switch (i) { case 1: printf(\"请输入你要创建链表La的结点数：\"); scanf(\"%d\ InitList_L(La, n); printf(\"La链表的长度为：%d\\n\ break; case 2: printf(\"请输入你要创建链表Lb的结点数：\"); scanf(\"%d\ InitList_L(Lb, n); printf(\"Lb链表的长度为：%d\\n\ break; case 3: if (La == NULL) //判断单链表是否存在 { printf(\"链表La不存在，请创建链表后再进行操作\\n\");

break; } if (Lb == NULL) //判断单链表是否存在 { printf(\"链表Lb不存在，请创建链表后再进行操作\\n\"); break; } MergerList(La, Lb, Lc); break; case 4: if (La == NULL) //判断单链表是否存在 { printf(\"链表La不存在，请创建链表后再进行操作\\n\"); break; } printf(\"La链表为：\"); ListDisplay(La); break; case 5: if (Lb == NULL) //判断单链表是否存在 { printf(\"链表Lb不存在，请创建链表后再进行操作\\n\"); break; } ListDisplay(Lb); break; case 6: if (Lc == NULL) //判断单链表是否存在 { printf(\"链表Lc不存在，请创建链表后再进行操作\\n\"); break; } ListDisplay(Lc); break; case 7: system(\"cls\"); Menu(); break; case 8: printf(\"感谢使用！\\n\"); exit(0); break; default: printf(\"您输入的信息有误，请重新输入\\n\");

}

} }

return 0;