数据结构考试需掌握代码汇总.doc

1．顺序表：
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 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));
if(!newbase)
exit(OVERFLOW); /* 存储分配失败 */
(*L).elem=newbase; /* 新基址 */
(*L).listsize+=LISTINCREMENT; /* 增加存储容量 */
}
q=(*L).elem+i-1; /* q为插入位置 */
for(p=(*L).elem+(*L).length-1;p>=q;--p) /* 插入位置及之后的元素右移 */
*(p+1)=*p;
*q=e; /* 插入e */
++(*L).length; /* 表长增1 */
return OK;
}

Status ListDelete(SqList *L,int i,ElemType *e) /* 算法2.5 */
{ /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
ElemType *p,*q;
if(i<1||i>(*L).length) /* i值不合法 */
return ERROR;
p=(*L).elem+i-1; /* p为被删除元素的位置 */
*e=*p; /* 被删除元素的值赋给e */
q=(*L).elem+(*L).length-1; /* 表尾元素的位置 */
for(++p;p<=q;++p) /* 被删除元素之后的元素左移 */
*(p-1)=*p;
(*L).length--; /* 表长减1 */
return OK;
}

2．链表
Status InitList(LinkList *L)
{ /* 操作结果：构造一个空的线性表L */
*L=(LinkList)malloc(sizeof(struct LNode)); /* 产生头结点,并使L指向此头结点 */
if(!*L) /* 存储分配失败 */
exit(OVERFLOW);
(*L)->next=NULL; /* 指针域为空 */
return OK;
}

Status ListInsert(LinkList L,int i,ElemType e) /* 算法2.9。不改变L */
{ /* 在带头结点的单链线性表L中第i个位置之前插入元素e */
int j=0;
LinkList p=L,s;
while(p&&j<i-1) /* 寻找第i-1个结点 */
{
p=p->next;
j++;
}
if(!p||j>i-1) /* i小于1或者大于表长 */
return ERROR;
s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
s->data=e; /* 插入L中 */
s->next=p->next;
p->next=s;
return OK;
}

Status ListDelete(LinkList L,int i,ElemType *e) /* 算法2.10。不改变L */
{ /* 在带头结点的单链线性表L中，删除第i个元素,并由e返回其值 */
int j=0;
LinkList p=L,q;
while(p->next&&j<i-1) /* 寻找第i个结点,并令p指向其前趋 */
{
p=p->next;
j++;
}
if(!p->next||j>i-1) /* 删除位置不合理 */
return ERROR;
q=p->next; /* 删除并释放结点 */
p->next=q->next;
*e=q->data;
free(q);
return OK;
}

3．栈
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(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return OK;
}

Status Pop(SqStack *S,SElemType *e)
{ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
if((*S).top==(*S).base)
return ERROR;
*e=*--(*S).top;
return OK;
}
Status GetTop(SqStack S,SElemType *e)
{ /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
if(S.top>S.base)
{
*e=*(S.top-1);
return OK;
}
else
return ERROR;
}

4．队列
Status InitQueue(LinkQueue *Q)
{ /* 构造一个空队列Q */
(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));
if(!(*Q).front)
exit(OVERFLOW);
(*Q).front->next=NULL;
return OK;
}

Status EnQueue(LinkQueue *Q,QElemType e)
{ /* 插入元素e为Q的新的队尾元素 */
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
if(!p) /* 存储分配失败 */
exit(OVERFLOW);
p->data=e;
p->next=NULL;
(*Q).rear->next=p;
(*Q).rear=p;
return OK;
}

Status DeQueue(LinkQueue *Q,QElemType *e)
{ /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
QueuePtr p;
if((*Q).front==(*Q).rear)
return ERROR;
p=(*Q).front->next;
*e=p->data;
(*Q).front->next=p->next;
if((*Q).rear==p)
(*Q).rear=(*Q).front;
free(p);
return OK;
}

