2019 August 30 CPP基础

C/CPP与数据结构-第一节 线性表（二）

线性表的链式存储

  1. 基本概念
    1. 链式存储定义:
      1. 为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示其直接后继的信息。
    2. n个结点链接成一个链表，即为线性表的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。
    3. 表头结点：
      1. 链表中的第一个结点，包含指向第一个数据元素的指针以及链表自身的一些信息
    4. 数据结点
      1. 链表中代表数据元素的结点，包含指向下一个数据元素的指针和数据元素的信息
    5. 尾结点
      1. 链表中的最后一个数据结点，其下一元素指针为空，表示无后继
  2. 链表技术领域推演
    1. 传统链表
      1. 一个结点分为数据域、指针域
      2. 数据域一旦发生改变，链表就需要重新建立；不能实现链表与数据业务的分离

      3. 比如：Teacher结构体本来有2个成员（数据域），1个指针（指针域），组成一个链表，但是如果我想再次给Teacher结构体添加一个成员呢？ 原来的链表便不能用了

         //传统链表结构
 typedef struct _Teacher
 {
 	char name[32];
 	int age;
 	struct _Teacher *next;
 }Teacher;
    2. Linux内核链表
      1. 一个结点只有一个指针域，指向下一个结点
      2. 让每个结构体包含这个链表
      3. 缺点：需要求偏移量，才能拿到每个业务中的链表地址

      4. 比如:next的值是在Teacher的2个成员变量的偏移

         typedef struct _Node {
    struct _Node *next;
 }Node;
            
 typedef struct _Teacher
 {
 	char name[32];
 	int age;
 	Node next;
 }Teacher;
    3. 企业链表，通用链表

      1. 于Linux链表相比，将链表放在第一个成员变量

         typedef struct _Node {
    struct _Node *next;
 }Node;
            
 typedef struct _Teacher
 {
 	Node next;
 	char name[32];
 	int age;
 }Teacher;

    4. 上面3种链表的示意图如下：

      图4

  3. 链表链式存储_api实现

     //LinkList.h 文件
 #ifndef _WBM_LIST_H_
 #define _WBM_LIST_H_
    
 typedef void LinkList;
    
 typedef struct _tag_LinkListNode {
 	struct _tag_tag_LinkListNode *next;
 }LinkListNode;
    
 //创建并且返回一个空的线性表
 LinkList* LinkList_Create();
    
 //销毁一个线性表list
 void LinkList_Destroy(LinkList* list);
    
 //将一个线性表list中的所有元素清空, 线性表回到创建时的初始状态
 void LinkList_Clear(LinkList* list);
    
 //返回一个线性表list中的所有元素个数
 int LinkList_Length(LinkList* list);
    
 //向一个线性表list的pos位置处插入新元素node
 int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);
    
 //获取一个线性表list的pos位置处的元素
 LinkListNode* LinkList_Get(LinkList* list, int pos);
    
 //删除一个线性表list的pos位置处的元素  返回值为被删除的元素，NULL表示删除失败
 LinkListNode* LinkList_Delete(LinkList* list, int pos);
    
 #endif
    
    
 //LinkList.c 文件
 #define _CRT_SECURE_NO_WARNINGS
 #include<stdlib.h>
 #include<stdio.h>
 #include<string.h>
 #include"LinkList.h"
    
 typedef struct _tag_LinkList
 {
 	//指向链表的头部
 	LinkListNode header;
 	int length;//链表的节点个数
    
 }TLinkList;
    
 //创建并且返回一个空的线性表
 LinkList* LinkList_Create() {
 	TLinkList *temp = NULL;
 	temp = (TLinkList *)malloc(sizeof(TLinkList));
 	if (temp ==NULL)
 	{
 		printf("LinkList_Create() error \n");
 		return NULL;
 	}
 	memset(temp, 0, sizeof(TLinkList));
 	temp->length = 0;
 	temp->header.next = NULL;
 	return temp;
 }
    
 //销毁一个线性表list
 void LinkList_Destroy(LinkList* list) {
 	if (list ==NULL)
 	{
 		return;
 	}
 	free(list);
 	return;
 }
    
 //将一个线性表list中的所有元素清空, 线性表回到创建时的初始状态
 void LinkList_Clear(LinkList* list) {
 	TLinkList *tlist = NULL;
 	tlist = (TLinkList *)list;
 	if (tlist == NULL)
 	{
 		return;
 	}
 	tlist->header.next = NULL;
 	tlist->length = 0;
 	return;
 }
    
 //返回一个线性表list中的所有元素个数
 int LinkList_Length(LinkList* list) {
 	TLinkList *tlist = NULL;
 	tlist = (TLinkList *)list;
 	if (tlist == NULL)
 	{
 		return -1;
 	}
 	return tlist->length;
 }
    
 //向一个线性表list的pos位置处插入新元素node
 int LinkList_Insert(LinkList* list, LinkListNode* node, int pos) {
 	int i = 0;
 	//搞一个辅助指针专门用于跳到相应的位置
 	LinkListNode *current = NULL;
 	TLinkList *temp = NULL;
 	temp = (TLinkList *)list;
    
 	if (list == NULL ||node == NULL ||pos<0)
 	{
 		return -1;
 	}
 	//辅助指针初始化，指向链表头部
 	current = &(temp->header);
    
 	//跳pos次
 	for ( i = 0; i < pos; i++)
 	{
 		current = current->next;
 	}
 	//新节点连接后继链表
 	node->next = current->next;
 	//前面链表连接新节点
 	current->next = node;
 	temp->length++;
 	return 0;
 }
    
 //获取一个线性表list的pos位置处的元素
 LinkListNode* LinkList_Get(LinkList* list, int pos) {
 	int i = 0;
 	//搞一个辅助指针专门用于跳到相应的位置
 	LinkListNode *current = NULL;
 	TLinkList *temp = NULL;
 	temp = (TLinkList *)list;
    
 	if (list == NULL || pos < 0)
 	{
 		return -1;
 	}
 	current = &(temp->header);
    
 	//跳pos次
 	for (i = 0; i < pos; i++)
 	{
 		current = current->next;
 	}
    
 	return current->next;
 }
    
 //删除一个线性表list的pos位置处的元素  返回值为被删除的元素，NULL表示删除失败
 LinkListNode* LinkList_Delete(LinkList* list, int pos) {
 	int i = 0;
 	//搞一个辅助指针专门用于跳到相应的位置
 	LinkListNode *current = NULL;
 	LinkListNode *ret = NULL;
 	TLinkList *temp = NULL;
 	temp = (TLinkList *)list;
    
 	if (list == NULL || pos < 0)
 	{
 		return NULL;
 	}
 	current = &(temp->header);
 	for (i = 0; i < pos; i++)
 	{
 		current = current->next;
 	}
 	ret = current->next;
 	current->next = ret->next;
    
 	temp->length--;
 	return ret;
 }
    
 //main.c文件
 #define _CRT_SECURE_NO_WARNINGS
 #include<stdlib.h>
 #include<string.h>
 #include<stdio.h>
 #include"LinkList.h"
    
 //企业链表
 typedef struct _Teacher
 {
 	LinkListNode next;
 	char name[32];
 	int age;
 }Teacher;
    
 int main() {
 	LinkList *list = NULL;
 	Teacher t1, t2, t3,t4;
 	t1.age = 31;
 	t2.age = 32;
 	t3.age = 33;
 	t4.age = 34;
 	//创建链表
 	list = LinkList_Create();
 	//插入元素
 	LinkList_Insert(list, (LinkListNode*)&t1, 0);
 	LinkList_Insert(list, (LinkListNode*)&t2, 0);
 	LinkList_Insert(list, (LinkListNode*)&t3, 0);
 	LinkList_Insert(list, (LinkListNode*)&t4, 2);
    
 	//遍历链表
 	for (int i = 0; i < LinkList_Length(list); i++)
 	{
 		Teacher *tem = (Teacher *)LinkList_Get(list, i);
 		if (tem == NULL)
 		{
 			return -1;
 		}
 		printf("insert age: %d \n", tem->age);
 	}
    	
 	//删除链表节点
 	while (LinkList_Length(list)>0)
 	{
 		Teacher *tem = (Teacher*) LinkList_Delete(list, 0);
 		if (tem==NULL)
 		{
 			return -1;
 		}
 		printf("delete  age: %d \n", tem->age);
 	}
    	
 	//销毁链表
 	LinkList_Destroy(list);
    
 	system("pause");
 	return 0;
 }
    1. 代码分析：

      1. 链表的插入分析： 图4

      2. 链表的删除分析 图4

      3. 关键点：

        1. 指针指向谁就把谁的地址复制给指针
        2. 添加了一个辅助指针current，用于定位需要获取、插入、删除节点的地址.
        3. current设置为表头节点的好处：可以直接根据插入的index，将current跳index次，正好就是目标节点的上一个节点。
        4. 删除节点，为何要将删除的节点地址返回呢？ 目的是让用户清理当前节点的内存。
    2. 优缺点：
      1. 优点：
        1. 无需一次性定制链表的容量
        2. 插入和删除操作无需移动数据元素
      2. 缺点：
        1. 数据元素必须保存后继元素的位置信息
        2. 获取指定数据的元素操作需要顺序访问之前的元素

