#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#include <conio.h>
#include "common.h"
#include "linklist.h"
#define ElemType char
struct Node /*结点类型定义*/
{
ElemType data;
struct Node * next;
};
typedef Node *LinkList; /* LinkList为结构指针类型*/
void InitList(LinkList *l)/*算法2.5 对单链表进行初始化*/ {
*l=(LinkList)malloc(sizeof(Node)); /*申请结点空间*/ (*l)->next=NULL; /*置为空表*/ }
void ClearList(LinkList L) //清空链表（保留头结点） {
Node *p;
p=L->next;
while(p!=NULL)
{
L->next = p->next;
free(p);
p=L->next;
}
}
void DestroyList(LinkList *l) //销毁链表（先清空，再销毁头结点，头结点设置为空） {
Node *p;
p=*l;
ClearList(p);
l=NULL;
free(p);
}
int EmptyList(LinkList L)
{
if(L->next==NULL) return TRUE;
else return FALSE;
}
void ShowList(LinkList L)
{
Node *p;
p=L->next;
while(p!=NULL)
{
printf("%c\n",p->data);
p=p->next;
}
}
void CreateFromHead(LinkList L)
/*算法 2.6 通过键盘输入表中元素值，利用头插法建单链表*/
{
Node *s;
char c;
int flag=1;
while(flag) /* flag初值为1，当输入"$"时，置flag为0，建表结束*/ {
c=getchar();
if(c!='$')
{
s=(Node*)malloc(sizeof(Node)); /*建立新结点s*/
s->data=c;
s->next=L->next;/*将s结点插入表头*/
L->next=s;
}
else
flag=0;
}
}
void CreateFromTail(LinkList L)
/*算法 2.7 通过键盘输入表中元素值，利用尾插法建单链表*/
{
Node *r, *s;
char c;
int flag =1; /*设置一个标志，初值为1，当输入"$"时，flag为0，建表结束*/
r=L; /*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/
while(flag) /*循环输入表中元素值，将建立新结点s插入表尾*/
{
c=getchar();
if(c!='$')
{
s=(Node*)malloc(sizeof(Node));
s->data=c;
r->next=s;
r=s;
}
else
{
flag=0;
r->next=NULL; /*将最后一个结点的next链域置为空，表示链表的结束*/ }
}
}
Node * Get (LinkList L, int i)
/*算法2.8 在带头结点的单链表L中查找第i个结点，若找到(1≤i≤n)，则返回该结点的存储位置; 否则返回NULL*/
{
int j;
Node *p;
p=L;
j=0; /*从头结点开始扫描*/
while ((p->next!=NULL)&&(j<i))
{
p=p->next; /* 扫描下一结点*/
j++; /* 已扫描结点计数器 */
}
if(i == j)
return p; /* 找到了第i个结点 */
else
return NULL; /* 找不到，i≤0或i>n */
}
Node *Locate( LinkList L,ElemType key)
/*算法2.9 在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL*/
{
Node *p;
p=L->next; /*从表中第一个结点开始 */
while (p!=NULL)
{
if (p->data!=key)
p=p->next;
else
break; /*找到结点值=key时退出循环 */
}
return p;
}
int ListLength(LinkList L)
/*算法2.10 求带头结点的单链表L的长度*/
{
Node *p;
int j;
p=L->next;
j=0; /*用来存放单链表的长度*/
while(p!=NULL)
{
p=p->next;
j++;
}
return j; /*j为求得的单链表长度*/
}
int InsList(LinkList L,int i,ElemType e)
/*算法2.11 在带头结点的单链表L中第i个位置插入值为e的新结点s*/
{
Node *pre,*s;
int k;
pre=L;
k=0; /*从"头"开始，查找第i-1个结点*/
while(pre!=NULL&&k<i-1) /*表未查完且未查到第i-1个时重复，找到pre指向第i-1个*/
{
pre=pre->next;
k=k+1;
} /*查找第i-1结点*/
if(!pre) /*如当前位置pre为空表已找完还未数到第i个，说明插入位置不合理*/ {
printf("插入位置不合理!");
return ERROR;
}
s=(Node*)malloc(sizeof(Node)); /*申请一个新的结点S */
s->data=e; /*值e置入s的数据域*/
s->next=pre->next; /*修改指针，完成插入操作*/
pre->next=s;
return OK;
}
int DelList(LinkList L,int i,ElemType *e)
/*算法2.11 在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中*/
{
Node *pre,*r;
int k;
pre=L;
k=0;
while(pre->next!=NULL && k<i-1) /*寻找被删除结点i的前驱结点i-1使p指向它*/ {
pre=pre->next;
k=k+1;
} /*查找第i-1个结点*/
if(!(pre->next)) /* 即while循环是因为p->next=NULL或i<1而跳出的,而是因为没有找到合法的前驱位置，说明删除位置i不合法。*/
{
printf("删除结点的位置%d不合理!",i);
return ERROR;
}
r=pre->next;
pre->next=pre->next->next; /*修改指针，删除结点r*/
*e = r->data;
free(r); /*释放被删除的结点所占的内存空间*/
printf("成功删除结点!");
return OK;
}
void main()
{
LinkList l;//指向头结点的指针
Node *p;
char choice;
int i;
ElemType c;
InitList(&l); //初始化
/////////////////////////////////////////////////////
//建立链表
printf("请选择建立方法：1、头插法 2、尾插法："); choice=getch(); putchar(choice);
if(choice=='1')
{ //头插建立链表
printf("\n用头插法建立单链表,请输入链表数据,以$结束!\n"); CreateFromHead(l);
}
else
{ //尾插建立链表
printf("\n用尾插法建立单链表,请输入链表数据,以$结束!\n"); CreateFromTail(l);
}
ShowList(l);
////////////////////////////////////////////
//查找
printf("请选择查找方法：A、序号查找 B、值查找："); choice=getch(); putchar(choice);
if(choice=='A' || choice=='a')
{
printf("\n请输入序号："); scanf("%d",&i);
p=Get(l,i);
if(p!=NULL) printf("%c",p->data);
else printf("序号非法！");
车 车 } } else { gets(&c); //处理前面输入留在缓冲区的回车 printf("\n请输入要查找的值："); scanf("%c",&c); p=Locate(l,c); if(p!=NULL) printf("%c",p->data); else printf("您要找的值不存在！"); } /////////////////////////////////////////////// //插入一个结点 printf("\n请输入插入位置："); scanf("%d",&i);gets(&c); //处理前面输入留在缓冲区的回printf("\n请输入插入的值："); scanf("%c",&c); if(InsList(l,i,c)==OK) { printf("插入数据成功。链表数据为：\n"); ShowList(l); } else printf("插入数据失败。\n"); /////////////////////////////////////////////// //删除一个结点 printf("\n请输入删除位置："); scanf("%d",&i);gets(&c); //处理前面输入留在缓冲区的回if(DelList(l,i,&c)==OK) { printf("%c已经被成功删除。链表数据为：\n",c); ShowList(l); } else printf("删除数据失败。\n"); DestroyList(&l);
第二篇：数据结构(C语言版答案)
第一章 习题答案
2、××√
3、（1）包含改变量定义的最小范围
（2）数据抽象、信息隐蔽
（3）数据对象、对象间的关系、一组处理数据的操作
（4）指针类型
（5）集合结构、线性结构、树形结构、图状结构
（6）顺序存储、非顺序存储
（7）一对一、一对多、多对多
（8）一系列的操作
（9）有限性、输入、可行性
4、（1）A（2）C（3）C
5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n）
第二章 习题答案
1、（1）一半，插入、删除的位置
（2）顺序和链式，显示，隐式
（3）一定，不一定
（4）头指针，头结点的指针域，其前驱的指针域
2、（1）A（2）A：E、A
B：H、L、I、E、A
C：F、M
D：L、J、A、G或J、A、G
（3）D（4）D（5）C（6）A、C
3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。
头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。
首元素结点：线性表中的第一个结点成为首元素结点。
4、算法如下：
int Linser(SeqList *L,int X)
{ int i=0,k;
if(L->last>=MAXSIZE-1)
{ printf(“表已满无法插入”)；
return(0);
}
while(i<=L->last&&L->elem[i]<X)
i++;
for(k=L->last;k>=I;k--)
L->elem[k+1]=L->elem[k];
L->elem[i]=X;
L->last++;
return(1);
}
5、算法如下：
#define OK 1
#define ERROR 0
Int LDel(Seqlist *L,int i,int k)
{ int j;
if(i<1||(i+k)>(L->last+2))
{ printf(“输入的i，k值不合法”);
return ERROR;
}
if((i+k)==(L->last+2))
{ L->last=i-2;
ruturn OK;
}
else
{for(j=i+k-1;j<=L->last;j++)
elem[j-k]=elem[j];
L->last=L->last-k;
return OK;
}
}
6、算法如下：
#define OK 1
#define ERROR 0
Int Delet(LInkList L,int mink,int maxk)
{ Node *p,*q;
p=L;
while(p->next!=NULL)
p=p->next;
if(mink<maxk||(L->next->data>=mink)||(p->data<=maxk)) { printf(“参数不合法”);
return ERROR;
}
else
{ p=L;
while(p->next-data<=mink)
p=p->next;
while(q->data<maxk)
{ p->next=q->next;
free(q);
q=p->next;
}
return OK;
}
}
9、算法如下：
int Dele(Node *S)
{ Node *p;
P=s->next;
If(p= =s)
{printf(“只有一个结点，不删除”)；
return 0;
}
else
{if((p->next= =s)
{s->next=s;
free(p);
return 1;
}
Else
{ while(p->next->next!=s)
P=p->next;
P->next=s;
Free(p);
return 1;
}
}
}
第三章 习题答案
2、（1）
3、栈有顺序栈和链栈两种存储结构。
在顺序栈中，栈顶指针top=-1时，栈为空；栈顶指针top=Stacksize-1时，栈为满。 在带头结点链栈中，栈顶指针top-〉next=NULL，则代表栈空；只要系统有可用空间，链栈就不会出现溢出，既没有栈满。
5、
#include<seqstack1.h>
#include "stdio.h"
void main( )
{
char ch,temp;
SeqStack s;
InitStack(&s);
scanf("%c",&ch);
while(ch!='@'&&ch!='&')
{
Push(&s,ch);
scanf("%c",&ch);
}
while(ch!='@'&&!IsEmpty(&s))
{
Pop(&s,&temp);
scanf("%c",&ch);
if(ch!=temp)
break;
}
if(!IsEmpty(&s))
printf("no!\n");
else
{
scanf("%c",&ch);
if(ch=='@') printf("yes!\n");
else printf("no!\n");
}
}
12、（1）功能：将栈中元素倒置。
（2）功能：删除栈中的e元素。
（3）功能：将队列中的元素倒置。
第四章习题答案
1、StrLength(s)操作结果为14；SubString(sub1,s,1,7)操作结果为sub1=’I AM A ’； SubString(sub2,s,7,1)操作结果为sub2=’ ’；StrIndex(s,’A’,4) 操作结果为5； StrReplace(s,’STUDENT’,q) 操作结果为’I AM A WORKER’；
StrCat(StrCat(sub1,t), StrCat(sub2,q)) 操作结果为’I AM A GOOD WORKER’； 2、
int StrReplace(SString S,Sstring T,SString V)
{
int i=1; //从串S的第一个字符起查找串T
if(StrEmpty(T)) //T是空串
return ERROR;
do
{
i=Index(S,T,i); //结果i为从上一个i之后找到的子串T的位置 if(i) //串S中存在串T
{
StrDelete(S,i,StrLength(T)); //删除该串T
StrInsert(S,i,V); //在原串T的位置插入串V
i+=StrLength(V); //在插入的串V后面继续查找串T }
}while(i);
return OK;
}
第五章习题答案
1、（1）数组A共占用48*6=288个字节；
（2）数组A的最后一个元素的地址为1282；
（3）按行存储时loc（A36）=1000+[（3-1）*8+6-1]*6=1126
（4）按列存储时loc（A36）=1000+[（6-1）*6+3-1]*6=1192
9、（1）（a，b）（2）（（c，d））（3）（b）（4）b（5）（d）
10、D
第六章 习题答案
1、三个结点的树的形态有两个；三个结点的二叉树的不同形态有5个。
2、略
3、证明：分支数=n1+2n2+…+knk （1）
n= n0+n1+…+nk （2）
n=分支数+1 （3） ∵
将（1）（2）代入（3）得
n0= n2+2n3+3n4+…+（k-1）nk+1
4、
注：C结点作为D的右孩子（画图的时候忘记了，不好意思）
5、n0=50，n2=n0-1=49，所以至少有99个结点。
6、（1）前序和后序相同：只有一个结点的二叉树
（2）中序和后序相同：只有左子树的二叉树
（3）前序和中序相同：只有右子树的二叉树
7、证明：∵n个结点的K叉树共有nk个链域，分支数为n-1（即非空域）。 ∴空域=nk-（n-1）=nk-n+1
8、对应的树如下：
9、（答案不唯一） 哈夫曼树如下图所示：
哈夫曼编码如下： 频率 编码
0.07 0010
0.19 10
0.02 00000 0.06 0001
0.32 01
0.03 00001 0.21 11
0.10 0011
11、对应的二叉树如下：
12、求下标分别为i和j的两个桔点的最近公共祖先结点的值。
typedef int ElemType;
void Ancestor(ElemType A[],int n,int i,int j)
{while(i!=j)
if(i>j) i=i/2;
else j=j/2;
printf("所查结点的最近公共祖先的下标是%d,值是%d",i,A[i]);
}
15、编写递归算法，对于二叉树中每一个元素值为X的结点，删去以它为根的子树，并释放相应的空间。
void Del_Sub(BiTree T)
{ if(T->lchild) Del_Sub(T->lchild);
if(T->rchild) Del_Sub(T->rchild);
free(T);
}
void Del_Sub_x(BiTree T,int x)
{ if(T->data==x) Del_Sub(T);
else
{if(T->lchild) Del_Sub_x(T->lchild,x);
if(T->rchild) Del_Sub_x(T->rchild,x);
}
}
22、
int Width(BiTree bt)
{if (bt==NULL) return (0);
else
{BiTree p,Q[50];
int front=1,rear=1,last=1;
int temp=0, maxw=0;
Q[rear]=bt;
while(front<=last)
{p=Q[front++]; temp++;
if (p->lchild!=NULL) Q[++rear]=p->lchild;
if (p->rchild!=NULL) Q[++rear]=p->rchild; {last=rear;
if(temp>maxw) maxw=temp;
temp=0;}
}
return (maxw);
}
}
第七章 习题答案
1、（1）顶点1的入度为3，出度为0； 顶点2的入度为2，出度为2；
顶点3的入度为1，出度为2；
顶点4的入度为1，出度为3；
顶点5的入度为2，出度为1；
顶点6的入度为2，出度为3；
（2）邻接矩阵如下：
0 0 0 0 0 0
1 0 0 1 0 0
0 1 0 0 0 1
0 0 1 0 1 1
1 0 0 0 0 0
1 1 0 0 1 0
（3）邻接表
（4）逆邻接表
2、答案不唯一
（2）深度优先遍历该图所得顶点序列为：1，2，3，4，5，6
边的序列为：（1，2）（2，3）（3，4）（4，5）（5，6）
（3）广度优先遍历该图所得顶点序列为：1，5，6，3，2，4
边的序列为：（1，5）（1，6）（1，3）（1，2）（5，4）
3、
（1）每个事件的最早发生时间：
ve(0)=0,ve(1)=5,ve(2)=6, ve(3)=12, ve(4)=15, ve(5)=16,
ve(6)=16, ve(7)=19, ve(8)=21, ve(9)=23
每个事件的最晚发生时间:：
vl(9)=23, vl(8)=21, vl(7)=19, vl(6)=19, vl(5)=16, vl(4)=15,
vl(3)=12, vl(2)=6, vl(1)=9, vl(0)=0
（2）每个活动的最早开始时间：
e(0,1)=0, e(0,2)=0, e(1,3)=5, e(2,3)=6, e(2,4)=6, e(3,4)=12, e(3,5)=12,
e(4,5)=15, e(3,6)=12, e(5,8)=16, e(4,7)=15, e(7,8)=19, e(6,9)=16, e(8,9)=21
每个活动的最迟开始时间：
l(0,1)=4, l(0,2)=0, l(1,3)=9, l(2,3)=6, l(2,4)=12, l(3,4)=12, l(3,5)=12, l(4,5)=15, l(3,6)=15, l(5,8)=16, l(4,7)=15, l(7,8)=19, l(6,9)=19, l(8,9)=21
（3）关键路径如下图所示：
4、顶点1到其余顶点的最短路经为：
1-〉3最短路经为1，3；长度为15
1-〉2最短路经为1，3，2；长度为19
1-〉5最短路经为1，3，5；长度为25
1-〉4最短路经为1，3，2，4；长度为29
1-〉6最短路经为1，3，2，4，6；长度为44
13、A(7)B(3)C(2)D(11)E(8)
14、略
15、略
第八章 查找
1、画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。
解：
ASL=(1+2*2+4*3+3*4)/10=2.9
5、
解：（1）插入完成后的二叉排序树如下：
ASL=(1+2*2+3*3+3*4+2*5+1*6)/12=3.5
(2)ASL=(1+282+3*4+4*5)=37/12
(3)
12、
解：哈希表构造如下：
H(22)=(22*3)%11=0
H(41)=(41*3)%11=2
H(53)=(53*3)%11=5
H(46)=(46*3)%11=6
H(30)=(30*3)%11=2 与(41)冲突
H1(30)=(2+1)%11=3
H(13)=(13*3)%11=6 与46冲突
H1(13)=(6+1)%11=7
H(01)=(01*3)%11=3 与30冲突
H1(01)=(3+1)%11=4
H(67)=(67*3)%11=3 与30冲突
H1(67)=(3+1)%11=4 与01冲突
H2(67)=(3+2)%11=5 与53冲突
H3(67)=(3+3)%11=6 与46冲突
H4(67)=(3+4)%11=7 与13冲突
H5(67)=(3+5)%11=8
ASLsucc=(1*4+2*3+6)/8=2
ASLunsucc=(2+8+7+6+5+4+3+2)/8=37/8
第九章 排序
1、以关键字序列（503，087，512，061，908，170，897，275，653，426）为例，手工执行以下排序算法，写出每一趟派结束时的关键字状态。
（1）直接插入排序（2）希尔排序（增量序列为5，3，1）（3）快速排序（4）堆排序（5）归并排序
解：（1）略
（2）增量为5的排序结果：170，087，275，061，426，503，897，512，653，908 增量为3的排序结果：061，087，275，170，426，503，897，512，653，908 增量为1的排序结果：061，087，170，275，426，503，512，653，897，908
（3）一次划分后：{426 087 275 061 170}503{897 908 653 512}
分别进行：{170 087 275 061}426 503 {512 653} 897 {908}
{061 087}170{275}426 503 512 {653} 897 908
061 087 170 275 426 503 512 653 897 908
（4）略
7、已知一组关键字：（40，27，28，12，15，50，7），要求采用快速排序法从小到大排序。请写出每趟排序后的划分结果。
解：初始状态：40 27 28 12 15 50 7
一次划分：{7 27 28 12 15} 40 {50}
依次划分：7 {27 28 12 15} 40 50
7 {15 12} 27 {28} 40 50
7 12 15 27 28 40 50
16、（1）A3 B1 C4 D2 E7
(2)C
(3)C
17、对，错，对