(完整word版)清华严蔚敏《数据结构》的全部代码实现C语言(word文档良心出品)

/*

c1.h (程序名) */

#include #include

#include /* malloc()等 */ #include /* INT_MAX等 */

#include /* EOF(=^Z或F6),NULL */ #include /* atoi() */ #include /* eof() */

#include /* floor(),ceil(),abs() */ #include /* exit() */ /* 函数结果状态代码 */ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

#define INFEASIBLE -1

/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */ typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

1

/* algo2-1.c 实现算法2.1的程序 */ #include\

typedef int ElemType;

#include\

/*c2-1.h 线性表的动态分配顺序存储结构 */

#define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量 */ #define LISTINCREMENT 2 /* 线性表存储空间的分配增量 */ typedef struct {

ElemType *elem; /* 存储空间基址 */ int length; /* 当前长度 */

int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */ }SqList;

#include\

/* bo2-1.c 顺序表示的线性表(存储结构由c2-1.h定义)的基本操作(12个) */ Status InitList(SqList *L) /* 算法2.3 */

{ /* 操作结果：构造一个空的顺序线性表 */

(*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!(*L).elem)

exit(OVERFLOW); /* 存储分配失败 */ (*L).length=0; /* 空表长度为0 */

(*L).listsize=LIST_INIT_SIZE; /* 初始存储容量 */ return OK; }

Status DestroyList(SqList *L)

{ /* 初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L */ free((*L).elem); (*L).elem=NULL; (*L).length=0; (*L).listsize=0; return OK; }

Status ClearList(SqList *L)

{ /* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */ (*L).length=0; return OK; }

Status ListEmpty(SqList L)

2

{ /* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */

if(L.length==0) return TRUE; else

return FALSE; }

int ListLength(SqList L)

{ /* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */ return L.length; }

Status GetElem(SqList L,int i,ElemType *e)

{ /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */ /* 操作结果：用e返回L中第i个数据元素的值 */ if(i<1||i>L.length) exit(ERROR); *e=*(L.elem+i-1); return OK; }

int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)) { /* 初始条件：顺序线性表L已存在，compare()是数据元素判定函数(满足为1,否则为0) */ /* 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 */ /* 若这样的数据元素不存在，则返回值为0。算法2.6 */ ElemType *p;

int i=1; /* i的初值为第1个元素的位序 */

p=L.elem; /* p的初值为第1个元素的存储位置 */ while(i<=L.length&&!compare(*p++,e)) ++i;

if(i<=L.length) return i; else

return 0; }

Status PriorElem(SqList L,ElemType cur_e,ElemType *pre_e) { /* 初始条件：顺序线性表L已存在 */

/* 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， */ /* 否则操作失败，pre_e无定义 */ int i=2;

ElemType *p=L.elem+1;

while(i<=L.length&&*p!=cur_e)

3

{

p++; i++; }

if(i>L.length)

return INFEASIBLE; else {

*pre_e=*--p; return OK; } }

Status NextElem(SqList L,ElemType cur_e,ElemType *next_e) { /* 初始条件：顺序线性表L已存在 */

/* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， */

/* 否则操作失败，next_e无定义 */ int i=1;

ElemType *p=L.elem;

while(i

i++; p++; }

if(i==L.length)

return INFEASIBLE; else {

*next_e=*++p; return OK; } }

Status ListInsert(SqList *L,int i,ElemType e) /* 算法2.4 */

{ /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1 */

/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */ ElemType *newbase,*q,*p;

if(i<1||i>(*L).length+1) /* i值不合法 */ return ERROR;

if((*L).length>=(*L).listsize) /* 当前存储空间已满,增加分配 */ {

newbase=(ElemType

*)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));

4