链表
2018-06-17 22:38:40来源:未知 阅读 ()
与顺序表相同,链表也是一种线性表,它的数据逻辑组织形式是一维的。而与顺序表不同的是,链表的物理存储结构是用一组地址任意的存储单元存储数据的。也就是说,它不像链表一样占据一段连续的内存空间,而是将存储单元分散在内存的任意地址上。在链表结构中,每一个数据元素记录都存放在链表的一个结点中(node),而每一个结点之间由指针将其连接一起,这样就形成一条如同“链”的结构。
在C语言中,链表的每一个结点可以是一个结构体元素,当然也可以是其他的构造类型元素。在链表的每一个结点中,都必须有一个专门存放指针(地址)的域,用这个指针域来存放后继结点的地址,这样就达到连接后继结点的目的。一条链表通常有有一个表头,用来存放第一个结点的地址。此外,一条链表的最后一个结点的指针域要置空,表示该结点为链表的结尾,因为它没有后继结点。
上图是链表的结构示意图
一个链表结点可用C语言描述如下:
typedef struct node{ ElemType data; struct node* next; }LNode,*LinkList;
创建一个链表如下:
LinkList CreatLinkList(int n){ /*建立一个长度为n的链表*/ LinkList p,r,list=NULL; ElemType e; int i; for(i=1;i<=n;i++){ Get(e);//输入获取数据 p=(LinkList)malloc(sizeof(LNode)); p->data=e; p->next=NULL; if(!list) list=p; else r->next=p; r=p; } return list; }
上述的代码思路是:调用函数 CreatLinlList(n);的时候,当i=1的时候,list是为null,此时将p的值赋值给表头(list),同时将p的值给此时的r,第二次i=2的时候list不为null,而此时p的值是一个新的结点,这是就要用到r了,r是上一个p的值,将r->next=p,表示将新的p值接上上一个值,此时重新将r值更新为这次的p值,之后循环。
向链表中插入结点(下面介绍的是在指针q指向的结点后面插入结点):
(1)先创建一个新的结点,并将指针p指向该结点
(2)将q指向的结点的next域的值(q->next)赋值给p->next;
(3)在将q->next=p;
上图就是插入的过程.
代码如下:
void insertList(LinkList *list,LinkList q,ElemType e){ LinkList p; p=(LinkList)malloc(sizeof(LNode)); p->data=e; if(!*list){ *list=p;//向空链表插入元素 p->next=NULL; } else{ p->next=q->next; q->next=p; } }
删除链表元素代码如下:
void delLink(LinkList *list,LinkList q){ LinkList r; if(q==*list){ *list=q->next; free(q); } else{ for(r=*list;r->next!=q;r=r->next);//遍历链表找到q的前驱结点 if(r->next!=NULL){ r->next=q->next; free(q); } } }
销毁一个链表代码如下:
void destroyLinkList(LinkList *list){ LinkList p,q; p=*list; while(p){ q=p->next; free(p); p=q; } *list=NULL; }
案例分析:
#include "stdio.h" #include <stdlib.h> typedef int ElemType; typedef struct node{ ElemType data; struct node* next; }LNode,*LinkList; LinkList CreatLinkList(int n){ /*建立一个长度为n的链表*/ LinkList p,r,list=NULL; ElemType e; int i; for(i=1;i<=n;i++){ scanf("%d",&e);//输入获取数据 p=(LinkList)malloc(sizeof(LNode)); p->data=e; p->next=NULL; if(!list) list=p; else r->next=p; r=p; } return list; } void insertList(LinkList *list,LinkList q,ElemType e){ LinkList p; p=(LinkList)malloc(sizeof(LNode)); p->data=e; if(!*list){ *list=p;//向空链表插入元素 p->next=NULL; } else{ p->next=q->next; q->next=p; } } void delLink(LinkList *list,LinkList q){ LinkList r; if(q==*list){ *list=q->next; free(q); } else{ for(r=*list;r->next!=q;r=r->next);//遍历链表找到q的前驱结点 if(r->next!=NULL){ r->next=q->next; free(q); } } } void destroyLinkList(LinkList *list){ LinkList p,q; p=*list; while(p){ q=p->next; free(p); p=q; } *list=NULL; } void main() { int e,i; LinkList l,q; q=l=CreatLinkList(1); scanf("%d",&e); while(e){ insertList(&l,q,e); q=q->next; scanf("%d",&e); } q=l; printf("The content of the linklist:\n"); while(q) { printf("%d ",q->data); q=q->next; } q=l; printf("\nDelete the fifth element\n"); for(i=0;i<4;i++) { if(q==NULL){ printf("the length of the linklist is smaller than 5!\n"); getchar(); return; } q=q->next; } delLink(&l,q); q=l; while(q) { printf("%d ",q->data); q=q->next; } destroyLinkList(&l); getchar(); }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:P1969 积木大赛
- leetcode 反转链表 2020-06-06
- 数据结构—链表 2020-05-29
- STL之list 2020-04-30
- gcc/g++ 链接顺序注意事项 2020-04-20
- 数据结构之顺序表的实现 2020-04-06
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash