线性表
线性结构是最常用,最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且有限的。

线性表的逻辑结构
线性表的定义
由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);
}