2019 July 28 CPP基础

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

数据结构的概念

数据结构相关概念

  1. 数据结构主要研究非数值计算程序问题中的操作对象以及它们之间的关系，不是研究复杂的算法
    1. 非数值计算
    2. 研究对象之间的关系，一个对象与另外一个对象之间存在什么关系？
      1. 比如：数组是按顺序排列的关系，map是一一对应的关系等等
  2. 数据
    1. 定义：程序的操作对象，用于描述客观事物
    2. 数据的特点：
      1. 可以输入到计算机
      2. 可以被计算机程序处理
    3. 数据是一个抽象的概念，将其进行分类后得到程序设计语言中的类型。如：int，float，char等等
  3. 数据对象：是性质相同的数据元素的集合
    1. 比如：数组，链表等等
  4. 数据元素： 组成数据对象的基本单位
    1. 就相当于数组元素，一个一个的节点。
  5. 数据项： 一个数据元素由若干数据项组成
    1. 比如：数组的每个元素都是对象类型，也就是数据元素，每个对象个各个属性组成了这个对象，这个对象的每个属性也叫数据项。
  6. 总结：数据结构是研究数据元素之间关系的一门学科，即节点与节点之间的关系。
    1. 数据元素之间不是独立的，存在特定的关系，这些关系即结构
    2. 比如：数组中各个元素之间存在固定的线性关系，一个一个按顺序排列
  7. 数据的逻辑结构
    1. 指数据元素之间的逻辑关系。
    2. 即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
    3. 逻辑结构可细分为4类：
      1. 集合：数据元素间除同属于一个集合外，无其他关系
      2. 线性结构：一个对一个，如线性表、栈、队列
      3. 树型结构：一个对多个，如树
      4. 图状结构：多个对多个，如图

      图4

  8. 数据的物理结构
    1. 物理结构也叫存储结构，是数据的逻辑结构在计算机存储器内的表示(或映像)。它依赖于计算机。说白了就是数据的逻辑结构在计算机怎么存储的。
    2. 存储结构可以分为4大类：
      1. 顺序
      2. 链式
      3. 索引：内存寻址很像，n楼层+m房间，编号为m+n
      4. 散列：将一个大的数据，通过单向散列函数生成一个值去存储
    3. 最常用的存储结构为：
      1. 顺序存储结构：
        1. 借助元素在存储器中的相对应位置来表示数据间的逻辑关系
      2. 链式存储结构：
        1. 借助指示元素的存储地址的指针表示数据元素间的逻辑关系。
  9. 数据的运算
    1. 在数据的逻辑结构上定义的操作，它在数据的存储结构上实现
    2. 最常用的数据运算有5种：
      1. 插入、删除、修改、查找、排序

