《数据结构》
实验课讲义。
实验一线性表基本操作的实现。
1.1单链表的运算
1、建立单链表。
假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符''为输入条件结束标志符。动态地建立单链表的常用方法有如下两种：
1） 头插法建表。
算法思路。
从一个空表开始，重复读入数据，生成新结点，将读入数据存放在新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。
注意：该方法生成的链表的结点次序与输入顺序相反。
具体算法实现。
linklist creatlistf(void)
2） 尾插法建表
算法思路
从一个空表开始，重复读入数据，生成新结点，将读入数据存放在新结点的数据域中，然后将新结点插入到当前链表的表尾上，直到读入结束标志为止。
具体算法实现
linklist creatlistr(void)
2.插入运算。
1）思想方法。
插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。
具体步骤：
1）找到ai-1存储位置p
2）生成一个数据域为x的新结点*s
3）令结点*p的指针域指向新结点。
4）新结点的指针域指向结点ai。
2）具体算法实现。
void insertlist(linklist head,datatype x,int i)
//将值为x的新结点插入到带头结点的单链表head的第i个结点的位置上。
listnode *p;
p=getnode(head,i-1);/寻找第i-1个结点。
if (p==null)//i<1或i>n+1时插入位置i有错。
error("position error")；
s=(listnode *)malloc(sizeof(listnode));
s->data=x;s->next=p->next;p->next=s;
3）算法分析。
算法的时间主要耗费在查找操作getnode上，故时间复杂度亦为o(n)。
3.删除运算。
1）思想方法。
删除运算是将表的第i个结点删去。
具体步骤：
1）找到ai-1的存储位置p（因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中）
2）令p-＞next指向ai的直接后继结点（即把ai从链上摘下）
3）释放结点ai的空间，将其归还给"存储池"。
2）具体算法实现。
void deletelist(linklist head,int i)
2.3.3循环链表（circular linked list）
循环链表是一种首尾相接的链表。
1、循环链表。
1）单循环链表——在单链表中，将终端结点的指针域null改为指向表头结点或开始结点即可。
2）多重链的循环链表——将表中结点链在多个环上。
2、带头结点的单循环链表。
注意：判断空链表的条件是head==head->next;
3、仅设尾指针的单循环链表。
用尾指针rear表示的单循环链表对开始结点a1和终端结点an查找时间都是o(1)。而表的操作常常是在表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。带尾指针的单循环链表可见下图。
注意：判断空链表的条件为rear==rear->next;
4、循环链表的特点。
循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。
例】在链表上实现将两个线性表（a1，a2，…，an）和（b1，b2，…，bm）连接成一个线性表（a1，…，an，b1，…bm）的运算。
分析：若在单链表或头指针表示的单循环表上做这种链接操作，都需要遍历第一个链表，找到结点an，然后将结点b1链到an的后面，其执行时间是o(n)。若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是o(1)。
相应的算法如下：
linklist connect(linklist a,linklist b)
//假设a，b为非空循环链表的尾指针。
linklist p=a->next;//保存a表的头结点位置。
a->next=b->next->next;//b表的开始结点链接到a表尾。
free(b->next);/释放b表的头结点。
b->next=p;//
return b;//返回新循环链表的尾指针。
注意：循环链表中没有null指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p-＞next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。
在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。
实验二栈、循环队列的简单应用。
2.1【例】在队列中依次加入元素a1，a2，…，an之后，a1是队头元素，an是队尾元素。退出队列的次序只能是a1，a2，…，an。
1） 循环队列的基本操作。
循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（queuesize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为：
方法一：if(i+1==queuesize) /i表示front或rear
i=0;else
i++; 方法二--利用"模运算"
i=(i+1)%queuesize；
2） 循环队列边界条件处理。
循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。 参见动画演示】
解决这个问题的方法至少有三种：
另设一布尔变量以区别队列的空和满；
少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；
使用一个计数器记录队列中元素的总数（即队列长度）。
3） 循环队列的类型定义。
#define queur size 100 //应根据具体情况定义该值。
typedef char queue datatype; /datatype的类型依赖于具体的应用。
typedef sturet头指针，队非空时指向队头元素。
int front尾指针，队非空时指向队尾元素的下一位置。
int rear计数器，记录队中元素总数。
datatype data[queuesize]
数据结构与算法
本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方 与完整的描述。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...
算法与数据结构
学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生，定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指...
算法与数据结构
1 简述算法的概念及其五个重要特性。2 下图是用邻接表存储的图，请画出此图，写出其邻接矩阵以及从c点开始分别按广度优先搜索和深度优先搜索遍历该图的结果。给定一棵用二叉链表表示的二叉树，其根指针为root，编写求此二叉树叶结点个数的算法，要求先写出二叉链表的类型定义。2.编写简单选择排序的算法。1 用...