四川省建设质量工程协会网站网站建设主

四川省建设质量工程协会网站,网站建设主,网站建设方案书doc模板,wordpress主题 制作教程1.栈是一种只能在一端进行插入和删除的线性表2.先构建一个数据类型#xff0c;里面有next,data,top(可有可无#xff09;typedef struct LNode {int top;//初始化的时候top等于-1#xff0c;只有有数据就让top1,这个数据项可有可无struct LNode* next;//和单链表一样int dat…1.栈是一种只能在一端进行插入和删除的线性表2.先构建一个数据类型里面有next,data,top(可有可无typedef struct LNode { int top;//初始化的时候top等于-1只有有数据就让top1,这个数据项可有可无 struct LNode* next;//和单链表一样 int data;//数据域 }LNode,*LinkStack;//重命名3.链栈的初始化void InitStack(LinkStack* Ps) { (*Ps) (LinkStack)malloc(sizeof(LNode));//创建头节点不存放数据 if ((*Ps) NULL) return; (*Ps)-next NULL;//养成良好的习惯表尾置为空 (*Ps)-top -1;//说明此时是没有元素的 }4.从头节点进栈这种时间复杂度比较高效每次进栈时间复杂度为O1int HeadPush(LinkStack* Ps, int elem)//前插 { LNode* s (LNode*)malloc(sizeof(LNode));//和单链表一样 if (s NULL) return 1; s-data elem;//把数据赋值给新开辟的节点 s-next(*Ps)-next;//把头节点的下一个元素赋值给s节点就是把s的后驱链接到头节点的后驱 (*Ps)-next s;//把头节点的后驱改为s,这样就把s节点给插入到表头的后面 s-top 1;//可有可无 return 0; }5.从头节点出栈这种时间复杂度比较高效每次出栈时间复杂度为O1int HeadPop(LinkStack* Ps)//前删 { if ((*Ps)-next NULL) { return 1; } LNode*temp(*Ps)-next;//删除头节点的下一个节点 (*Ps)-next temp-next;//把头节点的下一个节点指向下下个节点跳过一个节点 if (temp-next NULL) { (*Ps)-top -1;//说明此时没有元素可有可无 } free(temp);//因为是动态内存开辟的是放在栈区的需要手动释放 return 0; }6.尾节点的进栈可以一次性进栈也可以每次进栈一个元素。只需要找到最后一个非空的节点在后面插入一个元素就可以了。int TailPush(LinkStack* Ps)//这是一次性全部个建立好 { LNode* tail (*Ps); int x 0; scanf(%d, x); while (x ! 99)//等于99就不在建立 { LNode* s (LNode*)malloc(sizeof(LNode)); if (s NULL) return 1; s-next tail-next; s-data x; s-top 1; tail-next s; tail s; scanf(%d, x); } tail-next NULL; return 0; }int TailPush(LinkStack* Ps,int elem)//尾插法这种办法有点笨需要每次找到倒数第一个节点 { LNode* p GetTail(Ps);//找到倒数第一个非空节点然后在后面插入一个数据 LNode* s (LNode*)malloc(sizeof(LNode)); if (s NULL) { return 1; } s-next p-next; p-next s; s-top 1; s-data elem; return 0; }7.尾节点出栈。需要找到倒数第二个元素然后进行删除当链表只有一个元素这种情况要考虑一下int TailPop(LinkStack* Ps) { if (NULL (*Ps)-next) return -1; if ((*Ps)-next-next NULL)//如果这个链表只有一个元素 { LNode* ptr (*Ps)-next; (*Ps)-next ptr-next; free(ptr); return 0; } LNode* ptr (*Ps); while (ptr-next-next)//链表有两个以上的元素 { ptr ptr-next; } LNode* temp ptr-next; ptr-next temp-next; free(temp);//需要释放 }8.得到栈顶元素由于可以通过尾插法和头插法两种方式所以分别对应一种方式int Gettop(LinkStack* Ps)//头插法找top { if ((*Ps)-next NULL) { return -1; } return (*Ps)-next-data;//既可以返回数据也可以判断是不是空链表 }//链式存储没有存满的LNode* GetTail(LinkStack* Ps)//尾插法找top { LNode* p (*Ps); while (p-next) { p p-next; } return p;//是倒数最后一个指针 }9.打印链表元素的函数void Destory(LinkStack* Ps) { int ret 0; while (ret!1) { ret HeadPop(Ps);//HeadPop出栈成功会返回0空栈会返回1 } free(*Ps); }10.整体函数typedef struct LNode { int top;//初始化的时候top等于-1只有有数据就让top1,这个数据项可有可无 struct LNode* next;//和单链表一样 int data;//数据域 }LNode,*LinkStack;//重命名 void InitStack(LinkStack* Ps) { (*Ps) (LinkStack)malloc(sizeof(LNode));//创建头节点不存放数据 if ((*Ps) NULL) return; (*Ps)-next NULL;//养成良好的习惯表尾置为空 (*Ps)-top -1;//说明此时是没有元素的 } int HeadPush(LinkStack* Ps, int elem)//前插 { LNode* s (LNode*)malloc(sizeof(LNode));//和单链表一样 if (s NULL) return 1; s-data elem;//把数据赋值给新开辟的节点 s-next(*Ps)-next;//把头节点的下一个元素赋值给s节点就是把s的后驱链接到头节点的后驱 (*Ps)-next s;//把头节点的后驱改为s,这样就把s节点给插入到表头的后面 s-top 1;//可有可无 return 0; } int HeadPop(LinkStack* Ps)//前删 { if ((*Ps)-next NULL) { return 1; } LNode*temp(*Ps)-next;//删除头节点的下一个节点 (*Ps)-next temp-next;//把头节点的下一个节点指向下下个节点跳过一个节点 if (temp-next NULL) { (*Ps)-top -1;//说明此时没有元素可有可无 } free(temp);//因为是动态内存开辟的是放在栈区的需要手动释放 return 0; } int TailPush(LinkStack* Ps)//这是一次性全部个建立好 { LNode* tail (*Ps); int x 0; scanf(%d, x); while (x ! 99)//等于99就不在建立 { LNode* s (LNode*)malloc(sizeof(LNode)); if (s NULL) return 1; s-next tail-next; s-data x; s-top 1; tail-next s; tail s; scanf(%d, x); } tail-next NULL; return 0; } LNode* GetTail(LinkStack* Ps)//尾插法找top { LNode* p (*Ps); while (p-next) { p p-next; } return p;//是倒数最后一个指针 } int TailPush(LinkStack* Ps,int elem)//尾插法这种办法有点笨需要每次找到倒数第一个节点 { LNode* p GetTail(Ps);//找到倒数第一个非空节点然后在后面插入一个数据 LNode* s (LNode*)malloc(sizeof(LNode)); if (s NULL) { return 1; } s-next p-next; p-next s; s-top 1; s-data elem; return 0; } int TailPop(LinkStack* Ps) { if (NULL (*Ps)-next) return -1; if ((*Ps)-next-next NULL)//如果这个链表只有一个元素 { LNode* ptr (*Ps)-next; (*Ps)-next ptr-next; free(ptr); return 0; } LNode* ptr (*Ps); while (ptr-next-next)//链表有两个以上的元素 { ptr ptr-next; } LNode* temp ptr-next; ptr-next temp-next; free(temp);//需要释放 } void Display(LinkStack* Ps) { LNode* p (*Ps)-next; while (p) { printf(%d-, p-data); p p-next; } printf(NULL\n); } int Gettop(LinkStack* Ps)//头插法找top { if ((*Ps)-next NULL) { return -1; } return (*Ps)-next-data;//既可以返回数据也可以判断是不是空链表 }//链式存储没有存满的 void Destory(LinkStack* Ps) { int ret 0; while (ret!1) { ret HeadPop(Ps);//HeadPop出栈成功会返回0空栈会返回1 } free(*Ps); } int main() { LinkStack L; InitStack(L); //HeadPush(L, 1); //HeadPush(L, 2); //HeadPush(L, 3); //Display(L); //HeadPop(L); //HeadPop(L); //HeadPop(L); TailPush(L,1); TailPush(L, 1); TailPush(L, 1); TailPush(L,1); Display(L); TailPop(L); TailPop(L); TailPop(L); TailPop(L); Display(L); int retGettop(L); if (ret -1) { printf(空链表\n); } else { printf(%d\n, ret); } return 0; }