表ADT
表一般不用简单数组来实现,通常将其实现为链表。在链表中要不要使用表头则属于个人兴趣问题。在下面的例程中我们都使用表头。
按照C的约定,作为类型的List(表)和Position(位置)以及函数的原型都列在所谓的.h头文件中。具体的Node(结点)声明则在.c文件中。
如下代码为链表的类型声明:
#ifndef _List_H
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
List MakeEmpty( List L );
int IsEmpty( List L );
int IsLast( Position P, List L );
Position Find( ElementType X, List L );
void Delete( ElementType X, List L );
Position FindPrevious( ElementType X, List L );
void Insert( ElementType X, List L, Position L );
void DeleteList( List L );
Position Header( List L );
Position First( List L );
Position Advance( Position P );
ElementType Retrieve( Position P );
#endif /*_List_H */
/* Place in the implementation file */
struct Node
{
ElementType Element;
Position Next;
};
测试一个链表是否为空的函数:
/* Return true if L is empty */
int
IsEmpty( List L )
{
return L->next == NULL;
}
测试当前位置是否是链表的末尾的函数:
/* Return true if P is the last Position in List L */
/* Parameter L is unused in this implementation */
int
IsLast( Position P, List L )
{
return P->next == NULL;
}
Find例程:
/* Return Position of X in L; NULL if not found */
Position
Find( ElementType X, List L )
{
Position P;
P = L->next;
while( P != NULL && P->Element != X )
P = P->next;
return P;
}
删除链表L中的元素X的例程:
/* delete first occurrence of X from a list */
/* assume use of a header node */
Void
Delete( ElementTyep X, List L );
{
Position P, TmpCell;
P = FindPrevious( X, L );
if( !IsLast( P, L ) ) /* 如果是最后一个元素,说明X不在链表中*/
{
TmpCell = P->Next;
P->Next = TmpCell->Next;
free( TmpCell );
}
}
与Delete一起使用的FindPrevious例程:
/* Uses a header. If element is not found, then next field */
/* of returned value is NULL 也就是说如果找不到该元素,那么*/
/* 返回该链表的最后一个元素 */
Position
FindPrevious( ElementType X, List L )
{
Position P;
P = L;
while( P->Next != NULL && P->Next->Element != X )
P = P->Next;
return P;
}
链表的插入例程(在指定的位置P后插入):
void
Insert( ElementType X, List L, Position P)
{
Position TmpCell;
TmpCell = malloc( sizeof(struct Node) );
If(TmpCell == NULL)
FatalError("out of space!!!");
TmpCell->Element = X;
TmpCell->Next = P->Next;
P->Next = TmpCell;
}
最新文章
- Android Hack1 使用weight属性实现视图的居中显示
- 使用AFNetWorking 实现以Basic Authentication方式获取access-token
- iOS APNS配置(转)
- Logistic Regression分类器
- Ubuntu驱动摄像头
- Struts2标签实现for循环
- Lambda 中如果构建一个查询条件,扔该Where返回我们需要的数据。
- C# 类中隐藏基类方法和Partial
- AngularJS 疑难问题解决汇总
- Asp.Net MVC 之 Autofac 初步使用3 集成web api
- [0] TFS 分支/标签
- ABP官方文档翻译 8.1 通知系统
- centos上的grub文件修改
- Luogu P5285 [十二省联考2019]骗分过样例
- c# 属性改变
- numpy&;matplotlib读书笔记
- kotlin 插件更新到 1.2.41 程序出错 Please use kotlin-stdlib-jdk7 instead
- java.lang.NoClassDefFoundError: org/apache/jute/CsvOutputArchive
- Android 监听手机GPS打开状态
- AltiumDesigner元器件搜索中英文对照