数据结构 上机实验与解析

Question

我希望的是可以直接从网络上下载...
或者网络上可以直接看也就可以了...
不过希望有习题跟解析

我学的数据结构是 清华大学 严蔚敏 第二版

不是c语言跟c++
实验要求是用delphi来编程...

Answer 1

太高深了,我是学Java的给你下了点希望能用上http://v.youku.com/v_show/id_co00XNzI3NjY1Ng==.html
这是youku上的视频不过得安Flash播放器才能看
线性结构的特点：
在数据元素的非空有限集中，
（1） 存在唯一的一个被称作“第一个”的数据元素。
（2） 存在唯一的一个被称作“最后一个”的数据元素。
（3） 除“第一个”之外，集合的每一个数据元素只有一个前驱。
（4） 除“最后一个”之外，集合的每一个数据元素只有一个后继。

2.1线性表的类型定义
线性表（Linear List）是最常用且最简单的一种数据结构。简言之，一个线性表是n个数据元素的有限序列。
一个数据元素可以有若干个数据项（Item）组成。在这种情况下，常把数据元素称为记录（Record），含有大量记录的线性表又称为文件（File）。
同一个线性表中的数据元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。若将线性表记为：（a1, …, ai-1, ai, ai+1, …, an）则表中ai-1领先于ai，ai领先于ai+1,称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2,…,n-1时，ai又且仅有一个直接后继，当i=2,3,…,n时，ai又且仅有一个直接前驱。
线性表中元素的个数n（n≥0）定义为线性表的长度，n=0时称为空表。在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。

2.2线性表的顺序表示和实现
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。
假设线性表的每个元素需要占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC（ai+1）和第i个数据元素的存储位置LOC（ai）之间满足下列关系：LOC（ai+1）= LOC（ai）+L，一般来说，线性表的第i个数据元素ai的存储位置为：LOC（ai）= LOC（a1）+（i-1）*L,其中LOC（a1）是线性表的第一个数据元素a1的存储位置，通常称作线性表的起始位置或基地址。
线性表的这种机内表示称作线性表的顺序存储结构或顺序映像（Sequential Mapping），反之，称这种存储结构的线性表为顺序表。
线性表的顺序存储结构是一种随机存取的存储结构。

//--------------线性表的动态分配顺序存储结构--------------//
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空间的分配增量
Typedef struct
{
ElemType *elem; //存储空间基址
Int length； //当前长度
Int listsize； //当前分配的存储容量（以sizeof(ElemType)为单位）
}SqList；

当在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要耗费在移动元素上（换句话说，移动元素的操作为预估算法时间复杂度的基本操作），而移动元素的个数取决于插入或删除元素的位置。
在顺序存储结构的线性表中插入或删除一个数据元素，平均约移动表中一半的元素。

2.3线性表的链式表示和实现

2.3.1线性链表
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素ai的存储映像，称为结点（Node）。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或者链。N个结点（ai（1≤i≤n）的存储映像）链结成一个链表，即为线性表（a1， a2， …， an）的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称为线性链表或者单链表。
这个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点（即第一个数据元素的存储映像）的存储位置。线性链表中最后一个结点的指针为“空”（NULL）。
用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的。换句话说，指针为数据元素之间的逻辑关系得映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，由此，这种存储结构为非顺序映像或者链式映像。

//--------------线性表的单链表存储结构--------------//
Typedef struct
{
ElemType data;
Struct LNode *next；
}LNode， *LinkList；

有时候，我们在单链表的第一个结点之前附设一个结点，称之为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等类的附加信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）。
单链表是非随机存取的存储结构。单链表和顺序存储结构不同，它是一种动态结构。

//--------------线性表的静态单链表存储结构--------------//
#define MAXSIZE 1000 //链表的最大长度
Typedef struct
{
ElemType data;
Int cur；
}component， SLinkList[MAXSIZE]；

这种描述方法便于在不设“指针”类型的高级程序设计语言中使用链表结构。在如上述的链表中，数据的一个分量表示一个结点，同时用游标（指示器cur）代替指针指示结点在数组中的相对位置。为了和指针型描述的线性链表相区别，我们给这种用数组描述的链表起名静态链表。

