链表


#include <stdio.h>
#include <malloc.h>

typedef struct node{
	int data;//数据域
	struct node * next;//指针域
}Node;

int main()
{
	Node *pLinkNode=NULL;

	pLinkNode = (Node*)malloc(sizeof(Node));  

    pLinkNode->data = 2;
    pLinkNode->next = NULL;

	printf("%d\n",pLinkNode->data);

	return 0;
}

一步一步写算法(之单向链表)

    有的时候,处于内存中的数据并不是连续的。那么这时候,我们就需要在数据结构中添加一个属性,这个属性会记录下面一个数据的地址。有了这个地址之后,所有的数据就像一条链子一样串起来了,那么这个地址属性就起到了穿线连结的作用。

    相比较普通的线性结构,链表结构的优势是什么呢?我们可以总结一下:

    (1)单个节点创建非常方便,普通的线性内存通常在创建的时候就需要设定数据的大小

    (2)节点的删除非常方便,不需要像线性结构那样移动剩下的数据

    (3)节点的访问方便,可以通过循环或者递归的方法访问到任意数据,但是平均的访问效率低于线性表

    那么在实际应用中,链表是怎么设计的呢?我们可以以int数据类型作为基础,设计一个简单的int链表:

    (1)设计链表的数据结构

[cpp] view
plain
copy

  1. typedef struct _LINK_NODE  
  2. {  
  3.     int data;  
  4.     struct _LINK_NODE* next;  
  5. }LINK_NODE;  

    (2)创建链表

[cpp] view
plain
copy

  1. LINK_NODE* alloca_node(int value)  
  2. {  
  3.     LINK_NODE* pLinkNode = NULL;  
  4.     pLinkNode = (LINK_NODE*)malloc(sizeof(LINK_NODE));  
  5.       
  6.     pLinkNode->data = value;  
  7.     pLinkNode->next = NULL;  
  8.     return pLinkNode;  
  9. }  

    (3)删除链表

[cpp] view
plain
copy

  1. void delete_node(LINK_NODE** pNode)  
  2. {  
  3.     LINK_NODE** pNext;  
  4.     if(NULL == pNode || NULL == *pNode)  
  5.         return ;  
  6.           
  7.     pNext = &(*pNode)->next;  
  8.     free(*pNode);  
  9.     delete_node(pNext);   
  10. }  

    (4)链表插入数据

[cpp] view
plain
copy

  1. STATUS _add_data(LINK_NODE** pNode, LINK_NODE* pDataNode)  
  2. {  
  3.     if(NULL == *pNode){  
  4.         *pNode = pDataNode;  
  5.         return TRUE;  
  6.     }  
  7.       
  8.     return _add_data(&(*pNode)->next, pDataNode);  
  9. }  
  10.   
  11. STATUS add_data(const LINK_NODE** pNode, int value)  
  12. {  
  13.     LINK_NODE* pDataNode;  
  14.     if(NULL == *pNode)  
  15.         return FALSE;  
  16.           
  17.     pDataNode = alloca_node(value);  
  18.     assert(NULL != pDataNode);  
  19.     return _add_data((LINK_NODE**)pNode, pDataNode);  
  20. }  

    (5)删除数据

[cpp] view
plain
copy

  1. STATUS _delete_data(LINK_NODE** pNode, int value)  
  2. {  
  3.     LINK_NODE* pLinkNode;  
  4.     if(NULL == (*pNode)->next)  
  5.         return FALSE;  
  6.       
  7.     pLinkNode = (*pNode)->next;  
  8.     if(value == pLinkNode->data){  
  9.         (*pNode)->next = pLinkNode->next;  
  10.         free(pLinkNode);  
  11.         return TRUE;  
  12.     }else{  
  13.         return _delete_data(&(*pNode)->next, value);  
  14.     }  
  15. }  
  16.   
  17. STATUS delete_data(LINK_NODE** pNode, int value)  
  18. {  
  19.     LINK_NODE* pLinkNode;  
  20.     if(NULL == pNode || NULL == *pNode)  
  21.         return FALSE;  
  22.   
  23.     if(value == (*pNode)->data){  
  24.         pLinkNode = *pNode;  
  25.         *pNode = pLinkNode->next;  
  26.         free(pLinkNode);  
  27.         return TRUE;  
  28.     }         
  29.       
  30.     return _delete_data(pNode, value);  
  31. }  

    (6)查找数据

[cpp] view
plain
copy

  1. LINK_NODE* find_data(const LINK_NODE* pLinkNode, int value)  
  2. {  
  3.     if(NULL == pLinkNode)  
  4.         return NULL;  
  5.       
  6.     if(value == pLinkNode->data)  
  7.         return (LINK_NODE*)pLinkNode;  
  8.       
  9.     return find_data(pLinkNode->next, value);  
  10. }  

    (7)打印数据

[cpp] view
plain
copy

  1. void print_node(const LINK_NODE* pLinkNode)  
  2. {  
  3.     if(pLinkNode){  
  4.         printf("%d\n", pLinkNode->data);  
  5.         print_node(pLinkNode->next);  
  6.     }  
  7. }  

    (8)统计数据

[cpp] view
plain
copy

  1. int count_node(const LINK_NODE* pLinkNode)  
  2. {  
  3.     if(NULL == pLinkNode)  
  4.         return 0;  
  5.           
  6.     return 1 + count_node(pLinkNode->next);  
  7. }
