线性表
线性结构是最常用，最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且有限的。
线性表的逻辑结构
线性表的定义
由n个数据元素（结点）组成的有限序列，该序列中所有结点具有相同的数据类型。
线性表的逻辑结构
线性表中的数据元素所代表的具体含义随具体应用的不用而不同，在线性表的定义中，只不过是一个抽象的表示符号。
线性表的抽象数据类型定义
ADT List{
数据对象；
数据关系；
基本操作：InitList(&L)
ListLength(L)
......
GetElem(L,i.&e)
ListInsert(L,i.&e)
......
}ADT List
线性表的顺序储存
线性表的顺序储存
顺序储存：把线性表的结点按逻辑结构依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。
除了用数组来存储线性表的元素外，还应该有表示线性表的长度属性，所以用结构类型来定义顺序表类型。`
typedef int Static;
typedef int ElemType;
typedef struct sqlist
{
ElemType Elem_array[MAX_SIZE];
int length;
}SqList;
顺序表的基本操作
顺序线性表初始化
Static Init_Sqlist(SqList *L)
{
L -> Elem_array == (ElemType *)malloc(MAX_SIZE * sizeof(ElemType));
if (!L->Elem_array) return ERROR;
else { L->length = 0; return OK; }
}
顺序线性表的插入
Static Insert_Sqlist(SqList *L, int i, ElemType e)
{
int j;
if (i<0 || i>L->length - 1)
return ERROR;
if (L->length >= MAX_SIZE) {
printf("线性表溢出！\n");
return ERROR;
}
for (j = L->length; j >= i - 1; --j)
L->Elem_array[j + 1] = L->Elem_array[j];
L->Elem_array[i - 1] = e;
L->length++;
return OK;
}
顺序线性表的删除
ElemType Delete_SqList(SqList *L, int i)
{
int k; ElemType x;
if (L->length == 0){
printf("线性表L为空\n");
return ERROR;
}
else if (i<1 || i>L->length) {
printf("要删除的数据元素不存在！\n");
return ERROR;
}
else {
x = L->Elem_array[i - 1];
for (k = i; k < L->length; k++) {
L->Elem_array[k - 1] = L->Elem_array[k];
L->length--;
return (x);
}
}
}
顺序线性表的查找定位删除
Static Locate_Delete_Sqlist(SqList *L, ElemType x)
{
int i = 0, k;
while (i < L->length)
{
if (L->Elem_array[i] != x)
i++;
else {
for (k = i + 1; k < L->length; k++)
L->Elem_array[k - 1] = L->Elem_array[k];
L->length--;
break;
}
}
if (i > L->length) {
printf("要删除的数据元素不存在！\n");
}
return OK;
}
线性表的链式储存
线性表的链式储存结构
链式存储：在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).
结点的描述
typedef struct Lnode
{
ElemType data;
struct Lnode *next;
}LNode;
结点的实现
动态分配
p = (LNode*)malloc(sizeof(LNode));
动态释放
free(p)
结点的赋值
LNode *p;
p = (LNode*)malloc(sizeof(LNode));
p->data = 20; p->next = NULL;
单线性链式的基本操作
建立单链表
有两种常用方法：头插法；尾插法
（假设结点的数据类型是整型，以6789作为结束标志）
头插法
LNode *create_LinkList(void)
{
int data;
LNode *head,*p;
head = (LNode*)malloc(sizeof(LNode));
head->next = NULL;
while (1)
{
scanf("%d", &data);
if (data == 6789)
break;
p= (LNode*)malloc(sizeof(LNode));
p->next = data;
p->next = head->next;
head->next = p;
}
return (head);
}
尾插法
LNode *create_LinkList(void)
{
int data;
LNode *head,*p,*q;
head = (LNode*)malloc(sizeof(LNode));
p->next = NULL;
while (1)
{
scanf("%d", &data);
if (data == 6789)
break;
q= (LNode*)malloc(sizeof(LNode));
q->data = data;
q->next = p->next;
p->next = q;
p = q;
}
return (head);
}
单链表的查找
（1）按序号查找
ElemType Get_Elem(LNode *L, int i)
{
int j;
LNode *p;
p = L->next;
j = 1;
while (p != NULL && j < i) {
p = p->next;
j++;
}
if (j != i)
return (-6789);
else
return (p->data);
}
（2）按值查找
LNode *Locate_Node(LNode *L, int key)
{
LNode *p = L->next;
while (p != NULL && p->data != key)
p = p->next;
if (p->data == key) return p;
else
{
printf("你所要查找的结点不存在！！\n");
return (NULL);
}
}
单链表的插入
void Insert_LNode(LNode *L, int i,ElemType e)
{
int j = 0; LNode *p, *q;
p = L->next;
while (p != NULL && j < i - 1) {
p = p->next; j++;
}
if (j != i - 1)
printf("i太大或i为0！！\n");
else {
q = (LNode*)malloc(sizeof(LNode));
q->data = e;
q->next = p->next;
p->next = q;
}
}
单链表的删除
（1）按序号删除
void Delete_LinkList(LNode *L, int i)
{
int j = 0; LNode *p, *q;
p = L; q = L->next;
while (p->next != NULL && j < i) {
p = q; q = q->next; j++;
}
if (j != i) printf("i太大或i为0！！\n");
else {
p->next = q->next;
free(q);
}
}
（2）按值删除
void Delete_LinkList(LNode *L, int k)
{
LNode *p = L, *q = L->next;
while (q!=NULL && q->data!=key)
{
p = q; q = q->next;
}
if (q->data == key) {
p->next = q->next;
free(q);
}
else
printf("所要删除的结点不存在！！\n");
}
单链表的合并
LNode *Merage_LinkList(LNode *La, LNode *Lb)
{
LNode *Lc, *pa, *pb, *pc, *ptr;
Lc = La; pc = La; pa = La->next;
while (pa!=NULL && pb!=NULL)
{
if (pa->data < pb->data) {
pc->next = pa; pa = pa; pa = pa->next;
}
if (pa->data > pb->data) {
pc->next = pb; pc = pb; pb = pb->next;
}
if (pa->data == pb->data) {
pc->next = pa; pc = pa; pa = pa->next;
ptr = pb; pb = pb->next; free(ptr);
}
}
if (pa != NULL) pc->next = pa;
else pc->next = pb;
free(Lb);
return (Lc);
}
循坏链表
循坏链表是一种头尾相接的链表。其特点是最后一个结点的指针域指向链表的头结点，整个链表的指针域连接成一个环。
双向链表
双向链表指的是构成链表的每个结点中设立两个指针域，一个指向前驱的指针域prior，一个指向其直接后继的指针域next。
双向链表的结点及其类型定义
typedef struct Doublenode
{
ElemType data;
struct Doublenode *prior, *next;
}DoubleNode;
双向链表的基本操作
1：双向链表的插入：将值为e的结点插入双向链表中。
（1）：插入时仅仅指出直接前驱结点，钩链时必须注意先后次序“先右后左”。部分语句组如下：
S = (Double *)malloc(sizeof(DulNode));
S->data = e;
S->next = p->next; p->next->prior = S;
p->next = S; S->prior = p;
（2）插入时同时指出直接前驱点p和直接后继结点p,钩链时无须注意先后次序。部分语句组如下：
S = (Double *)malloc(sizeof(DulNode));
S->data = e;
p->next = S; S ->next=q;
S->prior = S; q->prior = S;
2：双向链表的结点删除：部分语句组如下：
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
一元多项式的表示和相加
一元多项式的表示
（1）顺序存储表示的类型
typedef struct {
float coef;/*系数部分*/
int expn;/*指数部分*/
}ElemType;
（2）链式存储表示的类型
typedef struct poly{
float coef;/*系数部分*/
int expn;/*指数部分*/
struct poly *next;
}Poly;
一元多项式的相加
（1）顺序存储表示的相加
typedef struct {
ElemType a[MAX_SIZE];
int length;
}Sqlist;
（2）链式存储表示的相加
Poly *add_poly(poly *La, poly *Lb)
{
ploy *Lc, *pc, *pa, *pb, *ptr; float x;
Lc = pc = La; pa = La->next;
while (pa != NULL && pb != NULL)
{
if (pa->expn < pb->expn) {
pc->next = pb; pc = pb;pa=pa->next
}
if (pa->expn > pb->expn) {
pc->next = pb; pc = pb; pb = pb->next
}
else {
x = pa->coef + pb->coef;
if (abs(x) <= 1.0e-6) {
ptr = pa; pa = pa->next; free(ptr);
ptr = pb; pb = pb->next; free(ptr);
}
else {
pc->next = pa; pa->coef = x;
pc = pa; pa = pa->next;
ptr = pb; pb = pb->next;
free(pb);
}
}
}
if (pa == NULL)pc->next = pb;
else pc->next = pa;
return (Lc);
}
；
；
，同时
，那么A = B。
，
，那么
。
，则CsA= {0})
。
个.； 
个。
)
形式，并将各因式x的系数化“+”(为了统一方便)；
的解可以根据各区间的符号确定。
型的不等式的解法。
q那么我们说，p是q的充分条件，q是p的必要条件。
。
