EEPW论坛

链表拓展——栈

栈是一种后进先出的数据结构，详看百度百科！

参考代码：

================================

#ifndef LIST_H
#define LIST_H


typedef char T;
//定义节点结构体
typedef struct NODE{
T data;
struct NODE *next;
}Node;


//链表结构体
typedef struct LIST{
Node *phead;
int size;
}List;


List *createList();
Node *enctypeNode(T data);
int appendList(List *plist,T data);
int insertBefore(List *plist,T data);
int insertByindex(List *plist,T data,int index);
T findByindex(List *plist,int index);
int getSzie(List *plist);
int removeAt(List *plist,int index);
int destoryNode(Node *node);
int destoryList(List *plist);
#endif

===========================

=============================

#include "list.h"
//入栈
int push(List *plist,T data)
{
insertBefore(plist, data);
}
//出栈
T pop(List *plist)
{
Node *temp=plist->phead;
T data=temp->next->data;
//每一次删除栈顶元素，以便下次取出元素
removeAt(plist,1);


return data;
}
//返回栈顶元素
T top(List *plist)
{
Node *temp=plist->phead;
return temp->next->data;
}
//获取栈中元素的个数
int size(List *plist)
{
return plist->size;
}
//判断栈是否为空
int isempty(List *plist)
{
return plist->size==0;
}

测试代码：

#include <stdio.h>
#include "list.h"
//把26个英文字母入栈
int main()
{
//首先创建链表，当作容器
List *plist=createList();
//入栈
char c;
for(c='a';c<='z';c++)
{
printf("%c ",c);
push(plist,c);
}
printf("top is %c\n",top(plist));
while(isempty(plist)==0)
{
printf("%c ",pop(plist));
}
putchar('\n');
destoryList(plist);
return 0;
}

源代码：stack.rar

链表拓展——队列

队列（queue）在计算机科学中，是一种先进先出的线性表。它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

详见百度百科！

参考源代码：

===============================

#ifndef LIST_H
#define LIST_H


typedef char T;
//定义节点结构体
typedef struct NODE{
T data;
struct NODE *next;
}Node;


//链表结构体
typedef struct LIST{
Node *phead;
int size;
}List;

==============================

#include <stdlib.h>
#include "list.h"
//创建链表
List *createList()
{
List *plist=malloc(sizeof(List));
plist->size=0;
plist->phead=malloc(sizeof(Node));
plist->phead->data=0;
plist->phead->next=NULL;


return plist;
}


//封装数据
Node *enctypeNode(T data)
{
//定义一个新的节点存放数据
Node *newnode=malloc(sizeof(Node));
//将数据存放入数据域
newnode->data=data;
newnode->next=NULL;
return newnode;
}


//追加数据到链表末尾
int appendList(List *plist,T data)
{
//定义一个新节点接受封装好的数据
Node *newnode=enctypeNode(data);
//首先找到头节点的指针欲
Node *temp=plist->phead;
while(temp->next)
{
temp=temp->next;
}
temp->next=newnode;
plist->size++;

return 0;
}
//向第一个节点位置添加数据
int insertBefore(List *plist,T data)
{
//定义一个新节点接受封装好的数据
Node *newnode=enctypeNode(data);
newnode->next=plist->phead->next;
plist->phead->next=newnode;
plist->size++;


return 0;
}
//通过下标添加数据
int insertByindex(List *plist,T data,int index)
{
//处理索引越界
if(index<1)
index=1;
if(index>plist->size)
index=plist->size;
Node *newnode=enctypeNode(data);
//定义两个指针，一个存放当前位置，一个存放前一个位置 
Node *temp=plist->phead;
Node *temp1=temp;
while(index--)
{
temp1=temp;
temp=temp->next;
}
newnode->next=temp1->next;
temp1->next=newnode;
plist->size++;


return 0;
}


//根据下标查找数据
T findByindex(List *plist,int index)
{
Node *temp=plist->phead;
//头节点无数据，不需要搜索
temp=temp->next;
while(index--)
temp=temp->next;
return temp->data;


}


//获取链表长度
int getSzie(List *plist)
{
return plist->size;
}
//根据下标删除数据
int removeAt(List *plist,int index)
{
Node *temp=plist->phead;
Node *temp1=temp;
while(index--)
{
temp1=temp;
temp=temp->next;
}
temp1->next=temp->next;
free(temp);
plist->size--;
return 0;
}
//销毁节点
int destoryNode(Node *node)
{
if(node->data)
free(node->next);
free(node);
node=NULL;
return 0;
}
//销毁链表
int destoryList(List *plist)
{
Node *temp,*cur;
temp=cur=plist->phead;
while(temp)
{
temp=temp->next;
destoryNode(cur);
cur=temp;
}
free(plist);
plist=NULL;


return 0;
}

===============================

#include "list.h"
//入栈
int push(List *plist,T data)
{
appendList(plist, data);
}
//出栈
T pop(List *plist)
{
Node *temp=plist->phead;
T data=temp->next->data;
removeAt(plist,1);


return data;
}
//返回队首元素
T top(List *plist)
{
Node *temp=plist->phead;
return temp->next->data;
}
//获取队列中元素的个数
int size(List *plist)
{
return plist->size;
}
//判断队列是否为空
int isempty(List *plist)
{
return plist->size==0;
}

#include <stdio.h>
#include "list.h"
//把26个英文字母入列
int main()
{
//首先创建链表，当作容器
List *plist=createList();
//入列
char c;
for(c='a';c<='z';c++)
{
printf("%c ",c);
push(plist,c);
}
//打印队首元素
printf("top is %c\n",top(plist));
//出列
while(isempty(plist)==0)
{
printf("%c ",pop(plist));
}
putchar('\n');
destoryList(plist);
return 0;
}

源代码：queue.rar

学习了