|
以前写的严蔚敏《数据结构》的部分源码。
#include <stdlib.h>
#include <stdio.h>
#define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量
#define LISTINCREMENT 10 // 线性表存储空间的分配增量
#define OK 1;
#define ERROR -1;
#define OVERFLOW -1;
typedef int ElemType;
typedef int Data;
typedef int Status;
// ---------线性表的动态分配顺序存储结构---------------
typedef struct{
ElemType* elem; // 存储空间基址
int length; // 当前长度
int listsize; // 当前分配的存储容量（以sizeof(ElemType)为单位）
Data data; // 数据成员
}SqList;
Status InitList_Sq(SqList& L)
{
// 构造一个空的线性表L。
L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if ( !L.elem )
{
exit(-1); // 存储分配失败
}
L.length = 0; // 空表长度为0
L.listsize = LIST_INIT_SIZE; // 初始化存储容量
return OK;
}
Status ListInsert_Sq(SqList& L,int i,ElemType e)
{
// 在顺序线性表L中第i个原属之前插入新的元素e
if ( i < 1 || i > L.length + 1 )
{
// i值不合法
return ERROR;
}
if ( L.length >= L.listsize)
{
// 当前存储空间已满，增加分配
ElemType* newbase = (ElemType*) realloc(L.elem,(L.listsize + LISTINCREMENT) * sizeof(ElemType));
if ( NULL == newbase )
{
exit(-1);
}
L.elem = newbase; // 新基址
L.listsize += LISTINCREMENT; // 增加存储容量
}
ElemType* q = &(L.elem[i-1]); // q为插入位置
for (ElemType* p=&(L.elem[L.length-1]); p>=q; --p)
{
// 插入位置之后的元素右移
*(p+1) = *p;
}
*q = e;
++L.length;
return OK;
}
Status ListDelete_Sq(SqList& L,ElemType& e)
{
// 在顺序线性表L中删除第i个元素，并用e返回其值。
if ( i < 1 || i > L.length)
{
return ERROR;
}
ElemType* p = &(L.elem[i-1]); // p为被删除元素的位置
e = *p; // 被删除的元素的值赋给e
ElemType* q = L.elem + L.length - 1;
for (++p; p<=q; ++p)
{
// 被删除元素之后的元素左移
*(p-1) = *p;
}
--L.length;
return OK;
}
int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType))
{
// 在顺序线性表L中查找第1个值与e满足compare()的元素的位序
int i = 1; // 初始为第一个元素的位序
ElemType* p = L.elem; // 初始为第一个元素的存储位置
while ( i <= L.length && !(*compare)(*p++,e) )
{
++i;
}
if ( i <= L.length )
{
return i;
}
else
{
return 0;
}
}
void MergeList_Sq(SqList La,SqList Lb,SqList& Lc)
{
// 已知顺序线性表La和Lb的元素按值非递减排序
// 归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排序
ElemType* pa = La.elem;
ElemType* pb = Lb.elem;
Lc.listsize = Lc.length = La.length + Lb.length;
ElemType* pc = Lc.elem = (ElemType*)malloc(Lc.listsize*sizeof(ElemType));
if ( !pc )
{
exit(-1);
}
ElemType* pa_last = La.elem + La.length -1;
ElemType* pb_last = Lb.elem + Lb.length -1;
while ( pa <= pa_last && pb <= pb_last )
{
// 归并
if ( *pa <= *pb )
{
*pc++ = *pa++;
}
else
{
*pc++ = *pb++;
}
}
while ( pa <= pa_last )
{
*pc++ = *pa++; // 插入La的剩余元素
}
while ( pb <= pb_last )
{
*pc++ = *pb++; // 插入Lb的剩余元素
}
}
// ----------------线性表的单链表存储结构-------------------
typedef struct LNode
{
ElemType data;
struct LNode* next;
}LNode,*LinkList;
Status GetElem_L(LinkList L,ElemType& e)
{
// L为带头结点的单链表的头指针
// 当第i个元素存在时，其值赋给e并返回OK,否则返回ERROR。
LinkList p = L->next;
int j = 1;
while ( p && j < i )
{
p = p->next;
++j;
}
if ( !p || j > i )
{
return ERROR;
}
e = p->data;
return OK;
}
Status ListInsert_L(LinkList& L,ElemType e)
{
// 在带头结点的单链表L中第i个位置之前插入元素e
LinkList p = L;
int j = 0;
while ( p && j < i - 1 )
{
p = p->next;
++j;
}
if ( !p || j > i - 1 )
{
return ERROR;
}
LinkList s = (LinkList)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
Status ListDelete_L(LinkList& L,ElemType& e)
{
// 在带头结点的单链表L中，删除第i个元素，并由e返回其值
LinkList p = L;
int j = 0;
while ( p->next && j < i - 1 )
{
p = p->next;
++j;
}
if (!(p->next) || j > i - 1)
{
return ERROR;
}
LinkList q = p->next;
p->next = q->next;
e = q->data;
free(q);
return OK;
}
void CreateList_L(LinkList& L,int n)
{
// 逆位序输入n个元素的值，建立带表头结点的单链表L。
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL; // 头结点
for ( int i=n; i>0; --i)
{
LinkList p = (LinkList)malloc(sizeof(LNode)); // 新结点
p->data = 0; // 插入元素值
p->next = L->next;
L->next = p; // 插入到表头
}
}
void MergeList_L(LinkList& La,LinkList& Lb,LinkList& Lc)
{
// 已知单链表La和Lb的元素按非递减排列
// 归并La和Lb得到新的单链表Lc，Lc也按值非递减排列。
LinkList pa = La->next;
LinkList pb = Lb->next;
LinkList pc;
Lc = pc = La; // 用La的头结点作为Lc的头结点
while ( pa && pb )
{
if ( pa->data <= pb->data )
{
pc->next = pa;
pc = pa;
pa = pa->next;
}
else
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb; // 插入剩余结点
free(Lb); // 释放Lb的头结点
}
// ---------线性表的静态单链表存储结构-------------
#define MAXSIZE 100 // 链表的最大长度
typedef struct SL
{
ElemType data;
int cur; // 指示结点在数组中的位置
}component,SLinkList[MAXSIZE];
int LocateElem_SL(SLinkList S,ElemType e)
{
// 在静态单链表S中查找第1个值为e的元素，返回它在S中的位序
int i = S[0].cur;
while ( i && S[i].data != e)
{
i = S[i].cur;
}
return i;
}
void InitSpace_SL(SLinkList& space)
{
// 将一维数组space中个分量链成一个备用链表，
// space[0].cur为头指针
// "0"表示空指针
for (int i=0; i<MAXSIZE-1; ++i)
{
space[i].cur = i + 1;
}
space[MAXSIZE-1].cur = 0;
}
int Malloc_SL(SLinkList& space)
{
// 若备用空间链表非空，则返回分配的结点下标
int i = space[0].cur;
if ( space[0].cur )
{
space[0].cur = space[i].cur;
}
return i;
}
void Free_SL(SLinkList& space,int k)
{
// 将下标为k的空闲结点回收到备用链表
space[k].cur = space[0].cur;
space[0].cur = k;
}
void difference(SLinkList& space,int &S)
{
// 依次输入集合A和B的元素，在一维数组space中建立表示集合(A-B)U(B-A)
// 的静态链表，S为其头指针
// 假设备用空间足够大，space[0].cur为其头指针
InitSpace_SL(space); // 初始化备用空间
S = Malloc_SL(space); // 生成S的头结点
int r = S; // r指向S的当前最后结点
int m=5,n=6; // 输入A和B的元素个数
// 建立集合A的链表
for (int j=1; j<=m; ++j)
{
// 分配结点
int i = Malloc_SL(space);
space[i].data = 0; // 输入A的元素值
space[r].cur = i; // 插入到表尾
r = i;
}
space[r].cur = 0; // 尾结点的指针为空
// 依次插入B的元素，若不在当前表中，则插入，否则删除
for (int j=1; j<=n; ++j)
{
int b = 3;
int p = S;
int k = space[S].cur; // k指向集合A中的第一个结点
while ( k != space[r].cur && space[k].data != b ) // 在当前表中查找
{
p = k;
k = space[k].cur;
}
if ( k == space[r].cur ) // 在当前表中不存在该元素，插入在r所指结点之后，且r的位置不变
{
int i = Malloc_SL(space);
space[i].data = b;
space[i].cur = space[r].cur;
space[r].cur = i;
}
else
{
// 该元素已在表中，删除之
space[p].cur = space[k].cur;
Free_SL(space,k);
if ( r == k )
{
r = p; // 若删除的是r所指结点，则需修改尾指针
}
}
}
}
//---------双向链表------------------
typedef struct DuLNode
{
ElemType data;
struct DuLNode* prior;
struct DuLNode* next;
}DuLNode,*DuLinkList;
#include <stdlib.h>
#include <stdio.h>
#define STACK_INIT_SIZE 100 // 存储空间初始分配量
#define STACKINCREMENT 10 // 存储空间分配增量
#define OK 1
#define OVERFLOW -1;
#define ERROR -1
typedef int SElemType;
typedef int Status;
typedef struct
{
SElemType* base; // 在栈构造之前和销毁之后，base的值为NULL
SElemType* top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
}SqStack;
Status InitStack(SqStack &S)
{
// 构造一个空栈S
S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if ( !S.base )
{
exit(-1);
}
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
Status DestroyStack(SqStack& S)
{
free(S.base);
S.base = S.top = NULL;
return OK;
}
Status GetTop(SqStack& S,SElemType& e)
{
// 若栈不空，则用e返回S的栈顶元素，并返回OK
if ( S.top == S.base )
{
return ERROR;
}
e = *(S.top-1);
return OK;
}
Status Push(SqStack& S,SElemType e)
{
// 插入元素e为新的栈顶元素
if ( S.top - S.base >= S.stacksize )
{
// 栈满，追加存储空间
S.base = (SElemType*)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(SElemType));
if ( !S.base )
{
exit(-1);
}
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}
Status Pop(SqStack& S,SElemType& e)
{
// 若栈不空，则删除S的栈顶元素，用e返回其值
if ( S.top == S.base )
{
return ERROR;
}
e = *--S.top;
return OK;
}
bool StackEmpty(SqStack& S)
{
return S.top == S.base;
}
void conversion(unsigned int N)
{
// 将非负十进制整数转换成等值的八进制数
SqStack S;
InitStack(S);
while ( N )
{
Push(S,N % 8);
N = N / 8;
}
SElemType e;
while ( !StackEmpty(S) )
{
Pop(S,e);
printf("%d",e);
}
}
#include <stdlib.h>
#define OK 1;
#define ERROR -1;
#define OVERFLOW -1;
typedef int QElemType;
typedef int Data;
typedef int Status;
// -------単链队列--------
typedef struct QNode
{
QElemType data;
struct QNode* next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front; // 队头指针
QueuePtr rear; // 队尾指针
}LinkQueue;
Status InitQueue(LinkQueue& Q)
{
// 构造一个空队列Q
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if ( !Q.front )
{
exit(-1);
}
Q.front->next = NULL;
return OK;
}
Status DestroyQueue(LinkQueue& Q)
{
// 销毁队列Q
while ( Q.front )
{
Q.rear = Q.front->next;
free(Q.front);
Q.front = Q.rear;
}
return OK;
}
Status EnQueue(LinkQueue& Q,QElemType e)
{
// 插入元素e为Q的心的队尾元素
QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
if ( !p )
{
exit(-1);
}
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
Status DeQueue(LinkQueue& Q,QElemType& e)
{
// 若队列不空，则删除Q的队头元素，用e返回其值
if ( Q.front == Q.rear )
{
return ERROR;
}
QueuePtr p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if ( Q.rear == p )
{
Q.rear = Q.front;
}
free(p);
return OK;
}
// -------循环队列--------
#define MAXQSIZE 100 // 最大队列长度
typedef struct
{
QElemType* base; // 初始化的动态分配存储空间
int front; // 头指针，若队列不空，指向队列头元素
int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;
Status InitSQueue(SqQueue& Q)
{
// 构造一个空队列
Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));
if ( !Q.base )
{
exit(-1);
}
Q.front = Q.rear = NULL;
return OK;
}
int SQueueLength(SqQueue Q)
{
// 返回Q的元素个数，即队列的长度
return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}
Status EnSQueue(SqQueue& Q,QElemType e)
{
// 插入元素e为Q的心的队尾元素
if ( (Q.rear+1) % MAXQSIZE == Q.front )
{
return ERROR;
}
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXQSIZE;
return OK;
}
Status DeSQueue(SqQueue& Q,QElemType& e)
{
// 若队列不为空，则删除Q的队头元素，用e返回其值
if ( Q.front == Q.rear )
{
return ERROR;
}
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;
return OK;
}
#include <stdlib.h>
#define OK 1;
#define ERROR -1;
#define OVERFLOW -1;
typedef int QElemType;
typedef int Data;
typedef int Status;
// -----------String的表示与实现------------
typedef struct
{
char* ch; // 若非空串，则按串长分配存储区，否则ch为NULL
int length; // 串长度
}HString;
Status StrAssign(HString& T,char* chars)
{
// 生成一个其值等于串常量chars的串T
if ( T.ch )
{
free(T.ch);
}
int i;
char* c;
for (i=0,c=chars; c; ++i,++c);
if ( !i )
{
T.ch = NULL;
T.length = 0;
}
else
{
if ( !(T.ch = (char*)malloc(i * sizeof(char))))
{
exit(-1);
}
for (int j=0; j<i; j++)
{
T.ch[j] = chars[j];
}
T.length = i;
}
return OK;
}
int StrLength(HString S)
{
// 返回S的元素个数，即串的长度
return S.length;
}
int StrCompare(HString S,HString T)
{
// 若S>T，返回值>0；若S=T，返回值=0；若S<T，返回值<0
for ( int i=0; i<S.length&&i<T.length; ++i)
{
if ( S.ch[i] != T.ch[i] )
{
return S.ch[i] - T.ch[i];
}
}
return S.length - T.length;
}
Status ClearString(HString& S)
{
// 将S清为空串
if ( S.ch )
{
free(S.ch);
S.ch = NULL;
}
S.length = 0;
return OK;
}
Status Concat(HString& T,HString S1,HString S2)
{
// 用T返回由S1和S2联接而成的新串
if ( T.ch )
{
free(T.ch);
}
if ( !(T.ch = (char*)malloc((S1.length + S2.length) * sizeof(char))) )
{
exit(-1);
}
for (int i=0; i<S1.length; i++)
{
T.ch[i] = S1.ch[i];
}
T.length = S1.length + S2.length;
for (int j=S1.length; j<T.length; j++)
{
T.ch[j] = S2.ch[j-S1.length];
}
return OK;
}
Status SubString(HString& Sub,HString S,int pos,int len)
{
// 用Sub返回串S的第pos个字符长度为len的字串
// 其中，1<=pos<=StrLength(S) && 0<=len<=StrLength(S)-pos+1
if ( pos < 1 || pos > S.length || len < 0 || len > S.length - pos +1 )
{
return ERROR;
}
if ( Sub.ch )
{
free(Sub.ch);
}
if ( !len )
{
Sub.ch = NULL;
Sub.length = 0;
}
else
{
Sub.ch = (char*)malloc(len * sizeof(char));
int i=0;
int j=pos-1;
for ( ; i<len&&j<pos+len-1; i++,j++)
{
Sub.ch[i] = S.ch[j];
}
Sub.length = len;
}
return OK;
}
// ------------串的块链存储表示--------------
#define CHUNKSIZE 80 // 块的大小
typedef struct Chunk
{
char ch[CHUNKSIZE];
struct Chunk* next;
}Chunk;
typedef struct
{
Chunk* head; // 串头
Chunk* tail; // 串尾
int curlen; // 串当前长度
}LString;
#include <stdlib.h>
#include <stdarg.h>
#define OK 1;
#define ERROR -1;
#define OVERFLOW -1;
#define UNDERFLOW -1;
typedef int ElemType;
typedef int Data;
typedef int Status;
// ---------数组的顺序存储表示-----------
#define MAX_ARRAY_DIM 8 // 假设数组维数的最大值为8
typedef struct
{
ElemType* base; // 数组元素基址，由InitArray分配
int dim; // 数组维数
int* bounds; // 数组维界基址，由InitArray分配
int* constants; // 数组映象函数常量基址，由InitArray分配
}Array;
Status InitArray(Array& A,int dim,...)
{
// 若维数dim和各维长度合法，则构造相应的数组A，并返回OK
if ( dim < 1 || dim > MAX_ARRAY_DIM )
{
return ERROR;
}
A.dim = dim;
A.bounds = (int*)malloc(dim * sizeof(int));
if ( !A.bounds )
{
exit(-1);
}
// 若各维长度合法，存入A.bounds，并求出A的元素总数elemtotal
int elemtotal = 1;
va_list ap;
va_start(ap,dim); // ap为va_list类型，是存放变长参数表信息的数组
for (int i=0; i<dim; ++i)
{
A.bounds[i] = va_arg(ap,int);
if ( A.bounds[i] < 0 )
{
return UNDERFLOW;
}
elemtotal *= A.bounds[i];
}
va_end(ap);
A.base = (ElemType*)malloc(elemtotal * sizeof(ElemType));
if ( !A.base )
{
exit(-1);
}
// 求映象函数的常数Ci，并存入A.constants[i-1],i = 1...,dim
A.constants = (int*)malloc(dim * sizeof(int));
if ( !A.constants )
{
exit(-1);
}
A.constants[dim-1] = 1; // L=1，指针的增减以元素的大小为单位
for (int i=dim-2; i>=0; --i)
{
A.constants[i] = A.bounds[i+1] * A.constants[i+1];
}
return OK;
}
Status DestroyArray(Array& A)
{
// 销毁数组A
if ( !A.base )
{
return ERROR;
}
free(A.base);
A.base = NULL;
if ( !A.bounds )
{
return ERROR;
}
free(A.bounds);
A.bounds = NULL;
if ( !A.constants )
{
return ERROR;
}
free(A.constants);
A.constants = NULL;
return OK;
}
Status Locate(Array A,va_list ap,int& off)
{
// 若ap指示的各下标值合法，则求出该元素在A中相对地址off
off = 0;
for (int i=0; i<A.dim; ++i)
{
int ind = va_arg(ap,int);
if ( ind < 0 || ind >= A.bounds[i] )
{
return OVERFLOW;
}
off += A.constants[i] * ind;
}
return OK;
}
Status Value(Array A,ElemType& e,...)
{
// A是n维数组，e为元素变量，随后是n个下标值
// 若各下标不超界，则e赋值为所指定的A的元素值
va_list ap;
va_start(ap,e);
Status result;
int off;
if ( (result = Locate(A,ap,off)) <= 0 )
{
return result;
}
e = *(A.base + off);
return OK;
}
Status Assign(Array& A,...)
{
// A是n维数组，e为元素变量，随后是n个下标值
va_list ap;
va_start(ap,off)) <= 0 )
{
return result;
}
*(A.base + off) = e;
return OK;
}
// ------广义表的头尾链表存储表示------
typedef int AtomType;
typedef enum
{
ATOM,// ATOM==0,原子；
LIST // LIST==0,子表
}ElemTag;
typedef struct GLNode
{
ElemTag tag; // 公共部分，用于区分原子结点和表结点
union // 原子结点和表结点的联合部分
{
AtomType atom; // atom是原子结点的值域，AtomType由用户定义
struct
{
struct GLNode* hp; // 表头
struct GLNode* tp; // 表尾
}ptr; // ptr是表结点的指针域，
};
}*GList;
// ------广义表的扩展线性链表存储表示------
typedef int AtomType;
typedef struct GELNode
{
ElemTag tag; // 公共部分，用于区分原子结点和表结点
union // 原子结点和表结点的联合部分
{
AtomType atom; // atom是原子结点的值域，AtomType由用户定义
struct
{
struct GLNode* hp; // 表头
};
};
struct GLNode* tp; // 相当于线性表的next，指向下一个元素结点
}*GEList;
#include <stdio.h>
#include <stdlib.h>
#define OK 1;
#define ERROR -1;
#define OVERFLOW -1;
#define UNDERFLOW -1;
typedef int TElemType;
typedef int Data;
typedef int Status;
// ----------二叉树的二叉链表存储表示-----------
typedef struct BiTNode
{
TElemType data;
struct BiTNode* lchild; // 左孩子结点
struct BiTNode* rchild; // 右孩子结点
}BiTNode,*BiTree;
#define STACK_INIT_SIZE 100 // 存储空间初始分配量
#define STACKINCREMENT 10 // 存储空间分配增量
// #define OK 1
// #define OVERFLOW -1;
// #define ERROR -1
typedef BiTree SElemType;
typedef struct
{
SElemType* base; // 在栈构造之前和销毁之后，base的值为NULL
SElemType* top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
}SqStack;
Status InitStack(SqStack &S)
{
// 构造一个空栈S
S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if ( !S.base )
{
exit(-1);
}
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
Status DestroyStack(SqStack& S)
{
free(S.base);
S.base = S.top = NULL;
return OK;
}
Status GetTop(SqStack& S,SElemType& e)
{
// 若栈不空，则删除S的栈顶元素，用e返回其值
if ( S.top == S.base )
{
return ERROR;
}
e = *--S.top;
return OK;
}
bool StackEmpty(SqStack& S)
{
return S.top == S.base;
}
Status PrintElement(TElemType e)
{
printf("%dn",e);
return OK;
}
Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e))
{
// 采用二叉链表存储结构，Visit是对数据元素操作的应用函数
// 先序遍历二叉树T的递归算法，对每个数据原属调用函数Visit
if ( T )
{
if ( Visit(T->data) )
{
if ( PreOrderTraverse(T->lchild,Visit))
{
if ( PreOrderTraverse(T->rchild,Visit))
{
return OK;
}
}
}
return ERROR;
}
else
{
return OK;
}
}
Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e))
{
// 终序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit
SqStack S;
InitStack(S);
Push(S,T); // 根指针进栈
SElemType p;
while ( !StackEmpty(S))
{
while ( GetTop(S,p) && p )
{
// 向左走到尽头
Push(S,p->lchild);
}
Pop(S,p); // 空指针退栈
if ( !StackEmpty(S) )
{
// 访问结点，向右一步
Pop(S,p);
if ( !Visit(p->data) )
{
return ERROR;
}
Push(S,p->rchild);
}
}
return OK;
}
Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType e))
{
// 中序遍历二叉树表的非递归算法
SqStack S;
InitStack(S);
BiTree p = T;
while ( p || !StackEmpty(S) )
{
if ( p )
{
// 根指针进栈，遍历左子树
Push(S,p);
p = p->lchild;
}
else
{
// 根指针退栈，访问根结点，遍历右子树
Pop(S,p);
if ( !Visit(p->data) )
{
return ERROR;
}
p = p->rchild;
}
}
return OK;
}
Status CreateBiTree(BiTree& T)
{
// 先序构造二叉树
char ch;
scanf(&ch);
if ( ch == ' ' )
{
T = NULL;
}
else
{
if ( !(T = (BiTree)malloc(sizeof(BiTNode))) )
{
exit(-1);
}
T->data = ch; // 生成根结点
CreateBiTree(T->lchild); // 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
return OK;
}
#include <stdio.h>
#include <stdlib.h>
int Search_Binary(int A[],int low,int high,int e)
{
// 折半查找，非递归
while ( low <= high )
{
int mid = (low + high) / 2;
if ( e == mid )
{
return mid;
}
else if ( e > mid )
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return -1;
}
int Search_Binary1(int A[],int e)
{
// 折半查找,递归
int mid = (low + high) / 2;
if ( e == mid )
{
return mid;
}
else if ( e > mid )
{
return Search_Binary1(A,mid+1,high,e);
}
else
{
return Search_Binary1(A,low,mid-1,e);
}
return -1;
}
#define OK 1;
#define ERROR -1;
#define OVERFLOW -1;
#define UNDERFLOW -1;
typedef int ElemType;
typedef int Data;
typedef int Status;
void InsertSort1(int A[],int n)
{
// 对数组A前n个元素直接插入排序
for (int i=1; i<n; ++i)
{
if ( A[i] < A[i-1] )
{
int tmp = A[i];
for (int j = i - 1; j >= 0&&tmp<A[j]; --j)
{
A[j + 1] = A[j];
}
A[j + 1] = tmp;
}
}
}
#define MAXSIZE 20 // 顺序表的最大长度
typedef int KeyType;
typedef struct
{
KeyType key; // 关键字项
}RcdType; // 记录类型
typedef struct
{
RcdType r[MAXSIZE]; // r[0]闲置或用作哨兵单元
int length; // 顺序表长度
}SqList; // 顺序表类型
void InsertSort(SqList& L)
{
// 直接插入排序
for (int i=2; i<L.length; ++i)
{
// <,需将L.r[i]插入有序子表
if ( L.r[i].key < L.r[i-1].key )
{
L.r[0] = L.r[i]; // 复制为哨兵
L.r[i] = L.r[i-1];
for (int j=i-2; L.r[0].key < L.r[j].key; --j)
{
L.r[j+1] = L.r[j];
}
L.r[j+1] = L.r[0];
}
}
}
void BInsertSort(SqList& L)
{
// 折半插入排序
for (int i=2; i<=L.length; ++i)
{
L.r[0] = L.r[i]; // 将L.r[i]暂存入L.r[0]
int low = 0;
int high = i - 1;
while ( low < high )
{
int mid = (low + high) / 2;
if ( L.r[0].key < L.r[mid].key )
{
high = mid -1;
}
else
{
low = mid + 1;
}
}
for (int j=i-1; j>=high+1; --j)
{
L.r[j+1] = L.r[j];
}
L.r[high+1] = L.r[0];
}
}
void ShellInsert(SqList& L,int dk)
{
// 一趟希尔排序，增量不再是1，而是dk
// 基本思想是先将整个待排记录序列分割成若干子序列分别进行直接插入排序
// 待序列基本有序时，再对所有记录进行一次直接插入排序
for (int i=dk+1; i<L.length; ++i)
{
// <,需将L.r[i]插入有序子表
if ( L.r[i].key < L.r[i-dk].key )
{
L.r[0] = L.r[i]; // 复制为哨兵
for (int j=i-dk; j>0&&L.r[0].key < L.r[j].key; j-=dk)
{
L.r[j+dk] = L.r[j];
}
L.r[j+dk] = L.r[0];
}
}
}
void ShellSort(SqList& L,int dlta[],int t)
{
// 按增量序列dlta[0...t-1]对顺序表L作希尔排序
for (int k=0; k<t; ++k)
{
ShellInsert(L,dlta[k]); // 一趟增量为dlta[k]的插入排序
}
}
int Partition(SqList& L,int high)
{
// 交换顺序表L中子表L.r[low,high]的记录，是枢轴记录到位，并返回其所在的位置
// 此时，在它之前(后)的记录均不大(小)于它
int pivokey = L.r[low].key; // 用子表的第一个记录做枢轴记录
while ( low < high ) // 从表的两端交替向中间扫描
{
while ( low < high && L.r[high].key >= pivokey )
{
--high;
}
// 将比枢轴记录小的记录交换到低端
RcdType tmp = L.r[low];
L.r[low] = L.r[high];
L.r[high] = tmp;
while ( low < high && L.r[low].key <= pivokey )
{
++low;
}
// 将比枢轴记录大的记录交换到高端
tmp = L.r[low];
L.r[low] = L.r[high];
L.r[high] = tmp;
}
return low;
}
int Partition1(SqList& L,high]的记录，是枢轴记录到位，并返回其所在的位置
// 此时，在它之前(后)的记录均不大(小)于它
L.r[0] = L.r[low]; // 用子表的第一个记录做枢轴记录
int pivokey = L.r[low].key; // 枢轴记录关键字
while ( low < high )
{
while ( low < high && L.r[high].key >= pivokey )
{
--high;
}
// 将比枢轴记录小的记录交换到低端
L.r[low] = L.r[high];
while (low < high && L.r[low].key <= pivokey )
{
++low;
}
// 将比枢轴记录大的记录交换到高端
L.r[high] = L.r[low];
}
L.r[low] = L.r[0]; // 枢轴记录到位
return low; // 返回枢轴位置
}
void QSort(SqList& L,int high)
{
// 对顺序表L中的字序列L.r[low...high]做快速排序
if ( low < high )
{
int pivoloc = Partition(L,high); // 将L.r[low...high]一分为二
QSort(L,pivoloc-1); // 对低子表递归排序，pivoloc是枢轴位置
QSort(L,pivoloc+1,high); // 对高子表递归排序
}
}
void QuickSort(SqList& L)
{
// 对顺序表L作快速排序
QSort(L,1,L.length);
}
int SelectMinKey(SqList& L,int i)
{
// 从第i个位置开始选择key最小的记录
int min = L.r[i].key;
int loc = i;
for (int j=i; j<=L.length; ++j)
{
if ( L.r[j].key < min )
{
loc = j;
}
}
return loc;
}
void SelectSort(SqList& L)
{
// 简单选择排序
for ( int i=1; i<L.length; ++i)
{
// 选择第i小的记录，并交换到位
int j = SelectMinKey(L,i); // 在L.r[i...L.length]中选择key最小的记录
if ( i != j )
{
RcdType tmp = L.r[i];
L.r[i] = L.r[j];
L.r[j] = tmp;
}
}
}
typedef SqList HeapType; // 堆采用顺序表存储表示
void HeapAdjust(HeapType& H,int s,int m)
{
// 已知H.r[s...m]中记录的关键字除H.[s].key之外均满足堆的定义，
// 本函数调整H.r[s]的关键字，使H.r[s...m]成为一个大顶堆
RcdType rc = H.r[s];
for ( int j=2*s; j<=m; j*=2) // 沿key较大的孩子结点向下筛选
{
if ( j < m && H.r[j].key < H.r[j+1].key )
{
++j; // j为key较大的记录的下标
}
if ( rc.key >= H.r[j].key )
{
break; // rc应插入在位置s上
}
H.r[s] = H.r[j];
s = j;
}
H.r[s] = rc;
}
void HeapSort(HeapType& H)
{
// 堆排序
for (int i=H.length/2; i>0; --i)
{
// 把H.r[1..H.length]建成大顶堆
HeapAdjust(H,i,H.length);
}
for (i=H.length; i>1; --i)
{
// 将堆顶记录和当前未经排序子序列H.r[1...i]中最后一个记录交换
RcdType tmp = H.r[1];
H.r[1] = H.r[i];
H.r[i] = tmp;
HeapAdjust(H,i-1); // 将H.r[1...i-1]重新调整为大顶堆
}
}
void Merge(RcdType SR[],RcdType TR[],int m,int n)
{
// 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..m]
int j = m+1;
int k = i;
for ( ; i<=m&&j<=n; ++j) // 将SR中记录由小到大并入TR
{
if ( SR[i].key < SR[j].key )
{
TR[k] = SR[i++];
}
else
{
TR[k] = SR[j++];
}
}
if ( i <= m )
{
// 剩余的SR[i..m]复制到TR
// TK[k..n] = SR[i..m];
}
if ( j <= n )
{
// 剩余的SR[j..n]复制到TR
// TR[k..n] = SR[j..n];
}
}
void MSort(RcdType SR[],RcdType TR1[],int t)
{
// 将SR[s..t]归并排序为TR1[s...t]
if ( s == t )
{
TR1[s] = SR[s];
}
else
{
int m = (s + t) / 2; // 将SR[s..t]平分为SR[s..m]和SR[m+1..t]
// MSort(SR,TR2,s,m); // 递归的将SR[s..m]归并为有序的TR2[s..m]
// MSort(SR,m+1,t); // 递归的将SR[m+1..t]归并为有序的TR2[m+1..t]
// Merge(TR2,TR1,m,t); // TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
}
}
void MergeSort(SqList& L)
{
// 归并排序
MSort(L.r,L.r,L.length);
}
template <class T>
void Merge1(T a[],int left,int center,int len)
{
T *t = new T[len-left];// 存放被合并后的元素
int i = left;
int j = center;
int k = 0;
while (i<center && j<len)
{
if (a[i] <= a[j])
t[k++] = a[i++];
else
t[k++] = a[j++];
}
while (i < center)
t[k++] = a[i++];
while (j < len)
t[k++] = a[j++];
// 把 t[] 的元素复制回 a[]
for (i=left,k=0; i<len; i++,k++)
a[i] = t[k];
delete []t;
}
template <class T>
void MSort1(T a[],int right)
{
if (left < right)
{
int center = (left + right) / 2;
MSort1(a,left,center);
MSort1(a,center+1,right);
Merge1(a,right+1);
}
}
template <class T>
void MergeSort1(T a[],int n)
{
MSort1(a,n-1);
}
template <class T>void MergeSort2(T a[],int n){ int beforeLen; // 合并前序列的长度 int afterLen = 1;// 合并后序列的长度 for (beforeLen=1; afterLen<n; beforeLen=afterLen) { afterLen = beforeLen << 1; // 合并后序列的长度是合并前的两倍 int i = 0;// 开始合并时第一个序列的起始位置下标，每次都是从 0 开始 for ( ; i+afterLen<n; i+=afterLen) Merge(a,i+beforeLen,i+afterLen); if (i+beforeLen < n) Merge(a,n); }} （编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