算法

  1. 概念
    1. 算法是特定问题求解步骤的描述
    2. 在计算机中表现为指令的有限序列
    3. 算法是独立存在的一种解决问题的方法和思想。
    4. 对于算法而言，语言并不重要，重要的是思想。
  2. 算法和数据结构区别
    1. 数据结构只是静态的描述了数据元素之间的关系
    2. 高效的程序需要在数据结构的基础上设计和选择算法
      1. 比如线性结构的排序跟非线性结构的排序选择的算法肯定不一样
    3. 程序=数据结构+算法
    4. 总结：
      1. 算法是为了解决实际问题而设计的
      2. 数据结构是算法需要处理的问题载体
      3. 数据结构与算法相辅相成
  3. 算法特性
    1. 输入
      1. 算法具有0个或多个输入
    2. 输出
      1. 算法至少有1个或多个输出
    3. 有穷性
      1. 算法在有限的步骤之后会自动结束而不会无限循环
    4. 确定性
      1. 算法中的每一步都有确定的含义，不会出现二义性
    5. 可行性
      1. 算法的每一步都是可行的
  4. 算法的时间复杂度
    1. 代码最终都会转化为一条一条指令
    2. 同一台计算机上执行每一条指令的时间是相同的
    3. 假设每条语句相当于一条指令（这里只是假设，本质上不会跟语言相关），那么确定一个算法的时间复杂度就是这个代码语句的数量

    4. 举例下面的算法

       long sum1(int n)
 {
     long ret = 0;                         
     int* array = (int*)malloc(n * sizeof(int)); 
     int i = 0;  
            
     for(i=0; i<n; i++)   
     {
         array[i] = i + 1;
     }
            
     for(i=0; i<n; i++) 
     {
         ret += array[i];
     }
            
     free(array); 
            
     return ret; 
 }
        
 long sum2(int n)
 {
     long ret = 0;
     int i = 0;
            
     for(i=1; i<=n; i++)
     {
         ret += i;
     }
            
     return ret;
 }

 long sum3(int n)
 {
     long ret = 0;
            
     if( n > 0 )
     {
         ret = (1 + n) * n / 2; 
     }
            
     return ret;
 }
      1. 这3个算法的语句数量(时间复杂度)分别为：2n+5、n+3、3
    5. 大O表示法：
      1. 一个算法的时间复杂度用程序的语句数量表达式来表达，当n很大时，常量可以忽略不计
        1. 上面上个用大O表示法为：O(n),O(n),O(1)
      2. 判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略。
      3. 在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度。
      4. 特点：
        1. 算法效率严重依赖于操作(Operation)数量
        2. 在判断时首先关注操作数量的最高次项
        3. 操作数量的估算可以作为时间复杂度的估算

      5. 常见的时间复杂度

        图4

  5. 算法的空间复杂度
    1. 算法的空间复杂度通过计算算法分配的存储空间实现
      1. S(n) = O(f(n))
        1. 其中，n为问题规模，f(n)为在问题规模为n时所占用存储空间的函数
    2. 大O表示法同样适用于算法的空间复杂度
    3. 当算法执行时所需要的空间是常数时，空间复杂度为O(1)
    4. 空间与时间的策略
      1. 多数情况下，算法执行时所用的时间更令人关注
      2. 如果有必要，可以通过增加空间复杂度来降低时间复杂度
      3. 同理，也可以通过增加时间复杂度来降低空间复杂度
    5. 例如：
      1. 上面的sum1、sum2、sum3的空间复杂度为：4n+12、8、4
      2. 用大O表示法为：O(n)，O（1），O（1）
    6. 时间换空间举例：
      1. 问题： 在一个由自然数1-1000中某些数字所组成的数组中，每个数字可能出现零次或者多次。设计一个算法，找出出现次数最多的数字。
      2. 实现方法
        1. 方法1：排序，然后找出出现次数最多的数字

        2. 方法2：时间换空间，即通过分配内存来简化时间复杂度

           void search(int a[], int len)
 {
     int sp[1000] = {0};
     int i = 0;
     int max = 0;
     //遍历数组，把每一个数字出现的次数缓存在sp数组中
     for(i=0; i<len; i++)     //时间复杂度n
     {
         int index = a[i] - 1;
                        
         sp[index]++;
     }
                    
     //遍历sp数组，找到最大值
     for(i=0; i<1000; i++) //时间复杂度n
     {
         if( max < sp[i] )
 	    {
             max = sp[i];
         }
     }
                    
     //打印出编号
     for(i=0; i<1000; i++) //时间复杂度n
     {
         if( max == sp[i] )
         {
             printf("%d\n", i+1);
         }
     }
 }
 int main()
 {
     int array[] = {1, 1, 3, 4, 5, 6, 6, 6, 2, 3};
                    
     search(array, sizeof(array)/sizeof(*array));
                    
     return 0;
 }
          1. 把每一个数字出现的次数的中间结果缓存到一个数组中
          2. 数字的出现结果按照数组的下标对应存储
          3. 比如：数字n出现的次数，放在新开辟的内存空间的a[n-1]的位置
          4. 这个算法的时间复杂度为：O(n)，用数组sp开辟的内存空间简化
          5. 如果使用方法1，那么时间复杂度是O(n的2次方)

线性表

  1. 线性表的定义：
    1. 线性表(List)是零个或多个数据元素的集合
    2. 线性表中的数据元素之间是有顺序的
    3. 线性表中的数据元素个数是有限的
    4. 线性表中的数据元素的类型必须相同
  2. 性质
    1. a0为线性表的第一个元素，只有一个后继
    2. an为线性表的最后一个元素，只有一个前驱
    3. 除a0和an外的其它元素ai，既有前驱，又有后继
    4. 线性表能够逐项访问和顺序存取

  3. 举例：

     下面的关系中可以用线性表描述的是  答案：D
 A.班级中同学的友谊关系 N:N
 B.公司中的上下级关系  1:N
 C.冬天图书馆排队占座关系 1:N
 D.花名册上名字之间的关系 1::1

  4. 线性表的操作

     创建线性表
 销毁线性表
 清空线性表
 将元素插入线性表
 将元素从线性表中删除
 获取线性表中某个位置的元素
 获取线性表的长度
    1. 线性表在程序中表现为一种特殊的数据类型
    2. 线性表的操作在程序中的表现为一组函数

    3. 下面这套API分别用线性表的不同存储方式来实现：

       #ifndef _WBM_LIST_H_
 #define _WBM_LIST_H_
        
 typedef void List;
 typedef void ListNode;
        
 //创建并且返回一个空的线性表
 List* List_Create();
        
 //销毁一个线性表list
 void List_Destroy(List* list);
        
 //将一个线性表list中的所有元素清空, 线性表回到创建时的初始状态
 void List_Clear(List* list);
        
 //返回一个线性表list中的所有元素个数
 int List_Length(List* list);
        
 //向一个线性表list的pos位置处插入新元素node
 int List_Insert(List* list, ListNode* node, int pos);  
        
 //获取一个线性表list的pos位置处的元素
 ListNode* List_Get(List* list, int pos);
        
 //删除一个线性表list的pos位置处的元素  返回值为被删除的元素，NULL表示删除失败
 ListNode* List_Delete(List* list, int pos);
        
 #endif