C++版链式存储

  1. 代码示例：

     //LinkList.h
 #include<iostream>
 using namespace std;
    
 //链表节点模板类
 template<typename T>
 struct Node
 {
 	T t; 
 	struct Node<T> *next;
 };
    
 template<typename T>
 class LinkList
 {
 public:
 	//构造析构函数
 	LinkList();
 	~LinkList();
 	//成员函数
 	int clear();
 	int insert(T &t, int pos);
 	int get(int pos, T &t);
 	int del(int pos, T &t);
 	int getLen();
 private:
 	//内部链表指针
 	Node<T>*m_header;
 	//记录链表长度
 	int m_len;
 };
    
 template<typename T>
 LinkList<T>::LinkList() {
 	//初始化表头节点
 	//在堆空间创建一个表头节点
 	Node<T> *node = new Node<T>;
 	node->next = NULL;
 	m_header = node;
 	//初始化节点长度
 	m_len = 0;
 }
 template<typename T>
 LinkList<T>:: ~LinkList() {
 	Node<T> *tem = NULL;
 	while (m_header)
 	{
 		tem = m_header->next;
 		delete m_header;
 		m_header = tem;
 	}
 }
 template<typename T>
 int LinkList<T>::clear() {
 	//1. 把旧节点删除
 	Node<T> *tem = NULL;
 	while (m_header)
 	{
 		tem = m_header->next;
 		delete m_header;
 		m_header = tem;
 	}
 	//2. 初始化
 	m_header = new Node<T>;
 	m_header->next = NULL;
 	m_len = 0;
 	return 0;
 }
 template<typename T>
 int LinkList<T>::insert(T &t, int pos) {
 	//引进辅助指针变量，并指向header
 	Node<T> *current = NULL;
 	current = m_header;
 	//辅助指针跳pos次
 	for (int i = 0; i < pos; i++)
 	{
 		current = current->next;
 	}
    
 	//由外部数据创建一个节点node：
 	//在堆中开辟一个空间用于缓存外部节点数据
 	Node<T> *node = new Node<T>;
 	node->next = NULL;
 	node->t = t; //把t1缓存下来
    
 	//把node节点加入到链表中
 	//1. 把current下一个节点地址赋值给node
 	node->next = current->next;
    
 	//2. 将node节点地址赋值给current
 	current->next = node;
    
 	m_len++;
 	return 0;
 }
 template<typename T>
 int LinkList<T>::get(int pos, T &t) {
 	//引进辅助指针变量
 	Node<T> *current = NULL;
 	current = m_header;
 	//辅助指针跳pos次
 	for (int i = 0; i < pos; i++)
 	{
 		current = current->next;
 	}
 	t = current->next->t;
 	return 0;
 }
    
 template<typename T>
 int LinkList<T>::del(int pos, T &t) {
 	//引进辅助指针变量
 	Node<T> *current = NULL;
 	Node<T> *ret = NULL;
 	current = m_header;
 	//辅助指针跳pos次
 	for (int i = 0; i < pos; i++)
 	{
 		current = current->next;
 	}
 	//把缓存的节点给上层应用
 	ret = current->next;
 	t = ret->t;
 	//删除操作
 	current->next = ret->next;
 	m_len--;
 	delete ret; //注意释放内存
 	return 0;
 }
    
 template<typename T>
 int LinkList<T>::getLen() {
    
 	return m_len;
 }
    
 //main.cpp
 #include<iostream>
 #include"LinkList.h"
 using namespace std;
    
 struct Teacher
 {
 	char name[32];
 	int age;
 };
 int main() {
 	Teacher t1, t2, t3,t4;
 	Teacher tem;
 	t1.age = 31;
 	t2.age = 32;
 	t3.age = 33;
 	t4.age = 34;
    
 	//创建链表
 	LinkList<Teacher> list;
    
 	//插入数据
 	list.insert(t1, 0);
 	list.insert(t2, 0);
 	list.insert(t3, 0);
 	list.insert(t4, 1);
    	
 	//遍历
 	for (int  i = 0; i < list.getLen(); i++)
 	{
 		list.get(i, tem);
 		cout << "age is" << tem.age << endl;
 	}
 	//销毁链表
 	while (list.getLen()>0)
 	{
 		list.del(0, tem);
 		cout << "del age is" << tem.age << endl;
 	}
    
 	cout << "hello!" << endl;
 	system("pause");
 	return 0;
 }

    图4

    图4

All content is licensed under CC BY-NC-SA

Buit with Jekyll and 3-Jekyll theme • Hosted on Github

Table of Contents