请写出线性表的顺序存储结构—顺序表的结构体
typedef struct Seqlist//定义结构体名字Sequlist
{
int elem[100];//数组
int length;//数组长度
}Seqlist;//创建一个Seqilst类型的结构体变量Seqlist
请写出线性表的链式存储结构—单链表的结构体
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;//存放下一个结点的地址
}SListNode;
请写出线性表的链式存储结构—双链表的结构体
typedef struct DoubleList
{
Node* head;
Node* tail;
int size;
}DoubleList;
typedef struct node
{
int data;
struct node *pre;
struct node *next;
}Node Node*;
请写出顺序栈的结构体
#define STACK_INIT SIZE 100
Typedef struct {
SElemType *base;//栈底
SELemType *top;//栈顶
Int stacksize;//栈的大小
}SqStack;
构造一个最大空间为maxsize的空顺序栈
Status InitStack (SqStack &S ,int maxsize)
{
S.base =new ElemType[maxsize];//创建一个大小为maxsize的ElemType数组作为基地址
if(!S.base) exit (OVERFLOW);//判断是否创建成功,大小是否小于等于0
S.top =S.base;//初始栈为空,栈顶等于栈底
S.stacksize =maxsize;//栈的大小为maxsize
return ok;
}
删除栈顶元素
Status Pop (SqStack &S,SElemType &e){
if (S.top ==S.base)return ERROR;//判断栈是否为空,若是,返回错误
e=*--S.top;//赋值e栈顶元素,将栈顶指针下移(删除当前栈顶元素)
return OK;//返回ok
}
请写出链栈的结构体
#define ElemType int //结点内数据类型
//链栈的结点
typedef struct StackNode
{
ElemType data; //数据域
struct StackNode *next; //指针域
}StackNode;
typedef StackNode* LinkStack; //链栈指针
请写出顺序队的结构体
#define MaxSize 10 //定义队列中最大元素个数
typedef struct {
int data[MaxSize];//用静态数组存放队列元素
int front, rear;//队头指针和队尾指针,这里队尾指针指向的是队尾元素的下一个位置
//针对这种队列设计方式:队列中元素的个数:(rear+MaxSize-front)%MaxSize,这会浪费一个存储空间
}Queue,*pQue;
请写出链队的结构体
typedef struct QNode {//节点结构体
QElemtype data;//数据域data
struct QNode *next;//指向下一节点的指针域next
}Qnode,*QueuePtr;//Queueptr是指向Qnode 节点的指针,用于指向队列的头节点
Status EnQueue (LinkQueue &Q,QElemType e))
{
p=new QNode;//新建节点p,
if (!p) exit (overflow);//若储存分配失败返回ERRPOR
p->data =e;//节点数据为e
p->next = NULL;//节点下一指针赋空
Q.rear->next=p;//节点原尾指针移动
Q.rear =p;
}
Status DeQueue (LinkQueue &Q,QElemType &e)
{
if (Q.fronr ==Q.rear) return ERROR;
p = Q.front->next;
e = p->data;
Q.front ->next -= p->next;
delete (p);
return OK;
}
请写出循环队列的结构体
#define Maxsize 100//最大化队列长度
typedef struct {
QElemType *base;//动态分配存储空间
int front;//头指针,指向对列头元素
int rear;//尾指针,指向队列尾元素的下一个位置
int queuesize;//队列大小
} SqQueue;
Status InitQueue (SqQueue &Q,int maxsize)//空循环队列的初始化
{
Q.base = new ElemType[maxsize];//Q.base是一个ElemType类型大小为mxisize数组的头指针
if(!Q.base)exit(OVERFlOW);
Q.queuesize =maxsize;//循环队列大小为maxsize
Q.front =Q.rear =0;
return OK;
}
Status EnQueue(SqQueue &Q,ElemType e){//插入元素为e为Q的新的队尾元素
if((Q.rear+1) % Q.queuesize == Q.front)//是否为0
return ERROR;
Q.base[Q.rear] = e;
Q.rear ={Q.rear+1} % Q.ququesize;//就是Q.rear=Q.rear+1,只不过通过取余将Q.rear定死在了一定范围内,防止越界访问
return OK;
}
更新队尾指针为(Q.rear+1) % Q.queuesize 的目的是实现循环队列的队尾指针的循环移动。在循环队列中,当队尾指针rear达到队列的最后一个位置时,如果要再插入元素,则需要将rear指针移动到队列的头部位置,这样就形成了一个循环的环形结构。计算新的rear位置时,采用取余运算可以保证rear始终处于队列范围内,防止越界访问。因此,更新队尾指针为(Q.rear+1) % Q.queuesize 可以保持rear指针在队列范围内循环移动。
Status DeQueue(SqQueue &Q,ElemType &e)
{
if (Q.front== Q.rear) return ERROR;
e = Q.base[Q.front];//赋值e队列首值
Q.front = (Q.front+1) % Q.queuesize;//队首指针后移,因取余而达到循环移动
return OK;
}
请写出二叉树的链式存储的结构体
typedef struct BiTNode
{
ElemType data;//数据域
struct BiTNode *Ichild,*rchild;//左,右孩子指针
}BiTNode,*BiTree
先序遍历
void PreOrder(BiTtree T){
if(T!=NULL){
visit(T);
PreOrder(T->Ichild);
PreOrder(T->rchild);
}
}
中序遍历
void InOrder(BiTtree T){
if(T!=NULL){
InOrder(T->Ichild);
visit(T);
InOrder(T->rchild);
}
}
后序遍历
void PostOrder(BiTtree T){
if(T!=NULL){
PostOrder(T->Ichild);
PostOrder(T->rchild);
visit(T);
}
}
非递归
void InOrder(BiTtree T)
{
InitStack (S);
Bitree p=T;
while(p||!IsEmpty(S))
{
if(p)
{
Push(S,p);
p=p->lchild;
}
else
{ree
Pop(S,p);
visit(p);
p=p->rchild;
}
}
}
层次遍历
void LevelOrder(BiTree T)
{
InitQueue(Q);
BiTree p;
Enqueue(Q,T);
while(!IsEmpty(Q)){
DeQueue(Q,p);
visit(p);
if(p->lchild!=NULL)
Enqueue(Q,p->lchild);
if(p->rchild!=NULL)
EnQueue(Q,p->rchild);
}
}
请写出线索二叉树的结构体
typedef struct ThreadNode
{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;
}ThreadNode, *ThreadTree;