一．线性表（ Linear List ）的定义：线性表是零个或多个具有相同类型的数据元素的有限序列。数据元素的个数定义为线性表的 长度 。长度等于零时称为空表，一个非空表通常记为 L ＝ ( a 1 ， a 2 ，……， a n ) 其中， a i （ 1 ≤ i ≤ n ）称为数据元素，下标 i 表示该元素在线性表中的位置或序号， 称元素 a i 位于表的第 i 个位置，或称 a i 是表中的第 i 个元素。
二、线性表的定义：
typedef struct{
ElemType *elem;
int length;
int listsize;
}List;
- 线性表基本操作：
1.InitList(&L)
/*操作结果：构造一个空的线性表*/
2.DestroyList(&L)
/*初始条件：线性表L已存在*/
/*操作结果：销毁线性表L*/
3.ClearList(&L)
/*初始条件：线性表L已存在*/
/*操作结果：将L重置为空表*/
4.ListEmpty(L)
/*初始条件：线性表L已存在*/
/*操作结果：若L为空表，则返回TRUE，否则返回FALSE*/
5.ListLength(L)
/*初始条件：线性表L已存在*/
/*操作结果：返回L中数据元素个数*/
6.GetElem(L,i,&e)
/*初始条件：线性表L已存在,1≤i≤LIST_SIZE*/
/*操作结果：用e返回L中第i个数据元素的值*/
7.LocatElem(L,e,compare())
/*初始条件：线性表L已存在,compaer()是数据元素判断函数*/
/*操作结果：返回L中第1个与e满足关系compaer()的数据元素的位序。若这样的数据元素不存在，则返回0*/
8.PriorElem(L,cur_e,&pre_e)
/*初始条件：线性表L已存在*/
/*操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义*/
9.NextElem(L,cur_e,&next_e)
/*初始条件：线性表L已存在*/
/*操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后续，否则操作失败，next_e无定义*/
10.ListInsert(&L,i,e)
/*初始条件：线性表L已存在*/
/*操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1*/
11.ListDelete(&L,i,&e)
/*初始条件：线性表L已存在*/
/*操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1*/
四、部分操作代码：
单链表的存储结构：
typedef struct Node
{
ElemType data;
struct Node* next;
}Node, * LinkList;
初始化操作：
Status InitList(LinkList* L)
{
*L = (LinkList)malloc(sizeof(Node));
if (!(*L))
{
return ERROR;
}
(*L)->next = NULL;
return OK;
}
单链表的读取：
Status GetElem(LinkList L, int i, ElemType* e)
{
int j;
LinkList p;
p = L->next;
j = 1;
while (p && j < i) //p不为空，循环遍历到i
{
p = p->next;
j++;
}
if (!p || j > i)
{
return ERROR;
}
*e = p->data;
return OK;
}
插入操作：
Status ListInsert(LinkList* L, int i, ElemType e)
{
int j;
LinkList p, s;
p = *L;
//此时p为链表中带头结点
j = 1;
while (p && j < i) // 用于寻找第i个结点
{
p = p->next;
j++;
}
if (!p || j > i)
{
return ERROR;
}
s = (LinkList)malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
删除操作：
Status ListDelete(LinkList* L, int i, ElemType* e)
{
int j;
LinkList p, q;
p = *L;
j = 1;
while (p->next && j < i)
{
p = p->next;
++j;
}
if (!(p->next) || j > i)
{
return ERROR;
}
q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return OK;
}
头插法：
void CreateListHead(LinkList* L, int n)
{
LinkList p;
int i;
srand(time(0)); // 初始化随机数种子
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
for (i = 0; i < n; i++)
{
p = (LinkList)malloc(sizeof(Node)); // 生成新结点
p->data = rand() % 100 + 1;
p->next = (*L)->next;
(*L)->next = p;
}
}
尾插法：
void CreateListTil(LinkList* L, int n)
{
LinkList p, r;
int i;
srand(time(0));
//初始化随机数种子
*L = (LinkList)malloc(sizeof(Node));
r = *L;
for (i = 0; i < n; i++)
{
p = (LinkList)malloc(sizeof(Node));
p->data = rand() % 100 + 1;
r->next = p;
r = p;
}
r->next = NULL;
}
整表清空：
Status ClearList(LinkList* L)
{
LinkList p, q;
p = (*L)->next;
while (p)
{
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL;
return OK;
}
打印：
void ShowList(LinkList L)
{
LinkList p;
p = L->next;
while (p)
{
printf(“%d “, p->data);
p = p->next;
}
}
主方法：
int main()
{
LinkList L;
Status i;
i = InitList(&L);
CreateListHead(&L, 10); //调用头插法操作函数创建长度为10的单链表
ShowList(L);
return 0;
}
五、顺序表
特点：线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，
作用：线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。
顺序存储的实现：一维数组存储顺序表中的数据
线性表顺序表示的优点是:
(1) 无需为表示结点间的逻辑关系而增加额外的存储空间（因为逻辑上相邻的元素其存储的物理位置也是相邻的）；
(2) 可方便地随机存取表中的任一元素。
线性表顺序表示的缺点：
(1) 插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低；
- 由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配，因此当表长变化较大时，难以确定合适的存储规模。
六、一元多项式相加中的三种情况：
1、若pa->exp<qb->exp， 则结点pa所指的结点应是“和多项式”中的一项，将结点pa插入在结点pc之后,令指针pa、pc后移；
2、 若pa->exp>qb->exp，则结点qb所指的结点应是“和多项式”中的一项，将结点pb插入在结点pc之后，pb 、pc后移；
若pa->exp=qb->exp， 则将两个结点中的系数相加， 释放qb结点;
当和不为零时修改结点pa的系数域， pa、pc后移；
若和为零，释放pa,pa后移。
- 合并算法：
1、设置工作指针pa,pb,pc，并对其进行初始化
2、重复做以下工作，直到pa或pb为空
3、将pa的值和pb的值进行比较
4、如果pa->data>pb->data,
5、pc->next=pb,pb=pb->next
6、如果pa->data<=pb->data,
7、pc->next=pa,pa=pa->next
8、Pc=pc->next
9、如果pa不空，
10、则将pa中剩余的结点链入pc
11、否则，将pb中剩余的结点链入pc
总结：若线性表的操作主要是进行查找，很少做插入和删除时，宜采用顺序表做存储结构。
因此，对于频繁进行插入和删除的线性表， 宜采用链表做存储结构。