|
栈是一种特殊的线性表，只能对线性表的一端进行操作。 链栈所以可以使用链式线性表来实现栈 =============================================================================== linklist.h ============================================================= #ifndef _MYLINKLIST_H_
#define _MYLINKLIST_H_
typedef void LinkList;
/*
typedef struct _tag_LinkListNode LinkListNode;
struct _tag_LinkListNode
{
LinkListNode* next;
};
*/
typedef struct _tag_LinkListNode
{
struct _tag_LinkListNode* next;
}LinkListNode;
LinkList* LinkList_Create();
void LinkList_Destroy(LinkList* list);
void LinkList_Clear(LinkList* list);
int LinkList_Length(LinkList* list);
int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);
LinkListNode* LinkList_Get(LinkList* list, int pos);
LinkListNode* LinkList_Delete(LinkList* list, int pos);
#endif
|
============================================================== linkstack.h ==============================================================
#ifndef _MY_LINKSTACK_H
#define _MY_LINKSTACK_H
typedef void LinkStack;
LinkStack* LinkStack_Create();
void LinkStack_Destroy(LinkStack* lstack);
void LinkStack_Clear(LinkStack* lstack);
int LinkStack_Push(LinkStack* lstack, void* item);
LinkStack* LinkStack_Top(LinkStack* lstack);
LinkStack* LinkStack_Pop(LinkStack* lstack);
int LinkStack_Size(LinkStack* lstack);
#endif // _MY_LINKSTACK_H
|
============================================================== linklist.c ==============================================================
#include<stdio.h>
#include "stdlib.h"
#include "string.h"
#include "linklist.h"
typedef struct _tag_LinkList
{
//这个句柄里面，需要保存所有节点信息。需要有一个起始点
//就是带头节点的链表。。。
LinkListNode header;
int length;
}TLinkList;
LinkList* LinkList_Create()
{
TLinkList *ret = (TLinkList *)malloc(sizeof(TLinkList));
if (ret == NULL)
{
return NULL;
}
//memset(ret, 0, sizeof(TLinkList));
ret->header.next = NULL;
ret->length = 0;
return ret;
}
void LinkList_Destroy(LinkList* list)
{
if (list == NULL)
{
return ;
}
free(list);
return ;
}
void LinkList_Clear(LinkList* list)
{
TLinkList *tList =NULL;
if (list == NULL)
{
return ;
}
tList = (TLinkList *)list;
tList->length = 0;
tList->header.next = NULL;
return ;
}
int LinkList_Length(LinkList* list)
{
TLinkList *tList = (TLinkList *)list;
if (tList == NULL)
{
return -1;
}
return tList->length;
}
int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
{
int i = 0;
TLinkList *tList = NULL;
LinkListNode *current = NULL;
tList = (TLinkList *)list;
//准备环境让辅助指针变量 指向链表头节点
current = &tList->header;
for (i=0; i<pos &&(current->next!=NULL); i++)
{
current = current->next;
}
//让node节点链接后续链表
node->next = current->next ;
//让前边的链表。链接node
current->next = node;
tList->length ++;
return 0;
}
LinkListNode* LinkList_Get(LinkList* list, int pos)
{
int i = 0;
TLinkList *tList = NULL;
LinkListNode *current = NULL;
LinkListNode *ret = NULL;
tList = (TLinkList *)list;
if (list == NULL || pos <0 ||pos>=tList->length)
{
return NULL;
}
//准备环境让辅助指针变量 指向链表头节点
current = &tList->header;
for (i=0; i<pos &&(current->next!=NULL); i++)
{
current = current->next;
}
ret = current->next;
return ret;
}
LinkListNode* LinkList_Delete(LinkList* list, int pos)
{
int i = 0;
TLinkList *tList = NULL;
LinkListNode *current = NULL;
LinkListNode *ret = NULL;
tList = (TLinkList *)list;
if (list == NULL || pos <0 ||pos>=tList->length)
{
return NULL;
}
//准备环境让辅助指针变量 指向链表头节点
current = &tList->header;
for (i=0; i<pos &&(current->next!=NULL); i++)
{
current = current->next;
}
ret = current->next;
//删除算法
current->next =ret->next;
tList->length--;
return ret;
}
|
============================================================== linkstack.c ============================================================== #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "linkstack.h"
#include "linklist.h"
typedef struct _tag_LinkStackNode
{
LinkListNode node; //占位结构。。。只要定义一个和node节大小一样的数据即可
void* item;
}TLinkStackNode;
//我要创建一个linkstack，准备用linklist去模拟实现
//相当于在 linkstack.c中写 linklist库的测试程序。。。。。。
LinkStack* LinkStack_Create()
{
//创建一个栈，通过线性表去模拟。。。（创建一个栈，相当于创建一个线性表）
return LinkList_Create();
}
void LinkStack_Destroy(LinkStack* lstack)
{
LinkStack_Clear(lstack); //注意 destory的时候，需要把栈中的所有元素都清空
LinkList_Destroy(lstack);
}
void LinkStack_Clear(LinkStack* lstack)
{
while(LinkStack_Size(lstack) > 0)
{
LinkStack_Pop(lstack); //在这个函数里面有内存释放函数
}
return;
}
//向栈中放元素，相当于 向线性表中插入一个元素
int LinkStack_Push(LinkStack* lstack, void* item)
{
int ret = 0;
//需要item数据，转换成 linklist的业务节点
TLinkStackNode *pTe = (TLinkStackNode *)malloc(sizeof(TLinkStackNode));
if(pTe == NULL)
{
return -1;
}
pTe->item = item;
//头插法 ，向线性表中插入元素，只不过是插入元素的时候，需要构造业务节点而已。。。。。。
//ret = LinkList_Insert(lstack, (LinkListNode*)(&pTe->node), 0);
ret = LinkList_Insert(lstack, (LinkListNode*)(pTe), 0);
if(ret != 0)
{
free(pTe);
}
return ret;
}
LinkStack* LinkStack_Top(LinkStack* lstack)
{
void* myItem = NULL;
TLinkStackNode* tmp = NULL;
tmp = (TLinkStackNode*)LinkList_Get(lstack, 0);
if(tmp == NULL)
{
return NULL;
}
myItem = tmp->item;
return myItem;
}
LinkStack* LinkStack_Pop(LinkStack* lstack)
{
void* myItem = NULL;
TLinkStackNode* tmp = NULL;
tmp = (TLinkStackNode*)LinkList_Delete(lstack, 0);
if(tmp == NULL)
{
return NULL;
}
myItem = tmp->item;
//注意向线性表中，插入元素的时，打造节点，分配内存；
//弹出元素时，需要释放节点内存，不要忘记
if(tmp != NULL)
{
free(tmp);
}
return myItem;
}
int LinkStack_Size(LinkStack* lstack)
{
return LinkList_Length(lstack);
}
|
============================================================== linkstack_test.c ============================================================== #include <stdio.h>
#include <stdlib.h>
#include "linkstack.h"
int main()
{
int a[10], i;
LinkStack* lstack = NULL;
lstack = LinkStack_Create();
for(i = 0; i < 10; i++)
{
a[i] = i + 1;
LinkStack_Push(lstack, &a[i]);
}
printf("top : %d \n", *((int *)(LinkStack_Top(lstack))));
printf("size : %d \n", LinkStack_Size(lstack));
while(LinkStack_Size(lstack) > 0)
{
printf("linkstack pop: %d \n", *((int *)LinkStack_Pop(lstack)));
}
LinkStack_Destroy(lstack);
printf("Hello world!\n");
return 0;
}
|
|
