👨‍💻Zhenry's Notebook Set

Search

SearchSearch

数据结构笔记5-线性表-应用&案例

Nov 21, 20246 min read

参考网课数据结构-青岛大学-王卓-第四周

参考书籍《数据结构C语言版第二版》 中国工信出版集团 人民邮电出版社出版 严蔚敏 编著

应用

线性表的合并

效果：：集合的并集

void union(List &La, List Lb){
	La_len=ListLength(La);
	Lb_len=ListLength(Lb);
	for(i=1;i<=Lb_len;i++){   
		GetElem(Lb,i,e);
		if(!LocateElem(La,e))  //先判断不在表内，再插入。
		ListInsert(&La,++La_len,e); 
	}
}

有序表的合并——用顺序表

void MergeList_Sq(SqList LA, SqList LB, SqList &LC){
	pa=LA.elem;
	pb-LB.elem;
	LC.length=LA.length+LB.length;
	LC.elem=new ElemType[LC.length];
	pc=LC.elem;
	pa_last=LA.elem+LA.length-1;
	pb_last=LB.elem+LB.length-1;
	while(pa<=pa_last && pb<=pb_last){
		if(*pa<=*pb) *pc++=*pa++; // 依次摘取表中较小的
		else *pc++=*pb++;	
	}
	while(pa<=pa_last) *pc++=*pa++; // 当一个表已经到达末尾，后面的直接逐个连接即可。
	while(pb<=pb_last) *pc++=*pb++;
}

时间复杂度和空间复杂度都是：

Note

表达式 *pc++=*pa++ 可以分解为以下步骤：

  1. *pc 表示访问指针 pc 指向的值。
  2. *pa 表示访问指针 pa 指向的值。
  3. *pa++ 表示先将 pa 指针指向的值取出，然后将 pa 指针向前移动一个单位。
  4. *pc++ 表示先将 pc 指针指向的值取出，然后将 pc 指针向前移动一个单位。
  5. 最后将 *pa 的值赋给 *pc。

Note

  1. ++p (前缀递增):
    • 这种操作首先增加指针 p 的值，然后再返回增加后的指针。
    • 这意味着指针 p 被增加后，返回的指针是新的地址，指向增加后的内存位置。
    • 通常用于需要获取新指针值的场景。
  2. p++ (后缀递增):
    • 这种操作首先返回指针 p 的当前值，然后将指针 p 增加。
    • 这意味着指针 p 被增加前，返回的指针是原始地址，指向增加前的内存位置。
    • 通常用于需要在增加指针前使用原始指针值的场景。

有序表的合并——用链表

void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc){
	pa=La->next;
	pb=Lb->next;
	pc=Lc=La;  //用La的头结点作为Lc的头结点
	while(pa&&pb){
		if(pa->data<=pb->data){
			pc->next-pb;
			pc=pb;
			pb=pb->next;
		}
		pc->next-pa?pa:pb;//接入长的表的入剩余部分
		delete Lb;	
	}
}

时间复杂度； 空间复杂度。

Hint

此处的表长之和之所以不写成是因为无法确定两个表的长度是否关联关系。 如：

案例

实现两个多项式的相加

输入系数，并顺序存储。

求和。

输出结果。

实现稀疏多项式的运算

多项式的链式储存结构：两个数据域+一个指针域

typedef struct PNode{
	float coef;
	int expn;
	struct PNode *next;
}PNode, *Polynomial;

稀疏多项式的创建

void CreatePolyn(Polynomial &P, int n){
	P=new PNode;
	P->next=NULL; // 先建立一个有头结点的单链表
	for(i=1;i<=n;++i){ 
		s=new PNode; 
		cin>>s->coef>>s->expn; 
		pre=P; //pre是指向前驱节点的指针，初始值为P
		q=P->next; //q是指向当下考察的节点的指针
		while(q&&q->expn<s->expn){ //找到q：第一个指数大于输入项指数的节点地址
			pre=q;
			q=q->next;
		}
		s->next=q; //将输入项s插入到q之前
		pre->next=s;
	}
}

稀疏多项式的相加的思路

  1. 设置三个指针Pa，Pb，Pc
    1. 前两个指针分别指向两个待加表的首元节点
    2. 第三个指针初始指向Pa的头结点，表示求和之后的表
  2. 当Pa和Pb均未到达表尾时，循环比较两个指针指向节点的存储指数大小
    1. 当存储的指数大小相同
      1. 当存储的系数加和为0，删除Pa，Pb指向的节点。
      2. 当存储的系数加和不为0，修改Pa指向的节点的系数值，删除Pb指向的节点。
    2. 当存储的指数大小不同
      1. 将指数相对小的节点插入求和之后的表。
  3. 对长的那个链表，将非空多项式的剩余段插入Pc节点之后
  4. 释放Pb的头结点

图书管理系统

Book类型的定义

struct Book{
	char id[20];
	char name[50];
	int price;
};

顺序表的写法

typedef struct{
	Book *elem; //这里写指针是因为顺序表要传入一个Book类型的数组
	int length;
}SqList;

链表的写法

typedef struct{
	Book data; //这里写data是因为对一个节点来说只需要传入一个book类型的数据就够了
	struct LNode *next;
}LNode, *LinkList;

Graph View

Backlinks