数据结构学习笔记（一）

线性表的基础概念

1.线性表是 n 个数据元素的有限序列，是一种线性关系，通常是一对一的关系

线性表操作

InitList(&L):初始化操作，构造一个空的线性表L。InsertList(&L,i,e):在线性表L的第i个位置插入新的数据元素e。DeleteList(&L,i,&e):删除线性表L的第i个位置的数据元素，并用e返回其值。ClearList(&L):将一个线性表L重置为一个空表。ListEmpty(L):判断一个线性表是否为空表。GetElem(L,i,&e):将线性表L的第i个位置的数据元素返回给e。LocateElem(L,e):查找线性表L中是否有和给定值e相等的数据元素，有则返回该数据元素在线性表中的序号。ListLength(L):返回线性表L中数据元素的个数，即求表长。

线性表

1.顺序表

线性表采用顺序储存结构的线性表称为顺序表 顺序表是一种随机存取的存储结构

#define ListSize100/顺序表的最大尺寸typedef int DataType;/顺序表元素类型typedef struct{DataType list[ListSize];/存储顺序表数据的数组int length;/顺序表长度}SeqList;

struct 是关键字，表示一个结构体类型，SeqList 是该结构体的类型名； {}里面是结构体的成员，list[ListSize]用来存储线性表中的数据元素，length 表示当前线性表中数据元素的个数； 如果要定义一个顺序表 L,则 SeqList L。

顺序表操作之插入

要求:插入操作就是在线性表 L 的第个位置插入数据元素 e,使线性表由{a1,a2,,ai-1,ai,…,an}变为{a1,a2,,ai-1,e,ai,,an},同时线性表的长度由 n 变为 n+1。

注意点:1. 满表不能进行插入操作 2. 插入位置必须合法

插入操作实现步骤:1. 将第 i 个位置之后的团苏全部后移. 2. 将待插入元素放入第 i 个位置, 3. 表长加一

顺序表操作之删除

注意点:1. 空表不能进行删除操作 2. 删除位置必须合法

删除过程： (1)被删除的数据元素赋值给 e。 (2)将第个位置以后的数据元素依次向左移动一个位置。 (3)将顺序表的表长减 1。

2. 链式表

链式表中的数据元素是以结点的方式储存的，每个结点中有数据域和指针域。（指针域中储存后继元素的储存位置）

头结点

单链表分为两种，一种是带头结点的单链表，一种是不带头结点的单链表。 头结点，是在单链表的第一个结点之前增加的一个结点，头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等信息，头结点的指针域用来存储第一个数据元素的存储位置。

增加头节点的好处是可以对于删除等操作所有元素都一致（第一个元素的操作不同）。

单链表的储存结构：

typedef struct Node{DataType data;struct Node *next;}ListNode,*LinkList;

struct 是关键字，表示一个结构体类型；struct Node 是一个类型名；}里面是结构体的成员，每个结点包括两个部分：数据域和指针域；ListNode 是链表的结点类型 LinkList 是指向链表结点的指针类型。 如果要定义一个单链表 L,则 LinkList L。

单链表操作之插入

1. 将待插入元素命为 p

2. 插入到 a[i]元素之后，令 a[i]=pre

1. 代码实现 //将 p 的指针域内存 a[i+1]的地址 p->next=pre->next //将 a[i]的指针域指向 p 的地址 pre->next=p

单链表操作之删除

1. 待删除的元素命名为 p

2. pre 指向待删除元素前一个

1. 代码实现 //pre 的指针域指向 p 的指针域 pre->next = p ->next //放掉 p 的内存 free(p)

练习题: 将两个顺序表 La 和 Lb,其元素均为非递减有序排列，将它们合并成一个顺序表 Lc,要求 Lc 也是非递减有序排列。 如：La=(2,2,3),Lb=(1,3,3,4),合并后 Lc=(1,2,2,3,3,3,4)。

算法思路： 1、初始化一个线性表 Lc 存放合并结果，Lc 递增有序。 2、设三个变量 i、j、k 分别指向 la、Lb、Lc 中第一个数据元素。 3、比较两个元素，若 La.elem[i]>Lb.elem[j]:将 Lb.elem[j]插入到表 Lc 中；若 La.elem[i]<=Lb.elem[j];将 La.elem[i]插入到表 Lc 中； 4、如两个表均未扫描完毕，返回 3； 5、将未扫描完的表中剩余的所有元素存放到表 Lc 中。

将两个单链表 La 和 Lb,其元素均为非递减有序排列，将它们合并成一个单链表 Lc,要求 Lc 也是非递减有序排列。 如：La=(2,2,3),Lb=(1,3,3,4),合并后 Lc=(1,2,2,3,3,3,4)。