数据结构C语言算法大全

数据结构C语言算法大全1)插入操作在顺序表L的第i(1<=L.length+1)个位置插入新元素e。如果i的输入不合法，则返回false，表示插入失败；否则，将顺序表的第i个元素以及其后的元素右移一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true。boolListInsert(SqList&L,inti,ElemTypee){//本算法实现将元素e插入到顺序表L中第i个位置if(i<1||i>L.length+1)returnfalse;//判断i的范围是否有效if(L.length>=MaxSize)returnfalse;//当前存储空间已满，不能插入for(intj=L.length;j>=i;j--)//将第i个位置及之后的元素后移L.data[j]=L.data[j-l];L.data[i-1]=e;//在位置i处放入eL.length++;//线性表长度加1returntrue;}2)删除操作删除顺序表L中第i(1<=i<=L.length)个位置的元素，成功则返回true,否则返回false，并将被删除的元素用引用变量e返回。复制纯文本新窗口boolListDelete(SqList&L,inti,int&e){//本算法实现删除顺序表L中第i个位置的元素if(i<1||i>L.length)returnfalse;//判断i的范围是否有效e=L.data[i-1];//将被删除的元素赋值给efor(intj=i;j<L.length;j++)//将第i个位置之后的元素前移数据结构C语言算法大全全文共25页，当前为第1页。L.data[j-1]=L.data[j];数据结构C语言算法大全全文共25页，当前为第1页。L.length--;//线性表长度减1returntrue;}3)按值查找（顺序查找）在顺序表L中查找第一个元素值等于e的元素，并返回其下标。intLocateElem(SqListL,ElemTypee){//本算法实现查找顺序表中值为e的元素，如果查找成功，返回元素位序，否则返回0inti;for(i=0;i<L.length;i++)if(L.data[i]==e)returni+1;//下标为i的元素值等于e，返回其位号i+1return0;//退出循环，说明查找失败}单链表的定义typedefstructLNode{//定义单链表结点类型ElemTypedata;//数据域structLNode*next;//指针域}LNode,*LinkList;采用头插法建立单链表数据结构C语言算法大全全文共25页，当前为第2页。数据结构C语言算法大全全文共25页，当前为第2页。

图2-4

头插法建立单链表

头插法建立单链表的算法如下：LinkListCreatList1(LinkList&L){//从表尾到表头逆向建立单链表L，每次均在头结点之后插入元素LNode*s;intx;L=(LinkList)malloc(sizeof(LNode));//创建头结点L->next=NULL;//初始为空链表scanf("%d",&x);//输入结点的值while(x!=9999){//输入9999表示结束s=(LNode*)malloc(sizeof(LNode));//创建新结点s->data=x;s->next=L->next;//重点（如果使用头插法的话）L->next=s;//将新结点插入表中，L为头指针scanf("%d",&x);}//while结束returnL;}数据结构C语言算法大全全文共25页，当前为第3页。数据结构C语言算法大全全文共25页，当前为第3页。头插法建立单链表的算法虽然简单，但生成的链表中结点的次序和输入数据的顺序不一致。若希望两者次序一致，可采用尾插法。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r,使其始终指向当前链表的尾结点，如图2-5所示。

图2-5

尾插法建立单链表

尾插法建立单链表的算法如下：LinkListCreatList2(LinkList&L){//从表头到表尾正向建立单链表L,每次均在表尾插入元素intx;//设元素类型为整型L=(LinkList)malloc(sizeof(LNode));LNode*s,*r=L;//r为表尾指针scanf("%d",&x);//输入结点的值while(x!=9999){//输入9999表示结束s=(LNode*)malloc(sizeof(LNode));s->data=x;//重点r->next=s;r=s;//r指向新的表尾结点scanf("%d",&x);}r->next=NULL;//尾结点指针置空returnL;}数据结构数据结构C语言算法大全全文共25页，当前为第4页。按序号查找结点值在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL。

按序号查找结点值的算法如下：LNodeGetElem(LinkListL,inti){//本算法取出单链表L（带头结点）中第i个位置的结点指针intj=1;//计数，初始为1LNode*p=L->next;//头结点指针赋给p//注意if(i==0)returnL;//若i等于0，则返回头结点if(i<1)returnNULL;//若i无效，则返回NULLwhile(p&&j<i){//从第1个结点开始找，查找第i个结点p=p->next;j++;}returnp;//返回第i个结点的指针，如果i大于表长，p=NULL，直接返回p即可}按值查找表结点从单链表第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针。若整个单链表中没有这样的结点，则返回NULL。按值查找结点的算法如下：数据结构数据结构C语言算法大全全文共25页，当前为第5页。LNodeLocateElem(LinkListL,ElemTypee){//本算法查找单链表L（带头结点）中数据域值等于e的结点指针，否则返回NULLLNode*p=L->next;while(p!=NULL&&p->data!=e)//从第1个结点开始查找data域为e的结点p=p->next;returnp;//找到后返回该结点指针，否则返回NULL}插入结点操作插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i-1个结点，再在其后插入新结点。

算法首先调用上面的按序号查找算法GetElem(L,

i-1)，查找第i-1个结点。假设返回的第i-1个结点为*p，然后令新结，点*s的指针域指向*p的后继结点，再令结点*p的指针域指向新插入的结点*s。其操作过程如图2-6所示。

图2-6

单链表的插入操作数据结构C语言算法大全全文共25页，当前为第6页。

数据结构C语言算法大全全文共25页，当前为第6页。p=GetElem(L,i-1);//语句①，查找插入位置的前驱结点s->next=p->next;//语句②，图2-6中辑作步骤1p->next=s;//语句③，图2-6中操作步骤2删除结点操作删除操作是将单链表的第i个结点删除。先检查删除位置的合法性，然后查找表中第i-1个结点，即被删结点的前驱结点，再将其删除。其操作过程如图2-7所示。

图2-7

单链表结点的删除

假设结点*p为找到的被删结点的前驱结点，为了实现这一操作后的逻辑关系的变化，仅需修改*p的指针域，即将*p的指针域next指向*q的下一结点。

实现删除结点的代码片段如下：p=GetElem(L,i-1);//查找删除位置的前驱结点q=p->next;//令q指向被删除结点p->next=q->next//将*q结点从链中“断开”free(q);//释放结点的存储空间数据结构C语言算法大全全文共25页，当前为第7页。和插入算法一样，该算法的主要时间也是耗费在查找操作上，时间复杂度为O(n)。

扩展：删除结点*p

要实现删除某一个给定结点*p，通常的做法是先从链表的头结点开始顺序找到其前驱结点，然后再执行删除操作即可，算法的时间复杂度为O(n)。

其实，删除结点*p的操作可以用删除*p的后继结点操作来实现，实质就是将其后继结点的值赋予其自身，然后删除后继结点，也能使得时间复杂度为O(1)。

实现上述操作的代码片段如下：数据结构C语言算法大全全文共25页，当前为第7页。q=p->next;//令q向*p的后继结点p->data=p->next->data;//和后继结点交换数据域p->next=q->next;//将*q结点从链中“断开”问题free(q);//释放后继结点的存储空间双链表双链表中结点类型的描述如下：typedefstructDNode{//定义双链表结点类型ElemTypedata;//数据域structDNode*prior,*next;//前驱和后继指针}DNode,*DLinklist;

双链表仅仅是在单链表的结点中增加了一个指向其前驱的prior指针，因此，在双链表中执行按值查找和按位查找的操作和单链表相同。但双链表在插入和删除操作的实现上，和单链表有着较大的不同。这是因为“链”变化时也需要对prior指针做出修改，其关键在于保证在修改的过程中不断链。此外，双链表可以很方便地找到其前驱结点，因此，插入、删除结点算法的时间复杂度仅为O(1)。数据结构C语言算法大全全文共25页，当前为第8页。数据结构C语言算法大全全文共25页，当前为第8页。在双链表中p所指的结点之后插入结点*s，其指针的变化过程如图2-9所示。

插入操作的代码片段如下：s->next=p->next;//语句①，将结点*s插入到结点*p之后p->next->prior=s;//语句②s->prior=p;//语句③p->next=s;//语句④

图2-9

双链表插入结点过程

上述代码的语句顺序不是唯一的，但也不是任意的，①②两步必须在④步之前，否则*p的后继结点的指针就丢掉了，导致插入失败。为了加深理解，读者可以在纸上画出示意图。若问题改成要求在结点*p之前插入结点*s，请读者思考具体的操作步骤。双链表的删除操作数据结构C语言算法大全全文共25页，当前为第9页。数据结构C语言算法大全全文共25页，当前为第9页。

图2-10

双链表删除结点过程

删除操作的代码片段如下：p->next=q->next;//图2-10中步骤①①q->next->prior=p;//图2-10中步骤②free(q);//释放结点空间栈的基本操作各种辅导书中给出的基本操作的名称不尽相同，但所表达的意思大致是一样的。这里我们以严蔚敏编写的教材为准给出栈的基本操作，希望读者能熟记下面的基本操作：

InitStack(&S)：初始化一个空栈S。

StackEmpty(S)：判断一个栈是否为空，若栈S为空返回true，否则返回false。

Push(&S,x)：进栈，若栈S未满，将x加入使之成为新桟顶。

Pop(&S,&x)：出栈，若栈S非空，弹出栈顶元素，并用x返回。

GetTop(S,&x)：读栈顶元素，若栈S非空，用x返回栈顶元素。

ClearStack(&S)：销毁栈，并释放栈S占用的存储空间。

注意：符号'&'是C++特有的，用来表示引用，有的书上釆用C语言中的指针类型‘*’，也可以达到传址的目的。

在解答算法题时，若题干没有做出限制，可以直接使用这些基本的操作函数。数据结构数据结构C语言算法大全全文共25页，当前为第10页。栈的顺序存储结构//-----栈的顺序存储表示-----

#defineSTACK_INIT_SIZE100;

#defineSTACKINCREMENT10;

typedefstruct{

SElemType*base;

SElemType*top;

intstacksize;

}SqStack;StatusInitStack(SqStack&S)

{//构造一个空栈S

S.base=(ElemType*)malloc(STACK_INIT_SIZE*

sizeof(ElemType));

if(!S.base)exit(OVERFLOW);//存储分配失败

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;

}数据结构C语言算法大全全文共25页，当前为第11页。

StatusPush(SqStack&S,SElemTypee){

if(S.top-S.base>=S.stacksize){//栈满，追加存储空间

S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

if(!S.base)exit(OVERFLOW);//存储分配失败

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

returnOK;

数据结构C语言算法大全全文共25页，当前为第11页。

StatusPop(SqStack&S,SElemType&e){

//若栈不空，则删除S的栈顶元素，

//用e返回其值，并返回OK；

//否则返回ERROR

if(S.top==S.base)returnERROR;

e=*--S.top;

returnOK;

}链队列：数据结构C语言算法大全全文共25页，当前为第12页。typedefstructQNode{//结点类型

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;

链队列——链式映象

typedefstruct{//链队列类型

QueuePtrfront;//队头指针

QueuePtrrear;//队尾指针

}数据结构C语言算法大全全文共25页，当前为第12页。StatusInitQueue(LinkQueue&Q){

//构造一个空队列Q

Q.front=Q.rear=

(QueuePtr)malloc(sizeof(QNode));

if(!Q.front)exit(OVERFLOW);

//存储分配失败

Q.front->next=NULL;

returnOK;

}数据结构C语言算法大全全文共25页，当前为第13页。

StatusEnQueue(LinkQueue&Q,

QElemTypee){

//插入元素e为Q的新的队尾元素

p=(QueuePtr)malloc(sizeof(QNode));

if(!p)exit(OVERFLOW);//存储分配失败

p->data=e;p->next=NULL;

Q.rear->next=p;Q.rear=p;

returnOK;

数据结构C语言算法大全全文共25页，当前为第13页。

StatusDeQueue(LinkQueue&Q,

QElemType&e){

//若队列不空，则删除Q的队头元素，

//用e返回其值，并返回OK；否则返回ERROR

if(Q.front==Q.rear)returnERROR;

p=Q.front->next;e=p->data;

Q.front->next=p->next;

if(Q.rear==p)Q.rear=Q.front;

free(p);returnOK;

}循环队列：数据结构C语言算法大全全文共25页，当前为第14页。#defineMAXQSIZE100//最大队列长度

typedefstruct{

QElemType*base;//动态分配存储空间

intfront;//头指针，若队列不空，

//指向队列头元素

intrear;//尾指针，若队列不空，指向

//队列尾元素的下一个位置

}数据结构C语言算法大全全文共25页，当前为第14页。

循环队列——顺序映象

StatusInitQueue(SqQueue&Q){

//构造一个空队列Q

Q.base=(ElemType*)malloc(MAXQSIZE*sizeof(ElemType));

if(!Q.base)exit(OVERFLOW);

//存储分配失败

Q.front=Q.rear=0;

returnOK;

}数据结构C语言算法大全全文共25页，当前为第15页。

StatusEnQueue(SqQueue&Q,ElemTypee)

{//插入元素e为Q的新的队尾元素

if((Q.rear+1)%MAXQSIZE==Q.front)

returnERROR;//队列满

Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%MAXQSIZE;

returnOK;

数据结构C语言算法大全全文共25页，当前为第15页。

StatusDeQueue(SqQueue&Q,ElemType&e)

{//若队列不空，则删除Q的队头元素，

//用e返回其值，并返回OK;否则返回ERROR

if(Q.front==Q.rear)returnERROR;

e=Q.base[Q.front];

Q.front=(Q.front+1)%MAXQSIZE;

returnOK;

}经典算法：行编辑while(ch!=EOF){//EOF为全文结束符while(ch!=EOF&&ch!='\n'){switch(ch){case'#':Pop(S,c);break;case'@':ClearStack(S);break;//重置S为空栈default:Push(S,ch);break;数据结构C语言算法大全全文共25页，当前为第16页。数据结构C语言算法大全全文共25页，当前为第16页。ch=getchar();//从终端接收下一个字符}2.从原表达式求得后缀式的规律为：

1)设立操作数栈；

2)设表达式的结束符为“#”，

予设运算符栈的栈底为“#”；

3)若当前字符是操作数，

则直接发送给后缀式。若当前运算符的优先数高于栈顶

运算符，则进栈；

5)否则，退出栈顶运算符发送给后

缀式；

6)“(”对它之前后的运算符起隔离

作用，“)”可视为自相应左括弧开始

的表达式的结束符。算法：数据结构C语言算法大全全文共25页，当前为第17页。voidtransform(charsuffix[],charexp[]){

InitStack(S);Push(S,#);

p=exp;ch=*p;

while(!StackEmpty(S)){

if(!IN(ch,OP))Pass(Suffix,ch);

else{}

if(ch!=#){p++;ch=*p;}

else{Pop(S,ch);Pass(Suffix,ch);}

}//while

}//CrtExptree

……

switch(ch){

case(:Push(S,ch);break;

case):Pop(S,c);

while(c!=()

{Pass(Suffix,c);Pop(S,c)}

break;

defult:

while(Gettop(S,c)&&(precede(c,ch)))

{Pass(Suffix,c);Pop(S,c);}

if(ch!=#)Push(S,ch);

break;

数据结构C语言算法大全全文共25页，当前为第17页。汉诺塔数据结构C语言算法大全全文共25页，当前为第18页。voidhanoi(intn,charx,chary,charz){

//将塔座x上按直径由小到大且至上而下编号为1至n

//的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。

1if(n==1)

2move(x,1,z);//将编号为１的圆盘从x移到z

3else{

4hanoi(n-1,x,z,y);//将x上编号为１至n-1的

//圆盘移到y,z作辅助塔

5move(x,n,z);//将编号为n的圆盘从x移到z

6hanoi(n-1,y,x,z);//将y上编号为１至n-1的

//圆盘移到z,x作辅助塔

7}

数据结构C语言算法大全全文共25页，当前为第18页。树：二叉树的顺序存储：#defineMAX_TREE_SIZE100//二叉树的最大结点数

typedefTElemTypeSqBiTree[MAX_

TREE_SIZE];//0号单元存储根结点

SqBiTreebt;二叉树的二叉链表存储：数据结构C语言算法大全全文共25页，当前为第19页。typedefstructBiTNode{//结点结构

TElemTypedata;

structBiTNode*lchild,*rchild;

//左右孩子指针

}BiTNode,*数据结构C语言算法大全全文共25页，当前为第19页。二叉树的三叉链表存储：typedefstructTriTNode{//结点结构

TElemTypedata;

structTriTNode*lchild,*rchild;

//左右孩子指针

structTriTNode*parent;//双亲指针

}TriTNode,*TriTree;二叉树的双亲链表存储：typedefstructBPTNode{//结点结构

TElemTypedata;

int*parent;//指向双亲的指针

charLRTag;//左、右孩子标志域

}BPTNode树的结构：数据结构C语言算法大全全文共25页，当前为第20页。typedefstructBPTree{//树结构

BPTNodenodes[MAX_TREE_SIZE];

intnum_node;//结点数目

introot;//根结点的位置

}数据结构C语言算法大全全文共25页，当前为第20页。树的先序遍历：voidPreorder(BiTreeT,

void(*visit)(TElemType&e))

{//先序遍历二叉树

if(T){

visit(T->data);//访问结点

Preorder(T->lchild,visit);//遍历左子树

Preorder(T->rchild,visit);//遍历右子树

}

}树的中序遍历递归算法：voidInorder(BiTreeT,void(*visit)(TElemType&e))

{//中序遍历二叉树

if(T){数据结构C语言算法大全全文共25页，当前为第21页。Inorder(T->lchild,visit);//遍历左子树

visit(T->data);//访问结点

Inorder(T->rchild,visit);//遍历右子树

}

数据结构C语言算法大全全文共25页，当前为第21页。树的中序遍历非递归算法：数据结构C语言算法大全全文共25页，当前为第22页。BiTNode*GoFarLeft(BiTreeT,Stack*S){

if(!T)returnNULL;

while(T->lchild){

Push(S,T);

T=T->lchild;

}

returnT;

}

voidInorder_I(BiTreeT,void(*visit)

(TelemType&e)){

Stack*S;

t=GoFarLeft(T,S);//找到最左下的结点

while(t){

visit(t->data);

if(t->rchild)

t=GoFarLeft(t->rchild,S);

elseif(!StackEmpty(S))//栈不空时退栈

t=Pop(S);

elset=NULL;//栈空表明遍历结束

}//while

}//数据结构C语言算法大全全文