Question

一个关于数据结构的问题

设计一个顺序结构线性表，实现如下操作：

1）SETNULL(L) 初始化，构造一个空的线性表

2）LENGTH(L) 求长度,返回线性表中数据元素个数

3）GET(L,i) 取表L中第i个数据元素的值

4）LOCATE(L,x) 按值查找，若表中存在一个或多个值为x的结点，返回第一个找到的数据元素的位序，否则返回一个特殊值。

5）INSERT(L,x,i) 在L中第i个位置新的数据元素x，表长加1。

6）DELETE(L,i) 删除表中第i个数据元素，表长减1。

Answer 1

这是我自己实现顺序表12种数据操作的源代码，你看看
/********************** 声明部分 **********************/
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#include <iostream.h>

#define ElemType int

/********************** 结构体定义部分 **********************/
typedef struct
{
ElemType *elem;
int length;
int listsize;

} SqList;

/********************** 函数块部分 **********************/

/********************** 构造一个空的线性表 **********************/
void InitList(SqList &L)
{
L.elem=(ElemType *)malloc(100*sizeof(ElemType));
if(!L.elem)
exit(0);
L.length=0;
L.listsize=100;
}

/***************销毁线性表*****************/
void DestroyList(SqList &L)
{
free(L.elem);
L.elem=NULL;
L.length=0;
L.listsize=0;
}

/**************清空线性表**************/
void ClearList(SqList &L)
{
L.length=0;
}

/*******判断线性表是否空*******/
int ListEmpty(SqList L)
{
return(L.length==0);
}

/************返回线性表的长度************/
int ListLength(SqList L)
{
return(L.length);
}

/********************** 用e返回L中第i个元素的值 **********************/
int GetElem(SqList L,int i,ElemType &e)
{
if (i<1 || i>L.length)
return 0;
e=*(L.elem+i-1);
return 1;
}

/**************查找元素的位置**************/
int LocateElem(SqList L, ElemType e,
int (*compare)(ElemType, ElemType))
{
int i;
ElemType *p;
i = 1;
p = L.elem;
while (i <= L.length && !(*compare)(*p++, e))
++i;
if (i <= L.length) return i;
else return 0;
}

/***********用pre_e返回cur_e的前驱************/
int PriorElem(SqList L,ElemType cur_e,ElemType &pre_e)//
{
int i=2;
ElemType *p=L.elem+1;
while(i<=L.length&&*p!=cur_e)
{
p++;
i++;
}
if(i>L.length)
return -1;
else
{
pre_e=*--p;
return 1;
}
}

/************next_e返回cur_e的后继*************/
int NextElem(SqList L,ElemType cur_e,ElemType &next_e)
{
int i=1;
ElemType *p=L.elem;
while(i<=L.length&&*p!=cur_e)
{
p++;
i++;
}
if(i==L.length)
return -1;
else
{
next_e=*++p;
return 1;
}
}

/********************** 在L中第i个位置之前插入新的数据元素e，L的长度加1 **********************/
int ListInsert(SqList &L, int i, ElemType e)
{

ElemType *p;
if (i < 1 || i > L.length+1) return 0;
if (L.length >= L.listsize)
{
ElemType *newbase = (ElemType *)realloc(L.elem,
(L.listsize+2)*sizeof (ElemType));
if (!newbase) return 0;
L.elem = newbase;
L.listsize += 2;
}
ElemType *q = &(L.elem[i-1]);
for(p = &(L.elem[L.length-1]);p>=q; --p)
*(p+1) = *p;
*q = e;
++L.length;
return 1;
}

/********************** 删除L的第i个元素，并用e返回其值，L的长度减1 **********************/
int ListDelete(SqList &L, int i, ElemType &e)
{
ElemType *p, *q;
if (i<1 || i>L.length)
return 0;
p = &(L.elem[i-1]);
e = *p;
q = L.elem+L.length-1;
for (++p; p<=q; ++p)
*(p-1) = *p;
--L.length;
return 1;
}

/********************************以此对L的每个数据元素调用函数vi()*****************************/
void ListTraverse(SqList L,void(*vi)(ElemType&))
{
ElemType *p;
int i;
p=L.elem;
for(i=1;i<=L.length;i++)
vi(*p++);
printf("\n");
}

/************比较功能函数***************/
int equal(int c1,int c2)
{
if(c1==c2)
return 1;
else
return 0;
}

/*********************输出格式（%d）*********************/
void print(int &c)
{
printf("%d ",c);
}

