本文将介绍几种存储结构,分别为链式结构、树形结构、图结构以及矩阵结构。
第一节 链式存储结构
所谓链式存储结构,一般就是用一个头指针指向链表的第一个节点,如果你要增加新的存储元素时,只需在已有节点的后面插入新结点即可。
链表通常有单链表、双链表、循环链表。在这,我只介绍单链表,双链表和循环链表只是单链表的拓展罢了。下图就是一个简单的单链表图示。
- typedefcharDataType;/***假设结点的数据域类型为字符***/
- typedefstructnode{/***结点类型定义***/
- DataTypedata;/***结点的数据域***/
- structnode*next;/***结点的指针域***/
- }ListNode;
- typedefListNode*LinkList;
- ListNode*p;
- LinkListhead;
- 附注:
- ①LinkList和ListNode*是不同名字的同一个指针类型(命名的不同是为了概念上更明确)
- ②LinkList类型的指针变量head表示它是单链表的头指针
- ③ListNode*类型的指针变量p表示它是指向某一节点的指针
下面我们来看单链表的操作:创建节点、增加节点、删除节点、查询、修改。
1.创建节点:声明一个节点并为其申请一段内存空间,此节点有数据域和指针域。
- node=(structList*)malloc(sizeof(structList));
2.增加节点:插入节点,分为头插入、尾插入和非头尾插入。
①. 在表头插入节点, 如图
- if(p==head)/***其中p为链表中的某一节点***/
- {
- structlist*s=NULL;
- s=(structlist*)malloc(structlist));/***申请空间***/
- s->Datanumber=data;/***为节点s的数据域赋值***/
- /***将节点s插入表头***/
- s->next=p;
- head=s;
- }