首页 > 代码库 > 数据结构快速回顾——开篇

数据结构快速回顾——开篇

2024-07-06 19:25:12   224人阅读

六月到了。开始找工作的节奏，IT方面知识储备严重欠缺，定计划，更新博客，记录自己的准备历程。

1、数据结构　　15天

2、常用算法（排序、动态规划、贪心等）　　30天

3、数据挖掘算法　　　15天

4、移动端、web端开发入门　　15天

5、操作系统　　10天

共计85天，那时将近9月，还能赶上找工作的大潮。

 

何为数据结构？数据结构用处？
一般来说，使用计算机解决一个问题的时候需要经历以下步骤：分析问题、抽象出数学模型、设计解数学模型的算法、写程序、测试、得到最终结果。为了解决非数值型数学模型，需要使用诸如表、树、图之类的数据结构，数据结构可以帮助我们更好的表达和操作非数值计算的程序中的对象。
定义：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

根据数据元素之间关系的特征分为以下四种基本结构：集合、线性结构（链表）、树形结构、图状结构。

根据数据元素在计算机中的存储方式分为以下两种结构：顺序存储结构和链式存储结构。

本篇主要介绍第一种数据结构——线性表
线性表是n个数据元素组成的有限序列。数据元素的内容是可变的。

线性表的顺序表示及实现：
顺序表示是指使用一组地址连续的存储单元依次存储线性表的数据元素。

  1 //定义线性表顺序存储结构
  2 #define OVERFLOW -2
  3 #define OK 1
  4 #define ERROR 0
  5 #define LIST_INIT_SIZE 100
  6 #define LISTINCREMENT 10 //空间不足时 增加分配的空间大小
  7 
  8 typedef int ElemType;
  9 typedef int Status;
 10 
 11 typedef struct
 12 {
 13         ElemType *elem;//存储数据的首地址
 14         int length;    //当前长度
 15         int listsize;//线性表容量
 16 }SqList;
 17 
 18 //初始化顺序表
 19 Status InitList_Sq(SqList &L)
 20 {
 21         L.elem = (ElemType*) malloc (LIST_INIT_SIZE * sizeof(ElemType));
 22         if(!L.elem)
 23                 exit(OVERFLOW);
 24         L.length = 0;
 25         L.listsize = LIST_INIT_SIZE;
 26         return OK;
 27 }
 28 
 29 //创建顺序表
 30 void CreateList(SqList &L, int len)
 31 {
 32         if(len > LIST_INIT_SIZE)   //顺序表大小大于初始化大小，重新分配空间
 33         {
 34                 L.elem = (ElemType*) realloc (L.elem, len*sizeof(ElemType));
 35                 L.listsize = len;
 36         }
 37         printf("请输入顺序表元素: \n");
 38         for(int i = 0; i < len; i++)
 39                 scanf("%d", &L.elem[i]);
 40         L.length = len;
 41         printf("建立的顺序表为:\n");
 42         for(int i = 0; i < len; i++)
 43                 printf("%d ", L.elem[i]);
 44         printf("\n顺序表一共 %d 个元素。\n",L.length);
 45 }
 46 
 47 //顺序表L的第i个位置之前插入新的元素e
 48 Status ListInsert_Sq(SqList &L, int i, ElemType e)
 49 {
 50     if(i > L.length+1 || i<1)
 51         return ERROR;
 52     if(i > L.listsize)
 53     {
 54         newBase = (ElemType*)realloc(L.elem, (L.listsize+LISTINCREMENT）*sizeof（ElemType);
 55         if(!newBase)
 56             exit(OVERFLOW);
 57         L.elem = newBase;
 58         L.listsize += LISTINCREMENT;
 59     }
 60     ElemType *q,*p;
 61     q = &(L.elem[i-1]);
 62     for(p = &(L.elem[L.length-1]); p > q; --p)
 63         *(p+1) = *p;
 64     *q = e;
 65     ++L.length;
 66     return OK;
 67 }
 68 
 69 //删除顺序表L的第i个位置
 70 Status ListInsert_Sq(SqList &L, int i, ElemType& e)
 71 {
 72     if(i > L.length || i<1)
 73         return ERROR;
 74 
 75     ElemType *q,*p;
 76     q = &(L.elem[i-1]);
 77     e = *q;
 78     p = &(L.elem[L.length-1]);
 79     for(;  q < p ; ++p)
 80         *q = *(q+1);
 81 
 82     --L.length;
 83     return OK;
 84 }
 85 //返回指定位置的元素
 86 ElemType GetElem(SqList &L, int i)
 87 {
 88         ElemType *e;
 89         if(!L.elem || i > L.length || i < 1)
 90                 exit (ERROR);
 91         e = L.elem+i-1;
 92         return *e;
 93 }
 94 
 95 
 96 //定位指定元素，如果有，返回第一个匹配的元素的位置
 97 int LocateElem(SqList &L, ElemType e)
 98 {
 99         int i;
100         if(!L.elem)
101                 exit (ERROR);
102         for(i = 0; i < L.length; i++)
103                 if(e == L.elem[i])
104                         return i+1;
105         return 0;
106 }

 

线性表的链式表示及实现：


联系
我们