线性表

定义与特点

由n个类型相同的数据元素组成的有限序列

存在第一个数据元素和最后一个数据元素

除了第一个外每个元素都有一个前驱

除了最后一个之外每个元素都有一个后继

顺序表示

代码实现

#define MAXSIZE 1024
typedef int ElemType;
typedef struct{
	ElemType *elem;  // 指向数据元素的基地址
	int length;  // 当前长度
}Sqlist;  // 顺序表

// 创建顺序表
Status InitList(SqList &L){
    // 分配空间
    L.elem = new ElemType[MAXSIZE];
    if (L.elem == NULL) exit(OVERFLOW);
    L.length = 0;
    return OK;
}// 时间复杂度 O(1)

// 销毁顺序表
Status DestroyList(SqList &L){
    if(L.elem != NULL) {
        delete []L.elem;  释放存储空间
        return OK;
    }
    return ERROR;
}// 时间复杂度 O(1)

// 获取线性表中的元素值
Status GetElem(SqList L, int i, ElemType &e){
	// 判断i值是否合理，若不合理，则返回ERROR
    if(i < 1 || i > L.length)  return ERROR;
    e = L.elem[i-1]; // 将结果存储在e中
    return OK;
}// 时间复杂度 O(1)

// 在线性表中查找值为e的数据
int LocateElem(SqList L, Elemtype e){
    for (int i = 0; i < L.length; i ++ ){
        if(L.elem[i] == e) 
            return i + 1;
    }
    return 0;
} // 时间复杂度 O(n)

// 在线性表的第i个数据元素的位置插入数据元素e
Status ListInsert(SqList &L, int i, ElemType e){
    if(i < 1 || i > L.length + 1) return ERROR;
    if (L.length >= MAXSIZE) return ERROR;
    for (int j = L.length - 1; j >= i - 1; j -- )
        L.elem[j + 1] = L.elem[j];
   	L.elem[i - 1] = e;
    L.length ++ ;
    return OK;
}// 时间复杂度 O(n)

// 在线性表L中的第i个元素删除
Status ListDelete(SqList &L, int i){
    if(i < 1 || i > L.length) retunr ERROR;
    for (int j = i; j < L.length; j ++ )  // 元素前移
        L.elem[j - 1] = L.elem[j];
   	L.length -- ; // 表长减1
    return OK;
}// 时间复杂度 O(n)

顺序表的优缺点

优点： 可随机访问， 存储空间使用紧凑

缺点： 插入删除需要大量移动元素， 预先分配空间按最大空间分配(可能造成空间的浪费，表的容量难以扩充)

链式表示

基础概念

用一组任意的存储单元存储线性表的数据元素

(可以不连续)

通过指针的指向来实现元素之间的相邻关系

额外存储一个后继节点的位置信息

每个数据元素存储的两部分信息合在一起被称为结点

• 数据元素内容被称作数据域
• 后继元素地址被称为指针域

最后一个节点的指针域为NULL

头节点：为了简化操作，在链表的第一个数据结点前附加的结点

首元结点：第一个存储数据元素的结点

无论链表是否为空，头指针都是非空的！！

代码实现

typedef struct LNode{
	ElemType data; // 数据域
	struct LNode *next;  // 指针域
}LNode, *LinkList;
// LinkList 为LNode类型的指针

// 链表的创建
Status InitList(LinkList &L){
    LNode* L = new LNode;
    // if(L == NULL) exit(OVERFLOW);
    L -> next = NULL;
    return OK;
}

// 链表的判空
int ListEmpty(LinkList L){
// 若L为空表，则返回1，否则返回0
    if (L->next == NULL)
        return 1;
   	else 
        return 0;
}

// 链表的长度
int ListLength(LinkList L){
	LNode* L = L->next;  // p指向第一个结点
    int i = 0;
    while(p){  // 遍历单链表，统计结点个数
        i ++ ;
        p = p->next;
    }
    return 1;
}

// 链表的取值
Status GetElem(LinkList L, int i, ElemType &e){
    LNode* p = L->next;
    int j = 1; // 从首元结点开始查找
    while(p){
        if(i == j){  // 找到
            e = p->data;
            return OK;
        }
        p = p -> next;
        j ++ ;
    }
    return ERROR;
}

// 链表的查找
int LocateElem(LinkList L, ElemType e){
    LNode* p = L->next;
    int i = 1;
    while(p){
        if(p->data == e) return i;
        p = p->next;
        i ++ ;
    }
    return 0;
}

// 链表查找(返回地址)
LNode* Find(LinkList L, ElemType e){
    LNode* p = L->next;
    while(p){
        if(p->data == e) return p;
        p = p->next;
    }
    return NULL;
}


