线性表（数据结构及其算法，可当作复习资料）

本文主要是介绍线性表（数据结构及其算法，可当作复习资料），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

线性表

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

线性表的逻辑结构

线性表的定义

由n个数据元素（结点）组成的有限序列，该序列中所有结点具有相同的数据类型。

线性表的逻辑结构

线性表中的数据元素所代表的具体含义随具体应用的不用而不同，在线性表的定义中，只不过是一个抽象的表示符号。

线性表的抽象数据类型定义

ADT List{数据对象；数据关系；基本操作：InitList(&L)ListLength(L)......GetElem(L,i.&e)ListInsert(L,i.&e)......
}ADT List

线性表的顺序储存

线性表的顺序储存

顺序储存：把线性表的结点按逻辑结构依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。
除了用数组来存储线性表的元素外，还应该有表示线性表的长度属性，所以用结构类型来定义顺序表类型。`

#define OK 1
#define ERROR -1
#define MAX_SIZE 100
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);elsereturn (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);}elseprintf("所要删除的结点不存在！！\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);
}

这篇关于线性表（数据结构及其算法，可当作复习资料）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---