数据结构学习二线性结构

发表于 更新于

学习数据结构笔记

线性结构

线性表

举例：一元多项式
$$f^{x} = a_0 + a_1{^x}+ … a_{n-1}{^n-1} + a_n^{x^n}$$

主要运算： 多项式相加、相减、相乘

分析如果表达多项式：

  1. 多项式的项数 n
  2. 各项系数 a_i 及指数 i

使用数组，以值为底，数组的下标当做指数，这样有很多的 0 项造成了空间的浪费。

那么可以使用数组将每一项分为一组，每组存两个数一个数是指数一个数是底数，这样就可以完全忽略掉 0 项。

还可以使用链表储存非零项

在链表中每个节点储存多个项式中的一个非零项，包括系数和指数两个数据域以及一个指针域

coef expon link 
1
2
3
4
5
6
7
typedef struct PolyNode *Polynomial;

struct PolyNode{
    int coef;
    int expon;
    Polynomial link;
}

什么是线性表

线性表：由同类型数据元素构成有序列表的线性结构。

  1. 表中元素个数称为线性表的长度

  2. 线性表没有元素时，成为空表

  3. 表起始位置称为表头，表结束位置称为表尾

线性表，使用一个数组，来储存值，但是数组是连续的，对其进行插入，需要找到位置，然后将其他值向后移动，然后插入，删除需要找到位置删除，将其他值向前移动，很麻烦。

链表，使用一个结构体，并且在结构体中储存值和下一个结构体的指针位置，但是链表的长度，和每个结构体的位置都不是已知的需要进行遍历，对链表进行删除和新增，只需要遍历找到位置，然后前一个结构体的指针指向新增的，即可，删除也很方便。

广义表，广义表是线性表的的推广，对于线性表而言，n 个元素都是基本的单元素，广义表中，这些元素不仅可以是单元素，也可以是另外一个广义表

多重链表： 链表中的节点可能同时隶属于多个链，多重链表中节点的指针域会有多个，但包含两个指针域的链表并不一定是多重链表，如双向链表并不是多重链表，多重链表有较多的用途：基本上如树``图这样相对复杂的数据结构都可以采用多重链表方式实现储存

堆栈

堆栈在计算机学科中有广泛的应用，例如函数调用，递归，表达式求值，都需要用到堆栈。

什么是堆栈

堆栈：具有一定操作约束的线性表，只在一端（栈顶）做插入、删除，插入数据：入栈，删除数据：出栈，后入先出

比如日常使用的碗，依次堆叠之后，那么最后放上去的总是最先使用的。

最简单的堆栈实现是使用一个一维数组和一个记录栈顶元素位置的变量组成

堆栈的链式储存实现

栈的链式储存结构实际上是一个单链表，叫做链栈，插入和删除操作只能在链栈的栈顶的进行。

堆栈的其他应用：
函数调用及递归实现
深度优先搜索
回溯算法等等

总结一下，数组和链表优缺点

数组：编程简单，调试容易，但是事先需要确定数组大小
链表：动态性强，编程略微复杂调试比较困难

课后题：

要求实现一个函数，将两个链表表示的递增整数序合并为一个非递减的整数序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
List Merge(List L1, List L2) {
   List L3;
   L3 = (PrtToNode)malloc(sizeof(struct Node)); // 申请内存
   L3 -> Next = NULL;

   PtrToNode tmp, p1, p2;
   tmp = L3;
   if(L1->Next == NULL && L2->Next!=NULL){
       // 判断L1还有位置，且L2不为空
       L3->Next = L2->Next;
       L2->Next = NULL;
   }elseif(L1->Next != NULL && L2->Next == NULL){
       L3->Next = L1->Next;
       L1->Next = NULL;
   }
   if((L1->Next !=NULL) && (L2->Next != NULL)){
       while(!(L1->Next==NULL && L2->Next==NULL)){
           if(L1->Next != NULL && L2->Next == NULL){
               tmp->Next = L1->Next;
               L1->Next = NULL;
               break;
           }
            if(L1->Next == NULL && L2->Next != NULL){
               tmp->Next = L2->Next;
               L2->Next = NULL;
               break;
           }

           if(L1->Next != NULL && L2->Next != NULL){
               if(L1->Next->Data < L2->Next->Data){
                   tmp->Next = L1->Next;
                   tmp = tmp->Next;
                   L1->Next = L1->Next->Next;
               }else{
                   tmp->Next = L2->Next;
                   tmp = tmp->Next;
                   L2->Next = L2->Next->Next;
               }
   }
   return L3;
}