// 链表的输出
void PrintList(LinkList L){
    LNode* p = L->next;
    while(p){
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

顺序表和链表对比

顺序表

• 表长固定，事先确定
• 插入删除少，按顺序访问多

链表

• 长度可以变化
• 频繁插入

单链表的就地逆置

void inverseLList(LinkList &L)
{
    LinkList p, q, temp = NULL;
    p = L->next;
    q = L->next->next;
    if (p == NULL || q == NULL)
    {
        return;
    }
    while (q != NULL)
    {
        temp = q->next;
        q->next = p;
        p = q;
        q = temp;
    }
    L->next->next = NULL; 
    L->next = p;
}

双向链表

typedef struct DLNode{
	ElemType data;
	struct DLNode *prior, *next;
}DLNode, *DLinkList;

// 插入
void InsertDLinkList(DLinkList p, Elemtype e){
    DLNode* s = new DLNode;
    s->data = e;
    s->next = p->next;
    s->prior = p;
    p->next = s;
    s->next->prior = s;
}

// 删除
void deleteDLinkList(DLinkList s){
    s->prior->next = s->next;
    s->next->prior = s->prior;
    delete s;
}

应用

有序表的合并

顺序表的合并

void mergeSqList(SqList &LA, SqList LB){
    int la = LA.length, lb = LB.length;
    for (int i = 0; i < lb; i ++ ){
        int has = false;
        for (int j = 0; j < la; j ++ ){
            if(LA.elem[j] == LB.elem[i]){
                has = true;
                break;
            }
        }
        if(has) continue;
        else{
            LA.elem[LA.length] = LB.elem[i];
            LA.length ++ ;
        }
    }
}

链表的合并

void mergeLinkList(LinkList &LA, LinkList LB)
{
	LinkList p = LA;
	while (p->next)
	{
		p = p->next;
	}
	LinkList s = LB->next;
	while (s)
	{
		LinkList t = LA->next;
		while (t)
		{
			if (t->data == s->data) break;
			t = t->next;
		}
		if (!t)
		{
			LinkList e = new LNode;
			e->data = s->data;
			e->next = NULL;
			p->next = e;
			p = e;
		}
		s = s->next;
	}
}

一元多项式的运算

多项式的加法

#include <stdio.h>
#include <stdlib.h>

typedef struct PNode
{
    int coeff;
    int expn;
    struct PNode *next;
} PNode, *Poly;
// 根据用户的输入，创建多项式
void createPoly(Poly &P, int n)
{
    P = new PNode;
    P->next = NULL;
    for (int i = 0; i < n; i++)
    {
        PNode *s = new PNode;
        scanf("%d%d", &s->coeff, &s->expn);
        PNode *pre = P;
        PNode *r = P->next;
        while (r && r->expn < s->expn)
        {
            pre = r;
            r = r->next;
        }
        s->next = r;
        pre->next = s;
    }
}
// 根据输出要求，打印多项式
void printPoly(Poly P)
{
    if (!P->next)
    {
        printf("0");
        return;
    }
    PNode *p = P->next;
    int count = 0;
    while (p)
    {
        if (count == 0 && p->expn != 0)
        {
            if (p->coeff != 0)
            {
                if (p->coeff == 1)
                    ;
                else if (p->coeff == -1)
                    printf("-");
                else
                    printf("%d", p->coeff);
                printf("x");

                if (p->coeff != 0 && p->expn >= 2)
                    printf("^%d", p->expn);
                p = p->next;
                count = 1;
            }
        }
        else if (count == 0 && p->expn == 0)
        {
            printf("%d", p->coeff);
            count = 1;
            p = p->next;
        }

        else
        {
            if (p->coeff != 0)
            {
                if (p->coeff == 1)
                    printf("+");
                else if (p->coeff == -1)
                    printf("-");
                else
                    printf("%+d", p->coeff);
                printf("x");
                if (p->coeff != 0 && p->expn >= 2)
                    printf("^%d", p->expn);
                p = p->next;
            }
        }
    }
    printf("\n");
}
// 多项式相加，P3=P1+P2
void addPoly(Poly P1, Poly P2, Poly &P3)
{
    PNode *p1 = P1->next;
    PNode *p2 = P2->next;
    P3 = new PNode;
    P3->next = NULL;
    PNode *p3 = P3;
    while (p1 && p2)
    {
        if (p1->expn == p2->expn)
        {
            int sum = p1->coeff + p2->coeff;
            if (sum) //和不为0
            {
                PNode *r = new PNode;
                r->coeff = sum;
                r->expn = p1->expn;
                r->next = NULL;
                p3->next = r;
                p3 = p3->next;
            }
            else //和为0
            {
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        else if (p1->expn < p2->expn)
        {
            PNode *r = new PNode;
            r->expn = p1->expn;
            r->coeff = p1->coeff;
            r->next = NULL;
            p3->next = r;
            p3 = p3->next;
            p1 = p1->next;
        }
        else
        {
            PNode *r = new PNode;
            r->expn = p2->expn;
            r->coeff = p2->coeff;
            r->next = NULL;
            p3->next = r;
            p3 = p3->next;
            p2 = p2->next;
        }
    }
    p3->next = p1 ? p1 : p2;
}

int main()
{
    int m, n;
    Poly p1, p2, p3;
    scanf("%d %d", &m, &n);
    createPoly(p1, m);
    createPoly(p2, n);
    printPoly(p1);
    printPoly(p2);
    addPoly(p1, p2, p3);
    printPoly(p3);
    return 0;
}

多项式的乘法

#include <stdio.h>
#include <stdlib.h> 

typedef struct PNode{
     int coeff;
     int expn;
     struct PNode *next;
} PNode, *Poly;

// 根据用户的输入，创建多项式
void createPoly(Poly &P, int n);
// 根据输出要求，打印多项式
void printPoly(Poly P);
// 多项式相乘，P3=P1*P2
void mulPoly(Poly P1, Poly P2, Poly &P3);

int main(){
	int m, n;
	Poly p1, p2, p3;
	scanf("%d %d", &m, &n);
	createPoly(p1, m);
	createPoly(p2, n);
	mulPoly(p1, p2, p3);
	printPoly(p1);
	printPoly(p2);
	printPoly(p3);	
	return 0;
}


void createPoly(Poly &P, int n)
{
	P = new PNode;
	P->next = NULL;
	while (n--)
	{
		Poly s = new PNode;
		scanf("%d %d", &s->coeff, &s->expn);
		if (s->coeff == 0) continue;
		Poly pre = P, q = P->next;
		while (q && q->expn < s->expn)
		{
			pre = q;
			q = q->next;
		}
		s->next = q;
		pre->next = s;
	}
}

void printPoly(Poly P)
{
	Poly s = P->next;
	while (s)
	{
		if (s != P->next && s->coeff > 0) printf("+");
		if (s->expn == 0)
		{
			printf("%d", s->coeff);
		}
		else if (s->expn == 1)
		{
			if (s->coeff != 1) printf("%d", s->coeff);
			printf("x");
		}
		else
		{
			if (s->coeff != 1) printf("%d", s->coeff);
			printf("x^%d", s->expn);
		}
		s = s->next;
	}
	printf("\n");
}

void addPoly(Poly P1, Poly P2, Poly &P3)
{
	Poly i = P1->next, j = P2->next, k = P3;
	k->next = NULL;
	while (i && j)
	{
		Poly t = new PNode;
		t->next = NULL;
		if (i->expn == j->expn)
		{
			if (i->coeff + j->coeff == 0)
			{
				i = i->next;
				j = j->next;
				continue;
			}
			t->coeff = i->coeff + j->coeff;
			t->expn = i->expn;
			i = i->next;
			j = j->next;
		}
		else if (i->expn < j->expn)
		{
			t->coeff = i->coeff;
			t->expn = i->expn;
			i = i->next;
		}
		else
		{
			t->coeff = j->coeff;
			t->expn = j->expn;
			j = j->next;
		}
		k->next = t;
		k = t;
	}
	while (i)
	{
		Poly t = new PNode;
		t->coeff = i->coeff;
		t->expn = i->expn;
		t->next = NULL;
		k->next = t;
		k = t;
		i = i->next;
	}
	while (j)
	{
		Poly t = new PNode;
		t->coeff = j->coeff;
		t->expn = j->expn;
		t->next = NULL;
		k->next = t;
		k = t;
		j = j->next;
	}
}

void cal(Poly P1, Poly P2, Poly &P3)
{
	Poly p2 = P2->next;
	Poly p = P3;
	while (p2)
	{
		Poly t = new PNode;
		t->expn = P1->expn + p2->expn;
		t->coeff = P1->coeff * p2->coeff;
		t->next = NULL;
		p->next = t;
		p = t;
		p2 = p2->next;
	}
}

void mulPoly(Poly P1, Poly P2, Poly &P3)
{
	P3 = new PNode;
	P3->next = NULL;
	Poly p1 = P1->next;
	while (p1)
	{
		Poly t = new PNode;
		t->next = NULL;
		cal(p1, P2, t);
		addPoly(t, P3, P3);
		p1 = p1->next;
	}
}