void main()
{
SqList L;
ElemType e,e0;
int i;
int j,k;
printf("//////////////////////////////////\n");
printf(" 现在进行线性表操作\n");
printf("//////////////////////////////////\n\n");

InitList(L);
printf("创建成功！\n");
printf("初始化L后：L.elem=%u L.length=%d\nL.listsize=%d\n",L.elem,L.length,L.listsize);

for(j=1;j<=5;j++)
i=ListInsert(L,1,j);
printf("在L的表头依次插入1~5后：*L.elem=");
for(j=1;j<=5;j++)
cout<<*(L.elem+j-1)<<" ";
cout<<endl;
printf("L.elem=%u L.length=%d L.listsize=%d \n",L.elem,L.length,L.listsize);

i=ListEmpty(L);
printf("L是否空；i=%d(1：是，0：否)\n",i);
ClearList(L);
i=ListEmpty(L);
printf("清空L后：L.elem=%u L.length=%d\nL.listsize=%d\n",L.elem,L.length,L.listsize);
printf("L是否空：i=%d(1：是，0：否)\n",i);

for(j=1;j<=10;j++)
ListInsert(L,j,j);
printf("在L的表尾依次插入1~10后：*L.elem=");
for(j=1;j<=10;j++)
cout<<*(L.elem+j-1)<<" ";
cout<<endl;
printf("L.elem=%u L.length=%d L.listsize=%d \n",L.elem,L.length,L.listsize);
ListInsert(L,1,0);
printf("在表头插入0后：*L.elem=");
for(j=1;j<=ListLength(L);j++)
cout<<*(L.elem+j-1)<<" ";
cout<<endl;
printf("L.elem=%u(有可能改变) L.length=%d(改变) L.listsize=%d(改变) \n",L.elem,L.length,L.listsize);

printf("请输入查找元素的位置i（0<i<12）：");
scanf("%d",&i);
GetElem(L,i,e);
printf("第%d个值为：%d\n",i,e);
while(1)
{
printf("请输入要查找的元素：");
scanf("%d",&j);
if((k=LocateElem(L,j,equal))==0)
printf("没有此元素！\n");
else
break;
}
printf("第%d个元素的值为%d\n",k,j);

printf("测试前两个数据：");
for(j=1;j<=2;j++)
{
GetElem(L,j,e0);
i=PriorElem(L,e0,e);
if(-1==i)
printf("元素%d无前驱\n",e0);
else
printf("元素%d的前驱是%d\n",e0,e);
}

printf("测试最后两个数据：");
for(j=ListLength(L)-1;j<=ListLength(L);j++)
{
GetElem(L,j,e0);
i=NextElem(L,e0,e);
if(-1==i)
printf("元素%d无后继\n",e0);
else
printf("元素%d的后继是%d\n",e0,e);
}

while(1)
{
printf("请输入要删除的元素的位置：");
scanf("%d",&j);
if((i=ListDelete(L,j,e))==0)
printf("删除第%d个数据失败！\n",j);
else
break;
}
printf("删除第%d个数据成功，其值为%d\n",j,e);

printf("依次输出元素：");
ListTraverse(L,print);

DestroyList(L);
printf("销毁L后：L.elem=%u L.length=%d\nL.listsize=%d\n",L.elem,L.length,L.listsize);
}