时间: 2024-09-18 04:16:21

链表的相关文章

[数据结构] 数组与链表的优缺点和区别

概述 数组 是将元素在内存中连续存放,由于每个元素占用内存相同,可以通过下标迅速访问数组中任何元素.但是如果要在数组中增加一个元素,需要移动大量元素,在内存中空出一个元素的空间,然后将要增加的元素放在其中.同样的道理,如果想删除一个元素,同样需要移动大量元素去填掉被移动的元素.如果应用需要快速访问数据,很少插入和删除元素,就应该用数组. 链表 中的元素在内存中不是顺序存储的,而是通过存在元素中的指针联系到一起,每个结点包括两个部分:一个是存储 数据元素 的 数据域,另一个是存储下一个结点地址的

c++类 链表-C++代码,链表,无法解析的字符

问题描述 C++代码,链表,无法解析的字符 #ifndef LIST_H #define LIST_H #include"ListNode.h" template< typename NODETYPE > class List { public: List(); ~List(); void insertAtFirst( const NODETYPE & ); void insertAtLast( const NODETYPE & ); bool remove

[经典面试题]在O(1)时间删除链表结点

[题目] 给定链表的头指针和一个结点指针,在O(1)时间删除该结点.链表结点的定义如下: struct ListNode {     int        value;     struct ListNode*  next; }; 函数的声明如下: void DeleteNode(ListNode* head,ListNode* node); [思路] 这是一道广为流传的Google面试题,能有效考察我们的编程基本功,还能考察我们的反应速度,更重要的是,还能考察我们对时间复杂度的理解. 在链表中

循环双链表初始化的问题

问题描述 循环双链表初始化的问题 s=(LinkList)malloc(sizeof(Node)); s->data=a[i]; s->next=L->next; if(L->next!=NULL) L->next->prior=s; L->next=s; s->prior=L; 在树上有对L->next的判空语句,但是我认为在循环链表中没有NULL节点,所以我想问问这样做是否多余? 解决方案 如果循环链表构建正确,确实没有必要判断. 但为了程序的健壮

数据结构模版----单链表实现方式总结

数据结构模版----单链表实现方式总结 前面我们提供了四种方式实现的单链表,有带头结点的不带头结点的,而单链表的结构体定义也有两种方式,那么这些实现方式,到底有什么区别呢,为什么会出现这么多种实现方式呢,下面我们就来细细体会 一 单链表结构体的实现区别 首先我们对比一下,单链表结构体 不同方式的单链表实现时,链表结点的实现是相同的,不同之处在于单链表结构体的实现上 单链表结构体的实现 [cpp] view plain copy print? typedef int ElemType;      

c++-[紧急求救]C++:在循环结构中使用链表,程序运行终端

问题描述 [紧急求救]C++:在循环结构中使用链表,程序运行终端 如题.(这是图像处理中的中值滤波,不过问题不涉及图像处理)链表操作都没有问题,在另外的程序中测试过.这这段代码中第一次调用也没有问题,就是第二次到list.insert()时会跳出中断:这段代码如下: int i j x y p t;//p为当前像素位置 int a[arg*arg] = {0}; linklist list; for (y = 0; y<nHeight - arg + 1; y++) { for (x = 0;

销毁链表到底有什么用,程序结束后不应该所有的内存都释放完了吗

问题描述 销毁链表到底有什么用,程序结束后不应该所有的内存都释放完了吗 销毁链表到底有什么用,程序结束后不应该所有的内存都释放完了吗 解决方案 是的,不管程序释放不释放,程序运行结束肯定释放.但是你写小程序要养成好习惯.不然大程序没有释放,这对于那种连续运行很久的程序来说就是一个灾难了. 解决方案二: C++还是java?C++是不会自动释放的.java大部分都 能自动释放,但也存在一些特例 解决方案三: c++ 程序结束后不释放? 链表就是结构体吗 没什么特殊的啊 解决方案四: 这个和申请变量

怎么用fscanf把文件的数据读入链表?

问题描述 怎么用fscanf把文件的数据读入链表? 我下面这段代码是哪里出错了? 写入文件没有问题 把文件里的东西写入链表 之后在输出链表 只输出第一行数据 之后都是0 #include "stdio.h" #include "stdlib.h" int n=0; struct stu { int num; char name[100]; float score; struct stu *next; }; void str(struct stu *h) { whil

c语言-为什么链表会无限循环输出??

问题描述 为什么链表会无限循环输出?? #include<stdio.h> #include<stdlib.h>//含malloc.h #define LEN sizeof( Faction) //一元多项式结构体 typedef struct Faction{ int coefficient;//系数 int exponent;//指数 struct Faction *next; }Faction; //创建链表 Faction *creat() { Faction *head,

STL--双端队列(deque)和链表(list)

双端队列(deque容器类): #include<deque>与vector 类似,支持随机访问和快速插入删除,它在容器中某一位置上的操作所花费的是线性时间. 与vector不同的是:deque 还支持从开始端插入数据:push_front() . 此外deque 不支持与vector 的capacity() .reserve() 类似的操作. deque,是"double-ended queue"的缩写.可以随机存取元素(用索引直接存取). 数组头部和尾部添加或移除元素都