2.3.2循环链表
循环链表（Circular Linked List）是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，这个链表形成一个环。
循环链表的操作和线性表基本一致，差别仅在于算法的循环条件不是p或者p->next是否为空，而是它们是否等于头指针。但有的时候，若在循环链表中设立尾指针而不设头指针，可使某些操作简化。

2.3.3双向链表
在单链表中，NextElem的执行时间为O（1），而PriorElem的执行时间为O（n）。为克服单链表这种单向性的缺点，可利用双向链表（Double Linked List）。
在双向链表的结点中有两个指针域，其一指向直接后继，另一个指向直接前驱。

//--------------线性表的双向链表存储结构--------------//
Typedef struct
{
ElemType data;
Struct *prior；
Struct *next；
}DuLNode， *DuLinkList；

//--------------一个带头结点的线性表类型定义--------------//
//--------------注意：不同的C++标准，其链表结构的定义是不同的--------------//
Typedef struct LNode
{
ElemType data;
Struct LNode *next；
}*Link， *Position；
Typedef struct
{
Link head，tail；
Int len；
}LinkList；

2.4一元多项式的表达和相加
一般情况下的一元n次多项式可写成：
Pn（x） =
其中，pi是指数为ei的项的非零系数，且满足
0≤ e1 ＜ e2 ＜ … ＜ em = n
若用一个长度为m且每个元素有两个数据项（系数项和指数项）的线性表
((p1, e1),(p2, e2),…,(pm, em))
便可以唯一的确定多项式Pn（x）。
若只对多项式进行“求值”等不改变多项式的系数和指数的运算，则采用类似于顺序表的顺序存储结构即可，否则应采用链式存储表示。
有序链表的基本操作定义与线性链表有两处不同：
第一， LocateElem的职能不同
第二， 增加了按有序关系进行插入的操作OrderInsert
Status LocateElem(LinkList L, ElemType e, Position &q, int (*compare)(ElemType, ElemType))
//若有序链表L中存在与e满足判定函数compare（）取值为0的元素，则q指示L中第一个
//值为e的结点的位置，并返回TRUE；否则q指示第一个与e满足判定函数compare（）取值＞0的元素的前驱的位置，并返回FALSE
Status OrderInsert(LinkList &L, ElemType e, int (*compare)(ElemType, ElemType))
//按有序判定函数compare（）的约定，将值为e的结点插入到有序链表L的适当位置上

//--------------多项式抽象数据类型的存储结构定义--------------//
typedef struct
{//项的表示，多项式的项作为LinkList的数据元素
Float coef; //系数
Int expn； //指数
}term， ElemType；//两个类型名：term用于本ADT，ElemType为LinkList的数据对象名
typedef LinkList polynomial； //用带头结点的有序链表表示多项式

void AddPolyn(polynomial &Pa, polynomial &Pb)
{//多项式加法：Pa = Pa + Pb，利用两个多项式的结点构成“和多项式”。
ha = GetHead(Pa); hb = GetHead(Pb); //ha和hb分别指向Pa和Pb的头结点
qa = NextPos(ha); qb = NextPos(hb); //qa和qb分别指向Pa和Pb中当前结点
while(!Empty(Pa)&&!Empty(Pb)) //Pa和Pb均非空
{
a = GetCurElem(qa); b = GetCurElem(qb); //a和b为两表中当前元素比较
swith(*cmp(a, b))
{
case -1: //多项式PA中当前结点的指数值小
ha = qa; qa = NextPos(Pa, qa); break;
case 0: //两者的指数值相等
sum = a.coef + b.coef;
if (sum != 0.0) //修改多项式PA中当前结点的系数值
{
SetCurElem(qa, sum); ha = qa;
}
else //删除多项式PA中当前结点
{
DelFirst(ha, qa); FreeNode(qa);
}
DelFirst(hb, qb); FreeNode(qb); qb = NextPos(Pb, hb);
qa = NextPos(Pa, ha); break;
case 1: //多项式PB中当前结点的指数最小
DelFirst(hb, qb); InsFirst(ha, qb);
qb = NextPos(Pb, hb); break;
}//switch
}//while
if (!Empty(Pb)) Append(Pa, qa); //连接Pb中剩余结点
FreeNode(hb); //释放Pb的头结点
}//AddPolyn

Answer 2

去网易学院

上面有视频教程