数据结构（双语）08-第三章-Stacks-Linked

DataStructure

数据结构计算机与信息技术系袁莹2019年03月22日TheListADT1.SimpleArrayimplementationofLists2.LinkedListsCreateInsertionDeletionFind/Get/AccessReview#defineMAXSIZE1024typedefint

DataType;typedef

struct{ DataType

data[MAXSIZE]; int

last; }SeqList;SequentialListsLinkedListstypedef

struct

node{ DataTypedata; structnode*next;}LNode,*Link_List;Link_ListCreateList(intn){ Link_ListL; LNode*p; L=(Link_List)malloc(sizeof(LNode)); L->next=NULL; for(inti=n;i>0;i--) {p=(Link_List)malloc(sizeof(LNode));

printf("请输入第%d个元素：",i); scanf("%d",&p->data); p->next=L->next; L->next=p;}

printf("单链表创建成功\n"); returnL;}CreateListtypedef

struct

node{ DataTypedata; structnode*next;}LNode,*Link_List;a1ptrNULLaiai+1an......Insertionpbss->next=p->nextp->next=s

takesO(1)time.5/18在第i个位置(即结点p后面)插入值为x的结点voidInsert(Link_ListL,inti,elementTypex){ intj; LNode*p; p=L; j=0; while(p&&(j<i-1)) { p=p->next; j++; } if(p&&(j<i)) { Link_Listq; s=(Link_List*)malloc(sizeof(Link_List));

s->data=x; s->next=p->next; p->next=s; printf("元素插入成功\n"); } else { printf(“Positiondosenotexist\n”);

}}typedef

struct

node{ DataTypedata; structnode*next;}LNode,*Link_List;找到第i-1个结点(p)的位置Deletiona1ptrNULLaiai+1an......bprenodepre->next=node->nextfree(node)bnode

takesO(1)time.删除第i个结点(即结点p后面的结点q)voidDelete(Link_ListL,inti){ intj; LNode*p; p=L; j=0; while(p->next&&(j<i-1))

{ p=p->next; j++; } if(p->next&&(j<i)) { LNode*q;

q=p->next; p->next=q->next; free(q); printf("删除元素成功\n"); } else printf(“Positiondoesnotexist\n”); }typedef

struct

node{ DataTypedata; structnode*next;}LNode,*Link_List;找到第i-1个结点(p)的位置3.3TheStackADT3.3.1.StackModel1234566565

AstackisaLast-In-First-Out(LIFO)list,thatis,anorderedlistinwhichinsertionsanddeletionsaremadeatthetoponly.Operations:IntIsEmpty(StackS);StackCreateStack();DisposeStack(StackS);MakeEmpty(StackS);Push(ElementTypeX,StackS);ElementTypeTop(StackS);Pop(StackS);Note:APop

(or

Top)onanemptystackisanerrorinthestackADT.

PushonafullstackisanimplementationerrorbutnotanADTerror.1、Linked

List

Implementation2、Array

Implementation3.3.2ImplementationofStacksNULLElementElementElementSStypedefintElementType;typedefstructNode{ ElementTypeElement; structNode*Next;}*Stack;Type

declaration1、LinkedListImplementation(withaheadernode)LinkedListImplementation(withaheadernode)Sint

IsEmpty

(Stack

S)

{ return

S->Next

==

NULL;};test

whether

a

stack

is

emptyLinkedListImplementation(withaheadernode)Stack

CreatStack

( ){ Stack

S; S=(Stack)malloc(sizeof(struct

Node)); if(S

==

NULL) return

Error; S->Next

=

NULL; return

S;}create

an

empty

stackSLinkedListImplementation(withaheadernode)NULLElementElementElement

Push:TmpCell->Next=S->NextS->Next=TmpCell

Top:FirstCell=S->NextS->Next=S->Next->Nextfree(FirstCell)returnS->Next->ElementSElementTmpCellS

Pop:ElementFirstCellSBut,thecallstomallocandfree

areexpensive.Easy!Simplykeepanotherstackasarecyclebin.PushvoidPush(ElementTypeX,StackS){StackTmpCell;TmpCell=malloc(sizeof(structNode));if(TmpCell==NULL)returnERROR;/*申请新结点失败，返回错误标志*/

TmpCell->Element=X;TmpCell->Next=S->Next;S->Next=TmpCell;}LinkedListImplementation(withaheadernode)TopElementTypeTop(StackS)/*将栈顶元素出栈*/{if(!IsEmpty(S)) returnS->Next->Element;returnERROR;/*栈空，返回错误标志*/}LinkedListImplementation(withaheadernode)PopvoidPop(StackS){ StackFirstCell; if(IsEmpty(S)) returnERROR; else {

FirstCell=S->Next; S->Next=S->Next->Next; free(FirstCell);}}ReadFigures3.39-3.44fordetailedimplementationsofstackoperations.LinkedListImplementation(withaheadernode)2、Array

Implementationtypedef

structStackRecord{

intTopOfStack;/*thetoppointer*/ /*++forpush,--forpop,-1foremptystack*/ ElementTypeArray[MAXSIZE];

/*arrayforstackelements*/}*SeqStack;Note:ErrorcheckmustbedonebeforePushorPop(Top).类型声明#defineMAXSIZE100typedefintElementType;typedefstruct{ intTopOfStack; ElementTypeArray[MAXSIZE];}*SeqStack;ArrayImplementation2、Array

Implementation初始化SeqStackinitSeqStack(){SeqStacks;s=(SeqStack)malloc(sizeof(SeqStack));s->TopOfStack=-1;returns;}ArrayImplementationPush入栈voidPush(SeqStacks,ElementTypex){

if(s->TopOfStack==MAXSIZE-1)/*栈满溢出*/printf("overflow");else

s->Array[++s->TopOfStack]=x;

/*入栈*/}ArrayImplementationTop返回栈顶元素ElementTypeTop(SeqStacks){return s->Array[s->TopOfStack];}ArrayImplementationPop出栈voidPop(SeqStacks){

if(s->TopOfStack==-1) printf("StackisNULL"); else

s->TopOfStack--;}ArrayImplementationReadFigures3.45-3.53fordetailedimplementationsofstackoperations.SummaryAstackisaLast-In-First-Out(LIFO)list,thatis,anorderedlistinwhichinsertionsanddeletionsaremadeatthetoponly.Operations:IntIsEmpty(StackS);StackCreateStack();DisposeStack(StackS);MakeEmpty(StackS);Push(ElementTypeX,StackS);ElementTypeTop(StackS);Pop(StackS);p29(9)1、假设某个不设头指针的无头结点单向循环链表的长度