数据结构算法复习笔记.docx
《数据结构算法复习笔记.docx》由会员分享，可在线阅读，更多相关《数据结构算法复习笔记.docx（132页珍藏版）》请在冰点文库上搜索。
数据结构算法复习笔记
1.链表[重点]
1）单链表的操作
1）建立单链表：
头插法建表和尾插法建表两种
typedefintdatatype;
typedefstructnode{
datatypedata;
structnode*next;
}LINKNODE;
/*头插入法建表*/
LINKNODE*createlinklistfromhead（）{
charch;
LINKNODE*head,*curr;
head=NULL;
ch=getchar（）;
while（ch!
='$'）{
curr=（LINKNODE*）malloc（sizeof（LINKNODE））;
if（!
curr）
returnNULL;
curr->data=ch;
curr->next=head;
head=curr;
ch=getchar（）;
}
returnhead;
}
/*尾插入法建表*/
LINKNODE*createlinklistfromtail（）{
charch;
LINKNODE*head,*tail,*curr;
head=NULL;
tail=NULL;
ch=getchar（）;
while（ch!
='$'）{
curr=（LINKNODE*）malloc（sizeof（LINKNODE））;
if（!
curr）
returnNULL;
curr->data=ch;
curr->next=NULL;
if（NULL==head）{
head=curr;
}else
tail->next=curr;
tail=curr;
ch=getchar（）;
}
returnhead;
}
2）查找运算：
/*按值查找，找到则返回该结点；否则返回NULL*/
LINKNODE*locate（LINKNODE*head,datatypekey）{
LINKNODE*curr=head;
while（curr->data!
=key&&NULL!
=curr）
curr=curr->next;
returncurr;//这里可以返回局部指针变量，是因为curr指向链表结点，它不会因为函数返回而撤销
}
3）插入结点：
后插和前插两种
/*在当前指针curr之后插入一值为value的结点。
成功返回0；否则返回1*/
intinsertafternode（LINKNODE*curr,datatypevalue）{
LINKNODE*newnode=（LINKNODE*）malloc（sizeof（LINKNODE））;
if（!
newnode）
return1;
newnode->data=value;
newnode->next=curr->next;
curr->next=newnode;
return0;
}
/*在当前指针curr之前插入一值为value的结点。
成功返回0；否则返回1*/
intinsertbeforenode（LINKNODE*head,LINKNODE*curr,datatypevalue）{
LINKNODE*pre=head;
LINKNODE*newnode=（LINKNODE*）malloc（sizeof（LINKNODE））;
if（!
newnode）
return1;
newnode->data=value;
if（curr==head）{
newnode->next=curr;
head=newnode;
}else{
while（pre->next!
=curr）
pre=pre->next;
newnode->next=curr;
pre->next=newnode;
}
return0;
}
4）删除结点：
/*删除值为value的结点，成功则返回0；失败返回1*/
intdeletenode（LINKNODE*head,datatypevalue）{
LINKNODE*curr,*pre=head;
if（!
（curr=locate（head,value）））{
cout<<"Havenotfoundthenodeinthelinklist"<return0;
}
if（curr==head）{
head=curr->next;
}else{
while（pre->next!
=curr）
pre=pre->next;
pre->next=curr->next;
}
free（curr）;
curr=NULL;
return0;
}
2）循环链表
尾指针tail指向头指针head，若表的插入和删除主要发生在表的首尾两端，宜采用尾指针表示的单循环链表。
3）双向链表
/*双向链表：
在当前指针curr之前插入一值为value的结点。
成功返回0；否则返回1*/
intinsertbeforenode（DLINKNODE*curr,datatypevalue）{
DLINKNODE*newnode=（DLINKNODE*）malloc（sizeof（DLINKNODE））;
if（!
newnode）
return1;
newnode->data=value;
newnode->next=curr;
newnode->pre=curr->pre;
curr->pre->next=newnode;
curr->pre=newnode;
return0;
}
/*双向链表：
删除结点curr，成功返回0；否则返回1*/
intdeletednode（DLINKNODE*curr）{
if（!
curr）
return1;
curr->pre->next=curr->next;
curr->next->pre=curr->pre;
free（curr）;
return0;
}
4）静态链表
data
next
0
1
1
2
2
3
av
3
4
1
4
5
…
maxsize-1
maxsize-1
NULL
STATICLINKNODEnodepool[maxsize];
cursorav;//标识nodepool中当前可用结点的下标
cursortail;
1）建表
/*初始化存储池nodepool，起始游标av=1;成功返回0；否则返回1*/
intinitialize（）{
intindex=0;
for（index=0;indexnodepool[index].next=index+1;
nodepool[maxsize-1].next=NULL;
av=1;//nodepool[0]不用
tail=1;
return0;
}
注意：
已使用的结点和未使用的结点都在nodepool存储池中，未使用的存储池首结点下标用av记录。
静态链表的首结点下标用head记录，尾结点下标用tail记录，当前结点下标用curr记录。
/*从存储池nodepool中分配一个结点，返回分配到的可用结点*/
cursorgetnode（）{
cursorcurr;
if（av==NULL）
curr=NULL;
else{
curr=av;
av=nodepool[av].next;
}
returncurr;
}
/*将curr所指向的结点归还nodepool；成功返回0；否则返回1*/
intfreenode（cursorcurr）{
nodepool[curr].next=av;
av=curr;
return0;
}
2）查找运算
/*在带头结点的静态链表head中查找值为value的结点，找到则返回该结点的游标值；否则返回NULL*/
cursorfindslinklist（cursorhead,datatypevalue）{
cursorcurr=head;
while（curr!
=tail&&nodepool[curr].data!
=value）
curr=nodepool[curr].next;
if（nodepool[curr].data==value）
returncurr;
elsereturnNULL;
}
/*在带头结点的静态链表head中查找第loc个结点*/
cursorfindslinklistbyloc（cursorhead,intloc）{
cursorcurr=head;
intindex=0;
while（（nodepool[curr].next!
=NULL）&&（indexcurr=nodepool[curr].next;
index++;
}
if（index==loc）
returncurr;
else
returnNULL;
}
3）插入结点：
/*在带头结点的静态链表head的第loc个结点之前插入值为value的结点；成功返回0；否则返回1*/
intinsertslinklist（cursorhead,datatypevalue,intloc）{
cursorcurrpre,newnode;
currpre=findslinklistbyloc（head,loc-1）;//查找第loc-1个位置的结点
if（NULL==currpre）//插入位置越界
return1;
newnode=getnode（）;
if（NULL==newnode）
return1;
nodepool[newnode].data=value;
nodepool[newnode].next=nodepool[currpre].next;
nodepool[currpre].next=newnode;
tail=newnode;//?
?
?
不对吧
return0;
}
4）删除结点：
/*删除带头结点的静态链表head的第loc个结点；成功返回0；否则返回1*/
intdeleteslinklist（cursorhead,intloc）{
cursorcurrpre,curr;
currpre=findslinklistbyloc（head,loc-1）;
if（（NULL!
=currpre）&&（NULL!
=nodepool[currpre].next））{
curr=nodepool[currpre].next;
nodepool[currpre].next=nodepool[curr].next;
freenode（curr）;
return0;
}else
return1;//删除位置越界
}
2.栈
1）顺序栈
#definemax_size64
typedefchardata_type;
/*顺序栈结构：
栈空时top=-1,栈满时top=max_size-1,top是栈顶元素游标*/
typedefstruct{
data_typedata[max_size];
inttop;
}SEQ_STACK;
1）置空栈
/*置空栈*/
boolsetnull（SEQ_STACK*s）{
s->top=-1;
returntrue;
}
2）判栈空
/*判栈空*/
boolempty（constSEQ_STACK*s）{
if（s->top>=0）
returnfalse;
else
returntrue;
}
3）判栈满
/*判栈满*/
boolfull（constSEQ_STACK*s）{
if（s->top==max_size-1）
returntrue;
else
returnfalse;
}
4）入栈
/*进栈*/
SEQ_STACK*push（SEQ_STACK*s,data_typex）{
if（full（s））{
cout<<"seq_stackisfull!
pushoperationfailed!
"<returnNULL;
}else{
s->top++;
s->data[s->top]=x;
}
returns;
}
5）出栈
/*退栈*/
data_typepop（SEQ_STACK*s）{
if（empty（s））{
cout<<"seq_stackisempty!
popoperationfailed!
"<returnNULL;
}else{
s->top--;
returns->data[s->top+1];//orinelseuse:
returns->data[s->top--];
}
}
6）取栈顶元素
/*取栈顶元素*/
data_typegettop（constSEQ_STACK*s）{
if（empty（s））{
cout<<"stackisempty!
"<returnNULL;
}else
returns->data[s->top];
}
2）链栈
/*链栈结构：
top指向栈顶，top==NULL时栈空*/
typedefstructnode{
data_typedata;
node*next;
}LINK_STACK;
1）入栈
/*将元素x插入栈顶top的顶部*/
LINK_STACK*pushlinkstack（LINK_STACK*top,data_typex）{
LINK_STACK*p;
if（NULL!
=（p=（LINK_STACK*）malloc（sizeof（LINK_STACK））））{
p->data=x;
p->next=top;
top=p;
//cout<<"x="<}
returntop;
}
2）出栈
/*删除链表top的顶部结点，datap为出栈元素的值*/
LINK_STACK*poplinkstack（LINK_STACK*top,data_type*datap）{
LINK_STACK*p;
if（NULL==top）{
cout<<"link_stackisempty!
"<returnNULL;
}else{
*datap=top->data;
p=top;
top=top->next;
free（p）;
returntop;
}
}
3.队列
1）顺序队列（对循环队列的情况）
#definemax_size64
typedefintdata_type;
/*
*顺序队列结构：
front指向队头元素的前一个位置，rear指向队尾元素的位置
*队列初始化：
头尾指针都指向向量空间下界的前一个位置-1
*队空：
sq->front==sq->rear;
*队满：
sq->rear-sq->front==max_size;
**/
typedefstruct{
data_typedata[max_size];
intfront,rear;
}SEQUEUE;
/*
*以下操作针对循环顺序队列，始終有一个元素（sq->data[sq->front]）是空的。
*队空：
sq->front==sq->rear;
*队满：
（sq->rear+1）%max_size==sq->front
**/
1）置空队列
/*置空循环顺序队列*/
boolsetnull（SEQUEUE*sq）{
sq->front=max_size-1;
sq->rear=max_size-1;
returntrue;
}
2）判队空
/*判循环顺序队列空*/
boolempty（SEQUEUE*sq）{
if（sq->rear==sq->front）
returntrue;
else
returnfalse;
}
3）取队首元素
/*取循环顺序队列头结点元素*/
data_typefront（SEQUEUE*sq）{
if（empty（sq））{
cout<<"Queueisempty!
"<returnNULL;
}else
returnsq->data[（sq->front+1）%max_size];
}
4）入队
/*将新元素x插入队列尾部，在空循环队列中插入第一个元素时，sq->rear指向1，sq->front指向max_size-1*/
boolenqueue（SEQUEUE*sq,data_typex）{
if（sq->front==（sq->rear+1）%max_size）{
cout<<"Queueisfull!
"<returnNULL;
}else{
sq->rear=（sq->rear+1）%max_size;
sq->data[sq->rear]=x;
returntrue;
}
}
5）出队
/*删除队列头结点元素，并返回该元素值*/
data_typedequeue（SEQUEUE*sq）{
if（empty（sq））{
cout<<"Queueisempty!
"<returnNULL;
}else{
sq->front=（sq->front+1）%max_size;
returnsq->data[sq->front];
}
}
2）链队列
typedefstructnode{
data_typedata;
node*next;
}LINKQUEUENODE;
typedefstruct{
LINKQUEUENODE*front,*rear;
}LINKQUEUE;
1）生成空队列
/*生成空链队列，队头附加了头结点（队首结点的前一个结点），且头指针指向头结点*/
boolsetnull（LINKQUEUE*lq）{
lq->front=（LINKQUEUENODE*）malloc（sizeof（LINKQUEUENODE））;
lq->front->next=NULL;
lq->rear=lq->front;
returntrue;
}
2）判队空
/*判链队列空*/
boolempty（LINKQUEUE*lq）{
if（lq->rear==lq->front）
returntrue;
else
returnfalse;
}
3）取队首元素
/*取出链队列的队头元素*/
data_typefront（LINKQUEUE*lq）{
if（empty（lq））{
cout<<"LINKQueueisempty!
"<returnNULL;
}else
returnlq->front->next->data;//lq->front是头结点,lq->front->next是队首结点
}
4）入队
/*将新元素x插入队列尾部*/
boolenqueue（LINKQUEUE*lq,data_typex）{
if（NULL!
=（lq->rear->next=（LINKQUEUENODE*）malloc（sizeof（LINKQUEUENODE））））{
lq->rear=lq->rear->next;
lq->rear->data=x;
lq->rear->next=NULL;
returntrue;
}else{
returnfalse;
}
}
5）出队
/*删除队列头结点元素，并返回该元素值。
采用将队首元素作为新的头结点，然后释放原来的头结点*/
data_typedequeue（LINKQUEUE*lq）{
if（empty（lq））{
cout<<"LINKQueueisempty!
"<returnNULL;
}else{
LINKQUEUENODE*s;
s=lq->front;//lq->front是头结点
lq->front=lq->front->next;//lq->front->next是队首结点
free（s）;
returnlq->front->data;
}
}
4.串
1）顺序串上的子串定位运算
/*串的顺序存储*/
typedefstruct{
charch[maxsize];
intcurlen;//当前串的长度
}SEQSTRING;
/*
升级会员 