线性表
线性表的顺序结构，链式结构的实现。
image.png
image.png

1.线性表的顺序表示

image.png
image.png
image.png
事件复杂度是要忽略高阶项系数和低阶项，上面的答案是O(n)
image.png
image.png
image.png
image.png
动态分配的数组仍属于顺序存储结构
什么是动态分配？

  • int p=(int )malloc(sizeof(int)*10);申请了一个空间，用数组的方式去做。

image.png
所有数据结构的4种操作：

  • 增删改查

什么是单步调试？

  • 每执行一步，数据的变化是怎么样的，是否符合自己的预期。
  1. #define _CRT_SECURE_NO_WARNINGS
  3. #include<stdio.h>
  4. #include<stdlib.h>
  7. typedef int ELemType;
  8. typedef struct LNode{
  9.     ELemType data;
  10.     struct LNode* next;//指向下一个结点
  11. }LNode,*LinkList;
  13. //头插法
  14. //和表尾无关，只动表头，所以变化L，初始化时表头就是表尾
  15. //先给表头申请空间，在判断插入的数据是否符合条件，符合则申请下一个链表空间
  16. //先让s指向L指向的元素(初始时为Null),(因为L不能同时指向两个结点，所以不先连接L和s)，再让L指向s
  17. // 如果先让L指向s的话，那就以前的p的next就失效了
  18. //输入数据，执行循环
  19. void CreateList1(LinkList &L) {
  20.     LNode* s;
  21.     int x;
  22.     L = (LinkList)malloc(sizeof(LNode));//带头结点的链表
  23.     L->next = NULL;//L->data里面没有放东西
  24.     scanf("%d", &x);//从标准输入读取数据
  25.     //3 4 5 6 7 9999
  26.     while (x != 9999) {
  27.         //如果输出的不是9999，,则添加元素申请一个新空间给s，强制类型转换
  28.         s = (LNode*)malloc(sizeof(LNode));
  29.         s->data = x;//吧读取到的值给新空间中的data成员
  30.         s->next = L->next;//让新结点的next指针指向链表的第一个元素(第一个放我们数据的元素)
  31.         L->next = s;//让s作为第一个元素
  32.         //第一个元素不是头结点，因为头结点什么也没存
  33.         scanf("%d", &x);//从标准输入读取数据
  34.     }
  35.     }
  37. //尾插法
  38. // 不管表头的事，初始化时表头就是表尾，前面不动，只动表尾
  39. //先给表头申请空间，在判断插入的数据是否符合条件，符合则申请下一个链表空间
  40. //因为r是表尾，所以next为NULL
  41. //定义一个结构体s存要插入的数据，复制表头的地址，做表尾，用于确定尾部的位置(确定是否超出范围等等)
  42. //进入循环后，给s赋值和下一个结点地址，r的next由Null指向s，s成为表尾
  43. LinkList CreateList2(LinkList &L) {
  44.     int x;
  45.     L = (LNode*)malloc(sizeof(LNode));//申请一个带头结点的链表
  48.     LNode* s, * r = L;//结构体指针,也可以写成LinkList s,r=L;r代表表尾结点，r指向表位尾部
  49.     //创建r是为了让r始终指向尾部，否则下次插入就要从开头遍历到尾部
  51.     scanf("%d",&x);
  52.     while (x != 9999) {
  53.         s = (LinkList)malloc(sizeof(LNode));
  54.         s->data = x;
  55.         r->next = s;//让尾部结点指向新结点
  56.         r = s;//r指向是表尾结点
  57.         scanf("%d",&x);
  58.     }
  59.     r->next = NULL;//让尾指针的next指针赋值为NULL
  60.     return L;
  63. }
  66. //打印链表
  67. //不改变值，不用加引用，如果加引用的话最后的结果为Null
  68. //如果不想改变值且加了引用,可以把形参给另一个变量来操作另一个变量
  69. //如void PrintList(LinkList &a) LinkList L=a;
  70. void PrintList(LinkList L) {
  71.     //要不要加引用，就是看是不是在子函数中要去改变主函数对应的变量，要改就要加。
  73.     L = L->next;
  74.     while (L != NULL) {//NULL是代表一张空的藏宝图，next是宝藏
  75.         printf("%3d\n",L->data);//打印当前结点数据
  76.         L = L->next;//指向下一个结点
  77.     }
  78. }
  80. //按序列查找
  81. //先定义一个序号，代表链表当前位置，在定义链表p表示当前所在链表
  82. //判断序列是否合法
  83. // 进入循环遍历，判断链表是否为空，且当前位置不能大于要查的序列
  84. // 挨个遍历
  85. LinkList GetElem(LNode* L, int i) {
  86.     int j = 1;//从第一个有数据的结点开始，因为下一步是L->next，所以j=1
  87.     LinkList p = L->next;//让p指向下一个结点
  88.     if (0 == i)
  89.         return L;//i是0就返回头结点
  90.     if (i < 1)
  91.         return NULL;
  92.     while (p&&j<i) {
  93.         p = p->next;//让p指向下一个结点
  94.         j++;
  95.     }
  96.     return p;
  97. }
  99. //按值查找
  100. LinkList LocateElem(LinkList L,ELemType e) {
  101.     LinkList p = L->next;
  102.     while (p != NULL&&p->data!=e) {
  103.         p = p->next;
  104.     }
  105.     return p;
  106. }
  110. //往第i个位置插入元素
  111. bool ListFrontInsert(LinkList L,int i,ELemType e) {
  112.     LinkList p = GetElem(L,i-1);//拿到要插入位置的前一个结点的地址值
  113.     if (NULL == p) 
  114.         return false;
  115.     LinkList s = (LinkList)malloc(sizeof(LNode));//给新结点申请空间
  116.     s->data = e;
  117.     s->next = p->next;
  118.     p->next = s;
  119.     return true;
  120. }
  122. //删除第i个位置的元素
  123. // 要找到前一个结点
  124. //需要两个链表，一个是结点前的，一个是结点后的，因为删除后要连接起来
  125. //判断前一个结点是否为空结点
  126. // 让前一个结点的next指向要删除结点的next
  127. // 释放当前要删除的结点，避免空指针异常
  128. //没有用引用，是因为没有改变L的值
  129. bool ListDelete(LinkList L,int i){
  130.     LinkList p = GetElem(L, i - 1 );
  131.     if (NULL == p) //判断p，因为要访问p->next如果为Null下面的程序就会崩溃
  132.         return false;
  133.     LinkList q = p->next;
  134.     if (q == NULL)
  135.         return false;
  136.     p->next = q-> next;
  137.     free(q);
  138.     q = NULL;//为了避免野指针
  139.     return true;
  140. }
  143. int main() {
  144.     LinkList L;//链表头，是结构体指针类型
  145.     LinkList search;
  146.     CreateList2(L);//输入数据可以为3 4 5 6 7 9999(输入9999代表循环结束)
  147.     PrintList(L);
  148.     search=GetElem(L, 2);//查找链表第二个位置的元素值
  149.     if (search != NULL) {
  150.         printf("按序号查找成功\n");
  151.         printf("%d\n",search->data);
  152.     }
  153.     search = LocateElem(L,6);//按值查询
  154.     if (search != NULL) {
  155.         printf("按值查找成功:%d\n", search->data);
  157.     }
  159.     ListFrontInsert(L,2,99);
  160.     PrintList(L);
  162.     //ListDelete(L, 4);
  163.     //PrintList(L);
  165.     return 0;
  166. }