《软件开发技术基础》第二章C语言版算法整理.docx
《《软件开发技术基础》第二章C语言版算法整理.docx》由会员分享，可在线阅读，更多相关《《软件开发技术基础》第二章C语言版算法整理.docx（55页珍藏版）》请在冰点文库上搜索。
《软件开发技术基础》第二章C语言版算法整理
线性结构
一、线性表
、顺序表
1、顺序表类型描述
structSeqList
{
ElemType*data;//顺序表存储数组的地址
intmaxsize;//顺序表最大允许长度
intlength;//顺序表当前长度
}SeqList；//定义一个线性表SeqList
（1）ElemType代表数组的类型。
（2）数组data需要在初始化函数中利用malloc操作动态申请，maxsize为其长度。
数组的下标从0开始。
（3）length表示线性表当前长度，初始长度为0（空表），最大不超过maxsize。
顺序表的主要算法
2、顺序表的主要算法
（1）顺序表的初始化
顺序表的初始化主要是为ElemType类型的数组申请空间，下面的初始化函数为顺序表申请了长度为size的空间。
voidInit（structSeqlist*L,intsize）
{
if（size>0）
{
L->maxsize=size;
L->length=0;
L->data=（ElemType*）malloc（size*sizeof（ElemType））;
}else
printf（"线性表初始化长度错误!
\n"）;
}
（2）在顺序表中第i个位置插入新元素x
voidInsertList（structSeqlist*L,inti,ElemTypex）
{
intj;
if（i<1||i>L->length+1||L->length==L->maxsize）
printf（"插入位置错误或表满!
\n"）;
else
{
for（j=L->length-1;j>=i-1;j--）
L->data[j+1]=L->data[j];//元素依次后移
L->data[i-1]=x;//向第i个位置存入新元素x
L->length++;//表长度加一
}
}
（3）在顺序表中删除第i个元素
voidDelete（SeqList*L,inti）
{
intj;
if（i<1||i>L->length）
{
print（"表中没有第%d个元素",i）;
}else
{
for（j=i;j<=L->length-1;j++）
L->data[j-1]=L->data[j];
L->length--;
}
}
（4）在顺序表中查找某个元素（按内容查找）
intLocateLise（SeqList*L,ElemTypex）
{
inti;
for（i=0;ilength;i++）
if（L->data[i]==x）
returni+1;//查找成功，返回元素位置
return0;//查找失败，返回0
}
3、顺序表的举例应用
//例2-1一元多项式相加
#include
#include
typedefstruct
{
doublecoef;
intexp;
}multi;
structSeqlist
{
multi*data;
intmaxsize;
intlength;
}L1,L2,L3;
voidInit（structSeqlist*L,intsize）
{
if（size>0）
{
L->maxsize=size;
L->length=0;
L->data=（multi*）malloc（size*sizeof（multi））;
}
else
printf（"thesizeofSeqlistisanerror!
\n"）;
}
voidInsert（structSeqlist*L,inti,doublecoef,intexp）
{
intj;
if（i<1||i>L->length+1||L->length==L->maxsize）
printf（"theplaceyouinsertisanerror!
\n"）;
else
{
for（j=L->length-1;j>=i-1;j--）
{
L->data[j+1].coef=L->data[j].coef;
L->data[j+1].exp=L->data[j].exp;
}
L->data[i-1].coef=coef;
L->data[i-1].exp=exp;
L->length++;
}
}
voiddisplay（structSeqlist*L）
{
inti;
for（i=0;i<=L->length-1;i++）
{
printf（"%f",L->data[i].coef）;
if（L->data[i].exp>0）
printf（"x^%d",L->data[i].exp）;
if（ilength-1）
printf（"+"）;
}
printf（"\n"）;
}
voidmain（）
{
inti=1,j=1,k=1,t;
doublec;
Init（&L1,3）;
Init（&L2,3）;
Init（&L3,10）;
Insert（&L1,1,3.5,0）;
Insert（&L1,2,4,2）;
Insert（&L1,3,2.5,4）;
Insert（&L2,1,1.5,1）;
Insert（&L2,2,2.6,2）;
Insert（&L2,3,1.6,3）;
printf（"L1（x）="）;
display（&L1）;
printf（"L2（x）="）;
display（&L2）;
while（i<=L1.length&&j<=L2.length）
{
if（L1.data[i-1].exp{
Insert（&L3,k,L1.data[i-1].coef,L1.data[i-1].exp）;
i++;
}else
if（L1.data[i-1].exp>L2.data[j-1].exp）
{
Insert（&L3,k,L2.data[j-1].coef,L2.data[j-1].exp）;
j++;
}else
if（L1.data[i-1].exp==L2.data[j-1].exp）
{
c=L1.data[i-1].coef+L2.data[j-1].coef;
t=L1.data[i-1].exp;
if（c!
=0）
Insert（&L3,k,c,t）;
i++;
j++;
}
k++;
}
while（i<=L1.length）
{
Insert（&L3,k,L1.data[i-1].coef,L1.data[i-1].exp）;
i++;
k++;
}
while（j<=L2.length）
{
Insert（&L3,k,L2.data[j-1].coef,L2.data[j-1].exp）;
j++;
k++;
}
printf（"L1（x）+L2（x）="）;
display（&L3）;
}
、单链表
1、单链表的描述
typedefstructLNode
{
ElemTypedata;//数据域，ElemType代表某种数据类型
structLNode*next;//指针域
}ListNode,*LinkList;
（1）ListNode是链表的结点类型，LinkList是指向链表结点的指针类型；
（2）LinklistL;
则定义了一个链表，L指向链表的第一个结点.若指向不带头结点的链表，表空标表示为：
L=NULL;若指向带头结点的链表，表空表示为：
L->next=NULL.
2、单链表的基本算法（带头结点的单链表）
（1）求单链表的长度
为了保持头指针不变，使用了指针p在链表中移动。
intLength（LinkListhead）
{
ListNode*p=head->next;//p指向第一个元素所在结点
intlen=0
while（p!
=NULL）//逐个检测p结点存在与否
{
len++;
p=p->next;//指针后移
}
returnlen;
}
（2）返回单链表中指定序号的结点的指针
ListNode*Get（LinkListhead,intpos）//得到位于pos处的结点指针
{
if（pos<0）returnNULL;//若该结点不存在，则返回null值
else
if（pos==0）returnhead;//若pos为0，则返回头指针
else
{
intk=0;
ListNode*p=head->next;
while（p!
=NULL&&k{
p=p->next;
k++;
}
if（p!
=NULL&&k==pos）
returnp;
else
returnNULL;
}
}
（3）从单链表中删除第i个结点
voidDelete（LinkListhead,inti）
{
if（i<0）
{
printf（"不存在第%d个元素！
\n",i）;
}else
{
ListNode*p=head;//p指向头结点（第0个结点）
ListNode*q;//q和p最终分别指向第i-1和第i个结点
intk=0;
while（p!
=NULL&&k{
q=p;
p=p->next;
k++;
}
if（p==NULL）
{
printf（"%d超出链表长度！
\n"）;
}else
{
q->next=p->next;
free（p）;//从链表中删除该结点，并释放结点p
}
}
}
（4）在第i个位置插入新结点x
voidInsert（LinkListhead,inti,ElemTypex）
{
if（i<1）
printf（"不存在第%d个位置！
\n",i）;
else
{
ListNode*p=head;//p最终将指向第i-1个结点
intk=0;//p目前指向第0个结点（头结点）
while（p!
=NULL&&k{
p=p->next;
k++;
}
if（p==NULL）
printf（"%d超出链表的最大位置！
\n",i）;
else
{
ListNode*s=（ListNode*）malloc（sizeof（ListNode））;
s->data=x;
s->next=p->next;
p->next=s;
}
}
}
（5）在单链表中查找数据值为x的结点
ListNode*Find（LinkListhead,ElemTypex）
{
ListNode*p=head->next;//p指向第一个元素所在结点
while（p!
=NULL&&p->data!
=x）
p=p->next;
returnp;
}
3、单链表的举例应用
//例2-2约瑟夫环
#include
#include
#include
typedefstructLNode
{
intdata;
structLNode*next;
}LNode;
voidInsert（LNode*head,inti,intx）
{
if（i<1）
printf（"不存在第%d个位置！
\n",i）;
else
{
LNode*p=head;
intk=0;
while（p!
=NULL&&k{
p=p->next;
k++;
}
if（p==NULL）printf（"%d超出链表的最大位置！
\n",i）;
else
{
LNode*s=（LNode*）malloc（sizeof（LNode））;
s->data=x;
s->next=p->next;
p->next=s;
}
}
}
voidDelete（LNode*head,inti）
{
if（i<0）
{
printf（"不存在第%d个元素！
\n",i）;
}else
{
LNode*p=head;
LNode*q;
intk=0;
while（p!
=NULL&&k{
q=p;
p=p->next;
k++;
}
if（p==NULL）
{
printf（"%d超出链表长度！
\n"）;
}else
{
q->next=p->next;
free（p）;
}
}
}
intmain（）
{
LNode*head,*p,*t;
intn,s,m;
inti,j;
head=（LNode*）malloc（sizeof（LNode））;
head->next=head;
printf（"请输入元素的总数、开始计数的整数以及间隔数:
\n"）;
scanf（"%d%d%d",&n,&s,&m）;
for（i=1;i<=n;i++）
Insert（head,i,i）;
p=head;
if（s>0&&s<=n）
{
for（i=0;ip=p->next;
}else
printf（"起始计数位置错误！
\n"）;
printf（"出列顺序为:
\n"）;
for（i=1;i<=n;i++）
{
for（j=1;j{
p=p->next;
if（p==head）
p=p->next;
}
t=p->next;
if（t==head）
{
p=t;
t=t->next;
}
printf（"%d",t->data）;
p->next=t->next;
free（t）;
}
printf（"\n"）;
return0;
}
二、栈
、顺序栈
1、顺序栈的类型描述
typedefstruct
{
ElemType*data;//存储元素的数组
inttop;//栈顶指针，存储栈顶元素下标
intstacksize;//最大可用空间数量
}SeqStack;
一般将数组的0下标单元作为栈底，将栈顶元素的下标存储在栈顶指针top中，它随着元素进栈出栈而变化。
top为-1表示空栈，top等于stacksize-1则表示栈满。
2、顺序栈的基本算法
（1）顺序栈初始化
堆栈的初始化主要是为存储元素的数组申请空间，下面的初始化函数申请了长度为size的空间。
voidInitStack（SeqStack*s,intsize）
{
if（size>0）
{
s->stacksize=size;
s->top=-1;
s->data=（ElemType*）malloc（size*sizeof（ElemType））;
}
else
printf（"堆栈初始化长度错误!
\n"）;
}
（3）进栈操作——若栈不满，则在栈顶插入元素x作为新的栈顶
voidPushStack（SeqStack*s,ElemTypex）
{
if（s->topstacksize-1）
{
s->top++;
s->data[s->top]=x;
}else
printf（"栈满!
\n"）;
}
（4）出栈操作——若栈不空，则删除s的栈顶元素，用e返回其值
voidPopStack（SeqStack*s,ElemType*e）
{
if（s->top>-1）
{
*e=s->data[s->top];
s->top--;
}else
printf（"栈空!
\n"）;
}
（4）取栈顶元素——若栈不空，则用e返回s的栈顶元素
voidGetTop（SeqStack*s,ElemType*e）
{
if（s->top>-1）
*e=s->data[s->top];
else
printf（"栈空!
\n"）;
}
链式栈
1、链式栈的类型描述
typedefstructnode
{
ElemTypedata;//数据域
structnode*next;//指针域
}SNode,*LinkStack;
LinkStacktop；//定义栈顶指针
（1）SNode用来定义结点，LinkStack用来定义栈顶指针。
（2）链栈通过链表实现，链表的第一个结点为栈顶,最后一个结点为栈底。
2、链式栈的基本算法
（1）进栈操作——若栈不满，则在栈顶插入元素x作为新的栈顶。
voidPushStack（LinkStacktop,ElemTypex）
{
SNode*p=（SNode*）malloc（sizeof（SNode））;
if（p!
=NULL）
{
p->data=x;
p->next=top;
top=p;
}
}
（2）出栈操作——若栈不空，则删除栈顶元素，用e返回其值。
voidPopStack（LinkStacktop,ElemType*e）;
{
SNode*p;
if（top!
=NULL）
{
*e=top->data;
p=top;
top=top->next;
free（p）;
}
}
3、栈的举例应用
//例2-3表达式求值
#include
#include
#include
structSqStack{
double*data;//存储元素的数组
inttop;//栈顶指针，存储栈顶元素的下标
intstacksize;//堆栈最大可分配空间数量，以元素为单位
};
voidInitStack（SqStack&s,intsize）//初始化
{
if（size>0）
{
s.stacksize=size;
s.top=-1;
s.data=（double*）malloc（sizeof（double））;//申请空间
}elseprintf（"堆栈初始化长度错误!
\n"）;
}
voidPush（SqStack&s,doublex）//入栈
{
if（s.top{
s.top++;
s.data[s.top]=x;
}elseprintf（"栈满"）;
}
voidPop（SqStack&s,double&e）//出栈
{
if（s.top>-1）{
e=s.data[s.top];
s.top--;
}elseprintf（"栈空"）;
}
intmain（）
{
SqStackT;//定义一个堆栈
doublea,b,c,d;
inti;
charexp[20];//存储表达式的数组，最长20个字符
doublenum1,num2;
printf（"依次输入a、b、c、d的值：
"）;
scanf（"%f%f%f%f",&a,&b,&c,&d）;//输入a,b,c,d的数值
printf（"输入表达式：
"）;
scanf（"%s",&exp）;//输入a,b,c,d组成的表达式
InitStack（T,20）;//堆栈初始化
//处理字符数组，计算后缀表达式
for（i=0;exp[i]!
='\0';i++）
{
switch（exp[i]）{
case'+':
case'-':
case'*':
case'/':
Pop（T,num2）;
Pop（T,num1）;
if（exp[i]=='+'）Push（T,num1+num2）;
if（exp[i]=='-'）Push（T,num1-num2）;
if（exp[i]=='*'）Push（T,num1*num2）;
if（exp[i]=='/'）Push（T,num1/num
升级会员 