线性表的顺序存储结构

  1. 概念：
    1. 指的是用一段地址连续的存储单元依次存储线性表的数据元素

  2. 设计实现：

     //seqlist.h文件
 #ifndef _WBM_LIST_H_
 #define _WBM_LIST_H_
    
 typedef void SeqList;
 typedef void SeqListNode;
    
 //创建并且返回一个空的线性表
 SeqList* SeqList_Create(int capacity);
    
 //销毁一个线性表list
 void SeqList_Destroy(SeqList* list);
    
 //将一个线性表list中的所有元素清空, 线性表回到创建时的初始状态
 void SeqList_Clear(SeqList* list);
    
 //返回一个线性表list中的所有元素个数
 int SeqList_Length(SeqList* list);
    
 //返回一个线性表的容量，指最大能够放多少
 int SeqList_Capacity(SeqList* list);
    
 //向一个线性表list的pos位置处插入新元素node
 int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);
    
 //获取一个线性表list的pos位置处的元素
 SeqListNode* SeqList_Get(SeqList* list, int pos);
    
 //删除一个线性表list的pos位置处的元素  返回值为被删除的元素，NULL表示删除失败
 SeqListNode* SeqList_Delete(SeqList* list, int pos);
    
 #endif
    
    
 // seqlist.c文件
 #define _CRT_SECURE_NO_WARNINGS
 #include"seqlist.h"
 #include<stdlib.h>
 #include<stdio.h>
 #include<string.h>
    
 //用数组来模拟线性表
 typedef struct _tag_seqlist
 {
 	int capacity;
 	int length;
 	int *node; //指针数组，一个数组内部存放的都是指针
 }TSeqlist;
    
 //创建并且返回一个空的线性表
 SeqList* SeqList_Create(int capacity) {
 	int ret;
 	TSeqlist *tem = NULL;
    
 	//给tem结构体分配一个内存
 	tem = (TSeqlist *)malloc(sizeof(TSeqlist));
 	if (tem == NULL)
 	{
 		ret = 1;
 		printf("SeqList_Create() err:%d \n",ret);
 		return NULL;
 	}
 	//将这个tem内存清空
 	memset(tem, 0, sizeof(TSeqlist));
 	//存储值
 	tem->capacity = capacity;
 	tem->length = 0;
 	tem->node = (int *)malloc(sizeof(void*)* capacity);
 	if (tem->node == NULL)
 	{
 		ret = 2;
 		printf("SeqList_Create2() err:%d \n", ret);
 		return NULL;
 	}
 	return tem;
 }
    
 //创建并且返回一个空的线性表
 int  SeqList_Create2(int capacity, SeqList** handle) {
 	int ret = 0;
 	TSeqlist *tem = NULL;
    
 	//给tem结构体分配一个内存
 	tem = (TSeqlist *)malloc(sizeof(TSeqlist));
 	if (tem == NULL)
 	{
 		ret = 1;
 		printf("SeqList_Create() err:%d \n", ret);
 		return ret;
 	}
 	//将这个tem内存清空
 	memset(tem, 0, sizeof(TSeqlist));
 	//存储值
 	tem->capacity = capacity;
 	tem->length = 0;
 	tem->node = (int *)malloc(sizeof(void*)* capacity);
 	if (tem->node == NULL)
 	{
 		ret = 2;
 		printf("SeqList_Create2() err:%d \n", ret);
 		return ret;
 	}
 	*handle = tem;
 	return ret;
 }
    
 //销毁一个线性表list
 void SeqList_Destroy(SeqList* list) {
 	TSeqlist *tem = NULL;
 	if (list == NULL)
 	{
 		return;
 	}
 	//释放内存
 	tem = (TSeqlist*)list;
 	if (tem->node != NULL)
 	{
 		free(tem->node);
 	}
 	free(tem);
 	return;
 }
    
 //将一个线性表list中的所有元素清空, 线性表回到创建时的初始状态
 void SeqList_Clear(SeqList* list) {
    
 	TSeqlist *tem = NULL;
 	if (list == NULL)
 	{
 		return;
 	}
 	//释放内存
 	tem = (TSeqlist*)list;
 	tem->length = 0;
 	memset(tem->node, 0, sizeof(void*)*tem->capacity);
 	return;
 }
    
 //返回一个线性表list中的所有元素个数
 int SeqList_Length(SeqList* list) {
 	TSeqlist *tem = NULL;
 	if (list == NULL)
 	{
 		return -1;
 	}
 	tem = (TSeqlist*)list;
 	return tem->length;
 }
 int SeqList_Capacity(SeqList* list) {
 	TSeqlist *tem = NULL;
 	if (list == NULL)
 	{
 		return -1;
 	}
 	tem = (TSeqlist*)list;
 	return tem->capacity;
 }
 //向一个线性表list的pos位置处插入新元素node
 int SeqList_Insert(SeqList* list, SeqListNode* node, int pos) {
 	TSeqlist *tem = NULL;
 	int i = 0;
 	if (list == NULL || node==NULL)
 	{
 		return -1;
 	}
 	tem = (TSeqlist*)list;
 	//如果已满则报错
 	if (tem->length>= tem->capacity)
 	{
 		return -2;
 	}
 	//容错处理，防止不连续
 	if (pos>tem->length)
 	{
 		pos = tem->length;
 	}
 	//最后一个元素的值往后移动，
 	for (i=tem->length; i>pos;i--)
 	{
 		tem->node[i] = tem->node[i - 1];
 	}
 	tem->node[i] = (int*)node;
 	tem->length++;
 	return 0;
 }
    
 //获取一个线性表list的pos位置处的元素
 SeqListNode* SeqList_Get(SeqList* list, int pos) {
 	TSeqlist *tem = NULL;
 	SeqListNode *temN = NULL;
 	tem = (TSeqlist*)list;
 	if (tem==NULL || pos<0 || pos>=tem->capacity)
 	{
 		return NULL;
 	}
 	temN = (SeqListNode *)tem->node[pos];
 	return temN;
 }
    
 //删除一个线性表list的pos位置处的元素  返回值为被删除的元素，NULL表示删除失败
 SeqListNode* SeqList_Delete(SeqList* list, int pos) {
 	TSeqlist *tem = NULL;
 	SeqListNode *temN = NULL;
 	int i = 0;
 	tem = (TSeqlist*)list;
 	if (list == NULL || pos<0 || pos >=tem->capacity)
 	{
 		return NULL;
 	}
 	temN =(SeqListNode*)tem->node[pos];
 	for (int i = pos+1; i < tem->length; i++)
 	{
 		tem->node[i - 1] = tem->node[i];
 	}
 	tem->length--;
 	return temN;
 }
    
 //main.c文件
 #define _CRT_SECURE_NO_WARNINGS
 #include<stdlib.h>
 #include<string.h>
 #include<stdio.h>
 #include"seqlist.h"
    
 typedef struct _Teacher
 {
 	char name[32];
 	int age;
    
 } Teacher;
    
 //思考1: 如何实现 链表的api(链表的算法) 和 具体的数据分离
 //思考2: 链表库(业务逻辑)  测试程序的业务逻辑  结点的生命周期 归谁管?
 int main(){
    
 	Teacher t1, t2, t3;
 	t1.age = 31;
 	t2.age = 32;
 	t3.age = 33;
 	int ret = 0;
 	SeqList *list;
 	//创建线性表
 	list = SeqList_Create(10);
 	//插入元素,头插法
 	ret = SeqList_Insert(list, (SeqListNode*)&t1, 0);
 	ret = SeqList_Insert(list, (SeqListNode*)&t2, 0);
 	ret = SeqList_Insert(list, (SeqListNode*)&t3, 0);
    
 	//遍历线性表//获取线性表的长度
 	for (int i = 0; i < SeqList_Length(list); i++)
 	{
 		//获取线性表的节点
 		Teacher *teacher = (Teacher *)SeqList_Get(list, i);
 		if (teacher == NULL)
 		{
 			printf("SeqList_Get:error%d \n", i);
 		}
 		printf("age:%d \n", teacher->age);
 	}
    
    
 	//删除线性表
 	while (SeqList_Length(list) > 0)
 	{
    		
 		Teacher *teacher = (Teacher *)SeqList_Delete(list, 0);
 		if (teacher == NULL)
 		{
 			printf("SeqList_Delete:error \n");
 		}
 		printf("SeqList_Delete-age:%d \n", teacher->age);
 	}
    
 	//销毁线性表
 	SeqList_Destroy(list);
    
 	system("pause");
 	return 0;
 }
  3. 优点和缺点
    1. 优点：
      1. 无需为线性表中的逻辑关系增加额外的空间
      2. 可以快速的获取表中合法位置的元素
    2. 缺点：
      1. 插入和删除操作需要移动大量元素
      2. 当线性表长度变化较大时难以确定存储空间的容量

All content is licensed under CC BY-NC-SA

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

Table of Contents