1、链接存储方法
链接方式存储的线性表简称为链表(Linked List)。
链表的具体存储表示为:
① 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的,也可以是不连续的)
② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址(或位置)信息(称为指针(pointer)或链(link))
注意:
链式存储是最常用的存储方式之一,它不仅可用来表示线性表,而且可用来表示各种非线性的数据结构。
2、链表的结点结构
┌──┬──┐
│data│next│
└──┴──┘
data域--存放结点值的数据域
next域--存放结点的直接后继的地址(位置)的指针域(链域)
注意:
①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。
②每个结点只有一个链域的链表称为单链表(Single Linked List)。
【例】线性表(bat,cat,eat,fat,hat,jat,lat,mat)的单链表示如示意图
3、头指针head和终端结点指针域的表示
单链表中每个结点的存储地址是存放在其前趋结点next域中,而开始结点无前趋,故应设头指针head指向开始结点。
注意:
链表由头指针唯一确定,单链表可以用头指针的名字来命名。
【例】头指针名是head的链表可称为表head。
终端结点无后继,故终端结点的指针域为空,即NULL。
4、单链表的一般图示法
由于我们常常只注重结点间的逻辑顺序,不关心每个结点的实际位置,可以用箭头来表示链域中的指针,线性表(bat,cat,fat,hat,jat,lat,mat)的单链表就可以表示为下图形式。
5、单链表类型描述 typedef char DataType; //假设结点的数据域类型为字符
typedef struct node{ //结点类型定义
DataType data; //结点的数据域
struct node *next;//结点的指针域
}ListNode;
typedef ListNode *LinkList;
ListNode *p;
LinkList head;
注意:
①LinkList和ListNode *是不同名字的同一个指针类型(命名的不同是为了概念上更明确)
②LinkList类型的指针变量head表示它是单链表的头指针
③ListNode *类型的指针变量p表示它是指向某一结点的指针
6、指针变量和结点变量
┌────┬────────────┬─────────────┐
│ │ 指针变量 │ 结点变量 │
├────┼────────────┼─────────────┤
│ 定义 │在变量说明部分显式定义 │在程序执行时,通过标准 │
│ │ │函数malloc生成 │
├────┼────────────┼─────────────┤
│ 取值 │ 非空时,存放某类型结点 │实际存放结点各域内容 │
│ │的地址 │ │
├────┼────────────┼─────────────┤
│操作方式│ 通过指针变量名访问 │ 通过指针生成、访问和释放 │
└────┴────────────┴─────────────┘
①生成结点变量的标准函数
p=( ListNode *)malloc(sizeof(ListNode));
//函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中
②释放结点变量空间的标准函数
free(p);//释放p所指的结点变量空间
③结点分量的访问
利用结点变量的名字*p访问结点分量
方法一:(*p).data和(*p).next
方法二:p-﹥data和p-﹥next
④指针变量p和结点变量*p的关系
指针变量p的值——结点地址
结点变量*p的值——结点内容
(*p).data的值——p指针所指结点的data域的值
(*p).next的值——*p后继结点的地址
*((*p).next)——*p后继结点
注意:
① 若指针变量p的值为空(NULL),则它不指向任何结点。此时,若通过*p来访问结点就意味着访问一个不存在的变量,从而引起程序的错误。
② 有关指针类型的意义和说明方式的详细解释,【参考C语言的有关资料】。
例子:
1.结构和函数原型:
/* * s_linklist.h * * Created on: 2017年10月18日 * Author: simon */ #ifndef S_LINKLIST_H_ #define S_LINKLIST_H_ #include <stdlib.h> #include <string.h> #include <stdio.h> typedef int type; typedef struct s_node { type data; struct s_node *pNext; }S_NODE,*S_PNODE; S_PNODE s_create_linklist(void); void s_print_linklist1(S_PNODE PHead); void s_insert_val_linklist(S_PNODE PHead,int pos,int data); //链表的长度 int s_length_linklist(S_PNODE PHead); void s_insert_val_linklist(S_PNODE PHead,int pos,int data); //选择排序 void s_selectsort_linklist(S_PNODE PHead); //链表逆序 S_PNODE s_reversed_linklist1(S_PNODE PHead); S_PNODE s_reversed_linklist2(S_PNODE head); //查找 S_PNODE s_find_linklist(S_PNODE PHead,int pos); //插入节点 void s_insert_node_linklist(S_PNODE PHead,S_PNODE node,int pos); #endif /* S_LINKLIST_H_ */
2.函数:
/* * s_linklist.c * * Created on: 2017年10月18日 * Author: simon */ #include "../include/s_linklist.h" //创建链表 S_PNODE s_create_linklist(void) { int num; int i; S_PNODE PHead = (S_PNODE)malloc(1*sizeof(S_NODE)); if(!PHead) { printf("HNode allocation failure\n"); exit(EXIT_FAILURE); } S_PNODE PTail = PHead; PHead->pNext = NULL; printf("please input the length of list:"); scanf("%d",&num); for(i=0;i<num;i++) { S_PNODE p = (S_PNODE)malloc(1*sizeof(S_NODE)); if(!p) { printf("Node allocation failure\n"); exit(EXIT_FAILURE); } printf("please input the value(%d) of list: ",i+1); scanf("%d",&p->data); PTail->pNext = p; PTail->pNext->pNext = NULL; PTail = p; p = NULL; } printf("allocation success\n"); return PHead; } //遍历链表,打印 void s_print_linklist1(S_PNODE PHead) { if(PHead == NULL) { printf("Linklist empty\n"); exit(EXIT_FAILURE); } S_PNODE p = PHead->pNext; while(p != NULL) { printf("%d\t",p->data); p = p->pNext; } p = NULL; printf("\n"); return ; } /** * 假如要在节点2的前面插入节点p,我们首先要找到节点2的前驱节点1,假设现在q指针指向节点1,则 (1)p->pNext=q->pNext; (2)q->pNext=p; */ void s_insert_val_linklist(S_PNODE PHead,int pos,int data) { if(PHead == NULL) { printf("PHead is empty\n"); exit(EXIT_FAILURE); } if(pos < 1) { printf("insert pos < 1\n"); exit(EXIT_FAILURE); } int index = 0; S_PNODE q = PHead; while(q != NULL&&index < pos-1) { index ++; //想插入的位置超出的范围。 if(q->pNext == NULL) { break; } q = q->pNext; } if(q->pNext == NULL||index == (pos - 1)) { S_PNODE p = (S_PNODE)malloc(1*sizeof(S_NODE)); p->data = data; p->pNext = q->pNext; q->pNext = p; p = q = NULL; printf("insert success\n"); } } //插入节点 void s_insert_node_linklist(S_PNODE PHead,S_PNODE node,int pos) { int index = 0; if(PHead == NULL&&PHead->pNext == NULL) { printf("Linklist is empty\n"); return ; } S_PNODE p = PHead; while( p->pNext != NULL&&index <(pos-1)) { index++; p = p->pNext; } if(p->pNext == NULL||index == (pos-1)) { node->pNext = p->pNext; p->pNext = node; p = NULL; } return ; } //链表的长度 int s_length_linklist(S_PNODE PHead) { if(PHead == NULL) { printf("Linklist is empty\n"); return 0; } int length = 0; S_PNODE p = PHead->pNext; while(p != NULL) { length++; p = p->pNext; } p = NULL; return length; } void s_selectsort_linklist(S_PNODE PHead) { if(PHead == NULL || PHead->pNext == NULL) { printf("Linklist is empty\n"); exit(EXIT_FAILURE); } S_PNODE p = PHead->pNext;; S_PNODE q; int i,j; int temp; int length = s_length_linklist(PHead); for(i = 0;i < length-1;i++,p = p->pNext) { for(j = i+1,q = p->pNext; j<length;j++,q = q->pNext) { if(q->data < p->data) { temp = q->data; q->data = p->data; p->data = temp; } } } } S_PNODE s_reversed_linklist1(S_PNODE PHead) { if(PHead->pNext == NULL || PHead == NULL) { printf("Linklist is empty\n"); exit(EXIT_FAILURE); } S_PNODE head = PHead->pNext; S_PNODE next; S_PNODE prev = NULL; while(head != NULL) { next = head->pNext; head->pNext = prev; prev = head; head = next; } return prev; } S_PNODE s_reversed_linklist2(S_PNODE head) { S_PNODE PNewHead; if(head == NULL || head->pNext == NULL) { return head; } PNewHead = s_reversed_linklist2(head->pNext); head->pNext->pNext = head; head->pNext = NULL; return PNewHead; } S_PNODE s_find_linklist(S_PNODE PHead,int pos) { if(PHead == NULL||PHead->pNext == NULL) { printf("Linklist is empty\n"); return NULL; } S_PNODE p = PHead; int index = 0; while(p != NULL&& index <(pos)) { index++; p = p->pNext; } if(index == pos) { return p; } printf("Not found\n"); return NULL; }
3.测试函数:
void s_linklist_test(void) { S_PNODE PHead = s_create_linklist(); s_print_linklist1(PHead); int length = s_length_linklist(PHead); printf("Linklist length is:%d\n",length); s_insert_val_linklist(PHead,1,5); s_print_linklist1(PHead); printf("reversed1:\n"); PHead->pNext = s_reversed_linklist1(PHead); s_print_linklist1(PHead); printf("reversed1:\n"); PHead->pNext = s_reversed_linklist2(PHead->pNext); s_print_linklist1(PHead); printf("sorted:\n"); s_selectsort_linklist(PHead); s_print_linklist1(PHead); S_PNODE p = s_find_linklist(PHead,1); printf("found :%d\n",p->data); printf("insert node\n"); S_PNODE node = (S_PNODE)malloc(1*sizeof(S_NODE)); memset(node,1,sizeof(S_NODE)); node->data = 1111; s_insert_node_linklist(PHead,node,5); s_print_linklist1(PHead); return ; }