第二章：线性表
线性表 = 顺序表 + 链表
顺序表：
优点：1. 相比链表可以快速查找，获取任意元素。
缺点：1. 删除元素，插入元素时，需要大量移动数据。
2. 由于存储需要一块较大的空白区域，相比较链表来说，有点浪费空间。
3. 由于是静态存储，存储大小已经在定义时被确定，无法自由扩充元素。
线性表的实现：
存储结构类型定义 = 当前顺序表的元素个数 + 存储空间的基地址
typedef struct item
{
double info_1; //元素信息1
int info_2; //元素信息2
} Item;
typedef struct element {
// 线性表的当前长度
int length;
//指向数据元素的基地址
Item * elem;
} SqList;
1 初始化：
void Init_List (SqList)
{
Scanf (%d “, &max_length);
//动态分配线性表存储空间
L.elem = (Item*)malloc(sizeof(Item) * max_length);
//存储失败退出
if（L.elem == NULL）exit(overflow);
//空表长度为0
L.length = 0;
}
2 取值
int get_elem (SqList L, int i, Item &e)
{
// 判断i值是否合理
if（i < 1 || i >L.length）return ERROR;
// e中存储序号为i的元素值
e = L.elem[i-1];
return 0;
}
3 查找
int LocateElem (SqList L, Item e)
{
for (int i=0; i<L.length; i++)
{
if(L.elem[i] == e) return i+1; // 查找成功，返回序号i+1
}
return 0; //查找失败， 返回0
}
4 插入
int ListInsert (SqList &L, int I; Item e)
{
if((i<1) || (i>L.length+1))
return ERROR; //i值不合法
if(L.length == max_length)
return ERROR； //当前存储空间已满
for (int j = L. length-1; j >=i-1; j--)
{
L.elem[j+1] = L.elem[j]; //插入位置及之后的元素后移
}
L.elem[i-1] = e; //将新元素e放入第i个位置
L.length ++;
return 0;
}
5 删除
int ListDelete (SqList &L, int i)
{
if((i<1) || (L. length))
return ERROR;
for (int j =i; j<=L.length-1; j++)
{
L.elem[j-1]=L.elem[j]; // 被删除元素之后的元素全部前移
}
L.length --；
return 0;
}
链表：
优点：数据元素的个数可以自由扩充插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高。
缺点：存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问。
节点组成：
数据域：存储元素数值数据。
指针域：存储直接后继结点的存储位置。
单链表的实现：数据类型 = 数据域 + 指针域
单链表组成 = 头指针 + 头结点 + 首结点
头指针：指向头结点的指针，类型为pNode
头结点：其数据域为空，指针域的内容为下一个结点(首结点)的地址
首结点：第一个存储有效数据的结点，其数据域存储第一个有效数据
0 存储结构定义
typedef struct node
{
Int Data;
struct node Next;
} Node, *pNode;
1 初始化单链表
Int Init_List(void)
{
pNode Head = (pNode)malloc(sizeof(Node)); //Head为头指针
Head->Next = NULL; //头结点指针域设为空
return 0;
}
2 单链表取值
int Get_Elem (pNode Head, int i; int &e)
{
pNode p1 = Head->Next; // p1指向首结点
int count =1;
while(p1 && count <i)
{
//顺链域扫描，直到p1指向地i个元素
p1 = p1->Next;
count++;
}
if (p1! = NULL || count >i)
return ERROR;
e = p1->Data; //将第i个结点的数据域赋给e
return 0;
}
3 单链表查找
pNode Locate_Elem (pNode Head, int e)
{
pNode p1 = Head->Next;
while (p1 && p1->Data! = e)
{
p1 = p1->Next;
}
Return p1;
}
4单链表插入
int List_Insert (pNode Head, int i, int e)
{
pNode p1 = Head;
int count = 0;
while (p1 && (count <i-1))
{
p1 = p1->Next;
count ++; //查找第i-1个结点，p1指向该结点
}
if (p1 == NULL || count >i-1)
return ERROR;
pNode s = (pNode)malloc (sizeof (Node));
s->Data = e; //插入新结点s
s->Next = p->Next;
p->Next = s;
return 0;
}
5 单链表删除：
int List_Delete (pNode Head, int i)
{
pNode p1 = Head;
int count =0;
while((p->Next) && (count <i-1))
{
p1 = p1->Next;
count++;
}
//当i>n或i<1时，删除的位置不合适
if (! (p1->Next) || (count >i-1))
return ERROR;
//临时保存被删除的结点的地址以备释放
pNode p2 = p1->Next;
p1->next = p2->Next;
delete p2;
return 0;
}
创建单链表的方法：
1.前插法创建单链表：
Void Create_List (int n)
{
pNode Head = (pNode)malloc (sizeof (Node));
Head->Next = NULL;
for (int i = 0; i < n; i++)
{
pNode p1 = (pNode)malloc (sizeof (Node));
scanf (“%d”, &(p1->Data));
p1->Next = Head->Next;
Head->Next = p1;
}
}
2.后插法创建单链表：
void Create_List (int n){
pNode Head = (pNode)malloc (sizeof (Node));
Head->Next = NULL;
pNode rear = Head; //尾指针rear指向头结点
for (int i = 0; i< n; i++)
{
pNode p1 = (pNode)malloc (sizeof (Node));
scanf (“%d”, &(p1->Data));
p1->Next = NULL;
rear->Next = p1;
rear = p1; //rear指向尾结点
}
}
双向链表：
在单链表中，若要寻找结点的直接前驱，则需要从头指针出发，为了解决这种缺点，双向链表创建。
双向链表的存储结构
Typedef struct Double_node
{
Int Data;
struct Double_node *prior;
struct Double_node *next;
} DuNode, *pDuNode;
双向链表的插入：
int List_Insert_dul (pDuNode Head, int i, int e)
{
int count =0;
pDuNode p1 = Head;
if (p1! = NULL && count <i-1)
{
p1 = p1->Next;
count ++; // p1指向第i个元素
}
pDuNode s = (pDuNode)malloc(sizeof(DuNode)); //新结点s
s->Data = e;
s->prior = p1->prior; // 对应图1步骤1
p1->prior->Next = s; // 对应图1步骤2
s->Next = p1; // 对应图1步骤3
p1->prior = s; // 对应图1步骤4
return 0;
}
双向链表的删除：
Int ListDelete_Dul (pDuNode Head, int i)
{
pDuNode p1 = Head;
int count = 0;
while(p1->next! = NULL && count <i-1)
{
p1 = p1->Next;
}
p1->prior->next = p1->Next; //图2步骤1
p1->Next->prior = p1->prior; //图2步骤2
delete p1;
return 0;
}