Simon 's Blog
navigation
!!! 3.单链表
? 线性表 ?    2017-09-02 01:23:11    219    0    0
simon88   ? 线性表 ?

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


上一篇: 1.顺序表

下一篇: 2.顺序表上实现的基本运算

219 人读过
0 条评论