Answer 2

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define QUEUE_INIT_SIZE 100
#define QUEUEINCREMENT 10
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct{
BiTree *base;
BiTree *top;
int stacksize;
}SqStack;
typedef struct QNode
{
BiTree data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
//输入字符序列，建立二叉链表
int CreateBiTree_PreOrder(BiTree &T)
{
char ch;
scanf("%c",&ch);
if(ch==' ')
{
T=NULL;
}
else
{
if(!(T=(BiTree)malloc(sizeof(BiTNode))))exit(OVERFLOW);
T->data=ch;
CreateBiTree_PreOrder(T->lchild);
CreateBiTree_PreOrder(T->rchild);
}
return OK;
}
//访问结点元素,将其值输出
int Visit(char e)
{
printf("%c",e);
return OK;
}
//先序遍历二叉树
int PreOrderTraverse(BiTree T,int (* Visit)(char e))
{
if(T)
{
if(Visit(T->data))
if(PreOrderTraverse(T->lchild,Visit))
if(PreOrderTraverse(T->rchild,Visit))
return OK;
return ERROR;
}
else
return OK;
}
//中序遍历二叉树
int InOrderTraverse(BiTree T,int(*Visit)(char e))
{
if(T)
{
if(InOrderTraverse(T->lchild,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->rchild,Visit))
return OK;
return ERROR;
}
else
return OK;
}
//后序遍历二叉树
int PostOrderTraverse(BiTree T,int(*Visit)(char e))
{
if(T)
{
if(PostOrderTraverse(T->lchild,Visit))
if(PostOrderTraverse(T->rchild,Visit))
if(Visit(T->data))
return OK;
return ERROR;
}
else
return OK;
}
//栈的初始化
int InitStack(SqStack &S)
{
S.base=(BiTree *)malloc(STACK_INIT_SIZE *sizeof(BiTree));
if(!S.base)
{
exit(OVERFLOW);
}
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
//获取栈顶元素
int GetTop(SqStack S,BiTree &e)
{
if(S.top==S.base)
{
return 0;
}
e=*(S.top-1);
return OK;
}
//入栈
int Push(SqStack &S,BiTree e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(BiTree *)realloc(S.base,(S.stacksize+STACKINCREMENT) *sizeof(BiTree));
if(!S.base)
{
exit(OVERFLOW);
}
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
//出栈
int Pop(SqStack&S,BiTree &e)
{
if(S.top==S.base)
return 0;
e=*--S.top;
return OK;
}
//判断栈是否为空
int StackEmpty(SqStack S)
{
if(S.top==S.base)
return 1;
else
return 0;
}
//非递归中序遍历
int inOrderTraverse(BiTree T,int (*Visit)(char e))
{
SqStack S;
InitStack(S);
BiTree p;
Push(S,T);
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;
}
//求二叉树的高度
int BiTreeDepth(BiTree T,int h,int &depth)
{
if(T)
{
if(h>depth)depth=h;
BiTreeDepth(T->lchild,h+1,depth);
BiTreeDepth(T->rchild,h+1,depth);
}
return OK;
}
//求二叉树的叶子个数
int BiTreeLeaf(BiTree T,int &count)
{
if(T)
{
if(!T->lchild&&!T->rchild)count++;
BiTreeLeaf(T->lchild,count);
BiTreeLeaf(T->rchild,count);
}
return OK;
}
//队列的初始化
void InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)
{
printf("错误\n");
return;
}
Q.front->next=NULL;
}
//入队列
void EnQueue(LinkQueue &Q,BiTree e)
{
QNode *p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p)
{
printf("错误\n");
return;
}
p->data=e;
Q.rear->next=p;
Q.rear=p;
}
//出队列
void DeQueue(LinkQueue &Q,BiTree &e)
{
QNode *p;
if(Q.front==Q.rear)
{
printf("错误\n");
return;
}
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
}
//判断队列是否为空
int QueueEmpty(LinkQueue Q)
{
if(Q.front==Q.rear)
return 1;
return 0;
}
//层次遍历
int HierarchyTraverse(BiTree T,int (*Visit)(char e))
{
BiTree p;
LinkQueue Q;
InitQueue(Q);
EnQueue(Q,T);
while(!QueueEmpty(Q))
{
DeQueue(Q,p);
Visit(p->data);
if(p->lchild!=NULL)
{
EnQueue(Q,p->lchild);
}
if(p->rchild!=NULL)
{
EnQueue(Q,p->rchild);
}
}
return OK;
}
void main()
{
printf("\t*************************************************************\n");
printf("\t\t1.输入字符序列，建立二叉链表。\n");
printf("\t\t2.先序遍历二叉树:递归算法。\n");
printf("\t\t3.中序遍历二叉树:递归算法。\n");
printf("\t\t4.后序遍历二叉树:递归算法。\n");
printf("\t\t5.中序遍历二叉树:非递归算法。\n");
printf("\t\t6.求二叉树的高度 。\n");
printf("\t\t7.求二叉树的叶子个数。\n");
printf("\t\t8.借助队列实现二叉树的层次遍历 。\n");
printf("\t\t0.退出 。\n");
printf("\t*************************************************************\n");
int choice;
int h=1,depth;
int count=0;
while(choice!=0)
{
printf("\n请您选择：");
scanf("%d",&choice);
switch(choice)
{
case 1:
getchar();
printf("请您建立二叉树：");
BiTree T;
CreateBiTree_PreOrder(T);
printf("二叉树OK!");
break;
case 2:
PreOrderTraverse(T,Visit);
break;
case 3:
InOrderTraverse(T,Visit);
break;
case 4:
PostOrderTraverse(T,Visit);
break;
case 5:
inOrderTraverse(T,Visit);
break;
case 6:
BiTreeDepth(T,h,depth);
printf("二叉树的高度是：%d",depth);
break;
case 7:
BiTreeLeaf(T,count);
printf("二叉树的叶子个数是：%d",count);
break;
case 8:
HierarchyTraverse(T,Visit);
break;
case 0:
break;
}
}
}