5．循环队列
Status EnQueue(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 DeQueue(SqQueue *Q,QElemType *e)
{ /* 若队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR */
if((*Q).front==(*Q).rear) /* 队列空 */
return ERROR;
*e=(*Q).base[(*Q).front];
(*Q).front=((*Q).front+1)%MAXQSIZE;
return OK;
}

Status InitQueue(SqQueue *Q)
{ /* 构造一个空队列Q */
(*Q).base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
if(!(*Q).base) /* 存储分配失败 */
exit(OVERFLOW);
(*Q).front=(*Q).rear=0;
return OK;
}

数值转换：
1）
/* algo3-1.c 调用算法3.1的程序 */
typedef int SElemType; /* 定义栈元素类型为整型 */
#include"c1.h"
#include"c3-1.h" /* 采用顺序栈 */
#include"bo3-1.c" /* 利用顺序栈的基本操作 */

void conversion() /* 算法3.1 */
{ /* 对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 */
SqStack s;
unsigned n; /* 非负整数 */
SElemType e;
InitStack(&s); /* 初始化栈 */
printf("n(>=0)=");
scanf("%u",&n); /* 输入非负十进制整数n */
while(n) /* 当n不等于0 */
{
Push(&s,n%8); /* 入栈n除以8的余数(8进制的低位) */
n=n/8;
}
while(!StackEmpty(s)) /* 当栈不空 */
{
Pop(&s,&e); /* 弹出栈顶元素且赋值给e */
printf("%d",e); /* 输出e */
}
printf("\n");
}

void main()
{
conversion();
}

/* algo3-2.c 改算法3.1，10进制→16进制 */
typedef int SElemType; /* 定义栈元素类型为整型 */
#include"c1.h"
#include"c3-1.h" /* 采用顺序栈 */
#include"bo3-1.c" /* 利用顺序栈的基本操作 */

void conversion()
{ /* 对于输入的任意一个非负10进制整数，打印输出与其等值的16进制数 */
SqStack s;
unsigned n; /* 非负整数 */
SElemType e;
InitStack(&s); /* 初始化栈 */
printf("n(>=0)=");
scanf("%u",&n); /* 输入非负十进制整数n */
while(n) /* 当n不等于0 */
{
Push(&s,n%16); /* 入栈n除以16的余数(16进制的低位) */
n=n/16;
}
while(!StackEmpty(s)) /* 当栈不空 */
{
Pop(&s,&e); /* 弹出栈顶元素且赋值给e */
if(e<=9)
printf("%d",e);
else
printf("%c",e+55);
}
printf("\n");
}

void main()
{
conversion();
}

2）括号匹配
/* algo3-3.c 括号匹配的检验，（限于()、[]） */
typedef char SElemType;
#include"c1.h"
#include"c3-1.h"
#include"bo3-1.c"

void check()
{ /* 对于输入的任意一个字符串，检验括号是否配对 */
SqStack s;
SElemType ch[80],*p,e;
if(InitStack(&s)) /* 初始化栈成功 */
{
printf("请输入表达式\n");
gets(ch);
p=ch;
while(*p) /* 没到串尾 */
switch(*p)
{
case '(':
case '[':Push(&s,*p++);
break; /* 左括号入栈，且p++ */
case ')':
case ']':if(!StackEmpty(s)) /* 栈不空 */
{
Pop(&s,&e); /* 弹出栈顶元素 */
if(*p==')'&&e!='('||*p==']'&&e!='[') /* 弹出的栈顶元素与*p不配对 */
{
printf("左右括号不配对\n");
exit(ERROR);
}
else
{
p++;
break; /* 跳出switch语句 */
}
}
else /* 栈空 */
{
printf("缺乏左括号\n");
exit(ERROR);
}
default: p++; /* 其它字符不处理，指针向后移 */
}
if(StackEmpty(s)) /* 字符串结束时栈空 */
printf("括号匹配\n");
else
printf("缺乏右括号\n");
}
}

void main()
{
check();
}

6．二叉树（仅考虑二叉链表的形式）
int BiTreeDepth(BiTree T)
{ /* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
int i,j;
if(!T)
return 0;
if(T->lchild)
i=BiTreeDepth(T->lchild);
else
i=0;
if(T->rchild)
j=BiTreeDepth(T->rchild);
else
j=0;
return i>j?i+1:j+1;
}

void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数。算法6.1，有改动 */
/* 操作结果: 先序递归遍历T,对每个结点调用函数Visit一次且仅一次 */
if(T) /* T不空 */
{
Visit(T->data); /* 先访问根结点 */
PreOrderTraverse(T->lchild,Visit); /* 再先序遍历左子树 */
PreOrderTraverse(T->rchild,Visit); /* 最后先序遍历右子树 */
}
}

void InOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */
/* 操作结果: 中序递归遍历T,对每个结点调用函数Visit一次且仅一次 */
if(T)
{
InOrderTraverse(T->lchild,Visit); /* 先中序遍历左子树 */
Visit(T->data); /* 再访问根结点 */
InOrderTraverse(T->rchild,Visit); /* 最后中序遍历右子树 */
}
}

typedef BiTree SElemType; /* 设栈元素为二叉树的指针类型 */
#include"c3-1.h"
#include"bo3-1.c"
Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType))
{ /* 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。算法6.3 */
/* 中序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit */
SqStack S;
InitStack(&S);
while(T||!StackEmpty(S))
{
if(T)
{ /* 根指针进栈,遍历左子树 */
Push(&S,T);
T=T->lchild;
}
else
{ /* 根指针退栈,访问根结点,遍历右子树 */
Pop(&S,&T);
if(!Visit(T->data))
return ERROR;
T=T->rchild;
}
}
printf("\n");
return OK;
}

Status InOrderTraverse2(BiTree T,Status(*Visit)(TElemType))
{ /* 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。算法6.2 */
/* 中序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit */
SqStack S;
BiTree p;
InitStack(&S);
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);
}
}
printf("\n");
return OK;
}

void PostOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */
/* 操作结果: 后序递归遍历T,对每个结点调用函数Visit一次且仅一次 */
if(T) /* T不空 */
{
PostOrderTraverse(T->lchild,Visit); /* 先后序遍历左子树 */
PostOrderTraverse(T->rchild,Visit); /* 再后序遍历右子树 */
Visit(T->data); /* 最后访问根结点 */
}
}

void LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ /* 初始条件：二叉树T存在,Visit是对结点操作的应用函数 */
/* 操作结果：层序递归遍历T(利用队列),对每个结点调用函数Visit一次且仅一次 */
LinkQueue q;
QElemType a;
if(T)
{
InitQueue(&q);
EnQueue(&q,T);
while(!QueueEmpty(q))
{
DeQueue(&q,&a);
Visit(a->data);
if(a->lchild!=NULL)
EnQueue(&q,a->lchild);
if(a->rchild!=NULL)
EnQueue(&q,a->rchild);
}
printf("\n");
}
}

7．查找表
int Search_Bin(SSTable ST,KeyType key)
{ /* 在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为 */
/* 该元素在表中的位置，否则为0。算法9.2 */
int low,high,mid;
low=1; /* 置区间初值 */
high=ST.length;
while(low<=high)
{
mid=(low+high)/2;
if EQ(key,ST.elem[mid].key) /* 找到待查元素 */
return mid;
else if LT(key,ST.elem[mid].key)
high=mid-1; /* 继续在前半区间进行查找 */
else
low=mid+1; /* 继续在后半区间进行查找 */
}
return 0; /* 顺序表中不存在待查元素 */
}

int Search_Seq(SSTable ST,KeyType key)
{ /* 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为 */
/* 该元素在表中的位置，否则为0。算法9.1 */
int i;
ST.elem[0].key=key; /* 哨兵 */
for(i=ST.length;!EQ(ST.elem[i].key,key);--i); /* 从后往前找 */
return i; /* 找不到时，i为0 */
}
8.排序表
void InsertSort(SqList *L)
{ /* 对顺序表L作直接插入排序。算法10.1 */
int i,j;
for(i=2;i<=(*L).length;++i)
if LT((*L).r[i].key,(*L).r[i-1].key) /* "<",需将L.r[i]插入有序子表 */
{
(*L).r[0]=(*L).r[i]; /* 复制为哨兵 */
for(j=i-1;LT((*L).r[0].key,(*L).r[j].key);--j)
(*L).r[j+1]=(*L).r[j]; /* 记录后移 */
(*L).r[j+1]=(*L).r[0]; /* 插入到正确位置 */
}
}

//简单插入排序（通俗写法）
#include "c1.h"
typedef int ElemType;
Status InSort(ElemType *a,int n)//简单插入排序
{
int i,j;
ElemType temp;
for(i=1;i<n;i++)//默认第一个数字有序
{
temp=*(a+i);
j=i-1;
while(temp<*(a+j)&&j>=0)
{
*(a+j+1)=*(a+j);
j--;
}
*(a+j+1)=temp;
}
return OK;
}

void BInsertSort(SqList *L)
{ /* 对顺序表L作折半插入排序。算法10.2 */
int i,j,m,low,high;
for(i=2;i<=(*L).length;++i)
{
(*L).r[0]=(*L).r[i]; /* 将L.r[i]暂存到L.r[0] */
low=1;
high=i-1;
while(low<=high)
{ /* 在r[low..high]中折半查找有序插入的位置 */
m=(low+high)/2; /* 折半 */
if LT((*L).r[0].key,(*L).r[m].key)
high=m-1; /* 插入点在低半区 */
else
low=m+1; /* 插入点在高半区 */
}
for(j=i-1;j>=high+1;--j)
(*L).r[j+1]=(*L).r[j]; /* 记录后移 */
(*L).r[high+1]=(*L).r[0]; /* 插入 */
}
}

void QuickSort(SqList *L)
{ /* 对顺序表L作快速排序。算法10.8 */
QSort(L,1,(*L).length);
}

void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}

希尔排序（通俗写法）
#include "stdio.h"
#include "string.h"
void main()
{
int data[11]={0,75,23,98,44,57,12,29,64,38,82};
int i,j,k,incr,temp;
printf("\n<<Shell sort>>\n");
printf("\nNumber:");
for(i=1;i<=10;i++)
printf("%d ",data[i]);
puts("");
for(i=0;i<60;i++)
printf("-");
incr=10/2;
while(incr>0)
{
for(i=incr+1;i<=10;i++)
{
j=i-incr;
while(j>0)
if(data[j]>data[j+incr])
{
temp=data[j];
data[j]=data[j+incr];
data[j+incr]=temp;
j=j-incr;
}
else
j=0;
}
printf("\nAccess: ");
for(k=1;k<=10;k++)
printf("%d ",data[k]);
incr=incr/2;
}
puts("");
for(i=0;i<60;i++)
printf("-");
printf("\nSorting: ");
for(i=1;i<=10;i++)
printf("%d ",data[i]);
}