前言

考研个人总结用（未完）

1.绪论

数据结构包括逻辑结构 物理结构 数据运算 逻辑结构线性结构 非线性结构（网状 树状） 集合 存储结构顺序存储 链式存储 索引存储 哈希存储

关联

数据的逻辑结构独立于存储结构，数据的存储方式有多种不同的选择;而数据的存储结构是逻辑结构在计算机上的映射，它不能独立于逻辑结构而存在。

例：

以下属于逻辑结构的是()

A.顺序表

B.哈希表

C.有序表

D.单链表

答案A B C都指定了存储结构，故不属于逻辑结构。

算法

算法是对特定问题求解步骤的一种描述。
特性：

• 有穷性
• 确定性
• 可行性
• 输入
• 输出

  时空复杂度

  算法原地工作是指算法所需的辅助空间为常量，即O(1)。时间复杂度一般指最坏情况下。

  2.线性表

  线性表是由具有相同数据类型的有限数据元素组成的，数据元素是由数据项组成的。

  顺序表

  逻辑结构和物理结构相同，存储密度大。顺序表中位序从1开始，数组从0开始。

  顺序表的创建

  建立顺序表的三个属性:
  1.存储空间的起始位置（数组名data） 2.顺序表最大存储容量（MaxSize） 3.顺序表当前的长度（length）

数组还可以动态分配空间，存储数组的空间是在程序执行过程中通过动态存储分配语句分配

顺序表的插入

• 判断插入的位置是否正确（i<1||i>l.length+1）
• 表长是否大于maxsize(已满)
• i之后的数据都往后移一位，插入i

  for (int j=L. length;j>=i;j--)
  L.data[j] =L.data[j-1];
  

• 修改length

  顺序表的删除

• 判断i的位置是否合法
• 取i上的值
• i位置之后的元素往前移一位

  for (int j=L. length;j>=i;j--)
  L.data[j] =L.data[j-1];
  

• 修改length

  链表

  不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息

带头结点的好处


- 处理操作简化，例如对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作统一

- 空表与非空表操作统一

单链表

声明

typedef struct Lnode {
   
ElemType data;
struct Dnode *next ;
}Lnode ,*Linklist;

双链表

声明

typedef struct Dnode {
   
ElemType data;
struct Dnode *next ,*prior;
}Dnode ,*DLinklist;

循环单链表

循环双链表

静态链表

静态链表借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，静态链表也要预先分配一块连续的内存空间。静态链表以next==-1作为其结束的标志。静态链表的插入、删除操作与动态链表的相同，只需要修改指针，而不需要移动元素。总体来说，静态链表没有单链表使用起来方便，适用于不支持指针的语言。

比较

• 顺序表可以顺序存取，也可以随机存取,链表只能顺序存储。
• 对于按值查找，时间复杂度都为O(n)，若顺序表有序则折半查找O（log₂n）,按序号查找链表为O（n）。
  q->prior(结点)->next（指针）=q（结点）

注意

修改链表，指针信息应该也要更新。

例

1.设线性表中有2n个元素，( )在单链表上实现要比在顺序表上实现效率更高。

A.删除所有值为x的元素

B.在最后一个元素的后面插入一个新元素

C.顺序输出前k个元素

D.交换第i个元素和第2n-i-1个元素的值(i=0,...,n-1)

答案（A）

2.巳知头指针h指向一个带头结点的非空单循环链表，结点结构为 data next, 其中next是指向直接后继结点的指针，p是尾指针，q是临时指针。现要删除该链表的第一个元素，正确的语句序列是( )。

A. h-> next=h-> next-> next;q= h-> next; free(q);

B. q=h-> next; h-> next= h-> next -> next; free(q);

C. q=h-> next;h-> next= q -> next; if(p != q) p= h; free(q);

D. q=h-> next; h-> next=q-> next; if(p== q) p= h; free(q);

答案第二种可以但是没有考虑特殊情况即只有一个元素。（D）

8.排序算法

例
1.对任意7个关键字进行基于比较的排序，至少要进行( ) 次关键字之间的两两比较。

A.13

B.14

C.15

D. 6

答案对于任意序列进行基于比较的排序，求最少的比较次数应考虑最坏情况。对任意n个关键字
排序的比较次数至少为「log₂(n!)]。将n=7代入公式，答案为13 （A）

冒泡排序

时间复杂度

平均时间 O（n²）最好时间 O（n）:也就是原来就是有序的 最坏时间 O（n²）

空间复杂度：

空间 O（1）

是否稳定

稳定：比较两个元素，相同则不交换，故稳定。

实现思路：

第一个for循环array.length-1次，第二个for循环负责前一位和当前位的比较，注意i，j的值不要越界。每次确定一个位置。

代码：

void BubbleSort (ElemType A[],int n) { .
for(i=0;i<n-1;i++) {
flag=false;
//表示本趟冒泡是否发生交换的标志
for (j=n-1;j>i;j--)
//一趟冒泡过程
if(A[j-1]>A[j]){
//若为逆序
swap (A[j-1],A[j]); //交换
flag=true;
}
if (flag==false)
return; :
//本趟遍历后没有发生交换，说明表已经有序
}

快速排序

时空复杂度

时间复杂度nlogn,在原数组有序的情况下复杂度O（n²）,空间复杂度O（logn）

是否稳定

不稳定

代码

void QuickSort (ElemType A[],int low, int high) {
   
if (1ow<high) {
   //递归跳出的条件
//Partition()就是划分操作，将表A[low--high]划分为满足上述条件的两个子表
int pivotpos=Partition (A, low, high); / /划分
QuickSort (A, low,pivotpos-1); // 依次对两个子表进行递归排序
QuickSort (A,pivotpos+1,high);
}
int Partition(ElemType A[],int low,int high){
    //一趟划分
ElemType pivot=A[low]; //将 当前表中第一个元素设为枢轴，对表进行划分
while (low<high) {
    / /循环跳出条件
while (low<high&&A[high]>=pivot) --high;
A[low]=A[high]; / /将比枢轴小的元素移动到左端
while (1ow<high&&A[low]<=pivot) ++1ow;
A[high]=A[1ow]; / /将比枢轴大的元素移动到右端
}
A[1ow]=pivot;//枢轴元素存放到最终位置
return low;//返回存放枢轴的最终位置
}