这些小活动你都参加了吗?快来围观一下吧!>>
电子产品世界 » 论坛首页 » 嵌入式开发 » 软件与操作系统 » 【一点一滴学嵌入式Linux】链表(单向链表)、栈与队列

共18条 1/2 1 2 跳转至

【一点一滴学嵌入式Linux】链表(单向链表)、栈与队列

专家
2013-09-19 22:53:34     打赏

链表是一种物理存储单元上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,链表比较方便插入和删除操作。



想要看懂链表程序,必须看懂这幅图!

关于链表更多了解,详看百度百科!


参考代码:

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

#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
#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;
}

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

测试main函数

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

#include
#include "list.h"

int main(int argc,char **argv)
{
//创建链表
List *plist=createList();


//添加数据
char c;
for(c='a';c<='z';c++)
{
appendList(plist,c);
}

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



源代码:list.rar




关键词: 一点一滴     嵌入式          Linux     链表     数据    

专家
2013-09-19 23:20:22     打赏
2楼

链表拓展——栈


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


参考代码:


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

#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
#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)
{
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





专家
2013-09-19 23:38:40     打赏
3楼

链表拓展——队列

队列(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;
}


测试main:

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

#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



菜鸟
2013-09-20 11:30:02     打赏
4楼

学习了


专家
2013-09-20 16:53:32     打赏
5楼
假期还在学习的都是寂寞的好同志

助工
2013-09-21 01:20:05     打赏
6楼
谢谢楼主,终于更新了

菜鸟
2013-09-21 08:27:16     打赏
7楼
不错不错,正在学习。

菜鸟
2013-09-21 14:12:58     打赏
8楼
学习了,建议有实例告诉我们,在什么情况下可以用到这些东西,并且可以借助实例做做实验,加深理解。

专家
2013-09-21 18:14:56     打赏
9楼
等会上实例,图文并茂~

专家
2013-09-22 13:12:01     打赏
10楼
支持楼主的系列

共18条 1/2 1 2 跳转至

回复

匿名不能发帖!请先 [ 登陆 注册 ]